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

На правах рукописи

Власенко Андрей Юрьевич

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

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

005548985 ..........11 МАЙ Ш

Томск-2014

005548985

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Кемеровский государственный университет» на кафедре ЮНЕСКО по новым информационным технологиям.

Научный руководитель: доктор физико-математических наук, профессор

[Афанасьев Константин Евгеньевич]

Официальные оппоненты:

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

Ведущая организация: Федеральное государственное бюджетное учреждение науки «Институт динамики систем и теории управления» Сибирского отделения Российской академии наук, г. Иркутск.

Защита диссертации состоится 19 июня 2014 г. в 12.00 на заседании диссертационного совета Д 212.267.08, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корп. № 2, ауд. 102).

С диссертацией можно ознакомиться в Научной библиотеке и на сайте федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет» www.tsu.ru.

Автореферат разослан «24» апреля 2014 г.

Материалы по защите диссертации размещены на официальном сайте ТГУ: http://wvw.tsu.ru/content/news/announcement_of_the_dissertations_in_the_tsu.php

Ученый секретарь

диссертационного совета Д 212.267.08 доктор технических наук, профессор

Скворцов

Алексей Владимирович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Высокопроизводительные вычислительные системы вошли в перечень критических технологий Российской Федерации. Во всем мире научные организации и технологические предприятия затрачивают огромные средства на приобретение суперкомпьютеров. Для эффективного использования данных вычислительных ресурсов требуется применение специальных технологий параллельного программирования. Фундаментальные основы параллельных вычислений были заложены в трудах Д. Амдала, Э. Дейкстры, М. Флинна, С. Крея, Я. Фостера, Дж. Дон-гары и др. В России в этом направлении работают коллективы под руководством С.М. Абрамова, A.B. Бухановского, И.В. Бычкова, Вл.В. Воеводина, В.П. Гергеля, Б.М. Глинского, В.А. Крюкова, В.Э. Малышкина, Л.Б. Соколинского, A.B. Старченко, Б.Н. Четверушкина и др.

В параллельном программировании особенно сложна разработка программ для вычислительных систем с распределенной памятью, среди которых наиболее распространены вычислительные кластеры. Основная особенность создания программ для этих систем заключается в том, что параллельное приложение представляет собой совокупность процессов, работающих на различных узлах кластера и обменивающихся данными по коммуникационной сети. Среди инструментов, позволяющих распределить выполнение задачи между узлами, выделяют языки программирования (PGAS-языки, DVM-система); предметно-ориентированные библиотеки (MKL, PETSc); библиотеки односторонних обменов (SHMEM, GASNET).

Однако наиболее распространенным инструментом создания приложений для кластерных систем в настоящее время остается интерфейс MPI (Message Passing Interface). При создании MPI-приложения разработчики встречаются со многими трудностями, среди которых особо следует выделить отладку. Причина этого заключается в том, что при параллельном программировании появляются новые источники ошибок. Одним из главных таких источников является «недетерминизм» (результаты работы могут различаться при запуске в другой программно-аппаратной среде или даже при нескольких запусках на одной вычислительной системе). Другая проблема — неверное использование самого MPI-стандарта.

