Параллельная программа

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

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

Основные различающие качества параллельных программ:

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

Производительность

Производительность параллельных программ зависит от наличия трёх основных источников временны́х потерь:

• необходимые взаимодействия между процессами, которые воплощаются в передачах данных; как правило, самое значительное слагаемое в сумме временных потерь;
• простои, причинами которых могут быть неравномерность загрузки исполняющих устройств, необходимость синхронизации, наличие последовательных компонентов в программе;
• излишние вычисления, необходимость в которых вызывается тем, что наиболее быстрый алгоритм для решаемой задачи может оказаться трудно параллелизуемым или не параллелизуемым вовсе. Разница между объёмом вычислений параллельной программы и лучшей последовательной программы есть объём излишних вычислений. Так, в параллельном воплощении быстрого преобразования Фурье выгоднее — по временным затратам — дублировать вычисления одних и тех же степеней на различных узлах обработки, чем передавать данные между узлами; т. е., необходимы излишние вычисления.

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

Время исполнения: длина отрезка времени между началом параллельного счёта и окончанием работы последнего из исполняющих узлов.

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

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

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

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

Эффективность: отношение ускорения к количеству исполняющих узлов; мера той доли времени, в течение которой исполняющий узел полезно занят. Исполняющие узлы не могут тратить время лишь на вычисления, и идеальное ускорение не достигается. Для идеальной параллельной системы эффективность равна 1.

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

Параллельную систему называют оптимальной по стоимости (cost-optimal), если стоимость решения на параллельной машине растёт в зависимости от объёма входных данных асимптотически одинаково со стоимостью лучшего последовательного решения. Поскольку эффективность есть соотношение последовательной и параллельной стоимостей, то оптимальная по стоимости параллельная система имеет эффективность Θ(1).

— Ю.Т.