Модели параллельных вычислений. Эффективные параллельные алгоритмы.
При оценке эффективности параллельного алгоритма широко используется модель абстрактной параллельной ЭВМ с общей памятьюPRAM (Parallel Random Access Machine). Полагается, что все N процессоров PRAM идентичны. Имеется три типа PRAM, отличающихся моделью того, что происходит при одновременном обращении нескольких процессоров к одной ячейке памяти:
В зависимости от способа разрешения конфликта по одновременной записи в ячейку памяти выделяется несколько типов CRCW PRAM. В самой слабой из моделей CRCW PRAM одновременная запись в ячейку возможна только нулей, в наиболее сильной – результатом записи является максимальное из записываемых чисел.
Эффективность алгоритма для PRAM определяется временем исполнения, как функцией длины входного вектора задачи и количества процессоров (см. ниже).
Одной из центральных проблем науки о параллельных вычислениях является выделение классов задач, для решения которых существуют эффективные параллельные алгоритмы – алгоритмы, которые могут быть решены на PRAM с числом процессоров () за полиномиальное время. Обозначим этот класс задач .
Определение 1. Задача принадлежит классу задач NC, если существуют такие константы , и такой алгоритм ее решения, что на PRAM с процессорами задача может быть решена за время
Доказано, что каждая следующая из рассмотренных моделей PRAM может выполнить любой шаг предыдущей модели за конечное число шагов. Доказано также, что каждый шаг наиболее сильной модели CRCW PRAM с процессорами может быть выполнен наиболее слабой моделью за шагов. Отсюда следует
Утверждение 1. Класс не зависит от модели PRAM
Можно показать, что , где класс задач P – класс задач, разрешимых на однопроцессорной ЭВМ за полиномиальное время.
Для многих задач класса доказана их принадлежность классу , например, для задачи линейного программирования. Однако до настоящего времени вопрос о совпадении этих классов остается открытым. Заметим, что совпадение этих классов означало бы, что любая задача, принадлежащая классу , допускает эффективное распараллеливании.
Для оценки эффективности параллельных алгоритмов в основном используют следующие величины:
Средняя степень параллелизма.
Средней степенью параллелизма называется отношение общего числа операций алгоритма к высоте ЯПФ алгоритма. Например, для алгоритма сдваивания чисел (см. параграф 1) средняя степень параллелизма равна

