The EM-4 under implicit parallelism
Pages 21 - 26
Abstract
The EM-4 is a supercomputer that offers very fast interprocessor communication and support for multithreading. In this paper we demonstrate that the EM-4, together with an automatic parallelization technique referred to as Data-Distributed Execution (DDE), offer a computing environment in which large portions of scientific code can be executed without the need for any explicit parallelism.
DDE exploits iteration-level parallelism in loops operating over arrays. It performs data-dependency analysis, based on which arrays are distributed over the different local memories. The code is then transformed to “follow” the data distribution by spawning each loop on all PEs concurrently but modifying its boundary conditions so that each operates mostly on the local subranges of the data, thus reducing remote accesses to a minimum. The approach has been tested on the EM-4 by implementing several benchmark programs representative of common scientific applications. The experiments show that high speedup is achievable by automatic parallelization of conventional Fortran-like programs.
References
[1]
Sakai, S., Yamaguchi, Y., Hiraki, K., Kodama, Y., Tuba, T. 'An Architecture of a Dataflow Chip Processor~ Proc. 15th Annual Int~ Symp. on Computer Arch., Jerusalem, Jun. 1989
[2]
Yamaguchi, Y., Sakai, S., Hiraki, K., Kodama, Y., Yuba, T. 'An Architectural Design of a Highly Parallel Dataflow Machine~ Information Processing 89, Ed G. Ritte~ Esevier Scientific Pub~shers, North-Holland, 1989
[3]
Bic, L. 'A Process-Oriented Model for Efficient Execution of Dataflow Programs ~ ~ Parallel and Distributed Computing, Vol. 8, No. 1, pp. ~2-51, Jan 1990
[4]
Bic, L., Roy, J.M.A., Nagel, M. 'Exploiting iteration-Level Paralle~sm in Dataflow Programs ~ 12th Int~ Conf. on Distributed Computing Systems, Yokohama, Japan, Jun. 1992
[5]
Sakai, S., Hiraki, K., Yamaguchi, Y., Kodama, Y., Yuba, T. 'Pipeline Optimization of a Dataflow Machine~ Advanced Topics in Data-Flow Computing, Prentice-Hal~ Eds. J-L. Gaudiot and L. Bic, 1991
[6]
Arvind, Bic, L., Ungere, T. 'Evolution of Data- Flow Computers~ Advanced Topics in Data-Flow Computing, Prentice-Hal~ Ed. j-L. Gaudiot and L. Bic, 1991
[7]
Arvind, Iannucci, R.A. 'Two Fundamental Issues in Mu~iprocessing~ Proc. DFLVR Conf. on Para~ lel Processing in Science and Enginee~n~ Bonn- Bad Godesberg, Germany, Inn. 1987
[8]
Arvind, Thomas, R.E. 'I-Structures: An Efficient Data Type for Functional Languages ~ Computer Science Tech. Rep. TM-178, MIT, Camb~dge, MA, Sep. 1980
[9]
Sato, M., Kodama, Y., Sakai, S., Yamaguchi, Y., and Koumura, Y. 'Thread-Based Programming for the EM-4 Hybrid Dataflow Machine~ Proc. 19th Annual Int'l Syrup. on Computer Arch., Gold Coast, Australia, May 1992
[10]
Cytron, R., Ferrante, J. 'What~ in a Name? -or- The Value of Renaming for Paralle~sm Detection and Storage Allocation~ Proc. Int7 Conf. on Pa~ allel Processing, Aug 198~ pp. 19-27
[11]
Ackerman, W.B., 'Data Flow Languages~ IEEE Compute~ Feb. lgS~ pp. 15-25
[12]
W. P. Crowley, C. P. Henderson, T. E. Rudy 'The SIMPLE Code~ UCID 17715 Lawrence Livermore Laboratory February 1978
[13]
McMahon, F.H. 'The Livermore Fo~ran Kernel: A Computer Test of the Nume~cal Performance Range~ UCRL-5374~ Lawrence Livermore National Laboratory, Livermore, CA, Dec. 1986
[14]
Padua, D.A., Kuck, D.J., Lawrie, D.H. 'Highspeed Mu~iprocessors and Compilation Techniques~ IEEE Trans. Computers, Sep. 1980, pp. 763-776
[15]
Padua, Wolfe, M. 'Advanced Compiler Organization~ Comm. A CM, Dec. 1989, pp. 1184-1201
Index Terms
- The EM-4 under implicit parallelism
Recommendations
Complementing user-level coarse-grain parallelism with implicit speculative parallelism
MICRO-44: Proceedings of the 44th Annual IEEE/ACM International Symposium on MicroarchitectureMulti-core and many-core systems are the norm in contemporary processor technology and are expected to remain so for the foreseeable future. Programs using parallel programming primitives like PThreads or OpenMP often exploit coarse-grain parallelism, ...
Thread-based programming for the EM-4 hybrid dataflow machine
Special Issue: Proceedings of the 19th annual international symposium on Computer architecture (ISCA '92)In this paper, we present a thread-based programming model for the EM-4 hybrid dataflow machine, where parallelism and synchronization among threads of sequential execution are described explicitly by the programmer. Although EM-4 was originally ...
Nonnumeric search results on the EM-4 distributed-memory multiprocessor
Supercomputing '94: Proceedings of the 1994 ACM/IEEE conference on SupercomputingNumeric scientific problems have been the main focus of supercomputing as their numerous implementations on various multiprocessors indicate. Nonnumeric problems on the other hand have received very little attention for parallel implementation due to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1993 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 1993
Check for updates
Qualifiers
- Article
Conference
ICS93
Sponsor:
Acceptance Rates
Overall Acceptance Rate 629 of 2,180 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 209Total Downloads
- Downloads (Last 12 months)31
- Downloads (Last 6 weeks)7
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in