Параллелизм

Параллелизм, конкуррентность (concurrency) характеристика параллельного алгоритма или расчёта (в смысле процесса исполнения параллельной программы).

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

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

Кроме моментальной, выделяют максимальную и среднюю степени параллелизма. Максимальная степень, как правило, меньше общего числа задач по причине существования между ними взаимных зависимостей.

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

— Ю.Т.