ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 1521
Скачиваний: 4
Метрики параллельных вычислений 4 8 1
Общая форма параллелизма на уровне программ проистекает из разбиения про-
граммируемых данных на подмножества. Это разделение называют
декомпозицией
области
(domain decomposition), а параллелизм, возникающий при этом, носит
название
параллелизма данных.
Подмножества данных назначаются разным вы-
числительным процессам, и называется этот процесс
распределением данных
(data
distribution). Процессоры выделяются определенным процессам либо по инициа-
тиве программы, либо в процессе работы операционной системой. На каждом про-
цессоре может выполняться более чем один процесс.
Параллелизм уровня команд
Параллелизм на уровне команд имеет место, когда обработка нескольких команд
или выполнение различных этапов одной и той же команды может перекрываться
во времени. Разработчики вычислительной техники издавна прибегали к методам,
известным под общим названием «совмещения операций*-, при котором аппарату-
ра ВМ в любой момент времени выполняет одновременно более одной операции.
Этот общий принцип включает в себя два понятия:
параллелизм
и
конвейеризацию.
Хотя у них много общего и их зачастую трудно различать на практике, термины
эти отражают два принципиально различных подхода.
В первом варианте совмещение операций достигается за счет того, что в соста-
ве вычислительной системы отдельные устройства присутствуют в нескольких
копиях. Так, в состав процессора может входить несколько АЛУ, и высокая произ-
водительность обеспечивается за счет одновременной работы всех этих АЛУ. Вто-
рой подход был описан ранее.
Метрики параллельных вычислений
В силу особенностей параллельных вычислений для оценки их эффективности
используют специфическую систему метрик. Наиболее распространенные из та-
ких метрик рассматриваются ниже.
Профиль параллелизма программы
Число процессоров многопроцессорной системы, параллельно участвующих в вы-
полнении программы в каждый момент времени
t,
определяют понятием
степень
параллелизма D(t)
(DOP, Degree Of Parallelism). Графическое представление па-
раметра
D(t)
как функции времени называют
профилем параллелизма программы.
Изменения в уровне загрузки процессоров за время наблюдения зависят от мно-
гих факторов (алгоритма, доступных ресурсов, степени оптимизации, обеспечива-
емой компилятором и т. д.). Типичный профиль параллелизма для алгоритма де-
композиции (divide-and-conquer algorithm) показан на рис. 10.1.
В дальнейшем будем исходить из следующих предположений: система состоит
из л гомогенных процессоров; максимальный параллелизм в профиле равен
т
и,
в идеальном случае,
п >> т.
Производительность одиночного процессора систе-
мы выражается в единицах скорости вычислений (количество операций в едини-
цу времени) и не учитывает издержек, связанных с обращением к памяти и пере-
сылкой данных. Если за наблюдаемый период загружены i процессоров, то
D - i.
16 Заk. 470
4 8 2 Глава 10. Параллелизм как основa высокопроизводительных вычислений
Рис. 1 0 . 1 . Профиль параллелизма
Общий объем вычислительной работы
W
(команд или вычислений), выпол-
ненной начиная со стартового момента t
s
до момента завершения
t
c
,
пропорциона-
лен площади под кривой профиля параллелизма:
Интеграл часто заменяют дискретным эквивалентом:
Средний параллелизм А
определяется как
В дискретной форме это можно записать так:
Профиль параллелизма на рисунке за время наблюдения
(t
s
, t
c
)
возрастает от 1
до пикового значения
т
= 8, азатем спадает до 0. Средний параллелизм A = (1x5 +
+ 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
а объем работы, выполненной в ре-
Метрики параллельных вычислений 4 8 3
Асимптотическое повышение быстродействия 5_ определяется как отношение
Сравнивая это выражение и предыдущие уравнения, можно констатировать,
что в идеальном варианте S
oo
=
А.
В общем случае нужно учитывать коммуникаци-
онные задержки и системные издержки. Отметим, что как S
oo
, так и
А
были опреде-
лены в предположении, что
п >> т.
В прикладных программах имеется широкий диапазон потенциального парал-
лелизма. М. Кумар в своей статье [146] приводил данные, что в вычислительно
интенсивных программах в каждом цикле параллельно могут выполняться от 500
до 3500 арифметических операций, если для этого имеется существующая вычис-
лительная среда. Однако даже правильно спроектированный суперскалярный про-
цессор способен поддерживать выполнение от 2 до 5,8 команды за цикл. Эти циф-
ры дают пессимистическую картину возможного параллелизма.
Ускорение, эффективность, загрузка и качество
Рассмотрим параллельное выполнение программы со следующими характеристи-
- 0(n) — общее число операций (команд), выполненных на «-процессорной сис-
теме;
-
Т(п) —
время выполнения
О(п)
операций на n-процессорной системе в виде
числа квантов времени.
В общем случае
Т(п) < О(п),
если в единицу времени
п
процессорами выполня-
ется более чем одна команда, где «
>
2. Примем, что в однопроцессорной системе
T(1) = о(1).
Ускорение
(speedup), или точнее, среднее ускорение за счет параллельного вы-
полнения программы — это отношение времени, требуемого для выполнения наи-
лучшего из последовательных алгоритмов на одном процессоре, и времени парал-
лельного вычисления на
п
процессорах. Без учета коммуникационных издержек
ускорение
S(n)
определяется как
Как правило, ускорение удовлетворяет условию
S(n) <= п.
Эффективность
(efficiency) n-процессорной системы — это ускорение на один
процессор, определяемое выражением
4 8 4 Глава 10. Параллелизм как основа высокопроизводительных вычислений
Эффективность обычно отвечает условию 1
/п < =Е(п) < =п.
Для более реалис-
тичного описания производительности параллельных вычислений необходимо
промоделировать ситуацию, когда параллельный алгоритм может потребовать
больше операций, чем его последовательный аналог.
Довольно часто организация вычислений на
п
процессорах связана с существен-
ными издержками. Поэтому имеет смысл ввести понятие
избыточности
(redun-
dancy) в виде
Это отношение отражает степень соответствия между программным и аппарат-
ным параллелизмом. Очевидно, что 1
<= R(n) <= п.
Определим еще одно понятие,
коэффициент полезного использования
или ути-
лизации (utilization), как
Тогда можно утверждать, что
Рассмотрим пример. Пусть наилучший из известных последовательных алго-
ритмов занимает 8 с, а параллельный алгоритм занимает на пяти процессорах 2 с
Тогда:
-
S(n) =8/2 = А;
- E
(n)=4/5 = 0,8;
-R(n)=
1/0,8- 1=0,25.
Собственное ускорение
определяется путем реализации параллельного алгоритма
на одном процессоре.
Если ускорение, достигнутое на
п
процессорах, равно и, то говорят, что алго-
ритм показывает
линейное ускорение.
В исключительных ситуациях ускорение S(n) может быть больше, чем и. В этих
случаях иногда применяют термин
суперлинейное ускорение.
Данное явление имеет
шансы на возникновение в двух следующих случаях:
- Последовательная программа может выполняться в очень маленькой памяти,
вызывая свопинги (подкачки), или, что менее очевидно, может приводить
к большему числу кэш-промахов, чем параллельная версия, где обычно каждая
параллельная часть кода выполняется с использованием много меньшего набо-
ра данных.
- Другая причина повышенного ускорения иллюстрируется примером. Пусть нам
нужно выполнить логическую операцию
А
1
v
A
2
где как
А
1
, так и
А
2
имеют зна-
чение «Истина» с вероятностью 50%, причем среднее время вычисления
А
i
, обо-
Метрики параллельных вычислений 4 8 5
значенное как T(A
i
), существенно различается в зависимости от того, является
ли результат истинным или ложным.
Пусть
, Теперь получаем четыре равновероятных случая (Т — «истина», F — «ложь»):
Таким образом, параллельные вычисления на двух процессорах ведут к сред-
нему ускорению:
Отметим, что суперлинейное ускорение вызвано жесткостью последователь-
ной обработки, так как после вычисления еще нужно проверить
А
2
.
К факторам, ограничивающим ускорение, следует отнести:
-
Программные издержки.
Даже если последовательные и параллельные алго-
ритмы выполняют одни и те же вычисления, параллельным алгоритмам прису-
щи добавочные программные издержки — дополнительные индексные вычис-
ления, неизбежно возникающие из-за декомпозиции данных и распределения
их по процессорам; различные виды учетных операций, требуемые в параллель-
ных алгоритмах, но отсутствующие в алгоритмах последовательных.
-
Издержки из-за дисбаланса загрузки процессоров.
Между точками синхро-
низации каждый из процессоров должен быть загружен одинаковым объемом
работы, иначе часть процессоров будет ожидать, пока остальные завершат свои
операции. Эта ситуация известна как
дисбаланс загрузки.
Таким образом, уско-
рение ограничивается наиболее медленным из процессоров.
-
Коммуникационные издержки.
Если принять, что обмен информацией и вы-
числения могут перекрываться, то любые коммуникации между процессорами
снижают ускорение. В плане коммуникационных затрат важен уровень грану-
лярности, определяющий объем вычислительной работы, выполняемой между
коммуникационными фазами алгоритма. Для уменьшения коммуникационных
издержек выгоднее, чтобы вычислительные гранулы были достаточно крупны-
ми и доля коммуникаций была меньше.
Еще одним показателем параллельных вычислений служит
качество
параллель-
ного выполнения программ — характеристика, объединяющая ускорение, эффек-
тивность и избыточность. Качество определяется следующим образом: