Оценка эффективности параллельных вычислений Комышев Е. Г. гр

Ускорение Ускорение – это отношение времени последовательного к времени параллельного выполнения программы.

Метрика Метрика эффективности (efficiency) - показывает, насколько хорошо программа использует вычислительные ресурсы системы.

Пример 53-кратное ускорение на 64 ядрах даёт эффективность в 82.8% (53/64 = 0.828) => каждое ядро простаивает около 17% времени => каждое ядро простаивает около 17% времени

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

Оценка максимального достижимого параллелизма Закон Амдала Закон Густафсона

Закон Амдала W = Wск + Wпр, где W общее число операций в задаче, Wпр число операций, которые можно выполнять параллельно, а Wcк число скалярных (нераспараллеливаемых) операций. a = Wск /W удельный вес скалярных операций. Ускорение зависит от потенциального параллелизма задачи и числа ядер n. Предельное ускорение определяется свойствами задачи.

Пример 1) если 95% времени последовательного выполнения может выполняться параллельно на 8 ядрах, то оценочное ускорение, согласно закону Амдала, составит около 6x (1 / ( /8) = 5.925) 2) возьмем a = 0,2 (что является реальным значением), тогда ускорение не может превосходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи.

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

Закон Густафсона масштабируемое ускорение s – процент времени последовательного выполнения в параллельном приложении для указанного размера набора данных. + берёт в расчёт рост объёма данных в пропорции к росту количества ядер и рассчитывает (верхнюю границу) ускорения работы приложения, как если бы больший объём данных мог быть обработан последовательно

Пример Eсли 1% времени работы на 32 ядрах выполняется последовательно, то ускорение выполнения такого приложения на том же наборе данных по сравнению с выполнением на одном ядре с одним потоком равно:

Сравнение Закон Амдала: процент последовательного выполнения равен 1%, => 1/( (0.99/32)) = 24.43x – плохой результат. процент последовательного выполнения равен 1%, => 1/( (0.99/32)) = 24.43x – плохой результат. - оценён для выполнения на 32 ядрах Если код идеально масштабируемый и объём данных увеличивается соответственно количеству ядер, то процент может остаться прежним.

Сравнение Пусть общее время выполнения параллельного приложения составляет 1040 секунд на 32 ядрах. => 1% последовательного времени = 10.4 сек (параллельное время)*32(ядра)+10.4 = секунд. Непараллельное время (10.4 секунды) составляет 0.032% общего времени работы. Учитывая результат, закон Амдала даёт ускорение в 1/( ( /32)) = x.

Выводы Для использования закон Густафсона необходимо знать процент последовательного времени при параллельном выполнении => эта формула обычно используется для расчёта ускорения масштабируемого параллельного выполнения, по отношению к последовательному выполнению задачи того же размера. Cтрогое использование данных о выполнении программы в формуле закона Амдала даёт гораздо более пессимистическую оценку, чем формула масштабируемого ускорения.

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

Спасибо за внимание