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

• Кудрявцев, Максим Владимирович
• кандидат физико-математических наук
• 2006

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

Введение.

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

Цель и задачи работы.

Основные результаты работы.

Практическая ценность работы.

Апробация работы.

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

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

1.1 Традиционные подходы. Интерактивная отладка, отладочные печати.

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

Глава 2. Метод граничных итераций и двойных тел циклов.

2.1 Описание метода.

2.1.1 Использование граничных итераций.

2.1.2 Инструментация с одним и с двумя телами циклов.

2.1.3 Алгоритм построения множеств итераций для отладки программ на «гранях» многомерных циклов.

2.1.4 Алгоритм построения множеств итераций для отладки программ на «уголках» многомерных циклов.

2.1.5 Алгоритм построения множеств итераций отлаживаемого запуска по результатам эталонного.

2.2 Реализация метода граничных итераций и двойных тел циклов в отладчике системы DVM.

2.2.1 Модель параллелизма DVM.

2.2.2 Основные возможности DVM-отладчика.

2.2.3 Инструментация Фортран-DVM программ с одним и с двумя телами циклов.

2.2.4 Особенности программной реализации метода.

2.2.5 Изменения формата трассы.

2.2.6 Реализация оценки покрытия операторов программы.

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

Глава 3. Метод интегральных характеристик массивов. Комбинированный метод.

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

3.2 Реализация метода в отладчике системы DVM.

3.2.1 Нумерация параллельных конструкций.

3.2.2 Реализация метода интегральных характеристик.

Вычисление контрольных сумм.

Запись/чтение трассы с контрольными суммами.

Формат файла трассы.

Сравнение контрольных сумм.

Новые структуры данных и функции.

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

Глава 4. Метод коррекции результатов редукционных операций.

4.1 Описание метода.

4.2 Реализация метода в отладчике системы DVM.

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

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

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

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

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

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

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

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

Оба этих метода отладки параллельных программ были в середине 90-х годов XX столетия предложены и реализованы в DVM-системе [36], показав высокую эффективность при отладке приложений с незначительным объемом данных и вычислений. В сравнительном отладчике системы DVM впервые реализовано полностью автоматическое определение контролируемых точек и сравниваемых в них переменных. Чем больше таких точек, тем выше точность локализации ошибки. Полный контроль во всех точках программы позволяет обнаружить первые проявления ошибок, но требует при этом неприемлемое количество ресурсов, которое невозможно обеспечить при отладке научно-технических приложений, требующих высокопроизводительных вычислений. Кроме того, сравнительную отладку невозможно применять к приложениям с недетерминированным поведением.

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

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

Цель и задачи работы

Целью диссертационной работы является разработка методов, способных автоматизировать отладку научно-технических приложений, требующих высокопроизводительных вычислений в моделях параллельного программирования с глобальным адресным пространством (ОрепМР [7], HPF [5], DVM [6]). В соответствии с этой целью были определены следующие задачи:

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

2. Разработать методы и алгоритмы автоматического обнаружения некорректного выполнения параллельных программ, написанных в моделях параллельного программирования с глобальным адресным пространством (ОрепМР, HPF, DVM). Эти методы, основанные на динамическом анализе корректности и сравнительной отладке, должны обеспечивать существенное сокращение требуемых ресурсов времени и памяти и высокую точность обнаружения первых проявлений некорректного поведения параллельной программы,

3. Программно реализовать разработанные методы и алгоритмы в отладчике системы DVM [8].

4. Оценить эффективность предложенных методов и алгоритмов на представительном наборе параллельных программ.

Основные результаты работы

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

1. Разработаны новые методы автоматического обнаружения некорректного выполнения параллельных программ, написанных в моделях параллельного программирования с глобальным адресным пространством (OpenMP, HPF, DVM). Эти методы, базирующиеся на динамическом контроле выполнения каждого оператора программы посредством его сопоставления со спецификациями параллелизма или с поведением эталонной программы, способны существенно упростить и ускорить отладку параллельных программ.

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

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

4. Проведено экспериментальное исследование эффективности созданного отладчика на представительном наборе параллельных программ, включающем пакет NPB [37] и реальные приложения, подтвердившее высокую эффективность разработанных методов и алгоритмов.

Перечисленные результаты обладают научной новизной.

Практическая ценность работы

Предложенные автором методы и алгоритмы могут быть использованы для отладки программ, написанных в моделях параллельного программирования с глобальным адресным пространством OpenMP, HPF и DVM. В некоторых случаях эти методы могут применяться и для отладки последовательных программ, а так же MPI-программ [3].

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

Новый отладчик реализован на языке Си и протестирован на демонстрационных программах, входящих в состав системы DVM, Фортран-DVM версиях программ пакета NPB и реальных задачах на ОС Windows и Linux.