Ввиду перечисленных и некоторых других факторов в MPI-программах возникает большое множество семантических ошибок, которые нуждаются в классификации и для обнаружения которых требуются специальные средства. При построении таких средств применяется несколько подходов. Один из них — «автоматизированный контроль корректности», выделяющийся следующими особенностями: 1) посредством применения аналитических алгоритмов средство отладки может обнаружить ошибки, обусловленные «недетерминизмом» (в отличие от диалоговой отладки); 2) для проведения анализа достаточно одного запуска параллельной программы и нет необходимости создавать эталонную версию (в

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

Попытки создания систем автоматизированного контроля корректности MPI-программ предпринимались как в работах российских ученых (ИПМ им. М.В. Келдыша - «Distributed Virtual Machine»; ИВМиМГ СО РАН - «Gepard»), так и в зарубежных научных центрах и коммерческих компаниях (HLRS - «MARMOT»; Intel Corporation - «Intel Message Checker»). Существенной проблемой создания систем данной категории является то, что организовать проверки на все возможные ошибки в программе чрезвычайно сложно. Причина этого, во-первых, в том, что MPI-стандарт накладывает множество ограничений на аргументы и последовательность вызовов функций, а несоблюдение любого ограничения является ошибкой. Во-вторых, MPI-стандарт регулярно претерпевает изменения (до настоящего момента уже была выпущена версия 3.0 стандарта), и каждая версия привносит новые функции, типы объектов и пр. В то же время пользователю далеко не всегда требуется выполнение инструментальным средством всех возможных проверок на его программе - зачастую он приблизительно представляет, в каких местах может возникнуть ошибка, а излишние проверки создают дополнительную нагрузку.

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

Объектом исследования являются теория и практика параллельного программирования.

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

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

Задачи исследования:

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

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

3. С помощью разработанной системы описания формализовать наиболее распространенные семантические ошибки в MPI-приложениях.

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

5. Провести тестирование инструментального средства отладки и сопоставить его с аналогами.

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

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

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

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

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

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

Практическая ценность диссертационного исследования:

1. Разработанные шаблоны ошибочного поведения применимы для анализа MPI-программ на наличие семантических ошибок.

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

. 3. Рекомендации, разработанные для пользователей программного средства, применимы как при описании ошибочного поведения, так и при проведении автоматизированного контроля корректности МР1-программ.

Основные положения, выносимые на защиту:

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

2. Система описания шаблонов ошибочного поведения МР1-приложений для использования в процессе автоматизированного контроля корректности.

3. Библиотека шаблонов ошибочного поведения для распространенных семантических ошибок в МР1-приложениях.

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

шаблонов ошибочного поведения.

Реализация результатов исследования. Система автоматизированного контроля корректности, являющаяся одним из результатов работы, была внедрена в центре коллективного пользования «Высокопроизводительные параллельные вычисления» КемГУ (http://icp.kemsu.ru/CKP). Система установлена на входящем в состав центра вычислительном кластере, она используется преподавателями и студентами математического факультета КемГУ для отладки МР1-программ и была применена при подготовке учебного курса «Параллельные вычислительные алгоритмы».

Апробация работы. Основные результаты диссертационного исследования по мере их получения были представлены на 17 конференциях, конкурсах и семинарах, в числе которых: VI Международный научный семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (Санкт-Петербург, 2006); V, VI, VII сибирская конференция по параллельным и высокопроизводительным вычислениям (Томск, 2009, 2011, 2013); Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: экзафлопсное будущее» (Абрау-Дюрсо, 2011); международная научная конференция «Параллельные вычислительные технологии» (Новосибирск, 2012); семинар ССКЦ «Архитектура, системное и прикладное программное обеспечение кластерных суперЭВМ» под руководством профессора Б.М. Глинского (Новосибирск, 2010); семинар «Информационные технологии и математическое моделирование» под руководством профессора К.Е. Афанасьева (Кемерово, 2006 - 2013).

Публикации. По теме диссертации опубликовано 18 работ, в том числе 3 статьи в изданиях, рекомендуемых ВАК для представления основных результатов диссертации, 1 статья в рецензируемом журнале и 14 публикаций в материалах конференций и семинаров.

Личный вклад. Основные результаты работы получены автором лично. Постановка задачи была выполнена совместно с научным руково-

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и шести приложений. Объем основного текста работы без приложений составляет 167 страниц машинописного текста, включая 11 иллюстраций, 4 таблицы и библиографический список из 90 литературных источников.

СОДЕРЖАНИЕ РАБОТЫ Во введении обозначена нарастающая актуальность параллельных вычислений в современной науке и технике. Рассматриваются основные архитектуры высокопроизводительных вычислительных систем. Перечислены основные средства создания параллельных программ для вычислительных кластеров. Особое внимание уделено описанию интерфейса MPI. Изложены некоторые трудности и источники проблем при использовании MPI. Обосновывается необходимость специальных средств отладки MPI-приложений. Среди прочих подходов к построению инструментов данной категории выделен автоматизированный контроль корректности. Ставится цель диссертационной работы, и определяются направления исследования.

Первая глава посвящена обзору и анализу различных типов ошибок, возникающих при MPI-программировании, методам обнаружения ошибок и средствам отладки. Дополнены классификации семантических ошибок в параллельных программах, приведенные в работах ИПМ им. М.В. Келдыша, HLRS (Германия) и Intel Corporation. Построена собственная классификация ошибок, возникающих при использовании MPI-стандарта первой версии (на рис. 1 приведён фрагмент классификации).

Далее в главе изложены основные подходы к отладке параллельных программ и охарактеризованы некоторые инструментальные средства, использующие данные подходы. Ниже приведен список основных методов, а в скобках — системы, реализующие эти методы:

- диалоговые отладчики (TotalView, Distributed Debugging Tool);

- средства верификации модели программы (MPI-Spin);

— средства сравнительной отладки (GEPARD, DVM);

— средства автоматизированного контроля корректности: динамический анализ (MARMOT, Intel Trace Analyzer & Collector - ITAC); анализ no трассе (GEPARD, Intel Message Checker).

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

Рисунок 1. Семантические ошибки в MPI-программах

Изложены алгоритмы поиска разных типов семантических ошибок системами MARMOT и ITAC, а также архитектуры данных систем.

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

Каждый шаблон пользователь заполняет в отдельном файле, содержащем следующие разделы:

1) Название шаблона (параметр «Name»).

2) Блок описания процессов, где указывается количество (параметр «К») и, опционально, номера процессов («pl», «р2»,...). Применив обозначение «n(MPI_COMM_WORLD)», пользователь может указать, что в описываемой ситуации принимают участие все процессы MPI-программы.

