Средства распараллеливания алгоритмов

Шаг 1

Шаг 2

Шаг 1

Шаг 2

Шаг 1

Шаг 2

Шаг 1

Шаг 2

Шаг 1

Шаг 0: присваиваются исходные значения

M=0, t=0 (М – критерий остановки алгоритма).

Шаг 1: Do Through шаг 3

while M¹2

else Stop

Шаг 2: If t=четное Then сравнить (I_2k, I_2k-1) для (P_2k, P_2k-1), " K=1, 2, …, N/2

If I_2k<I_2k-1 then

I_2k®P_2k-1

I_2k-1®P_2k

Шаг 3: If была перестановка Then M=0

Else M=M+1

t=t+1

Этот алгоритм сортировки упорядочивает массив из N чисел за N+1 шагов в реальном масштабе времени, производя на каждой итерации N/2 операций сравнения, что требует время порядка O(N²).

Современные суперЭВМ в большинстве являются параллельными системами, поэтому важной задачей является стандартизация методов распараллеливания алгоритмов и программ. Известно, что параллельные системы строятся либо с разделяемой памятью, либо с общей памятью. Для систем 1-го типа существует стандарт распараллеливания MPI. Здесь задача распараллеливания сводится к разделению на подзадачи меньших размеров с обменом сообщениями между ними. Для систем 2-го типа разработан стандарт OpenMP. В этом случае задачи легче поддаются распараллеливанию, и нет необходимости в дополнительной пересылке данных.

Существует несколько видов средств распараллеливания.

1) Autotasking – это автоматическое распараллеливание с помощью компиляторов последовательного кода, написанного на языке С и Fortran.

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

Кроме того, компилятор распознает типовые операции (умножение матриц) и генерирует обращение к специальным библиотекам быстрых подпрограмм для параллельных систем, написанных на Ассемблере.

2) Macrotasking – это программный код, который вносится в программу вручную. Его называют кодированием с явным вызовом нитей.

3) Microtasking – это автораспараллеливание с указанием директив. Директивы указывают компилятору на параллельный код, скрываемый в операторах циклов, ввода/вывода и отдельных фрагментах программы.

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

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

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

В основном используются системы третьего типа. Для них существует несколько стандартизированных способов распараллеливания, основанных на общем наборе директив.

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

В основе OpenMP лежит модуль fork/join (WWW.OpenMP.Org)

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

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

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

Переменные, объявляемые как Private, при входе в параллельную конструкцию является неопределенными для любого процессора.

C$OMP Parallel [ключ, ключ, …]

блок операторов

C$OMP End Parallel [NOWAIT]

Флаг NOWAIT определяет синхронизацию процесса.

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

Распределение подзадач между процессорами задается с помощью одной из 2-х конструкций.

1. C$OMP Do [ключи]

тело цикла

C$OMP End Do

Ключи бывают следующие:

ü Private;

ü Shared;

ü Reduction;

ü Ordered;

ü Schedule.

1) Schedule указывает способ планирования выполнения цикла, объявляется вместе с параметрами:

Schedule (тип, М)

Типы могут быть:

- Static – операции, которые будут распараллеливаться статически.

- Dynamic – операции будут распараллеливаться динамически порциями по М итераций. Т. о. если какой-либо процессор заканчивает свою работу, то ему выделяют следующую порцию.

- Guided – размер порций экспоненциально уменьшается для каждой новой порции, выдаваемой процессору.

- Runtime – тип планирования, т. е. значение переменной М задается во время выполнения программы.

2) Reduction позволяет организовать параллельное выполнение цикла с вычислением суммы значений функции.

Например:

C$OMP Parallel Do Reduction (+ Sum)

C$OMP Private (x)

Do i=1,N

x=a(i)

sum=sum + F(x)

End Do

C$OMP End Parallel Do

2. Если фрагмент программы не содержит циклов, то для распределения работы между процессорами используется другая директива:

C$OMP Sections [ключи]

C$OMP Section

блок операторов

[C$OMP Section

блок операторов]

…

C$OMP End Sections

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

Кроме того, может использоваться также следующая директива:

C$OMP Single

…

C$OMP End Single

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

Для синхронизации параллельных процессов используются директивы

C$OMP Barrier

C$OMP Atomic,

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

Существует также директива

C$OMP Ordered

…

C$OMP End Ordered,

которая задает блок операторов, которые обязательно выполняются последовательно.

В разработке данного стандарта приняли участие IBM, HP, Gray Research, Intel, SGI. Пример подобного компьютера – MIPS pro 7.21 (SGI).

Дата добавления: 2014-01-07