Распределенные вычисления

Учебное пособие по курсу “Распределенные вычисления” для студентов математических специальностей.

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

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

Параллельные компьютеры и супер-ЭВМ

К классу супер-ЭВМ принадлежат компьютеры, которые имеют максимальную производительность в настоящее время. Быстрое развитие компьютерной индустрии определяет относительность данного понятия – то, что десять лет назад можно было назвать суперкомпьютером, сегодня под это определение уже не попадает. Например, производительность персональных компьютеров, использующих Pentium-III/800MHz, сравнима с производительностью суперкомпьютеров начала 70-х годов, однако по сегодняшним меркам суперкомпьютерами не являются ни те, ни другие.

В любом компьютере все основные параметры тесно связаны. Трудно себе представить универсальный компьютер, имеющий высокое быстродействие и мизерную оперативную память, либо огромную оперативную память и небольшой объем дисков. Следуя логике, делаем вывод: супер-ЭВМ это компьютеры, имеющие в настоящее время не только максимальную производительность, но и максимальный объем оперативной и дисковой памяти. Какие же суперкомпьютеры существуют в настоящее время в мире? Вот лишь несколько параметров, дающих достаточно красноречивую характеристику машин этого класса. В 2001 году компьютер ASCI WHITE, занимал первое место в списке пятисот самых мощных компьютеров мира. Он объединяет 8192 процессора Power 3 с общей оперативной памятью в 4 Терабайта и производительностью более 12 триллионов операций в секунду.

Простые расчеты показывают, что конфигурации подобных систем могут стоить не один миллион долларов США - ради интереса прикиньте, сколько стоят, скажем, лишь 4 Тбайта оперативной памяти? Возникает целый ряд естественных вопросов: какие задачи настолько важны, что требуются компьютеры стоимостью несколько миллионов долларов? Или, какие задачи настолько сложны, что хорошего Пентиума не достаточно? На эти и подобные им вопросы хотелось бы найти разумные ответы.

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

Примем упрощенную схему, при которой моделируемая область отображается в куб, однако и ее будет достаточно для оценки числа необходимых арифметических операций. Разумные размеры куба, при которых можно получать правдоподобные результаты - это 100*100*100 точек. В каждой точке куба надо вычислить от 5 до 20 функций: три компоненты скорости, давление, температуру, концентрацию компонент (вода, газ и нефть - это минимальный набор компонент, в более реалистичных моделях рассматривают, например, различные фракции нефти). Далее, значения функций находятся как решение нелинейных уравнений, что требует от 200 до 1000 арифметических операций. И, наконец, если исследуется нестационарный процесс, т.е. нужно понять, как эта система ведет себя во времени, то делается 100-1000 шагов по времени. Что получилось:

10⁶(точек сетки)*10(функций)*500(операций)*500(шагов по времени) = 2.5*10¹²

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

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

В 1995 году корпус автомобиля Nissan Maxima удалось сделать на 10% прочнее благодаря использованию суперкомпьютера фирмы Cray (The Atlanta Journal, 28 мая, 1995г). С помощью него были найдены не только слабые точки кузова, но и наиболее эффективный способ их удаления.

По данным Марка Миллера (Mark Miller, Ford Motor Company), для выполнения crash-тестов, при которых реальные автомобили разбиваются о бетонную стену с одновременным замером необходимых параметров, съемкой и последующей обработкой результатов, компании Форд понадобилось бы от 10 до 150 прототипов новых моделей при общих затратах от 4 до 60 миллионов долларов. Использование суперкомпьютеров позволило сократить число прототипов на одну треть.

Совсем недавний пример – это развитие одной из крупнейших мировых систем резервирования Amadeus, используемой тысячами агенств со 180000 терминалов в более чем ста странах. Установка двух серверов Hewlett-Packard T600 по 12 процессоров в каждом позволила довести степень оперативной доступности центральной системы до 99.85% при текущей загрузке около 60 миллионов запросов в сутки.

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

Источники увеличения производительности ЭВМ

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

Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира - EDSAC, появившемся в 1949 году в Кембридже и имевшем время такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*n арифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметических операций в секунду. Сравним с одним вычислительным узлом современного суперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды (1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметических операций в секунду.

Что же получается? За полвека производительность компьютеров выросла более, чем в семьсот миллионов раз. При этом выигрыш в быстродействии, связанный с уменьшением времени такта с 2 микросекунд до 1.8 наносекунд, составляет лишь около 1000 раз. Откуда же взялось остальное? Ответ очевиден – использование новых решений в архитектуре компьютеров. Основное место среди них занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.

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

Параллельная обработка. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени.

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

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находиться первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени – ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы, конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств из предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то, действуя по аналогии с предыдущим примером, надо набрать тысячу бригад, каждая из которых в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка...

Краткая история появления параллелизма в архитектуре ЭВМ. Сегодня параллелизмом в архитектуре компьютеров уже мало кого удивишь. Все современные микропроцессоры, будь то Pentium III или PA-8700, MIPS R14000, Е2К или Power3 используют тот или иной вид параллельной обработки. В ядре Pentium 4 на разных стадиях выполнения может одновременно находиться до 126 микроопераций. На презентациях новых чипов и в пресс-релизах корпораций это преподносится как последнее слово техники и передовой край науки, и это действительно так, если рассматривать реализацию этих принципов в миниатюрных рамках одного кристалла.

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

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

IBM-701(1953) и IBM-704(1955): разрядно параллельная память, разрядно параллельная арифметика. Все самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разрядно последовательную память, из которой слова считывались последовательно бит за битом. Первым коммерчески доступным компьютером, использующим разрядно параллельную память и разрядно параллельную арифметику, стал IBM 701, а наибольшую популярность получила модель IBM 704 (продано 150 экз.), в которой, помимо сказанного, была впервые применена память на ферритовых сердечниках и аппаратное АУ с плавающей точкой.

IBM-709(1958): независимые процессоры ввода/вывода. Процессоры первых компьютеров сами управляли вводом/выводом. Однако скорость работы самого быстрого внешнего устройства, а по тем временам это магнитная лента, была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода процессор фактически простаивал. В 1958г. к компьютеру IBM 704 присоединили 6 независимых процессоров ввода/вывода, которые после получения команд могли работать параллельно с основным процессором, а сам компьютер переименовали в IBM 709. Данная модель получилась удивительно удачной, так как вместе с модификациями было продано около 400 экземпляров, причем последний был выключен в 1975 году - 20 лет существования!

IBM-STRETCH (1961): опережающий просмотр вперед, расслоение памяти. В 1956 году IBM подписывает контракт с Лос-Аламосской научной лабораторией на разработку компьютера STRETCH, имеющего две принципиально важные особенности: опережающий просмотр вперед для выборки команд и расслоение памяти на два банка для согласования низкой скорости выборки из памяти и скорости выполнения операций.

ATLAS (1963): конвейер команд. Впервые конвейерный принцип выполнения команд был использован в машине ATLAS, разработанной в Манчестерском университете. Выполнение команд разбито на 4 стадии: выборка команды, вычисление адреса операнда, выборка операнда и выполнение операции. Конвейеризация позволила уменьшить время выполнения команд с 6 мкс до 1,6 мкс. Данный компьютер оказал огромное влияние, как на архитектуру ЭВМ, так и на программное обеспечение: в нем впервые использована мультипрограммная ОС, основанная на использовании виртуальной памяти и системы прерываний.

CDC-6600 (1964): независимые функциональные устройства. Фирма Control Data Corporation (CDC) при непосредственном участии одного из ее основателей, Сеймура Р.Крэя (Seymour R.Cray) выпускает компьютер CDC-6600 - первый компьютер, в котором использовалось несколько независимых функциональных устройств. Для сравнения с сегодняшним днем приведем некоторые параметры компьютера: время такта 100нс, производительность 2-3 млн. операций в секунду, оперативная память разбита на 32 банка по 4096 60-ти разрядных слов, цикл памяти 1мкс, 10 независимых функциональных устройств. Машина имела громадный успех на научном рынке, активно вытесняя машины фирмы IBM.

CDC 7600 (1969): конвейерные независимые функциональные устройства. CDC выпускает компьютер CDC-7600 с восемью независимыми конвейерными функциональными устройствами - сочетание параллельной и конвейерной обработки. Основные параметры: такт 27,5 нс, 10-15 млн. опер/сек., 8 конвейерных ФУ, 2-х уровневая память.

ILLIAC-IV (1974): матричные процессоры. Проект: 256 процессорных элементов (ПЭ) = 4 квадранта по 64ПЭ, возможность реконфигурации: 2 квадранта по 128ПЭ или 1 квадрант из 256ПЭ, такт 40нс, производительность 1Гфлоп. Работы начаты в 1967 году, к концу 1971 изготовлена система из 1 квадранта, в 1974г. она введена в эксплуатацию, доводка велась до 1975 года. Центральная часть: устройство управления (УУ) + матрица из 64 ПЭ. УУ это простая ЭВМ с небольшой производительностью, управляющая матрицей ПЭ; все ПЭ матрицы работали в синхронном режиме, выполняя в каждый момент времени одну и ту же команду, поступившую от УУ, но над своими данными. ПЭ имел собственное АЛУ с полным набором команд, ОП - 2Кслова по 64 разряда, цикл памяти 350нс, каждый ПЭ имел непосредственный доступ только к своей ОП. Сеть пересылки данных: двумерный тор со сдвигом на 1 по границе по горизонтали.

Несмотря на результат в сравнении с проектом: стоимость в 4 раза выше, сделан лишь 1 квадрант, такт 80нс, реальная произв-ть до 50Мфлоп – данный проект оказал огромное влияние на архитектуру последующих машин, построенных по схожему принципу, в частности: PEPE, BSP, ICL DAP.

CRAY-1 (1976): векторно-конвейерные процессоры. В 1972 году С.Крэй покидает CDC и основывает свою компанию Cray Research, которая в 1976г. выпускает первый векторно-конвейерный компьютер CRAY-1: время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая производительность 160 миллионов операций в секунду, оперативная память до 1Мслова (слово - 64 разряда), цикл памяти 50нс. Главным новшеством является введение векторных команд, работающих с целыми массивами независимых данных и позволяющих эффективно использовать конвейерные функциональные устройства.

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

Современная классификация супер-ЭВМ

По каким же направлениям идет развитие высокопроизводительной вычислительной техники в настоящее время? Основных направлений пять: PVP, SMP, NUMA, MPP, кластеры.

Основным параметром классификации параллельных компьютеров является наличие общей (SMP) или распределенной памяти (MPP). Нечто среднее между SMP и MPP представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом MPP. При поддержке команд обработки векторных данных говорят о векторно-конвейерных процессорах, которые, в свою очередь могут объединяться в PVP-системы с использованием общей или распределенной памяти. Все большую популярность приобретают идеи комбинирования различных архитектур в одной системе и построения неоднородных систем. При организациях распределенных вычислений в глобальных сетях (Интернет) говорят о мета-компьютерах, которые, строго говоря, не представляют собой параллельных архитектур.

Параллельные векторные системы (PVP). Конвейерные функциональные устройства и набор векторных команд – это две особенности таких машин. В отличие от традиционного подхода, векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры, т.е. команда вида A=B+C может означать сложение двух массивов, а не двух чисел. Характерным представителем данного направления является семейство векторно-конвейерных компьютеров CRAY, куда входят, например, CRAY EL, CRAY J90, CRAY T90.

Архитектура. Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP).

