Методология поддержки разработки эффективных параллельных программ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Бабкова, Варвара Вадимовна

• Бабкова, Варвара Вадимовна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Бабкова, Варвара Вадимовна

1. Введение.

2. Современное состояние технологий разработки параллельных программ.'.

3. Методология разработки параллельных программ в среде

Par Java.

3.1. Методология.

3.2. Оценка максимального потенциально достижимого ускорения.

3.3. Исследование гнезд циклов на возможность параллельного выполнения.

3.4. Преобразование гнезд циклов к виду, допускающему параллельное выполнение.

3.5. Распределение данных по узлам вычислительной сети.

3.6. Выбор операций обмена данными.

3.7. Оценка границ области масштабируемости и времени счета на реальных данных.

4. Механизм контрольных точек.

5. Программа моделирования интенсивных атмосферных вихрей.

Введение диссертации (часть автореферата) на тему «Методология поддержки разработки эффективных параллельных программ»

Актуальность. Одной из фундаментальных проблем параллельного программирования является проблема организации высокопродуктивных вычислений. Под высокопродуктивными вычислениями понимается комплексный подход к оценке качества высокопроизводительных программ, при котором учитывается не только время выполнения (эффективность), но и ресурсы, затраченные на разработку.

В настоящее время обеспечение высокой продуктивности существенно осложняется тем, что промышленная разработка прикладных параллельных программ для систем с распределенной памятью (кластеры) ведется на последовательных языках программирования с явным использованием обращений к коммуникационной библиотеке MPI, что связано с необходимостью ручной доводки программ (распределение данных, шаблоны коммуникаций и др.).

Актуальной является задача Создания технологических процессов и поддерживающих их инструментальных средств разработки параллельных программ позволяющих сократить неприемлемо высокие затраты времени и человеческих ресурсов на разработку приложений.

Конечно, наиболее кардинальным решением было бы создание нового языка высокого уровня, который обеспечил бы возможность разрабатывать параллельные программы с помощью оптимизирующих компиляторов. Но, к сожалению, исследования по высокоуровневым языкам параллельного программирования, проводившиеся, начиная с 1988 года, не увенчались успехом. Ни один из разработанных языков: HPF (и его Java-версия HPJava), С ilk, UPC (и его Java- версия Titanium) и ряд других менее известных языков, — не сумел решить поставленных перед ним задач. Основная причина неудачи в том, что, несмотря на значительные усилия, до сих пор не удалось разработать компиляторные технологии, позволяющие генерировать эффективный параллельный код. Отметим также, что надежды, связанные с созданием языков нового поколения XI0, Chapel, Fortress, даже, несмотря на то, что эти языки требуют более детально описывать структуру параллельной вычислительной среды, пока не оправдываются.

В отличие от разработки последовательных программ, где достаточно хорошо развиты технологические средства, в настоящее время не существует устоявшихся технологических процессов, позволяющих разрабатывать параллельные программы гарантированного качества. Кроме того, существующие инструментальные средства, как правило, базируются на использовании целевой аппаратуры, что связано со значительными накладными расходами, как по времени разработки, так и по используемым ресурсам.

Цель диссертационной работы. В ИСП РАН разрабатывается интегрированная инструментальная среда ParJava поддерживающая разработку параллельных программ. Целью диссертационной работы является исследование и создание методологии поддержки разработки параллельных программ и реализация ее в рамках среды ParJava, которая разрабатывается в Институте системного программирования РАН. Также целью диссертационной работы является реализация и апробирование методологии и соответствующих инструментальных средств на классе численных приложений, связанных с решением сильно нелинейных многокомпонентных трехмерных систем уравнений в частных производных смешанного типа.

Научная новизна. Научной новизной обладают следующие результаты диссертационной работы:

1. Исследована, разработана и апробирована методология поддержки создания масштабируемых параллельных программ решения задач математической физики в среде РапГауа.

2. Разработан и реализован в среде РапТауа механизм оптимальной организации контрольных точек.

3. В рамках предлагаемой методологии разработан масштабируемый параллельный алгоритм численного моделирования процессов и условий генерации интенсивных атмосферных вихрей (ИАВ) в модели трехмерной сжимаемой атмосферы.

