автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Отладка DVM-программ

ВВЕДЕНИЕ.

ГЛАВА 1. РАЗРАБОТКА ПРОГРАММ ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1. Интерфейс передачи сообщений MPI.

1.2. Средства программирования высокого уровня.

1.2.1. Автоматические распараллеливающие компиляторы.

1.2.2. Языки с параллелизмом по данным.

1.2.3. Языки с параллелизмом по данным и вычислениям.

1.2.4. Общие проблемы и особенности отладки.

1.3. Обзор существующих систем отладки.

1.3.1. Отладка параллельных программ с использованием среды MAD.

1.3.2. Сравнительный отладчик Guard99.

ГЛАВА 2. МЕТОДЫ ОТЛАДКИ DУМ-ПРОГРАММ.

2.1. Обзор D VM модели.

2.2. Классы возможных ошибок и методы их обнаружения.

2.3. Достоинства предложенных методов отладки.

ГЛАВА 3. МЕТОД ДИНАМИЧЕСКОГО КОНТРОЛЯ DVM-УКАЗАНИЙ.

3.1. Контроль инициализации переменных и элементов массивов.

3.2. Контроль приватных и неизменяемых переменных.

3.3. Контроль редукционных переменных.

3.4. Контроль доступа к элементам распределенного массива.

3.5. Контроль использования буфера удаленного доступа.

3.6. Ограничения метода динамического контроля.

ГЛАВА 4. МЕТОД СРАВНЕНИЯ РЕЗУЛЬТАТОВ ВЫПОЛНЕНИЯ.

4.1. Накопление трассировки.

4.2. Сравнение результатов вычислений.

4.3. Контроль редукционных операций.

4.4. форматы входных и выходных файлов.

4.4.1. Конфигураъщонный файл трассировки.

4.4.2. Файл трассировки.

ГЛАВА 5. РЕАЛИЗАЦИЯ ДИНАМИЧЕСКОГО ОТЛАДЧИКА.

5.1. Состав DVM-отладчика.

5.2. Прототипы отладочных функций.

5.3. Реализация базовых модулей.

5.3.1. Таблица.

5.3.2. Хеш-таблица.

5.3.3. Таблица переменных.

5.3.4. Модуль выдачи диагностики.

5.4. Реализация системы динамического контроля DVM-указаний.

5.4.1. Режим работы динамического контроля с таблицей переменных.

5.4.2. Основные функции модуля динамического контроля.

5.4.3. Параметры системы динамического контроля.

5.5. Реализация системы сравнения результатов выполнения.

5.5.1. Основные структуры системы сравнения результатов выполнения .93 5.5.2: Модуль записи трассировки.

5.5.3. Модуль накопления трассировки.

5.5.4. Модуль чтения трассировки.

5.5.5. Модуль сравнения трассировки.

5.5.6. Модуль обработки редукции.

5.5.7. Параметры системы сравнения результатов выполнения.

Вычислительные программы для последовательных ЭВМ традиционно создавались на языках Фортран 77 и Си. Для многопроцессорных ЭВМ с распределенной памятью (Cray ТЗЕ, Intel Paragon, IBM SP2, МВС-1000) и сетей ЭВМ такие программы в настоящее время, как правило, создаются на языках Фортран 77 и Си, расширенных библиотеками передачи сообщений (PVM [19,41], MPI [49]). Разработка таких параллельных программ требует от прикладного программиста гораздо больше усилий, чем разработка последовательных программ, поскольку ему требуется не только распределить данные и вычисления между разными процессорами, но и организовать взаимодействие процессоров посредством обмена сообщениями. Фактически, параллельная программа представляет собой систему взаимодействующих программ, каждая из которых выполняется на своем процессоре. Отладка таких программ еще более осложняется их недетерминированным поведением.

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

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

Второй подход базируется на использовании языков программирования с параллелизмом по данным, самыми яркими представителями которых являются HPF [24], Fortran D [47] и Vienna Fortran [13,48]. При этом подходе на программиста возлагается ответственность за распределение данных между процессорами, а представление программы в виде системы процессов, взаимодействующих посредством обмена сообщениями, осуществляет компилятор автоматически.

Третьим подходом является DVM-подход, при котором пользователь должен точно специфицировать не только распределение данных, но и распределение вычислений, а также может полностью управлять обменом информации между процессорами [2,27].

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

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

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

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

Это позволило предложить следующую методику поэтапной отладки программ для систем с автоматизацией распараллеливания.

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

Целью диссертационной работы являлась разработка методов отладки параллельных программ для систем автоматизации распараллеливания и их реализация в рамках DVM-системы.

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

1. На основе анализа возможных ошибок в параллельных программах, разрабатываемых с использованием систем автоматизации распараллеливания, предложена новая методика поэтапной отладки программ:

• Сначала программа отлаживается на рабочей станции как последовательная программа.

• Затем производится проверка распараллеливающих указаний посредством моделирования параллельного выполнения программы.

• На третьем этапе программа выполняется на параллельной машине в режиме сравнения результатов параллельного и последовательного выполнения.

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

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

