Параллельные вычисления. Баканов В.М. - 70 стр.

                                       - 70 -


  При последовательном вычислении граф алгоритма (рис.19) полностью
копирует последовательность действий табл.4; имеет 3 входных вершины
(соответствующие вводу коэффициентов a,b и c), две выходные вершины
(вычисленные корни x1 и x 2 исходного уравнения) и 11 вершин, соответст-
вующих операторам алгоритма.




Рисунок 19 — Граф алгоритма (зависимость ‘операции - операнды’) нахождения корней
      полного квадратного уравнения для последовательного выполнения.

   Одним из (неэкономных по использованию памяти при использовании)
представлений графа G=(V,E) является квадратная матрицей смежности
(нумерация строк и столбцов соответствует нумерации операторов, булева
‘1’ в (i,j)-той ячейке соответствует наличию дуги e(i,j), ‘0’ – отсутствию
оной):

    ⎡0   0 0 0 0 0 0 0 0 0 0⎤
    ⎢0   0 0 0 1 0 0 0 0 0 0⎥⎥
    ⎢
    ⎢0   0 0 0 0 0 0 1 1 0 0⎥
    ⎢                        ⎥
    ⎢0   0 0 0 0 1 0 0 0 0 0⎥
    ⎢0   0 0 0 0 1 1 0 0 0 0⎥
    ⎢                        ⎥
    ⎢0   0 0 0 0 0 1 0 0 0 0⎥
    ⎢0   0 0 0 0 0 0 1 1 0 0⎥
    ⎢                        ⎥
    ⎢0   0 0 0 0 0 0 0 0 1 0⎥
    ⎢0   0 0 0 0 0 0 0 0 0 1⎥
    ⎢                        ⎥
    ⎢1   0 0 0 0 0 0 0 0 0 0⎥
    ⎢                        ⎥
    ⎣1   0 0 0 0 0 0 0 0 0 0⎦


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