Примеры. NEC SX-4/SX-5, линия векторно-конвейерных компьютеров CRAY: от CRAY-1, CRAY J90/T90, CRAY SV1, серия Fujitsu VPP.

Модель программирования. Эффективное программирование подразумевает векторизацию циклов (для достижения разумной производительности одного процессора) и их распараллеливание (для одновременной загрузки нескольких процессоров одним приложением).

Симметричные мультипроцессорные системы (SMP). Параллельные компьютеры с общей памятью. Вся оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами. Это снимает проблемы предыдущего класса, но добавляет новые - число процессоров, имеющих доступ к общей памяти, по чисто техническим причинам нельзя сделать большим. В данное направление входят многие современные многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire.

Архитектура. Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора (HP 9000). Аппаратно поддерживается когерентность кэшей.

Примеры. HP 9000 V-class, N-class; SMP-cервера и рабочие станции на базе процессоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu и др.).

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

Операционная система. Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel-платформ поддерживается Windows NT). ОС автоматически (в процессе работы) распределяет процессы/нити по процессорам (scheduling), но иногда возможна и явная привязка.

Модель программирования. Программирование в модели общей памяти. (POSIX threads, OpenMP, другие средства поддержки многопоточности). Для SMP-систем существуют сравнительно эффективные средства автоматического распараллеливания.

Системы с неоднородным доступом к памяти (NUMA). Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом доступ к локальной памяти в несколько раз быстрее, чем к удаленной памяти. В случае если аппаратно поддерживается когерентность кэшей во всей системе (обычно это так), говорят об архитектуре cc-NUMA (cache-coherent NUMA). Модель программирования аналогична SMP.

Примеры. HP HP 9000 V-class в SCA-конфигурациях, SGI Origin2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000, SNI RM600.

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

Операционная система. Обычно вся система работает под управлением единой ОС, как в SMP. Но возможны также варианты динамического подразделения системы, когда отдельные разделы системы работают под управлением разных ОС (например, Windows NT и UNIX в NUMA-Q 2000).

Массивно-параллельные системы (MPP). Параллельные компьютеры с распределенной памятью. Идея построения компьютеров этого класса тривиальна: возьмем серийные микропроцессоры, снабдим каждый своей локальной памятью, соединим посредством некоторой коммуникационной среды – вот и все. Достоинств у такой архитектуры масса: если нужна высокая производительность, то можно добавить еще процессоров, если ограничены финансы или заранее известна требуемая вычислительная мощность, то легко подобрать оптимальную конфигурацию и т.п. Однако есть и решающий минус, сводящий многие плюсы на нет. Дело в том, что межпроцессорное взаимодействие в компьютерах этого класса идет намного медленнее, чем происходит локальная обработка данных самими процессорами. Именно поэтому написать эффективную программу для таких компьютеров очень сложно, а для некоторых алгоритмов иногда просто невозможно. К данному классу можно отнести компьютеры Intel Paragon, IBM SP1, Parsytec, в какой-то степени IBM SP2 и CRAY T3D/T3E, хотя в этих компьютерах влияние указанного минуса значительно ослаблено. К этому же классу можно отнести и сети компьютеров, которые все чаще рассматривают как дешевую альтернативу крайне дорогим суперкомпьютерам.

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

Основные причины появления массивно-параллельных компьютеров - это, во-первых, необходимость построения компьютеров с гигантской производительностью, и, во-вторых, необходимость производства компьютеров в большом диапазоне, как производительности, так и стоимости. Не все в состоянии купить однопроцессорный CRAY Y-MP C90, да и не всегда такие мощности нужны. Для массивно-параллельного компьютера, в котором число процессоров может сильно меняться, всегда можно подобрать конфигурацию с заранее заданной производительностью и/или стоимостью.

Архитектура. Система состоит из однородных вычислительных узлов, включающих: один или несколько центральных процессоров, локальную память (прямой доступ к памяти других узлов невозможен), коммуникационный процессор или сетевой адаптер, иногда - жесткие диски (как в SP) и/или другие устройства ввода/вывода. К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы.

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

Узлы связаны через некоторую коммуникационную среду, например: Intel Paragon – двумерная прямоугольная решетка, IBM SP2 – коммутатор, CRAY T3D – трехмерный тор, nCube-10 – гиперкуб, а также разного рода деревья.

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

Примеры. IBM RS/6000 SP2, Intel PARAGON/ASCI Red, CRAY T3E, Hitachi SR8000, транспьютерные системы Parsytec.

Масштабируемость. Общее число процессоров в реальных системах достигает нескольких тысяч (ASCI Red, Blue Mountain).

Операционная система. Существуют два основных варианта. Либо полноценная ОС работает только на управляющей машине (front-end), на каждом узле работает сильно урезанный вариант ОС, обеспечивающие только работу расположенной в нем ветви параллельного приложения. Пример: Cray T3E. Либо на каждом узле работает полноценная UNIX-подобная ОС (вариант, близкий к кластерному подходу). Пример: IBM RS/6000 SP + ОС AIX, устанавливаемая отдельно на каждом узле.

Модель программирования. Программирование в рамках модели передачи сообщений (коммуникационные библиотеки MPI, PVM, BSPlib).

Кластерные системы. Последнее направление, строго говоря, не является самостоятельным, а скорее представляет собой комбинации предыдущих трех. Из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти сформируем вычислительный узел. Если полученной вычислительной мощности не достаточно, то объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют кластерной, и по такому принципу построены CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, последние модели IBM SP2 и другие. Именно это направление является в настоящее время наиболее перспективным для конструирования компьютеров с рекордными показателями производительности.

Архитектура. Набор рабочих станций (или даже ПК) общего назначения, используется в качестве дешевого варианта массивно-параллельного компьютера. Для связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. При объединении в кластер компьютеров разной мощности или разной архитектуры, говорят о гетерогенных (неоднородных) кластерах. Узлы кластера могут одновременно использоваться в качестве пользовательских рабочих станций. В случае, когда это не нужно, узлы могут быть существенно облегчены и/или установлены в стойку.

Операционная система. Используются стандартные для рабочих станций ОС, чаще всего, свободно распространяемые - Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки.

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

Факторы, снижающие производительность параллельных компьютеров

К сожалению, чудеса в жизни редко случаются. Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования. Начнем с самых простых вещей. У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот этого, скорее всего, и не будет.

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

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

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

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

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

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

Закон Амдала. Предположим, что в вашей программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Так вот, для того, чтобы оценить, какое ускорение S может быть получено на компьютере из 'p' процессоров при данном значении f, можно воспользоваться законом Амдала:

Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0).

Ниже в таблице показано, на какое максимальное ускорение работы программы можно рассчитывать в зависимости от доли последовательных вычислений и числа доступных процессоров. Предполагается, что параллельная секция может быть выполнена без каких-либо дополнительных накладных расходов. Так как в программе всегда присутствует инициализация, ввод/вывод и некоторые сугубо последовательные действия, то недооценивать данный фактор никак нельзя – практически вся программа должна исполняться в параллельном режиме, что можно обеспечить только после анализа всей (!) программы.

Максимальное ускорение работы программы в зависимости от доли последовательных вычислений и числа используемых процессоров.
Число процессоров	Доля последовательных вычислений
2	1.33	1.60	1.82	.90	1.96
8	1.78	2.91	4.71	5.93	7.02
32	1.94	3.66	7.80	12.55	19.75
512	1.99	3.97	9.83	19.28	45.63
2048	2.00	3.99	9.96	19.82	48.83

Посмотрим на проблему с другой стороны. А какую же часть кода надо ускорить (а значит и предварительно исследовать), чтобы получить заданное ускорение? Ответ можно найти в следствии из закона Амдала: для того чтобы ускорить выполнение программы в q раз необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем на 99.99% кода, что почти всегда составляет значительную часть программы!

Отсюда первый вывод – прежде, чем основательно переделывать код для перехода на параллельный компьютер (а любой суперкомпьютер, в частности, является таковым) надо основательно подумать. Если, оценив заложенный в программе алгоритм, вы поняли, что доля последовательных операций велика, то на значительное ускорение рассчитывать явно не приходится и нужно думать о замене отдельных компонент алгоритма.

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

По своей природе он строго последователен, так как на i-й итерации цикла требуется результат с (i-1)-й и все итерации выполняются одна за другой. Имеем 100% последовательных операций, а значит и никакого эффекта от использования параллельных компьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве реальных программ (вопрос: а почему в большинстве, а не во всех?) нет существенной разницы, в каком порядке складывать числа, выберем иную схему сложения. Сначала найдем сумму пар соседних элементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схеме все пары можно складывать одновременно! На следующих шагах будем действовать абсолютно аналогично, получив вариант параллельного алгоритма.

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

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

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

Как вы думаете, верно ли утверждение: чем мощнее компьютер, тем быстрее на нем можно решить данную задачу? Нет, это не верно. Это можно пояснить простым бытовым примером. Если один землекоп выкопает яму в 1м³ за 1 час, то два таких же землекопа это сделают за 30 мин - в это можно поверить. А за сколько времени эту работу сделают 60 землекопов? За 1 минуту? Конечно же, нет! Начиная с некоторого момента, они будут просто мешать друг другу, не ускоряя, а замедляя процесс. Так же и в компьютерах: если задача слишком мала, то мы будем дольше заниматься распределением работы, синхронизацией процессов, сборкой результатов и т.п., чем непосредственно полезной работой.

Программирование с передачей сообщений

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

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

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

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

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

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

Прикладной буфер. Адресное пространство, где хранятся данные, которые должны быть посланы или получены.

Системный буфер. Системное адресное пространство для хранения сообщений. В зависимости от типа операции посылки (приема), данные в прикладном буфере могут быть скопированы в системный буфер (из системного буфера). Это позволяет коммуникационным связям быть асинхронными.

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

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

Message Passing Interface

MPI – это программный инструментарий для обеспечения связи между ветвями параллельного приложения. MPI расшифровывается как Message passing interface (Взаимодействие через передачу сообщений). Несколько путает дело тот факт, что этот термин уже применяется по отношению к аппаратной архитектуре ЭВМ. Программный инструментарий MPI реализован, в том числе и для ЭВМ с такой архитектурой. MPI предоставляет программисту единый механизм взаимодействия ветвей внутри параллельного приложения. MPI не зависит от машинной архитектуры: однопроцессорные или многопроцессорные системы с общей или раздельной памятью. MPI не зависит от взаимного расположения ветвей – на одном процессоре или на разных. MPI не зависит от API операционной системы (API = applications programmers interface = интерфейс разработчика приложений). Весь параллелизм явен: программист ответствен за правильное выделение параллелизма, и осуществление алгоритма, используя конструкции MPI.

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

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

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

