Параллельная обработка

Необходимость параллельной обработки может возникнуть по следующим причинам [27]:

1. Надо уменьшить время решения данной задачи.

2. Увеличить пропускную способность.

3. Улучшить использование системы.

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

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

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

Например.

Рассмотрим граф, описывающий последовательность процессов большой программы (см. рис.3.17).

Рис. 3.17. Граф выполнения большой программы

Из рисунка видно, что выполнение процесса р₅ не может начаться до завершения процессов р₂ и р₃ и в свою очередь выполнение процессов р₂ и р₃ не может начаться до завершения процесса р₁.

В данном случае для выполнения программы достаточно трех процессоров.

Ускорение обработки на многопроцессорной системе определяется отношением времени однопроцессорной обработки к времени многопроцессорной обработки, т.е.

(4.1)

При автоматическом обнаружении параллельных вычислений мы различаем в последовательной программе явную и скрытую параллельную обработку. Хотя в обоих случаях требуется анализ программы, различие между этими видами обработки состоит в том, что скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выполнение. При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R (Read) и выходных (записываемых) переменных W (Write) каждого процесса. Два процесса i, j (i<>j) могут выполняться параллельно при следующих условиях:

R_i I W_j = Æ (пустое множество)

W_i I R_j = Æ

W_i I W_j = Æ

(4.2)

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

· уменьшение высоты деревьев арифметических выражений;

· преобразование линейных рекуррентных соотношений;

· замена операторов;

· преобразование блоков IF и DO к каноническому виду;

· распределение циклов.

Проиллюстрируем эти преобразования на простых примерах. На
рис. 3.18 показаны деревья разбора для арифметического выражения (((a+b)+c)+d). На рис. 3.18а изображено дерево минимальной высоты (3) для первоначального выражения, а на рис. 3.18б - дерево, высота которого уменьшена до 2 путем преобразования первоначального выражения к виду (a+b)+(c+d) с использованием ассоциативности. Для арифметического выражения с n переменными или константами уменьшение высоты дерева позволяет достигнуть ускорения обработки порядка O(n/log₂ n) при использовании O(n) процессоров. В примере, показанном на рис. 3.18, выражение может быть вычислено за два шага вместо трех первоначальных.

а) б)

Рис. 3.18. Деревья разбора до (а) и после (б) преобразования

Рассмотрим следующий блок операторов присваивания:

X=BCD+E

Y=AX

Z=X+FG

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

X=BCD+E

Y=ABCD+AE

Z=BCD+E+FG

Этот блок может быть вычислен параллельно за три шага с ускорением обработки 6/3 = 2 при использовании 5 процессоров.

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