Размещено на http://www.allbest.ru/

Введение

Важность параллельных программ

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

Проблемы разработки параллельных программ.

Трудность написания

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

Функциональная отладка

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

Отладка эффективности.

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

Глава 1. Параллельные программы и предсказание их выполнения

Модели параллельного программирования

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

Рассмотрим основные модели параллельного программирования:

Модель передачи сообщений. MPI.

В модели передачи сообщений параллельная программа представляет собой множество процессов, каждый из которых имеет собственное локальное адресное пространство. Взаимодействие процессов - обмен данными и синхронизация - осуществляется посредством передачи сообщений. Обобщение и стандартизация различных библиотек передачи сообщений привели в 1993 году к разработке стандарта MPI (Message Passing Interface). Его широкое внедрение в последующие годы обеспечило коренной перелом в решении проблемы переносимости параллельных программ, разрабатываемых в рамках разных подходов, использующих в качестве модели выполнения модель передачи сообщений.

В числе основных достоинств MPI по сравнению с интерфейсами других коммуникационных библиотек обычно называют следующие его возможности:

· Возможность использования в языках Фортран, Си, Си++;

· Предоставление возможностей для совмещения обменов сообщениями и вычислений;

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

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

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

· Удобные средства именования адресатов сообщений, упрощающие разработку стандартных программ или разделение программы на функциональные блоки;

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

Модель параллелизма по данным. HPF.

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

Модель параллелизма по данным имеет следующие достоинства.

· Параллелизм по данным является естественным параллелизмом вычислительных задач, поскольку для них характерно вычисление по одним и тем же формулам множества однотипных величин - элементов массивов.

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

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

Модель параллелизма по управлению. OpenMP.

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

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

Крупнейшие производители компьютеров и программного обеспечения объединили свои усилия и в октябре 1997 года выпустили описание языка OpenMP Fortran - расширение языка Фортран 77. Позже вышли аналогичные расширения языков Си и Фортран 90/95.

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

Модель параллелизма по данным и управлению. DVM.

Эта модель, положенная в основу языков параллельного программирования Фортран-DVM и Си-DVM, объединяет достоинства модели параллелизма по данным и модели параллелизма по управлению. Базирующаяся на этих языках система разработки параллельных программ (DVM) создана в Институте прикладной математики им. М.В. Келдыша РАН.

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

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

Система должна базироваться на высокоуровневой модели выполнения параллельной программы, удобной и понятной для программиста, привыкшего программировать на последовательных языках. Такая модель (DVM-модель) была разработана в 1994 году.

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

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

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

Предсказание.

Возможность предсказывать характеристики выполнения программ позволяет пользователю:

· отладить эффективность на рабочих станциях без параллельных ЭВМ

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

· оценить разные технические решения при проектировании ЭВМ (насколько они выгодны для определенного набора программ)

· оценка целесообразности приобретения ЭВМ (выгоднее и быстрее выполнять программу на n-процессорной машине, а, возможно, и на однопроцессорной машине)

Оценим возможности предсказания для описанных выше моделей:

Модель передачи сообщений. MPI.

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

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

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

Модель параллелизма по данным. HPF.

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

Возможный способ предсказания выполнения программ на HPF состоит в моделировании работы программы и системы поддержки.

Модель параллелизма по управлению. OpenMP.

В OpenMP витки параллельных циклов или параллельных секций распределяются между нитями. Нити работают над небольшим объемом данных (данных необходимых для выполнения нескольких витков цикла). В работе таких нитей велика роль кэша. А прогнозирование работы кэша весьма усложняет процесс предсказания характеристик выполнения OpenMP программ.

Модель параллелизма по данным и управлению. DVM.

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

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

DVM Предиктор.

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

Предиктор представляет собой систему обработки трассировочной информации, собранной системой поддержки выполнения DVM-программ (библиотекой Lib-DVM) во время прогона программы на инструментальной ЭВМ и состоит из двух крупных компонент: интерпретатора трассы (PRESAGE) и оценщика времени (RATER). По трассировке и заданным пользователем параметрам целевой ЭВМ, интерпретатор трассы вычисляет временные характеристики выполнения данной программы на целевой ЭВМ (MPP или кластере рабочих станций). При этом он вызывает функции оценщика времени, который, в свою очередь, моделирует параллельное выполнение DVM-программ и является, фактически, моделью библиотеки LIB-DVM, используемой ею библиотеки передачи сообщений (MPI) и аппаратуры.