Отладчик находится в опытной эксплуатации на ряде крупнейших вычислительных систем России: кластерах МВС-15000ВМ, MBC-6000IM Межведомственного Суперкомпьютерного Центра РАН, кластере ANT НИВЦ МГУ, кластере RSC4 Института прикладной математики им. М.В. Келдыша РАН, а так же ЭВМ Regatta и кластере факультета ВМиК МГУ им. М.В. Ломоносова и доступен в исходных кодах. С помощью нового отладчика найдены ошибки в ряде реальных приложений.

Разработанный отладчик так же планируется использовать на практических занятиях факультета ВМиК МГУ в годовом спецкурсе по параллельному программированию кафедр Автоматизации систем вычислительных комплексов и Системного программирования.

Апробация работы

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

1. Научная конференция «Тихоновские чтения», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Автоматизация отладки параллельных программ», октябрь 2006 г.

2. Всероссийская научная конференция «Научный сервис в сети Интернет: технологии параллельного программирования». Доклад «Развитие средств отладки DVM-программ», Новороссийск, сентябрь 2006 г.

3. Объединенный научно-исследовательский семинар кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ им. М.В. Ломоносова. Доклад «Автоматизация отладки параллельных программ», Москва, июнь 2006 г.

4. X Байкальская Всероссийская конференция «Информационные и математические технологии в науке, технике и образовании». Доклад «Отладка параллельных программ», Северобайкальск, июль 2005 г.

5. Научная конференция «Ломоносовские Чтения», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Сравнительная отладка параллельных программ», Москва, апрель 2005 г.

6. Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2005», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Новые возможности DVM отладчика», Москва, апрель 2005 г.

7. Конференция «Технологии Microsoft в теории и практике программирования», факультет ВМиК МГУ им. М.В. Ломоносова. Москва, ноябрь 2004 г.

8. Образовательный семинар Зимней Школы Intel. Доклад «Сравнительная отладка DVM-программ», Нижний Новгород, февраль 2004 г.

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

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

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

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

В заключении перечисляются основные результаты работы.

Автор выражает благодарность Поддерюгиной Наталье Викторовне за реализацию инструментации в трансляторе Фортран-DVM. Работа выполнена под руководством доктора физико-математических наук, профессора кафедры Системного программирования факультета ВМиК МГУ им. М.В. Ломоносова Крюкова Виктора Алексеевича, которому автор выражает искреннюю признательность. и

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

Заключение

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

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

1. Разработаны новые методы автоматического обнаружения некорректного выполнения параллельных программ, написанных в моделях параллельного программирования с глобальным адресным пространством (OpenMP, HPF, DVM). Эти методы, базирующиеся на динамическом контроле выполнения каждого оператора программы посредством его сопоставления со спецификациями параллелизма или с поведением эталонной программы, способны существенно упростить и ускорить отладку параллельных программ.

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

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

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

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

1. Single UN1. Specification V3. http://www.unix.org/singleunixspecification/

2. MSDN: Processes and Threads. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/base/processesandthreads.asp

3. Message-Passing Interface Forum, http://www.mpi-forum.org

4. Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderam V. PVM 3 User's Guide and Reference Manual // Cambridge, MA, USA:MIT Press, 1994.

5. High Performance Fortran Forum, http://www.hipersoft.rice.edu/hpff/

6. Коновалов H.A., Крюков B.A., Михайлов C.H., Погребцов JI.A. Fortran-DVM язык разработки мобильных параллельных программ//Программирование. 1995. № 1.49-54.

7. OpenMP Consortium, http://www.openmp.org

8. Крюков В.А., Удовиченко Р.В. Отладка DVM- программ // Программирование. 2001. № 3. 19-29.9. pdbx.http://publib.boulder.ibm.com/infocenter/clresctr/vxrx/topic/com.ibm. cluster.pe.doc/pe42/am 103 00223 .html

9. Prism. http://docs.sun.com/app/docs?q=prism

10. Total View, http://www.etnus.com

11. Francioni J. Pancake C.M. High Performance Debugging Standards Effort // Scientific Programming. Amsterdam: IOS Press. Vol. 8. 2000. 95-108.http://web.engr.oregonstate.edu/~pancake/papers/HPDebugForum.pdf

12. Guard Parallel Relative Debugger. http://sourceforge.net/projects/guardsoft/

13. DejaVu project home page. http://researchweb.watson.ibm.com/dejavu/

14. Trace-Driven Debugging of Message Passing Programs. http://ipdps.cc.gatech.edu/1998/papers/166.pdf

15. Tip F. A survey of program slicing techniques. http://domino.research.ibm.com/comm/researchpeople.nsf/pages/tip. jpll995.html

16. Abramson D.A., Sosic R. Relative Debugging using Multiple Program Versions // Intensional Programming I. Sydney: World Scientific. 1995.http://www.csse.monash.edu.au/%7Edavida/papers/islip.pdf

17. Manne F., Andersen S.O. Automating the Debugging of Large Numerical Codes // Modern Software Tools for Scientific Computing. Birkhauser Verlag. 1997. Chapter 16. http://www.ii.uib.no/~fredrikni/fredrik/papers/debug.ps

