Глоссарий
1 Граф алгоритма
Граф алгоритма (ГА) — это ориентированный ациклический мультиграф, вершины которого соответствуют операциям алгоритма, а дуги — передаче данных между ними. Вершины ГА могут соединяться несколькими дугами, в частности когда в качестве разных аргументов одной и той же операции используется одна и та же величина. ГА почти всегда является параметризованным графом. В частности, его вид часто зависит от входных данных.
ГА используется как удобное представление алгоритма при исследовании его структуры, ресурса параллелизма, а также других свойств. Его можно рассматривать как параметризованную информационную историю. Он сохраняет её информативность, при это обладая компактностью за счёт параметризации. Разработана методика построения ГА по исходному тексту программ.
См. также: Граф алгоритма
2 Ярусно-параллельная форма графа алгоритма
Ярусно-параллельная форма (ЯПФ) — это представление графа алгоритма, в котором:
- все вершины разбиты на перенумерованные подмножества ярусов,
- начальная вершина каждой дуги расположена на ярусе с номером меньшим, чем номер яруса конечной вершины,
- между вершинами, расположенными на одном ярусе, не может быть дуг.
Высота ЯПФ – это число ярусов. Ширина яруса – число вершин, расположенных на ярусе. Ширина ЯПФ – это максимальная ширина ярусов в ЯПФ. Высота ЯПФ ∼ сложность параллельной реализации алгоритма/программы.
Канонической ярусно-параллельной формой называется ЯПФ, высота которой равна длине критического пути + 1, а все входные вершины расположены на первом ярусе. Для заданного графа его каноническая ЯПФ единственна.
См. также:
