Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

General purpose optimization technology

  • Conference paper
  • First Online:
Languages and Compilers for Parallel Computing (LCPC 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1033))

Abstract

A necessary condition for the establishment, on a substantial basis, of a parallel software industry would appear to be the availability of technology for generating transportable software, i.e. architecture independent software which delivers scalable performance for a wide variety of applications on a wide range of multiprocessor computers. We are in the process of developing H-BSP — a general purpose parallel computing environment for developing transportable algorithms. H-BSP is based on the Bulk Synchronous Parallel Model (BSP), in which a computation involves a number of supersteps, each having several parallel computational threads that synchronize at the end of the superstep. The BSP Model deals explicitly with the notion of communication among computational threads and introduces parameters g and L that quantify the ratio of communication throughput to computation throughput, and the synchronization period, respectively. These two parameters, together with the number of processors and the problem size, are used to quantify the performance and, therefore, the transportability of given classes of algorithms across machines having different values for these parameters. Recently algorithm designers have developed algorithms for a number of regular problems that are provably optimal as functions of g and L, but for many irregular problems developing optimal solutions will depend on the compiler and the run-time system taking advantage of the g and L values for the intended target. This paper describes the unbundled compiler technology and, particularly, the optimization technology it provides, that facilitates the development of such a parallel computer environment.

Research supported in part by ARPA Contract Nr. F19628-92-C-0113.

