Диаграмма Ганта и планирование

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 7 · страница 7.2
Диаграмма Ганта и планирование
Как распределить задачи между процессорами, чтобы всё выполнилось быстрее? Разбираем диаграмму Ганта, конвейер, зависимости задач и закон Амдала — с 50 задачами из ЕГЭ №22.
Диаграмма Ганта
— это визуальный способ показать, какой процессор что делает в каждый момент времени.
На ЕГЭ №22 встречаются задачи на планирование процессов, конвейерную обработку, графы зависимостей и закон Амдала. Эта страница научит решать каждый тип.
ФГОС · углублённый
ЕГЭ · № 22
01
Что такое диаграмма Ганта?
Визуализация расписания выполнения задач на процессорах
ЕГЭ · № 22
Определение
Диаграмма Ганта
— это горизонтальная временна́я шкала, где каждая строка представляет один процессор (или ресурс), а цветные блоки показывают, какая задача выполняется в каждый момент времени.
Простой пример
Допустим, есть 3 независимых процесса:
A = 5 с
,
B = 3 с
,
C = 4 с
, и 2 процессора.
Вариант 1:
P1 = {A(5), C(4)} = 9 с, P2 = {B(3)} = 3 с. Общее время =
9 с
.
Вариант 2:
P1 = {A(5)} = 5 с, P2 = {B(3), C(4)} = 7 с. Общее время =
7 с
.
Вариант 3:
P1 = {A(5), B(3)} = 8 с, P2 = {C(4)} = 4 с. Общее время =
8 с
.
Правило
Оптимальное расписание минимизирует
максимальное
время загрузки любого процессора (makespan).
Нижняя оценка (lower bound)
Минимально возможное время не может быть меньше:
⌈Сумма всех времён / N⌉
— если бы загрузка была идеально равномерной
max(время одного процесса)
— самый длинный процесс нельзя разделить
В нашем примере: ⌈12/2⌉ = 6, max = 5. Нижняя оценка = max(6, 5) =
6
. Но достичь 6 не удалось — лучший вариант = 7.
Алгоритм решения
1. Посчитайте сумму всех времён и нижнюю оценку.
2. Попробуйте распределить задачи так, чтобы загрузка была максимально равномерной.
3. Начинайте с самых длинных процессов — их сложнее «пристроить».
4. Проверьте: если makespan = нижней оценке, это точно оптимум.
Жадный алгоритм (LPT — Longest Processing Time first)
Отсортируйте процессы по убыванию времени. Каждый следующий процесс назначайте на тот процессор, который освободится раньше всего. Это не всегда даёт оптимум, но обычно близко к нему.
P1:
P2:
A (5 с)
B (3 с)
C (4 с)
0
2
4
6
8 с
P1 = {A} = 5 с, P2 = {B, C} = 7 с → makespan = 7 с
Рис. 1.
Диаграмма Ганта: оптимальное расписание для A(5), B(3), C(4) на 2 процессорах
02
Конвейерная обработка
Как ускорить обработку, разбив задачу на стадии
ЕГЭ · № 22
Идея конвейера
Вместо того чтобы обрабатывать каждую команду целиком и только потом брать следующую, мы разбиваем обработку на
стадии
. Пока одна команда проходит стадию 2, следующая уже на стадии 1.
Аналогия: конвейер на заводе. Пока одна машина красится, другая собирается, третьая проходит контроль качества.
Ключевая формула
Формула конвейера
T = Σtᵢ + (n − 1) · max(tᵢ)
Где:
Σtᵢ
— сумма времён всех стадий (время прохождения первой команды)
max(tᵢ)
— время самой медленной стадии («узкое место»)
n
— количество команд
Почему именно так?
Первая команда должна пройти все стадии последовательно: это занимает
Σtᵢ
. После этого каждая следующая команда выходит с интервалом
max(tᵢ)
— потому что конвейер не может выпускать команды чаще, чем работает самая медленная стадия.
Пример
Конвейер из 3 стадий: 2 нс, 4 нс, 3 нс. Обработать 8 команд.
Σtᵢ = 2 + 4 + 3 =
9 нс
(первая команда)
max(tᵢ) =
4 нс
(стадия 2 — узкое место)
Ещё 7 команд: 7 × 4 =
28 нс
Итого: 9 + 28 =
37 нс
Сравнение с последовательным выполнением
Без конвейера: 8 команд × (2+4+3) = 8 × 9 =
72 нс
.
С конвейером:
37 нс
. Ускорение: 72/37 ≈
1.95 раза
.
Чем больше команд, тем ближе ускорение к числу стадий (но никогда не превышает его).
Частный случай: все стадии одинаковые
Если все
k
стадий длятся
t
нс, формула упрощается:
T = (k + n − 1) · t
Пример: 5 стадий по 1 нс, 100 команд → T = (5 + 100 − 1) × 1 =
104 нс
.
Обратная задача
«Сколько команд обработается за T нс?» — выразите n из формулы:
n = (T − Σtᵢ) / max(tᵢ) + 1
(округлить вниз)
03
Зависимости между задачами
Когда задачи не могут выполняться в произвольном порядке
ЕГЭ · № 22
Граф зависимостей (DAG)
Часто задачи связаны: задача B не может начаться, пока не завершится задача A. Это описывается
ориентированным ациклическим графом
(DAG).
A → B
означает: B зависит от A, B стартует не раньше, чем A завершится.
Критический путь
Критический путь
— самый длинный путь в графе от начала до конца. Он определяет
минимальное
время выполнения всего проекта, даже если у нас бесконечно много процессоров.
Алгоритм нахождения критического пути
1. Для каждой задачи вычислите
самое раннее время старта
:
start(X) = max(finish(Y) для всех Y → X)
finish(X) = start(X) + время(X)
2. Для начальных задач (без зависимостей): start = 0.
3. Ответ = max(finish(X) для всех X).
Пример
Задачи: A(3), B(2), C(4), D(5), E(2). Зависимости: A→C, B→D, C→E, D→E.
A(3)
B(2)
C(4)
D(5)
E(2)
Рис. 2.
Граф зависимостей: A→C→E и B→D→E
Решение:
A: start=0, finish=3
B: start=0, finish=2
C: start=3 (ждёт A), finish=3+4=7
D: start=2 (ждёт B), finish=2+5=7
E: start=max(7,7)=7 (ждёт C и D), finish=7+2=
9
Критический путь: A→C→E = 3+4+2 = 9 (или B→D→E = 2+5+2 = 9). Оба пути одинаковой длины!
Типичная ошибка
Нельзя просто сложить все времена! Задачи на разных ветках выполняются
параллельно
. Сумма всех времён = 3+2+4+5+2 = 16, но ответ = 9.
04
Закон Амдала
Почему бесконечное число ядер не даёт бесконечного ускорения
ЕГЭ · № 22
Формула
Закон Амдала
S = 1 / ((1 − p) + p / N)
p
— доля параллельного кода (от 0 до 1)
N
— число процессоров
S
— ускорение (во сколько раз быстрее)
Смысл
Часть программы
(1 − p)
— последовательная, её нельзя ускорить никаким числом ядер. Она всегда выполняется за своё время. Параллельная часть
p
ускоряется в
N
раз.
Примеры
p (паралл.)
N ядер
Ускорение S
Комментарий
80%
4
2.5
Из 4 ядер выжали 2.5×
90%
10
5.3
10 ядер → только 5.3×
99%
100
≈50
100 ядер → только 50×
50%
1000
≈2
1000 ядер, а ускорение всего 2×
Теоретический предел
При N → ∞:
S_max = 1 / (1 − p)
Если 90% кода параллельно, максимальное ускорение = 1/0.1 =
10 раз
, даже с миллионом ядер.
Обратная задача: сколько ядер нужно?
Дано: ускорение S, доля p. Найти N.
N = p / (1/S − (1−p))
Пример: p=0.9, S=4. N = 0.9 / (0.25 − 0.1) = 0.9/0.15 =
6 ядер
.
05
Стратегия решения ЕГЭ №22
Четыре типа задач и алгоритм для каждого
Тип 1: Распределение независимых процессов
Алгоритм
1. Найдите сумму всех времён и нижнюю оценку ⌈сумма/N⌉.
2. Отсортируйте процессы по убыванию.
3. Распределяйте, начиная с самых длинных, на наименее загруженный процессор.
4. Ответ = makespan (максимальная загрузка).
Тип 2: Конвейер
Алгоритм
1. Найдите Σtᵢ (сумма стадий) и max(tᵢ) (узкое место).
2. Подставьте в формулу: T = Σtᵢ + (n−1)·max(tᵢ).
3. Для обратной задачи: n = ⌊(T − Σtᵢ) / max(tᵢ)⌋ + 1.
Тип 3: Зависимости (критический путь)
Алгоритм
1. Нарисуйте граф зависимостей.
2. Для каждой задачи: start = max(finish всех предшественников), finish = start + время.
3. Начальные задачи: start = 0.
4. Ответ = max(finish всех задач).
Тип 4: Закон Амдала
Алгоритм
1. Определите p (доля параллельного кода) и N (число ядер).
2. Подставьте: S