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

• Романенко, Алексей Анатольевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Романенко, Алексей Анатольевич

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ И СРЕДСТВА ОТЛАДКИ

ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. АНАЛИЗ И КЛАССИФИКАЦИЯ ВОЗМОЖНЫХ ОШИБОК.

1.1. Параллельные вычисления.

1.1.1. Модель.

1.1.2. Анализ ошибок на уровне модели вычислений.

1.2. Поведение параллельной программы.

1.3. Параллельная программа.

1.3.1. Модель.

1.3.2. Реализация модели передачи сообщений.

1.3.3. Анализ ошибок, обусловленных моделью программы.

1.4. Среда выполнения параллельной программы.

1.4.1. Модель.

1.4.2. Реализация.

1.4.3. Анализ ошибок обусловленных средой выполнения.

1.5. Классификация ошибок.

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

1.6.1. Обнаружение дедлоков.

1.6.2. Обнаружение ошибок соревнования.

1.6.3. Обнаружение ошибок в коммуникациях.

1.6.4. Обнаружение несбалансированности загрузки.

1.6.5. Метод отладки параллельных программ.

1.7. Требования к организации отладки параллельных программ.

1.8. Средства отладки параллельных программ.

1.8.1. Влияние средств отладки на выполнение программы.

1.8.2. Классиф икацпя инструментов отладки.

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

1.9.1. Total View.

1.9.2. Jumpshot.

1.9.3. AIMS.

1.9.4. Vampire.

1.9.5. Paradyn.

Выводы.

ГЛАВА 2. ОСНОВНЫЕ ПРОЕКТНЫЕ РЕШЕНИЯ И

АЛГОРИТМЫ РЕАЛИЗАЦИИ ОТЛАДЧИКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ GEPARD.

2.1. Многопроцессорная вычислительная система МВС-1000/М.

2.2. Кластер Новосибирского государственного университета.

2.3. Messages Passing Interface (MPI). Параллельная программа HAMPI.

2.4. Формулировка задачи.

2.5. Архитектура отладчика.

2.6. Обработка исходного кода.

2.7. Обеспечение информационного контекста.

2.8. Подсистема контроля выполнения.

2.9. Подсистема визуализации.

2.10. Синхронизация времени.

2.11. Описание поведения системы взаимодействующих процессов.

2.11.1. Выбор алфавита событий.

2.11.2. Определение множества всех протоколов.

2.11.3. Процесс отладки.

2.11.4. Отладка направления передачи данных.

Выводы. щ

ГЛАВА 3. ПРОЕКТ GEPARD.

3.1. Компоненты отладчика.

3.2. Язык отладки. Препроцессор.

3.3. Подсистема контроля выполнения.

3.4. Подсистема анализа собранной информации.

3.5. Анализ информации.

3.6. Использование и перспективы развития отладчика т GEPARD.

Выводы.

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

Актуальность темы

Процесс поиска и устранения ошибок в программе является трудным и однообразным занятием. Ситуация осложняется тем, что тестирование не может гарантировать отсутствие ошибок в программе. Особенно остро эта проблема стоит при разработке распределенных и параллельных программ (ГШ). При определенных условиях ошибки могут себя не проявлять. Во многих случаях проблема усугубляется отсутствием комплексных средств отладки и тестирования.

На вычислительном комплексе МВС-1000/М [1] складывается ситуация, когда растет количество пользователей и возрастает количество разрабатываемых программ. Из средств, предоставляемых пользователю для отладки, есть инструменты и библиотеки для разработки, как последовательных, так и параллельных программ. При этом если для разработки первых пользователю также предоставляются и средства отладки (GDB, strace), то пользователь, который занимается разработкой 1111, вынужден отлаживать свои программы с помощью вставления в код вызова функции вывода информации на экран, что очень не эффективно, либо переходить на другие вычислительные комплексы, где есть соответствующие средства.

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

Цель работы

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

Научная новизна

Отладка ПП представляет собой более сложную задачу по сравнению с отладкой последовательной программы. Во время исполнения 1111 состоит из набора последовательных процессов, которые взаимодействуют между собой. Помимо процессов появляется еще один объект, который требует отладки - система коммуникаций. Если отладка кода процессов может быть выполнена с использованием существующих последовательных отладчиков, то отладка поведения всей системы взаимодействующих процессов осложняется недетерминизмом, обычно огромным числом протоколов в поведении ПП. Именно на отладку поведения в большей степени должен быть ориентирован инструмент отладки ПП (далее просто отладчик). Помимо этого отладчик должен обладать свойствами профилировщика (profiler) - программы, позволяющей контролировать использование ресурсов приложением во время выполнения (память, процессор, сеть и т.д.) с тем, чтобы пользователь мог оптимизировать использование этих ресурсов относительно какого-либо критерия.

