MPI как средство параллельной подДержки програмной реализации сетевого объекта 

Смагин А.Н., Резник В.Н., Бервено В.С.
Донецкий Национальный Технический Университет
Кафедра Электронных Вычислительных Машин

smagin@cs.dgtu.donetsk.ua
bonvlad@tcc-online.com
bvs@ukrtop.com

Abstract 

Smagin A.N., Reznik V.N., Berveno V.S. MPI as means of parallel support of program realization of network object. Program realization of network object is discussed. MPI as means of parallel support is considered. Analyse of hierarchy of parallel programming means is described. 

1.	Анализ иерархии средств параллельного программирования
Создание параллельной программы включает в себя две основных стадии: 

    -    декомпозиция (распараллеливание) последовательного алгоритма, 
-	распараллеленный алгоритм записывается в виде программы. 

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

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

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

Рис. 1 – Иерархия средств разработки параллельного приложения

2.	MPI или Shared Memory?
Перед тем, как перейти непосредственно к программированию, необходимо выбрать одни из стандартов, а для этого рассмотрим преимущества и недостатки данных стандартов.

Преимущества модели SHARED MEMORY (SHM): 
-	Функции работы с Shared Memory непосредственно входят в состав каждой многозадачной операционной системы. В пределах одного компьютера средства межпроцессовой коммуникации реализуются через SHM, и потому заведомо являются более быстрыми.
-	В модели с общей памятью, совместно используемые данные хранятся в такой памяти в единственном экземпляре, без создания локальных копий. Процессы, работающие с такими данными, затрачивают незначительное время на синхронизацию доступа к данным, и в целом соотношение скорости коммуникаций и скорости вычислений в модели с общей памятью выше, чем в модели с передачей сообщений. Следовательно, класс задач, пригодных к распараллеливанию в SHM, в принципе шире, нежели в MPI. 
-	SHM намного дольше используется для программирования высокопроизводительных вычислений, и многие работы по исследованию данного принципа программирования выразились в наработанном коде и методах. 

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

Преобладающие преимущества MPI над  SHM выражаются в следующем: 
-	все имеющиеся реализации SHM API в принципе непереносимы за пределы SMP-машин, недостаточно эффективны или недостаточно распространены; 
-	стоимость вычислений и коммуникаций в SMP-машинах падает медленнее, чем в MPP-комплексах и сетях; 
-	методика обмена данными в виде сообщений обладает изначально большей наглядностью для программиста;
-	в отличие от MPI, SHM API, как правило, реализует только самые базовые операции. 
Таким образом, можно сделать вывод, что MPI повышает скорость выполнения программ, а также повышает скорость их написания.

3.	Особенности программной реализации сетевого объекта (СО)
                   На рисунке 2 приведена алгоритмическая структура модели СО, базирующаяся на уравнениях объекта.

Рис. 2 – Алгоритмическая структура модели СО
Описание блоков алгоритмической структуры модели:
СДС – сложная динамическая система любой физической природы, в которой происходят переходные или динамические процессы.
Математическая модель – аппаратно-программные средства, в которых с заданной или требуемой точностью воспроизводятся динамические процессы, протекающие в СДС. Основой для разработки мат. модели СДС является ее формальное описание.
	Топологический анализатор (ТА) – аппаратно-программные средства, обеспечивающие удобное описание топологии на некотором входном языке (формально-вербальном), кодирование топологии, формирование описаний топологий, по которым могут быть составлены уравнения протекания процессов. 
Генератор уравнений (ГУ) – программное средство, которое по данным ТА и по уравнениям элементов СДС формирует систему уравнений всей СДС в целом. Генератор уравнений выполняет матрично-векторные операции, соответствующие переходу от одной системы уравнений к другой, удобную для численного решения. 
Решатель уравнений (РУ) – аппаратно-программное средство, которое реализует некоторый численный метод решения сформированных уравнений. РУ включает блок инициализации (ввод параметров из файла, задание векторов начальных условий Y(0)), блок цикла с управлением по точности или по заданному времени интегрирования и блок визуализации. 
Визуализация результатов моделирования (ВРМ) – представляет собой средства компьютерной графики, с помощью которых в наглядной форме представляются результаты моделирования.
Подсистема диалога – програмное средство, обеспечивающее для пользователя «доброжелательный» интерфейс со всеми функциональными блоками СДС.
С точки зрения распараллеливания интерес представляет решатель уравнений. 
Рассмотрим два подхода к распараллеливанию программы РУ:
	-    основан на MIMD структуре,   
	-    основан на SPMD  структуре.
      Поиск варианта MIMD-распараллеливания можно вести в рамках следующих трех программных структур.

      Процесс Т1 запускает выполнение процессов. До начала возможного параллельного выполнения Т1 … Тn, «ведущий» процесс выполняет большое число последовательных операций, чтобы «породить» параллельные управляющие потоки Т2 … Тn.
      Далее эти процессы работают параллельно и достигают каждый окончания своей программы и операции объединения, которая ведет к синхронизации с процессом Т1 и к терминации указанных потоков. Для каждой параллельной нити в программе генерируются заново и заканчиваются управляющие потоки.
      Генерирование и детерминирование управляющих потоков вызывает большие затраты ресурсов. 

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

                   Оба выше описанных методов объединяет метод Reusable-thread-pool-модель. 

      С помощью которого нам удается:
уменьшить объем работ, связанных с многократным генерированием и терминированием управляющих потоков (процессы), исключить многократное исполнение последовательных частей программы.        
       Основная идея заключается в том, что новые процессы генерируются, если они требуются в программе, т.е. к началу параллельной части программы. В конце параллельного блока программы управляющие потоки переводятся в состояние «недействующий» и к началу следующего параллельного участка снова активизируются. Таким образом последовательная часть программы выполняется только одним управляющим потоком. 

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

4.	Использование MPI в качестве параллельной поддержки СО 
         Рассмотрим типы обмена данными, которые необходимы для параллельной поддержки СО.  Векторно-матричная запись X = -W*Y разворачивается в (n-1) операций вида: 
                                                    
         Эти операции требуют следующую виртуальную структуру обмена данными между процессами:

Рис. 3 – Структура обмена данными от TYk к TX

         Так как каждый TХ – процесс требует ввода данных от всех процессов TY, то отправитель TYk после вычисления своей компоненты Yk(i) должен выполнить посылку типа «broadcast»:

Рис. 4 – Операция типа «broadcast»

           Виртуальный обмен осуществляется по алгоритму, приведенному на рис. 5.

Рис. 5 – Блок-схема виртуального объекта

          При максимальном распараллеливании операции «broadcast» передачу вектора Y каждому процессу TX можно осуществлять за 5 шагов (рис. 5). 
          Изложенные соображения используем при отображении виртуального обмена (коммуникаций) на распределенный кластер.
	   Литература
1.	Евсеев И.: „MPI – программный инструмент для параллельных вычислений“. (http://www.csa.ru:81/~il/mpi_tutor/intro.shtmr).
2.	Резник В.Н., Смагин А.Н.: „Параллельное моделирование сетевого динамического объекта на основе MIMD-модели с помощью MPI“.  Методические материалы.
3.	Абрамов Ф.А., Фельдман Л.П., Святный В.А.: „Моделирование динамических процессов рудничной аэрологии“. Киев, Наукова думка, 1981, 291 с.
4.   Святний В.А.: „Проблеми паралельного моделювання складних динамічних систем“. Наукові праці ДонДТУ, Серія ІКОТ, вип. 6., 1999, с. 6-14.