• Алгоритмы сравнения результатов последовательного и параллельного выполнения программы.

3. Созданы средства отладки параллельных программ, разрабатываемых на языках C-DVM [2] и Fortran-DVM [27].

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

Заключение

Целью данной работы являлась разработка методов отладки параллельных программ для систем автоматизации распараллеливания и их реализация в рамках DVM-системы.

Основными результатами данной работы являются:

1. На основе анализа возможных ошибок в параллельных программах, разрабатываемых с использованием систем автоматизации распараллеливания, предложена новая методика поэтапной отладки программ:

• Сначала программа отлаживается на рабочей станции как последовательная программа.

• Затем производится проверка распараллеливающих указаний посредством моделирования параллельного выполнения программы.

• На третьем этапе программа выполняется на параллельной машине в режиме сравнения результатов параллельного и последовательного выполнения.

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

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

• Алгоритмы сравнения результатов последовательного и параллельного выполнения программы.

3. Созданы средства отладки параллельных программ, разрабатываемых на языках C-DVM и Fortran-DVM.

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

В качестве языка программирования использовался язык Си. Общий объем исходных текстов заново разработанных программ составляет примерно 7000 строк. Реализовано примерно 200 функций.

- 124

Динамический отладчик функционирует в рамках DVM-системы на операционных системах Windows 95/NT и UNIX. В составе DVM-системы он был установлен на ЭВМ МВС-1000 (в ИПМ им. М.В.Келдыша РАН и в межведомственном суперкомпьютерном центре Миннауки РФ и РАН), кластере рабочих станций SUN (ИСП РАН и INRIA-IRISA, г. Рен, Франция), кластере рабочих станций SGI и кластере на базе Pentium III и Marynet (Северо-китайский институт вычислительной техники, г. Пекин).

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

Основные положения диссертации опубликованы в работах [3], [4] и [5] и докладывались на заседании объединенного научно-исследовательского семинара кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета Вычислительной Математики и Кибернетики МГУ (1999 г.).

1. Арапов Д. Можно ли превратить сеть в суперкомпьютер? // Открытые системы.- 1997,-№4.-С. 6-10.

2. Коновалов Н. А., Крюков В. А., Погребцов А. А., Сазанов Ю. JL. C-DVM язык разработки мобильных параллельных программ- М.: Препринт ИПМ им. М. В. Келдыша РАН, 1997. - №86. - 37 с.

3. Крюков В. А., Удовиченко Р. В. Отладка DVM-программ // Программирование.- 2000. Принято к печати.

4. Крюков В. А., Удовиченко Р. В. Отладка DVM-программ. М.: Препринт ИПМ им. М. В. Келдыша РАН, 1999. - №56. - 26 с.

5. Отладка DVM-программ. Руководство пользователя. / Институт прикладной математики им. М. В. Келдыша РАН. http://www.keldysh.ru/dvm/. - ноябрь 1999.

6. Спецификация интерфейса Lib-DVM. / Институт прикладной математики им. М. В. Келдыша РАН. http://www.keldysh.ru/dvm/dvmhtml/rus/sys/libdvm /rtsIDr0.html.

7. Abramson D. A., Foster I., Michalakes J., Sosic R. Relative Debugging: A new paradigm for debugging scientific applications // The Communications of the Association for Computing Machinery (CACM). 1996. - Vol. 39, №11.- P. 67-77.

8. Abramson D. A., Sosic R., Watson G. Implementation Techniques for a Parallel Relative Debugger // International Conference on Parallel Architectures and Compilation Techniques (PACT'96). Boston, 1996. - October 20-23.

9. Abramson D. A., Watson G. Relative Debugging for Parallel Systems // Proceedings of PCW 97, September 25-26. Canberra, 1997. - P.P1-C-1-P1-C-8.

10. Butler R., Lusk E. User's guide to the p4 parallel programming system: Technical Report ANL-92/17 / Argonne National Laboratory. 1992. - http://www-fp .mcs. anl.gov/~lusk/p4/p4-manual/p4.html.

11. Chapman В. M., Mehrotra P., Zima H. P. User Defined Mappings in Vienna Fortran // ACM SIGPLAN Notices. January 1993. - Vol.28, No.l. - P.72-75.

12. Choi J.-D., Min S. L. RACE FRONTIER: Reproducing Data Races in Parallel-Program Debugging // Proc. 3rd ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPOPP). Williamsburg: Virginia, April 1991. — P.145-154.

13. Fortran 90 Handbook / Adams J., Brainerd W., Martin J., Smith В., Wagener J. -New-York: McGraw-Hill, 1992. 823 p.

14. Gait J. A Probe Effect in Concurrent Programs // IEEE Software Practice and Experience. - 1986. - Vol. 16(3). - P. 225-233.

15. Geist G. A., Kohl J., Papadopoulos P. Visualization, Debugging and Performance in PVM // Proc. of Visualization and Debugging Workshop. Oct. 1994.

16. Grabner S., Kranzlmuller D. A Comparison of Monitoring Strategies for Distributed Memory Computers // Proc. of CONPAR 94-VAPP VI. Linz: Austria, Sept. 1994. -P.66-75.