3) Блок функций, которые должны вызвать указанные процессы для возникновения ситуации. Каждая функция обозначается как «Fn», где п -ее номер. Указывается приведенный в предыдущем разделе номер процесса (рш) и через двоеточие — имя MPI-функции без префикса «MPI». Для обозначения любой операции из некоторого множества существу-

ют специальные макросы. Так, запись «Fl=pl:Send_any» означает, что первый процесс вызывает любую из блокирующих операций отправки. Для объединения нескольких условий используются символы для конъюнкции (&&), дизъюнкции (||) и отрицания (!). Можно указать сразу несколько функций при помощи одного выражения. Например, «FA=pA:Bcast» значит, что все процессы должны вызвать MPI_Bcast. 4) Третий блок содержит условия на аргументы функций. В каждой строке этого блока пользователь указывает функцию из предыдущего блока, номер ее аргумента и значение, принимаемое аргументом. Значением может быть конкретное число: «Fl(2)=7»; номер процесса: «Fl(4)=pl»; аргумент другой функции: «Fm(2)>Fn(2)>> или макрос MPI: «Fl(4)=MPI_ANY_SOURCE». Условия в блоке базируются на логических отношениях равенства «=», неравенства «!=», больше «»> и меньше «<». Кроме перечисленного, в систему описания введено несколько дополнительных конструкций для составления условий.

Каждый раздел предваряет запись «»' block» (/ - номер раздела).

Ниже рассмотрен пример файла шаблона. Описываемая шаблоном ошибка «Повторное использование активного запроса обмена» заключается в том, что некоторый процесс вызывает неблокирующую функцию точка-точка, а затем, не освобождая «запрос обмена» (request), вызывает другую неблокирующую функцию, использующую тот же request. Name=Repeated using of active request 1 block K=1 2block Fl=pl:IPTP F2=pl:Wait! && Test! F3=pl:IPTP ЗЫоск Fl(7)=F2(l) Fl(7)-F3(7)

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

На текущий момент при помощи введенной системы описания разработаны шаблоны для 22 семантических ошибок (20 - для функций стандарта MPI-1 и 2-для MPI-2) и 2 пользовательских проверки:

1. Несовпадение длин посылаемого и принимаемого сообщений в функциях точка-точка.

2. Взаимно недопустимые типы данных в операциях передачи и приема.

3. Несовпадение размеров буферов в разных процессах при коллективной операции:

а. для функций, перераспределяющих данные;

Ь. для редукционных функций.

4. Взаимно недопустимые типы принимаемых и отправляемых данных в векторном варианте коллективной операции:

a. для функций сбора данных (МР1_ОаЙ1егу, МР1_А1^аИ1егу);

b. для функции рассылки данных (МР1_8сайегу);

c. для функции перераспределения данных (МР1_АШоа11у).

5. Несовпадение кодов редукционной операции в разных процессах.

6. Задание пользователем разных номеров гоо1-процессов в разных процессах-участниках коллективной операции.

7. Несовпадение количества процессов во вновь создаваемой группе.

8. Незавершенная коллективная операция.

9. Выход без вызова функции МР1_РтаИге.

10. Неблокирующая передача без последующего МР1_\Уак или МР1_Тсз1

11. Повторное использование активного запроса обмена.