Практическая значимость работы определяется тем, что разработанные инструментальные средства позволяют существенно уменьшить накладные расходы на разработку параллельных приложений, как по времени разработки, так и по используемым ресурсам. Кроме того, была реализована масштабируемая параллельная программа, моделирующая развитие интенсивных атмосферных вихрей в трехмерной сжимаемой сухоадиабатической атмосфере, которая позволила физикам проверять, исследовать и развивать теорию ИАВ.

Апробация работы и публикации

По теме диссертации опубликовано семь работ [1-7], в том числе две — в изданиях по перечню ВАК.

Основные положения и результаты диссертации докладывались и обсуждались на следующих научных конференциях:

• Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ: технологии параллельного программирования», г. Новороссийск, 18-23 сентября 2006.

• Международный научно-практический Семинар и Молодежная школа «Высокопроизводительные Параллельные Вычисления на Кластерных Системах» 12-17 декабря 2006 года.

• International Conference on the Methods of Aerophysical Research -Novosibirsk, 2007.

• Sixth International Conference on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia

• MTPP 2007 Parallel Computing Technologies First Russian-Taiwan Symposium Pereslavl-Zalesskii (Russia), September 2-3, 2007

• V Всероссийская межвузовская конференция молодых ученых, г. Санкт-Петербург , 15-18 апреля 2008 г .

• Международная научная конференция «Космос, астрономия и программирование» (Лавровские чтения), 20-22 мая 2008 г. Санкт-Петербург

Краткое содержание работы.

В первом разделе приводится обзор существующих инструментальных средств, таких как TAU (Университет штата Орегон и Исследовательский центр Juelich из Лос-Аламоса) и Paradyn (Университет штата Висконсин), поддерживающих реализацию, отладку и доводку параллельных программ. Как правило, эти системы предоставляют программисту наборы таких инструментов для анализа параллельных программ как профилировщик, трассировщик, инструменты для моделирования работы программы, визуализатор и др. Эти системы являются наборами различных инструментов, нацеленных на поддержку разработки параллельных программ. Однако в них не рассматриваются вопросы организации технологического процесса, позволяющего разрабатывать параллельные программы гарантированного качества, опираясь на их инструменты. Кроме того, разработанные в рамках этих систем инструментальные средства, как правило, базируются на использовании целевой аппаратуры, что связано со значительными накладными расходами, как по времени разработки, так и по используемым ресурсам.

В настоящее время разрабатывается большое количество параллельных приложений. Анализ масштабируемости приложений, опубликованных в журналах «Математическое моделирование» и «Computer Physics Communications» за 2005-2007 годы и приводимый в первом же разделе, показал, что в большинстве параллельных программ математической физики обеспечивается масштабируемость до 30 вычислителей.

Во втором разделе описана предлагаемая методология разработки параллельных программ и инструменты ParJava, поддерживающие этот процесс. Инструментальные средства среды ParJava позволяют увязать этапы процесса в единый технологический процесс, обеспечивающий итеративную разработку параллельной программы: если после очередного этапа выясняется невозможность достижения необходимого качества (масштабируемости), следует вернуться на предыдущий этап и скорректировать его результаты.

В разделе 3 рассматривается оптимизированный алгоритм реализации механизма контрольных точек в среде ParJava, позволяющий существенно сократить объемы сохраняемых данных и время на их сохранение.

Пользователь указывает в программе место сохранения данных с помощью специальных директив, за счет чего компилятор может выполнять анализ потока данных для выявления мертвых переменных, которые можно не сохранять в контрольной точке.

Результатом будет значительное уменьшение размеров сохраняемых данных в контрольной точке, и при этом еще будет уменьшение накладных расходов на сохранение.

Раздел 4 посвящен программе моделирования интенсивных атмосферных вихрей (ИАВ), как пример применения разработанного технологического процесса и инструментария на практике.

Возможность развития ИАВ (торнадо, ураганов) за счет начальной энергии мезовихрей впервые была ранее показана численно и были представлены результаты численного моделирования осесимметричного вихря в одномерной несжимаемой нестратифицированной атмосфере. В Институте физики Земли была реализована численная модель развития торнадо в трехмерной сжимаемой сухоадиабатической атмосфере. Большой объем вычислений для получения численного решения задач подобного типа потребовал реализации программы на высокопроизводительных вычислительных кластерах.

Для решения системы использовалась явная разностная условно-устойчивая схема второго порядка точности по времени и пространству; критерии ее устойчивости оказались близкими к явной схеме Маккормака.

