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

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

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

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

В системах с конвейерной архитектурой, таких как CRAY-1, предусмотрены специальные векторные команды, позволяющие за одно обращение выполнить операцию над всеми элементами вектора.

Векторизующий компилятор –это программа, которая просматривает исходный текст

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

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

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

Рассмотрим пример умножения на вектор:

C_i=Σ(от m до j=1) A_IJB_J

Do 10 i=1,4

C(i)=0

Do 10 j=1,4

C (i)=c(i)+A(I,j)+B(j)

10 continue

in parallel for 1<i<4 , 1<j<4 do begin

temp (I,j)=a(I,j)*b(j)

end in parallel do

in parallel for 1<i<4 do begin

c(i)=0

do 0 j=1,4

c(i) = c(i)+temp(I,j)

10 continue

end in parallel

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

Второе условие – независимость по данным между операциями проводимыми над отдельными элементами векторов for (i=0: j<n: i++)

Третье условие – регулярность расположения элементов векторов (расстояние между элементами вектора, которое подвергается обработки, должно быть известным, постоянным и одинаковым).

Четвертое условие – отсутствие обращений к функциям пользователя при обработке элементов вектора: {f(a[i]};}