Определение контуров в граф-схеме алгоритма

Алгоритм использует свойство появления ненулевого элемента в главной диагонали матрицы S_T. В качестве исходной берется не треугольная матрица S. Поэтому при получении транзитивных связей предыдущий алгоритм вызывается несколько раз до получения неизменяемой матрицы S_T.

Алгоритм 3.2. Определение контуров в граф-схеме алгоритма.

1. Вычисление матрицы := S, i := 0.

2. С помощью алгоритма 3.1, используя матрицу вычислить матрицу .

3. На главной диагонали матрицы определяется, есть ли ненулевые элементы? Если есть, то исследуемый граф имеет цикл – работа алгоритма завершена. В противном случае проверяем, изменилась ли матрица . Если , то исследуемый граф не имеет контуров. Алгоритм заканчивает работу. Иначе определяется , i := i+1 и осуществляется переход на шаг 2.

Конец алгоритма.

Пример работы данного алгоритма проиллюстрирован на рисунке 3.15 и рисунке 3.16.

Рисунок 3.15. Иллюстрация работы алгоритма 3.2: граф (а) и матрица следования S (б)

Рисунок 3.16. Матрица S_T для графа, изображенного на рисунке 3.15 а

Вопросы для самопроверки

1. В чем отличие матрицы следования от расширенной матрицы следования и матрицы следования с транзитивными связями?

2. В каких случаях используется треугольная матрица следования?

3. Что является признаком наличия цикла (контура) в информационно-логическом графе в матрице следования?

4. С какой целью вычисляется матрица следования с транзитивными связями?

5. В чём смысл операций «Ä» и «Å»?

Задание на лабораторную работу

Используя программу, разработанную в предыдущей лабораторной работе, необходимо дополнить ее следующими функциями:

1. Построение матрицы следования S по заданному графу.

2. Построение матрицы следования S_R (с указанием весов).

3. Построение матрицы следования S_T с транзитивными связями.

4. Определение наличия или отсутствия контура в исходном графе.

5. Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

6. Сохранить копию программы для выполнения последующих лабораторных работ на дискете.

7. Оформить отчет о проделанной работе.

Содержание отчета

1. Цель работы.

2. Ответы на вопросы для самопроверки.

3. Схемы алгоритмов и их описание.

4. Распечатки экранных форм, полученных в результате работы программы.

5. Анализ полученных результатов.

3. Лабораторная работа №4. Построение матрицы логической несовместимости операторов

Цель работы – ознакомление с понятием логической несовместимости операторов, практическая реализация алгоритмов работы с матрицами логической несовместимости L в виде программных модулей.

Теоретическая часть

Для оценки возможности выполнения программных модулей параллельно, важную роль играют логически несовместимые операторы.

Рассмотрим множество вершин, принадлежащих n-ветви i-го логического оператора. Это множество назовем Mi.n. Аналогично построим множество вершин для дуги k – это множество вершин, принадлежащих k-ветви i-го логического оператора – множество MK_i. В множества Mi.n и Mi.k сама вершина i не входит.

Определение 4.1. Если вершина p  Mi.n, а q  Mi.k и соответствующие им операторы могут выполняться либо один, либо другой при однократном выполнении алгоритма, то эти операторы называются логически несовместимыми.

При реализации алгоритма в логическом операторе i выполняется либо ветвь i.n, либо i.k. Следовательно, при планировании параллельных вычислений следует исключать планирование параллельного выполнения операторов, принадлежащих разным ветвям, т.е. попросту исключить их из планирования. Однако встречаются ситуации, когда ветви i.n и i.k пересекаются, т.е. Mi.n I Mi.k = Mi.nk  Ø.

Определение 4.2. Если Mi.nk  Ø, то существует внутреннее замыкание i-го логического оператора.

В этом случае операторы могут планироваться для параллельного выполнения. На рисунке 4.1 приведён граф, в котором на вершине 6 произошло пересечение логических ветвей оператора 1. Операторы 6, 7, 9, 10 могут быть запланированы для параллельного выполнения.

Рисунок 4.1. Граф-схема ИЛГ с пересечением логических путей оператора 1

