Ярусно-параллельная форма графа

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

Ярусно-параллельная форма графа (ЯПФ) — деление вершин ориентированного ациклического графа на перенумерованные подмножества <math>V_i</math> такие, что, если дуга <math>e</math> идет от вершины <math>v_1 \in V_j</math> к вершине <math>v_2 \in V_k</math>, то обязательно <math>j < k</math>.

Каждое из множеств <math>V_i</math> называется ярусом ЯПФ, <math>i</math> — его номером, количество вершин в ярусе — его шириной. Количество ярусов в ЯПФ называется её высотой, а максимальная ширина её ярусов — шириной ЯПФ.

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

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

Личные инструменты

Served in 0.080 secs.