Слайд 3
2. Модель в виде графа "операции-операнды"
1. Для уменьшения сложности излагаемого материала
при построении модели предполагается, что время выполнения любых вычислительных операций является одинаковым и равняется 1 (в тех или иных единицах измерения).
2. Кроме того, принимается, что передача данных между вычислительными устройствами выполняется мгновенно без каких-либо затрат времени (что может быть справедливо, например, при наличии общей разделяемой памяти в параллельной вычислительной системе).
3. Множество операций, выполняемых в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости в виде ациклического ориентированного графа G=(V, R), где V={1, 2, … |V|} есть множество вершин графа, представляющих выполняемые операции алгоритма, а R есть множество дуг графа. При этом дуга r =(i, j) принадлежит графу тогда и только тогда, когда операция j использует результат выполнения операции i. Вершины без входных дуг моделируют операции ввода, а вершины без выходных дуг – операции вывода.
5. Обозначим через d(G) диаметр (длину максимального пути) графа.
6. Операции алгоритма, между которыми нет пути в G=(V, R), могут быть выполнены параллельно.