12. Неосвобождение определенного пользователем типа данных.

13. Гонки данных, обусловленные применением MPI_ANY_SOUR.CE.

14. Дедлоки, обусловленные циклом отправок или получений.

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

16. Неверный номер процесса приемника/отправителя (отрицательный или выходящий за пределы коммуникатора).

17. Тэг операции точка-точка отрицателен или слишком велик.

18. Передача типа точка-точка без вызова парной операции.

19. Отрицательное число передаваемых элементов сообщения.

20. Изменение данных, участвующих в неблокирующей коммуникации, основным потоком МР1-процесса.

21. Неверный режим доступа при открытии файла.

22. Отсутствие закрывающей функции для использованного файла.

23. Превышение количества передаваемых элементов заданного значения.

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

Третья глава посвящена описанию инструментального средства автоматизированного контроля корректности собственной разработки диссертанта. Предлагаемое средство построено по клиент-серверной архитектуре и его основу составляют (рис. 2):

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

— Препроцессор, служащий для получения имени файла и номера строки для каждого вызова МР1-функции.

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

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

Ниже приводится алгоритм одного сеанса работы системы отладки (рис. 3). Цифры на рисунке соответствуют номерам действий в алгоритме.

1. Пользователь формирует файлы шаблонов.

2. Затем заполняет конфигурационный файл, где указывает ряд параметров (исходные файлы своего проекта; число MPI-процессов и др.).

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

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

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

6. Затем призводится вызов "mpiexec" для MPI-программы. Ключами вызова являются пользовательские аргументы из конфигурационного файла, а также номер ТСР-порта для связи с сервером.

7. Сначала сервер-анализатор проверяет корректность составления файлов шаблонов и заполняет специальные структуры данных.

8. Затем сервер передает MPI-процессам список функций для профилирования, которые фигурируют в файлах шаблонов.

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

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

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

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

13. По завершении работы MPI-программы, найденные сервером ошибки заносятся в результирующий файл ошибок.

Вычислительный узел О

Сервер-анализатор

1. список шаблонов [

(2. список функций для профилирования | | 3. список операций точка-точка |

[4. списки групповых коммуникаций] [ 5. двумерный массив ссылок] ! 6. логические ошибки I

С

>■• С

Головной узел кластера

конфиг. файл]

Препроцессор

311 Утилита запуска

ф\

Чь.

ч.

I 3 Вычислительный узел 1

её:

МР!-процесс

С

основной поток

служебный поток

3

[ 7. список~функций для профилирования]

шаблон р]

Вычислительный узел п

МР1-процесс

С

основной поток

служебный поток

|7. список функций для профилирования

Рисунок 2. Модель компонентов и размещения

Одной из основных структур данных на сервере является динамический список, содержащий информацию о ситуациях, возникновение которых необходимо проверить (на рис. 2 элемент №1). Содержание списка соответствует данным в файлах шаблонов (для каждой ситуации - количество процессов и их номера; имена МР1-функций; условия на аргументы). Еще один список (на рис. 2 элемент №2) предназначен для рассылки МР1-процессам. Каждый его элемент содержит информацию о функции, фигурирующей в каких-либо файлах шаблонов.

Также на сервере хранится информация о вызываемых программой МР1-функциях. Основной структурой данных для коммуникаций типа точка-точка является еще один список (на рис. 2 элемент №3). В отличие от операций точка-точка, имеющих почти идентичный набор аргументов, у каждой из коллективных функций свой набор параметров. Поэтому данные о вызовах точка-точка хранятся в одном списке, а для каждой групповой функции ведется свой список (на рис. 2 элемент №4). В эти списки добавляются элементы при поступлении сообщений от МР1-процессов.

:: Пользователь

3) Запустить

4) Преобразовать (исход, код)

j

5) Компилировать (преобраз. исход, код)-

компилятор

6) Запустить (хост, ТСР-порт)

.„О X

7) Запустить (n, ip серв.-анализ., ТСР-порт)

МР1-проиессы

X

' 9) Передать имена МР1-функций '

10) Передать параметры вызова МР!-функции

¡^- !

Сообщение о вызове Нпайге или о зависании

К-------—-........

14) Файл найденных ошибок р ^ i -

Ж X