Определение 4.3. Вершина и имеющая наименьший номер, называется минимальной внутренне замкнутой вершиной i-го логического оператора и обозначается inz_i.

Так, для примера, представленного на рисунке 4.2, inz₁ = 6.

Рисунок 4.2. Граф-схема алгоритма, имеющая замыкающие дуги и со стороны 1.1, и со стороны 1.2

Следует отметить, что замыкание логических путей может осуществляться за счет внешних информационных связей. Как показано на рисунке 4.3, замыкание может произойти за счет информационных связей путями, идущими от операторов 3 или 4. При этом должен существовать информационный путь к вершинам 3 или 4 от входа в алгоритм (вершина 1).

Рисунок 4.3. Граф-схема алгоритма с замыканием логических ветвей за счёт вершин, не принадлежащих путям оператора 2

Целесообразно рассматривать внешние замыкания для ветвей i.n и i.k отдельно. Это связано с тем, что при рассмотрении возможности параллельного выполнения операторов, включенных в логические ветви, необходимо учитывать результаты как внешнего, так и внутреннего замыканий совместно, имея в виду при этом, что возможно внешнее замыкание только одной ветви.

Определение 4.4. Если существует информационный путь в вершину от начальной вершины граф-схемы, то вершина Z называется внешне замкнутой в n-ветви для i-го логического оператора. Если таких вершин несколько, то вершину Z с минимальным номером называют минимальной внешне замкнутой вершиной в n-ветви для i-го логического оператора.

Обозначим эту вершину ezi.n = x_j.

Определение 4.5. Если множество содержит внешнее замыкание ezi.n = x_j, то подмножество называется внешне замкнутым для n-ветви логического оператора L_i.

При рассмотрении влияния внешних и внутренних замыканий для оценки возможности распараллеливания операторов, принадлежащих ветвям логического оператора, необходимо учесть, что:

1. внутреннее замыкание, как правило, порождает операторы, которые можно выполнять параллельно;

2. для возможности распараллеливания операторов, принадлежащих путям логического оператора, достаточно одного внешнего замыкания при наличии внутреннего;

3. определение множества MZ_i всех замкнутых операторов i-го логического оператора требуется вычислить объединение множеств: .

Ситуации, соответствующие пунктам 1 и 2, проиллюстрированы на рисунках 4.1, 4.2 и 4.3. На рисунке 4.4 рассмотрена ситуация, соответствующая пункту 3.

Рисунок 4.4. Пример граф-схемы, в которой внешнее замыкание ветви 2.1 уточняет множество операторов, подлежащих распараллеливанию

На рисунке 4.5 приведён алгоритм построения матрицы логической несовместимости операторов, в котором использованы следующие обозначения:

S – матрица следования;

RS – размерность матрицы S;

S_T – матрица с транзитивными связями;

RST – размерность матрицы S_T;

MLO – множество логических операторов;

RMLO – размерность множества логических операторов;

M – множество вершин операторов;

Mk.n – множество вершин операторов, принадлежащих путям, включающим дугу n k-го логического оператора;

Vk.g – множество вершин операторов, внешне замкнутых для k-го логического оператора связи G;

Mk.g – множество вершин операторов, принадлежащих путям, включающим дугу g k-го логического оператора;

RMk.n – размерность множества логических операторов ветви k.n;

RMk.g – размерность множества логических операторов ветви k.g;

Nk.g – множество вершин операторов, внутренне замкнутых для k-го логического оператора;

Vk.n – множество вершин операторов, внешне замкнутых для k-го логического оператора связи n;

MZ_k – объединенное множество внешних и внутренних замыканий для k-го логического оператора.

Рисунок 4.5. Схема алгоритма построения матрицы логической несовместимости операторов. Начало

Рисунок 4.5. Продолжение

Рисунок 4.5. Окончание

Процедура PMLO.

Признаком логического оператора матрицы S является появление в соответствующем столбце значений j.n или j.g.

Алгоритм 4.1. Получение множества логических операторов.

1. В матрице S, размера RS выбираем первый столбец (j := 1), RMLO := 0, MLO := Ø.

