Метод половинного деления.

Он используется для разделения домена на части примерно равного размера в отношении объема вычислений и коммуникаций при стремлении минимизировать стоимость коммуникаций, т.е. количество связей, пересекающих границы задачи. Используется подход «разделяй и властвуй». Вначале домен делится на 2 части по 1-му измерению. Затем субдомены, в свою очередь, делятся пополам, и т.д. Заметьте, что эта рекурсивная стратегия дополняет параллельное выполнение самого алгоритма балансировки.

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

Другой вариант бисекции называется несбалансированной бисекцией. В этом случае при делении стремятся получить более «квадратные» субдомены. Вместо автоматического деления пополам рассматривается P-1 разделов, представляющих собой несбалансированные решетки с нагрузкой 1/P и (P-1)/P, 2/P и (P-2)/P и т.д. Выбирается такое разделение, которое оптимизирует «отношение сторон» получаемых субдоменов. Этот метод требует больше вычислений, но позволяет сократить затраты на коммуникации.

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

Решетка рассматривается как граф с N вершинами. Алгоритм вначале вычисляет два «края» графа – т.е. наиболее удаленные друг от друга точки (наиболее удаленные в смысле расстояния на графе, т.е. минимального количества ребер на пути от 1 края к др.). Затем все прочие точки относят к 1 из субдоменов, исходя из их близости к «краям».

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

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

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

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