Рисунок 3. Диаграмма последовательности Поскольку групповая функция должна быть вызвана на всех процессах, входящих в коммуникатор, то для шаблонов с участием групповых функций характерен следующий вид второго блока: «FA=pA:Coll__data» или «FA=pA:Coll_reduc» (Coll data - коллективная операция, перераспределяющая данные; Coll reduc - редукционная операция). Для анализа MPI-вызовов на соответствие этим шаблонам введен двумерный массив ссылок {F/j) на элементы списка вызовов данной функции (на рис. 2 элемент № 5).

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

Для тестирования были взяты простые программы, содержащие 9 типов ошибок, и 1 программа, не удовлетворяющая пользовательской проверке. Данные программы были запущены под управлением разработанной системы и систем-аналогов (MARMOT и ITAC). При каждом тесте в качестве начальных данных для разработанного средства отладки была предоставлена директория, содержащая 24 созданных шаблона.

Результаты проведенных тестов собраны в таблицу 1. По каждому тесту для инструментальных средств были выставлены следующие оценки: _ «++» — ошибка продиагностирована точно; указаны функции, приведшие к появлению ошибки, и их локализация в программе.

Таблица 1. Результаты тестирования средств отладки

ОШИБКА MARMOT ITAC Собственное средство

I. Гонка данных, обусловленная применением макроса MPI ANY SOURCE + - -- ++

2. Потенциальный дедлок (2 процесса выполняют встречные операции MPI Send) -- + - ++

3. Несоответствие в размере сообщений точка-точка (буфер процесса-приемника больше) -- -- ++

4. Несоответствие в типе данных (процесс отправляет сообщение другого типа, чем принимает адресат) -- ++ ++

5. Непарная посылка (процесс выполняет MPI_Send, но адресат не вызывает операцию приема) -- + - ++

6. Ошибка «грязных данных» (основной поток изменяет данные, участвующие в неблокирующей коммуникации) -- ++ ++

7. Неблокирующая коммуникация без функции ожидания ++ ++ ++

8. Несоответствие в номере корневого процесса при коллективной коммуникации + - ++ ++

9. Не полностью запущенная коллективная операция (MPI Beast, вызванный не всеми процессами) + - + - ++

10. Пользовательская проверка на превышение количества передаваемых элементов заданного значения -- -- ++

— «+ —» — в сообщении не содержится четкого указания на существующую ошибку, но имеется какая-либо информация, сужающая область поиска проблемы (например, выявлено зависание процессов).

— «--» — отсутствуют сообщения, каким-либо образом способствующие обнаружению ошибки.

Тестирование показало, что свободно-распространяемое средство MARMOT плохо обнаруживает глобальные ошибки и применяет «грубые» и неточные алгоритмы поиска некорректного использования MPI-стандарта. ITAC способен обнаружить большее число ошибок, однако данная система работает только с Intel MPI. К тому же и ITAC обнаруживает далеко не все ошибки, вызванные неверным использованием MPI. В результате некоторых ситуаций, вызванных семантическими ошибками, ITAC «подвешивает» программу, поскольку многие MPI-функции преднамеренно реализованы в данной системе как блокирующие. Такой подход является достаточно «грубым» и далеко не всегда сообщение о возникшей ситуации зависания дает очевидное представление пользователю об истинной причине данной ситуации. Пользовательские проверки не способна производить ни одна из систем, за исключением разработки диссертанта.

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

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

f

внедрении в центр коллективного пользования «Высокопроизводительные параллельные вычисления» КемГУ, определение системы описания шаблонов в расширенной форме Бэкуса-Наура, текст 24 шаблонов и листинги программ, для отладки которых было применено разработанное средство.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В ДИССЕРТАЦИИ

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

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

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

4. Создано программное средство отладки, обнаруживающее шаблонные ситуации во время работы MPI-приложений.

5. Разработаны рекомендации по составлению текстовых шаблонов и применению созданного программного средства.

Результаты работы соответствуют следующим пунктам паспорта специальности 05.13.11: «Модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования» (п.1); «Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования» (п.8).

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях, рекомендованных ВАК РФ:

1. Власенко, А. Ю. Модель масштабируемой системы автоматического контроля корректности параллельных программ / А. Ю. Власенко // Вестник НГУ. Серия: Информационные технологии. — 2009. - Т.7, № 4. -С. 53-66. - 1 п.л.

