3.7.3.Автоматическое распараллеливание

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

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

COBEGIN;

оператор-1;

оператор-2;

оператор-n;

COEND;

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

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

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

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

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

3.7.3.1Расщепление цикла

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

FOR I=1 TO 4 DO

A(I) = B(I)+C(I);

Этот цикл суммирует соответствующие элементы массивов B и C и помещает суммы этих элементов в массив А. По данному программному циклу последовательный процессор выполняет поочередно следующие операции:

А(1)=В(1)+С(1);

А(2)=В(2)+С(2);

А(3)=В(3)+С(3);

А(4)=В(4)+С(4);

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

COBEGIN;

А(1)=В(1)+С(1);

А(2)=В(2)+С(2);

А(3)=В(3)+С(З);

А(4)=В(4)+С(4);

COEND;

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