Cтраница 2
Система операций описывается следующим образом. UN операций, которые необходимо выполнить. На множестве операций определяется отношение - предшествования, представляемое, например, в виде ориентированного бесконтурного графа ( С /, Е) с множеством U вершин, соответствующих операциям, и множеством Е С U x U дуг. Необходимо заметить, что транзитивная редукция не является столь уж безобидной процедурой. При построении расписаний используются различные графовые модели параллельных программ: с информационными, логическими либо информационно-логическими связями, а также графы, вершины, которых представляют операции и обработки, и обмена данными. В моделях с логическими связями ( по управлению) в силу их природы имеет место априорное упорядочение операций. Информационные связи ( по данным) позволяют выявить скрытый параллелизм программы. [16]
Исследованию свойств последовательно-параллельных графов посвящены работы Дж. В случае, когда граф оказывается последовательно-параллельным, алгоритм строит его полное декомпозиционное дерево. Алгоритм имеет линейную от числа вершин и дуг графа оценку временной сложности. В [178] описан алгоритм построения полного декомпозиционного дерева произвольного бесконтурного графа. [17]
С композицией связывается некоторый орграф, дуги которого проводятся на основе сводимости задач. Эквивалентным задачам отвечают сильно связанные компоненты ориентированного графа. Этот орграф порождает декомпозицию задач, свойства которой определяются максимальным бесконтурным графом. [18]
Если СФЭ не содержит функциональных элементов, то каждая ее вершина является входом. В этом случае функция, реализуемая в вершине, тождественно равна переменной ( или отрицанию переменной), приписанной соответствующему входу. Пусть для СФЭ, содержащих не более т 0 элементов, для каждой вершины функция, реализуемая в ней, определена. Рассмотрим произвольную СФЭ S с m 1 элементами. Поскольку СФЭ является ориентированным бесконтурным графом, то существует вершина с нулевой полустепенью исхода. Удаляя эту вершину, получаем СФЭ с m элементами, в которой по предположению индукции каждой вершине можно однозначно сопоставить функцию, реализуемую в этой вершине. [19]