2. Просматриваем j-й столбец по строкам и определяем равенство текущего элемента матрицы j.n или j.g.

3. Если найден такой элемент, то полагаем , j := j+1.

4. Если j  RS,то переходим к шагу 2, иначе – конец алгоритма.

Конец алгоритма.

Процедура PMNG.

Для получения множеств Mk.n и Mk.g k-го логического оператора необходимо просмотреть k-й столбец и включить во множество MN номера операторов, которые в соответствующих строках имеют значение k.n, а во множество MG – номера операторов, которые в соответствующих строках имеют значение k.g.

Алгоритм 4.2. Получение множеств Mk.n и Mk.g k-го логического оператора.

1. В соответствии со значением k, выбираем элемент множества . В q_k столбце матрицы S_T просматриваем i-е строки, i := 1 (номер строки), l := 1 (номер позиции в множестве Mk.n), m := 1 (номер позиции в множестве Mk.g).

2. Если элемент матрицы S_N(i, k) = j.n, то Mk.n[l] := i, l := l+1 и осуществляется переход к шагу 5.

3. Если S_N(i, k) = j.g, то Mk.g[m] := i; m := m+1 и выполняется шаг 5.

4. Если условия пунктов 2 и 3 не выполняются, то осуществляется переход на шаг 5.

5. Вычислим i := i+1; если i > RST, то RMk.n := l, RMk.g := m и выполнение алгоритма заканчивается, иначе осуществляется переход на шаг 2.

Конец алгоритма.

Процедура PREZ.

Процедура PREZ формирует множество внешних замыканий для рассматриваемого логического оператора, используя свойства матрицы S_T. Берётся i-ая строка матрицы S_T, содержащая все нули (вход ИЛГ). Затем – для i-го столбца номера всех элементов, равных 1, фиксируются в множестве WZ. Если для рассматриваемого k-го логического оператора пересечения множеств и не пусты, то обнаружены внешние замыкания для ветвей k-го логического оператора (номера внешне замкнутых операторов входят в эти пересечения).

Алгоритм 4.3. Формирование множества внешних замыканий.

1. Формируем множество из номеров нулевых строк матрицы S_T: ZS := {i₁, ..., i_q}. Полагаем Vk.n := Ø, Vk.g := Ø.

2. Для всех элементов i_p  ZS строим множество ED_p номеров строк, содержащих единичные элементы в i_p столбцах.

3. Исключим из множества ED_p, p = 1, …, q элементы, равные номеру рассматриваемого логического оператора k. Перенумеруем множества ED_p, учитывая удаленные элементы. Получим множество ED_u, u = 1, …, f, f < q. Если все ED_u = Ø, то Vk.n := Ø, Vk.g := Ø.

4. Вычислим множества где Mk.g и Mk.n – множества операторов для текущего вложенного оператора k.

Конец алгоритма.

Вопросы для самопроверки

1. Дайте определение логически несовместимых операторов.

2. Дайте определения внешних и внутренних замыканий.

3. Когда внешнее замыкание одной ветви сказывается на определенном множестве логически несовместимых операторов?

4. С какой целью вычисляется матрица логически несовместимых операторов?

5. Почему в алгоритме 4.3 анализируются только те столбцы матрицы S_T, номера которых совпадают с номерами нулевых строк этой матрицы?

6. Почему учёт воздействия внешних замыканий на логическую несовместимость зависит от наличия или отсутствия внешних замыканий?

Задание на лабораторную работу

Используя программу, разработанную в предыдущей лабораторной работе, необходимо дополнить её следующими функциями:

1. Для заданного информационно-логического графа построить матрицу логической несовместимости операторов.

2. Выделить на исходном графе логически несовместимые вершины.

3. Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

4. Сохранить копию программы для выполнения последующих лабораторных работ на дискете.

5. Оформить отчет о проделанной работе.

Содержание отчета

1. Цель работы.

2. Ответы на вопросы для самопроверки.

3. Схемы алгоритмов и их описание.

4. Распечатки экранных форм, полученных в результате работы программы.

5. Анализ полученных результатов.