Файл: 481-550.pdf

4 8 6 Глава 10. Параллелизм как основа высокопроизводительных вычислений

Поскольку как эффективность, так и величина, обратная избыточности, пред-

ставляют собой дроби, то Q(n)

 < =S(n).

 Поскольку

 Е(п)

 — это всегда дробь, a

 R(n) -

число между 1 и и, качество

 Q(n)

 при любых условиях ограничено сверху величи-

ной ускорения S(n).

Закон Амдала

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

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

 п

 раз, В реальности достичь такого показателя по ряду причин

не удается. Главная из этих причин заключается в невозможности полного распа-
раллеливания ни одной из задач. Как правило, в каждой программе имеется фраг-
мент кода, который принципиально должен выполняться последовательно и толь-
ко одним из процессоров. Это может быть часть программы, отвечающая за запуск
задачи и распределение распараллеленного кода по процессорам, либо фрагмент
программы, обеспечивающий операции ввода/вывода. Можно привести и другие
примеры, но главное состоит в том, что о полном распараллеливании задачи гово-
рить не приходится. Известные проблемы возникают и с той частью задачи, кото-
рая поддается распараллеливанию. Здесь идеальным был бы вариант, когда па-
раллельные ветви программы постоянно загружали бы все процессоры системы,
причем так, чтобы нагрузка на каждый процессор была одинакова. К сожалению,
оба этих условия на практике трудно реализуемы. Таким образом, ориентируясь
на параллельную ВС, необходимо четко сознавать, что добиться прямо пропорцио-
нального числу процессоров увеличения производительности не удастся, и, есте-
ственно, встает вопрос о том, на какое реальное ускорение можно рассчитывать.
Ответ на этот вопрос в какой-то мере дает закон Амдала.

Джин Амдал (Gene Amdahl) — один из разработчиков всемирно известной Си-

стемы IBM 360, в своей работе [48], опубликованной в 1967 году, предложил фор-

мулу, отражающую зависимость ускорения вычислений, достигаемого на много-

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

ускорение".

 Напомним, что ускорение 5 — это от-

ношение времени T

s

, затрачиваемого на проведение вычислений на однопроцес-

сорной ВС (в варианте наилучшего последовательного алгоритма), ко времени T,

решения той же задачи на параллельной системе (при использовании наилучшего
параллельного алгоритма):

Оговорки относительно алгоритмов решения задачи сделаны, чтобы подчерк-

нуть тот факт, что для последовательного и параллельного решения лучшими мо-

Закон Амдала  4 8 7

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

Проблема рассматривалась Амдалом в следующей постановке (рис. 10.2). Преж-

де всего, объем решаемой задачи с изменением числа процессоров, участвующих
в ее решении-, остается неизменным. Программный код решаемой задачи состоит
из двух частей: последовательной и распараллеливаемой. Обозначим долю опера-
ций, которые должны выполняться последовательно одним из процессоров, через f,
где 0 <=f<= 1 (здесь доля понимается не по числу строк кода, а по числу реально
выполняемых операций). Отсюда доля, приходящаяся на распараллеливаемую
часть программы, составит 1 -f. Крайние случаи в значениях/соответствуют пол-
ностью параллельным (f= 0) и полностью последовательным (f- 1) програм-
мам. Распараллеливаемая часть программы равномерно распределяется по всем
процессорам. ,

Рис. 10.2. К постановке задачи в законе Амдала

С учетом приведенной формулировки имеем;

В результате получаем формулу Амдала, выражающую ускорение, которое мо-

жет быть достигнуто на системе из

 п

 процессоров:

4 8 8 Глава 10. Параллелизм как основа высокопроизводительных вычислений

Формула выражает простую и обладающую большой общностью зависимость.

Характер зависимости ускорения от числа процессоров и доли последовательной

части программы показан на рис. 10.3.

Рис. 10.3. Графики зависимости ускорения от:

 а —

 доли последовательных вычислений;

б —

 числа процессоров

Если устремить число процессоров к бесконечности, то в пределе получаем:

Это означает, что если в программе 10% последовательных операций (то есть

/-0,1), то, сколько бы процессоров ни использовалось, убыстрения работы про-

граммы более чем в десять раз никак ни получить, да и то, 10 — это теоретическая
верхняя оценка самого лучшего случая, когда никаких других отрицательных фак-
торов нет. Следует отметить, что распараллеливание ведет к определенным издерж-

кам, которых нет при последовательном выполнении программы. В качестве при-

мера таких издержек можно упомянуть дополнительные операции, связанные
с распределением программ по процессорам, обмен информацией между процес-
сорами и т. д.