Эффективность выполнения параллельных программ на многопроцессорных ЭВМ с распределенной памятью определяется следующими основными факторами:

степенью распараллеливания программы - долей параллельных вычислений в полном объеме вычислений;

равномерностью загрузки процессоров во время выполнения параллельных вычислений;

временем, необходимым для выполнения межпроцессорных обменов;

степенью совмещения межпроцессорных обменов с вычислениями;

эффективностью выполнения вычислений на каждом процессоре.

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

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

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

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

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

Компиляция программы;

Прогон программы.

Постановка задачи

Для более точного предсказания характеристик выполнения DVM программ предлагается:

1. Разработать и внедрить в существующий предиктор DVM более точную модель выполнения операции COPY (копирования секции одного массива в другой массив). С помощью этой модели предсказать характеристики выполнения этой операции и проверить точность такого предсказания на различных тестах.

2. Разработать и внедрить в существующий предиктор DVM алгоритм предсказания выполнения спецификации ACROSS параллельного цикла, а именно:

· Разобраться в особенностях конвейерной обработки ACROSS-циклов

· Выяснить возможность и эффективность использования конвейера для таких циклов.

· Разобраться в алгоритме запуска конвейера, реализованном в системе DVM.

· Построить модель выполнения трехмерного конвейера и, используя ее и алгоритм запуска конвейера в системе DVM, предсказать характеристики выполнения ACROSS-циклов. Внедрить этот алгоритм предсказания в существующий предиктор.

· Проверить точность предсказания на специально написанных тестах и тестах NAS (BT,SP,LU).

Глава 2. Операция копирования массивов COPY

Описание операции COPY

Язык C-DVM предоставляет средства для копирования распределенных массивов (секций распределенных массивов), которые позволяют обеспечить совмещение обмена данных с вычислениями.

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

Для того чтобы C-DVM программа могла компилироваться и выполняться как обычная последовательная программа, копирование массивов (секций) записывается как обычный многомерный цикл. Тело цикла должно состоять из единственного оператора присваивания. Заголовки цикла должны быть записаны макрокомандами DO(v,first,last,step) или FOR(v,times). Все переменные цикла должны использоваться в индексных выражениях правой и левой части оператора присваивания, причем в одном и том же порядке. Каждое индексное выражение может содержать только одну переменную цикла и должно зависеть от нее линейно.

Для асинхронного копирования нужно:

· объявить директивой COPY_FLAG переменную - флаг завершения операции копирования;

· перед циклом указать директиву COPY_START с адресом переменной-флага;

· перед использованием присвоенных значений убедиться в завершении (дождаться завершения) операции копирования директивой COPY_WAIT с адресом той же переменной.

Пример асинхронного копирования

DVM(DISTRIBUTE [BLOCK][]) float A[N][N];

DVM(ALIGN [i][j] WITH [j][i]) float B[N][N];

. . .

DVM(COPY_FLAG) void * flag;

. . .

DVM(COPY_START &flag)

FOR(i,N)

FOR(j,N)

B[i][j]=A[i][j];

. . .

DVM(COPY_WAIT &flag);

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

Пример синхронного копирования

DVM(COPY)

FOR(i,N)

FOR(j,N)

B[i][j]=A[i][j];

. . .

Алгоритм предсказания выполнения операции COPY

Рассмотрим операцию копирование массива A в массив B (B=A).

В системе DVM любое измерение массива бывает 2 типов:

· распределенное, когда индексы этого измерения массива распределяются между процессорами и каждый индекс попадает только на один процессор.

· размноженное, когда на каждом процессоре имеется весь диапозон индексов этого измерения массива.

Рассмотрим различные случаи распределения массивов A и В:

· если массив A полностью размножен (по всем измерениям), то для такого копирования требуется обращение типа “память-память” и коммуникаций при этом нет.

· если массив B полностью размножен и массив А распределен (хотя бы по одному измерению), то на каждом процессоре имеется своя копия массива B, которой надо присвоить элементы массива А. Для этого требуется рассылка частей массива A, которые имееются на любом процессоре всем остальным.

· если оба массива распределены (неважно как и по каким измерениям). В этом случае надо:

1. взять B_i - часть массива B на i-том процессоре.

2. вычислить A_i - часть массива A, которая потребуется для присваивания B_i. Для этого от начала блока массива A откладывается блок размером B_i.

3. все части A_i, которые не лежат на i-том процессоре, надо переслать на i-тый процессор.

Некоторые особенности при реализации предсказания по этому алгоритму:

