More Web Proxy on the site http://driver.im/

research-article

A Block-Based Mode Selection Model for SIMD/SPMD Parallel Environments

Authors:

M.J. AtallahAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 21, Issue 3

Pages 271 - 288

https://doi.org/10.1006/jpdc.1994.1059

Published: 01 June 1994 Publication History

Abstract

One of the challenges for parallel compilers and compiler-related tools is, given a machine-independent parallel language, to generate executable code for a variety of computational models, and to identify those specific parallel modes for which a program is well-suited. One portion of this problem, developing a method for estimating the relative execution time of a data-parallel algorithm in an environment capable of the SIMD and SPMD (MIMD) modes of parallelism, is presented. Given a data-parallel program in a language whose syntax is mode-independent and empirical information about instruction execution time characteristics, the goal is to use static source-code analysis to determine an implementation that results in an optimal execution time for a mixed-mode machine capable of SIMD and SPMD parallelism. Statistical information about individual operation execution times and paths of execution through a parallel program is assumed. A secondary goal of this study is to indicate language, algorithm, and machine characteristics that must be researched to learn how to provide the information needed to obtain an optimal assignment of parallel modes to program segments.

References

[1]

Aho, A., Sethi, R., and Ullman, J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA, 1986.

Digital Library

[2]

Antonio, J. K., Tsai, W. K., and Huang, G. M. A highly parallel algorithm for multistage optimization problems and shortest path problems. J. Parallel Distrib. Comput. 12, 3 (July 1991), 213-222.

Digital Library

[3]

Auguin, M., and Boeri, F. The OPSILA computer. In Consard, M. (Ed.), Parallel Languages and Architectures. Elsevier, Amsterdam/New York, 1986, pp. 143-153.

[4]

Auguin, M., and Boeri, F. Experiments on a parallel SIMD/SPMD architecture and its programming. Proc. France-Japan Artificial Intelligence and Computer Science Symp. '87. Nov. 1987, pp. 385-411.

[5]

Berg, T. B., Kim, S. D., and Siegel, H. J. Limitations imposed on mixed-mode performance of optimized phases due to temporal juxtaposition. J. Parallel Distrib. Comput. 13, 2 (Oct. 1991), 154-169.

Digital Library

[6]

Berg, T. B., and Siegel, H. J. Instruction execution trade-offs for SIMD vs. MIMD vs. mixed-mode parallelism. Proc. 5th Int'l Parallel Processing Symp. May 1991, pp. 301-308.

Digital Library

[7]

Browne, J., Azam, M., and Sobec, S. CODE: A unified approach to parallel programming. IEEE Software 6, 4 (July 1989), 10-17.

Digital Library

[8]

Browne, J. C., Tripathi, A. R., Fedak, S., Adiga, A., and Kapur, R. N. A language for specification and programming of reconfigurable parallel computation structures. Proc. 1982 Int'l Conf. Parallel Processing. Aug. 1982, pp. 142-149.

[9]

Bronson, E. C., Casavant, T. L., and Jamieson, L. H. Experimental application-driven architecture analysis of an SIMD/MIMD parallel processing system. IEEE Trans. Parallel Distrib. Systems 1, 2 (Apr. 1990), 195-205.

Digital Library

[10]

Bryson, A. E., and Ho, Y.-C. Applied Optimal Control. Hempshire, Washington, DC, 1975.

[11]

Chen, M., and Cowie, J. Prototyping Fortran-90 compilers for massively parallel machines. Proc. ACM SIGPLAN 1992 Conf. Programming Language Design and Implementation. June 1992, pp. 94-105.

Digital Library

[12]

Darema, F., George, D. A., Norton, V. A., and Pfister, G. F. A single-program-multiple-data computational model for EPEX/ FORTRAN. Parallel Comput. 7, 1 (Nov. 1988), 430-433.

[13]

David, H. A. Order Statistics. 2nd ed., Wiley, New York, 1981.

[14]

Dijkstra, E. A note on two problems in connexion with graphs. Numer. Math. 1 (1959), 269-271.

Digital Library

[15]

