Жадный планировщик, оценка Брента и закон Амдала

Если ты знаешь, почему жадное расписание укладывается в T₁/p + T∞ и чем закон Амдала отличается от закона Густафсона, листай до «Теперь сам».

Как думаешь, что выбрать

Две программы одинаковы по работе: T₁ = 10⁹ операций. У первой глубина 10³, у второй 10⁶. Машина - 1000 ядер. Насколько первая программа будет быстрее второй?

Ответь себе до чтения. Глубины различаются в тысячу раз, и хочется ответить «в тысячу». Но на тысяче ядер время первой упирается в работу: 10⁹ / 10³ = 10⁶, и глубина 10³ на этом фоне незаметна. Время второй - где-то между 10⁶ и 10⁶ + 10⁶. Разница - самое большее вдвое, а не в тысячу раз. Где глубина решает, а где нет, - то, ради чего нужна оценка Брента.

На что это похоже

Диспетчер такси, у которого правило одно: если машина свободна и есть заказ, который можно выполнять, - отдать его. Диспетчер не планирует день наперёд и не держит машину «на всякий случай». Такой диспетчер иногда ошибается: отдаёт заказ, который мог подождать, и потом важному заказу не хватает машины. Но ошибается не сильно: простаивать машины могут, только когда заказов меньше, чем машин, - а это бывает, лишь пока идёт самая длинная цепочка «этот заказ ждёт тот».

Механизм: полные и неполные шаги

Возьмём граф из операций единичной длины и разделим шаги жадного исполнения на два вида.

Полный шаг - все p процессоров заняты. На нём делается p единиц работы, поэтому полных шагов не больше T₁ / p.

Неполный шаг - кто-то простаивает. Жадный планировщик не держит процессор свободным при готовой задаче, значит, на неполном шаге выполняются ВСЕ готовые операции. Среди них обязательно первая операция самой длинной оставшейся цепочки: всё, от чего она зависит, уже сделано, иначе цепочка была бы длиннее. Значит, каждый неполный шаг укорачивает оставшуюся глубину на единицу, и неполных шагов не больше T∞.

Итого Tₚ ≤ T₁ / p + T∞. Точнее, у Херлихи и Шавита: T₁ / p + T∞ · (p − 1) / p: на неполном шаге хотя бы один процессор занят полезной работой, поэтому простаивающих на нём не больше p − 1. Для задач разной длительности, как в сборке проекта, та же граница известна со времён Грэхема (1966).

Правило

Жадное расписание на p процессорах укладывается в Tₚ ≤ T₁ / p + T∞ (оценка Брента). Нижняя граница для любого расписания - max(T₁ / p, T∞), поэтому жадное не хуже лучшего больше чем вдвое. Если параллелизм T₁ / T∞ намного больше p, слагаемое T∞ пренебрежимо и ускорение почти линейное: Tₚ ≈ T₁ / p.

Разбор: сборка на 1, 2, 3, 4 и 8 машинах

Возьмём сборку из прошлого урока: работа 44, глубина 22. Исполним её жадно: в каждый момент свободная машина берёт первую по списку задачу, у которой всё готово. Время идёт событиями - от одного окончания задачи до следующего, - поэтому цикл крутится по числу задач, а не по минутам.

zadachi = [
    ["скачать", 4, []],
    ["ядро", 9, ["скачать"]],
    ["драйверы", 6, ["скачать"]],
    ["утилиты", 3, ["скачать"]],
    ["модули", 7, ["ядро"]],
    ["тесты ядра", 5, ["ядро", "драйверы"]],
    ["документация", 8, []],
    ["образ", 2, ["модули", "тесты ядра", "утилиты"]],
]

def zhadno(zadachi, p):
    # свободная машина сразу берёт первую готовую задачу по списку
    gotovo = {}
    idut = []
    nachata = {}
    t = 0
    while len(gotovo) < len(zadachi):
        for imya, dlit, zavisit in zadachi:
            if len(idut) == p:
                break
            if imya in nachata:
                continue
            mozhno = True
            for z in zavisit:
                if z not in gotovo:
                    mozhno = False
            if mozhno:
                nachata[imya] = t
                idut.append([t + dlit, imya])
        t = idut[0][0]
        for e in idut:
            if e[0] < t:
                t = e[0]
        ostalis = []
        for e in idut:
            if e[0] == t:
                gotovo[e[1]] = t
            else:
                ostalis.append(e)
        idut = ostalis
    return t

