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

• Падарян, Вартан Андроникович
• кандидат физико-математических наук
• 2005

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

1. Введение.

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

3. Модель параллельной программы и ее интерпретация.

3.1 Описание модели.

3.2 Моделирование коммуникационных функций.

3.3 Интерпретация модели.

Интерпретация базовых блоков.

3.4 Частичная интерпретация.

3.5 Оценка времени выполнения программы.

3.6 Интерпретация коммуникационных функций при оценке времени работы программы.

3.7 Точность оценки времени.

4. Описание программного обеспечения.

4.1 Работа среды ParJava при построении оценки времени выполнения параллельной программы.

4.2. Построение статических моделей классов.

4.3. Компоновка модели.

4.4. Интерпретатор параллельной программы.

4.5 Обработка исключительных ситуаций в интерпретаторе.

4.6. Редукция вершин модели.

4.7. Частотное профилирование параллельной программы.

4.8. Инструментирование исходного кода.

4.9. Сбор частотного профиля и трассы параллельной программы.

4.10. Коррекция.

4.11. Анализ контекста базовых блоков.

4.12. Получение оценок времени работы базовых блоков.

4.13. Ограничения реализации.

5. Результаты численных экспериментов.

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

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

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

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

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

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

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

1 вычислить динамические характеристики, используя точное знание параметров кластера.

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

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

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

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

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

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

Среда ParJava, разработанная в ИСП РАН, используется в учебном процессе кафедры системного программирования факультета ВМиК МГУ и кафедры системного программирования ФУПМ МФТИ. ParJava используется как средство разработки в проекте по созданию библиотеки методов параллельного символьного решения задач линейной алгебры PolyCalc (Тамбовский государственный университет). Проект ParJava поддержан грантами РФФИ и Минпромнауки.

Среда ParJava доступна по http://www.ispras.ru/groups/ctt/parjava.html. Апробация работы.

Основные результаты работы опубликованы в статьях [1] - [14]. Результаты работы обсуждались на следующих конференциях и семинарах:

1. Международная конференция «Avances en la Ciencia de la Computacion, ENC'04», Colima, Mexico. Septiembre 20 - 24, 2004.

2. Всероссийская научная конференция «Научный сервис в сети Интернет», Новороссийск, 20 - 25 сентября, 2004.

3. Конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.

4. Международная конференция «The 10th EuroPVM/MPI conference», Venice, Italy. September 29 - October 2, 2003;

5. Международная конференция «Computer science and Information technologies», Yerevan. September 22 - 26,2003;

6. Международная конференция «Вычислительная механика и современные прикладные программные системы», Владимир. 30 июня - 5 июля, 2003;

7. Международная конференция «Parallel and Distributed Processing Techniques and Applications», Las Vegas. June 23 - 26, 2003;

8. Международный семинар «Russian - Indian Intern. Workshop on НРС», Москва. 16 — 20 июня, 2003;

9. Международная конференция «Parallel Computational Fluid Dynamics», Москва. 13 — 15 мая, 2003;

10. Конференция «Современные проблемы фундаментальных и прикладных наук», Москва - Долгопрудный. 23 - 30 ноября, 2001.

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

В разделе 3 рассматривается модель параллельной программы и способ ее интерпретации. Предлагается строить модель параллельной Java-программы на основе ее абстрактного синтаксического дерева (АСД). Вводится набор базовых коммуникационных операций, коммуникационные функции MPI рассмотрены как композиция базовых операций. Определяется интерпретация модели параллельной программы. Вводится понятие редукции вершины модели параллельной программы, а также понятие корректности редукции. Сформулированы и доказаны достаточные требования корректности редукции. Рассмотрены особенности интерпретации для того случая, когда вычисляется оценка времени работы параллельной программы. Предложена методика предварительной оценки времени работы базовых блоков Java-программы. Заканчивается раздел набором утверждений об абсолютной и относительной погрешностях прогноза времени работы параллельной программы, получаемого при ее интерпретации. Все утверждения сопровождаются доказательствами.

В разделе 4 описано программное обеспечение, позволяющее прогнозировать время выполнения программы, параллельной по данным. Подробно описываются внутреннее представление параллельной Java-программы и реализация интерпретатора. Особое внимание уделено процессу выявления динамических свойств программы, в состав которого входят инструментация исходного кода, сбор профилей и компенсация влияния инструментальных операторов.

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

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

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

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

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

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

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

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

4. Разработан интерпретатор модели параллельной программы. Интерпретатор реализован и включён в среду разработки параллельных программ ParJava.

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

Все разработанные средства интегрированы в инструментальную среду ParJava. Среда ParJava, разработанная в ИСП РАН, используется в учебном процессе кафедры системного программирования факультета ВМиК МГУ и кафедры системного программирования ФПМЭ МФТИ.

Среда ParJava доступна по http://www.ispras.ru/groups/ctt/parjava.html.

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

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

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

1. В. А. Падарян. Оценка времени работы параллельной программы с помощью интерпретатора среды ParJava. / Препринт Института Системного Программирования РАН №6. М.: ИСП РАН, 2005.

2. В. А. Падарян. Интерпретация иерархической модели в среде ParJava. // Тезисы конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.

3. Виктор Иванников, Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян. Применение среды ParJava для разработки параллельных программ. // Труды Института Системного Программирования, т.5. 2004. с. 41-62.

