Программирование на типовых алгоритмических структурах с массивным параллелизмом

Авторы

  • П.К. Берзигияров

Ключевые слова:

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

Аннотация

Рассматривается новая технология программирования, основанная на ограниченных формах параллелизма — типовых алгоритмических структурах с массивным параллелизмом. Приведена классификация типовых алгоритмических структур. На основе анализа задач вычислительной газодинамики и квантовой химии предложены новые проблемно-ориентированные структуры. Рассмотрены различные механизмы композиции таких структур, применяемые в процессе разработки параллельных программ, а также вопросы их оптимизации. Описаны особенности программной реализации этих структур, включая механизмы обеспечения мобильности и эффективности, а также объектно-ориентированные методы повторного использования и специализации типовых алгоритмических структур. Представлена архитектура системы программирования.

Новые вычислительные технологии

Загрузки

Опубликован

2001-02-08

Выпуск

Том 2 (2001): Выпуск 1.

Раздел

Раздел 2. Программирование

Автор

П.К. Берзигияров

Институт проблем химической физики РАН
проспект академика Семенова, 1, 142432, Черноголовка

Библиографические ссылки

  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.