rabota = 44
glubina = 22
for p in [1, 2, 3, 4, 8]:
    tp = zhadno(zadachi, p)
    niz = max(rabota / p, glubina * 1.0)
    verh = rabota / p + glubina * (p - 1) / p
    print(p, tp, round(niz, 1), round(verh, 1))

1 44 44.0 44.0
2 23 22.0 33.0
3 22 22.0 29.3
4 22 22.0 27.5
8 22 22.0 24.8

Столбцы: машин, время жадного расписания, нижняя граница, верхняя. Уже с трёх машин сборка идёт 22 минуты - ровно глубина, дальше ускорять нечего. На двух машинах жадное расписание дало 23 при нижней границе 22: в момент 13 машина взяла «утилиты», которые могли подождать, а «модули» с критического пути начались на минуту позже. Это и есть типичная ошибка жадного диспетчера - небольшая и ограниченная верхней границей 33.

Разбор: закон Амдала и закон Густафсона

Пусть в программе доля f выполняется строго последовательно (чтение входа, финальная сводка), а остальное идеально делится между p ядрами. Тогда время на p ядрах - f + (1 − f) / p от исходного, и ускорение

S(p) = 1 / (f + (1 − f) / p)  →  1 / f   при p → ∞

Это закон Амдала (1967): последовательная доля - часть глубины, и её никакие ядра не ускорят. Густафсон (1988) заметил, что с ростом машины обычно растёт и задача: на тысяче ядер решают не ту же задачу быстрее, а задачу в тысячу раз больше за то же время. Если последовательная часть при этом не растёт, ускорение «по объёму» - f + (1 − f) · p.

f = 0.05
print("ядер  Амдал  Густафсон")
for p in [1, 2, 4, 8, 16, 64, 256, 1024]:
    amdal = 1 / (f + (1 - f) / p)
    gustafson = f + (1 - f) * p
    print(p, round(amdal, 2), round(gustafson, 2))
print("предел Амдала", round(1 / f, 1))

ядер  Амдал  Густафсон
1 1.0 1.0
2 1.9 1.95
4 3.48 3.85
8 5.93 7.65
16 9.14 15.25
64 15.42 60.85
256 18.62 243.25
1024 19.64 972.85
предел Амдала 20.0

Пять процентов последовательного кода - и выше двадцатикратного ускорения не подняться: на 64 ядрах уже 15,4, на 1024 - 19,6. Густафсон понимает те же 5% иначе - как долю последовательной части во времени работы на большой машине, которая не растёт вместе с задачей, - и получает почти линейный рост. Противоречия нет: это ответы на разные вопросы. Амдал - «во сколько раз быстрее решится ЭТА задача», Густафсон - «во сколько раз больше задачу я решу за то же время». Перед покупкой ядер полезно понять, какой из двух вопросов твой.

Что ломается без этого

Ставка на число ядер. Сервис перевели с 8 на 64 ядра и получили прирост всего на 11%. Профиль показал: половина времени уходит на разбор запроса в одном потоке. По Амдалу с f = 0,5 предел - 2, на 8 ядрах ускорение уже 1,78, на 64 - 1,97: до предела оставалось совсем немного.

Ручное расписание вместо жадного. Задачи раскладывают по машинам заранее, «поровну по числу». Одна машина получает длинные задачи и работает вдвое дольше остальных, которые давно простаивают. Жадный планировщик - пул задач, из которого свободный исполнитель берёт следующую, - не держит исполнителя свободным, пока есть готовая задача: простой возможен, только когда готовых задач меньше, чем исполнителей.

Зачем это в работе

Пул потоков в Java (ForkJoinPool), планировщик Go и Tokio в Rust, concurrent.futures в Python - все устроены жадно: свободный исполнитель берёт готовую задачу. Оценка Брента объясняет, почему этого хватает: если задач в запасе много больше, чем исполнителей, ускорение близко к линейному без всякого планирования наперёд.

Закон Амдала - первое, что считают при оценке «стоит ли распараллеливать»: замерить долю времени, которая останется последовательной, и посчитать 1 / f. Если выходит 3, нет смысла заказывать сервер на сто ядер.

Теперь сам

1. T₁ = 10⁶, T∞ = 10³. В каких пределах время жадного расписания на 100 ядрах? Почти ли линейно ускорение?
2. Программа на 16 ядрах ускорилась в 8 раз. Какую долю f это означает по Амдалу, и каким будет предел?
3. Почему неполных шагов жадного расписания не больше T∞, а не, скажем, T∞ · p?