4. Victor Ivannikov, Serguei Gaissaryan, 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.

5. 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.

6. 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.

7. 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.

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

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

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

11. PGHPF Compiler User's Guide, http://www.pgroup.com/doc/pghpfug/hpfug.htm

12. Luiz DeRose and Daniel A. Reed. SvPablo: A Multi-Language Architecture-Independent Performance Analysis System. // Proceedings of the International Conference on Parallel Processing (ICPP'99), Fukushima, Japan, September 1999, pp. 311-318.

13. 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

14. D. Brown, S. Hackstadt, A. Malony, B. Mohr. Program Analysis Environments for Parallel Language Systems: The TAU Environment. // Proceedings of the 2nd Workshop on

15. Environments and Tools For Parallel Scientific Computing, Townsend, Tennessee, May 1994, pp. 162-171.

16. S. Shende, and A. D. Malony. Integration and Application of the TAU Performance System in Parallel Java Environments. // Proceedings of the Joint ACM Java Grande -ISCOPE 2001 Conference, June 2001, pp. 87-96.

17. Java Native Interface, http://java.sun.eom/j2se/l.4.2/docs/guide/jni/index.html

18. Java Virtual Machine Profiler Interface. http://java.sun.eom/j2se/l.4.2/docs/guide/jvmpi/index.html

19. В. В. Воеводин, Вл. В. Воеводин. Параллельные вычисления. / СПб: БВХ-Петербург, 2000.

20. K. Shanmugam, A. Malony, B. Mohr. Speedy: An Integrated Performance Extrapolation Tool for pC++ Programs. // Proceedings of the Joint Conference PERFORMANCE TOOLS'95 and MMB'95, 20th-22nd September, 1995, Heidelberg, Germany.

21. C.L. Mendes. Performance prediction by trace transformation. // Fifth Brazilian Symposium on Computer Architecture, Florianopolis, September 1993.

22. Jesus Labarta, Sergi Girona, Vincent Pillet, Toni Cortes, and Luis Gregoris. DiP: A Parallel Program Development Environment. // Proceedings of the Euro-Par'96, Vol. II, 1996, pp. 665-674.

23. W. E. Nagel, A. Arnold, M. Weber, H.-C. Hoppe, and K. Solchenbach. VAMPIR: Visualization and analysis of MPI resources. // Supercomputer, 12(1): 69—80, January 1996.

24. Николай Коновалов, Виктор Крюков. Параллельные программы для вычислительных кластеров и сетей. // Открытые системы, 2002, №3.

25. Н.А. Коновалов, В.А. Крюков, С.Н. Михайлов, А.А. Погребцов. Fortran DVM язык разработки мобильных параллельных программ. // Программирование 1995, №1.

26. Н.А. Коновалов, В.А. Крюков, Ю.Л. Сазанов. C-DVM язык разработки мобильных параллельных программ. // Программирование №1, 1999.

27. J. С. Yan, S. R. Sarukkai, and P. Mehra. Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs using the AIMS Toolkit. // Software Practice & Experience. April 1995. Vol. 25, No. 4, pp 429-461.

28. S. R. Sarukkai, J. C. Yan, and J. Gotwals. Normalized Performance Indices for Message Passing Parallel Programs. // Proceedings of the International Conference on Supercomputing ICS-94, Manchester, England, July 11-15, 1994. pages 323-332.

29. Sundeep Prakash and Rajive Bagrodia. MPI-Sim: Using Parallel Simulation to Evaluate MPI Programs. // Proceedings of the Winter Simulation Conference, 1998, pp. 467-474.

30. Thomas Phan and Rajive Bagrodia. Optimistic Simulation of Parallel Message-Passing Applications. // Proceedings of the fifteenth workshop on Parallel and distributed simulation, 2001, pp. 173-181.

31. Mendel Rosenblum, Edouard Bugnion, Scott Devine, and Stephen Alan Herrod. Using the SimOS Machine Simulator to Study Complex Computer Systems. // Modeling and Computer Simulation, vol. 7, №1, 1997, pp. 78-103.

32. Sundeep Prakash, Ewa Deelman, and Rajive Bagrodia. Asynchronous Parallel Simulation of Parallel Programs. // IEEE Transaction on Software Engineering, May 2000, Vol. 26, No. 5, pp. 385-400.

33. J. Misra. Distributed Discrete-Event Simulation. // ACM Computing Surveys, Vol. 18, Issue 1, March 1986, pp. 39-65.

34. K.M. Chandy and R. Sherman. The conditional event approach to distributed simulation. // Proceedings of the SCS Multiconference on Distributed Simulation, Tampa, FL, March 1989, pp. 95-99.

35. Adve, V. S., R. Bagrodia, E. Deelman, T. Phan and R. Sakellariou. // Compiler-Supported Simulation of Highly Scalable Parallel Applications. // Proceedings of the IEEE/ACM SC99 Conference, November 13-18, 1999, Portland, Oregon, USA, pp. 1-20.

36. Vikram Adve and John Mellor-Crummey. Using Integer Sets for Data-Parallel Program Analysis and Optimization. // Proceedings of the SIGPLAN'98 Conference on Programming Language Design and Implementation (PLDI), Montreal, CA, June 1998, pp. 186-198.