2. Власенко, А. Ю. Система автоматического контроля корректности и виртуальная лаборатория как компоненты информационно-вычислительного портала / А. Ю. Власенко, H. Н. Окулов // Научно-технический вестник Поволжья.-2011. - №6.-С. 120-123. — 0,3 пл./0,15 п.л.

3. Афанасьев, К. Е. Автоматизированный анализ корректности MPI-программ на основе определенных пользователем шаблонов ошибочного поведения / К. Е. Афанасьев, А. Ю. Власенко // Вестник Томского государственного университета. Серия: Управление, вычислительная техника и информатика. - 2014. - №1 (26). - С. 75-83. - 0,7 п.л. / 0,5 п.л.

?

В рецензируемом журнале

4. Афанасьев, К. Е. Семантические ошибки в параллельных программах для систем с распределенной памятью и методы их обнаружения современными средствами отладки / К. Е. Афанасьев, А. Ю. Власенко // Вестник КемГУ. - 2009. - №2. - С. 13-20. - 0,54 п.л. / 0,27 п.л.

В материалах конференций и семинаров

5. Власенко, А. Ю. Архитектура и принципы работы масштабируемого инструментального средства динамического обнаружения семантических ошибок в MPI-программах / А. Ю. Власенко // Материалы IX международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах». — Владимир: изд-во Владимирского государственного университета, 2009. - С. 73-76. - 0,32 п.л.

6. Власенко, А. Ю. Комплекс информационных систем поддержки параллельных вычислений в рамках информационно-вычислительного портала / А. Ю. Власенко, Н. Н. Окулов // Труды международной суперкомпьютерной конференции «Научный сервис в сети Интернет: экзафлопсное будущее». - Абрау-Дюрсо, 2011. - С. 517-523. - 0,5 п.л. / 0,25 пл.

7. Афанасьев, К. Е. Реализация подхода автоматического контроля корректности в распределенной информационной системе / К. Е. Афанасьев, А. Ю. Власенко // Программа и тезисы докладов шестой сибирской конференции по параллельным и высокопроизводительным вычислениям. - Томск, 2011. - С. 78-79. - 0,07 пл. / 0,05 п.л.

8. Власенко, А. Ю. Программный комплекс для анализа, отладки и оптимизации параллельных приложений / А. Ю. Власенко, Н. Н. Окулов, А. В. Демидов // Параллельные вычислительные технологии (ПаВТ'2012): труды международной научной конференции (Новосибирск, 26 - 30 марта 2012 г.). - Челябинск, 2012. С. 715. - 0,09 п.л. / 0,03 пл.

Свидетельство об официальной регистрации программы для ЭВМ

9. Афанасьев К. Е., Власенко А. Ю. Свидетельство о государственной регистрации программы для ЭВМ № 2012610206 «Распределенная автоматизированная система обнаружения логических ошибок в MPI-программах» от 10.01.2012 // Реестр программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам. Москва, 2012.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кемеровский Государственный Университет»

На правах рукописи

Власенко Андрей Юрьевич

АВТОМАТИЗИРОВАННЫЙ КОНТРОЛЬ КОРРЕКТНОСТИ МИ-ПРОГТАММ НА ОСНОВЕ ШАБЛОНОВ ОШИБОЧНОГО

ПОВЕДЕНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: доктор физико-математических наук, профессор Афанасьев К.Е.

Кемерово - 2014

Оглавление

Оглавление....................................................................................................................2

Введение.........................................................................................................................5

ГЛАВА 1. СЕМАНТИЧЕСКИЕ ОШИБКИ В ПАРАЛЛЕЛЬНЫХ ПРОГРАММАХ И ПОДХОДЫ К ИХ ОБНАРУЖЕНИЮ................................17

1.1 Семантические ошибки в параллельных программах....................................17

1.2 Опрос пользователей..........................................................................................28

1.3 Методы и программные средства обнаружения семантических ошибок ....31

1.3.1 Диалоговая отладка...........................................................................................................31

1.3.2 Верификация модели программы.....................................................................................34

1.3.3 Сравнительная отладка.....................................................................................................37

1.3.4 Автоматизированный анализ корректности....................................................................38

1.3.5 Анализ по трассе................................................................................................................40

1.3.6 Анализ во время исполнения............................................................................................43

ГЛАВА 2. ШАБЛОНЫ ОШИБОЧНОГО ПОВЕДЕНИЯ..................................52

2.1 Система описания шаблонов ошибочного поведения....................................52

2.2 Примеры шаблонов............................................................................................58