Dietz, H. G., and Klappholz, D. Refined C: A sequential language for parallel programming. Proc. 1985 Int'l Conf. Parallel Processing. Aug. 1985, pp. 442-449.

[16]

Dietz, H. G., Zaafrani, A., and O'Keefe, M. T. Static scheduling for barrier MIMD architectures. J. Supercomputing 5 (1992), 263-289.

Digital Library

[17]

Fineberg, S. A., Casavant, T. L., and Siegel, H. J. Experimental analysis of a mixed-mode parallel architecture using bitonic sequence sorting. J. Parallel Distrib. Comput. 11, 3 (Mar. 1991), 239-251.

Digital Library

[18]

Freund, R. F. Optimal selection theory for superconcurrency, Proc. Supercomputing '89. Nov. 1989, pp. 699-703.

Digital Library

[19]

Freund, R. F. SuperC or distributed heterogeneous HPC. Comput. Systems Engrg. 2, 4 (1991), 349-355.

[20]

Freund, R. F., and Siegel, H. J. Heterogeneous processing. Computer. Special Issue on Heterogeneous Processing. 26, 6 (June 1993), 13-17.

[21]

Giolmas, N., Watson, D. W., Chelberg, D. M., and Siegel, H. J. A parallel approach to hybrid range image segmentation. Proc. 6th Int'l Parallel Processing Symp. Mar. 1992, pp. 334-342.

Digital Library

[22]

Gupta, M., and Banerjee, P. Compile-time estimation of communication costs on multicomputers. Proc. 6th Int'l Parallel Processing Symp. Mar. 1992, pp. 470-475.

Digital Library

[23]

High Performance Fortran Forum. Draft: High performance Fortran language specification. High Performance Fortran Forum. Sept. 1992.

[24]

Hillis, W. D. and Steele, G. L., Jr. Data parallel algorithms. Comm. ACM 29, 12 (Dec. 1986), 1170-1183.

Digital Library

[25]

Hiranandani, S., Kennedy, K., Koelbel, C., Kremer, U., and Tseng, C.-W. An overview of the Fortran D programming system. Preliminary Proc. 4th Workshop on Languages and Compilers for Parallel Computing. Aug. 1991, pp. e1-e17.

[26]

Jamieson, L. H. Characterizing parallel algorithms. In Jamieson, L. H., Gannon, D. B., and Douglass, R. J. (Eds.). The Characteristics of Parallel Algorithms. MIT Press, Cambridge, MA, 1987, pp. 65-100.

[27]

Khokhar, A. A., Prasanna, V. K., Shaaban, M. E., and Wang, C.-L. Heterogeneous computing: challenges and opportunities. Computer, Special Issue on Heterogeneous Processing. 26, 6 (June 1993), 18-27.

[28]

Kim, S. D., Nichols, M. A., and Siegel, H. J. Modeling overlapped operation between the control unit and processing elements in an SIMD machine. J. Parallel Distrib. Comput., Special Issue on Modeling of Parallel Computers. 12, 4 (Aug. 1991), 329-342.

[29]

Midkiff, S. P., and Padua, D. A. Issues in the optimization of parallel programs. Proc. 1990 Int'l Conf. Parallel Processing. 2, Aug. 1990, pp. 105-113.

[30]

Moore, E. F. The shortest paths through a maze. Proc. Int'l Symp. Theory of Switching. 1957, pp. 285-292.

[31]

Nichols, M. A., Siegel, H. J., and Dietz, H. G. Data management and control-flow aspects of an SIMD/SPMD parallel language/compiler. IEEE Trans. Parallel Distrib. Systems. 4, 2 (Feb. 1993), 222-234.

Digital Library

[32]

Papoulis, A. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, New York, 1984.

[33]

Philippsen, M., Warschko, T., Tichy, W. F., and Herter, C. Project Triton: Towards improved programmability of parallel machines. Proc. 26th Hawaii Int'l Conf. System Sciences. Jan. 1993, pp. 192-201.

[34]

