Параллельная задача
Параллельная задача — это задача, в которой отдельные части можно выполнять одновременно на нескольких исполнителях, процессорах или вычислительных устройствах. Главное условие: одновременно выполняемые части не должны зависеть друг от друга.
Обычно сначала выделяют подзадачи и устанавливают связи между ними. Если результат одной подзадачи нужен для начала другой, эти подзадачи нельзя выполнять одновременно. Такие связи рассматриваются в теме зависимостей между задачами. Если зависимостей нет, подзадачи можно распределить между исполнителями.
Как оценивают выполнение
Пусть работа состоит из подзадач длительностью \(t_1,t_2,\ldots,t_n\). При последовательном выполнении общее время равно сумме длительностей. При параллельном выполнении время определяется самым длинным критическим участком с учётом зависимостей. В простейшем случае, когда все подзадачи независимы и исполнителей достаточно, достаточно времени самой долгой подзадачи.
Нужно обработать три независимых файла за \(2\), \(5\) и \(3\) секунды. Один исполнитель потратит \(2+5+3=10\) секунд. Три исполнителя обработают файлы одновременно, поэтому задача завершится через \(\max(2,5,3)=5\) секунд.
Параллельная задача — это не обязательно задача, в которой все действия выполняются одновременно. Часть действий может быть последовательной из-за зависимостей. Расписание параллельных вычислений показывает, в какой момент запускается каждая подзадача.
Три независимые подзадачи выполняются 4, 7 и 2 секунды. Сколько времени потребуется при наличии трёх исполнителей?
Главное
- Параллельная задача содержит подзадачи, которые можно выполнять одновременно.
- Зависимые подзадачи запускаются только после получения нужного результата.
- Для независимых подзадач и достаточного числа исполнителей время равно длительности самой долгой подзадачи.