Параллельное программирование в модели "параллелизм данных"

Параллельное программирование в модели параллелизм данных

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

Эта модель не обладает свойствами, привязывающими е§ к какой-то конкретной параллельной архитектуре, будь то SIMD или MIMD . Основным архитектурным признаком этой модели является то, что компьютер, реализующий эту модель, работает одновременно с набором слов памяти, а не с каждым словом отдельно, как это происходит в последовательном компьютере.

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

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

Рассмотрим введение параллельных вычислений для случая все сразу на примере следующего фрагмента программы на языке Фортран, в котором необходимо каждый элемент массива A разделить на соответствующий элемент массива B и сохранить в результат в массиве C:

 DO i = lbound(A) , ubound(B)
  IF (B(i) /= 0) THEN
   C(i) = A(i) / B(i)
  END IF 
 END DO

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

FORALL(индексная_переменная=нижний_индекс : верхний_индекс [: шаг][, условие])

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

 FORALL (i = lbound(A): ubound(B): 1, B(i) /= 0 ) 
  C(i) = A(i) / B(i) 
 END FORALL

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

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

Другой подход во введении параллельности типа все сразу состоит в том, чтобы использовать вместо for-циклов групповые, монолитные операции, которые имеют дело не с отдельными элементами массивов, а с целыми массивами или с регулярными подмножествами их элементов. В этом случае программист должен стараться вместо сложных циклов использовать наборы простых циклов, содержащих элементарные операции с тем, чтобы простые циклы можно было заменить монолитными операциями. Поскольку монолитные операций обычно имеют ту же мнемонику, что и скалярные, то во избежание путаницы в некоторых языках требуется выделять операнды монолитные операций с помощью дополнительных обозначений. Например, в Фортране 90 для указания массива используется цепочка '(:)'. Это частный случай общей формы, которая позволяет указывать регулярные подмножества элементов массива:

переменная_массив([нижний_индекс]: [верхний_индекс[: шаг]])

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

Программа на Фортране 90, в которой каждый элемент массива A делится на соответствующий элемент массива B, а в результат сохраняется в массиве C, с помощью операции монолитного деления и оператора where может быть записана следующим образом:

 WHERE ( B(:) /= 0 ) 
  C(:) = A(:) / B(:) 
 END WHERE