· когда шаг копирования не равен 1, то при определении размера блока надо вычислять по схеме [(last - first)/step+1].

· когда шаг отрицательный, т.е копирование ведется в порядке убывание индексов. В этом случае можно перевернуть блок, так чтобы last>first и step>0 и считать этот блок по обычной схеме.

Глава 3. Спецификация ACROSS для параллельного цикла

Описание использования спецификации ACROSS

Рассмотрим следующий цикл



DO(i, 1, N-2, 1)

DO(j, 1, N-2, 1)

A[i][j] =(A[i][j-1]+A[i][j+1]+A[i-1][j]+A[i+1][j])/4.0;

Между витками цикла с индексами i1 и i2 (i1<i2) существует зависимость по данным (информационная связь) массива A, если оба эти витка осуществляют обращение к одному элементу массива по схеме запись-чтение или чтение-запись.

Если виток i1 записывает значение, а виток i2 читает это значение, то между этими витками существует потоковая зависимость или просто зависимость i1i2.

Если виток i1 читает “старое” значение, а виток i2 записывает “новое” значение, то между этими витками существует обратная зависимость i1i2.

В обоих случаях виток i2 может выполняться только после витка i1.

Значение i2 - i1 называется диапазоном или длиной зависимости. Если для любого витка i существует зависимый виток i + d (d - константа), тогда зависимость называется регулярной или зависимостью с постоянной длиной.

Цикл с регулярными вычислениями, в котором существуют регулярные зависимости по распределенным массивам, можно распределять с помощью директивы PARALLEL, указывая спецификацию ACROSS.

В спецификации ACROSS перечисляются все распределенные массивы, по которым существует регулярная зависимость по данным. Для каждого измерения массива указывается длина прямой зависимости (flow-dep-length) и длина обратной зависимости (anti-dep-length). Нулевое значение длины зависимости означает отсутствие зависимости по данным.

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

DVM(PARALLEL [i][j] ON A[i][j]; ACROSS A[1:1][1:1])

DO(i, 1, N-2, 1)

DO(j, 1, N-2, 1)

A[i][j]=(A[i][j-1]+A[i][j+1]+A[i-1][j]+A[i+1][j])/4.0;

По каждому измерению массива А существует прямая и обратная зависимость длиной 1.

Спецификация ACROSS реализуется через теневые грани. Длина обратной зависимости определяет ширину обновления правой грани, а длина прямой зависимости - ширину обновления левой грани. Обновление значений правых граней производится перед выполнением цикла (как для директивы SHADOW_RENEW). Обновление левых граней производится во время выполнения цикла по мере вычисления значений удаленных данных. Это позволяет организовать так называемые волновые вычисления для многомерных массивов. Фактически, ACROSS-ссылки являются подмножеством SHADOW-ссылок, между которыми существует зависимость по данным.

Конвейерная обработка спецификации ACROSS

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

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

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

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

Рассмотрим различные варианты использования конвейера:

Вариант 1

DVM(DISTRIBUTE [BLOCK]) float A[N];

DVM(PARALLEL [i] ON A[i]; ACROSS A[1:1])

DO(i, 1, N-2, 1)

A[i]=(A[i-1]+A[i]+A[i+1])/3.0;

Размещено на http://www.allbest.ru/

...

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Р процессоров

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Вариант 2

DVM(DISTRIBUTE [][BLOCK]) float A[N][N];

DVM(PARALLEL [i][j] ON A[i][j]; ACROSS A[1:1][1:1])

DO(i, 1, N-2, 1)

DO(j, 1, N-2, 1)

A[i][j]=(A[i][j-1]+A[i][j+1]+A[i-1][j]+A[i+1][j])/4.0;

Размещено на http://www.allbest.ru/

...

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Р процессоров

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Здесь лучше всего использовать одномерный конвейер по первому измерению с шагом X. При этом “x” - это остаток от деления длины первого измерения массива на шаг X, а “y” - количество индексов второго измерения, которые распределились на последний процессор.

Вариант 3

DVM(DISTRIBUTE [BLOCK][BLOCK]) float A[N][N];

DVM(PARALLEL [i][j] ON A[i][j]; ACROSS A[1:1][1:1])

DO(i, 1, N-2, 1)

DO(j, 1, N-2, 1)

A[i][j]=(A[i][j-1]+A[i][j+1]+A[i-1][j]+A[i+1][j])/4.0;

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

...

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

...

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

P1

... ... ...

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