(поскольку общее число операций алгоритма равно , а высота ЯПФ - .
Идеальный параллельный алгоритм имеет степень параллелизма (например, алгоритм сложения двух векторов).
Средняя степень параллелизма характеризует только сам параллельный алгоритм. Из этой характеристики никак не следует эффективность этого алгоритма для конкретной параллельной вычислительной системы.
Ускорение параллельного алгоритма.
Ускорение параллельного алгоритма является его наиболее информативной характеристикой, которая показывает во сколько раз применение параллельного алгоритма уменьшает время решения задачи по сравнению с последовательным алгоритмом. Ускорение параллельного алгоритма определяется величиной
 (1)

где - время выполнения алгоритма на одном процессоре, - время выполнения того же алгоритма на процессорах.
Идеальным, очевидно, является ускорение . В реальности это ускорение недостижимо. Перечислим причины невозможности достижения идеального ускорения:
Пример 1
Рассмотрим в качестве примера ускорение, которое может обеспечить алгоритм сдваивания при умножении вещественных чисел на -процессорной вычислительной системе. Положим, что числа , хранятся на первом процессоре, числа , - на втором процессоре, и т.д. Пусть – время выполнения сложения на одном процессоре, а - время обмена одним вещественным числом между соседними процессорами. Тогда искомое ускорение
 (2)

Заметим, что более строго в числителе формулы (2) следовало бы написать , а в знаменателе - (log2-1)(1+). Однако, при достаточно больших единицей в числителе и в первом из сомножителей знаменателя можно пренебречь.
Поскольку , из равенства (2) следует
 (3)

Очевидно, идеальной ситуаций является ситуация, когда можно пренебречь временем обмена данными, т.е. когда можно положить . Сравним этот случай со случаем, когда время обмена равно времени выполнения умножения . Из формулы (3) следует, что при этом ускорение алгоритм сдваивания падает в два раза (см. рис. 1).
Рис. 1.  К примеру 1. Зависимость ускорения алгоритма сдваивания от числа процессоров в системе. Прямая SN=N соответствует идеальному случаю.
Рис.1 получен с помощью следующей MATLAB – программы:
N=2:1:100;
plot(N,N);
p=log2(N);
S=(2*N)./(1+p);
hold on
plot(N,S);
hold on
S=(2/3)*(2*N)./(1+p);
plot(N,S);
hold on
S=0.5*(2*N)./(1+p);
plot(N,S);
Примечание 1
Как уже указывалось, в формуле (1) величина - время выполнения алгоритма на одном процессоре. Но, как мы видели, параллельный алгоритм может содержать лишние операции по сравнению с соответствующим последовательным алгоритмом. Т.е., вообще говоря, параллельный алгоритм не является «хорошим» для последовательной реализации. Поэтому, более строго, в формуле (1) в качестве величины следует использовать время выполнения быстрейшего последовательного алгоритма на одном процессоре
Эффективность параллельного алгоритма.
Эффективность параллельного алгоритма определяется величиной
 (4)

где - ускорение параллельного алгоритма, - количество процессоров в системе.
Из того факта, что , следует ограничение сверху на величину эффективности: .
Пример 2
В условиях прим. 1 рассмотрим эффективность, которую может обеспечить алгоритм сдваивания. Из формул (3), (4) для этого алгоритма имеем
 (5)

Рис. 2.  К примеру 2. Зависимость эффективности алгоритма сдваивания от числа процессоров в системе. Прямая EN=1 соответствует идеальному случаю.
Рис.2 получен с помощью следующей MATLAB – программы:
N=2:1:100;
plot(N,1);
p=log2(N);
E=2./(1+p);
hold on
plot(N,E);
E=4/3./(1+p);
hold on
plot(N,E);
E=1./(1+p);
hold on
plot(N,E);
Можно выделить следующие основные причины потери эффективности параллельных вычислений:
Время инициализации параллельной программы – это время генерации начальных данных (часто на одном процессоре) и рассылки результатов по всем процессорам.
Несбалансированность загрузки процессоров приводит к тому, что часть процессоров вынуждена какое-то время простаивать. На проблеме балансировки загрузки процессоров мы детально останавливались в главе 1.3.
Затраты на коммуникации определяются пропускной способностью коммуникационной сети, латентностью коммуникационной сети, диаметром коммуникационной сети (который в значительной мере определяется топологий коммуникационной сети. Коммуникационные затраты могут быть сокращены за счет использования встречных обменов данными и асинхронной передачи данных. Современные коммуникационные средства параллельных вычислительных систем, а также коммуникационные библиотеки допускают использование встречных обменов, когда данные передаются одновременно в обе стороны. Асинхронные обмены данными (обмены данными, выполняемые параллельно с выполнением вычислений) также поддерживаются большинством современных параллельных компьютеров, как на аппаратном, так и программном уровнях.
Закон Амдала (Amdahl).
Несколько детализируем величину - положим
 (6)

Здесь
- доля операций, выполняемых на одном процессоре - минимальный параллелизм;
- доля операций, выполняемых на процессорах () – частичный параллелизм;
- доля операций, выполняемых на процессорах (максимальный параллелизм);
- время подготовки данных.
Выделим три следующих частных случая:
  1. Легко видеть, что в этом случае ускорение максимально возможно и равно ;
  2. Здесь ускорение равно средней степени параллелизма , т.е. ;
  3. Ускорение в этом случае называется законом Амдала (см. рис. 3)
     (7)

Рис. 3.  Закон Амдала. Если всего 1% (α=0.01) операций выполняется последовательно, то ускорение уменьшается вдвое по сравнению с максимально возможным.
Рис.3 получен с помощью следующей MATLAB – программы:
N=1:1:100;
alpha=0.01;
S=N./(N*alpha+(1-alpha));
plot(N,S);
alpha=0.02;
S=N./(N*alpha+(1-alpha));
hold on
plot(N,S);
alpha=0.03;
S=N./(N*alpha+(1-alpha));
hold on
plot(N,S);
alpha=0.04;
S=N./(N*alpha+(1-alpha));
hold on
plot(N,S);
Из закона Амдала следует, что если, к примеру, , т.е. всего 10% операций программы выполняется последовательно, то при любом, как угодно большом количестве используемых процессоров , ускорение, превышающее 10, принципиально получить невозможно (см. табл.1).
Таблица 1    
Количество процессоров
21.331.601.821.901.96
81.782.914.715.937.02
321.943.667.8012.5519.75
511.993.979.8319.2845.63
20482.003.999.9619.8248.83

Таблица 1. Предельное ускорение, как функция доли последовательных операций в процентах и количества процессоров .
В формуле (7) не учитывается возможный дисбаланс загрузки процессоров. Введем в рассмотрение коэффициент дисбаланса загрузки процессоров . Тогда формула (7) примет вид
 (8)

Если учесть еще коммуникационные потери времени, то формула (7) примет вид
 (9)

где = - коэффициент сетевой деградации; , - количество операций обмена данными и общее количество вычислительных операций, соответственно; , - время выполнения одной операций обмена данными и время выполнения одной вычислительной операции, соответственно. Формула (9) определяет сетевой закон Амдала.
«Парадокс» параллелизма.
«Парадокс» параллелизма» состоит в достижении ускорения (1) и эффективности (4) параллельного алгоритма, превышающих значения и 1, соответственно. Другими словами, «парадокс» параллелизма состоит в «суперлинейном» росте производительности параллельной вычислительной системы с ростом количества ее процессоров.
«Парадокс» параллелизма, по сути, не является парадоксом. Ускорение параллельного алгоритма, превышающее , возможно по двум основным причинам.
  1. Суммарная оперативная память параллельной системы превышает оперативную память последовательной ЭВМ, с которой производится сравнение. Это позволяет на параллельной системе разместить всю программу в оперативной памяти, в то время как на последовательной ЭВМ приходится использовать выгрузку программы на накопитель на жестких магнитных дисках («свопинг»).
  2. Использование на параллельной вычислительной системе априори параллельного алгоритма, который не может быть использован на последовательной ЭВМ (например, снова из-за оперативной памяти).