ИГ используются для представления схем алгоритмов, не содержащих логические операторы. ИЛГ – для содержащих.
ИГ и ИЛГ представляются с помощью выражения G = (X, P, D), X –множество вершин i, X={1..m}. Это множество вершин графа, соответствующие множеству операторов параллельного алгоритма. P = {1..Pm} – множество весов вершин графа.
В общем случае Pi – вектор.
Если Pi - скаляр, то рассматривается решение этой задачи на однородной ВС (с одинаковыми процессорами). Тогда Pi – время решения i-ой процедуры.
Если Pi – вектор, предполагается решение этой задачи на неоднородной ВС. И, тогда, если система содержит S разнотипных процессоров, то вектор Pi = { Pi1,…, Pis}, где Pi1,…, Pis – набор времен решения i-ой процедуры на нек-ом типе процессора из множества S.
D – множество дуг гафов. Дуги бывают двух типов: di Є D1, dj Є D2, D = D1 U D2.D1- множество информационных дуг графа. D2 – множество информационно-логических дуг графа.
ИЛ дуги графа исходят из логических блоков графа. И дуги графа исходят из выполняемых блоков графа. Дуги dj нагружены метками True или False.
Граф, содержащий только информационные дуги называется информационным графом.
Аналогично – ИЛГ. ИГ мы также будем называть информационный граф схемы алгоритма, аналогично ИЛГ.
ИГ: ИЛГ:
Нумерация в кружке – имя процедуры (номер вершины). Скобки – вектора весов (тут 3х мерные вектора) Номер позиции – тип процессора. ∞ - на этом процессоре данная процедура не выполняется.
Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями.
Определение 1. Если в параллельном алгоритме существует связь между операторами α, β и α – исполнительный блок, то в графе G существует дуга di Î D1, исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать α → β.
Определение 2. Если в параллельном алгоритме существует связь между операторами α, β и α – логический блок, то в графе G существует дуга di Î D2, исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать 
или 
соответственно и называть связь по управлению.
Связь 
определяет связь между операторами, если оператор α принимает значение “ TRUE ”, связь 
- в противном случае.
Связи α → β, 
, назовём задающими связями.
Определение 3. Путями в графе G назовём последовательности вершин α1,…, αn, такие, что для любой пары вершин αi, αi+1 существует дуга uÎD1 U D2, исходящая из вершины αi и входящая в вершину αi+1.
В графе G нет циклов, поэтому все пути имеют конечную длину. Кроме того, будем считать, что значения логических переменных не связаны друг с другом, поэтому в процессе реализации алгоритма возможен любой из допустимых путей.
Определение 4. Характеристикой пути в графе G назовем количество вершин, входящих в этот путь.
Определение 5. Длиной пути в графе G со скалярными весами вершин назовем сумму весов вершин, составляющих этот путь.
Определение 6. Путь максимальной длины Ткр в графе G со скалярными весами вершин назовем критическим. В одном графе может быть несколько критических путей.
В качестве примера алгоритмов в виде схемы последовательного и параллельного алгоритмов с некоторыми трехмерными весами вершин представлен рис. 3.
Нумерация блоков в последовательном алгоритме дана в соответствии с ярусностью. В качестве формального средства обработки графов введем матрицу следования S. В матрице следования для удобства использования в столбцах помечены значением 1 все выходящие из данной вершины связи, а в строках – все входящие в заданную вершину связи.
Более точное определение матрицы следования заключается в следующем: i –ой вершине графа G ставятся в соответствие i – ые столбец и строка матрицы, если существует связь по управлению 
, то элемент матрицы равен (i,j) = jT, 
порождает значение (i,j) = jF, при j → i образуется (i,j) = 1. Остальные элементы матрицы равны 0.
Если мы хотим сказать, что между элементом i и j существует некоторая связь, то будем писать i → j. Для отражения весов вершин вводится понятие расширенной матрицы следования SR: прибавляется дополнительно k столбцов с номерами m+1,…,m+k, где k – размерность вектора весов вершин граф – схемы.
