О построении упрощенной модели библиотеки MPI в терминах сетей Петри

АННОТАЦИЯ

В работе предложена минимальная модель библиотеки MPI. Представлена цветная сеть Петри, описывающая минимальный набор функций MPI, необходимый для функционирования параллельной программы. Этот набор включает в себя: функцию инициализации работы библиотеки ‑ MPI_Init, после вызова которой разрешены вызовы других функций MPI; функции коллективных операций MPI_Scatter и MPI_Gather, рассчитанные на участие всех процессов во взаимодействии, принадлежащих коммуникатору MPI_COMM_WORLD; функцию двунаправленного обмена данными между вычислительными процессами MPI_SendRecv; a также функцию корректного завершения – MPI_Finalize, после вызова которой функции MPI вызываться не должны. Моделирование функций выполнено с использованием событий начала и конца работы функции. Для моделирования коллективных операций использован приём, собирающий поочерёдно все процессы в состоянии после начала работы функции, затем внутренний переход моделирует выполнение взаимодействия одновременно для всех процессов, и окончательно процессы поочерёдно заканчивают выполнение коллективной операции. Представлена развертка цветной сети Петри, в которой: каждое параметризованное место заменяется множеством мест, каждому из которых назначается единственное значение параметра; каждый параметризованный переход заменяется множеством переходов, соответствующих единственной комбинации входных параметров. Новые места и переходы соединяются дугами, так чтобы исходные выражения цветной сети выполнялись.

ABSTRACT

In the article the minimal model of the MPI library is proposed. The coloured Petri net describing the minimal set of MPI functions required for most parallel programs is presented. The set includes a function of library initialization MPI_Init, after which other MPI calls are allowed; collective operations MPI_Scatter and MPI_Gather requiring all processes in communicator group to participate in communication; function MPI_SendRecv of bidirectional data exchange between computing processes in communicator MPI_COMM_WORLD; as well as a function MPI_Finalize for the correct completion of a parallel program, after which MPI functions are not to be called. The modeling of functions is fulfilled using start and finish events of the function. The collective operation is modeled using the following approach. First, all processes are collected one by one in the special state just after start event. Second, the especial internal transition is fired to designate that all processes together start specific collective operation. After communications, processes are exited sequentially from collective operation in arbitrary order. Unfolding of the coloured Petri net to ordinary Petri net is presented. Each coloured place is replaced on a set of simple places each of which designates one value from a color. Each parameterized transition is replaced on a set of simple transitions each of which corresponds to combination of transition input parameters. New places and transitions are connected by arcs, so that the original expressions of the colored net are conserved unaltered.

Введение

С момента появления многоядерных и мультиядерных архитектур наблюдается стремительный рост производительности вычислительных систем. В настоящее время уже преодолен барьер в 1 PFLOPS (10¹⁵ операций в секунду), ведутся исследования по созданию «экзафлопной» машины (10¹⁸ операций в секунду).

Однако, параллельное программирование остаётся настолько сложным процессом, что больше напоминает искусство, чем техническую работу. При переходе от последовательного алгоритма к параллельному для получения эффективного параллельного кода зачастую необходимо полностью изменить логику работы последовательного алгоритма. При этом в параллельном коде чрезвычайно тяжело найти ошибки с помощью отладки. Среди всего многообразия существующих программ только считанные единицы прошли формальную верификацию, доказывающую их корректность. В 2003 году Ч.Э. Хоар отнес проблему создания верифицирующего компилятора к разряду крупнейших нерешенных научно-технических задач современности (Grand Challenge) [5].

До сих пор не существует коммерчески значимых средств формальной автоматизированной проверки корректности программ. Сети Петри – один из немногих формальных языков, позволяющий автоматизировать процесс построения моделей поведения программных систем. Программная инженерия и сети Петри неоднократно пересекались в прошлом, рождая интересные идеи в обеих областях [4]. Авторами были сделаны определённые шаги в направлении моделирования императивных программ [1,2,6]. В 2008 группой авторов [3, 7] было сформулировано требование разбиения кода программ на отдельные элементы различной степени детализации, верификация которых может быть произведена независимо от всех остальных элементов программы. При этом для анализа поведения программы необходимо иметь не только модель вычислительного процесса, построенного на основании исходного кода программы, необходима также модель окружающей среды, в которой должна выполняться программа.  В связи с этим работы, направленные на построение композициональных моделей специализированных библиотек, предназначенных для разработки параллельных программ, являются особенно актуальными.

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

Минимальная модель библиотеки MPI

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

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

Рисунок 1. Минимальная модель MPI в терминах цветных сетей Петри

На рисунке 1 представлена цветная сеть Петри, описывающая минимальный набор функций MPI, необходимый для функционирования параллельной программы. Этот набор включает в себя функцию инициализации работы библиотеки – MPI_Init, после вызова которой разрешены вызовы других функций MPI. Функцию корректного завершения – MPI_Finalize, после вызова которой функции MPI вызываться не должны. Функции коллективных операций MPI_Scatter (функция рассылает данные из буфера определенного процесса всем процессам) и MPI_Gather (функция осуществляет сбор данных со всех процессов в буфере определенного процесса), рассчитанные на участие всех процессов во взаимодействии, принадлежащих коммуникатору MPI_COMM_WORLD. Коммуникатор – это объект, представляющий собой идентификатор группы запущенных программой параллельных процессов, которые могут обмениваться сообщениями. А также функцию двунаправленного обмена данными между вычислительными процессами MPI_SendRecv. Моделирование всех функций выполнено с использованием двух событий – начала и конца работы функции. Для моделирования коллективных операций использован приём, собирающий поочерёдно все процессы в состоянии после начала работы функции, затем внутренний переход, скрывающий подробности реализации, моделирует выполнение взаимодействия одновременно для всех процессов, и окончательно процессы поочерёдно заканчивают выполнение коллективной операции.

Цветная сеть Петри, описывающая минимальную модель MPI, имеет менее тридцати мест и переходов, из которых десять мест и переходов содержат разметку с использованием параметров, соответствующих rank‑у (номеру процесса в коммуникаторе) вычислительных процессов. Для анализа корректности взаимодействий в параллельной программе необходимо выполнить развёртку этой сети. Для этого была разработана автоматическая процедура развертки цветной сети. При этом каждое параметризованное место заменяется множеством мест, каждому из которых назначается единственное значение параметра. Каждый параметризованный переход заменяется множеством переходов, соответствующих единственной комбинации входных параметров. Новые места и переходы соединяются дугами, так чтобы исходные выражения цветной сети выполнялись. При такой развертке количество элементов исходной сети значительно увеличивается. На рисунке 2 представлена развертка минимальной сети для двух вычислительных процессов, в которой общее количество мест и переходов приближается к сорока. Для трех процессов количество мест и переходов будет порядка 55, а для четырёх – порядка 75. Фактически увеличение количества процессов показывает, что при анализе сетей желательно использовать привязку результатов к исходной цветной сети, так как сети с большим количеством элементов невозможно изобразить в читабельном виде.

Рисунок 2. Развертка минимальной модели MPI для двух процессов

Заключение

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

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