WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

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

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

В качестве примера рассмотрим цикл:

for (i = 1; i <= 100; i++) for(j = 1; j <=100; j++) { X[i,j] = X[i,j] + Y[i – 1,j]; /*s1*/ Y[i,j] = Y[i,j] + X[i,j - 1]; /*s2*/ } Распределение данных по вычислителям для таких задач можно построить с помощью инструмента среды ParJava «DataDistr», который использует методы целочисленного программирования. Для приведенного примера этот инструмент выдаст следующую модификацию цикла с распределением независимых данных по вычислителям:

X[1,100] = X[1,100] + Y[0,100]; /*s1*/ for (p = -99; p <= 98; p++) { if (p >= 0) Y[p+l,l] = X[p+l,0] + Y[p+l,l]; /*s2*/ for (i = max(l,p+2); i <= min(100,100+p); i++) { X[i,i-p-l] = X[i,i-p-l] + Y[i-l,i-p-l];/*s1*/ Y[i,i-p] = X[i,i-p-l] + Y[i,i-p]; /*s2*/ } if (p <= -1) X[101+p,100] = X[101+p,100] + Y[101+p-l,100];

/*s1*/ } Y[100,l] = X[100,0] + Y[100,l]; /*s2*/ где p – номер вычислителя, а цикл по p определяет распределение данных по вычислителям. Таким образом, исходный цикл расщепился на 200 цепочек вычислений, каждая из которых может выполняться независимо.

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

Если программа принадлежит к классу задач, сводящихся к системе линейных алгебраических уравнений с полной матрицей, то массив, в котором хранится матрица системы, разбивается на блоки. При этом у смежных блоков возникают так называемые теневые грани, размер которых определяется алгоритмом решения задачи и определяет фактический объем передаваемых в сети сообщений. Очевидно, что в случае, когда по всем индексам взаимосвязи между элементами массива однородны, то оптимальнее всего разбивать массив по всем его размерностям, так как с увеличением количества плоскостей разбиения суммарный объем передаваемых данных снижается. Так, при обработке трехмерного массива с Nэлементами уже при использовании 128 вычислителей, в случае одномерного разбиения и толщины теневой грани в один элемент объем передаваемых данных равен 254N2, в случае двумерного разбиения – 44N2, а в случае трехмерного разбиения – 26N2. Однако, в случае неоднородных зависимостей по различным индексам может выясниться, что разбиения по некоторым индексам приводят к дополнительным обменам. Так как это обусловлено спецификой конкретной решаемой задачи, оно не может быть оценено заранее.

В предлагаемой методологии с помощью инструмента среды ParJava “Reduction” строится так называемый «скелет» программы, в котором сохранены доля последовательных вычислений, объем пересылок и время счета тела цикла.

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

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

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

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

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

В MPI определено несколько видов посылки и приема сообщений:

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

В качестве примера рассмотрим программу, в которой процесс отправляет данные (массив buf0) соседнему процессу с помощью функции MPI_Issend, а тот, в свою очередь, получает данные, используя функцию MPI_Irecv. На рисунке схематически показана передача данных из массива buf0 процесса P0 в массив bufпроцесса P1.