...

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Р2 процес

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лучше всего использовать двумерный конвейер: по первому измерению с шагом X, а по второму с шагом Y. При этом возникают остатки от деления локальных размеров каждого процессора на шаги конвейера, т.е. x1, x2 и y1, y2. Эти величины тоже зависят от X и Y, что усложняет процесс определения оптимальных шагов разбиения.

Особенности конвейерной обработки цикла ACROSS

При использовании конвейера надо следить за тем, чтобы результат получался таким же, как и в случае отсутствия конвейерной обработки. Ведь в двумерном конвейере мы невольно меняем порядок вычисления элементов на одном процессоре, вычисляя сначала блок размера X на Y, а не всю первую строчку, т.е. переходим на вычисление второй строчки, не закончив вычисление первой. Это может привести к неправильным результатам.

Для того чтобы понять, когда это происходит, рассмотрим два случая:

Случай 1. Горизонтальный порядок выполнения цикла.

Обозначим:

“C” - старое значение элемента,

“T” - текущий элемент,

“Н” - новое значение элемента,

И рассмотрим цикл ACROSS A[1:1][1:1]. Получим следующую картинку:

H H H

H T С

С C C

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

Случай 2. Вертикальный порядок выполнения цикла.

В этом случае получим такую картинку:

H H C

H T C

H C C

Если сравнить эти два случая, то получится, что когда на [i][j]-том витке цикле есть обращения к элементам А[i-1][j+1] или А[i+1][j-1], то результаты горизонтального порядка и вертикального получатся разными.

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

H H C H H H

H T C H T C

C C C H C C

Если теперь сравним с горизонтальным порядком вычисления цикла, то придем к следующему выводу: когда на [i][j]-том витке цикле есть обращения к элементам А[i-1][j+1] или А[i+1][j-1], то описанная выше схема двумерного конвейера выдаст результат, отличный от результата без использования конвейера. Для того чтобы результат получился таким же, надо в предыдущей строке делать на один элемент больше вычислений или отказаться от квантования (т.е. разбиения на шаги конвейера) второго измерения, и использовать одномерный конвейер.

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

Последнее возможно на следующем примере (2 процессора, массив A[4][2] и цикл с зависимостями по данным во всех направлениях) (цифрами обозначим последовательность вычисления элементов, одинаковые цифры означают одновременное вычисление):

1 2 1 2

3 4 а если бы конвейер заработал, то было 2 3

5 6 3 4

7 8 4 5

Цикл нельзя выполнить быстрее последовательного его выполнения, и, значит, использование конвейера и любого количества процессоров здесь неэффективно.

Реализация конвейера в системе DVM

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

Требования к текущему параллельному циклу:

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

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

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

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

Механизм конвейера.

Витки цикла на каждом процессоре разбиваются на порции путём разбиения измерения цикла QuantumPLAxis на части. За измерение цикла QuantumPLAxis принимается измерение с минимальным номером, удовлетворяющее условиям:

измерение QuantumPLAxis линейно отображено в некоторое измерение распределённого массива;

локальная длина этого измерения (с учётом шага) больше единицы;

номер измерения QuantumPLAxis не равен номеру измерения PipeLinePLAxis.

Каждая очередная порция витков поступает на выполнение при очередном обращении к функции dopl_.

Перед передачей управления программе пользователя для выполнения n-й порции витков функция dopl_ осуществляет следующие действия:

ожидание завершения передачи ожидающему процессору частей всех теневых граней заданной группы границ, подготовленных для него при выполнении (n-2)-й порции витков (при n > 2);

инициализация неблокирующей передачи ожидающему процессору частей теневых граней, подготовленных для него при выполнении (n-1)-й порции витков (при n > 1);

инициализация неблокирующего приёма от ожидаемого процессора частей всех теневых граней заданной группы границ, которые будут им подготовлены (или уже подготовлены) при выполнении (n+1)-й порции витков (если n-я порция витков не является последней);

приём с ожиданием его завершения (при n = 1) или ожидание завершения приёма (при n > 1) от ожидаемого процессора частей всех теневых граней заданной группы границ, подготовленных им при выполнении n-й порции витков.

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

Если ожидаемого процессора не существует, то приём в теневые грани не производится.

Если системе поддержки не удалось найти измерение цикла, которое по сформулированным выше условиям может быть принято за измерение QuantumPLAxis, то процессорный конвейер не инициализируется (схема ACROSS будет выполнена без конвейеризации).

