Ярусно-параллельная форма графа (ЯПФ) — деление вершин ориентированного ациклического графа на перенумерованные подмножества ${\displaystyle V_{i}}$ такие, что, если дуга ${\displaystyle e}$ идет от вершины ${\displaystyle v_{1}\in V_{j}}$ к вершине ${\displaystyle v_{2}\in V_{k}}$ , то обязательно ${\displaystyle j<k}$ .

Каждое из множеств ${\displaystyle V_{i}}$ называется ярусом ЯПФ, ${\displaystyle i}$ — его номером , количество вершин ${\displaystyle \left|V_{i}\right|}$ в ярусе — его шириной . Количество ярусов в ЯПФ называется её высотой , а максимальная ширина её ярусов — шириной ЯПФ .

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

Минимальной высотой всех возможных ЯПФ графа является его критический путь . Построение ЯПФ с высотой, меньшей критического пути, невозможно.

Если в составе яруса могут быть вершины, находящиеся в различных отношениях (например, или , что типично для граф-схем параллельных алгоритмов ), ярус называется сечением, а ЯПФ — множеством сечений. Наличие более одного отношения между вершинами сечения существенно усложняет большинство алгоритмов обработки .

См. также топологическая сортировка .

Примечания