Оценка эффективности алгоритмов

Целью этой серии экспериментов была оценка эффективности алгоритмов при разном числе вычислительных узлов типа (1х1.3). На рис. 5.1 и 5.2 представлены результаты при использовании двух и четырех рабочих станциях соответственно.

Рис 5.1. Результаты экспериментов для системы из двух рабочих станций

Рис 5.2. Результаты экспериментов для системы из четырех рабочих станций

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

Рис 5.3. Результаты экспериментов, полученные при использовании алгоритма Кеннона

36. Закон Амдала

Линейное ускорение считается теоретическим пределом эффективности вычислений на мультипроцессоре. Обоснованием этого свойства параллельной обработки служит закон Амдала. Ключевым моментом закона Амдала является доля последовательной обработкиотносительно полноговремени выполнения параллельной программы, когда в параллельной программе используется единственный процессор. Эта долянезависима от числа процессоров. Пусть f – доля таких вычислений в общем объеме, 0 < f < 1. Максимальное ускорение S, достижимое на вычислительной системе из p процессоров, можно оценить при помощи следующей формулы:

.

Вопрос: может ли существовать ускорение, большее, чем число процессоров (суперлинейное) S_p>p и E_p>1?

Ответ: Нет. Каждый параллельный алгоритм, решая задачу за времяT_p с p процессорами, может в принципе моделироваться последовательным алгоритмом за время T₁=pT_p на единственном процессоре.

Тем не менее, суперлинейное ускорение обнаружено экспериментально при решении нескольких классов задач. Распространено мнение, что суперлинейное ускорение – это результат некорректной методики измерений времен T₁ и T_p. Считается, что одной из возможных причин служит эффект различия в алгоритмах кэширования вследствие различий оборудования и операционных систем.

Неявное предположение в законе Амдала состоит том, что при решении конкретной задачи число шагов вычисления (объем вычислений) в последовательной и параллельной программах одинаков. Существование суперлинейного ускорения легко объясняется при невыполнении этого предположения. Если объемы вычислений последовательной и параллельной программ могут различаться (как это следует из существования суперлинейного ускорения), то закон Амдала характеризует не мультипроцессор, а класс параллельных алгоритмов.

Зако́н Амдала (англ. Amdahl'slaw, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Идейное значение

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

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