= MPI =

программный инструмент
для параллельных вычислений

Краткий обзор: назначение, особенности, перспективы

[ Автор: Илья Евсеев ]
[ Организация: ИВВиБД ]
[ Подразделение: ЦСТ ]

Содержание

 

Место MPI в иерархии средств
параллельного программирования

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

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

С точки же зрения программиста базовых методик работы (или, как нынче принято говорить, парадигм) две - данные могут передаваться:

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

Следовательно, единый интерфейс программиста может быть создан, тем не менее долгое время создатели компьютеров и операционных систем шли разными путями. Например, для работы с семафорами и разделяемой памятью в Windows, в Юниксах 4.4BSD и SVR4 примерно одни и те же действия представлены разными наборами системных вызовов. В мире локальных/глобальных сетей стандарт вроде бы выработан - это TCP/IP. Однако для работы с внутримашинными сетями, где состав абонентов и маршрутизация трафика жестко фиксированы, а вероятность доставки пакетов равна 100%, универсальность и гибкость TCP/IP отрицательно сказываются на скорости, поэтому для MPP-машин интерфейсы программиста создаются индивидуально (или, вернее, создавались индивидуально до тех пор, пока не появился MPI).

Таким образом, можно считать назревшей потребность в стандарте на интерфейс программиста, который бы сделал создание параллельных приложений таким же:

... каким Си и Юникс сделали программирование вообще. Стандартом по выбору основных производителей ЭВМ решено сделать MPI. Ими образован MPI Forum, и в свет выпущена спецификация, которой должны удовлетворять все конкретные разработки. Головная организация проекта - Аргоннская национальная лаборатория США - распространяет пакет MPICH (MPI CHameleon), перенесенный на большинство платформ. Большая часть созданных другими разработчиками реализаций MPI базируется на MPICH. По идее, в итоге иерархия средств разработки должна стать примерно такой:

Параллельное приложение
Средства быстрой разработки приложений (RAD)
Распараллеливающие препроцессоры

M P I

разделяемая память
и семафоры 		индивидуальные интерфейсы
с передачей сообщений 		TCP/IP
SMP-машины MPP-машины сети

 

Правила работы с MPI

MPI расшифровывается как Message Passing Interface - Интерфейс с передачей сообщений, т.е. конкретному стандарту присвоено название всего представляемого им класса программного инструментария. В его состав входят, как правило, два обязательных компонента: Кроме того, может присутствовать справочная система (manual pages для Юникса), командные файлы для облегчения компиляции/компоновки программ и все такое прочее. В стандарте отсутствует все лишнее, например, нет средств автоматического переноса и построения копий исполняемого файла в сети. Это нужно, если MPI-приложение предстоит выполнять сетью машин - но это можно выполнить и утилитами Юникса. В стандарте нет никаких средств автоматической декомпозиции, нет отладчика (правда, есть функции хронометража и предусмотрена возможность профилирования). То есть это система межпроцессовой связи в чистом (можно даже сказать - в голом) виде, и не более того.

Для MPI принято писать программу, содержащую код всех ветвей сразу. MPI-загрузчиком запускается указываемое количество экземпляров программы. Каждый экземпляр определяет свой порядковый номер в запущенном коллективе, и в зависимости от этого номера и размера коллектива выполняет ту или иную ветку алгоритма. Такая модель параллелизма называется Single program/Multiple data ( SPMD ), и является частным случаем модели Multiple instruction/Multiple data ( MIMD ). Каждая ветвь имеет пространство данных, полностью изолированное от других ветвей. Обмениваются данными ветви только в виде сообщений MPI.

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

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

 

Функции пересылки данных

Хотя с теоретической точки зрения ветвям для организации обмена данными достаточно всего двух операций (прием и передача), на практике все обстоит гораздо сложнее. Одними только коммуникациями "точка-точка" (т.е. такими, в которых ровно один передающий процесс и ровно один принимающий) занимается порядка 40 функций. Пользуясь ими, программист имеет возможность выбрать: 2 простейшие (но и самые медленные) функции - MPI_Recv и MPI_Send - выполняют блокирующую приемопередачу с автоматическим выбором зацепления (кстати сказать, все функции приема совместимы со всеми функциями передачи).

Таким образом, MPI - весьма разветвленный инструментарий. Приведу цитату из раннего себя: "То, что в конкурирующих пакетах типа PVM реализовано одним-единственным способом, в MPI может быть сделано несколькими, про которые говорится: способ А прост в использовании, но не очень эффективен; способ Б сложнее, но эффективнее; а способ В сложнее и эффективнее при определенных условиях".

Замечание о разветвленности относится и к коллективным коммуникациям (при которых получателей и/или отправителей несколько): в PVM эта категория представлена одной функцией, в MPI - 9 функций 5 типов:

На упреки типа "Зачем столько всего сваливать в одну кучу? Программисту легче будет в случае необходимости самому написать такую функцию, нежели разбираться в разбухшей документации?" можно возразить, что, например, вариант-самоделка "один-всем" будет, скорее всего, выглядеть примерно так: 
    if( myRank == 0 )
    {
        for( i=1; i < numLoops; i++ )
            MPI_Send( ... , i, ... );
    } else
        MPI_Recv( ... , 0, ... );