Параллельная программа была реализована в среде ParJava с использованием библиотеки MPI. Инструменты среды ParJava позволили провести анализ параллельной программы и оптимизировать ее код.

В главе приведены описание алгоритма, графические результаты моделирования и график полученной масштабируемости.

Раздел 5 содержит выводы и направления дальнейших исследований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Бабкова, Варвара Вадимовна

6. Заключение

В работе получены следующие новые научные результаты:

4. Исследована, разработана и апробирована методология поддержки создания масштабируемых параллельных программ решения задач математической физики в среде РапГауа.

5. Разработан и реализован в среде РапГауа механизм оптимальной организации контрольных точек.

6. В рамках предлагаемой методологии разработан масштабируемый параллельный алгоритм численного моделирования процессов и условий генерации интенсивных атмосферных вихрей (ИАВ) в модели трехмерной сжимаемой атмосферы.

Предложенный технологический процесс позволяет увязать инструментальные средства среды Раг1ауа в единую технологическую цепочку, обеспечивающую итеративную разработку параллельной программы.

Отметим, что итеративная разработка предполагает достаточно большое число итераций, что может привести к большим накладным расходам по времени разработки и ресурсам. Итеративная разработка реальных программ, предложенная в данной работе, возможна благодаря тому, что большая часть процесса выполняется на инструментальном компьютере, в том числе за счет использования инструментов, базирующихся на интерпретаторе параллельных программ.

Предложенный технологический процесс был применен для разработки параллельной программы моделирования интенсивных атмосферных вихрей. Инструменты среды РапГауа позволили провести анализ параллельной программы и оптимизировать ее код, работая на инструментальной машине, не выходя каждый раз на кластер. Это существенно сократило сроки и необходимые ресурсы на разработку.

В будущем планируется совершенствование предложенного технологического процесса за счет разработки и реализации новых инструментов, в частности, подсистемы сбора и анализа трасс на интерпретаторе. Кроме того, планируется развитие полученных результатов по численному моделированию процесса рождения и эволюции торнадо и реализация новых реальных приложений.

Список литературы диссертационного исследования кандидат физико-математических наук Бабкова, Варвара Вадимовна, 2008 год

1. Аветисян А.И., Бабкова В., Гайсарян С.С., Губарь А.Ю. Рождение торнадо в теории мезомасштабной турбулентности по Николаевскому. Трехмерная численная модель в Par Java. // Журнал «Математическое моделирование». (Принято к печати)

2. А.И.Аветисян, В.В. Бабкова и А.Ю.Губарь. «Возникновение торнадо: трехмерная численная модель в мезомасштабной теории турбулентности по В.Н.Николаевскому»// «ДАН / Геофизика» , том 419, №4, с. 547-552.

3. Victor P. Ivannikov, Arutyun I. Avetisyan, Varvara V. Babkova, Alexander Yu. Gubar "Tornado arising modeling using high performance cluster systems" //

4. Sixth International Conference on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia

5. J.C. Adams, W.S. Brainard, J.T. Martin, B.T. Smith, J.L. Wagener. Fortran 95 Handbook. Complete ISO/ANSI Reference. Scientific and Engineering Computation Series. MIT Press, Cambridge, Massachusetts, 1997

6. B. Carpenter, G. Fox, H.K. Lee, S.B.Lim. Translation Schemes for the HPJava Parallel Programming Language // LNCS v. 2624, 2003, pp. 177-192

7. R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson, K.H. Randall, Y. Zhou. Cillc: An Efficient Multithreaded Runtime System. // Proc of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 1995, pp. 207-216

8. W. Chen, C. Iancu, K. Yelick. Communication Optimizations for Fine-grained UPC Applications //14th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2005.

9. B.L. Chamberlain, D. Callahan, H.P. Zima. Parallel Programmability and the Chapel Language // International Journal of High Performance Computing Applications, August 2007, 21(3): 291-312.

10. E. Allen, D. Chase, J. Hallett et al The Fortress Language Specification (Version 1.0) / cSun Microsystems, Inc., March 31, 2008 (262 pages)

11. А.Б.Горшков. «Алгоритм распараллеливания при численном решении двумерных стационарных уравнений Навье-Стокса с использованием неявной итерационной схемы» «Математическое моделирование», 2005, т. 17, № 11, с. 67-71.

