Профиль параллелизма программы

 

Число процессоров многопроцессорной системы, параллельно участвующих в вы­полнении программы в каждый момент времени t, определяют понятием степень параллелизма D(t) (DOP, Degree Of Parallelism). Графическое представление па­раметра D(t) как функции времени называют профилем параллелизма программы. Изменения в уровне загрузки процессоров за время наблюдения зависят от мно­гих факторов (алгоритма, доступных ресурсов, степени оптимизации, обеспечива­емой компилятором и т. д.). Типичный профиль параллелизма для алгоритма де­композиции (divide-and-conquer algorithm) показан на рис. 86.

В дальнейшем будем исходить из следующих предположений: система состоит из п гомогенных процессоров; максимальный параллелизм в профиле равен т и, в идеальном случае, п >> т. Производительность А одиночного процессора систе­мы выражается в единицах скорости вычислений (количество операций в едини­цу времени) и не учитывает издержек, связанных с обращением к памяти и пере­сылкой данных. Если за наблюдаемый период загружены i процессоров, то D = i.

 

 

Рис. 86. Профиль параллелизма.

 

Общий объем вычислительной работы W (команд или вычислений), выпол­ненной начиная со стартового момента t_s до момента завершения t_e, пропорциона­лен площади под кривой профиля параллелизма:

.

Интеграл часто заменяют дискретным эквивалентом:

,

где – общее время, в течение которого , а – общее затраченное время.

Средний параллелизм А определяется как

.

Профиль параллелизма на рисунке за время наблюдения (t_s, t_e) возрастает от 1 до пикового значения т = 8, а затем спадает до 0. Средний параллелизм А = ( 1 х 5 + 2 x 3 + 3 x 4 + 4 x 6 + 5 x 2 + 6 x 2 + 8 x 3) /(5 + 3 + 4 + 6 + 2 + 2 + 3) = 93/25 = 3,72. Фактически общая рабочая нагрузка и А представляют собой нижнюю гра­ницу асимптотического ускорения.

Будем говорить, что параллельная программа выполняется в режиме i, если для ее исполнения задействованы i процессоров. Время, на продолжении которого си­стема работает в режиме i, обозначим через t_i, а объем работы, выполненной в режиме i, как . Тогда, при наличии п процессоров время исполнения Т(п) для двух экстремальных случаев: п = 1(T(1)) и n = ∞(T(∞)) можно записать в виде:

и .

Асимптотическое повышение быстродействия S_∞ определяется как отношение T(1) к T(∞):

.

Сравнивая это выражение и предыдущие уравнения, можно констатировать, что в идеальном варианте S_∞ = A. В общем случае нужно учитывать коммуникаци­онные задержки и системные издержки. Отметим, что как S_∞ так и А были опреде­лены в предположении, что n >> m.

В прикладных программах имеется широкий диапазон потенциального парал­лелизма. М. Кумар в своей статье приводил данные, что в вычислительно интенсивных программах в каждом цикле параллельно могут выполняться от 500 до 3500 арифметических операций, если для этого имеется существующая вычис­лительная среда. Однако даже правильно спроектированный суперскалярный про­цессор способен поддерживать выполнение от 2 до 5,8 команды за цикл. Эти циф­ры дают пессимистическую картину возможного параллелизма.