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

Решение.

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

Начальный момент обозначим 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 = 36 мс. Его нижнюю границу задаёт цепочка 101 → 103 → 105 → 107 → 108:
15 + 3 + 15 + 1 + 2 = 36.
Самое раннее расписание достигает этой границы. Разрешено сдвигать отдельные процессы, пока не нарушены зависимости и общий срок T. Минимальное время всей системы не требует самого раннего запуска абсолютно каждой строки.

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

Обоснуем верхнюю границу длительности. Минимальное время всей системы 36 мс. Две параллельные работы слева возможны либо у {101,102}, либо у 105 вместе с последовательными 104,106. Эти стадии разделяет 103. В первой стадии 101 заканчивается не позднее 36−3−15−1−2=15, а две работы справа возможны лишь после 8 мс процесса 109. Поэтому здесь не более 7 мс. Вторая стадия начинается не раньше 15+3=18. Справа возможны пары {110,111}, {110,113}, {112,113}. Если непрерывный интервал включает 111, то 111 заканчивается не позднее 36−13=23 из-за последующего 112. После 111 второй параллельный процесс может обеспечивать только 113 длительностью 8 мс; без разрыва он должен стартовать в момент окончания 111. Поэтому такой интервал заканчивается не позднее 23+8=31 и длится не более 31−18=13 мс. Если 111 в интервал не попадает, то на всём интервале нужен 113, что даёт не более 8 мс. Наибольшая из полученных границ — 13 мс.

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

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

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

Ответ: 13.