Зависимость, параллельная программа

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

Наличие зависимости между частями запрещает их одновременное (и вообще произвольное по порядку) исполнение в параллельных (распределённых) вычислениях.

Выявление зависимостей — первый и необходимый шаг при декомпозиции последовательной программы с целью приведения её к параллельной форме.

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

Зависимости в общем подразделяются на зависимости по данным и зависимости по управлению; кроме того, для стадии планирования исполнения (scheduling) выделяют т. наз. зависимости в планировании.

Зависимости по данным

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

• прямая зависимость (она же зависимость по потоку или настоящая; flow dependency, true dependency): существует от приказа (инструкции, команды, кода) П1 к приказу П2, если П1 помещает результат в ячейку памяти (регистр, переменную и под.), которая далее используется как операнд в приказе П2;
• обратная зависимость (anti-dependency): существует от приказа П1 к приказу П2, если приказ П1 использует как операнд ячейку памяти, которая далее используется приказом П2 для записи результата вычисления;
• зависимость по выходу или по выводу (output dependency): существует от приказа П1 к приказу П2, если приказы П1 и П2 пользуются одной и той же ячейкой памяти для сохранения результата своего вычисления.

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

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

Зависимости по управлению

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

— Ю.Т.

Ссылки и примечания

Источники

• Grama, ... Introduction to parallel computing
• Sinnen...