На этом шаге мы рассмотрим балансировку загрузки процессоров и ее виды.
Балансировка нагрузки применяется для оптимизации выполнения распределенных (параллельных) вычислений с помощью распределенной (параллельной) вычислительной системы (ВС). Балансировка нагрузки предполагает равномерную нагрузку вычислительных узлов (процессора многопроцессорной ЭВМ или компьютера в сети). При появлении новых заданий программное обеспечение, реализующее балансировку, должно принять решение о том, где (на каком вычислительном узле) следует выполнять вычисления, связанные с этим новым заданием. Кроме того, балансировка предполагает перенос части вычислений с наиболее загруженных вычислительных узлов на менее загруженные узлы.
Будем считать, что распределенное приложение представляет собой совокупность логических процессов, которые взаимодействуют друг с другом, посылая друг другу сообщения. Логические процессы распределяются по разным вычислительным узлам и могут функционировать параллельно.
При распределении логических процессоров по вычислительным узлам их стараются распределять так, чтобы загрузка вычислительных узлов была равномерной. Однако при выполнении распределенного приложения возникает конфликт между сбалансированным распределением объектов по процессорам и низкой скоростью обменов сообщениями между процессорами. Если логические процессы распределены между процессорами таким образом, что издержки на коммуникацию между ними сведены к нулю, то некоторые процессоры (компьютеры) могут простаивать, в то время как остальные будут перегружены. В другом случае, "хорошо сбалансированная" система потребует больших затрат на коммуникацию. Следовательно, стратегия балансировки должна быть таковой, чтобы вычислительные узлы были загружены достаточно равномерно, но и коммуникационная среда не должна быть перегружена.
Проблема балансировки вычислительной нагрузки распределённого приложения возникает по той причине, что:
- структура распределенного приложения неоднородна, различные логические процессы требуют различных вычислительных мощностей;
- структура вычислительного комплекса (например, кластера) также неоднородна, то есть разные вычислительные узлы обладают разной производительностью;
- структура межузлового взаимодействия неоднородна, так как линии связи, соединяющие узлы, могут иметь различные характеристики пропускной способности.
Следует различать статическую и динамическую балансировки. Статическая балансировка выполняется до начала выполнения распределенного приложения. Очень часто при распределении логических процессов по процессорам используется опыт предыдущих выполнений, применяются генетические алгоритмы. Однако предварительное размещение логических процессов по процессорам (компьютерам) далеко не всегда эффективно.
Это объясняется тем, что:
- может измениться вычислительная среда, в которой происходит выполнение приложения, какой-либо вычислительный узел может выйти из строя;
- вычислительный узел, на котором выполняется распределенное приложение, занят ещё и другими вычислениями, доля которых со временем может возрасти.
Так или иначе, выигрыш от распределения логических процессов по компьютерам с целью выполнения параллельной обработки становится неэффективным.
Динамическая балансировка предусматривает перераспределение вычислительной нагрузки на узлы во время выполнения приложения. Программное обеспечение, реализующее динамическую балансировку, определяет:
- загрузку вычислительных узлов;
- пропускную способность линий связи;
- частоту обменов сообщениями между логическими процессами распределенного приложения и др.
Цель балансировки загрузки может быть сформулирована следующим образом: исходя из набора задач, включающих вычисления и передачу данных, и сети компьютеров определенной топологии, найти такое распределение задач по компьютерам, которое обеспечивает примерно равную вычислительную загрузку компьютеров и минимальные затраты на передачу данных между ними.
К методам построения параллельных алгоритмов со статической балансировкой загрузки процессоров относятся метод сдваивания, метод геометрического параллелизма и метод конвейерного параллелизма. Динамическая балансировка загрузки процессоров применяется при использовании метода коллективного решения.
На следующем шаге мы рассмотрим метод сдваивания.
