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

Ярусно-параллельная форма графа (ЯПФ) — деление вершин ориентированного ациклического графа на перенумерованные подмножества <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> — его номером, количество вершин <math>\left| V_i \right |</math> в ярусе — его шириной. Количество ярусов в ЯПФ называется её высотой, а максимальная ширина её ярусов — шириной ЯПФ.

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

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

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

Отрывок, характеризующий Ярусно-параллельная форма графа

Он облокотился на стол с пером в руке, и, очевидно обрадованный случаю быстрее сказать словом всё, что он хотел написать, высказывал свое письмо Ростову.
– Ты видишь ли, дг'уг, – сказал он. – Мы спим, пока не любим. Мы дети пг`axa… а полюбил – и ты Бог, ты чист, как в пег'вый день создания… Это еще кто? Гони его к чог'ту. Некогда! – крикнул он на Лаврушку, который, нисколько не робея, подошел к нему.
– Да кому ж быть? Сами велели. Вахмистр за деньгами пришел.
Денисов сморщился, хотел что то крикнуть и замолчал.
– Сквег'но дело, – проговорил он про себя. – Сколько там денег в кошельке осталось? – спросил он у Ростова.
– Семь новых и три старых.
– Ах,сквег'но! Ну, что стоишь, чучела, пошли вахмистг'а, – крикнул Денисов на Лаврушку.
– Пожалуйста, Денисов, возьми у меня денег, ведь у меня есть, – сказал Ростов краснея.
– Не люблю у своих занимать, не люблю, – проворчал Денисов.
– А ежели ты у меня не возьмешь деньги по товарищески, ты меня обидишь. Право, у меня есть, – повторял Ростов.
– Да нет же.
И Денисов подошел к кровати, чтобы достать из под подушки кошелек.
– Ты куда положил, Ростов?
– Под нижнюю подушку.
– Да нету.
Денисов скинул обе подушки на пол. Кошелька не было.
– Вот чудо то!
– Постой, ты не уронил ли? – сказал Ростов, по одной поднимая подушки и вытрясая их.
Он скинул и отряхнул одеяло. Кошелька не было.
– Уж не забыл ли я? Нет, я еще подумал, что ты точно клад под голову кладешь, – сказал Ростов. – Я тут положил кошелек. Где он? – обратился он к Лаврушке.
– Я не входил. Где положили, там и должен быть.
– Да нет…
– Вы всё так, бросите куда, да и забудете. В карманах то посмотрите.
– Нет, коли бы я не подумал про клад, – сказал Ростов, – а то я помню, что положил.
Лаврушка перерыл всю постель, заглянул под нее, под стол, перерыл всю комнату и остановился посреди комнаты. Денисов молча следил за движениями Лаврушки и, когда Лаврушка удивленно развел руками, говоря, что нигде нет, он оглянулся на Ростова.