В системе DVM есть средства управления автоматическим определением шагов конвейера (файлы syspar.* базовых наборов параметров). Есть набор параметров, которые могут отменить использование конвейера в системе или задать число квантов конвейера для всех циклов сразу.

При нулевом значении параметра *PipeLineParPtr число групп координат витков для измерения цикла QuantumPLAxis будет определяться значением параметра запуска системы поддержки AcrossGroupNumber. Если значение параметра *PipeLineParPtr или параметра запуска системы поддержки AcrossGroupNumber равно -1, то инициализация схемы ACROSS будет осуществлена без конвейеризации.

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

Пусть конвейеризируемое измерение параллельного цикла имеет длину M и отображено на линейку из P процессоров.

Пусть также:

N размер квантуемого измерения цикла;

Q число квантов (порций), на которое разбито квантуемое измерение;

T_c время выполнения одного витка цикла;

T_m среднее время передачи одной обрабатываемой в цикле точки при межпроцессорных обменах;

W ширина границы для конвейеризируемого измерения цикла.

Тогда время выполнения программой пользователя порции витков при конвейеризации схемы ACROSS есть

(1)

Полное (с учётом межпроцессорных обменов) время выполнение порции витков в общем случае равно

T_irecv + T_wrecv + T_p + T_wsend + T_{isend ,}

где: T_irecv время инициализации приёма от ожидаемого процессора порции границ, необходимой для выполнения следующей порции витков;

T_wrecv время ожидания завершения приёма от ожидаемого процессора порции границ, необходимой для выполнения текущей порции витков;

T_wsend время ожидания завершения передачи ожидающему процессору порции границ, полученной после выполнения предыдущей порции витков;

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

Время выполнения схемы ACROSS определяется временем работы последнего в линейке процессора и равно

T_a =

T_irecv + T_1,wrecv + T_p + 0 + 0 +

T_irecv + T_wrecv + T_p + T_wsend,p + T_isend,p +

…….. …… ……… …… … …… ……… …… ……… ……

T_irecv + T_wrecv + T_p + T_wsend,p + T_isend,p +

0 + T_wrecv + T_p + T_wsend,p + T_isend,p

Всего Q строк-слагаемых

Здесь

T_1,wrecv время ожидания завершения приёма последним процессором первой порции границ;

T_wsend,p время ожидания завершения передачи последним процессором порции границ, полученной после выполнения предыдущей порции витков;

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

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

(2)

Время T_1,wrecv может быть представлено в виде



(3)

Подставляя (3) в (2) и заменяя T_p по формуле (1), получим

(4)

где:

При условии независимости K₁, K₂ и C от Q минимум времени выполнения схемы ACROSS T_a достигается при

(5)

Условие независимости K₁, K₂ и C от Q, при котором была получена формула (5), эквивалентно, очевидно, независимости от Q времени T_wrecv. Время T_wrecv является константой лишь в том случае, если порция границ, необходимая для выполнения следующей порции витков, успевает поступить от ожидаемого процессора за время выполнения текущей порции. Такой конвейер не вызывает задержек при обменах порциями границ.

В общем случае время T_wrecv определяется выражением

параллельный программа конвейер массив



(6)

Здесь

T_0,wrecv время ожидания завершения приёма порции границ, уже поступившей от ожидаемого процессора;

T_b время передачи порции границ.

Очевидно

(7)

Подставляя (7) и T_p из (1) в (6), имеем

(8)

Подставляя в (4) T_wrecv для недогруженного конвейера

(), получаем

(9),

где:



Минимум времени выполнения схемы ACROSS для недогруженного конвейера достигается при

(10)

Следует подчеркнуть, что при заданных объёмах обрабатываемых данных (M, N) наименьшее время выполнения цикла ACROSS достигается на сбалансированном конвейере

(при )

т.е. в точке перехода от перегруженного конвейера к недогруженному.

Такая схема соответствует одномерному конвейеру, и для него находит наилучший шаг. Но система DVM использует эту схему и в многомерных конвейерах.

Расчет шагов многомерного конвейера.

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

При этом если не найдет ни одного конвейеризуемого измерения или ни одного квантуемого - то система DVM выполнит цикл без использования конвейера.

Если найдутся необходимые измерения, то система вычисляет произведения всех конвейеризуемых измерений и обозначает за M, а произведение всех квантуемых за N. Ширину границы W для конвейеризируемого измерения цикла, фигурирующую в формулах (5) и (10), рассматривает как суммарный объём всех входящих в группу теневых параллелепипедов (совокупность теневых элементов, по которым идет обмен данными между процессорами), делённый на размер квантуемого измерения цикла.