Закон Густафсона

Известную долю оптимизма в оценку, даваемую законом Амдала, вносят исследо-
вания, проведенные уже упоминавшимся Джоном Густафсоном из NASA Ames
Research [115]. Решая на вычислительной системе из 1024 процессоров три боль-
ших задачи, для которых доля последовательного кода/лежала в пределах от 0,4

до 0,8%, он получил значения ускорения по сравнению с однопроцессорным вари-
антом, равные соответственно 1021,1020 и 1016. Согласно закону Амдала для дан-

ного числа процессоров и диапазона f, ускорение не должно было превысить вели-

Закон Густафсона  4 8 9

чины порядка 201. Пытаясь объяснить это явление, Густафсон пришел к выводу,

что причина кроется в

 ИСХОДНОЙ

 предпосылке, лежащей в основе закона Амдала:

увеличение числа процессоров не сопровождается увеличением объема решаемой
задачи. Реальное же поведение пользователей существенно отличается от такого
представления. Обычно, получая в свое распоряжение более мощную систему,
пользователь не стремится сократить время вычислений, а, сохраняя его практи-
чески неизменным, старается пропорционально мощности ВС увеличить объем
решаемой задачи. И тут оказывается, что наращивание общего объема программы
касается главным образом распараллеливаемой части программы. Это ведет к со-
крашению значения f. Примером может служить решение дифференциального
уравнения в частных производных. Если доля последовательного кода составляет

10% для 1000 узловых точек, то для 100 000 точек доля последовательного кода

снизится до 0,1%. Сказанное иллюстрирует рис. 10.4, который отражает тот факт,

что, оставаясь практически неизменной, последовательная часть в общем объеме

увеличенной программы имеет уже меньший удельный вес.

Рис. 10.4. К постановке задачи в законе Густафсона

Было отмечено, что в первом приближении объем работы, которая может быть

произведена параллельно, возрастает линейно с ростом числа процессоров в сис-

теме. Для того чтобы оценить возможность ускорения вычислений, когда объем

4 9 0 Глава 10. Параллелизм как основа высокопроизводительных вычислений

последних увеличивается с ростом количества процессоров в системе (при посто-
янстве общего времени вычислений), Густафсон рекомендует использовать выра-

жение, предложенное Е. Барсисом (Е. Barsis):

Данное выражение известно как

 закон масштабируемого ускорения

 или

 закон

Густафсона

 (иногда его называют также законом Густафсона-Барсиса), В заклю-

чение отметим, что закон Густафсона не противоречит закону Амдала. Различие
состоит лишь в форме утилизации дополнительной мощности ВС, возникающей
при увеличении числа процессоров.

Классификация параллельных

вычислительных систем

Даже краткое перечисление типов современных параллельных вычислительных
систем (ВС) дает понять, что для ориентирования в этом многообразии необходи-
ма четкая система классификации. От ответа на главный вопрос — что заложить
в основу классификации — зависит, насколько конкретная система классификации
помогает разобраться с тем, что представляет собой архитектура ВС и насколько
успешно данная архитектура позволяет решать определенный круг задач. Попыт-
ки систематизировать все множество архитектур параллельных вычислительных
систем предпринимались достаточно давно и длятся по сей день, но к однознач-
ным выводам пока не привели. Исчерпывающий обзор существующих систем клас-
сификации ВС приведен в [5].

Классификация Флинна

Среди всех рассматриваемых систем классификации ВС наибольшее признание

получила классификация, предложенная в 1966 году М. Флинном [99, 100]. В ее
основу положено понятие потока, под которым понимается последовательность
элементов, команд или данных, обрабатываемая процессором. В зависимости от

количества потоков команд и потоков данных Флинн выделяет четыре класса ар-

хитектур: SISD, MISD, SIMD, MIMD.

SISD

SISD

 (Single Instruction Stream/Single Data Stream) — одиночный поток команд

и одиночный поток данных (рис. 10.5,

 а).

 Представителями этого класса являют-

ся, прежде всего, классические фон-неймановские ВМ, где имеется только один

поток команд, команды обрабатываются последовательно и каждая команда ини-

циирует одну операцию с одним потоком данных. То, что для увеличения скорос-
ти обработки команд и скорости выполнения арифметических операций может

применяться конвейерная обработка, не имеет значения, поэтому в класс SISD од-

новременно попадают как ВМ CDC 6600 со скалярными функциональными уст-

ройствами, так и CDC 7600 с конвейерными. Некоторые специалисты считают,

что к SISD-системам можно причислить и векторно-конвейерные ВС, если рассмат-
ривать вектор как неделимый элемент данных для соответствующей команды.