Ноябрь 1992: Рабочая группа встречается в Миннеаполисе. Представлен проект MPI (MPI-1). В целом принята структура MPI. Для доработки организован MPI Форум – приблизительно 175 человек из 40 организаций, включая производителей параллельных компьютеров, авторов программного обеспечения, академических и прикладных ученых.

Ноябрь 1993: Конференция Supercomputing 93 – представлен проект стандарта MPI.

Май 1994: Выпущена заключительная версия спецификации проекта.

Причины для использования MPI: MPI – единственная библиотека передачи сообщений, которая может рассматриваться как стандарт. Она поддерживается фактически на всех высокопроизводительных компьютерах и локальных сетях. Мобильность – нет необходимости изменять исходный код при переносе приложения на другую платформу, которая поддерживает MPI. Производительность – реализация MPI от производителя должна быть способна использовать родные особенности аппаратных средств ЭВМ, чтобы оптимизировать производительность. Функциональные возможности – более чем 115 процедур. Доступность – доступны разнообразные коммерческие и открытые реализации.

Несколько вычислительных устройств (процессоров), по нынешней терминологии, могут быть объединены одним из трех способов:

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

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

Минимально в состав MPI входят: библиотека программирования (заголовочные и библиотечные файлы для языков Си, Си++ и Фортран) и загрузчик приложений. Дополнительно включаются: профилирующий вариант библиотеки (используется на стадии тестирования параллельного приложения для определения оптимальности распараллеливания); загрузчик с графическим и сетевым интерфейсом для X-Windows и проч. Минимальный набор функций прост в освоении и позволяет быстро написать надежно работающую программу. Использование же всей мощи MPI позволит получить быстро работающую программу – при сохранении надежности.

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

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

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

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

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

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

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

Сравнение с PVM. MPI – не первая попытка создания стандарта на обмен сообщениями между ветвями параллельного приложения. PVM – это изначально исследовательский проект. Его несомненными достоинствами являются простота использования (в теории) и почтенный возраст – он появился на свет в 1989 году, и, таким образом, на 6 лет старше MPI. Надо признать, по сравнению с PVM, MPI – это сложный пакет. То, что в PVM реализовано одним-единственным способом, в MPI может быть сделано несколькими, про которые говорится: способ А прост в использовании, но не очень эффективен; способ Б сложнее, но эффективнее; а способ В сложнее и эффективнее при определенных условиях. Изложение в доступных через Интернет учебниках рассчитано на профессиональных программистов, а не на прикладников, потому что упорядочено по областям применения (способы А, Б и В в одной главе), а не по уровням сложности (способ А в первой главе, способ Б в следующей, способ В и вовсе вынесен в приложения).

Более детальную информацию, как-то: спецификацию, учебники и различные реализации MPI можно найти на сервере NetLib. Первоисточником для данного пособия является книга MPI: The complete reference издательства MIT Press.

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

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

Особенность MPI: понятие области связи (communication domains). При запуске приложения все процессы помещаются в создаваемую для приложения общую область связи. При необходимости они могут создавать новые области связи на базе существующих. Все области связи имеют независимую друг от друга нумерацию процессов. Программе пользователя в распоряжение предоставляется коммуникатор – описатель области связи. Многие функции MPI имеют среди входных аргументов коммуникатор, который ограничивает сферу их действия той областью связи, к которой он прикреплен. Для одной области связи может существовать несколько коммуникаторов таким образом, что приложение будет работать с ней как с несколькими разными областями. В исходных текстах примеров для MPI часто используется идентификатор MPI_COMM_WORLD. Это название коммуникатора, создаваемого библиотекой автоматически. Он описывает стартовую область связи, объединяющую все процессы приложения.

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

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

Локальные – не инициируют пересылок данных между ветвями. Большинство информационных функций является локальными, т.к. копии системных данных уже хранятся в каждой ветви. Функция передачи MPI_Send и функция синхронизации MPI_Barrier не являются локальными, поскольку производят пересылку. Следует заметить, что, к примеру, функция приема MPI_Recv (парная для MPI_Send) является локальной: она всего лишь пассивно ждет поступления данных, ничего не пытаясь сообщить другим ветвям.

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

Принятая в MPI нотация записи. Регистр букв: важен в Си, не играет роли в Фортране.

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

Если идентификатор сконструирован из нескольких слов, слова в нем разделяются подчерками: MPI_Get_count, MPI_Comm_rank. Иногда, однако, разделитель не используется: MPI_Sendrecv, MPI_Alltoall.

Порядок слов в составном идентификаторе выбирается по принципу от общего к частному: сначала префикс MPI_, потом название категории ( Type, Comm, Group, Attr, Errhandler и т.д.), потом название операции ( MPI_Errhandler_create, MPI_Errhandler_set, ...). Наиболее часто употребляемые функции выпадают из этой схемы: они имеют анти-методические, но короткие и стереотипные названия, например MPI_Barrier, или MPI_Unpack.

Имена констант (и неизменяемых пользователем переменных) записываются полностью заглавными буквами: MPI_COMM_WORLD, MPI_FLOAT. В именах функций первая за префиксом буква - заглавная, остальные маленькие: MPI_Send, MPI_Comm_size.

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

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

Коммуникаторы и группы. MPI использует объекты называемые коммуникаторами и группами для определения коллектива процессов, которые могут иметь коммуникации друг с другом. Большинство процедур MPI требуют в качестве одного из аргументов определения коммуникатора.

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

Ранг. Внутри коммуникатора, каждый процесс имеет свой собственный уникальный, целочисленный идентификатор, назначенный системой при инициализации коллектива процессов. Процессы в коммуникаторе нумеруются последовательно, начиная с нуля. Идентификаторы используются в программе, чтобы определить источник и приемник сообщений. Часто используются в условных конструкциях, чтобы управлять выполнением программы (если ID=0 делаем это, а если ID=1 делаем то).

Обрамляющие функции. Начало и завершение.

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

MPI_Init: Инициализация библиотеки, создание первоначального коллектива MPI_COMM_WORLD. Одна из первых инструкций в функции main (главной функции приложения). Она получает адреса аргументов, стандартно получаемых самой main от операционной системы и хранящих параметры командной строки. В конец командной строки программы MPI-загрузчик добавляет ряд информационных параметров, которые требуются MPI_Init. Эта функция должна быть вызвана в любой программе MPI, перед любой другой функцией MPI и вызвана лишь однажды. Для C программ, MPI_Init может быть использована для передачи аргументов командной строки всем процессам, хотя это не требуется по стандарту и зависит от реализации MPI.

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

MPI_Abort: Вызов MPI_Abort из любой задачи принудительно завершает работу всех задач, подсоединенных к заданной области связи (коммуникатору). Если указан описатель MPI_COMM_WORLD, будет завершено все приложение (все его задачи) целиком, что, по-видимому, и является наиболее правильным решением. Рекомендуется в качестве коммуникатора всегда указывать MPI_COMM_WORLD, хотя в большинстве реализаций MPI аварийно заканчивают работу все процессы независимо от указанного коммуникатора. Следует помнить, что стандартные функции exit, abort, terminate, stop могут завершить работу лишь одного процесса. Выпадение из коллектива одного процесса может привести к зависанию остальных. Следует всегда использовать только MPI_Abort для аварийного завершения работы.

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

MPI_Comm_size: Определяет число процессов в заданном коммуникаторе (области связи). При использовании с коммуникатором MPI_COMM_WORLD возвращает число процессов, присоединенных к программе.

MPI_Comm_rank: Определяет порядковый номер процесса в коммуникаторе. Первоначально, каждый процесс имеет уникальный номер от 0..N-1, где N – число процессов в коммуникаторе MPI_COMM_WORLD. Если процесс становится связанным с другим коммуникатором, то в нем он будет иметь другой уникальный номер в пределах новой области связи.

#include <mpi.h>
#include <stdio.h>

int main(int argc, char **argv) {
    int numtasks, rank, rc;

    rc = MPI_Init(&argc,&argv);
    if(rc != 0) {
    printf("Error starting MPI program. Terminating.\n");

    MPI_Abort(MPI_COMM_WORLD, rc);
    }
    MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    printf("Number of tasks= %d My rank= %d\n", numtasks, rank);
    MPI_Finalize();
    return 0;
}

Простейшие процедуры передачи сообщений типа точка-точка.

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

Задача №1 принимает сообщение и определяет его длину:

int buf[10],len;
MPI_Status status;
MPI_Recv(buf, 10, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Get_count(&status, MPI_INT, &len);

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

Размер буфера. Задается не в байтах, а в количестве ячеек. Для MPI_Send указывает, сколько ячеек требуется передать (в примере передаются 5 чисел). В MPI_Recv означает максимальную емкость приемного буфера. Если фактическая длина пришедшего сообщения меньше – последние ячейки буфера останутся нетронутыми, если больше – произойдет ошибка времени выполнения.

Тип ячейки буфера. Из соображений переносимости, MPI оперирует массивами однотипных данных. Предопределены стандартные типы данных, соответствующие типам данных C++. Для описания базовых типов Си в MPI определены константы MPI_INT, MPI_CHAR, MPI_DOUBLE и так далее, имеющие тип MPI_Datatype. Их названия образуются префиксом MPI_ и именем соответствующего типа (int, char, double, ...), записанным заглавными буквами. Пользователь может регистрировать в MPI свои собственные типы данных (производные типы), например структуры, после чего MPI сможет обрабатывать их наравне с базовыми типами. Процесс регистрации описывается далее. Специальные MPI типы MPI_BYTE и MPI_PACKED не относятся к стандартным типам C.

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

Идентификатор сообщения. Произвольное неотрицательное целое число, назначенное программистом, чтобы уникально идентифицировать сообщение. MPI стандарт гарантирует, что целые числа 0-32767 можно использовать как признаки, но большинство реализаций позволяют больший диапазон значений. Оно служит той же цели, что и, например, расширение файла – задача-приемник: по идентификатору определяет смысл принятой информации; сообщения, пришедшие в неизвестном порядке, может извлекать из общего входного потока в нужном алгоритму порядке. Хорошим тоном является обозначение идентификаторов символьными именами посредством операторов #define или const int. Операции Send/Receive, должны совпадать по идентификаторам сообщения. Для приема можно использовать MPI_ANY_TAG, чтобы получить сообщение с любым идентификатором.

Описатель области связи (коммуникатор). Указывает контекст связи (множество процессов), относительно которых задаются номера источника и приемника сообщений. Он обязан быть одинаковым для MPI_Send и MPI_Recv. Если программист не создает явно новые коммуникаторы, обычно используется предопределенный коммуникатор MPI_COMM_WORLD.

Статус завершения приема. Содержит информацию о принятом сообщении: его идентификатор, номер задачи-передатчика, код завершения и количество фактически пришедших данных. В C этот аргумент – указатель на предопределенную структуру MPI_Status (с полями MPI_SOURCE и MPI_TAG).

С одной стороны, мы передаем в MPI_Recv номер задачи, от которой ждем сообщение, и его идентификатор; а с другой – получаем их от MPI в структуре status? Это сделано потому, что MPI_Recv может быть вызвана с аргументами-джокерами MPI_ANY_TAG и MPI_ANY_SOURCE (принимай что угодно/от кого угодно), и после такого приема данных программа узнает фактические номер/идентификатор, читая поля MPI_SOURCE и MPI_TAG из структуры status.

Поле MPI_ERROR, как правило, проверять необязательно – обработчик ошибок, устанавливаемый MPI по умолчанию, в случае сбоя завершит выполнение программы до возврата из MPI_Recv. Таким образом, после возврата из MPI_Recv поле status.MPI_ERROR может быть равно только MPI_SUCCESS.

Тип MPI_Status не содержит поля, в которое записывалась бы фактическая длина пришедшего сообщения. Длина принятого сообщения определяет потом с помощью функции MPI_Get_count:

MPI_Status status;
int count;
MPI_Recv(... ,  MPI_INT, ... , &status);
MPI_Get_count(&status, MPI_INT, &count);
/* ... теперь count содержит количество принятых ячеек */

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

Запрос на завершение отложенной блокировки. Используется для не блокируемых операций send/receive. Поскольку не блокируемая операция может вернуть управление прежде, чем будет завершена операция передачи данных, система возвращает уникальный номер запроса. Программист использует этот назначенный системой дескриптор позже (в процедурах типа WAIT) для завершения отложенного блокирования. В C этот аргумент – указатель на предопределенную структуру MPI_Request.

Наиболее используемые функции MPI для передачи сообщений с блокировкой:

int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm)

