Параллелизм независимых ветвей

Крупнозернистый параллелизм.

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

DO 11 = 1,N

1 C(I,J) = A(I,J) + B(I,J)

Нетрудно видеть, что при фиксированном J операции сложения для всех I можно выполнять параллельно, поскольку ЯПФ этого цикла имеет один ярус. По существу этот цикл соответствует сложению столбца J матриц А и В с записью результата в столбец J матрицы С. Этот цикл на параллельном языке записывается в виде такой векторно операции:

С (*, j) = A (*, j) + В (*, j).

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

Области применения векторных операций над массивами обширны: цифровая обработка сигналов (цифровые фильтры); механика, моделирование сплошных сред;

метеорология; оптимизация; задачи движения; расчеты электрических характеристик БИС

и т. д.

Суть параллелизма независимых ветве состоит в том, что в программе решения большо задачи могут быть выделены независимые программные части — ветви. Под независимостью ветве в первую очередь понимается независимость по данным.

В параллельных языках запуск параллельных ветве осуществляется с помощью оператора FORK Ml, М2,..., ML, где Ml, М2,..., ML — имена независимых ветве. Каждая ветвь заканчивается оператором JOIN (R,K), выполнение которого вызывает вычитание единицы из ячейки памяти R. Так как в R предварительно записано число, равное количеству ветве, то при последнем срабатывании оператора JOIN (все ветви выполнены) в R оказывается нуль и управление передается на оператор К. Иногда в JOIN описывается подмножество ветвей, при выполнении которого срабатывает этот оператор. В последовательных языках аналогов операторам FORK и JOIN нет и ветви выполняются друг за другом. Рассмотрим пример задачи с параллелизмом ветве.

Параллелизм вариантов

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

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

Системы распределенных вычислений идеальны для решения вариантных задач. Закон Амдала.

Одной из главных характеристик параллельных систем является ускорение R параллельной системы, которое определяется выражением:

R = Ti /Т_п,

где Т^ - время решения задачи на однопроцессорной системе, а Тп - время решения той же задачи на п - процессорной системе.

Пусть W = W^ + Wi j,, где W - общее число операций в задаче, W_m - число операций, которые можно выполнять параллельно, a W_g - число скалярных (нераспараллеливаемых) операций.

Обозначим также через t время выполнения одной операции. Тогда получаем известный закон Амдала [13]:

Здесь а = W^ /W - удельный вес скалярных операций.

Закон Амдала определяет принципиально важные для параллельных вычислени положения:

•S ускорение зависит от потенциального параллелизма задачи (величина 1- а) и параметров аппаратуры (числа процессоров п).

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

Пусть, например, а = 0,2 (что является реальным значением), тогда ускорение не может превосходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи. Очевидной является чрезвычайно высокая чувствительность ускорения к изменению величины а.

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