17. Grabner S., Kranzlmuller D., Volkert J. Debugging of Concurrent Processes // Proc. 3rd Euromicro PDP Workshop. Sanremo: Italy, Jan. 1995. - P.547-554.

18. High Performance Fortran language specification // High Performance Fortran Forum. Scientific Programming. 1993. - Vol. 2. - P. 1-170.

19. HPD Version 1 Standard: Command Interface for Parallel Debuggers: Technical Report CSTR-97 / High Performance Debugging Forum; ed. Pancake C., Francioni J.- Dept. of Computer Science, Oregon State University, 1997. 161 p.

20. Koelbel C., Loveman D., Schreiber R., et al. The High Performance Fortran Handbook. Cambridge: The MIT Press, 1994. - 394 p.

21. Kranzlmuller D., Christanell A., Grabner S., Volkert J. Control and Data Flow Analysis for Parallel Program Debugging // Proc. VECPAR'96, 2nd Intl. Conf. on Vector and Parallel Proc. Porto: Portugal, Sept. 1996. - P.81-92.

22. Kranzlmuller D., Grabner S., Volkert J. Race Condition Detection with the MAD Environment // Proc. of PART'95, Second Australasian Conference on Parallel and Real-Time Systems. Fremantle: Australia, Sept. 1995. -P.160-166.

23. Kranzlmuller D., Koppler R., Holzner Ch., Grabner S., Volkert J. Parallel Program Visualization with MUCH // Proc. of ACPС'96. Klagenfurt: Austria, Sept. 1996. -P.148-160.

24. Lastovetsky A. mpC a Multi-Paradigm Programming Language for Massively Parallel Computers // ACM SIGPLAN Notices. - February 1996. - Vol. 31(2). -P. 13-20.

25. Leu E., Schiper A., Zramdini A. Execution Replay on Distributed Memory Architectures // Proc. of 2nd IEEE Symp. on Parallel & Distr. Processing. Dallas: TX, Dec. 1990.-P. 106-112.

26. May J., Berman F. Panorama: A portable, extensible debugger // ACM/ONR Workshop on Parallel and Distributed Debugging. Sigplan Notices. 1993. - Vol. 28(12)P.96-106.

27. Maybee P. NeD: The network extensible debugger // Proceedings of the Summer 1992 USENIX Technical Conference. San Antonio, 1992. - P.145-156.

28. Miller B. P., Choi J.-D. A Mechanism for Efficient Debugging of Parallel Programs // Proc. of the SIGPLAN/SIGOPS Workshop on Parallel & Distr. Debugging. -Madison: Wisconsin, May 1988. -P.141-150.

29. Netzer R. H. В., Miller B. P. What are Race Conditions? Some Issues and Formalizations // ACM Letters on Progr. Languages and Systems. - 1992. - Vol. 1(1). -P.74-88.

30. Pancake C. Establishing Standards for HPC System Software and Tools // NHSE Review. Nov. 1997. - Vol. 2 (1). - Online journal available at http://nhse.cs.rice.edu/NHSEreview/97-1 .html.

31. Pancake С. M., Netzer R. H. B. A Bibliography of Parallel Debuggers, 1993 Edition // Proc. of the ACM/ONR Workshop on Parallel and Distributed Debugging. San Diego, May 1993.-P. 169-186.

32. PVM 3 User's Guide and Reference Manual: Technical report / Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderam V. Oak Ridge National Laboratory ORNL/TM-12187, 1993. - 159 p.

33. Ramsey N., Hanson D. R. A retargetable debugger // Proceedings of SIGPLAN'92 Conference on Programming Language Design and Implementation. ACM, 1992. -P.22-31.

34. Reiss S. P. Trace-Based Debugging // AADEBUG '93. Linkoping: Sweden, May 1993. -P.305-314.

35. Satterthwaite E. Debugging tools for high level languages // Software Practice and Experience. - July-September 1972. - Vol. 2(3). - P. 197-217.

36. Sosic R. Design and Implementation of Dynascope, a directing Platform for Compiled Programs // Computing Systems. 1995. - Vol. 8(2). - P. 107-134.

37. Sosic R., Abramson D. A. Guard: A Relative Debugger: Technical Report #CIT-94-21 / Griffith University, School of Computing and Information Technology. 15 p.

38. Vienna Fortran A Language Specification. Version 1.1.: Technical Report TR92-4 / Zima H., Brezany P., Chapman В., Mehrotra P., Schwald A. - Institute for Software Technology and Parallel Systems, University of Vienna, March 1992. - 86 p.

39. Walker D. W. The Design of a Standard Message-Passing Interface for Distributed Memory Concurrent Computers // Parallel Computing. 1994. - Vol. 20(4). - P.657-673.

40. Weinand A., Gamma E., Marty R. ET++ An Object Oriented Application Framework in С++ // OOPSLA'88 Conference Proceedings. SIG-PLAN Notices. -San Diego, Sept. 1988.-Vol. 23(11). - P.168-182.