Для отладки ПП необходимо:

1. Минимально влиять на поведение программы. В противном случае некоторые ошибки при отладке могут себя не проявлять;

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

Эта функция является базовой и реализована в большинстве отладчиков.

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

4. Иметь возможность разбивать программу на логические блоки. Это позволит более детально изучать поведение программы на определенных участках. Эта возможность реализована в отладчиках Vampire, AIMS и отсутствует в Jumpshot, Paradyn.

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

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

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

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

Научная и практическая значимость

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

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

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

3. Предложена новая архитектура построения отладчиков параллельных программ.

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

Выполнение работы проводилось в соответствии с планами исследований по проекту «Методы и технологии распараллеливания алгоритмов и параллельная реализация численного моделирования на многопроцессорных системах» по Программе № 17.3 фундаментальных исследований РАН «Параллельные вычисления на многопроцессорных вычислительных системах» и междисциплинарному интеграционному проекту СО РАН № 148 «Самоорганизация, катализ и процессы химической эволюции в гравитационно и термодинамически неустойчивых системах, моделирующих ранние этапы формирования Земли».

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

Выводы

Отладчик GEPARD состоит из трех основных компонентов: препроцессора, подсистемы контроля выполнения и анализа информации.

Отладчиком поддерживаются два языка программирования С и Fortran.

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

Система визуализации и анализа имеет графический и текстовый интерфейсы. Графический интерфейс реализован на кросс платформенной библиотеке QT и сейчас он (графический интерфейс) существует под ОС Linux и Windows. Ядро системы анализа не привязано к системе визуализации и поэтому легко может быть реализована версия для других операционных систем. Ядро системы анализа написано на языке программирования С++.

Предложено несколько стратегий развития отладчика GEPARD.

Заключение

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

Результатом выполненной работы является:

1. На основе анализа моделей вычислений, программы и среды выполнения, выявлены и классифицированы поведенческие ошибки ПЛ.

2. Предложены методы обнаружения поведенческих ошибок.

3. Сформулированы технические требования, предъявляемые к отладчику ПП ориентированному на отладку поведения 1111.

4. С точки зрения выдвинутых требований проведен сравнительный анализ существующих отладчиков 1111.

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

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

Список литературы диссертационного исследования кандидат технических наук Романенко, Алексей Анатольевич, 2004 год

1. Официальный сервер Сибирского Суперкомпьютерного Центра, www2.sscc.ru.

2. Малышкин В.Э. Параллельное программирование мультикомпьютеров. Ярославль. 1999

3. Методическое пособие по многопользовательским многооперационным системам, ermak.cs.nstu.ru/~mos/.

4. Хоар Ч. Взаимодействующие последовательные процессы. Мир. 1989.

5. Hwang, К., and Xu, Z., Scalable Parallel Computing Technology, Architecture, Programming, WCB McGraw-Hill, USA (1998)

6. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. Санкт-Петербург, БХВ-Петербург, 2002.

7. Message Passing Interface Forum. MPI: Message Passing Interface standard.

8. Gropp W., Lusk E., User's Guide for MPICH, a Portable Implementation of MPI Version 1.2.0. Argone National Lab. 1999

9. Burns G., Daoud R., Vaigl J. LAM: An Open Cluster Environment for MPI. Ohaio supercomputer center. 1998.

10. Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderman V. PVM: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing. MIT Press, 1994

11. MPI-2: Extensions on the Message-Passing Interface. www.mpi-forum.org/docs/.

12. Карпов Ю.Г. Анализ корректности параллельной программы разделения множеств. //Программирование. 1996. #5.

13. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт

14. Петербург, БХВ-Петербург, 2002.

15. Фридланд А .Я., Ханамирова Л.С., Фридланд И.А. Информатика. Толковый словарь основных терминов. М. Приор, 1998

16. Grabner S., Kranzlmuller D., Volkert J., A Debugging Strategy for Distributed Memory Machines, in: Proc. Icole'94, Workshop iiber Parallelverarbeitung, Lessach, Austria, pp. 114-123 (Oct. 1994)

17. McDowell Ch.E., Helmbold D.P., Debugging Concurrent Programs, ACM Computing Surveys, Vol. 21, No. 4, pp. 593-622 (December 1989).

