Задание EGEINFA3580C: Параллельные вычисления

Решение.

В приложенной таблице 12 процессов. Первый столбец содержит их идентификаторы, второй — длительности в миллисекундах, третий — идентификаторы всех необходимых предшественников. Ноль в третьем столбце означает отсутствие предшественников. Типовой пример из условия не заменяет данные файла.

Начальный момент обозначим 0. Пусть d(B) — длительность процесса B, S(B) — время его начала, F(B) — время окончания. Процесс занимает промежуток от S(B) включительно до F(B) не включительно. Его результат доступен уже в момент F(B); следующий процесс может начаться в этот же момент.

Для самого раннего допустимого запуска используем правила:
S(B) = 0, если предшественников нет;
S(B) = max(F(A)), где максимум берётся по всем предшественникам A;
F(B) = S(B) + d(B).
Длительности разных предшественников не складываем: они могут работать параллельно. Но ждать требуется завершения каждого, поэтому выбираем самое позднее окончание. Строки вычисляем после их предшественников, даже если в файле они расположены в другом порядке.

Эти времена достижимы одновременным запуском всех готовых процессов. Раньше запустить очередной процесс нельзя: хотя бы один необходимый результат ещё отсутствует. Последовательно применяя это рассуждение по зависимостям, получаем минимальные времена окончания каждого процесса.

Проверка зависимостей и длительностей. Полный расчёт самого раннего расписания, все времена в мс:

Сначала фиксируем обязательное условие: минимальное время всей системы T = 50 мс. Его нижнюю границу задаёт цепочка 108 → 109 → 110:
17 + 10 + 23 = 50.
Самое раннее расписание достигает этой границы. Разрешено сдвигать отдельные процессы, пока не нарушены зависимости и общий срок T. Минимальное время всей системы не требует самого раннего запуска абсолютно каждой строки.

Разделим граф на независимые компоненты. Процессы 101–107 дают не более 3 одновременных работ. Процессы 108–112 дают не более 2 одновременных работ. В первой компоненте возможны только тройки {102, 103, 107} и {102, 105, 106}. Во второй после 108 идут две последовательные ветви 109 → 110 и 111 → 112, каждая даёт не более одного активного процесса. Поэтому во всей системе одновременно может работать не более 5 процессов. Ниже построено расписание, где это число достигается.

Обоснуем верхнюю границу длительности. Минимальное время всей системы равно 50 мс. Для пяти параллельных процессов в правой компоненте должны закончиться 17 мс процесса 108, так что интервал начинается не раньше 17. В левой компоненте тройки только {102,103,107} и {102,105,106}; их разделяет 104. В первой тройке 103 должен закончиться не позднее 50−10−14=26, иначе последовательные 104 и 106 не успеют к 50. Поэтому первая стадия даёт не более 26−17=9 мс. Во второй тройке процесс 105 длится только 4 мс. Максимум этих границ равен 9 мс.

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

На всём промежутке [17; 26) одновременно работают 5 процессов. При завершении одного процесса другой может сразу занять его место; разрыва параллельной работы нет:

Длина промежутка 26 − 17 = 9 мс. Она совпадает с доказанной верхней границей. Последний процесс заканчивается в момент 50 мс, поэтому требование минимального общего времени также выполнено.

Ответ: 9.