... в то время, как имеющиеся в MPI функции оптимизированы - не пользуясь функциями "точка-точка", они напрямую (на что, согласно идеологии MPI, программа пользователя права не имеет) обращаются: А если такая архитектурно-зависимая оптимизация невозможна, используется оптимизация архитектурно-независимая (интересно, как много программистов захотело бы делать ее вручную?): передача производится не напрямую от одного ко всем (время передачи линейно зависит от количества ветвей-получателей), а по двоичному дереву (время передачи логарифмически зависит от количества). Как следствие, скорость работы повышается.

 

Коллективы ветвей

В MPI хорошо продумано объединение ветвей в коллективы. В сущности, такое деление служит той же цели, что и введение идентификаторов для сообщений: помогает надежнее отличать сообщения друг от друга. В большинстве функций MPI имеется параметр типа "коммуникатор", который можно рассматривать как дескриптор (номер) коллектива. Он ограничивает область действия данной функции соответствующим коллективом. Коммуникатор коллектива, который включает в себя все ветви приложения, создается автоматически при старте и называется MPI_COMM_WORLD.

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

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

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

 

Зачем MPI знать о типах данных

О типах передаваемых данных MPI должен постольку-поскольку при работе в сетях на разных машинах данные могут иметь разную разрядность (например, тип int - 4 или 8 байт), ориентацию (младший байт располагается в ОЗУ первым на процессорах Intel, последним - на всех остальных), и представление (это, в первую очередь, относится к размерам мантиссы и экспоненты для вещественных чисел). Поэтому все функции приемопередачи в MPI оперируют не количеством передаваемых байт, а количеством ячеек, тип которых задается параметром функции, следующим за количеством: MPI_INTEGER, MPI_REAL и т.д. Это переменные типа MPI_Datatype (тип "описатель типов", каждая его переменная описывает для MPI один тип). Они имеются для каждого базового типа, имеющегося в используемом языке программирования.

Однако, пользуясь базовыми описателями, можно передавать либо массивы, либо одиночные ячейки (как частный случай массива). А как передавать данные агрегатных типов, например, структуры? В MPI имеется механизм конструирования пользовательских описателей на базе уже имеющихся (как пользовательских, так и встроенных).

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

  • не налезают друг на друга,
  • не располагаются с разрывами (выравнивание полей в структурах не в счет).

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

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

     

    Чего нет в MPI, но будет в MPI-2

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

     

    Сравнение с PVM

    Сравнение необходимо, так как названия MPI и PVM часто упоминаются рядом.
    Итак, общие характеристики:

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

    Подробнее о PVM читайте тут.

     

    Сравнение с SHM

    Преимущества модели shared memory ( SHM ) по сравнению с MPI:

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

    Итак, почему MPI не(намного) хуже SHM:

    Почему MPI предпочтительнее SHM:

    Таким образом:

     

    Какое программное обеспечение существует
    между программистом и MPI

    MPI сам по себе является средством:

    Таким образом, программист заинтересован в инструментах, которые облегчали бы:

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

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

    Средства автоматической декомпозиции. Идеалом является такое оптимизирующее средство, которое на входе получает исходный текст некоего последовательного алгоритма, написанный на обычном языке программирования, и выдает на выходе исходный текст этого же алгоритма на этом же языке, но уже в распараллеленном на ветви виде, с вызовами MPI. Что ж, такие средства созданы (например, в состав полнофункционального пакета Forge входит, наряду с прочим, и такой препроцессор), но до сих пор, насколько мне известно, никто не торопится раздавать их бесплатно. Кроме того, вызывает сомнение их эффективность.

    языки программирования. Это наиболее популярные на сегодняшний день средства полуавтоматической декомпозиции. В синтаксис универсального языка программирования (Си или Фортрана) вводятся дополнения для записи параллельных конструкций кода и данных. Препроцессор переводит текст в текст на стандартном языке с вызовами MPI. Примеры таких систем: mpC (massively parallel C) и HPF (High Performance Fortran).

    Общим недостатком инструментов, производящих преобразование "текст в текст", является то, что синтаксическому разбору подвергаются оба текста: и исходный (его обрабатывает распараллеливающий препроцессор), и генерируемый (его обрабатывает компилятор). Это уменьшает скорость построения программы, и, кроме того, необходимость делать синтаксический разбор усложняет написание препроцессора. Поэтому, например, те фирмы-производители, которые поставляют свои ЭВМ вместе с Фортраном, встраивают HPF прямо в компилятор машинно-зависимого кода. Для расширений языка Си аналогичное решение может быть найдено в использовании GNU C.

    Оптимизированные библиотеки для стандартных языков. В этом случае оптимизация вообще может быть скрыта от проблемного программиста. Чем больший объем работы внутри программы отводится подпрограммам такой библиотеки, тем бОльшим будет итоговый выигрыш в скорости ее (программы) работы. Собственно же программа пишется на обычном языке программирования безо всяких упоминаний об MPI, и строится стандартным компилятором. От программиста потребуется лишь указать для компоновки имя библиотечного файла MPI, и запускать полученный в итоге исполняемый не непосредственно, а через MPI-загрузчик. Популярные библиотеки обработки матриц, такие как Linpack, Lapack и ScaLapack, уже переписаны под MPI.

    Средства визуального проектирования. Действительно, почему бы не расположить на экране несколько окон с исходным текстом ветвей, и пусть пользователь легким движением мыши протягивает стрелки от точек передачи к точкам приема - а визуальный построитель генерирует полный исходный текст? Тем, кто стряпал базы данных в Access'e, такая технология покажется наиболее естественной.

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

     

    Рекомендуемые источники информации по MPI

    Наконец, если у Вас есть вопросы, можете написать письмо мне.

     

    Версии документа

     


    Хостинг от uCoz