Электронный коспект лекций (1162752), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Решетка транспьютеров, вкоторойкаждый транспьютер параллельно с вычислениямиможет обмениваться одновременно по 8 каналам с 4 соседями,является хорошимпримером,длякоторого будутформулироваться различные экзаменационные задачи.Время передачисообщениямеждудвумяузламитранспьютерной матрицы определяется двумя характеристикамиаппаратуры - временем старта передачи Ts и временем передачиодногобайта информации соседнему узлу Tb. При этомпроцессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми. За время Ts+Tbтранспьютер может передать 1 байт информации своим четыремсоседям и принять от них 4 байта информации (по одному байту откаждого).Конвейеризация (разбиение сообщения на кванты, чтобывоспользоваться параллельной работой каналов вдоль маршрутапередачи) и параллельное использование нескольких маршрутов –два метода ускорения передачи сообщений.3.1ОбменсообщениямимеждуприкладнымипроцессамиSEND, RECEIVE (адресат/отправитель, [тэг,] адрес памяти, длина)адресация - физический/логическийномерпроцессора,уникальный идентификатор динамически создаваемого процесса,служба имен (сервер имен или широковещание - broadcasting).Обычно пересылкавсоседний компьютер требует трикопирования - из памяти процесса-отправителя в буфер ОС насвоем компьютере, пересылка между буферами ОС, копирование впамять процесса-получателя.Блокирующие операцииsend(до освобождения памяти сданными или до завершения фактической передачи) инеблокирующие.Буферизуемые и небуферизуемые (rendezvous или с потерейинформации при отсутствии receive).Надежные и ненадежные.MPI - Message-Passing Interface [4](Message Passing Interface Forum, May 5, 1994http://www.mpi-forum.org)(1) Цели: Создать интерфейс прикладного программирования (не толькодля компиляторов или библиотек реализации систем); Обеспечитьвозможностьэффективных коммуникаций(избежать копирования из памяти впамять,позволитьсовмещение вычислений и коммуникаций или разгрузку накоммуникационный процессор там, где он есть); Разрешить расширения для использования в гетерогеннойсреде; Исходить из надежности коммуникаций (пользователь недолжен бороться с коммуникационными сбоями - это делокоммуникационных подсистем нижнего уровня); Определить интерфейс, который бы не слишком отличалсяот используемых в то время, таких как PVM, Express, P4, и пр.; Определить интерфейс,который мог бы быстро бытьреализован на многих продаваемых платформах без серьезнойпеределки коммуникационного и системного ПО.**************************************************************(2) Что включено в MPI ? Коммуникации точка-точка; Коллективные операции; Группы процессов; Коммуникационные контексты; Простой способ создания процессов для модели SPMD(одна программа используется для обработки разныхданных на разных процессорах); Топология процессов.**************************************************************(3) Что не включено в MPI ? Явные операции с разделяемой памятью и явная поддержканитей (процессов с общей памятью); Операции, которые требуют больше поддержки отоперационных систем, чем действующие в настоящее времястандарты на ОС (например, получение сообщений черезмеханизм прерываний, активные сообщения); Вспомогательные функции, такие как таймеры.**************************************************************(4) Некоторые понятия.Коммуникационные операции могут быть:неблокирущие - если возврат осуществляется до завершенияоперации;блокируюшие - если возврат означает, что пользователь можетиспользовать ресурсы (например, буфера), указанные в вызове;Операция называется локальной, если ее выполнение нетребует коммуникаций; нелокальной, еслиеевыполнениеможет требовать коммуникаций; коллективной, если в еевыполнении должны участвовать все процессы группы.(5) Группы, контексты, коммуникаторы.Группа - упорядоченное (от 0 до ранга группы) множествоидентификаторов процессов (т.е.

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

могут рассматриваться как пара - группа иконтекст. Кроме того, они служат и для целей оптимизации,храня необходимые для этого дополнительные объекты.Имеются предопределенные коммуникаторы (точнее, создаваемыепри инициализации MPI-системы): MPI_COMM_WORD - все процессы MPI_COMM_SELF - один текущий процесс**************************************************************(6) Операции над группами (локальные, без обмена сообщениями).Для поддержкипользовательскихсерверовимеетсяколлективная операция разбиения группы на подгруппы поключам, которые указывает каждый процесс группы.Для поддержки связывания с серверами, имеются средствапостроения коммуникатора по некоторому имени, известному исерверу и клиентам.(7) Точечные коммуникации.Основные операции - send, receiveОперации могут быть блокирующими и неблокирующими.В операции send задается: адрес буфера в памяти; количество посылаемых элементов; тип данных каждого элемента; номер процесса-адресата в его группе; тег сообщения; коммуникатор.(последние 3 параметра - аналоги «почтового конверта»)В операции receive задается:адрес буфера в памяти;количество принимаемых элементов;тип данных каждого элемента;номер процесса-отправителя в его группе (либо «любой»);тег сообщения (либо «любой»);коммуникатор;статус (источник и тег, необходимые в том случае, когдаони неизвестны - при их задании с помощью шаблона«любой»).Предусмотрена конвертациягетерогенной среде.данныхприработевИмеется четыре режима коммуникаций - стандартный,буферизуемый, синхронный и режим готовности.В стандартном режиме последовательность выдачи операцийsend и receive произвольна, операция send завершается тогда,когда сообщение изъятоизпамяти процесса (например,переписано в системный буфер) и эта память уже можетиспользоваться процессом.

При этом выполнение операцииможет осуществляться независимо от наличия receive, либотребовать наличие (вопрос реализации MPI). Поэтому операциясчитается нелокальной.В буферизуемом режиме последовательность выдачи операцийsend и receive произвольна, операция send завершается тогда,когда сообщение изъято из памяти и помещено в буфер,предварительно заведенный в памяти процесса. Если места вбуфере нет - ошибка программы (но есть возможность определитьсвой буфер).

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

Операция нелокальная.Во всех четырех режимах операция receive завершается послеполучения сообщения в заданный пользователем буфер приема.Неблокирующие операции не приостанавливают процесс досвоего завершения,авозвращаютссылкунакоммуникационный объект, позволяющий опрашивать состояниеоперации или дожидаться ее окончания.Имеются операции проверки поступающих процессу сообщений,без чтения их в буфер (например, для определения длинысообщения и запроса затем памяти под него).Имеется возможностьаварийнозавершатьвыданныенеблокирующие операции,и поэтому предоставленывозможности проверки, хорошо ли завершились операции.Имеется составная операция send-receive, позволяющая избежатьтрудностей с порядком выдачи отдельных операций вобменивающихся между собой процессах. Для частного случаяобмена даннымиодного типа и длины предлагаетсяспециальная операция (send-receive-replace),в которой дляпосылки и приема сообщения используется один буфер.(8) Коллективные коммуникации.Для обеспечения коллективныхследующие функции:коммуникацийвведены барьер для всех членов группы (BARRIER); передача сообщения всем членам группы от одного(BROADCAST); сбор данных от всех членов группы для одного (GATHER); рассылка данных всем членам группы от одного (SCATTER); сбор данных от всех членов группы для всех (ALLGATHER); рассылка данных всем членам группы от всех (ALLTOALL); глобальные операции (сумма, максимум, и т.п.), когдарезультат сообщается всем членам группы или толькоодному.

При этом пользователь может сам определитьглобальную операцию - функцию;Схема перемещения данных между 4 процессамиДанныеPr-0Pr-1Pr-2Pr-3A0BROADCASTA0A0A0A0Pr-0Pr-1Pr-2Pr-3A0A1A2A3SCATTERGATHERA0A1A2A3Pr-0Pr-1Pr-2Pr-3A0A0A0A0A1A1A1A1A2A2A2A2A3A3A3A3ALLGATHERA0A1A2A3Pr-0Pr-1Pr-2Pr-3A0B0C0D0A1B1C1D1A2B2C2D2A3B3C3D3ALLTOALLA0A1A2A3Названия функций и параметры:MPI_BARRIER(IN comm)B0B1B2B3C0C1C2C3D0D1D2D3MPI_BCAST(IN/OUT buffer, IN cnt, IN type, IN root, IN comm)MPI_GATHER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,IN recvcnt, IN recvtype, IN root, IN comm)MPI_SCATTER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,IN recvcnt, IN recvtype, IN root, IN comm)MPI_ALLGATHER(IN sendbuf, IN sendcnt, IN sendtype,OUT recvbuf, IN recvcnt, IN recvtype, IN comm)MPI_ALLTOALL(IN sendbuf, IN sendcnt, IN sendtype, OUTrecvbuf,IN recvcnt, IN recvtype, IN comm)У последних 4-х функций есть векторные варианты,предназначенные для работы с неравномерным распределениемданных по процессорам.PVM (Parallel Virtual Machine).Широко известная система PVM [5] была создана дляобъединения нескольких связанных сетью рабочих станций вединуювиртуальную параллельнуюЭВМ.Системапредставляет собой надстройку над операционной системойUNIX и используется в настоящее время на различныхаппаратных платформах, включая и ЭВМ с массовымпараллелизмом.Задача пользователя представляет собой множество подзадач,которыединамически создаются на указанных процессорахраспределенной системы и взаимодействуют между собойпутем передачи и приема сообщений (а также посредствоммеханизма сигналов).Достоинства - простота, наличие наследованного от OS UNIXаппарата процессов исигналов,а также возможностьдинамического добавления к группе вновь созданных процессов.Недостатки - низкая производительность и функциональнаяограниченность (например, имеется только один режим передачисообщений - с буферизацией).MPI-2 (1997 г.) http://www.mpi-forum.orgРазвивает MPI в следующих направлениях: Динамическое создание и уничтожение процессов (важно дляработы в сетях ЭВМ). Односторонние коммуникации и средства синхронизации дляорганизации взаимодействия процессов через общую память(для эффективной работы на системах с непосредственнымдоступом процессоров к памяти других процессоров). Параллельные операции ввода-вывода (дляэффективногоиспользования существующих возможностей параллельногодоступа многих процессоров к различным дисковымустройствам).4 Синхронизация в распределенных системахОбычно децентрализованные алгоритмы имеют следующиесвойства:(1) Относящаяся к делу информацияраспределенамножества ЭВМ.(2)Процессыпринимаютрешение на основелокальной информации.средитолько(3) Не должно быть единственной критической точки, выход изстроя которой приводил бы к краху алгоритма.(4) Не существует общих часов или другого источника точногоглобального времени.Первые три пункта все говорят о недопустимости сборавсей информации дляпринятия решения в одно место.Обеспечение синхронизации безцентрализациитребуетподходов, отличных от используемых в традиционных ОС.Последний пункт также очень важен - в распределенныхсистемах достигнуть согласия относительно времени совсемнепросто.

Характеристики

Список файлов лекций