Оптимизация параллельных вычислений
В параллельных вычислениях несколько исполнителей могут выполнять задачи одновременно, но их число ограничено. На этой странице разберём, как по длительностям задач находить минимально возможное время работы и строить расписание без конфликтов.
Модель задачи и нижняя оценка
Сначала полезно повторить расписание параллельных вычислений, а также базовые понятия из страницы основы параллельных вычислений. Пусть есть \(n\) независимых задач с длительностями \(t_1,t_2,\ldots,t_n\) и \(m\) одинаковых исполнителей. Каждая задача выполняется одним исполнителем целиком и не прерывается. Исполнитель не может выполнять две задачи одновременно.
Расписание — распределение задач по исполнителям с указанием порядка выполнения. Время расписания \(T\) — момент окончания последней задачи. Требуется минимизировать \(T\).
Для любого расписания существуют две очевидные нижние оценки. Во-первых, самая длинная задача требует не меньше времени \(\max_i t_i\): даже если все остальные задачи выполняются параллельно, эта задача должна закончиться. Во-вторых, суммарная работа равна \(S=\sum_{i=1}^{n}t_i\). Если исполнителей \(m\), то за время \(T\) они могут выполнить не более \(mT\) единиц работы.
Минимальное время не может быть меньше \(\max(\max_i t_i,S/m)\). Если задачи неделимы, дробь \(S/m\) обычно округляют вверх: \(T\ge\left\lceil S/m\right\rceil\). Эта оценка необходима, но не всегда достижима из-за невозможности идеально сбалансировать целые задачи.
Если длительность каждой задачи — целое число, полезно проверять возможное время \(T\) перебором. Для фиксированного \(T\) нужно выяснить, можно ли разложить задачи по \(m\) группам так, чтобы сумма в каждой группе не превышала \(T\). Это уже задача упаковки, поэтому простой подсчёт общей суммы иногда недостаточен.
Жадное распределение и баланс нагрузки
Один из основных практических методов — жадное распределение. Задачи сортируют по убыванию длительности, затем каждую очередную задачу помещают к исполнителю с наименьшей текущей загрузкой. Такой подход называют LPT-эвристикой: сначала идут самые длинные задачи, поэтому они не «застревают» в конце расписания.
- Отсортировать длительности по невозрастанию.
- Для каждой задачи найти исполнителя с минимальной текущей суммой.
- Добавить длительность задачи к его загрузке.
- После распределения взять максимальную загрузку — это длина построенного расписания.
Если исполнителей мало, удобно вести несколько текущих сумм в таблице. После каждой задачи выбирайте минимальную сумму. При равенстве можно выбрать любого из соответствующих исполнителей.
Жадный алгоритм быстро строит хорошее расписание, но без дополнительных условий не всегда даёт абсолютный минимум. Например, при трёх исполнителях задачи длительностей \(8,7,6,5,4,3\) он распределит их как \(8+3\), \(7+4\), \(6+5\), то есть получит время \(11\). В других наборах локально лучший выбор может привести к неоптимальному результату.
Есть 2 исполнителя и задачи длительностей \(7,6,5,4\). Какое расписание строит жадный алгоритм после сортировки по убыванию?
Точный поиск минимального времени
Когда задач немного, минимум можно найти полным перебором. Нужно перебрать все варианты распределения задач по исполнителям, вычислить загрузку каждого и выбрать минимальное значение максимальной загрузки. Если у каждой из \(n\) задач есть \(m\) вариантов исполнителя, число распределений равно \(m^n\), поэтому метод подходит только для небольших входных данных.
Чтобы ускорить перебор, применяют отсечения. Если текущая максимальная загрузка уже не меньше найденного лучшего ответа, ветвь можно не продолжать. Также не стоит пробовать одинаковые по загрузке исполнители: назначение задачи первому или второму из них даёт симметричные варианты.
Для фиксированного \(T\) расписание существует тогда и только тогда, когда задачи можно разбить на \(m\) групп, сумма длительностей каждой из которых не превосходит \(T\). Поэтому поиск минимума можно организовать двоичным поиском по \(T\), если проверка выполнимости монотонна.
Монотонность означает: если задачи можно выполнить за время \(T\), то их можно выполнить и за любое большее время. Нижнюю границу берут из оценки \(T_{\min}^{(0)}\), а верхнюю — например, \(S\), если все задачи выполняет один исполнитель. Затем проверяют середину диапазона и сужают его.
В учебных задачах проверка часто упрощается ограничениями: задачи могут быть уже отсортированы, длительности могут быть маленькими, а число исполнителей — равно двум или трём. Для двух исполнителей достаточно искать разбиение на две группы с максимально близкими суммами. Тогда ответ равен \(\max(x,S-x)\), где \(x\) — сумма первой группы.
Разобранный пример: два исполнителя
Даны четыре независимые задачи длительностью \(2,3,4,7\) и два одинаковых исполнителя. Требуется найти минимальное время.
Суммарная работа равна \(16\), поэтому нижняя оценка по загрузке — \(16/2=8\). Самая длинная задача длится \(7\), значит общая нижняя оценка равна \(8\). Теперь проверим, достижимо ли время 8.
Итак, нижняя оценка 8 не достигается: если задача 7 выполняется у одного исполнителя, остальные задачи дают загрузку 9; если добавить к ней любую задачу, получится больше 8. При времени 9 существует расписание: первый исполнитель выполняет задачи 7 и 2, второй — задачи 4 и 3.
Зависимости, оценки и типичные ошибки
Если задачи зависят друг от друга, простое распределение по суммарным длительностям уже недостаточно. Сначала нужно учитывать зависимости между задачами: задача может начаться только после окончания предшественников. В таком случае расписание строят по уровням или в порядке готовности задач. Задачи без зависимостей можно распределять описанным выше способом.
В некоторых экзаменационных задачах длительность выражается формулой, например количеством операций, числом делителей или временем обработки. Тогда сначала нужно правильно вычислить длительность каждой задачи. Для задач о разложении числа могут понадобиться делимость, простые числа и факторизация. Не следует смешивать время одной задачи с суммарным временем всех задач.
1. Делить сумму длительностей на число исполнителей и сразу считать результат ответом. Это только нижняя оценка. 2. Забывать про самую длинную задачу. 3. Распределять задачи в исходном порядке, хотя эффективнее сначала отсортировать их по убыванию. 4. Игнорировать зависимости. 5. При записи ответа брать сумму загрузок вместо максимальной загрузки. 6. Считать, что исполнитель может начать следующую задачу до окончания предыдущей.
Время расписания — это максимальная, а не суммарная загрузка исполнителей: \(T=\max(L_1,L_2,\ldots,L_m)\).
Алгоритм решения на экзамене
- Выписать длительность каждой задачи и проверить, нет ли зависимостей.
- Посчитать \(S\) и найти \(t_{\max}\).
- Получить нижнюю оценку \(L=\max(t_{\max},\lceil S/m\rceil)\).
- Попробовать построить расписание с помощью сортировки по убыванию и распределения к наименее загруженному исполнителю.
- Если нужен строгий минимум, проверить значения времени от \(L\) вверх или применить двоичный поиск с проверкой группировки.
- Ответом назвать максимальную загрузку, а не сумму и не среднее.
Быстрая проверка
Итоги
- Минимальное время не меньше \(\max(t_{\max},\lceil S/m\rceil)\).
- Время расписания равно максимальной загрузке исполнителя.
- Для хорошего быстрого решения сортируют задачи по убыванию и добавляют каждую к наименее загруженному исполнителю.
- Для строгого минимума используют полный перебор, проверку разбиения или двоичный поиск по времени.
- Зависимости между задачами необходимо учитывать отдельно: доступна только задача, для которой завершены все предшественники.