s t0 на рисунке 1) будут При вызове MPI_Issend (момент времени инициализированы необходимые структуры данных, доступ к буферу buf0 будет передан сетевому процессору (процесс NP0 ), который будет выполнять передачу P0 NP0 NP1 Pr MPI_Irecv t0 MPI_Issend s tr ts t1 MPI_WaitMPI_Waits tMPI_Waitr tMPI_WaitРисунок 1 Схема процесса неблокирующего обмена сообщения, а процесс P0 продолжит выполнять свою программу. Таким образом, выполнение операции MPI_Issend в процессе P0 закончится в момент времени s t1. До тех пор пока процессу P0 не потребуется снова использовать массив buf0, он может выполняться параллельно с передачей данных. Как только процессу Pпотребуется поместить новые данные в buf0, он должен вызвать функцию MPI_Wait, которая обеспечит доступ к массиву buf0, как только процесс NPs tзакончит передачу данных в сеть, и буфер освободится (момент ). Начиная с Временная ось этого момента, буфер buf0 будет свободен, и его можно будет снова использовать в процессе P0. Следовательно, как показано на рисунке 1, вызов MPI_Waits tзаблокирует процесс P0 до момента, а вызов MPI_Wait2 не приведет к блокировке процесса P0.

Для приема сообщения, процесс P1 вызывает функцию MPI_Irecv (в момент r tвремени ), которая инициализирует структуры данных, после чего выполнение процесса P1 будет продолжено, а прием сообщения будет осуществлять сетевой процесс NP1, записывающий данные в массив buf1 процесса P1. Выполнение r tоперации MPI_Irecv в процессе P1 закончится в момент времени. Момент времени, когда процесс NP1 получит все данные из сети, на рисунке обозначен r tчерез. Как только процессу P1 понадобятся данные из принимающего буфера (buf1), он вызовет функцию MPI_Wait (MPI_Wait4). Если бы функция MPI_Wait r tбыла вызвана до момента, (вызов MPI_Wait3), процесс заблокировался бы до r tмомента.

Сетевые процессоры могут одновременно обслуживать и посылку, и прием данных. Время, потраченное на запрос (разрешение) на передачу данных от процесса NP0 к процессу NP1 определяется латентностью сети (L).

Как видно из схемы на рисунке 1 необходимо добиться, чтобы во время s tпередачи данных сетевым процессором (промежуток между моментами времени s r r t2 t1 tи для отправителя и время между и для получателя) вычислитель был занят обработкой данных, а не простаивал в ожидании окончания пересылки.

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

Проиллюстрировать важность оптимального выбора операций пересылок можно на следующем «скелете» программы (рисунок 2 а). Если в рассматриваемом «скелете» заменить блокирующие операции Send и Recv на неблокирующие и установить соответствующую операцию Wait после гнезда циклов, получится «скелет», представленный на рисунке 2б. На рисунке 3 приведены графики ускорения «скелетов» программ, представленных на рисунках 2а и 2б. Пунктирная линия, идущая под 45 градусов к осям, обозначает идеальное ускорение, при котором последовательная часть равна нулю. Вспомогательная пунктирная медиана - это вспомогательная линия, позволяющая судить о качестве масштабируемости.

//sending //sending ISend Send IRecv Recv //calculating //calculating for (i = beg_i + 1; i < end_i - 1; i++) for (i = beg_i; i < end_i; i++) for (j = 0; j < N; j++) for (j = 0; j < N; j++) B[i][j] = f(A[i][j]);

B[i][j] = f(A[i][j]);

//waiting Wait();

//calculating last columns if (myid != 0) for (j = 0; j < N; j++) B[0][j] = f(tempL[j]);

if (myid != proc_size - 1) for (j = 0; j < N; j++) B[N - 1][j] = f(tempR[j]);

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

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

Сравнение на модельном примере 0 5 10 15 20 25 процессоры блокирующий send неблокирующий send Амдалева кривая для этой программы Рисунок 3 Сравнение масштабируемости параллельных программ, использующих блокирующие и неблокирующие пересылки К сожалению, в большинстве реальных программ такими простыми преобразованиями не удается достичь необходимого уровня перекрытия, либо такое ускорение преобразование невозможно. Использование предлагаемой методологии обеспечивает возможность применения различных преобразований программы и достижения необходимых параметров программы в приемлемое время.

На следующем этапе необходимо проинтерпретировать полученную программу на реальных данных, для того, чтобы оценить, какое количество вычислителей будет оптимальным для счета. Для этого используется инструмент среды ParJava «Inerpreter».

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

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

Применение интерпретатора позволяет достаточно точно оценивать ускорение программы. Ошибка на реальных приложениях не превосходила 10%, и в среднем составила ~5%.

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

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

Пользователь указывает в программе место сохранения данных с помощью директивы EXCLUDE_HERE. С помощью этих директив компилятор может выполнять анализ потока данных. В контрольной точке 1 (рисунок 4) не сохраняются данные, которые будут обновлены до своего использования («мертвые» переменные). В контрольной точке 2 не сохраняются данные, которые используются только для чтения до этой контрольной точки. Результатом будет значительное уменьшение размеров сохраняемых данных в контрольной точке и уменьшение накладных расходов на сохранение.

Контрольная точка Контрольная точка Рисунок 4 Контрольные точки Выполнение программы Вначале граф потока управления G=(N, E) разбивается на подграфы G.

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

Для каждого подграфа вычисляются 2 множества переменных:

• DE(G) - множество переменных, которые «мертвы» на каждой директиве EXCLUDE_HERE в G.

• RO(G) - множество переменных, предназначенных только-для-чтения по всему подграфу G.

Для нахождения двух множеств DE(G) и RO(G) используется консервативный анализ потока данных.

В каждом состоянии S в программе вычисляются множествя def[S] и use[S], характеризующие доступ к памяти:

• use[S] – множество переменных, которые могут быть использованы вдоль некоторого пути в графе.

• def[S] – множество переменных, которым присваиваются значения до их использования вдоль некоторого пути в графе, начинающегося в S, или множество определений переменных.

Определив эти базовые множества, мы можем определить DE(G) и RO(G):

Ячейка памяти l «живая» в состоянии S, если существует путь из S в другое состояние S такой, что l use[S] и для каждого S на этом пути ldef[S]. Ячейка l является элементом DE(G), если l «мертвая» во всех операторах сохранения контрольных точек в G.

Ячейка памяти l является ячейкой только-для-чтения в операторе S, если l use[S]. Поэтому l RO(G) тогда и только тогда, когда lgen[S] для всех S в G.

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

Анализ «живых» переменных обычно выражается в виде уравнений потоков данных, по одному на каждое состояние в программе. Мы дадим уравнение потока данных, которое позволит нам определить DE(G) и RO(G) для каждого подграфа G в программе. Каждое из этих уравнений может быть решено обычным итеративным методом.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»