Balancing Report

Тезисы доклада

Допустим, у нас есть задача, совершенно точно распараллеливаемая, например, вычисление функции в цикле:

for i := 1 to n do
    F(i);

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

Есть два подхода к балансировке загрузки: статическая и динамическая балансировка.

Если бы мощность каждого компьютера и время вычисления каждой задачи были заранее известны, то статическая балансировка явилась бы оптимальной стратегией. Этапы:
1: решается эквивалент задачи укладки рюкзака (NP-полная задача, но есть очень хорошие приближенные методы) для получения оптимальной карты загрузки;
2: по составленной карте загрузок хост-компьютер раздает задачи дочерним компьютерам;
3: после окончания работы дочерние компьютеры посылают результаты хост-компьютеру.

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

Будут рассмотрены следующие стратегии:
- равномерная декомпозиция;
- экспоненциальная декомпозиция;
- диффузный метод.

Обозначения:
U - множество задач;
N - количество компьютеров (процессоров)

Равномерная декомпозиция (централизованная балансировка)
1) U разбивается на K (>N) множеств wk;
2) компьютер Pi принимает от хост-компьютера задачи первого из нераспределенных множеств wk;
3) после завершения обработки wk компьютер Pi посылает результаты хост-компьютеру;
4) если обработаны не все wk, то goto 2);
Не подходит, если разница в мощностях компьютеров или в вычислительных затратах отдельных задач велика.

Экспоненциальная декомпозиция (централизованная балансировка)
1) шаг итерации k = 1;
2) если обработаны не все задачи из U, то хост-компьютер выделяет среди оставшихся Zk задач множество Uk: |Uk| = Zk/p, p - коэффициент декомпозиции;
3) Uk разбивается на множества wkj, j=1..N;
4) компьютер Pi принимает от хост-компьютера задачи первого из нераспределенных множеств wkj;
5) после завершения обработки wkj компьютер Pi посылает результаты хост-компьютеру;
6) если обработаны не все wkj, то goto 4);
7) если не все задачи из U обработаны, то k = k+1, Zk = Zk * (1 - p-1), goto 2).

Диффузный метод (децентрализованная балансировка)
1) U разбивается на N множеств wi;
2) компьютер Pi принимает от хост-компьютера задачи из wi;
3) после завершения wi компьютер Pi посылает результаты хост-компьютеру;
4) Pi посылает запрос некоторому компьютеру Pj, если Pj имеет необработанные задачи, то Pi забирает у него 1/p из них (чаще всего p = 2), посылает сообщение хост-компьютеру об этом факте, goto 3);
5) хост-компьютер после получения решения всех задач посылает компьютерам сообщение о завершении работы.
Нужно принимать во внимание следующее:
- активный обмен сообщениями между компьютерами может затормозить работу;
- могут возникнуть ситуации соперничества, когда несколько компьютеров пытаются украсть задачи с одного компьютера;
- чтобы минимизировать время простоя компьютера, когда он все выполнил и ожидает ответ от другого компьютера, стоит посылать запрос о количестве задач чуть раньше, чем все задачи на этом компьютере будут решены (в таком случае необходим механизм оценки работы);
- целесообразно ввести некоторые более сложные оценки загруженности - не количество нерешенных задач, а, например, оценочное время на решение или отношение мощности к объему задач. Тогда компьютер может воровать задачи только у того, у кого загруженность меньше.

Список литературы:

[1] Карпенко А.П., Федорук В.Г., Федорук Е.В. "Исследование эффективности балансировки загрузки многопроцессорной системы при распараллеливании одного класса вычислительных задач", 2007, link
[2] J. Watts "A Practical Approach to Dynamic Load Balancing", 1995, link
[3] P. Liu, C.-H. Yang "Locality-Preserving Dynamic Load Balancing for Data-Parallel Applications on Distributed-Memory Multiprocessors", link

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License