18. Krawczyk H., Wiszniewski В., Analysis and Testing of Distributed Software Applications, in: Wilson, D.R., (Ed.), C3 Industrial Control, Computers, and Communication Series, Research Studies Press Ltd., Baldock, Hertfordshire, England (1998).

19. Steve McConnell, Code complete. Microsoft Press. 1993

20. Horward M., LeBlance D., Writing secure code, Microsoft Press. 2003.

21. Microsoft Solution Framework, www.microsoft.com/msf/.

22. Романюк С.Г. Оценка надежности программного обеспечения. //Открытые системы. 1994. #4

23. Петренко А., Бритвина Е., Трошев С., Монахов А., Петренко О. Тестирование на основе моделей. //Открытые системы. 2003. #9

24. Abramson D., Foster I., Michalakes J., Sosic R., Relative Debugging and its Application to the Development of Large Numerical Models //Proceedings of the 1995 АСМЯЕЕЕ Supercomputing Conference, Dec. 1995

25. Geist, G.A., Beguelin, A., Dongarra, J.J., Jiang, W., Manchek, R., Sunderam, V.S., PVM3 User's Guide and Reference Manual, Technical Report, Oak Ridge National Laboratory, Tennessee, MIT Press, Cambridge, MA, USA 1994.

26. Самофалов B.B., Коновалов A.B., Технология отладки программ длямашин с массовым параллелизмом //Вопросы атомной науки и техники, сер. Математическое моделирование физических процессов, вып. 4, 1996, стр. 52-56

27. Rosenberg, J.B., How Debuggers Work: Algorithms, Data Structures, and Architecture, 1996

28. Ландау Л.Д., Лифшиц Е.М. Теоретическая физика. Т.З. Квантовая механика. Нерелятивистская теория. М.: Физматлит, 2001

29. Hollingsworth J.K., Miller В.P. An adaptive cost model for parallel program instrumentation. Proceedings of EuroPar'96, 1996

30. Петренко A.K. Методы отладки и мониторинга параллельных программ (обзор). //Программирование. 1994. #3

31. Etnus, LLC, Parallel debugger TotalView, 2001

32. Hood R. The p2d2 Project: Building a Portable Distributed Debugger. 1996 www.nas.nasa.gov/Groups/Tools/Projects/P2D2.

33. Zaki, O., Lusk, E., Gropp, W., Swider, D., Toward Scalable Performance Visualization with Jumpshot, 2001

34. Yan, J.C., Sarukkai, S.R., Mehra, P., Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs using the AIMS Toolkit, 1995

35. Visualization and Analysis of Parallel Programs, www.pallas.com/e/products/vampir.

36. Баранов A.B., Лацис A.O., Храмцов М.Ю., Шарф С.В. Руководство системного программиста (администратора) системы управленияпрохождением задач МВС-1000/М (версия 2.01). www.j scc.ru/infonnat/1000MPrgGuide.zip.

37. Страница кластера Новосибирского государственного университета ccfit.nsu.ru/cluster.

38. Карпов В.Я. Алгоритмический язык Фортран. М.: Наука. 1976

39. Немнюгин С., Стесик О. Современный Фортран. Самоучитель. Санкт-Петербург, БХВ-Петербург, 2004

40. Kernighan, Brian W., Ritchie, Dennis M. The С Programming Language (Second Edition). Prentice-Hall; 1988

41. Kalev D. ANSI/ISO С++ Professional Programmer's Handbook. Macmillan Computer Publishing. 1999.

42. Burley J.C. GCC 3.2.3 G77 Manual. gcc.gnu.org/onlinedocs/gcc-3.2.3/g77/.

43. Menapace J., Kingdon J., MacKenzie D. The "stabs" debug format. 2000. www.sunsite.ualberta.ca/Documentation/Gnu/gdb-4.18/htmlchapter/.

44. Qt С++ GUI Application Development Toolkit, doc.trolltech.com.

45. Gale Т., Main I. And GTK team. GTK+ 2.0 Tutorial, www.gtk.org/tutorial/.

46. Eckel B. Thinking in Java, 2nd edition, Revision 12,2001

47. Корнеев В.Д. Параллельное программирование в MPI 2-е изд., Новосибирск, Издательство ИВМиМГ СО РАН, 2002

48. Srinivasan S., Advanced Perl Programming, O'Reilly & Associates, 1999, ISBN 1-56592-220-4