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

8.5 Уточнение закона Амдаля – типичная форма ускорения кластера

Рассмотрим теперь формальную модель ускорения многопроцессорной системы MPP архитектуры, предположив, что топология связей в ней представляет решетку процессоров. Такая архитектура наиболее типична для кластерных систем. Проводя аналогии между кристаллической решеткой и решеткой процессоров, можно прийти к выводу, что модель кластера может быть представлена, в первом приближении, как модель Изинга (Модель Изинга — математическая модель статистической физики, предназначенная для описания намагничивания материала).. Такая модель отражает ситуацию, когда узлы решетки процессоров нагружены равномерно, а эффективность связи между узлами отражается величиной «порядка» модели Изинга.

Приведем кратко вывод асимптотической формулы для ускорения кластерной системы, описываемой моделью Изинга. Пусть время работы алгоритма на одном процессе составляет T₁. Разобьем в первом приближении алгоритм на две функциональные части, предположив, что малая часть α является чисто последовательной (выполняется на одном процессоре), а оставшаяся часть (1- α) может быть распараллелена на систему из N процессоров. Тогда время выполнения алгоритма на системе из N процессоров может быть представлена следующим образом:

(1)

В этом случае ускорение

(2)

что соответствует закону Амдаля. В формуле (2) не учтено время, необходимое системе для пересылок данных (взаимодействия) между процессорами (узлами) в решетках кластера. Учет времени, необходимого на эти накладные расходы, когда не совершается никаких вычислений, приводит к трансформации выражения (1):

(3)

где τ_ij – время взаимодействия между i – тым и j – м процессором (узлом)
Естественно, в оптимально сконфигурированной системе нас интересует минимизация последнего члена в (3). Представим его следующим образом:

(4)

где τ₀ – некоторое характерное время (временной масштаб). Все остальные переменные и получающиеся коэффициенты есть суть безразмерные величины. Здесь - функция расстояния между узлами, d – величина, зависящая от характера соединения разных процессоров друг с другом.
Решение такой задачи аналогично рассмотрению фазовых переходов второго рода в решетке из N узлов., в каждом из которых находится «диполь» с осью, перпендикулярной плоскости решетки. Диполь может иметь две противоположные ориентации (в нашем случае это прохождение или не прохождение или не прохождение информации), так что общее число возможных конфигураций диполей в решетке равно 2^N. Эта модель известна в литературе как модель Изинга.
Предполагая, что все процессоры одинаково нагружены, (где v₀, V₀ – скорости передачи сообщения между узлами и соответствующий масштаб), d_ij  d, получаем:

(5)

где β – коэффициент, отражающий архитектуру (диаметр системы), γ – коэффициент, равный отношению производительности узла (процессора) к производительности связи (скорость линка).
Тогда (3) примет вид:
(6)

следовательно ускорение S_N будет равно:

(7)

Исследование зависимости (7) показывает, что S_N имеет максимум (см. рис.). Это означает, что существует некоторое оптимальное количество узлов (процессоров), при котором эффективность кластера оказывается наибольшей. S_N достигает максимума при количестве процессоров:

(8)

Следовательно, оптимальное количество узлов кластера наиболее существенно зависит от диаметра системы и отношения производительности узла к производительности линка. В точке максимума будет наблюдаться приблизительно следующее ускорение:

(8)