Международный
научный журнал

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


On construction of MPI library simplified model in terms of Petri nets

Цитировать:
О построении упрощенной модели библиотеки MPI в терминах сетей Петри // Universum: Технические науки : электрон. научн. журн. Леонтьев Д.В. [и др.]. 2017. № 10(43) . URL: http://7universum.com/ru/tech/archive/item/5195 (дата обращения: 12.12.2019).
 
Прочитать статью:

Keywords: modeling of computing processes, communicating sequential processes, Petri nets, MPI, interprocess communication, architecture of computing systems

АННОТАЦИЯ

В работе предложена минимальная модель библиотеки 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 (1015 операций в секунду), ведутся исследования по созданию «экзафлопной» машины (1018 операций в секунду).

Однако, параллельное программирование остаётся настолько сложным процессом, что больше напоминает искусство, чем техническую работу. При переходе от последовательного алгоритма к параллельному для получения эффективного параллельного кода зачастую необходимо полностью изменить логику работы последовательного алгоритма. При этом в параллельном коде чрезвычайно тяжело найти ошибки с помощью отладки. Среди всего многообразия существующих программ только считанные единицы прошли формальную верификацию, доказывающую их корректность. В 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 должна включать в себя работу со всеми параметрами функций, определяющими контекст взаимодействий. В будущих работах авторы ставят для себя задачу разработать подходы к решению данного вопроса.


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

1. Голенков Е.А., Соколов А.С., “Метод автоматического построения модели параллельной программы в терминах сетей Петри” // Вычислительные методы и программирование. – 2005. №63. С. 77–82.
2. Тарасов Г.В., Харитонов Д.И., Голенков Е.А., “Об одном представлении функции в модели императивной программы, заданной сетями Петри” // Моделирование и анализ информационных систем. – 2011. – Т. 18, № 2. С. 18–38
3. Харитонов Д.И. Раздельная верификация объектно-ориентированных программ с построением протокола С++ класса в терминах сетей Петри. // Моделирование и анализ информационных систем. – 2009. – Т. 16, №1. С. 92-112.
4. Denaro G., M. Pezz`e, “Petri nets and software engineering” // Lectures on Concurrency and Petri Nets – Springer Verlag. 2004. P. 439–466.
5. Hoare, C.A.R. The Verifying Compiler: A Grand Challenge for Computing Research // Journal of the ACM – 2003. Vol. 50. No. 1. P. 63-69.
6. Kharitonov D., Tarasov G., “Modeling function calls in program control flow in terms of Petri Nets” // ACSIJ Advances in Computer Science: an International Journal. – 2014. №12. С. 82–91.
7. Krone, J., Ogden, W., Sitaraman, M., Weide, B. Refocusing the Verifying Compiler Grand Challenge // Clemson University, School of Computing 05.2008. [Электронный ресурс] Режим доступа: URL: https://www.cs.clemson.edu/resolve/research/reports/RSRG-08-01.pdf. (дата обращения: 11.10.2017).

Информация об авторах:

Леонтьев Денис Васильевич Leontyev Denis

аспирант, Институт автоматики и процессов управления Дальневосточного отделения Российской академии наук, 690041, Россия, г. Владивосток, ул. Радио, д. 5

Postgraduate student, Institute of Automation and Control Processes, Far Eastern Branch Russian Academy of Sciences, 690041, Russia, Vladivostok, Radio str., 5


Парахин Роман Валерьевич Parakhin Roman

инженер-программист, Институт автоматики и процессов управления Дальневосточного отделения Российской академии наук, 690041, Россия, г. Владивосток, ул. Радио, д. 5

Software Engineer, Institute of Automation and Control Processes, Far Eastern Branch Russian Academy of Sciences, 690041, Russia, Vladivostok, Radio str., 5


Тарасов Георгий Витальевич Tarasov Georgiy

научный сотрудник, Институт автоматики и процессов управления Дальневосточного отделения Российской академии наук, 690041, Россия, г. Владивосток, ул. Радио, д. 5

Research scientist, Institute of Automation and Control Processes, Far Eastern Branch Russian Academy of Sciences, 690041, Russia, Vladivostok, Radio str., 5


Харитонов Дмитрий Иванович Kharitonov Dmitry

канд. техн. наук, Институт автоматики и процессов управления Дальневосточного отделения Российской академии наук, 690041, Россия, г. Владивосток, ул. Радио, д. 5

Candidate of Engineering Sciences, Institute of Automation and Control Processes, Far Eastern Branch Russian Academy of Sciences, 690041, Russia, Vladivostok, Radio str., 5


Читателям

Информация о журнале

Выходит с 2013 года

ISSN: 2311-5122

Св-во о регистрации СМИ: 

ЭЛ №ФС77-54434 от 17.06.2013

ПИ №ФС77-66236 от 01.07.2016

Скачать информационное письмо

Включен в перечень ВАК Республики Узбекистан

Размещается в: 

doi:

The agreement with the Russian SCI:

cyberleninka

google scholar

Ulrich's Periodicals Directory

socionet

Base

 

OpenAirediscovery

CiteFactor

Поделиться

Лицензия Creative CommonsЯндекс.Метрика© Научные журналы Universum, 2013-2019
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Непортированная.