Автоматическое обнаружение параллелизма

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

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

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

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

При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R и выходных (записываемых) переменных W каждого процесса.

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

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

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

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

г) преобразование блоков условных переходов и циклов к каноническому виду;

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

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

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

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