Параллельная Обработка Данных, 10 лекция (от 06 ноября)

Материал из eSyr's wiki.

Закончили архитектуру параллельных вычислительных систем. Для классов были выписаны сложности.

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

[править] Технологии параллельного программирования

Задача — Метод — Алгоритм — Технология программирования — Программа — Компилятор — Компьютер

ТП — центральная часть. Речь пойдет о параллельных ТП.

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

Эффективность. Допускает ли она создание эффективных программ?
Переносимость. Хочется, чтобы программа не была привязана к конкретному компьютеру
Продуктивность. Работы программиста.

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

Использование традиционных языков программирования. Паскаль, Фортран. Предполагается, что компьютеры с параллельной архитектурой. Кто-то должен выявить параллельную структуру. Это нагрузка ложиться на компилятор. Надежда на умный компилятор, как показывает история — пустая. В любом случае требуется вмешательство. Так что, как бы ни был удобен этот путь (столько всего написано), он неэффективен.
Специальные комментарии. Не влияют на суть программы, там указываются дополнительные сведения, упрощающие жизнь компилятору. Чуть-чуть сдвигаемся в сторону эффективности, остаемся в рамках прежней программной инфраструктуры (такую программу можно скормить и не поддерживающему специальные комментарии компилятору). Это часто использовали на векторных компьютерах. В них самым главным было распознать внутренние циклы без зависимостей. Именно эта дополнительная информация и была наиболее часто используемым видом комментариев.
Введение дополнительных конструкций в традиционные языки. Была иллюзия, что добавим несколько новых конструкций, человеку нужно будет немножко поменять, и всё станет параллельно. Пример — HPF. Где-то через 7-8 лет осознали, что страдает эффективность. MPC — позволяет программировать для неоднородной сети компьютеров. Большие проблемы с переносимостью — без спецефичных компиляторов для платформы не будет параллельных программ.
Новые языки. Occam, Sisal. Опять проблемы с переносимостью. Появление любых новых стандартов, вовлечение в свою веру, привлечение людей — это большие сложности. В ипме был создан язык НОРМА — для обработки сеточных функций. Хорошо с эффективностью и продуктивностью, плохо с переносимостью. Речи о том, чтобы использовать везде, к сожалению не идет.

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

Библиотеки передачи сообщений. PVM, MPI, Shmem. За основу берутся традиционные программы. На сегодняшний день 95 % процентов программ — это наполовину с, наполовину фортран.
параллельные предметные библиотеки. Хорошие пакеты по линейке, преобразование Фурье, обработки изображений. Обвязка на обычном языке, а весь параллелизм в спец библиотеке, реализованной специалистами, грамотно распараллеленными. Примеры — Scalapack — основные функции ЛинАла для компов с распределённой памятью. FFTW — преобразования Фурье, часто используется, и многие другие. Подход удачный, часто применяется.
Специализированные комплексы программ. Средство самого высокого уровня, человек формулирует задачу в терминах предметной области, все этапы за программиста сделают. Maxima, ANSYS GAMESS, Flow Vision. Это самый идеальный вариант, если можно этим подходом решить задачу — то так и надо делать.

Базовый вопрос — дали систему из 1000 процов. А как себе представить себе функционирование программы, над которой одновременно работают 1000 процессоров? Вопрос до модели о конца не решен, пока есть два подхода

SPMD(Single program Multiple Data). Берется один код программы и все процессоры работают согласно одной и той же программе, но каждый процесс работает над своими данными. Как этого добиться? В любом случае в ТП предусматривается средство самоопределение процесса. пусть это функция MyID. Она возвращает уникальный номер, приписанный данному процессору. Как разделить работу? Очень просто — ид == работе с процессором номер ид.
Мастер/Рабочие — разбиение всего множества процессов параллельной программы на мастера (распределяющего ресурсы) и подчиненных. Подчиненные, как правило, работают по одному тексту прораммы, а мастер - по другому. Master/Slaves — запретили по соображением политкорректности.

Перейдем к детальному рассмотрению MPI.

[править] MPI

Начало 90 годов. Аббревиатура от Message Passing Interace. Ориентирована на компы с распр. памятью, в которых процессы общаются с помощью передачи сообщений. Полный вариант стандарта — более 100 функций. Разберем основные идеи.

Стандарт 1.1 До сих пор используется, хотя появился уже 2.0. Пользователи не уверены в том что переход на 2.0 эффективен, и многие юзают 1.1. МПИ распр в виде библиотек для С и фортрана. Все детали текущей реализации доступны на mpiforum.org. На всех современных платформах есть мпи. Изначально он был ориентирован на Линукс, но уже давно есть поддержка для виндовс, в вин кластер сервер — он выдвинут на первый план. Конструкции мпи начинаются с MPI_ .

include<mpi.h>

Что из себя представляет паралл. MPI программа? Это набор независимых процессов (процесс в терминах юникса, у каждого процесса свое адресное пространство, общей памяти у процессов нет). Предполагается, что породили м штук процессов одновремено, потом завершаются. Нельзя динамически породить паралл. процесс. В мпи2 от этого отошли. В очень большом числе случаев это вполне достаточно, как показывает опыт. Введено понятие группы процессов. Для группы выделяется специальное пространство для общения, которое называется коммуникатор. Есть надежда, что общение в нескольких коммуникаторах эффективней, чем в общей куче. Имеется нечто всеобъемлющее — коммуникатор, куда погружены все процессы. Он называется MPI_COMM_WORLD — определен всегда. Каждый паралл. процесс имеет уникальный номер. В каждом коммуникаторе процесс может иметь свой номер. В способе формирования коммуникаторов и групп — полная свобода, они могут полностью вкладываться, частично пересекаться, вовсе не пересекаться. То, что касается сообщений. Набор однотипных данных, которые передаются от одного процесса к другому. Это содержательная сторона сообщения. Важно, что все данные имеют один и тот же тип, для разнородной инфы требуется спец ритуальный танец. Каждое сообщение имеет тэг (некая доп информация, целое число). Введено понятие производных типов. Пользователь может создавать свои типы и их передавать. Например туда пользователь может внести неоднородность. Не во всех задачах процессы общаются аморфной кучей. Иногда процессы например образовывают кольцо, у каждого ровно два соседа. Есть понятие виртуальная топология, определив которое, можно навести порядок в общении процессов друг с другом. Часто процессы располагают в узлах прямоугольной решетки с/без зацикленности по тору. Несколько слов о самой технологии. Рассматривать будем на примере с. Основа с эта функция.

Любая мпи функция возвращает код. Если вернулось MPI_SUCCESS — всё закончилось нормально. Если же вернулось не это значение — код ошибки можно посмотреть в стандарте.

Общие функции.
- MPI_Init(int * argc, char *** argv); сколько процессов породилось — указано в аргв. Все остальные действия могут выполняться только поосле того как выполнилась функция мпи инит. Но и выполнить ее можно только один раз.
- MPI_Finalize(void) — закончить все мпи процессы.
- MPI_Initialized(int *flag) — запускал ли кто-нибудь уже мпи_инит или нет. Содержательный результат возвращется через флаг
- MPI_Comm_size(MPI_COMM comm, int *size) — количество параллельных процессоров в данном коммуникаторе.
- MPI_Comm_run(MPI_COMM comm, int *my_id) — коммуникатор и переменная куда будет зписан номер процесса.

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

#include <mpi.h>
main(int argc, char * argv[])
{
	int size;//щбщее кол-во процессов
	int my_id;//номер текущего
	MPI_Init(&argc, &argv);
	// порождение произошло, теперь смотрим сколько вокруг и свой номер
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Comm_run(MPI_COMM_WORLD, &my_id);
	printf("Total: %d \n proc %d", size, my_id);
	MPI_Finalize();
}

Сколько процессов порождается — указывается через argv. Напечатано будет столько раз, сколько процессов породилось. Порядок, в котором появляются выдачи, заранее не определен, он может быть любым. Гарантируется лишь что строка — это неделимая сущность и она выдается целиком .

Взаимодействие процессов
- Коллективные операции(все процессы вовлечены)
- Точка-точка(взаимодействует пара процессов между собой)
  - Синхронные(с блокировкой)
    - MPI_Send(void * buf, int count, MPI_Datatype, int dest, int tag, MPI_comm comm) — буфер сообщения который надо передать, кол-во элементов, тип элементов, номер процесса получателя, тег, в рамках какого коммуникатора.
    Причем тут синхронность? Она тут трактуется не совсем стандартно. Посылающий процесс блокируется до тех пор, пока у него есть опасение испортить отправляемые параметры. Гарантируется, что что бы в отправляющем процессе не стояло после мпи_сенд, оно будет отправлено ровно в том виде в каком было на момент вызова мпи_сенд. Доставка не гарантируется.
    - MPI_Recv(void * buf, int count, MPI_Datatype, int dest, int tag, MPI_comm comm, MPI_Status * status) — статус описывает статус принимаемого сообщения. Возврат произойдет только когда в буфер запишутся все count элементов принимаемого сообщения.
    Вся система построена на том, что есть два процесса — один посылает, а другой принимает.
    Несколько общих замечаний.
    Предположим, есть процесс А и процесс Б. В некоторый момент процесс А посылает Б два сообщения. Процесс Б их может принять. И оба сообщения идут с одним и тем же тэгом. Есть ли гарантия того что сообщения придут в определенном порядке? Да. Если от одного и того же процесса ушли два сообщения, то первым приде то, которое первым было отправлено. Но вот если А и С отправляют что-то Б, то чьё сообщение придет первым — неопределено
    Есть константа MPI_ANYSOURCE — если ее поставить в ресв то сообщения будут ждаться от любого процесса. Аналогично MPI_ANYTAG.
    Справедливости в обслуживании процессов нет. Если Б закидывает А сообщениями в цикле, то единичное сообщение из С в А может и не пробиться.
    Принятая семантика синхронных операций может приводить к тупиковым ситуациям.
    Есть два процесса, им надо обменяться сообщениями.
    Оба пишут
    MPI_Send
    MPI_Recv
    А сделал сенд Б, аналогично Б сделал сенд А. А дальше у них стоит прием. Оба процесса могут стоять бесконечно долго ожидая завершения мпи_сенд, из за особенности семантики мпи_сенд. Конкретная реализация может ожидать того, что принимающая сторона заберет сообщение. И все друг друга ждут. Эта ситуация описана во всех мануалах, она просто обходится при помощи операций асинхронного взаимодействия. Но к этому надо быть готовыми. Она может проявляться по-разному — аналогичный эффект возникает если надо организовать обмен сообщений между соседями в кольце.
  - Асинхронные(без блокировки)