Research supported in part by ARPA Contract Nr. F19628-92-C-0113 and a grant from the National Science Foundation, NSF-CDA-9308833

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Aggarwal, A. Chandra and M. Snir Communication Complexity of PRAMs, Theoretical Computer Science, 71(1990), pp 3–28.

    Article  Google Scholar 

  2. S. P. Amarasinghe and M. Lam Communication Optimization and Code Generation for Distributed Memory Machines Proceedings of the ACM SIGPLAN'93, Conference on Programming Language Design and Implementation, June 1993

    Google Scholar 

  3. R.H. Bisseling and W. F. McColl Scientific Computing on Bulk Synchronous Parallel Architectures Preprint 836, Dept. of Mathematics, Utrecht University, December 1993

    Google Scholar 

  4. T. Cheatham, H. Gao, and D. Stefanescu A Suite of Analysis Tools Based on a General Purpose Abstract Interpreter, Proceedings of the International Conference on Compiler Construction, Edinburgh, April 1994

    Google Scholar 

  5. T. Cheatham, A. Fahmy, D. Stefanescu, and L. Valiant Bulk Synchronous Parallel Computing — a Paradigm for Transportable Software, Proceedings HICSS95, Vol II, pp 268–275.

    Google Scholar 

  6. T. Cheatham, A. Fahmy, and D. Stefanescu Supporting Multiple Evolving Compilers, SEKE'94, Riga, June 1994

    Google Scholar 

  7. T. Cheatham, Models, Languages, and Compiler Technology for High Performance Computers, Workshop on Mathematical Foundations of Computer Science, Kosice, Slovakia, Lecture Notes on Computer Science, Springer Verlag, August 1994.

    Google Scholar 

  8. T. Cheatham, A. Fahmy, and D. Stefanescu H-BSP — A General Purpose Parallel Computing Environment, Proceedings of IFIP World Congress, Vol. 1, pp 515–520, Hamburg, August 1994

    Google Scholar 

  9. T. Cheatham, A. Fahmy, and D. Stefanescu A Compiler for BSP-L, A Programming Language for the Bulk Synchronous Processing Model, Proceedings of IEEE TENCON'94, Singapore, August 1994

    Google Scholar 

  10. T.Cheatham The Unbundled Compiler, Technical Report, Harvard University, 1993

    Google Scholar 

  11. D. E. Culler, et al. Introduction to Split-C EECS, UC Berkeley, Berkeley, CA 94720, April 1993

    Google Scholar 

  12. A. Geist, et al. PVM3 Users Guide and Reference Manual ORNL/TM-12187, Oak Ridge National Laboratory, Tennessee, May 1993

    Google Scholar 

  13. A.V.Gerbessiotis and L.G.Valiant Direct bulk-synchronous parallel algorithms, Third Scandinavian Workshop on Algorithm Theory, vol. 621, pages 1–18, Springer Verlag, 1992. Extended version in Journal of Parallel and Distributed Computing, 22, pp. 251–267, 1994

    Google Scholar 

  14. E. Heinz, M. Phillipson Synchronization Barrier Elimination in Synchronous FORALLs TR13/93 University of Karlsruhe, April 1993

    Google Scholar 

  15. S. Hiranandani, K.Kennedy, C.Tseng Compiling Fortran D for MIMD Distributed-Memory Machines Communications of the ACM, August 1992

    Google Scholar 

  16. J.W.Hong and H.T.Kung I/O Complexity: The Red-Blue Pebble Game Proceedings of the 13-th ACM Symposium on Theory of Computing, pp 326–333, 1981

    Google Scholar 

  17. V.Kathail and D. Stefanescu A Data Mapping Parallel Language TR-21-89, Center for Research in Computing Technology, Harvard University, December 1989

    Google Scholar 

  18. W. F. McColl General Purpose Parallel Computing, In A.M. Gibbons and P.Spirakis, editors, Lectures on Parallel Computation, Proc. 1991 ALCOM Spring School on Parallel Computation, vol 4 of Cambridge International Series on Parallel Computation, Cambridge University Press, 1993

    Google Scholar 

  19. W. F. McColl BSP Programming In DIMACS Series of Discrete Mathematics and Theoretical Computer Science, 1994. To appear.

    Google Scholar 

  20. W. F. McColl Scalable Parallel Computing: A Grand Unified Theory and its Practical Development Proceedings of IFIP World Congress, Vol. 1, pp 539–546, Hamburg, August 1994

    Google Scholar 

  21. R. Miller and J. Reed The Oxford BSP Library. Users Guide. Version 1.0, Oxford University, 1994

    Google Scholar 

  22. M. Paterson. Manuscript. 1994

    Google Scholar 

  23. J. P. Singh, E. Rothberg, and A. Gupta Modeling Communication in Parallel Algorithms: A Fruitful Interaction Between Theory and Systems Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1994.

    Google Scholar 

  24. D. Stefanescu and Y. Zhou An Equational Framework for the Abstract Analysis of Functional Programs, Proceedings of ACM Conference on Lisp and Functional Programming, Orlando, 1994.

    Google Scholar 

  25. L. G. Valiant A Bridging Model for Parallel Computation Communications of the ACM, 33(8):103–111, 1990

    Article  Google Scholar 

  26. L. G. Valiant A combining mechanism for parallel computers. In Parallel Architectures and Their Efficient Use, Proceedings of First Heinz Nixdorf Symposium, Paderborn, Germany, November 1992. Lecture Notes in Computer Science Vol678, Springer-Verlag, 1–10.

    Google Scholar 

  27. L. G. Valiant Why BSP Computers? Proceedings of the 7-th International Parallel Processing Symposium, pp 2–5, IEEE Computer Society Press, Los Alamitos, CA, 1993

    Google Scholar 

  28. M.E.Wolf and M.Lam A Data Locality Optimizing Algorithm, Conference on Programming Languages Design and Implementation'91, 1991

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Aiken Computation Laboratory, Harvard University, 33 Oxford St, 02138, Cambridge, MA

    Thomas Cheatham, Amr Fahmy & Dan C. Stefanescu

Authors
  1. Thomas Cheatham
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amr Fahmy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dan C. Stefanescu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Chua-Huang Huang Ponnuswamy Sadayappan Utpal Banerjee David Gelernter Alex Nicolau David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cheatham, T., Fahmy, A., Stefanescu, D.C. (1996). General purpose optimization technology. In: Huang, CH., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1995. Lecture Notes in Computer Science, vol 1033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014215

Download citation

  • DOI: https://doi.org/10.1007/BFb0014215

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60765-6

  • Online ISBN: 978-3-540-49446-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation