Декомпозиция, параллельная программа

Декомпозиция (расчёта): процесс разделения последовательного расчёта или алгоритма на элементарные части–задачи (tasks) с целью параллельного исполнения; часть параллелизации.

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

В зависимости от конкретного приложения декомпозиция может производиться во время инициализации программы (статическая декомпозиция), или же задачи могут выделяться во время исполнения программы (динамическая декомпозиция); в этом случае число задач, доступных (предъявляемых) к исполнению, может существенно изменяться за время исполнения. В любой момент исполнения параллельной программы число исполнимых одновременно задач есть верхний предел для доступного (возможного) уровня параллелизма и, таким образом, для числа вычисляющих устройств, которые могут быть полезно задействованы.

В процессе декомпозиции определяются (обнаруживаются) также зависимости между задачами, которые, собственно, и ограничивают сверху достижимый уровень параллелизма.

— Ю.Т.