Расписание параллельных вычислений
Расписание параллельных вычислений — это план, который показывает, какой исполнитель, какую тапсырманы и в какой момент выполняет. При составлении расписания учитывают длительность работ и зависимости: задачу нельзя начать, пока не завершены все необходимые предшественники.
Основные элементы
У каждой тапсырма есть длительность \(t_i\). Исполнитель может выполнять только одну тапсырманы одновременно. Если тапсырма \(B\) зависит от тапсырма \(A\), то начало \(B\) должно быть не раньше окончания \(A\). Поэтому расписание можно представить как таблицу или диаграмму времени: по горизонтали откладывают время, а по вертикали — исполнителей.
Здесь \(C_i\) — время окончания тапсырма \(i\), а \(C_{\max}\) — общее время выполнения расписания, или его длина. Хорошим обычно считают расписание с меньшим \(C_{\max}\). Однако простое равномерное распределение работ не всегда возможно: длинная задача или цепочка зависимостей может стать ограничением.
Есть два исполнителя и тапсырма: \(A\) длится 3 минут, \(B\) — 2 минут и зависит от \(A\), \(C\) — 2 минут и не имеет зависимостей. Сначала исполнитель 1 выполняет \(A\) с 0 до 3, а исполнитель 2 — \(C\) с 0 до 2. После завершения \(A\) тапсырма \(B\) выполняется с 3 до 5. Всё расписание занимает 5 минут.
Параллельная тапсырма — это отдельная работа, которую можно выполнять одновременно с другими. Расписание — это уже полный план размещения многих задач по исполнителям. Параллельность не означает, что любую задачу можно запустить в любой момент: зависимости сохраняются.
Тапсырма \(B\) зависит от \(A\). Когда можно начать \(B\)?
Главное
- Расписание указывает исполнителя и время выполнения каждой тапсырма.
- При планировании учитывают длительности, число исполнителей и основы параллельных вычислений, включая возможность одновременной жұмысы.
- Длина расписания определяется формулой \(C_{\max}=\max_i C_i\); зависимости нельзя нарушать.