Основы параллельных вычислений
Параллельные вычисления позволяют выполнять несколько независимых задач одновременно на разных исполнителях. В этой теме научимся распределять работы между исполнителями, вычислять время расписания и понимать, когда ускорение ограничено самой длиной задачи.
Модель параллельных вычислений
Пусть есть \(n\) независимых задач с длительностями \(t_1,t_2,\ldots,t_n\) и \(k\) одинаковых исполнителей. Исполнитель может выполнять только одну задачу в каждый момент времени. Если задача уже начата, обычно предполагается, что её не прерывают и не переносят на другого исполнителя.
Параллельная задача — это набор работ, которые можно выполнять одновременно на нескольких исполнителях. Задачи называются независимыми, если начало одной задачи не зависит от окончания другой.
Результат распределения задач называют расписанием. В нём для каждой задачи указано, какой исполнитель её выполняет и в какой момент она начинается. В простейшей модели все исполнители доступны в момент \(0\), передача данных и переключение между задачами не занимают времени.
Время расписания и нижние границы
Время окончания всего набора задач равно моменту, когда завершилась последняя задача. Его называют длиной расписания или временем выполнения \(T\). Для каждого исполнителя складываются длительности назначенных ему задач, а \(T\) равен наибольшей из получившихся сумм.
Здесь \(A_j\) — множество задач, назначенных исполнителю \(j\), а \(S_j\) — его суммарная занятость. Чем меньше максимальная загрузка, тем быстрее расписание.
Для любого расписания справедливо \(T\ge\max(t_1,\ldots,t_n)\): самую длинную задачу нельзя выполнить быстрее её длительности. Кроме того, \(T\ge\frac{t_1+\cdots+t_n}{k}\), потому что исполнители вместе могут выполнить не более \(kT\) единиц работы.
Если сумма длительностей делится на \(k\) и задачи удаётся распределить с одинаковой загрузкой, нижняя граница достигается. Тогда расписание оптимально. Но равенство может быть невозможно: крупные задачи приходится сочетать с мелкими, и один исполнитель может оказаться загружен дольше остальных.
Практический алгоритм распределения
Для небольшого числа задач можно перебрать варианты распределения. На экзамене чаще применяют жадное правило: сортируют задачи по убыванию длительности и каждую следующую задачу назначают исполнителю с наименьшей текущей загрузкой. Такой способ называется правилом «сначала самые длинные».
- Запишите длительности задач и упорядочьте их по убыванию.
- Для каждой задачи найдите исполнителя с минимальной текущей суммой.
- Прибавьте длительность задачи к его загрузке.
- После распределения возьмите максимальную загрузку.
Сначала вычислите нижнюю границу по формуле (2). Затем постройте расписание. Если его длина совпала с нижней границей, улучшить его нельзя: расписание оптимально.
Есть 2 исполнителя и задачи длительностью 8, 7, 4 и 3. Какова нижняя граница времени выполнения?
Разобранный пример
Есть 3 исполнителя и 7 независимых задач длительностью \(9,8,7,6,5,4,3\). Требуется получить как можно меньшее время выполнения.
Сначала найдём нижнюю границу, затем применим жадное распределение.
Получилось расписание длиной 16, но нижняя граница равна 14. Значит, жадное распределение здесь не доказало оптимальность и его можно улучшить. Переберём сочетания: исполнитель 1 получает \(9+5=14\), исполнитель 2 — \(8+6=14\), исполнитель 3 — \(7+4+3=14\).
Время 14 совпадает с нижней границей. Следовательно, это оптимальное расписание: ни один способ не может завершить все задачи раньше 14 единиц времени.
Ограничения и зависимости
Если задачи нельзя начинать произвольно, необходимо учитывать зависимости между задачами. Например, задача B может стартовать только после окончания A. Тогда одной суммы длительностей недостаточно: важна самая длинная цепочка зависимых задач — критический путь.
При наличии зависимостей сначала строят расписание параллельных вычислений с учётом разрешённых порядков. Для полностью независимых задач порядок не важен, поэтому достаточно балансировать загрузку исполнителей. Если некоторые задачи нельзя разделить или одна задача длится дольше всей средней нагрузки, ускорение ограничено.
1. Делить сумму длительностей на число исполнителей и сразу считать ответом: это только нижняя граница. 2. Забывать о самой длинной задаче. 3. Складывать времена всех исполнителей вместо максимального. 4. Распределять задачи поровну по количеству, а не по суммарной длительности. 5. Игнорировать зависимости и запускать задачу до готовности её исходных данных.
Полезно отличать распределение задач от оптимизации параллельных вычислений. Распределение отвечает на вопрос «кто выполняет работу», а оптимизация также учитывает накладные расходы, обмен данными и неравномерность загрузки.
Оценка ускорения
Если все задачи выполнялись последовательно, время равно \(T_1=\sum t_i\). При \(k\) исполнителях время равно \(T_k\). Ускорение показывает, во сколько раз вычисление стало быстрее.
Теоретически ускорение не может быть больше \(k\), потому что имеется только \(k\) исполнителей. На практике оно меньше из-за длинных задач, простоев и зависимостей. Поэтому важно не только число исполнителей, но и возможность равномерно разделить работу.
Для независимых задач: сумма длительностей даёт общий объём работы, максимум загрузок даёт время расписания, а нижняя граница равна максимуму из длительности самой длинной задачи и средней работы на одного исполнителя.
Проверь себя
Кратко
- Независимые задачи можно выполнять одновременно на разных исполнителях.
- Время расписания — максимальная сумма длительностей задач, назначенных одному исполнителю.
- Нижняя граница: \(T\ge\max(\max_i t_i,\sum t_i/k)\).
- Жадное правило: сортировать задачи по убыванию и добавлять каждую к наименее загруженному исполнителю.
- Совпадение времени расписания с нижней границей доказывает оптимальность.
- При зависимостях нужно учитывать порядок запуска и критический путь.