2.2.1 Шаблоны для локальных ошибок....................................................................................61

2.2.2 Шаблоны для глобальных ошибок...................................................................................66

ГЛАВА 3. МОДЕЛЬ И АЛГОРИТМЫ ОБНАРУЖЕНИЯ СЕМАНТИЧЕСКИХ ОШИБОК СИСТЕМОЙ АВТОМАТИЗИРОВАННОГО КОНТРОЛЯ КОРРЕКТНОСТИ.....................74

3.1 Требования к системе автоматизированного контроля корректности. Анализ требований...................................................................................................74

3.2 Моделирование поведения системы автоматизированного контроля корректности.............................................................................................................77

3.3 Архитектура и основные структуры данных...................................................81

3.3.1 Конфигурационный файл..................................................................................................81

3.3.2 Утилита запуска.................................................................................................................85

3.3.3 Препроцессор.....................................................................................................................88

3.3.4 MPI-процессы.....................................................................................................................91

3.3.5 Сервер-анализатор.............................................................................................................93

3.4 Процесс выявления соответствия поведения MPI-программы шаблонам ошибочного поведения..........................................................................................105

ГЛАВА 4. ТЕСТИРОВАНИЕ СИСТЕМЫ АВТОМАТИЗИРОВАННОГО КОНТРОЛЯ КОРРЕКТНОСТИ. ПРИМЕРЫ АНАЛИЗА ПРОГРАММ.....115

4.1 Тестовая база.....................................................................................................115

4.2 Используемые тесты........................................................................................116

4.3 Анализ проведенных тестов............................................................................146

4.4 Отладка прикладных MPI-программ..............................................................148

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

Список литературы.................................................................................................156

Приложение 1. Определение системы описания шаблонов в расширенной форме Бэкуса-Наура................................................................................................168

Приложение 2. MPI-программа сортировки массива методом чет-нечетной перестановки.............................................................................................................169

Приложение 3. MPI-программа поблочного умножения матрицы на вектор.........................................................................................................................175

Приложение 4. Текст шаблонов для распространенных ошибок MPI-программ ...................................................................................................................180

Приложение 5. Свидетельство о регистрации разработанного программного средства......................................................................................................................191

Приложение 6. Акт о внедрении программного средства...............................192

Введение

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

Таким образом, потребности прикладных исследователей являются одним из главных факторов, способствующих постоянному росту производительности вычислительных систем. Для увеличения быстродействия ЭВМ применяются различные методы, среди которых одну из ключевых ролей играет распределение вычислительной нагрузки по нескольким устройствам. Этот принцип носит название «параллелизм». Параллелизм применяется на многих этапах обработки информации в компьютере [46].

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

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

Приблизительно с 1970-го по 1985 год производительность процессоров росла преимущественно за счет совершенствования элементной базы и увеличения тактовой частоты. Затем, вплоть до 2000 года, основную роль стали играть архитектурные усовершенствования — конвейеризация, суперскалярность, спекулятивные вычисления, кэширование, увеличение разрядности [30, 41]. К настоящему времени ресурс повышения тактовой частоты практически исчерпан и в апреле 2005 года ведущие компании этого рынка Intel и AMD одновременно приступили к продаже двухъядерных процессоров даже для персональных компьютеров. На сегодняшний день число ядер процессоров увеличивается, но, несмотря на это, для многих численных задач (примеры таких задач приведены выше) производительности современных ПК явно недостаточно. Пределом увеличения производительности за счет множества процессорных ядер в пределах одного сервера являются суперкомпьютеры с общей памятью. Но когда такая система включает более 32 (максимум 64) ядер, то встает проблема некоторых физических ограничений, не только не способствующих росту производительности, но даже сокращающих ее [30].

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

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

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

-Языки программирования: языки модели PGAS (Partitioned Global Address Space) [55, 67], SNet [62], MC# [63], система Норма[33], Т-система[11], C-DVM (Distributed Virtual Machine) [36], Fortran-DVM[15].

-Предметно-ориентированные высокоуровневые библиотеки [16]: MKL

[38], PETSc [43,53].

-Библиотеки односторонних обменов: SHMEM [68], GASNET (Global-Address Space Networking) [57], ARMCI (Aggregate Remote Memory Copy Interface) [79];

-Системы автоматизированного распараллеливания: CAPTools (Computer Aided Parallelization Tools) [80], Parawise [69], BERT77 [56].