Типы данных MPI
тип MPI	тип данных
MPI_CHAR	signed char
MPI_SHORT	signed short int
MPI_INT	signed int
MPI_LONG	signed long int
MPI_UNSIGNED_CHAR	unsigned char
MPI_UNSIGNED_SHORT	unsigned short int
MPI_UNSIGNED	unsigned int
MPI_UNSIGNED_LONG	unsigned long int
MPI_FLOAT	float
MPI_DOUBLE	double
MPI_LONG_DOUBLE	long double
MPI_BYTE	8 binary digits
MPI_PACKED	data packed or unpacked with MPI_Pack()/ MPI_Unpack

Базисная операция посылки данных. Блокирующая посылка сообщения с идентификатором msgtag, состоящего из count элементов типа datatype, процессу с номером dest. Все элементы сообщения расположены подряд в буфере buf. Значение count может быть нулем. Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа. Разрешается передавать сообщение самому себе.

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

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

int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Status *status)

Прием сообщения с идентификатором msgtag от процесса source с блокировкой. Число элементов в принимаемом сообщении не должно превосходить значения count. Если число принятых элементов меньше значения count, то гарантируется, что в буфере buf изменятся только элементы, соответствующие элементам принятого сообщения.

Блокировка гарантирует, что после возврата из подпрограммы все элементы сообщения приняты и расположены в буфере buf.

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

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

MPI_Ssend. Синхронная блокируемая посылка. Аналогична MPI_Send, за исключением того, что процесс-отправитель гарантированно дождется, пока процесс-получатель примет сообщение, и только потом вернет управление.

MPI_Bsend. Буферизуемая посылка с блокировкой. Аналогична MPI_Send, за исключением того, что позволяет пользователю работать с собственной буферизацией. Используется при недостатке места в системном буфере. Возвращает управление после того, как сообщение будет скопировано из программного буфера в назначенный буфер. Должна использоваться вместе с MPI_BUFFER_ATTACH.

MPI_Buffer_attach и MPI_Buffer_detach. Используются для назначения (освобождения) буфера сообщений, используемого функцией MPI_Bsend. Аргумент «size» определяет число байт – размер буфера. Только один буфер может быть назначен для процесса.

MPI_Rsend. Небуферизуемая посылка с блокировкой. Аналогична MPI_Send, за исключением того, что ее рекомендуется использоваться, только если программист уверен, что соответствующий получатель уже готов к приему.

Некоторые конструкции с приемом-передачей применяются очень часто:

/* Обмен данными с соседями по группе
   (в группе четное количество ветвей!): */
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(
MPI_COMM_WORLD, &rank);
if(rank % 2 ) {
    /* Ветви с четными номерами передают следующим нечетным ветвям */
    MPI_Send(...,( rank+1) % size,...);
    /* а потом принимают от предыдущих */
    MPI_Recv(...,( rank+size-1) % size ,...);
} else {
    /* Нечетные ветви поступают наоборот:
       сначала принимают от предыдущих ветвей */
    MPI_Recv(..., ( rank-1) % size ,...);
    /* потом передают следующим. */
    MPI_Send(..., ( rank+1) % size ,...);
}

/* Посылка данных и получение подтверждения: */
MPI_Send(..., anyRank ,...);   /* Посылаем данные */
MPI_Recv(..., anyRank ,...);   /* Принимаем подтверждение */

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

int MPI_Sendrecv( void *sbuf, int scount, MPI_Datatype stype, int dest, int stag, void *rbuf, int rcount, MPI_Datatype rtype, int source, MPI_Datatype rtag, MPI_Comm comm, MPI_Status *status)

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

Сообщение, отправленное операцией MPI_Sendrecv, может быть принято обычным образом (например, MPI_Recv), и точно также операция MPI_Sendrecv может принять сообщение, отправленное обычной операцией MPI_Send. Буфера приема и посылки обязательно должны быть различными. Блокировка, пока send-буфер не освободится и recv-буфер не будет готов. Следует учесть, что и прием, и передача используют один и тот же коммуникатор, порядок приема и передачи данных MPI_Sendrecv выбирает автоматически; гарантируется, что автоматический выбор не приведет к клинчу.

int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype stype, int dest, int stag, int source, int rtag, MPI_Comm comm, MPI_Status *status)

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

Что такое клинч? Дальше следует краткая иллюстрация этой ошибки, очень распространенной там, где для пересылок используется разделяемая память.

Вариант 1 вызовет клинч, какой бы инструментарий не использовался. Функция приема не вернет управления до тех пор, пока не получит данные, поэтому функция передачи не может приступить к отправке данных; поэтому функция приема... и так далее.

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

Однако при использовании MPI зависания во втором варианте не произойдет! MPI_Send, если на приемной стороне нет готовности (не вызван MPI_Recv), не станет ее дожидаться, а положит данные во временный буфер и вернет управление программе немедленно. Когда MPI_Recv будет вызван, данные он получит не напрямую из пользовательского буфера, а из промежуточного системного. Буферизация – дело громоздкое – может быть, и не всегда сильно экономит время (особенно на SMP-машинах), зато повышает надежность: делает программу более устойчивой к ошибкам программиста.

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

Пример передач сообщений с блокировкой: Задача 0 шлет информацию задаче 1 и ожидает ответа.

#include <mpi.h>
#include <stdio.h>

int main(int argc, char **argv) {
    int numtasks, rank, dest, source, rc, tag=1;
    char inmsg, outmsg='x';
    MPI_Status Stat;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    if (rank == 0) {
      dest = source = 1;
      MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
      MPI_Recv(&inmsg, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
    } else if (rank == 1) {
      dest = source = 0;
      MPI_Recv(&inmsg, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
      MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
    }
    MPI_Finalize();
    return 0;
}

Не блокируемые процедуры передачи сообщений типа точка-точка.

Наиболее широко используемые функции MPI для неблокируемых передач сообщений:

int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request)

Передача сообщения, аналогичная MPI_Send, однако возврат из подпрограммы происходит сразу после инициализации процесса передачи без ожидания обработки всего сообщения, находящегося в буфере buf (возвращает управление немедленно, без ожидания отправки сообщения или его копирования системный буфер). Это означает, что нельзя повторно использовать данный буфер для других целей без получения дополнительной информации о завершении данной посылки. Дескриптор запроса request возвращается для последующей отложенной блокировки. Окончание процесса передачи (т.е. того момента, когда можно переиспользовать буфер buf без опасения испортить передаваемое сообщение) можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.

Сообщение, отправленное любой из процедур MPI_Send и MPI_Isend, может быть принято любой из процедур MPI_Recv и MPI_Irecv.

int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request)

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

int MPI_Issend (void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)

Неблокируемая синхронная передача. Аналогично MPI_Isend, за исключением того, что MPI_Wait или MPI_Test будут ожидать приема этого сообщения процессом-приемником.

int MPI_Ibsend (void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)

Неблокируемая буферизуемая передача. Аналогично MPI_Bsend, за исключением того, что MPI_Wait или MPI_Test будут ожидать приема этого сообщения процессом-приемником. Должна использоваться только с MPI_Buffer_attach.

int MPI_Irsend (void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)

Неблокируемая буферизуемая передача. Аналогично MPI_Rsend, за исключением того, что MPI_Wait или MPI_Test будут ожидать приема этого сообщения процессом-приемником. Должна использоваться, только если пользователь уверен, что соответствующий приемник уже готов.

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

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

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

int MPI_Waitany( int count, MPI_Request *requests, int *index, MPI_Status *status)

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

int MPI_Waitsome( int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses)

Выполнение процесса блокируется до тех пор, пока по крайней мере одна из операций обмена, ассоциированных с указанными идентификаторами, не будет завершена. Параметр outcount содержит число завершенных операций, а первые outcount элементов массива indexes содержат номера элементов массива requests с их идентификаторами. Первые outcount элементов массива statuses содержат параметры завершенных операций.

Функции типа TEST: проверяют статус передач с отложенной блокировкой. Параметр flag возвращает логическое значение ИСТИНА, если операция завершилась. Для нескольких неблокируемых передач, пользователь может проверять их: все, некоторые или первую завершенную.

Проверка завершенности асинхронных процедур MPI_Isend или MPI_Irecv, ассоциированных с идентификатором request. В параметре flag возвращает значение 1, если соответствующая операция завершена, и значение 0 в противном случае. Если завершена процедура приема, то атрибуты и длину полученного сообщения можно определить обычным образом с помощью параметра status.

int MPI_Testall( int count, MPI_Request *requests, int *flag, MPI_Status *statuses)

В параметре flag возвращает значение 1, если все операции, ассоциированные с указанными идентификаторами, завершены (с указанием параметров сообщений в массиве statuses). В противном случае возвращается 0, а элементы массива statuses неопределены.

int MPI_Testany(int count, MPI_Request *requests, int *index, int *flag, MPI_Status *status)

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

int MPI_Testsome( int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses)

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

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

int MPI_Send_init (void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request)

Формирование запроса на выполнение пересылки данных. Все параметры точно такие же, как и у подпрограммы MPI_Isend, однако в отличие от нее пересылка не начинается до вызова подпрограммы MPI_Startall.

int MPI_Recv_init (void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request)

Формирование запроса на выполнение приема данных. Все параметры точно такие же, как и у подпрограммы MPI_Irecv, однако в отличие от нее реальный прием не начинается до вызова подпрограммы MPI_Startall.

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