Вновь вычисленные значения M, N, W подставляются в формулу (10), и система получает оптимальное количество квантов. При распределении общего числа квантов по квантуемым измерениям приоритет отдаётся внешним измерениям цикла: число квантов для самого внешнего измерения полагается равным его размеру; далее общее число квантов делится на этот размер, а остаток аналогично распределяется по наиболее внутренним измерениям.

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

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

Модель трехмерного конвейера

Мы имеем массив, распределенный по процессорам (на рисунке большие квадраты) и шаги конвейера X, Y, Z. Шаги определяют размеры внутренних квадратов. Остатки от деления размеров локального блока каждого процессора на шаг конвейера обозначим соответственно маленькими буквами x,y,z.

z2

Z

Z

z1

Z

Z

Z

Z

…

z1

Z

Z

Z

Z



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

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

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

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

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

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

DVM(DISTRIBUTE [BLOCK][BLOCK]) float A[N][N];

DVM(PARALLEL [i][j] ON A[i][j]; ACROSS A[1:1][1:1])

DO(i, 1, N-2, 1)

DO(j, 1, N-2, 1)

A[i][j]=(A[i][j-1]+A[i][j+1]+A[i-1][j]+A[i+1][j])/4.0;

Рассмотрим запуск такого цикла на процессорной решетке Px1. И пусть N=100. Считаем количество квантов (=100) одинаковым в обеих схемах. А коммуникации, для простоты, считаем бесконечно быстрыми.

Схема горизонтального обхода:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Время выполнения такого конвейера будет 100*100=10000

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

P

...

Размещено на http://www.allbest.ru/

Схема вертикального обхода:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

P Время выполнения такого конвейера будет 100*X+(P-2)*X+x.

... X=100 div P; x=100 mod P, => выигрыш по сравнению с горизонтальным случаем почти в P раз.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Алгоритм предсказания выполнения спецификации ACROSS

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

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

А в конце работы предиктор все интервалы выводит в виде файла на языке HTML.

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

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

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

Глава 4. Результаты предсказания программ DVM на МВС 1000М

Собиралась трасса выполнения на 1 процессоре соответствующих программ на МВС-1000М. Далее предсказание по трассе проводилось в среде Windows без доступа к параллельной машине. Результаты предсказания сравнивались с реальными характеристиками программ и приведены в виде следующих графиков .

Программа копирования

Времена выполнения программы

Времена коммуникационных расходов



Расхождение времен выполнения в точке 2x2 связано с возникновением при счете системных расходов (возможно из-за непопадания в кэш).

Программа SOR

Времена выполнения программы

Времена коммуникационных расходов

Времена работы процессоров



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

Заметим, что такое поведение программы не является разовым, а повторяется от запуска к запуску SOR программы.



Тесты NAS

Программа BT

Времена выполнения программы

Времена коммуникационных расходов

Недостаточный параллелизм



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

В тестах NAS (BT,SP,LU) используются распределения данных только по одному измерению. Поэтому запуск программу на двумерной решетке заведомо приводит к дублированию вычислений и снижению эффекта распараллеливания. Этот факт измеряется величиной недостаточного параллелизма.

Программа SP

Времена выполнения программы



Времена коммуникационных расходов

Недостаточный параллелизм

Здесь предсказание получилось достаточно точным к реальному выполнению программы.



Программа LU

Времена выполнения программы

Времена коммуникационных расходов Недостаточный параллелизм



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



Заключение

В данной дипломной работе реализована новая версия предиктора, которая более точно предсказывает характеристики DVM программ, что было показано на примерах тестов NAS.

В процессе выполнения работы:

1. Детально изучены исходные тексты и документация к системе поддержки DVM

2. В предикторе разработан и внедрен более точный алгоритм предсказания выполнения операции COPY.

3. Изучены возможность и эффективность конвейерной обработки ACROSS-циклов

4. Разработан и внедрен в существующий предиктор DVM алгоритм предсказания выполнения спецификации ACROSS параллельного цикла.

Новая версия предиктора проверена на точность предсказания на специально написанных тестах и тестах NAS (BT,SP,LU).

Предиктор реализован на языке Си++. В результате проделанной работы изменения коснулись 20 файлов предиктора. Были добавлены 15 новых функций и внесены изменения в тела 12 функций. Заменено или добавлено 1323 строк кода суммарным объемом 44 067 байт.