10 Графовые модели. Общие понятия

Ориентированный граф может быть представлен как пара множеств (V, E), где V – конечное множество вершин,

Е – множество дуг.

Путь в графе – это последовательность П вида

П = ν₀, ν₁, … , ν_n (n>0), такая что (ν_i, v_i+1  E)

Если ν₀₌ ν_n, то путь называется контуром. Вершина U является предшественником вершины ν, а ν является последователем u, если существует путь из u в ν_. Через In(v) обозначают множество входящих дуг в вершину v, out – выходные дуги.

10.1 Модель биологического графа

Особенности:

1. Возможность одновременной передачи управления по нескольким выходным дугам одной вершины.

2. Наличия условия инициирования вершины (может быть потребована передача управления по одной или нескольким входным дугам вершин графа).

Биологический граф – ориентированный граф вида (V,E), с каждой вершиной которого сопоставляется пара символов (Рис.19):

Рисунок 19 - Примеры символов, сопоставляемых с вершинами биологического графа

Входы – символы, отображающие условия инициирования вершин. Выходы – символы, определяющие условия передачи управления по выходным дугам.

Пример вида вершин биологического графа представлен на рисунке 20

Рисунок 20- Пример вида вершин биологического графа

Символ «*», указываемый для входных вершин, определяет конъюнктивно-входную логику (условие «и»), требующее передачи управления по всем входным дугам. Символ «+» определяет дизъюнктивно-входную логику (условие «или») передачи управления по входным дугам.

Символы «+» и «*», сопоставленные с выходными дугами, интерпретируются аналогично. При наличии одной выходной дуги, ее логика (тип) соответствует входной логике данной вершины.

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

Примеры биологических графов представлены на рис. 21, 22.:

Рисунок 21 – Пример биологического графа (1)

Рисунок 22 – Пример биологического графа (2)

Срабатывание U1инициирует вершины U2 и U3, однако, срабатывание U6 возможно при получении управления по любой из входных дуг. Таким образом, срабатывание U6 произойдет дважды, а сама программа, моделируемая графом, генерирует да результата.

Правило функционирования моделей биологических графов

1. Инициирование выполнения всех начальных вершин, в которые не идут дуги.

2. При завершении выполнения, вершины с дизъюнктивной логикой (выходной), фишка, отображающая передачу управления, сопоставляется с любой из выходных дуг.

3. При завершении вершины с конъюнктивной логикой, все ее выходные дуги активизируются (на них указывают фишки).

4. Если вершина обладает конъюнктивной входной логикой , но для ее запуска необходимо наличие фишек на всех ее входных дугах

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

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

Модель биологического графа может быть использована для решения задач:

1. Вычисление времени выполнения параллельной программы, моделируемой биологическим графом (с каждой вершиной сопоставляется определенная временная функция операции).

2. Составление расписания запуска параллельно выполняющихся задач в составе МВК.

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