Пример передач с отложенной блокировкой: Обмен по кругу с ближайшими соседями.

    #include <mpi.h>
    #include <stdio.h>
    int main(int argc, char **argv) {
    int numtasks, rank, next, prev, buf[2], tag1=1, tag2=2;
    MPI_Request reqs[4];
    MPI_Status stats[4];
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    prev = rank-1;
    next = rank+1;
    if(rank == 0)  prev = numtasks - 1;
    if (rank == (numtasks - 1))  next = 0;
    MPI_Irecv(&buf[0], 1, MPI_INT, prev, tag1, MPI_COMM_WORLD, &reqs[0]);
    MPI_Irecv(&buf[1], 1, MPI_INT, next, tag2, MPI_COMM_WORLD, &reqs[1]);
    MPI_Isend(&rank, 1, MPI_INT, prev, tag2, MPI_COMM_WORLD, &reqs[2]);
    MPI_Isend(&rank, 1, MPI_INT, next, tag1, MPI_COMM_WORLD, &reqs[3]);
    MPI_Waitall(4, reqs, stats);
    MPI_Finalize();
}

Определение размера сообщения до его помещения в приемный буфер

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

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

За исключением адреса и размера пользовательского буфера, она имеет такие же параметры, как и MPI_Recv. Она возвращает заполненную структуру MPI_Status и после нее можно вызвать MPI_Get_count. Стандарт MPI гарантирует, что следующий за MPI_Probe вызов MPI_Recv с теми же параметрами (имеются в виду номер задачи-передатчика, идентификатор сообщения и коммуникатор) поместит в буфер пользователя именно то сообщение, которое было принято функцией MPI_Probe. MPI_Probe блокирует работу процесса до момента получения требуемого сообщения.

Аналогичная функция MPI_Iprobe позволяет определить, пришло ли сообщение, не блокируя процесс.

int MPI_Iprobe( int source, int msgtag, MPI_Comm comm, int *flag, MPI_Status *status)

Когда задача-приемник не знает заранее длины ожидаемого сообщения. Пользовательский буфер заводится в динамической памяти:

MPI_Probe(MPI_ANY_SOURCE, tagMessageInt, MPI_COMM_WORLD, &status);
/* MPI_Probe вернет управление, после того как примет  данные в системный буфер */
MPI_Get_count(&status, MPI_INT, &bufElems);
buf = malloc( sizeof(int) * bufElems );
MPI_Recv(buf, bufElems, MPI_INT, ...);
/* ... дальше параметры у MPI_Recv такие же, как в MPI_Probe,
   MPI_Recv останется просто скопировать данные
   из системного буфера в пользовательский */

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

Когда задача-приемник собирает сообщения от разных отправителей с содержимым разных типов. Без MPI_Probe порядок извлечения сообщений в буфер пользователя должен быть задан в момент компиляции:

MPI_Recv(floatBuf, floatBufSize, MPI_FLOAT, MPI_ANY_SOURCE, tagFloatData,...);
MPI_Recv(intBuf, intBufSize, MPI_INT, MPI_ANY_SOURCE, tagIntData,...);
MPI_Recv(charBuf, charBufSize, MPI_CHAR, MPI_ANY_SOURCE, tagCharData,...);

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

for (int i=0; i < 3; i++) {
    MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
    switch (status.MPI_TAG) {
        case tagFloatData:
            MPI_Recv(floatBuf, floatBufSize, MPI_FLOAT, ... );
            break;
        case tagIntData:
            MPI_Recv(intBuf, intBufSize, MPI_INT, ... );
            break;
        case tagCharData:
            MPI_Recv(charBuf, charBufSize, MPI_CHAR, ... );
            break;
    } /* конец switch */
} /* конец for */

Многоточия здесь означают, что последние 4 параметра у MPI_Recv такие же, как и у предшествующей им MPI_Probe.

Джокеры. В MPI используются два джокера: MPI_ANY_SOURCE для номера задачи-отправителя (принимай от кого угодно) и MPI_ANY_TAG для идентификатора получаемого сообщения (принимай что угодно). MPI резервирует для них какие-то отрицательные целые числа, в то время как реальные идентификаторы задач и сообщений лежат всегда в диапазоне от 0 до 32767. Пользоваться джокерами следует с осторожностью, потому что по ошибке таким вызовом MPI_Recv может быть захвачено сообщение, которое должно приниматься в другой части задачи-получателя.

Если логика программы достаточно сложна, использовать джокеры можно ТОЛЬКО в функциях MPI_Probe и MPI_Iprobe, чтобы перед фактическим приемом узнать тип и количество данных в поступившем сообщении (на худой конец, можно принимать, и не зная количества - был бы приемный буфер достаточно вместительным, но тип для MPI_Recv надо указывать явно - а он может быть разным в сообщениях с разными идентификаторами).

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

Процедуры для коллективных коммуникаций

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

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

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

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

Точки синхронизации, они же барьеры. Функция MPI_Barrier создает барьер синхронизации в группе. Каждая задача, находя вызов MPI_Barrier, блокируется, пока все остальные процессы в группе не дойдут до того же барьера.

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

int myid, numtasks;
MPI_Comm_rank(MPI_COMM_WORLD, &myid);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
if (numtasks < 4) {
    if(myid == 0)  printf("Слишком мало процессов в группе\n");
    MPI_Barrier(MPI_COMM_WORLD);
    MPI_Abort(MPI_COMM_WORLD,0);
}

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

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

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

Обозначения: «x» – нормальное выполнение, точка – ветвь простаивает и процессорное время отдано под другие цели, «b» – вызван MPI_Barrier, «|» – MPI_Barrier ждет своего вызова в остальных ветвях.

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

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

int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int source, MPI_Comm comm)

Рассылка сообщения от процесса source всем процессам, включая рассылающий процесс. При возврате из процедуры содержимое буфера buf процесса source будет скопировано в локальный буфер процесса. Значения параметров count, datatype и source должны быть одинаковыми у всех процессов.

int MPI_Gather (void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int dest, MPI_Comm comm)

Сборка данных со всех процессов в буфере rbuf процесса dest. Каждый процесс, включая dest, посылает содержимое своего буфера sbuf процессу dest. Собирающий процесс сохраняет данные в буфере rbuf, располагая их в порядке возрастания номеров процессов. Параметр rbuf имеет значение только на собирающем процессе и на остальных игнорируется, значения параметров count, datatype и dest должны быть одинаковыми у всех процессов.

Векторный вариант – MPI_Gatherv – позволяет задавать разное количество отправляемых данных в разных задачах-отправителях. Соответственно, на приемной стороне задается массив позиций в приемном буфере, по которым следует размещать поступающие данные, и максимальные длины порций данных от всех задач. Оба массива содержат позиции/длины не в байтах, а в количестве ячеек типа recvCount.

int MPI_Scatter (void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int root, MPI_Comm comm)

Разбрызгиватель: выполняет обратную MPI_Gather операцию – части передающего буфера из задачи root распределяются по приемным буферам всех задач.

И векторный вариант: MPI_Scatterv, рассылающий части неодинаковой длины в приемные буферы неодинаковой длины.

int MPI_Allgather (void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm)

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

int MPI_Alltoall (void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm)

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

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

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

Предопределенных описателей операций в MPI насчитывается 12. MPI_MAX и MPI_MIN ищут поэлементные максимум и минимум. MPI_SUM вычисляет сумму векторов. MPI_PROD вычисляет поэлементное произведение векторов. MPI_LAND, MPI_BAND, MPI_LOR, MPI_BOR, MPI_LXOR, MPI_BXOR – логические и двоичные операции «И», «ИЛИ», «исключающее ИЛИ». MPI_MAXLOC, MPI_MINLOC – поиск индексированного минимума/максимума - здесь не рассматриваются.

Естественный вопрос – с массивами каких типов умеют работать эти функции? Ответ приводится в виде таблицы. Количество типов для ячеек векторов, поддерживающих ту или иную операцию, строго ограничено ниже перечисленными. Никакие другие встроенные или пользовательские описатели типов использоваться не могут! Обратите также внимание, что все операции являются ассоциативными ((a+b)+c = a+(b+c)) и коммутативными (a+b = b+a). Помимо встроенных операций, пользователь может вводить свои собственные операции. Для этого служат функции MPI_Op_create и MPI_Op_free, а также тип MPI_User_function.