18. ZPL. http://www.cs.washington.edu/research/zpl/home/index.html

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

20. Hood R., Jost G. Support for Debugging Automatically Parallelized Programs // Proceedings of AADEBUG'2000. Munich. 2000. http://arxiv.org/ftp/cs/papers/0012/0012006.pdf

21. Computer Aided Parallelization Tools (CAPTools). http://www.parallelsp.com/

22. Matthews G., Hood R., Jin H., Johnson S., Ierotheou C. Automatic Relative Debugging of OpenMP Programs. NAS Technical Report NAS-03-014. 2003.http://www.nas.nasa.gov/News/Techreports/2003/PDF/nas-03-014.pdf

23. Jin H., Frumkin M., Yan J. Code Parallelization with CAPO A User Manual. NAS Technical Report NAS-01-008. 2001. http://www.nas.nasa.gov/News/Techreports/2001/PDF/nas-01-008.pdf

24. GDB: The GNU Project Debugger, http://www.gnu.org/software/gdb/

25. The Dyninst API. http://www.dyninst.org/

26. Hood R. The p2d2 Project: Building a Portable Distributed Debugger // Proc. of the ACM SIGMETRICS Symposium on Parallel and Distributed Tools. Philadelphia. 1996. 127-136. http://doi.acm.org/10.1145/238020.238058

27. Vetter J.S., de Supinski B.R. Dynamic Software Testing of MPI Applications with Umpire // Proc. SC2000: High Performance Networking and Computing Conf. 2000.http://www.llnl.gov/CASC/people/vetter/pubs/scOO-umpire-vetter.pdf

28. MPI-CHECK. http://andrew.ait.iastate.edu/HPC/MPI-CHECK.htm

29. Marmot, http://www.hlrs.de/organization/amt/projects/marmot/

30. Intel Thread Checker. http://www.intel.com/cd/software/products/asmo-na/eng/threading/286406.htm

31. Система DVM. www.keldysh.ru/dvm

32. NAS parallel benchmarks. http://www.nas.nasa.gov/Software/NPB/

33. Крюков B.A., Кудрявцев М.В. Автоматизация отладки параллельных программ // Вычислительные методы и программирование. Том 7, раздел 2. http://www.srcc.msu.su/num-meth. 2006. 102-109.

34. Крюков В.А., Кудрявцев М.В. Развитие средств отладки DVM-программ // Научный сервис в сети Интернет: технологии параллельного программирования. Труды Всероссийской научной конференции. М.: Изд-во МГУ. 2006. 135-137.

35. Кудрявцев М.В. Новые возможности DVM отладчика // Материалы международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2005" секция "Вычислительная математика и кибернетика". М.:МАКС Пресс. 2005. 33-34.

36. Кудрявцев М.В., Крюков В.А. Повышение эффективности отладки DVM-программ // Технологии Microsoft в теории и практике программирования: тезисы конференции студентов, аспирантов и молодых ученых. М.:МАКС Пресс. 2004.24.

37. Воронков А.В., Головков СЛ. Архив пакета прикладных программ «РЕАКТОР». Препринт Института прикладной математики им. М.В.Келдыша РАН. №119. М., 2005.

38. Удовиченко Р. В. Отладка DVM-программ. Дис. канд. физ.-мат. наук. М., 2000.

39. Zeller A. Yesterday, my program worked. Today, it does not. Why? // Proc. ESEC/FSE 99. Toulouse. France. September 1999. Vol. 1687 of LNCS. 253-267. http://www.st.cs.uni-sb.de/papers/tr-99-01/

40. Hildebrandt R., Zeller A. Simplifying Failure-Inducing Input // Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis. ACM Press. 2000. 135-145. http://doi.acm.org/10.1145/347324.348938

41. Alpern В. и др. The Jalapeno virtual machine // IBM systems journal, Vol 39. No 1.2000.http://www.research.ibm.com/journal/sj/391/alpern.pdf

42. Alpern В., Choi J.-D., Ngo Т., Sridharan M., Vlissides J. A Perturbation-Free Replay Platform for Cross-Optimized Multithreaded Applications // IBM Research Report 21864 http://www.research.ibm.com/dejavu/rc21864.pdf

43. Zeller A. Isolating cause-effect chains from computer programs // SIGSOFT Softw. Eng. Notes 27, 6 Nov. 2002. 1-10. http://doi.acm.org/10.1145/605466.605468

44. Ladebug debugger manual. ftp://ftp.compaq.com/pub/products/software/developer/ladebugdebu ggermanual.html

45. Сайт с документацией компании Sun. Workshop: Command-Line Utilities, http://docs.sun.com/app/docs/doc/802-5763/6i9ggirrf?q=LockLint#hic

46. Assure for Threads. Reference Manual. Version 4.0. KAI Software, A Division of Intel Americas, Inc. http://www.physics.ohio-state.edu/doco/KAI/assure40/docs/AssureTReference.pdf