Оценка времени выполнения

Время выполнения последовательного алгоритма

Время выполнения последовательной части параллельного алгоритма

Время выполнения параллельной части алгоритма на p процессорах

Время выполнения всего параллельного алгоритма

Коэффициент ускорения и эффективность

Ускорение

Эффективность

Время выполнения на паракомпьютере

Оптимальное количество процессоров

	kå	T1		1
		pTp		( p 1) 1

Графики зависимостей

Примеры закона Амдала

Централизованная схема вычислений

Симметричная мультипроцессорная система

И другие суперкомпьютеры

Векторные, конвейерные процессоры

Обмен данными

Централизованная схема

Главный процессор раздает рабочим задачу

Рабочие выполняют задачу и возвращают результат главному процессору

Главный процессор – узкое место – существенно последовательная часть алгоритма

Главный процессор в один момент времени может обработать только данные с одного рабочего

Главный процессор (master)

Рабочий

процессор

Рабочий

процессор

SMP система

Шина не может передавать данные от нескольких процессоров одновременно

Шина – существенно последовательная часть

Конвейер

Пока конвейер не заполнен параллельной обработки нет

Заполнение конвейера – существенно последовательная часть алгоритма

Prefetch

Декодирование

сложение

Сохранение

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

Другая формулировка закона Амдала

Пусть параллельный алгоритм выполняется за время Tp

Пусть β – доля существенно последовательных операций параллельного алгоритма, тогда (1- β) – доля алгоритма, которая выполняется параллельно на p процессорах

Оценка времени для закона Густафсона

Время параллельной обработки

Время последовательной обработки (параллельная часть выполняется в p раз медленнее)

Ускорение

Получили линейную масштабируемость

Связь или противоречие?

Используются разные параметры

Амдал – доля последовательных операций последовательного алгоритма

Густафсон – доля последовательных операций параллельного алгоритма

Связь между параметрами

Доля последовательных вычислений зависит от количества процессоров и объема данных с которыми работает алгоритм!

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

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