Однако стандартом де-факто при разработке параллельных программ для вычислительных систем с распределенной памятью является MPI (Message Passing Interface) [78, 32]. MPI - это стандарт, использующий модель передачи сообщений между совместно протекающими процессами [44], реализациями которого являются библиотеки функций. Спецификация MPI содержит множество коммуникационных процедур различного характера: посылки типа точка-точка, широковещательные рассылки, редукционные операции, функции для организации процессов в группы и др. На сегодняшний день существуют как свободно-

распространяемые (MPICH, MPI-LAM, OpenMPI, MVAPICH), так и коммерческие реализации данного стандарта, адаптированные под конкретную вычислительную или сетевую архитектуру (IntelMPI, HP-MPI, Microsoft MPI, ScaliMPI). Благодаря тому, что при использовании MPI прикладной исследователь оперирует с памятью на низком уровне, то, создавая MPI-приложение, можно добиться высокой производительности параллельного кода.

К сожалению, параллельное программирование в MPI-стандарте - сложная и трудоемкая задача. Пользователю приходится проектировать свое приложение таким образом, чтобы загрузить работой несколько вычислительных узлов кластера. Причем для того, чтобы программа была эффективной, она должна быть способной работать с любым количеством процессоров, предоставленным в ее пользование в момент запуска и равномерно распределять нагрузку между ними. Наибольшее количество проблем в большинстве случаев возникает на этапе отладки приложения. Даже из практики разработки последовательного программного обеспечения известно, что примерно 2/3 времени, затрачиваемого на создание системы, приходится на отладку [50]. Ситуация еще более усложняется тем, что при распараллеливании программы на п независимых процессов, число ошибок в общем случае следует умножать на п. К тому же стандартные техники тестирования и отладки неэффективны применительно к параллельным программам, потому как из-за взаимодействия параллельно работающих процессов на разных узлах кластерной системы возникает широкое множество ошибок, которые не имеют место в последовательных программах. Среди этих ошибок наиболее опасны потенциальные, возникающие из-за большого количества источников недетерминированного поведения таких программ во время работы [85].

s

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

В построении высокопроизводительных вычислительных комплексов за последние годы наметилась тенденция резкого увеличения среднего числа вычислительных узлов на один комплекс. Соответственно увеличивается количество процессов параллельных программ, запускаемых на суперкомпьютерах. В связи с этим все более востребованными становятся автоматизированные средства отладки. Существенной проблемой создания систем данной категории является то, что организовать проверки на все возможные ошибки в пользовательской программе чрезвычайно сложно. Причина этого заключается, во-первых, в том, что MPI-стандарт накладывает огромное количество ограничений на аргументы и последовательность вызовов функций, а несоблюдение любого ограничения является ошибкой. Во-вторых, MPI-стандарт регулярно претерпевает изменения (до настоящего момента были выпущены версии 1.0, 1.1, 1.2, 1.3, 2.0, 2.1, 2.2, 3.0 стандарта), и каждая версия привносит новые функции, типы данных, константы и пр. В то же время пользователю далеко не всегда требуется выполнение системой всех возможных проверок на его программе - зачастую он приблизительно представляет, в каких местах и функциях может возникнуть ошибка, а излишние проверки создают дополнительную нагрузку на вычислительную систему.

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

позволит не только обнаруживать ошибки, но и осуществлять пользовательские проверки.

Цель работы

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

Для достижения поставленной цели были сформулированы следующие задачи:

1) Выполнить обзор и анализ методов и инструментальных средств отладки параллельных программ.

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

3) С помощью разработанной системы описания формализовать наиболее распространенные семантические ошибки в MPI-приложениях.

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

5) Провести тестирование инструментального средства отладки и сопоставить его с аналогами.

Методы исследований

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

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

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

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

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

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

Практическая ценность работы заключается в том, что:

1) Разработанные шаблоны ошибочного поведения применимы для анализа МР1-программ на наличие семантических ошибок.

2) Созданное программное средство предоставляет прикладным программистам инструментарий для выявления семантических ошибок в МР1-программах в автоматизированном режиме, что существенно сокращает время разработки параллельных приложений и увеличивает эффективность

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

3) Рекомендации, разработанные для пользователей программного средства, применимы как при описании ошибочного поведения, так и при проведении автоматизированного контроля корректности MPI-программ.

Первая глава да