Programming using standardized algorithmic structures with massive parallelism

Authors

  • P.K. Berzigiyarov

Keywords:

параллельное программирование
типовые алгоритмические структуры
оптимизация программ
массивный параллелизм

Abstract

A new technology of programming based on standardized algorithmic structures with massive parallelism is considered. A classification of such structures is given. New problem-oriented structures are proposed on the basis of our analysis of problems in the field of computational gas dynamics and quantum chemistry. Various mechanisms for composition of such structures and their optimization are discussed. Some special features of implementation of these structures are described, including the mechanisms for providing the portability and efficiency as well as object-oriented methods for their reusing and specializing. The architecture of the programming system under consideration is presented.

New computational technologies

Downloads

Published

2001-02-08

Issue

Vol. 2 (2001): Issue 1.

Section

Section 2. Programming

Author Biography

P.K. Berzigiyarov

Institute of Problems of Chemical Physics of RAS

References

  1. Берзигияров П.К. Формальное конструирование программ на базе алгоритмических структур с массовым параллелизмом: статическая конвейеризация алгоритмов «разделяй-и-властвуй» // Тез. докл. VI-й конференции «Транспьютерные системы и их применение». Вестник Российской транспьютерной ассоциации. Домодедово, 1996. 46.
  2. Берзигияров П.К., Султанов В.Г. Параллельное моделирование рэлей-тейлоровских гидродинамических неустойчивостей // Вестн. Моск. ун-та. Вычисл. матем. Киберн. 2001. № 1. 1-10.
  3. Грибов Л.А., Муштакова С.П. Квантовая химия. М.: Гардарики, 1999.
  4. Aldinucci M., Coppola M., Danalutto M. Rewriting skeleton programs: how to evaluate the data-parallel stream-parallel tradeoff // Proc. of International Workshop on Constructive Methods for Parallel Programming. Technical Report MIP-9805. University of Passau. Passau, 1998.
  5. Bacci B., Danelutto M., Pelagatti S., Vanneschi M. SkIE: an heterogeneous environment for HPC applications // Parallel Computing. 1999. 25, N 13-14. 1827-1852.
  6. Balay S., Gropp W.D., McInnes L.C., Smith B.F. Efficient management of parallelism in object-oriented numerical software libraries // Modern Software Tools in Scientific Computing / Arge E., Bruaset A.M., Langtangen H.P. (Eds.). Birkhauser Press: 1997. 163-202.
  7. Berzigyarov P.K. Static Pipelines for Divide-and-Conquer Functions: Transformations and Analysis. Preprint IVTAN, N 8-391. Moscow, 1995.
  8. Bird R.S. An introduction to the theory of lists // Logic of Programming and Calculi of Discrete Design / Broy M. (Ed.). NATO ASI Series. 1987.
  9. Boglaev Yu.P. On the parallel and perpendicular computations // Parallel Algorithms and Applications. 1994. 3. 89-107.
  10. Botorog G.H., Kuchen H. Skil: an imperative language with algorithmic skeletons for efficient distributed programming // Proc. of the Fifth International Symposium on High Performance Distributed Computing (HPDC-5). IEEE Computer Society. 1996. 243-252.
  11. Botorog G.H., Kuchen H. Algorithmic skeletons for adaptive multigrid methods // LNCS. 1995. 980. 27-41.
  12. Bratvold T.A. Skeleton-based parallelization of functional programs: PhD thesis. Dept. of Computing and Electrical Engineering. Heriot-Watt University. Edinburgh, 1994.
  13. Campbell D.K. G. Towards the Classification of Algorithmic Skeletons. Technical Report YCS 276. Department of Computer Science, University of York. York, 1996.
  14. Cole M.I. Algorithmic Skeletons: Structured Management of Parallel Computation. Massachusetts, Cambridge. Boston: MIT Press, 1989.
  15. Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software. Reading-Amsterdam-Tokyo: Addison-Wesley, 1995.
  16. Gorlatch S., Bischof H. A generic MPI implementation for a data-parallel skeleton: formal derivation and application to FFT // Information Processing Letters. 1998. 8, N 4. 447-458.
  17. Gropp W., Huss-Ledermann S., Lumsdaine A., Lusk E., Nitzberg B., Saphir W., Snir M. MPI: The Complete Reference. Vol. 2. The MPI Extensions. Boston: MIT Press, 1998.
  18. Darlington J., Field A.J., Harrison P.G., Kelly P.H. J., Sharp D.W. N., Wu Q., While R.L. Parallel programming using skeleton functions // In: Parallel Architectures and Languages. Berlin: Springer-Verlag, 1993. 146-160.
  19. Darlington J., Guo Y., To H.W., Yang J. SPF: Structured parallel Fortran // Proc. of the Sixth Parallel Computing Workshop. Japan. Kawasaki, 1996. 1-6.
  20. Decyk V. K. Skeleton PIC Codes for Parallel Computers. Physics Department. UCLA. Los Angeles, 1994.
  21. MacDonald S., Szafron D., Schaeffer J., Bromling S. Generating parallel program frameworks from parallel design patterns // Proc. of EuroPar’2000. Berlin: Springer-Verlag, 2000. 95-104.
  22. MacDonald S., Szafron D., Schaeffer J., Bromling S. From patterns to frameworks to parallel programs // IEEE Concurrency. 1999. 7, N 1-4. 1-21.
  23. MacDonald S., Szafron D., Schaeffer J. Object-oriented pattern-based parallel programming with automatically generated frameworks // Proc. of the Fifth USENIX Conference on Object-Oriented Tools and Systems. San Diego, 1999. 29-43.
  24. MacDonald S. Parallel Object-Oriented Pattern Catalogue. Draft. 1998.
  25. MacDonald S. Design patterns in enterprise // Proc. of CASCON’96. Toronto, 1996. 1-10.
  26. Massingill B.L., Chandy K.M. Parallel Program Archetypes. Technical Report CS-TR-96-28. California Institute of Technology. Pasadena, 1996.
  27. McInnes L.C., Smith B.F. PETSc 2.0: A case study of using MPI to develop numerical software libraries // Proc of the 1995 MPI Developers Conference. University of Notre Dame. Notre Dame, 1995. 1-16.
  28. Mou Z.G., Hudak P. An algebraic model for divide-and-conquer and its parallelism // Journal of Supercomputing. 1988. N 2. 257-278.
  29. Osoba F.O., Rabhi F.A. A parallel multigrid skeleton using BSP // Proc. of EuroPar’98. LNCS. Berlin: Springer-Verlag. 1998. 1-6.
  30. Pelagatti S. Structured Development of Parallel Programs. London-Bristol: Taylor&Francis, 1997.
  31. Pelagatti S. A methodology for the development and the support of massively parallel programs: PhD thesis. Dipartimento di Informatica Universita’ di Pisa. Pisa, 1993.
  32. Reynders J.V. W. et al. POOMA: A framework for scientific simulations on parallel Architectures // In: Parallel Programming using C++. Cambridge: MIT Press, 1996. 1-43.
  33. Serot J., Ginhac D., Derutin J-P. Skipper: A skeleton-based parallel programming environment for real-time image processing applications // LNCS. 1999. 1662, 296-305.
  34. Siu S. Openness and Extensibility in Design-Pattern-Based Parallel Programming Systems. Master of Applied Science Thesis. University of Waterloo. Ontario. Canada. Waterloo, 1996.
  35. Siu S., De Simone M., Goswami D., Singh A. Design patterns for parallel programming // Parallel and Distributed Processing Techniques and Applications. California. Pasadena, 1996. 230-240.
  36. Skillicorn D.B., Hill J., McColl B. Questions and answers about BSP // Scientific Programming. 1997. 6, N 3. 249-274.
  37. Skillicorn D.B. Models for practical parallel computation // International Journal of Parallel Programming. 1991. 20, N 2. 133-158.
  38. Skillicorn D.B. The Bird-Meertens formalism as a parallel programming model // NATO ASI Workshop on Software for Parallel Computation. Italy. Cetraro. June 1992. Berlin: Springer-Verlag, 1993. 1-14.
  39. Skillicorn D.B., Danelutto M., Pelagatti S., Zavanella A. Optimizing data-parallel programs using the BSP cost model // LNCS. 1998. 1470. 698-706.
  40. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: The Complete Reference. Vol. 1. The MPI Core. Boston: MIT Press, 1998.
  41. Singh A., Schaeffer J., Szafron D. Views on template-based parallel programming // Proc. of CASCON’96. Toronto, 1996. 1-12.
  42. To H.W. Optimizing the Parallel Behavior of Combinations of Program Components: PhD thesis. University of London Imperial College of Science, Technology and Medicine, Department of Computing. London, 1995.
  43. Yabe T., Ishikawa T., Wang P.Y. A universal solver for hyperbolic equations by cubic-polynomial interpolation II. Two- and three-dimensional solvers // Computer Physics Communications. 1991. N 66. 233-242.
  44. Zavanella A. Optimizing skeletal stream parallelism on a BSP computer // LNCS. 1999. 1685. 853-857.
  45. Zavanella A., Pelagatti S. Using BSP to optimize data-distribution in skeleton programs // LNCS. 1999. 1593. 613-622.
  46. Valiant L.G. A bridging model for parallel computation // Communications of the ACM. 1990. 33, N 8. 103-111.