Qin, B., Sholl, H. A., and Ammar, R. A. Micro time cost analysis of parallel computations. IEEE Trans. Comput. 40, 5 (May 1991), 613-628.

Digital Library

[35]

Siegel, H. J., Armstrong, J. B., and Watson, D. W. Mapping computer vision related tasks onto reconfigurable parallel processing systems. Computer 25, 2 (Feb. 1992), 54-63.

Digital Library

[36]

Siegel, H. J., Schwederski, T., Nation, W. G., Armstrong, J. B., Wang, L., Kuehn, J. T., Gupta, R., Allemang, M. D., Meyer, D. G., and Watson, D. W. The design and prototyping of the PASM reconfigurable parallel processing system. In Zomaya, A. (Ed.). Parallel Computing: Paradigms and Applications. Chapman and Hall, London, UK, 1994, to appear.

[37]

Sunderam, V. S. Design issues in heterogeneous network computing, revised edition of proceedings. Proc. Workshop on Heterogeneous Processing (WHP '92). May 1992, pp. 101-112.

[38]

Tucker, L. W., and Robertson, G. G. Architecture and applications of the Connection Machine. Computer 21, 8 (Aug. 1988), 26-38.

Digital Library

[39]

Wang, M. C., Kim, S. D., Nichols, M. A., Freund, R. F., Siegel, H. J., and Nation, W. G. Augmenting the optimal selection theory for superconcurrency. Proc. Workshop on Heterogeneous Processing (WHP '92). May 1992, pp. 13-21.

[40]

Watson, D. W., Antonio, J. K., Siegel, H. J., and Atallah, M. J. Static program decomposition among machines in an SIMD/SPMD heterogeneous environment with non-constant mode switching costs. Proc. Workshop on Heterogeneous Processing (WHP '94). Apr. 1994, pp. 58-65.

[41]

Zima, H. P., Bast, H.-J., and Gerndt, M. SUPERB: a tool for semiautomatic MIMD/SIMD parallelization. Parallel Comput. 6, 1 (Jan. 1988), 1-18.

Cited By

Li YAntonio JSiegel HTan MWatson D(1997)Determining the Execution Time Distribution for a Data Parallel Program in a Heterogeneous Computing EnvironmentJournal of Parallel and Distributed Computing10.1006/jpdc.1997.134944:1(35-52)Online publication date: 10-Jul-1997
https://dl.acm.org/doi/10.1006/jpdc.1997.1349

Index Terms

A Block-Based Mode Selection Model for SIMD/SPMD Parallel Environments

Recommendations

Data Management and Control-Flow Aspects of an SIMD/SPMD Parallel Language/Compiler

Features of an explicitly parallel programming language targeted for reconfigurable parallel processing systems, where the machine's N processing elements (PEs) are capable of operating in both the SIMD and SPMD modes of parallelism, are described. The ...
Compile-time selection of parallel modes in an SIMD/SPMD heterogeneous parallel environment
SPMD Performance Analysis with Parallel Computing of Matlab
ICINIS '12: Proceedings of the 2012 Fifth International Conference on Intelligent Networks and Intelligent Systems

Matlab Parallel Toolbox is an effective tool for developing parallel program under a multi-processor environment, in which SPMD is the key statement for single instruction multiple data parallel implementation. However, when using spmd to achieve ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 21, Issue 3

Special issue on heterogeneous processing

June 1994

80 pages

ISSN:0743-7315

Editors:
Richard Freund
Naval Command, San Diego, CA
,
Vaidy Sunderam
Emory Univ., Atlanta, GA
,
Allan Gottlieb
New York Univ., New York, NY
,
Kai Hwang
Univ. of Southern California, Los Angeles
,
Sartaj Sahni
Univ. of Florida, Gainesville

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 1994

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li YAntonio JSiegel HTan MWatson D(1997)Determining the Execution Time Distribution for a Data Parallel Program in a Heterogeneous Computing EnvironmentJournal of Parallel and Distributed Computing10.1006/jpdc.1997.134944:1(35-52)Online publication date: 10-Jul-1997
https://dl.acm.org/doi/10.1006/jpdc.1997.1349

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents