Редактирование: Параллельная Обработка Данных, 10 лекция (от 06 ноября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 18: | Строка 18: | ||
# Продуктивность. Работы программиста. | # Продуктивность. Работы программиста. | ||
- | Любая технология — это компромисс между этими критериями. С точки зрения этих критериев мы и будем оценивать технологии. Когда говорим про | + | Любая технология — это компромисс между этими критериями. С точки зрения этих критериев мы и будем оценивать технологии. Когда говорим про ТПП, имеется ввиду целый набор подходов, которыми можно пользоваться: |
- | * Использование традиционных языков программирования. Паскаль, Фортран. Предполагается, что компьютеры с параллельной архитектурой. Кто-то должен | + | * Использование традиционных языков программирования. Паскаль, Фортран. Предполагается, что компьютеры с параллельной архитектурой. Кто-то должен определить параллельную струкутуру. Это нагрузка ложиться на компилятор. Надежда на умный компилятор, как показывает история — пустая. В любом случае требуется вмешательство. Так что, как бы ни был удобен этот путь (столько всего написано), он неэффективен. |
- | * Специальные комментарии. Не влияют на суть программы, там указываются дополнительные сведения, упрощающие жизнь компилятору. Чуть-чуть сдвигаемся в сторону эффективности, остаемся в рамках прежней программной инфраструктуры (такую программу можно скормить и не поддерживающему | + | * Специальные комментарии. Не влияют на суть программы, там указываются дополнительные сведения, упрощающие жизнь компилятору. Чуть-чуть сдвигаемся в сторону эффективности, остаемся в рамках прежней программной инфраструктуры (такую программу можно скормить и не поддерживающему специальние комментарии компилятору). Это часто использовали на векторных компютерах. В них самое главное было — распознать внутренние циклы без зависимостей. Именно эта дополнительная информация и была наиболее часто используемым видом комментариев. |
- | * Введение дополнительных конструкций в | + | * Введение дополнительных конструкций в традициионые языки. Была иллюзия, что добавим несколько новых конструкций, человку нужно будет немножко поменять и все станет параллельно. Пример HPF -- через 7-8 лет осознали, что страдает эффективность. MPC - поззволяет прораммировать для неоднородной сети компьютеров.Большие проблемы с переносимостью -- без спецефичных компиляторов для платформы не будет параллельных программ. |
- | * Новые языки. Occam, Sisal. Опять проблемы с переносимостью. Появление любых новых стандартов, вовлечение в свою веру, привлечение людей | + | *Новые языки. Occam, Sisal. Опять проблемы с переносимостью. Появление любых новых стандартов, вовлечение в свою веру, привлечение людей -- это большие сложности В ипмебыл создан язык НОРМА - для обработки сеточных функций. Хорошо с эффективностью и продуктивностью, плохо с переносимостью, Речи о том чтобы использовать везде к сожалению не идет. |
- | Сейчас | + | Сейчас наиболле распространненая арх — компы с распределённой памятью. Общение — передачей сообщений. Появилось много библиотек передачи сообщений. |
- | * Библиотеки передачи сообщений. PVM, MPI, Shmem. За основу | + | *Библиотеки передачи сообщений. PVM, MPI, Shmem. За основу беруться традиционные программы. На сегодняшнитй день 95% процентов прорамм -- это наполовину с, наполовину фортран. |
- | * параллельные | + | *параллельные предмнтные библиотеки. Хорошие пакеты по линейке, преобр фурье, обработки изображений. Обвязка на обычном языке, а весь паралеллизм в спец библиотеке, реализованной специалистами, грамотно распралеллеными. ПРимеры -- Scalapack - основные функции линала для компов с распр памятью.FFTW - преобразования фурье, часто используется, и многие другие. Подход удачный, часто используется. |
- | * Специализированные комплексы программ. Средство самого | + | *Специализированные комплексы программ. Средство самого выского уровня, чел формулирует задачу в терминах предметной области, все этапы за программиста сделают. Maxima, ANSYS GAMESS, Flow Vision. Это самый идеальный вариант, если можно этим подходом решить задачу -- то так и надо делать. |
- | Базовый вопрос | + | Базовый вопрос - дали систему из 1000 процов. А как себе представить себе функционирование программы, анд которой одновременно работают 1000 процессоров. Вопрос о модели о конца не решен, пока есть два подхода |
- | * SPMD(Single program Multiple Data). Берется один код программы и все процессоры работают согласно одной и той же программе, но каждый процесс работает над своими данными. Как этого добиться? В любом случае в | + | *SPMD(Single program Multiple Data). Берется один код программы и все процессоры работают согласно одной и той же программе, но каждый процесс работает над своими данными. Как этого добиться? В любом случае в тп предусматривается средство самоопределение роцесса. пусть это функция MyID. Оно взвращает униек номер приписанный данному процессору. Как разделить работу? Очен просто --- ид == работе с роцессором номер ид. |
- | * Мастер/ | + | *Мастер/Рбочие -- разбиение всего множествоа процессов параллеьной программы на мастера(распределяюещего ресурсы) и подчиненных. Подчиенные как правило работают по одномк =у тексту прораммы, мастр по собственной. Master/Slaves -- запретили по соображением политкорректности. |
Перейдем к детальному рассмотрению MPI. | Перейдем к детальному рассмотрению MPI. | ||
- | + | ==MPI== | |
- | == MPI == | + | Начало 90 годов. Аббревиатура от Message Passing Interace. Ориентирована на компы с распр памятью, в которых роцессы общаются с помощью передачи сообщений. Полный вариант стандарта -- более 100 функций. Разберем основные идеи. |
- | Начало 90 годов. Аббревиатура от Message Passing Interace. Ориентирована на компы с распр | + | |
- | + | ||
Стандарт 1.1 | Стандарт 1.1 | ||
- | До сих пор используется, хотя появился уже 2.0. Пользователи не уверены в том что переход | + | До сих пор используется, хотя появился уже 2.0. Пользователи не уверены в том что переход н 2.0 эффективен и многие юзают 1.1. |
- | МПИ распр в виде библиотек для | + | МПИ распр в виде библиотек для с и фортрана. Все детали текущей реализации доступны на mpiforum.org,.На всех современных платформах есть мпи. Изначально он был ориентирован на инукс, но уже давно есть погддержка для виндовс, в вин клстер сервер - он выдвинут на первый план. |
Конструкции мпи начинаются с MPI_ . | Конструкции мпи начинаются с MPI_ . | ||
- | # include<mpi.h> | + | #include<mpi.h> |
- | Что из себя представляет | + | Что из себя представляет парл мпи программа -- набор независимых процессов(процесс в терминах юникса, у каждого процесса свое адресное пространство, общей памяти у процессов нет). Предпорлагается что породили м штук процессов одновремено, потом завершаются. Нельзя динамически породить парал процесс.В мпи2 от этого отошли. В очень большом числе случаев это вполне достаточно, как показывает опыт. |
- | Введено понятие группы процессов. Для группы выделяется специальное пространство для | + | Введено понятие группы процессов. Для группы выделяется специальное пространство для общение, которое называется коммуникатор. Есть надежда, что общение в нескольких коммуникаторах эффективней, чем в общей куче. Имеется нечто всеобъемлющее -- коммуникатор куда погружены все процессы. Он называется MPI_COMM_WORLD -- определен всегда. Каждый пар процесс имеет уникальный номер. В каждом коммуникаторе процесс может иметь свой номер. В способе формирования коммуникаторов и групп - полная свобода, они могут полностью вкладываться,частично пересекаться, вовсе не пересекаться. |
- | То, что касается сообщений. Набор однотипных данных, | + | То, что касается сообщений. Набор однотипных данных, кот передаются от одного процесса к другому. Это содержательная сторона сообщения. Важно, что все данные имеют один и тот же тип, для разнородной инфы требуется спец ритуальный танец. Каждое сообщение имеет тэг(некая доп информация, целое число). Введено понятие производных типов.Пользователь может создавать свои типы и их передавать. Например туда пользователь может внести неоднородность. |
- | Не во всех задачах процессы общаются аморфной кучей. Иногда процессы например образовывают кольцо, у каждого ровно два соседа. Есть понятие виртуальная топология, | + | Не во всех задачах процессы общаются аморфной кучей. Иногда процессы например образовывают кольцо, у каждого ровно два соседа. Есть понятие виртуальная топология, опредлив которое можно навести порядок в общении процессов друг с другом. Часто процессы распологают в узлах прямоугольной решетки с/без зацикленности по тору. |
- | Несколько слов о самой | + | Несколько слов о самой технлогии. Рассматривать будем на примере с. Основа с эта функция. |
- | Любая мпи функция возвращает код | + | Любая мпи функция возвращает код - MPI_SUCCESS - все закончилось нормально. Если вернулось не это значение -- код ошибки можно посмтореть в стандарте. |
- | * Общие функции. | + | *Общие функции. |
- | ** MPI_Init(int * argc, char *** argv); сколько процессов породилось | + | ** MPI_Init(int * argc, char *** argv); сколько процессов породилось - указано в аргв. Все остальные действия могут выполняться только поосле того как выполнилась функция мпи инит. Но и выполнить ее можно только один раз. |
- | ** MPI_Finalize(void) | + | ** MPI_Finalize(void) - закончить все мпи процессы. |
- | ** MPI_Initialized(int *flag) | + | ** MPI_Initialized(int *flag) - запускал ли кто-нибудь уже мпи_инит или нет.Содержательный результат возвращется через флаг |
- | ** MPI_Comm_size(MPI_COMM comm, int *size) | + | ** MPI_Comm_size(MPI_COMM comm, int *size) - количество параллельных процессоров в данном коммуникаторе. |
- | ** MPI_Comm_run(MPI_COMM comm, int *my_id) | + | ** MPI_Comm_run(MPI_COMM comm, int *my_id) -- коммуникатор и переменная куда будет зписан номер процесса. |
Осмысленная мпи программа: | Осмысленная мпи программа: | ||
Порождает некторое кол-во процессов, каждый процесс определяет сколько работает рядом с ним и свой номер. | Порождает некторое кол-во процессов, каждый процесс определяет сколько работает рядом с ним и свой номер. | ||
Строка 70: | Строка 68: | ||
} | } | ||
- | Сколько процессов порождается — указывается через argv. Напечатано будет столько раз, сколько процессов породилось. Порядок | + | Сколько процессов порождается — указывается через argv. Напечатано будет столько раз, сколько процессов породилось. Порядок в котором появятся выдачи заранее не определен, он может быть любым. Гарантируется лишь что строка — это неделимая сущность и она выдается целиком <!-- на самом деле, тут надо пояснить, кем это гарантируется. Так как неопределённость возникает именно при доступе к устройствам ввода-вывода, то иенно в сторону их и надо сотреть. Кроме того, понятно, что это гарантируется тем, что эти операции выполняются последовательно, не определён лишь их порядок (отсюда мораль — как можно меньше дёргать I/O) -->. |
* Взаимодействие процессов | * Взаимодействие процессов | ||
- | ** Коллективные операции(все процессы | + | ** Коллективные операции(все процессы воввлечены) |
** Точка-точка(взаимодействует пара процессов между собой) | ** Точка-точка(взаимодействует пара процессов между собой) | ||
*** Синхронные(с блокировкой) | *** Синхронные(с блокировкой) | ||
- | **** MPI_Send(void * buf, int count, MPI_Datatype, int dest, int tag, MPI_comm comm) — буфер сообщения который надо передать, кол-во элементов, тип элементов, номер процесса получателя, тег, в рамках какого коммуникатора. | + | **** 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_Recv(void * buf, int count, MPI_Datatype, int dest, int tag, MPI_comm comm, MPI_Status * status) — статус описывает статус принимаемого сообщения. Возврат произойдет только когда в буфер запишутся все count элементов принимаемого сообщения. |
- | ***: Вся система построена на том, что есть два процесса | + | ***: Вся система построена на том, что есть два процесса -- один посылает, а другой принимает. |
- | ***: Несколько общих замечаний. | + | ***: Несколько общих замечаний. |
- | ***: Предположим, есть процесс А и процесс Б. В некоторый момент процесс А посылает Б два сообщения. Процесс Б их может принять. И оба сообщения идут с одним и тем же тэгом. Есть ли гарантия того что сообщения придут в определенном порядке? Да. Если от одного и того же процесса ушли два сообщения, то первым приде то, | + | ***: Предположим, есть процесс А и процесс Б. В некоторый момент процесс А посылает Б два сообщения. Процесс Б их может принять. И оба сообщения идут с одним и тем же тэгом. Есть ли гарантия того что сообщения придут в определенном порядке? Да. Если от одного и того же процесса ушли два сообщения, то первым приде то, кторое первым было отправлено. Но вот если А и С отправляют что-то Б, то чьё сообщение придет первым -- неопределено |
- | ***: Есть константа MPI_ANYSOURCE | + | ***: Есть константа MPI_ANYSOURCE - если ее поставить в ресв то сообщения будут ждаться от любого процесса. Аналогично MPI_ANYTAG. |
- | ***: Справедливости в обслуживании процессов нет. Если Б | + | ***: Справедливости в обслуживании процессов нет. Если Б зкидывает А сообщениями в цикле, то еденичное сообщение из С в А может и не пробиться. |
***: Принятая семантика синхронных операций может приводить к тупиковым ситуациям. | ***: Принятая семантика синхронных операций может приводить к тупиковым ситуациям. | ||
***: Есть два процесса, им надо обменяться сообщениями. | ***: Есть два процесса, им надо обменяться сообщениями. | ||
Строка 89: | Строка 87: | ||
***: MPI_Send | ***: MPI_Send | ||
***: MPI_Recv | ***: MPI_Recv | ||
- | ***: А сделал сенд Б, аналогично Б сделал сенд А. А дальше у них стоит прием. Оба процесса могут стоять | + | ***: А сделал сенд Б, аналогично Б сделал сенд А. А дальше у них стоит прием. Оба процесса могут стоять бесконечон долго ожидая завершения мпи_сенд, из за особенности семантики мпи_сенд. Конкретная реализация может ожидать того, что принмающая сторона заберет сообщение. И все друг друга ждут. Эта ситуация описана во всех мануалах, она просто обходится при помощи операций асинхронного взаимодействия. Но к этому надо быть готовыми. Она может проявятьс япо разному -- аналогичный эффет возникает если надо организовать обмен сообщений между соседями в кольце. |
*** Асинхронные(без блокировки) | *** Асинхронные(без блокировки) | ||
{{Параллельная Обработка Данных}} | {{Параллельная Обработка Данных}} | ||
{{Lection-stub}} | {{Lection-stub}} |