12. И.В.Шариков, Д.М. Хрупов, С.Т. Суржиков. «Использование параллельных вычислений при численном моделировании взаимодействия воздушной лазерной плазмы с поверхностью» // «Математическое моделирование» 2006, т. 18,№8, с. 12-24.

13. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jaffrey D. Ullman. Compilers: principles, techniques, and tools. -2nd ed., Pearson Education Inc., 2007, c.836.

14. Jeremy Kepner, David Koester "HPCS Application Analysis and Assessment"// http://www.highproductivity.org/kepner-HPCS.htm21.http://www.totalviewtech.com/index.htm22.http://www.allinea.com/?page=48

15. В.П. Иванников, А.И. Аветисян, С.С. Гайсарян, В. А. Падарян. Прогнозирование производительности MPl-программ на основе моделей. // Журнал «Автоматика и телемеханика», 2007, N5, с. 8-17.

16. Хргиан А.Х. Физика атмосферы. М: Изд-во Московского Университета, 1986. С.240.

17. Nikolaevskiy V.N. Angular Momentum in Geophysical Turbulence: Continuum. Spatial Averaging Method . Dordrecht: Kluwer (Springer). 2003. P. 245.

18. Арсеньев C.A., Губарь А.Ю., Николаевский B.H. Самоорганизация торнадо и ураганов в атмосферных течениях с мезомасштабными вихрями. // ДАН, 2004, т.396, № 4, с.541-546.

19. Хаин А.П., Сутырин Г.Г. Тропические циклоны и их взаимодействие с океаном. Д.: Гидрометеоиздат, 1983. С.272.

20. Емцев Б.Т. Техническая гидромеханика. М.: Машиностроение, 1978. С.463.

21. Флетчер К. Вычислительные методы в динамике жидкостей (2т). М.: Мир, 1991. С.504, С.522.

22. Gilbert Anthony. Tornado With a Measured Intensity of T3 at Hill Head, Hampshire, 5, November 1999. // J.Meteorol. 2000. 25, N254. c.361-367.

23. Васильев B.A, Романовский Ю.М, Яхно В.Г. Автоволновые процессы. М.: Наука, 1987. С.240.

24. Е. S. Posmentier//Geophys. J. R.astr. Soc. (1967), 13, pp.487 501. 33.Sameer S. Shende, Allen D. Malony. The TAU Parallel Performance System //

25. The International Journal of High Performance Computing Applications,Volume 20, No. 2, Summer 2006, pp. 287-311

26. The Vampir System http://www.vampir.eu/index.html

27. The Cache Performance and Optimizations of Blocked Algorithms. Monica S. Lam, Edward E. Rothberg and Michael E. Wolf, Computer Systems Laboratory, Stanford University, CA 94305.

28. Самарский A.A., Гулин A.B. Численные методы. M.: Наука, 1989, 432 с.

29. Victor Ivannikov, Serguei Gaissaiyan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference. LNCS 2840. Sept. 2003, Venice, pp. 491-494.

30. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Analyzing Dynamic Properties of Parallel Program in ParJava Environment. // Proc. of the conf. Computer science and Information technologies. Sept. 2003, Yerevan, pp. 19-23.

31. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Estimating Scalability of a Parallel Program in ParJava Environment. // Russian -Indian Intern. Workshop on HPC, June 2003, Moscow, pp 29-30.

32. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Development of Scalable Parallel Programs in ParJava Environment. // Parallel CFD 2003, May 2003, Moscow, pp. 291 293.

33. А.И. Аветисян, С.С. Гайсарян, В.А. Падарян. Эффективный обмен данными на сетях JavaVM. // Тезисы докладов, XLIV Научная конференция МФТИ, Современные проблемы фундаментальных и прикладных наук, 4.VII. Ноябрь 2001, Москва Долгопрудный, стр. 29.

34. А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. Параллельное программирование с распределением по данным в системе ParJava. // Вычислительные методы и программирование. 2001 г., Москва, т. 2, №1. стр. 129-146.

35. А.И. Аветисян, В. А. Падарян. Библиотека интерфейсов и классов, расширяющих язык Java средствами разработки параллельных программ в модели SPMD. // Труды института системного программирования, 2001, Москва, т.2, стр. 49-64.

36. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Using symbolic execution of a parallel program to estimate its scalability. // «Parallel and Distributed Processing Techniques and Applications», Las Vegas. 2003.

