ПРЕДСТАВЛЕНИЕ АЛГОРИТМОВ ВЗВЕШЕННЫМИ ГРАФАМИ. СВЁРТКА И РАЗВЁРТКА ВЕРШИН ГРАФА. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ МАТРИЦ СЛЕДОВАНИЯ ИНФОРМАЦИОННОГО ГРАФА. АЛГОРИТМЫ ИХ ПОЛУЧЕНИЯ.

Информационный, или информационно-логический граф зада­ется с помощью выражения

G = (X,P,D), где X={i} = {1. ..., m} — множество вершин графа, со­ответствующее множеству операторов параллельного алгоритма, Р={p_i}, i =1. ..., m; p_i — множество весов, определяющих вре­мя выполнения каждого i-го оператора. В общем случае p_i — век­тор. Размерность вектора равна количеству типов процессоров, ис­пользуемых в неоднородной ВС. Для однородной ВС p_i — скаляр, а D — множество дуг графа. Дуги бывают двух типов:

.

Дуги назовем информационны­ми. Эти дуги соответствуют связям, исходящим из исполнительных блоков параллельного алгоритма. Информационно-логические ду­ги соответствуют связям, исходящим из логических блоков. Дуги нагружены меткой Т для связей, соответствующих логическому значению TRUE, и F для связей со значением FALSE.

Граф, содержащий только дуги из множества D₁, называется информационным графом, или информационной граф-схемой алго­ритма. Граф, содержащий некоторые дуги (в частном слу­чае — все), называется информационно-логическим графом, или информационно-логической граф-схемой алгоритма.

ИГ: ИЛГ:

Нумерация в кружке – имя процедуры (номер вершины).

Скобки – вектора весов (тут 3х-мерные вектора)

Номер позиции – тип процессора.

∞ - на этом процессоре данная процедура не выполняется.

Если в параллельном алгоритме существует связь между операторами , и — исполнительный блок, то в графе G существует дуга , исходящая из вершины и входящая в вершину . Эту связь будем обозначать и называть информационной связью.

Если в параллельном алгоритме существует связь между операторами , и — логический блок, то в графе G существует дуга исходящая из вершины и входящая в вершину . Эту связь будем обозначать для дуги с меткой Т и для дуги с меткой F и называть связью по управлению.

Связи , , называют задающими связями.

Путями в графе G назовем последователь­ности вершин , такие, что для любой пары вершин существует дуга , исходящая из вершины , и входящая в вершину .

В графе G нет циклов, поэтому все пути имеют конечную дли­ну. Кроме того, будем считать, что значения логических перемен­ных для различных логических операторов не связаны друг с дру­гом, поэтому в процессе реализации алгоритма возможен любой из допустимых путей.

Длиной пути в графе G назовем количество вершин, входящих в этот путь.

Характеристикой пути в графе G со скаляр­ными весами вершин назовем сумму весов вершин, составляющих этот путь.

Путь с максимальной характеристикой Т_кр в графе G со скалярными весами вершин назовем критическим. В одном графе может быть несколько критических путей.

В качестве формального сред­ства обработки графов введем матрицу следования S (транспонированная матрица смежности). В матрице следования для удобства использования в столбцах помечены не­нулевым значением все выходящие из данной вершины связи, а в строках — все входящие в данную вершину связи.

Более точное определение матрицы следования заключается в следующем: i –ой вершине графа G ставятся в соответствие i – ые столбец и строка матрицы, если существует связь по управлению , то элемент матрицы равен (i,j) = jT, порождает значение (i,j) = jF, при j → i образуется (i,j) = 1. Остальные элементы матрицы равны 0.

Расширенные матрицы SR следования для

а) последовательного алгоритма и б) параллельного алгоритма