Расписание параллельных вычислений
Расписание параллельных вычислений — это план, который показывает, какой исполнитель, какую задачу и в какой момент выполняет. При составлении расписания учитывают длительность работ и зависимости: задачу нельзя начать, пока не завершены все необходимые предшественники.
Основные элементы
У каждой задачи есть длительность \(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\); зависимости нельзя нарушать.