37. Barton P. Miller etc, The Paradyn Parallel Performance Measurement Tools // Computer, Volume 28 , Issue 11 (November 1995) Pages: 37 46

38. Sabri Pllana, Thomas Fahringer, Performance Prophet: A Performance Modeling and Prediction Tool for Parallel and Distributed Programs // Parallel Processing, 2005. ICPP 2005 Workshops. International Conference Workshops 14-17 June 2005 Page(s): 509-516

39. D. A. Grove and P.D. Coddington, Communication Benchmarking and Performance Modelling of MPI Programs on Cluster Computers// Proceedings of the 18th International Parallel and Distributed Processing Symposium (1PDPS'04)

40. PGI CDK, Cluster Development Kit. Linux cluster development tools for 32-bit and 64-bit processor-based systems. http://www.pgroup.com/products/cdkindex.htm

41. Douglas Miles, Brent Leback and David Norton , Optimizing Application Performance on x64 Processor-based Systems with PGI Compilers and Tools// http://www.pgroup.com/lit/pgiarticletuning.pdf

42. PGHPF Compiler User's Guide, http://www.pgroup.eom/doc/p.ghpf u,g/hp(ug.htm

43. David F. Bacon, Susan L. Graham, Oliver J. Sharp Compiler Transformations for High-Performance Computing// ACM Computing Surveys, Vol. 26, No. 4, December 1994

44. Message Passing Interface http:/Avww-unix.mcs.anl.gov/mpi/

45. MPI: The Message Passing Interface http://parallel.ru/tcch/techdev/mpi.html

46. MPI Implementation List, http://www.lam-mpi.org/mpi/implementations/

47. Myricom home page, http://www.myri.com/

48. R. Baldoni. J.M. Hellary. M. Raynal, "Direct Dependency-Based Determination of Consistent Global Checkpoints". 1998.

49. K. Mani Chandy, Leslie Lamport. "Distributed Snapshots: Determining Global States of Distributed Systems". ACM Transactions on Computer Systems Vol.3, No. 1, February 1985.

50. Babaoglu and K. Marzullo. "Consistent global states of distributed systems: Fundamental Concepts and mechanisms". Distributed Systems, Ed. S. Mullender, Addison Wesley pp.55-96 1993.

51. Y.M. Wang, P.Y. Chung, I,J. Lin and W.K. Fuchs. "Checkpoint space reclamation for uncoordinated checkpointing in message-passing systems". In IEEE Transactions on Parallel and Distributed Systems, 6(5): 546-554, May 1995.

52. D.L. Russel. "State restoration in systems of communicating processes". In IEEE Transactions on Software Engineering, SE-6(2): 183-194, Mar. 1980.

53. D.Briatico A. Ciuffoltti, and L. Simoncini. "A distributed domino-effect free recovery algorithm. "In Proceeings of the IEEE International Symposium on Reliability, Distributed Software,a nd Databases, pp.207-215, Dec. 1984.

54. R. Neitzer, J. Xu. Necessary and sufficient conditions for consistent global snapshots. IEEE Transactions on Parallel and Distributed Systems. 6(2): 165-169, February 1995.

55. N. Nevis. W.K.Fuchs. "Coordinated Checkpointing Without Direct Coordination". 1998.

56. Sung E. Choi. Steven J. Deitz. "Compiler Support for Automatic Checkpointing."In Proceedings of the Sixteenth Annual International Symposium on High Performance Computing Systems and Applications, 2002.

57. L. Lamport. Time, clocks and ordering events in distributed systems. Communications of the ACM, 21(7):558-565, July 1978.

58. D.Briatico A. Ciuffoltti, and L. Simoncini. "A distributed domino-effect free recovery algorithm. "In Proceeings of the IEEE International Symposium on Reliability, Distributed Software,a nd Databases, pp.207-215, Dec. 1984.

59. Y.M. Wang, A.Lowry and W.K. Fuchs, "Consistent Global Checkpoints Based on Direct Dependency Tracking."Information Processing Letters, 50:223-230. 1994.

60. P.Cremonesi and C. Gennaro "Integrated Performance Models for SPMD Applications and MIMD Architectures."In IEEE Transactions on Parallel and Distributed Systems, vol. 12 No. 13, Dec. 2002

61. J. Hellary, A. Mostefaoui, R. Netzer, and M.Raynal. "Preventing useless checkpoints in distributed computations."In 16th IEEE Symposium of Reliable Distributed Systems, October 1997