int MPI_Allreduce( void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

MPI Reduction Operation	C data types	Fortran data types
MPI_MAX	maximum	integer, float	integer, real, complex
MPI_MIN	minimum	integer, float	integer, real, complex
MPI_SUM	sum	integer, float	integer, real, complex
MPI_PROD	product	integer, float	integer, real, complex
MPI_LAND	logical AND	integer	logical
MPI_BAND	bit-wise AND	integer, MPI_BYTE	integer, MPI_BYTE
MPI_LOR	logical OR	integer	logical
MPI_BOR	bit-wise OR	integer, MPI_BYTE	integer, MPI_BYTE
MPI_LXOR	logical XOR	integer	logical
MPI_BXOR	bit-wise XOR	integer, MPI_BYTE	integer, MPI_BYTE
MPI_MAXLOC	max value and location	float, double and long double	real, complex,double precision
MPI_MINLOC	min value and location	float, double and long double	real, complex, double precision

Выполнение count глобальных операций op с возвратом count результатов во всех процессах в буфере rbuf. Операция выполняется независимо над соответствующими аргументами всех процессов. Значения параметров count и datatype у всех процессов должны быть одинаковыми.

int MPI_Reduce( void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

Функция аналогична предыдущей, но результат будет записан в буфер rbuf только у процесса root.

int MPI_Reduce_scatter( void *sbuf, void *rbuf, int *recvcount, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

Сначала делается векторная распределенная операция для всех процессов в группе. Затем, вектор результата делится на части и распределяется между процессами. Это эквивалентно отдельным операциям MPI_Reduce и MPI_Scatter. Каждая задача получает не весь массив-результат, а его часть. Длины этих частей находятся в массиве – третьем параметре функции. Размер исходных массивов во всех задачах одинаков и равен сумме длин результирующих массивов.

int MPI_Scan (void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

Аналогична функции MPI_Allreduce в том отношении, что каждая задача получает результирующий массив. Главное отличие: здесь содержимое массива-результата в задаче i является результатом выполнение операции над массивами из задач с номерами от 0 до i включительно.

Пример коллективных коммуникаций: Раздача строк матрицы.

#include <mpi.h>
#include <stdio.h>
#define SIZE 4
int main(int argc, char **argv) {
    int numtasks, rank, sendcount, recvcount, source;
    float sendbuf[SIZE][SIZE] = {
     {1.0,  2.0, 3.0, 4.0},
     {5.0,  6.0, 7.0, 8.0},
     {9.0, 10.0, 11.0, 12.0},
     {13.0, 14.0, 15.0, 16.0}  };
    float recvbuf[SIZE];
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    if (numtasks == SIZE) {
     source = 1;
     sendcount = recvcount = SIZE;
     MPI_Scatter(sendbuf,sendcount,MPI_FLOAT,recvbuf,recvcount,
                MPI_FLOAT, source, MPI_COMM_WORLD);
     printf("rank=%d  Results: %f %f %f %f\n", rank,recvbuf[0],
            recvbuf[1],recvbuf[2],recvbuf[3]);
     }else
     printf("Must specify %d processors. Terminating.\n", SIZE);
    MPI_Finalize();
}

Зачем MPI знать тип передаваемых данных?

Действительно, зачем? Стандартные функции пересылки данных, например, memcpy, прекрасно обходятся без подобной информации – им требуется знать только размер в байтах. Вместо одного такого аргумента функции MPI получают два: количество элементов некоторого типа и символический описатель указанного типа (MPI_INT, и т.д.). Причин тому несколько:

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

Приложение MPI может работать на гетерогенном вычислительном комплексе (коллективе ЭВМ с разной архитектурой). Одни и те же типы данных на разных машинах могут иметь разное представление, например: на плавающую арифметику существует 3 разных стандарта (IEEE, IBM, Cray); тип char в терминальных приложениях Windows представлен альтернативной кодировкой ГОСТ, а в Юниксе – кодировкой KOI-8r; ориентация байтов в многобайтовых числах на ЭВМ с процессорами Intel отличается от общепринятой (у Intel – младший байт занимает младший адрес, у всех остальных – наоборот). Если приложение работает в гетерогенной сети, через сеть задачи обмениваются данными в формате XDR (eXternal Data Representation), принятом в Internet. Перед отправкой и после приема данных задача конвертирует их в/из формата XDR. Естественно, при этом MPI должен знать не просто количество передаваемых байтов, но и тип содержимого.

Такие часто используемые в Си типы данных, как структуры, могут содержать в себе некоторое пустое пространство, чтобы все поля в переменной такого типа размещались по адресам, кратным некоторому четному числу (часто 2, 4 или 8) - это ускоряет обращение к ним. Причины тому чисто аппаратные. Выравнивание данных настраивается ключами компилятора. Разные задачи одного и того же приложения, выполняющиеся на одной и той же машине (даже на одном и том же процессоре), могут быть построены с разным выравниванием, и типы с одинаковым текстовым описанием будут иметь разное двоичное представление. MPI будет вынужден позаботиться о правильном преобразовании. Например, переменные такого типа могут занимать 9, 10, 12 или 16 байт:

typedef struct {
    char c;
    double  d;
} CharDouble;

Создание собственных типов описывается дальше по тексту.

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

Вариант 1 (настолько тупой и медленный, что никогда не применяется). Каждый элемент в разнотипном наборе данных посылается отдельно:

#define msgTag 10

struct {
    int i;
    float f[4];
    char  c[8];
} s;

MPI_Send(&s.i, 1, MPI_INT, targetRank, msgTag,  comm );
MPI_Send(s.f, 4, MPI_FLOAT, targetRank, msgTag+1, comm );
MPI_Send(s.c, 8, MPI_CHAR,  targetRank, msgTag+2, comm );
// ... и на приемной стороне столько же раз вызывается MPI_Recv.

Вариант 2 (классический). Функция приема/передачи вызывается один раз, но до/после нее многократно вызывается функция упаковки/распаковки:

// Передача:
int bufPos = 0;
char tempBuf [sizeof(s)];

MPI_Pack(&s.i, 1, MPI_INT,tempBuf,sizeof(tempBuf),&bufPos,comm);
MPI_Pack(s.f,4,MPI_FLOAT,tempBuf,sizeof(tempBuf),&bufPos,comm);
MPI_Pack(s.c,8,MPI_CHAR,tempBuf,sizeof(tempBuf),&bufPos,comm );
MPI_Send(tempBuf,bufPos,MPI_BYTE,targetRank,msgTag,comm);
// Прием:

int bufPos = 0;
char tempBuf[sizeof(s)];

MPI_Recv(tempBuf,sizeof(tempBuf),MPI_BYTE,sourceRank,msgTag,comm,&status);
MPI_Unpack(tempBuf,sizeof(tempBuf),&bufPos,&s.i,1,MPI_INT,comm);
MPI_Unpack(tempBuf,sizeof(tempBuf),&bufPos,s.f,4,MPI_FLOAT,comm);
MPI_Unpack(tempBuf,sizeof(tempBuf),&bufPos,s.c,8,MPI_CHAR,comm);

Вариант 2 обозван здесь классическим, потому что пришел в MPI из PVM, где предлагается в качестве единственного. Он прост в понимании, за что его все и любят. Замечания по применению:

MPI_BYTE – особый описатель типа, который не описывает тип данных для конкретного языка программирования (в Си он ближе всего к unsigned char). Использование MPI_BYTE означает, что содержимое соответствующего массива не должно подвергаться никаким преобразованиям – и на приемной, и на передающей стороне массив будет иметь одну и ту же длину и одинаковое двоичное представление.

Зачем функциям упаковки/распаковки требуется описатель области связи? Описатель, помимо прочего, несет в себе информацию о распределении подсоединенных к области связи задач по процессорам и компьютерам. Если процессоры одинаковые, или задачи выполняются на одном и том же процессоре, данные просто копируются, иначе происходит их преобразование в промежуточный формат XDR (eXternal Data Representation – разработан фирмой Sun Microsystems, используется в Интернете для взаимодействия разнотипных машин). Коммуникаторы у функций упаковки/распаковки и у соответствующей функции передачи/приема должны совпадать, иначе произойдет ошибка.

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

В примере некорректно выбран размер временного буфера: использовалось неверное предположение, что в XDR-формате данные займут места не больше, чем в формате используемого ветвью процессора; или что XDR-преобразование заведомо не будет применено. Правильным же решением будет для определения необходимого размера временного буфера на приемной стороне использовать связку MPI_Probe / MPI_Get_count / MPI_Recv, а на передающей - функцию MPI_Pack_size:

int bufSize = 0;
void *tempBuf;
MPI_Pack_size(1, MPI_INT,   MPI_COMM_WORLD, &bufSize);
MPI_Pack_size(4, MPI_FLOAT, MPI_COMM_WORLD, &bufSize);
MPI_Pack_size(8, MPI_CHAR,  MPI_COMM_WORLD, &bufSize);
tempBuf = malloc(bufSize);
/* ... теперь можем упаковывать, не опасаясь переполнения */

Однако и вариант 2 замедляет работу: по сравнению с единственным вызовом memcpy на SMP-машине или одном процессоре, нудная упаковка/распаковка – дело весьма небыстрое!

Вариант 3 (жульнический). Если есть уверенность, что одни и те же типы данных в обеих ветвях приложения имеют одинаковое двоичное представление, то:

// Передача:
MPI_Send (&s, sizeof(s), MPI_BYTE...);
// Прием:
MPI_Recv(&s, sizeof(s), MPI_BYTE...);

А все, чем чреват такой подход, подробно перечислялось ранее.

Создание и использование собственных типов данных.

MPI также обеспечивает программиста средствами для определения собственных структур данных, основанных на комбинировании примитивных типов данных MPI. Такие определенные пользователем структуры называются производными типами данных. Пользовательские описатели типов создаются на базе созданных ранее пользовательских описателей, и на базе встроенных описателей; встроенные описатели имеются для всех стандартных типов: MPI_INT, MPI_CHAR, MPI_LONG, MPI_FLOAT, MPI_DOUBLE и так далее; тип MPI_BYTE служит для передачи двоичных данных; после конструирования, но перед использованием описатель должен быть зарегистрирован функцией MPI_Type_commit; после использования описатель должен быть удален функцией MPI_Type_free.

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

MPI_Type_commit. Передает системе новый тип данных. Требуется для создания всех пользовательских типов.

MPI_Type_contiguous: самый простой конструктор типа, он создает описание массива.

Функция MPI_Type_count вернет количество ячеек в переменной составного типа: после MPI_Type_count(intArray16, &count) значение count станет равным 16. Как правило, нет прямой необходимости использовать эту функцию.

Пример: Создание типа данных, представляющего строку матрицы и рассылка разных строк всем процессам.

#include <mpi.h>
#include <stdio.h>
#define  SIZE 4
int main(int argc, char **argv) {
    int numtasks, rank, source=0, dest, tag=1, i;
    float a[SIZE][SIZE] =
     {1.0, 2.0, 3.0, 4.0,
      5.0, 6.0, 7.0, 8.0,
      9.0, 10.0, 11.0, 12.0,
      13.0, 14.0, 15.0, 16.0};
    float  b[SIZE];
    MPI_Status stat;
    MPI_Datatype  rowtype;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    MPI_Type_contiguous(SIZE, MPI_FLOAT, &rowtype);
    MPI_Type_commit(&rowtype);
    if(numtasks == SIZE) {
     if(rank == 0) {
        for (i=0; i < numtasks; i++)
          MPI_Send(&a[i][0], 1, rowtype, i, tag, MPI_COMM_WORLD);
     }
     MPI_Recv(b,SIZE, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &stat);
     printf("rank=%d  b= %3.1f %3.1f %3.1f %3.1f\n",
            rank,b[0],b[1],b[2],b[3]);
    }
    else
     printf("Must specify %d processors. Terminating.\n", SIZE);
    MPI_Finalize();
}

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

MPI_Type_vector (int count, /* количество элементов в новом типе */

int blocklength, /* количество ячеек базового типа в одном элементе */

int stride, /* расстояние между началами эл-тов, в числе ячеек */

MPI_Datatype oldtype, /* описатель базового типа, т.е. типа ячейки */

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

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

Пример: Создание типа данных для столбцов матрицы и распределение информации из разных столбцов всем процессам.

#include <mpi.h>
#include <stdio.h>
#define SIZE 4
int main(int argc, char **argv) {
    int numtasks, rank, source=0, dest, tag=1, i;
    float a[SIZE][SIZE] = 
     {1.0, 2.0, 3.0, 4.0,  
      5.0, 6.0, 7.0, 8.0, 
      9.0, 10.0, 11.0, 12.0,
     13.0, 14.0, 15.0, 16.0};
    float b[SIZE]; 
    MPI_Status stat;
    MPI_Datatype columntype;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    MPI_Type_vector(SIZE, 1, SIZE, MPI_FLOAT, &columntype);
    MPI_Type_commit(&columntype);
    if (numtasks == SIZE) {
     if (rank == 0) {
        for (i=0; i < numtasks; i++) 
          MPI_Send(&a[0][i], 1, columntype, i, tag, MPI_COMM_WORLD);
      }
     MPI_Recv(b, SIZE, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &stat);
     printf("rank=%d  b= %3.1f %3.1f %3.1f %3.1f\n",
           rank,b[0],b[1],b[2],b[3]);
     }
    else
     printf("Must specify %d processors. Terminating.\n", SIZE);
    MPI_Finalize();
}

MPI_Type_indexed: расширение векторного описателя; длины массивов и расстояния между ними теперь не фиксированы, а у каждого массива свои. Соответственно, аргументы №2 и №3 здесь – не переменные, а массивы: массив длин и массив позиций.

Пример: создание шаблона для выделения правой верхней части матрицы.

/* кол-во массивов в переменной нового типа */
#define SIZE  100
float a[SIZE][SIZE];
int len[SIZE];  /* длины этих массивов */
int pos[SIZE]; /*их позиции от начала, отсчитываемые в количестве ячеек */
MPI_Datatype upper;
...
for (i=0; i < SIZE; i++ ) {
    pos[i] = SIZE*i + i;
    len[i] = SIZE - i;
}
MPI_Type_indexed(SIZE, len,pos, MPI_FLOAT, &upper);
MPI_Type_commit(&upper);
/* Поступающий поток чисел типа 'float' будет размещен в верхней правой части матрицы 'a'  */
MPI_Recv(a, 1, upper, ....);

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

Пример: Создание типа данных для выделения переменной длины порций массива и передачи их всем процессам.

#include <mpi.h>
#include <stdio.h>
#define NELEMENTS 6
int main(int argc, char **argv) {
    int numtasks, rank, source=0, dest, tag=1, i;
    int blocklengths[2], displacements[2];
    float a[16] = {
      1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 
      9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0};
    float b[NELEMENTS]; 
    MPI_Status stat;
    MPI_Datatype indextype;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    blocklengths[0] = 4;
    blocklengths[1] = 2;
    displacements[0] = 5;
    displacements[1] = 12;
    MPI_Type_indexed(2, blocklengths, displacements, MPI_FLOAT, &indextype);
    MPI_Type_commit(&indextype);
    if(rank == 0) {
     for(i=0; i < numtasks; i++) 
        MPI_Send(a, 1, indextype, i, tag, MPI_COMM_WORLD);
     }
    MPI_Recv(b, NELEMENTS, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &stat);
    printf("rank=%d  b= %3.1f %3.1f %3.1f %3.1f %3.1f %3.1f\n",
        rank,b[0],b[1],b[2],b[3],b[4],b[5]);
    MPI_Finalize();
}

MPI_Type_struct: создает описатель структуры. Наверняка будет использоваться Вами чаще всего.

int *len, /* массив с длинами полей (на тот случай, если это массивы) */

MPI_Aint *pos, /* массив со смещениями полей от начала структуры, в байтах */

MPI_Datatype *types, /* массив с описателями типов полей */

Здесь используется тип MPI_Aint: это просто скалярный тип, переменная которого имеет одинаковый с указателем размер. Введен он исключительно для единообразия с Фортраном, в котором нет типа указатель. По этой же причине имеется и функция MPI_Address: в Си она не нужна (используются оператор вычисления адреса & и основанный на нем макрос offsetof()); а в Фортране оператора вычисления адреса нет, и используется MPI_Address.

#include <stddef.h>  /* подключаем макрос 'offsetof()' */

typedef struct {
    int    i;
    double d[3];
    long   l[8];
    char   c;
} AnyStruct;

AnyStruct st;
MPI_Datatype anyStructType;

int len[5] = { 1, 3, 8, 1, 1 };

MPI_Aint pos[5] = {
    offsetof(AnyStruct,i),
    offsetof(AnyStruct,d),
    offsetof(AnyStruct,l),
    offsetof(AnyStruct,c),
    sizeof(AnyStruct)
};

MPI_Datatype typ[5] = {
    MPI_INT,
    MPI_DOUBLE,
    MPI_LONG,
    MPI_CHAR,
    MPI_UB
};

MPI_Type_struct(5, len, pos, typ, &anyStructType );
MPI_Type_commit(&anyStructType);  /* подготовка закончена */
MPI_Send(st, 1, anyStructType, ...);

Обратите внимание: структура в примере содержит 4 поля, а массивы для ее описания состоят из 5 элементов. Сделано это потому, что MPI должен знать не только смещения полей, но и размер всей структуры. Для этого и служит псевдотип MPI_UB (upper bound).
Адрес начала структуры и адрес ее первого поля, как правило, совпадают, но если это не так: нулевым элементом массива typ должен быть MPI_LB.

Пример: Создание типа данных, представляющего частицу и пересылка массива частиц всем процессам.

#include <mpi.h>
#include <stdio.h>
#define NELEM 25

typedef struct {
   float x, y, z;
   float velocity;
   int   n;
   int   type;
} Particle;

int main(int argc, char **argv) {
    int numtasks, rank, source=0, dest, tag=1, i;
    Particle p[NELEM], particles[NELEM];
    MPI_Datatype particletype, oldtypes[2]; 
    int blockcounts[2];
    /* MPI_Aint type used to be consistent with syntax of */
    /* MPI_Type_extent routine */
    MPI_Aint offsets[2], extent;
    MPI_Status stat;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    /* Setup description of the 4 MPI_FLOAT fields x, y, z, velocity */
    offsets[0] = 0;
    oldtypes[0] = MPI_FLOAT;
    blockcounts[0] = 4;
    /* Setup description of the 2 MPI_INT fields n, type */
    /* Need to first figure offset by getting size of MPI_FLOAT */
    MPI_Type_extent(MPI_FLOAT, &extent);
    offsets[1] = 4 * extent;
    oldtypes[1] = MPI_INT;
    blockcounts[1] = 2;
    /* Now define structured type and commit it */
    MPI_Type_struct(2, blockcounts, offsets, oldtypes, &particletype);
    MPI_Type_commit(&particletype);
    /* Initialize the particle array and then send it to each task */
    if(rank == 0) {
        for (i = 0; i < NELEM; i++) {
           particles[i].x = i * 1.0;
           particles[i].y = i * -1.0;
           particles[i].z = i * 1.0; 
           particles[i].velocity = 0.25;
           particles[i].n = i;
           particles[i].type = i % 2; 
        }
        for (i = 0; i < numtasks; i++)
           MPI_Send(particles, NELEM, particletype, i, tag, MPI_COMM_WORLD);
    }
    MPI_Recv(p, NELEM, particletype, source, tag, MPI_COMM_WORLD, &stat);
    /* Print a sample of what was received */
    printf("rank=%d   %3.2f %3.2f %3.2f %3.2f %d %d\n", rank,p[3].x,
       p[3].y,p[3].z,p[3].velocity,p[3].n,p[3].type);
    MPI_Finalize();
    return 0;
}

MPI_Type_extent и MPI_Type_size: важные информационные функции. Их характеристики удобно представить в виде таблицы:

Вид данных	sizeof	MPI_Type_extent	MPI_type_size
стандартный тип	равносильны
массив	равносильны
структура	равносильны	sizeof(поле1)+sizeof(поле2)+...
Описатель типа MPI с перекрытиями и разрывами	не определена	адрес последней ячейки данных - адрес первой ячейки данных + sizeof(последней ячейки данных)	sizeof(первой ячейки данных) + sizeof(второй ячейки данных) + ...

Можно сказать, что MPI_Type_extent сообщает, сколько места переменная типа занимает при хранении в памяти, а MPI_Type_size – какой минимальный размер она будет иметь при передаче (сжатая за счет неиспользуемого пространства). В Фортране их придется использовать постоянно ввиду отсутствия sizeof.

Коммуникаторы, группы и области связи.

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

Область связи (communication domain) - это нечто абстрактное: в распоряжении программиста нет типа данных, описывающего непосредственно области связи, как нет и функций по управлению ими. Области связи автоматически создаются и уничтожаются вместе с коммуникаторами. Абонентами одной области связи являются все задачи либо одной, либо двух групп.

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

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

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

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

Копирование. Самый простой способ создания коммуникатора – скопировать один-в-один уже имеющийся:

MPI_Comm tempComm;
MPI_Comm_dup(MPI_COMM_WORLD, &tempComm);
/* ... передаем данные через tempComm ... */
MPI_Comm_free(&tempComm);

Новая группа при этом не создается – набор задач остается прежним. Новый коммуникатор наследует все свойства копируемого.

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

MPI_Comm_split(
    existingComm, /* существующий описатель, например MPI_COMM_WORLD */
    indexOfNewSubComm, /* номер подгруппы, куда надо поместить ветвь */
    rankInNewSubComm, /* желательный номер в новой подгруппе */
    &newSubComm); /* описатель области связи новой подгруппы */

Эта функция имеет одинаковый первый параметр во всех ветвях, но разные второй и третий – и в зависимости от них разные ветви определяются в разные подгруппы; возвращаемый в четвертом параметре описатель будет принимать в разных ветвях разные значения (всего столько разных значений, сколько создано подгрупп). Если indexOfNewSubComm равен MPI_UNDEFINED, то в newSubComm вернется MPI_COMM_NULL, т.е. ветвь не будет включена ни в одну из созданных групп.

Создание через группы. В предыдущих двух случаях коммуникатор создается от существующего коммуникатора напрямую, без явного создания группы: группа либо та же самая, либо создается автоматически. Самый же общий способ таков: Функцией MPI_Comm_group определяется группа, на которую указывает соответствующий коммуникатор. На базе существующих групп функциями семейства MPI_Group_xxx создаются новые группы с нужным набором ветвей, для итоговой группы функцией MPI_Comm_create создается коммуникатор (не забудьте, что она должна быть вызвана во ВСЕХ ветвях-абонентах коммуникатора, передаваемого первым параметром). Все описатели созданных групп очищаются вызовами функции MPI_Group_free.

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

Типичное использование: извлечь дескриптор глобальной группы из MPI_COMM_WORLD с помощью MPI_Comm_group. Сформировать новую группу как подмножество глобальной группы с помощью MPI_Group_incl. Создать новый коммуникатор для новой группы с помощью MPI_Comm_create. Определить новый идентификатор процесса в новом коммуникаторе с помощью MPI_Comm_rank. Произвести коммуникации, используя любые процедуры MPI для передачи сообщений. После окончания освобождаем новые коммуникатор и группу, используя MPI_Comm_free и MPI_Group_free.

MPI_Comm_group. Возвращает дескриптор группы, связанной с данным коммуникатором.

MPI_Group_rank. Возвращает ранг процесса в группе или MPI_UNDEFINED, если процесс не входит в эту группу.

MPI_Group_size. Возвращает размер группы – число процессов.

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

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

MPI_Group_intersection. Создает группу из пересечения двух групп.

MPI_Group_union. Создает группу из объединения двух групп.

MPI_Group_difference. Создает группу из разности двух групп.

MPI_Group_compare. Сравнивает две группы и возвращает целое число: MPI_IDENT – если порядок и состав членов в обеих группах одинаков, MPI_SIMILAR – если только состав одинаков, и MPI_UNEQUAL – в остальных случаях.

MPI_Group_free. Освобождает группу (системный объект).

MPI_Comm_create. Создает новый коммуникатор из старого коммуникатора и новой группы.

MPI_Comm_compare. Сравнивает два коммуникатора и возвращает целое число: MPI_IDENT – если контекст и группа одни и те же, MPI_CONGRUENT – если разный контекст, но одинаковая группа, MPI_SIMILAR – если разный контекст, но сходная группа, а иначе – MPI_UNEQUAL.

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

#include <mpi.h>
#include <stdio.h>
#define NPROCS 8
int main(int argc, char **argv) {
    int rank, new_rank, sendbuf, recvbuf, numtasks,
        ranks1[4]={0,1,2,3}, ranks2[4]={4,5,6,7};
    MPI_Group orig_group, new_group;
    MPI_Comm new_comm;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    if(numtasks != NPROCS) {
        printf("Must specify MP_PROCS= %d. Terminating.\n", NPROCS);
        MPI_Finalize();
        exit(0);
   }
   sendbuf = rank;
   /* Extract the original group handle */
   MPI_Comm_group(MPI_COMM_WORLD, &orig_group);
   /* Divide tasks into two distinct groups based upon rank */
   if(rank < NPROCS/2) {
     MPI_Group_incl(orig_group, NPROCS/2, ranks1, &new_group);
   } else {
     MPI_Group_incl(orig_group, NPROCS/2, ranks2, &new_group);
   }
   /* Create new communicator and then perform collective communications */
   MPI_Comm_create(MPI_COMM_WORLD, new_group, &new_comm);
   MPI_Allreduce(&sendbuf, &recvbuf, 1, MPI_INT, MPI_SUM, new_comm);
   MPI_Group_rank(new_group, &new_rank);
   printf("rank=%d newrank= %d recvbuf= %d\n",rank,new_rank,recvbuf);
   MPI_Finalize();
   return 0;
}

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

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

Атрибуты идентифицируются целыми числами, которые MPI назначает автоматически. Некоторые константы для описания системных атрибутов: MPI_TAG_UB, MPI_HOST, MPI_IO, MPI_WTIME_IS_GLOBAL. К этим атрибутам программист обращается редко, и менять их не может; а для таких часто используемых атрибутов, как обработчик ошибок или описание топологии, существуют персональные наборы функций, например, MPI_Errhandler_xxx.

Атрибуты – удобное место хранения совместно используемой информации; помещенная в атрибут одной из ветвей, такая информация становится доступной всем использующим коммуникатор ветвям без пересылки сообщений (вернее, на MPP-машине, к примеру, сообщения будут, но на системном уровне, т.е. скрытые от глаз программиста).

Пользовательские атрибуты создаются и уничтожаются функциями MPI_Keyval_create и MPI_Keyval_free; модифицируются функциями MPI_Attr_put, MPI_Attr_get и MPI_Attr_delete. При создании коммуникатора на базе существующего атрибуты из последнего тем или иным образом копируются или нет в зависимости от функции копирования типа MPI_Copy_function, адрес которой является параметром функции создания атрибута. То же и для удаления атрибутов при уничтожении коммуникатора: задается пользовательской функцией типа MPI_Delete_function, указываемой при создании атрибута.

Корректное удаление отслуживших описателей. Здесь имеются в виду ВСЕ типы системных данных, для которых предусмотрена функция MPI_Xxx_free (и константа MPI_XXX_NULL). В MPI-I их 7 штук: коммуникаторы; группы; типы данных; распределенные операции; квитанции (request's); атрибуты коммуникаторов; обработчики ошибок (errhandler's). Дальше все описывается на примере коммуникаторов и групп, но изложенная схема является общей для всех типов ресурсов.

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

Взаимосвязанными описателями являются описатели коммуникатора и группы, (коммуникатор ссылается на группу); или описатели типов, если один создан на базе другого (порожденный тип ссылается на исходный). Пример:

MPI_Comm subComm;
MPI_Group subGroup;
int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_split(MPI_COMM_WORLD, rank / 3, rank % 3, &subComm);

/* Теперь создан коммуникатор subComm, и автоматически создана группа, на которую распространяется его область действия. На коммуникатор заведена ссылка из программы - subComm. На группу заведена системная ссылка из коммуникатора. */

/* Теперь на группу имеется две ссылки - системная из коммуникатора, и пользовательская subGroup. */

/* Пользовательская ссылка на группу уничтожена, subGroup сброшен в MPI_GROUP_NULL. Собственно описание группы из системных данных не удалено, так как на него еще ссылается коммуникатор. */

/* Удалена пользовательская ссылка на коммуникатор, subComm сброшен в MPI_COMM_NULL. Так как других ссылок на коммуникатор нет, его описание удаляется из системных данных. Вместе с коммуникатором удалена системная ссылка на группу. Так как других ссылок на группу нет, ее описание удаляется из системных данных. */

Для MPI не играет роли, в каком порядке будут вызваны завершающие вызовы MPI_Xxx_free, это дело программы. И не пытайтесь уничтожать константные описатели вроде MPI_COMM_WORLD или MPI_CHAR: их создание и уничтожение - дело самого MPI.

Виртуальные пользовательские топологии

Внутри группы задачи пронумерованы линейно от 0 до (размер группы-1). Однако через коммуникатор можно дополнительно навязать для них еще одну систему нумерации. Таких дополнительных систем в MPI две: декартова n-мерная решетка (с цикличностью и без оной), а также биориентированный граф. Предоставляются функции для создания нумераций (MPI_Topo_test, MPI_Cart_xxx, MPI_Graph_xxx) и для преобразования номеров из одной системы в другую. Этот механизм не должен восприниматься как предоставляющий возможность подгонки связей между ветвями под аппаратную топологию для повышения быстродействия – он всего лишь автоматизирует перерасчет адресов, которым должны заниматься ветви, скажем, при вычислении матриц: через коммуникатор задается картезианская система координат, где координаты ветви совпадают с координатами вычисляемой ею подматрицы.

MPI_Cart_coords. Возвращает координаты процесса в декартовой топологии.

MPI_Cart_create. Создание нового коммуникатора с декартовой топологией.

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

MPI_Cart_map. Задать для процессов декартову топологию.

MPI_Cart_rank. Определить ID процесса в коммуникаторе по его декартовым координатам.

MPI_Cart_shift. Возвращает ID источника и приемника для циклического сдвига в декартовой топологии. Текущий процесс задает направление и длину сдвига.

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

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

MPI_Dims_create. Создает разделение процессов в декартовской сетке.

MPI_Graph_create. Создание нового коммуникатора с топологией графа.

MPI_Graph_get. Получить информацию о топологии графа для данного коммуникатора.

MPI_Graph_map. Задать для проыессов топологию графа.

MPI_Graph_neighbors. Получить соседей данного процесса в графовой топологии.

MPI_Graphdims_get. Получить информацию о топологии графа (число узлов и число ребер) для данного коммуникатора.

MPI_Topo_test. Определить тип топологии коммуникатора.

Пример: Работа с 4x4 декартовой топологией из 16 процессов.

    #include <mpi.h>
    #include <stdio.h>
    #define SIZE 16
    #define UP    0
    #define DOWN  1
    #define LEFT  2
    #define RIGHT 3
    int main(int argc, char **argv) {
    int  numtasks, rank, source, dest, outbuf, i, tag=1, 
    inbuf[4]={MPI_PROC_NULL,MPI_PROC_NULL,MPI_PROC_NULL,MPI_PROC_NULL,},
       nbrs[4], dims[2]={4,4}, periods[2]={0,0},
    reorder=0, coords[2];
    MPI_Request reqs[8];
    MPI_Status stats[8];
    MPI_Comm cartcomm;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
    if (numtasks == SIZE) {
      MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &cartcomm);
      MPI_Comm_rank(cartcomm, &rank);
      MPI_Cart_coords(cartcomm, rank, 2, coords);
      MPI_Cart_shift(cartcomm, 0, 1, &nbrs[UP], &nbrs[DOWN]);
      MPI_Cart_shift(cartcomm, 1, 1, &nbrs[LEFT], &nbrs[RIGHT]);
      outbuf = rank;
      for(i=0; i < 4; i++) {
         dest = nbrs[i];
         source = nbrs[i];
         MPI_Isend(&outbuf, 1, MPI_INT, dest, tag, MPI_COMM_WORLD, &reqs[i]);
         MPI_Irecv(&inbuf[i], 1, MPI_INT, source, tag, MPI_COMM_WORLD, &reqs[i+4]);
         }
      MPI_Waitall(8, reqs, stats);
      printf("rank=%d coords= %d %d  neighbors(u,d,l,r)= %d %d %d %d\n",
            rank,coords[0],coords[1],nbrs[UP],nbrs[DOWN],nbrs[LEFT], nbrs[RIGHT]);
      printf("rank=%d inbuf(u,d,l,r)= %d %d %d %d\n",
    rank,inbuf[UP],inbuf[DOWN],inbuf[LEFT],inbuf[RIGHT]);
      }
    else
      printf("Must specify %d processors. Terminating.\n", SIZE);
    MPI_Finalize();
}

Второстепенные детали

Обработчики ошибок. По умолчанию, если при выполнении функции MPI обнаружена ошибка, выполнение всех ветвей приложения завершается. Это сделано в расчете на неряшливого программиста, не привыкшего проверять коды завершения (malloc, open, write, и т. д.), и пытающегося распространить такой стиль на MPI. При аварийном завершении по такому сценарию на консоль выдается очень скудная информация: в лучшем случае, там будет название функции MPI и название ошибки. Обработчик ошибок является принадлежностью коммуникатора, для управления обработчиками служат функции семейства MPI_Errhandler_xxx.

Многопоточность. Сам MPI неявно использует многопоточность очень широко, и не мешает программисту делать то же самое. Однако: разные задачи имеют с точки зрения MPI ОБЯЗАТЕЛЬНО разные номера, а разные потоки (threads) внутри одной задачи для него ничем не отличаются. Программист сам идентификаторами сообщений и коммуникаторами должен устанавливать такую дисциплину для потоков, чтобы один поток не стал, допустим, вызывая MPI_Recv, джокером перехватывать сообщения, которые должен принимать и обрабатывать другой поток той же задачи. Другим источником ошибок может быть использование разными потоками коллективных функций над одним и тем же коммуникатором: используйте MPI_Comm_dup!

Работа с файлами. В MPI-2 средства перенаправления работы с файлами появились, в MPI-1 их нет. Все вызовы функций напрямую передаются операционной системе (Unix/Parix/NFS/...) на той машине, или на том процессорном узле MPP-компьютера, где находится вызывающая ветвь. Теоретически возможность подключения средств расширенного управления вводом/выводом в MPI-1 есть – каждый коммуникатор хранит атрибут с числовым кодом MPI_IO – это номер ветви, в которую перенаправляется ввод/вывод от всех остальных ветвей в коммуникаторе; сам MPI ничего с ним не делает и никак не использует.

Работа с консолью также отдается на откуп системе; это может приводить к перемешиванию вывода нескольких задач, поэтому рекомендуется весь вывод на экран производить из какой-то одной задачи (обычно нулевой).

MPI 2.0. В марте 1995 MPI Форум начал обсуждение расширений к стандарту MPI. Эти расширения стали теперь частью стандарта MPI-2. Ключевые особенности новых функциональных возможностей:

1) Динамические процессы: расширение, удаляющее статическую модель процесса MPI. Обеспечивает процедуры для создания новых процессов.

2) Односторонние коммуникации: процедуры для однонаправленных коммуникаций. Включают в себя операции с общей памятью (put/get), и удаленные операции.

3) Расширенные коллективные действия: не-блокируемые коллективные операции и приложение коллективных операций к интракоммуникаторам

4) Внешние интерфейсы: определяет стандартные процедуры для профилирования и отладки MPI программ.

Посылка с блокировкой	MPI_Send(buffer, count, type, dest, tag, comm)
Посылка без блокировки	MPI_Isend(buffer, count, type, dest, tag, comm, request)
Прием с блокировкой	MPI_Recv(buffer, count, type, source, tag, comm, status)
Прием без блокировки	MPI_Irecv(buffer, count, type, source, tag, comm, request)

0 (0,0)	1 (0,1)	2 (0,2)	3 (0,3)
4 (1,0)	5 (1,1)	6 (1,2)	7 (1,3)
8 (2,0)	9 (2,1)	10 (2,2)	11 (2,3)
12 (3,0)	13 (3,1)	14 (3,2)	15 (3,3)