§26. Степень параллелизма численного алгоритма

В этом параграфе представлен ряд основных понятий и способов измерения параллелизма [27, 41]. Начнем со случая парал­лельной системы, состоящей из pпроцессоров. Дадим, прежде всего, некоторые определения.

Определение 3. Степенью параллелизма численного алгоритма называется число его операций, которые можно вы­полнять параллельно.

Проиллюстрируем это определение несколькими примерами и по ходу дела уточним его. Начнем с задачи сложения двух векторов а и b. Сложения независимы и могут выполняться параллельно. Таким образом, степень параллелизма этого алгоритма равна n. Отметим, что понятие степени параллелизма не связано с числом процессоров нашей системы, оно является характеристикой параллелизма, внутренне присущего алгоритму. Разумеется, от числа процес­соров зависит время, необходимое для завершения вычислений. Например, если n= 1000 и число процессоров p также равно 1000, то все суммы условно можно вычислить за один временной шаг, однако при p = 10 потребуется 100 временных шагов.

Рассмотрим теперь задачу сложения n чисел . Обычный последовательный алгоритм: – непригоден для параллельных вычислений. Однако в самой задаче заключен немалый параллелизм. На рис. 54 показано, как можно осуществить суммирование восьми чисел в три этапа. Задача суммирования разделена на меньшие подзадачи, которые могут решаться независимо. Граф на рис. 54 называется графом сдваивания. В частности, та же идея применима к вычисле­нию произведения nчисел , достаточно заменить на рис. 54 знак + на знак *. Точно так же, чтобы найти максимальное из nчисел , можно заменить знак операции сложения символом max; например, вместо на рис. 54 стояло бы , и т. д. Заметим, что граф на рис. 54 представляет собой двоичное дерево, поэтому операцию, вы­полняемую с помощью графа сдваивания, иногда называют операцией на дереве.

Для чисел алгоритм сдваивания состоит из этапов; на первом этапе выполняются n/2 сложений, на втором - n/4, и т. д., пока на последнем этапе не будет выполнено единственное сложение. Очевидно, что на первом этапе степень параллелизма равна n/2, на втором - n/4, и т. д.

Определение 4. Средней степенью параллелизма числен­ного алгоритма называется отношение общего числа операций алгоритма к числу его этапов.

Рис. 54. Схема алгоритма сдваивания

Для алгоритма сдваивания средняя степень параллелизма равна , тогда как при сложении двух n-векторов средняя степень параллелизма равна n, т. е. совпадает со степенью параллелизма. Этот последний алгоритм обладает «идеальным» параллелизмом, в то время как для алгоритма сдваивания средняя степень параллелизма в раз меньше идеальной. И все же алгоритм сдваивания можно считать хорошо параллелизуемым, особенно по сравнению с последовательным алгоритмом, для которого средняя степень параллелизма равна .

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