Как составить потоковый граф

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

1. Граф строится
   отображением управляющей структуры
   программы. В ходе отображения закрывающие
   скобки условных операторов и операторов
   циклов (end
   if;
   end
   loop)
   рассматриваются как отдельные (фиктивные)
   операторы.

2. Узлы (вершины)
   потокового графа соответствуют линейным
   участкам программы, включают один или
   несколько операторов программы.

3. Дуги потокового
   графа отображают поток управления в
   программе (передачи управления между
   операторами). Дуга — это ориентированное
   ребро.

4. Различают
   операторные и предикатные узлы. Из
   операторного узла выходит одна дуга,
   а из предикатного — две дуги.

5. Предикатные узлы
соответствуют простым условиям в
программе. Составное условие программы
отображается в несколько предикатных
узлов. Составным называют условие, в
котором используется одна или несколько
булевых опера­ций (OR,
AND).

Например, фрагмент
программы

if
a
OR
b

then x

else у

end if;

вместо прямого
отображения в потоковый граф вида,
показанного на рис. 5.3, отображается в
преобразованный потоковый граф (рис.
5.4).

Рис. 5.3.
Прямое
отображение в потоковый граф

Нет

Да

Нет

Рис. 5.4.
Преобразованный
потоковый граф

1. Замкнутые области,
   образованные дугами и узлами, называют
   регионами.

1. Окружающая граф
   среда рассматривается как дополнительный
   регион. Например, показанный здесь граф
   имеет три региона — Rl,
   R2,
   R3.

Цикломатическая
сложность

Цикломатическая
сложность — метрика ПО, которая
обеспечивает количествен­ную оценку
логической сложности программы. В
способе тестирования базового пути
цикломатическая сложность определяет:

• количество
  независимых путей в базовом множестве
  программы;

• верхнюю оценку
  количества тестов, которое гарантирует
  однократное выполнение всех операторов.

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

Путь начинается
в начальном узле, а заканчивается в
конечном узле графа. Независи­мые
пути формируются в порядке от самого
короткого к самому длинному. Каждый
новый путь включает новую дугу.

Все независимые
пути графа образуют базовое множество.

Свойства базового
множества:

1) тесты, обеспечивающие
его проверку, гарантируют:

— однократное
выполнение каждого оператора;

— выполнение каждого
условия по True-ветви
и по False-ветви;

2) мощность базового
множества равна цикломатической
сложности потокового графа.

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

Цикломатическая
сложность вычисляется одним из трех
способов:

1. цикломатическая
   сложность равна количеству регионов
   потокового графа;

2. цикломатическая
   сложность определяется по формуле:
   V(G)=E—N+2,
   где Е
   — количество
   дуг, N —
   количество
   узлов потокового графа;

3. цикломатическая
   сложность формируется по выражению
   V(G)
   = р + 1, где р
   — количество предикатных узлов в
   потоковом графе G.

Вычислим
цикломатическую сложность графа из
примера каждым из трех спо­собов:

1. потоковый граф
   имеет 3 региона;

2. V(G) =
   7 дуг — 6 узлов + 2 = 3;

3. V(G) =
   2 предикатных узла +1= 3.

Время на прочтение
8 мин

Количество просмотров 10K

В первой части статьи мы рассмотрели основные отличия архитектуры потока данных (dataflow) от архитектуры потока управления (controlflow), совершили экскурсию в 1970-е, когда появились первые аппаратные dataflow-машины и сравнили статическую и динамическую потоковые модели вычислений. Сегодня я продолжу вас знакомить с dataflow-архитектурами. Добро пожаловать под кат!

В дополнение к вышесказанному: реализация циклов в динамических потоковых системах

Рассмотрим более подробно работу контекста на примере организации циклов. Напомню, контекст — это поле в структуре токена, однозначно определяющее экземпляр узла dataflow-графа. В случае с циклами контекстом будет являться номер итерации.

Пример 1. Числа Фибоначчи

Вычисление чисел Фибоначчи является класическим примером цикла с зависимостью итераций по данным. N-ное число равно сумме (N-1)-го и (N-2)-го:

int fib [MAX_I];
fib [0] = 1;
fib [1] = 1;
for (i = 2; i < MAX_I; i++)
{
	fib [i] = fib [i-1] + fib [i-2];
}

Построим потоковый граф вычислений:

Легко видеть, что граф состоит из (MAX_I-2) одинаковых узлов, отличающихся только значениями контекста (цифры под изображением узла). Логика работы узла (в псевдокоде) будет выглядеть так:

узел fib (входы: токен A, токен B)
	переменная i = поле_контекста(A);
	переменная result = поле_данных(A) + поле_данных(B);
	отправить_токен (данное: result, метка: host, контекст: i);
	если (i < MAX_I-1)
		отправить_токен (данное: result, метка: fib, контекст: i+1);
		отправить_токен (данное: result, метка: fib, контекст: i+2);
	конец если
конец узел fib

Для старта программы требуется отправисть три токена:

отправить_токен (данное: 1, метка: fib, контекст: 2);
отправить_токен (данное: 1, метка: fib, контекст: 2);
отправить_токен (данное: 1, метка: fib, контекст: 3);

В результате выполнения потоковой программы на хост будет отправлен набор токенов, каждый из которых в поле контекста будет нести номер числа Фибоначчи, а в поле данных — само число. Обратите внимание, еще один токен (отмечен на графе пунктирной линией) посылается «в никуда», точнее, никогда не запускает выполнения узла по причине отсутствия парного ему токена. Избавиться от него можно либо добавив еще одну проверку условия (i < MAX_I-2) в коде узла, либо организовав программный или аппаратный «сборщик мусора».

Пример 2. Сложение матриц

Рассмотрим теперь пример, где нет зависимости между итерациями по данным: сложение матриц

C[i,j] = A[i,j] + B[i,j].

int A [MAX_I][MAX_J];
int B [MAX_I][MAX_J];
int C [MAX_I][MAX_J];
GetSomeData (A, B);
for (i = 0; i < MAX_I; i++)
	for (j = 0; j < MAX_J; j++)
	{
		C[i,j] = A[i,j] + B[i,j];
	}

Все (MAX_I*MAX_J) итераций могут быть выполнены одновременно. Вот так выглядит граф сложения матриц:

Контекст в данном случае представляет собой структуру из двух координат {i; j}. C учетом этого узел графа будет выглядеть так:

узел add (входы: токен A, токен B)
	переменная {i, j} = поле_контекста(A);
	переменная result = поле_данных(A) + поле_данных(B);
	отправить_токен (данное: result, метка: host, контекст: {i, j});
конец узел add

Обратите внимание, никаких проверок границ здесь нет! Число итераций автоматически выбирается исходя из размерности входных данных. Входные данные, кстати, должны поступать в таком виде:

отправить_токен (данное: A[0, 0], метка: add, контекст: {0, 0});
отправить_токен (данное: B[0, 0], метка: add, контекст: {0, 0});
отправить_токен (данное: A[0, 1], метка: add, контекст: {0, 1});
отправить_токен (данное: B[0, 1], метка: add, контекст: {0, 1});
...
отправить_токен (данное: A[MAX_I-1, MAX_J-1], метка: add, контекст: {MAX_I-1, MAX_J-1});
отправить_токен (данное: B[MAX_I-1, MAX_J-1], метка: add, контекст: {MAX_I-1, MAX_J-1});

Dataflow-системы очень эффективны для обработки разреженных данных, так как фактически пересылаются и обрабатываются только значимые элементы.

Гибридные dataflow-архитектуры

«Чистые» потоковые архитектуры, подобные описанным MIT Static Dataflow Machine и Manchester Dataflow Machine, к сожалению, имели много слабых мест:

• Dataflow-машины давали огромные возможности для параллелизма выполнения. Обратной стороной этого преимущества было то, что на последовательных участках вычислительного графа они показывали резкое падение производительности.
• Загрузка исполнительных устройств была далека от максимально возможной. Большая часть машинного времени тратилась на поиск соответствия операндов, выборку инструкций, а исполнительное устройство все это время простаивало, выполняя лишь по одной инструкции на каждую пару токенов.
• Трудным было конструирование устройств сопоставления. Ассоциативная память сложнее, дороже, медленнее, занимает больше места и потребляет больше энергии, по сравнению с обычной оперативной памятью такого же объема.
• Сам принцип управления потоком данных не позволял организовать эффективный конвейер. Почти все устройства работали асинхронно, требовались буферы и очереди в линиях связи.
• По сравнению с классической многопроцессорной архитектурой, в dataflow-машинах значительно выше была нагрузка на коммутационную сеть. Ведь фактически, каждая операция требовала пересылки двух токенов.

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

Threaded dataflow

Этому термину нет вообще никакого адекватного перевода на русский. Суть данного подхода состоит в том, чтобы последовательные участки вычислительного графа, которые невозможно распараллелить, заменить тредами (threads) — наборами последовательно выполняемых инструкций. Сразу исчезают «лишние» промежуточные токены, и растет загрузка исполнительных устройств. Принципы threaded dataflow были воплощены «в железе» в процессоре Epsilon [21] в 1989 году.

Крупнозернистая архитектура потока данных

Дальнейшим развитием threaded dataflow стали так назыаемые крупнозернистые потоковые архитектуры (large-grain dataflow). Когда стало ясно, что параллелизм «чистого» dataflow во многих случаях избыточен, возникло решение строить потоковый граф не из отдельных операторов, а из блоков. Таким образом, в крупнозернистой архитектуре каждый узел представляет собой не одну инструкцию, а классическую последовательную программу. Взаимодействие между узлами по-прежнему осуществляется по принципу потока данных. Одним из преимуществ такого подхода стала возможность использовать в качестве исполнительных устройств обычные фон-неймановские процессоры. Следует отметить, что несмотря на название «крупнозернистая», блоки, на которые разбивается задача, все равно намного мельче, чем, скажем, в кластерных системах. Типичный размер блока составляет 10-100 инструкций и 16-1К байт данных.

Векторная dataflow-архитектура

В векторных потоковых системах токен содержит не одно значение, а сразу множество. Соответственно, и операции выполняются не над парами операндов, а над парами векторов. В качестве примера такой системы можно привести машину SIGMA-1 (1988) [22]. Иногда векторный режим поддерживается только частью исполнительных устройств системы. Часто также применяются гибридные архитектуры, объединяющие сразу несколько подходов, например крупнозернистая архитектура с возможностью выполнения векторных операций.

Реконфигурируемые системы

Развитие технологий ПЛИС сделало возможным принципиально новый подход к архитектуре dataflow. Что, если собрать машину, ориентированную на решение одной конкретной задачи? Если реализовать непосредственно на схемотехническом уровне нужный вычислительный граф, можно добиться потрясающих результатов. Вместо устройств сложных и медленных сопоставления можно использовать безусловное перенаправление данных от одного функционального модуля к другому. Сами исполнительные устройства тоже можно «заточить» под нужную задачу: выбрать тип арифметики, разрядность, нужный набор поддерживаемых операций.
Разумеется, подобная машина будет очень узкоспециализированной, но ведь достоинство ПЛИС как раз в возможности неоднократного перепрограммирования. Таким образом, под каждую отдельную задачу собирается нужная архитектура. Некоторые системы позволяют даже осуществлять перенастройку прямо в процессе работы. Реконфигурируемые системы на базе FPGA-микросхем в настоящее время выпускаются серийно в самых разных форматах — от блока «ускорителя» для ПК до системы производительностью порядка нескольких Тфлопс [31].
Из недостатков реконфигурируемых архитектур можно выделить следующие:

• Принципиальная однозадачность. Для запуска новой задачи требуется остановка системы и перепрограммирование ПЛИС, входящих в ее состав.
• Сложность программирования. Программирование каждой задачи включает в себя синтез всей вычислительной архитектуры под данную задачу.
• Избыточная аппаратная сложность. Обратной стороной гибкости ПЛИС является наличие на кристалле большого процента элементов, которые непосредственно не участвуют в вычислениях, а служат только для реконфигурации. Тем не менее, эти элементы потребляют энергию и выделяют тепло во время работы, что ухудшает энергетические показатели эффективности системы (Гфлопс/Вт).

Программирование под dataflow-архитектуры

Программирование в парадигме dataflow существенно отличается от привычного структурного, а ближе скорее к функциональному. Здесь нет переменных, массивов и других именованных областей памяти, нет вызываемых процедур и функций в привычном смысле этого слова. Потоковое программирование использует принцип однократного присваивания. Каждая единица данных (как правило, это токен) получает значение только один раз, при создании, и в дальнейшем может быть только прочитана. Этот принцип отражает однонаправленность ветвей вычислительного графа.
В dataflow, к сожалению, так и не выработался какой-либо стандарт программирования. Обычно под каждую архитектуру разрабатывается свой язык. Расскажу о нескольких наиболее известных.

VAL

VAL (Value-oriented Algorithmic Language)[41] был разработан в Массачусетском технологическом институте (MIT) в 1979 году специально для MIT Dataflow Machine. Вот как выглядит, к примеру, вычисление факториала на VAL:

for Y:integer := 1; P:integer := N;
do	if P ~= 1 then iter Y := Y*P; P := P-1; enditer;
	else Y
	endif
endfor

SISAL

SISAL (Streams and Iteration in a Single Assignment Language)[42], появившийся в 1983 году, является дальнейшим развитием VAL. В отличие от VAL, SISAL позволяет использовать рекурсию.
Вычисление факториала:

function factorial( n : integer returns integer )
	if n <=1 then 1
	else n * factorial( n - 1 )
	end if
end function

Вариант без рекурсии от хабраюзера middle:

function factorial (n : integer returns integer)
  for i in 1, n
    returns value of prod i
  end for
end function

Id

Id [43] — параллельный язык общего назначения, создан в конце 1970-х — начале 1980-х годов в MIT. Дальнейшая работа над Id привела к развитию языка pH — параллельного диалекта Haskell’а.
Факториал на Id:

( initial j <- n; k <- 1
	while j > 1 do
		new j <- j - 1;
		new k <- k * j;
	return k )

А граф вычислений для данной программы будет выглядеть так:

Lucid

Язык Lucid [44][45] разработан в 1976 Биллом Уэйджем (Bill Wadge) и Эдом Эшкрофтом (Ed Ashcroft). Оперирует понятиями потоков значений (аналог переменных) и фильтров, или преобразователей (аналог функций).
Факториал на Lucid:

fac
  where
    n = 0 fby (n + 1);
    fac = 1 fby ( fac * (n + 1) );
  end

Quil

Quil (2010) [46] — язык, основанный на Lucid, в настоящее время работа над ним продолжается. На сайте языка есть онлайн-интерпретатор, так что написать вычисление факториала на Quil оставляю как самостоятельное задание читателям.

Заключение

«Бум» потоковых архитектур пришелся на 1970-80-е годы, потом интерес к dataflow постепенно угасал. В наши дни элементы потоковых вычислителей можно встретить в архитектуре DSP (сигнальных процессоров), сетевых маршрутизаторов и графических процессоров. Но постепенно все большее число специалистов вновь обращаются к парадигме dataflow в рамках высокопроизводительных вычислений. Вероятно, это можно связать с тем, что сегодня фон-неймановская архитектура подходит к своему пределу масштабируемости, и для дальнейшего повышения производительности требуются новые подходы.
Несколько особняком стоят реконфигурируемые архитектуры, в которых постепенно стирается грань между программной и аппаратной частью. За какой технологией будущее? Вопрос остается открытым.

Bonus Game. Самым любознательным из читателей предлагаю попытаться определить, графы каких алгоритмов изображены на «картинках для привлечения внимания» в заголовке каждой части статьи. Удачи!

---

Литература

Нумерация источников продолжается с первой части.

Гибридные dataflow-системы

[21] — The Epsilon dataflow processor, V.G. Grafe, G.S. Davidson and others.
[22] — Efficient vector processing on dataflow supercomputer SIGMA-1, K. Hiraki, S. Sekiguchi, T. Shimada.

Реконфигурируемые системы

[31] — Семейство многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой, Н.Н. Дмитриенко, И.А. Каляев и другие.
[32] — Dynamically Reconfigurable Dataflow Architecture for High-Performance Digital Signal Processing on Multi-FPGA Platforms, Voigt, S.-O., Teufel, T.

Языки программирования dataflow-систем

[41] — VAL — A Value-oriented Algorithmic Language
[42] — Sisal Language Tutorial
[43] — ID Language Reference Manual, Rishiyur S. Nikhil, 1991
[44] — LUCID, the dataflow programming language, Academic Press Professional, Inc. San Diego, CA, USA 1985 ISBN:0-12-729650-6
[45] — Fluid Programming in Lucid
[46] — The Quil Language

Методы анализа — Потоковый граф

Индекс материала
Методы анализа
Описание потоков данных и процессов
Описание потоков данных и процессов
Методы анализа, ориентированные на структуры данных
Методика Джексона
Шаг объект-структура
Шаг начального моделирования
Контрольные вопросы
Основы проектирования программных систем
Особенности этапа проектирования
Структурирование системы
Моделирование управления
Декомпозиция подсистем на модули
Связность модуля
Функциональная связность
Коммуникативная связность
Временная связность
Связность по совпадению
Сцепление модулей
Контрольные вопросы
Классические методы проектирования
Проектирование для потока данных типа «преобразование»
Проектирование для потока данных типа «запрос»
Доопределение функций
Учет системного времени
Структурное тестирование программного обеспечения
Тестирование «черного ящика»
Потоковый граф
Цикломатическая сложность
Шаги способа тестирования базового пути
Тестирование ветвей и операторов отношений
Тестирование циклов
Неструктурированные циклы
Функциональное тестирование программного обеспечения
Способ разбиения по эквивалентности
Способ анализа граничных значений
Способ диаграмм причин-следствий
Организация процесса тестирования программного обеспечения
Тестирование интеграции
Восходящее тестирование интеграции
Системное тестирование
Стрессовое тестирование
Все страницы

Страница 28 из 42

Потоковый граф

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

1. Граф строится отображением управляющей структуры программы. В ходе отображения закрывающие скобки условных операторов и операторов циклов (end if; end loop) рассматриваются как отдельные (фиктивные) операторы.

2. Узлы (вершины) потокового графа соответствуют линейным участкам программы, включают один или несколько операторов программы.

3. Дуги потокового графа отображают поток управления в программе (передачи управления между операторами). Дуга — это ориентированное ребро.

4. Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

4. Предикатные узлы соответствуют простым условиям в программе. Составное условие программы отображается в несколько предикатных узлов. Составным называют условие, в котором используется одна или несколько булевых операций (OR, AND).

5. Например, фрагмент программы

if a OR b

then x

else у

end if;

вместо прямого отображения в потоковый граф вида, показанного на рис. 6.4, отображается в преобразованный потоковый граф (рис. 6.5).

Рис. 6.4. Прямое отображение в потоковый граф

Рис. 6.5. Преобразованный потоковый граф

6. Замкнутые области, образованные дугами и узлами, называют регионами.

7. Окружающая граф среда рассматривается как дополнительный регион. Например, показанный здесь граф имеет три региона — Rl, R2, R3.

Пример 1. Рассмотрим процедуру сжатия:

процедура сжатие

1 выполнять пока нет EOF

1 читать запись;

2 если запись пуста

3 то удалить запись:

4 иначе если поле а >= поля b

5 то удалить b;

6 иначе удалить а;

7а конец если;

7а конец если;

7b конец выполнять;

8 конец сжатие;

Рис. 6.6. Преобразованный потоковый граф процедуры сжатия

Она отображается в потоковый граф, представленный на рис. 6.6. Видим, что этот потоковый граф имеет четыре региона.

Построение графа потока управления CFG (Control Flow Graph)

Выполнено командой:

PiedPiper (Бергер Анна, Колесников Сергей)

От каких проектов зависит:

1. Базовые блоки

Зависимые проекты:

1. Построение трехадресного кода по графу потока управления
2. Итерационный алгоритм (и вспомогательные алгоритмы для его работы)
3. Построение дерева доминаторов

Теория

Граф потока управления — множество всех возможных путей исполнения программы, представленное в виде графа. В графе потока управления каждый узел графа соответствует базовому блоку. Ребро из блока В в блок С идет тогда и только тогда, когда первая команда блока С может следовать непосредственно за последней командой блока В. Тогда говорим, что В — предшественник С, а С — преемник В.

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

Входные данные:

• Список базовых блоков (BasicBlocksList)

Выходные данные:

• Граф потока управления (Graph)

Используемые структуры данных

• BidirectionalGraph<BasicBlock, Edge> — граф потока управления (структура данных из пакета QuickGraph)
• Dictionary<int, BasicBlock> blockMap — соответствие между узлами графа и уникальными идентификаторами базовых блоков (blockId)

Реализация алгоритма

// построение графа потока управления по списку базовых блоков
public Graph(BasicBlocksList listBlocks)
{
   CFG.AddVertexRange(listBlocks.Blocks);

   foreach (BasicBlock block in listBlocks.Blocks)
   {
   	blockMap.Add(block.BlockId, block);
   }

   foreach (var block in listBlocks.Blocks)
   {
   	foreach (var numIn in block.InputBlocks)
   	{
   		CFG.AddEdge(new Edge<BasicBlock>(this.getBlockById(numIn), block));
   	}
   }
   ...
}

Для удобства использования графа в нем реализованы следующие методы:

• public BasicBlock getBlockById(int id) — по идентификатору базового блока возвращается базовый блок — узел графа
• public BasicBlocksList getChildren(int id) — по идентификатору базового блока возвращается список базовых блоков-преемников
• public BasicBlocksList getParents(int id) — по идентификатору базового блока возвращается список базовых блоков-предшественников
• BasicBlock getRoot() — точка входа в программу
• public int GetCount() — количество вершин в графе
• public IEnumerable<Edge> GetEdges() — список ребер в графе
• public IEnumerable GetVertices() — список вершин в графе
• public bool Contains(BasicBlock block) — проверка, содержится ли базовый блок в графе
• public bool IsAncestor(int id1, int id2) — проверка является ли блок с blockId = id1

Пример использования

...
var b = BasicBlocksGenerator.CreateBasicBlocks(threeAddressCode);
Graph g = new Graph(b);
...

Тест

Программа

b = 1;
if 1
  b = 3;
else
  b = 2;

Список базовых блоков

BlockId = 0
Commands:
   b = 1
   goto $GL_2 if 1 == 0
InputBlocksNumbers = {}
OutputBlocksNumbers = {1; 2}
BlockId = 1
Commands:
   b = 3
   goto $GL_1
InputBlocksNumbers = {0}
OutputBlocksNumbers = {3}
BlockId = 2
Commands:
   $GL_2: <no-op>
   b = 2
InputBlocksNumbers = {0}
OutputBlocksNumbers = {3}
BlockId = 3
Commands:
   $GL_1: <no-op>
InputBlocksNumbers = {1; 2}
OutputBlocksNumbers = {}

Граф потока управления

0:
<-- 
-->  1 2
1:
<--  0
-->  3
2:
<--  0
-->  3
3:
<-- 1 2
--> 

From Wikipedia, the free encyclopedia

A flow graph is a form of digraph associated with a set of linear algebraic or differential equations:^[1][2]

«A signal flow graph is a network of nodes (or points) interconnected by directed branches, representing a set of linear algebraic equations. The nodes in a flow graph are used to represent the variables, or parameters, and the connecting branches represent the coefficients relating these variables to one another. The flow graph is associated with a number of simple rules which enable every possible solution [related to the equations] to be obtained.»^[1]

Although this definition uses the terms «signal-flow graph» and «flow graph» interchangeably, the term «signal-flow graph» is most often used to designate the Mason signal-flow graph, Mason being the originator of this terminology in his work on electrical networks.^[3][4] Likewise, some authors use the term «flow graph» to refer strictly to the Coates flow graph.^[5][6] According to Henley & Williams:^[2]

«The nomenclature is far from standardized, and…no standardization can be expected in the foreseeable future.»

A designation «flow graph» that includes both the Mason graph and the Coates graph, and a variety of other forms of such graphs^[7] appears useful, and agrees with Abrahams and Coverley’s and with Henley and Williams’ approach.^[1][2]

A directed network – also known as a flow network – is a particular type of flow graph. A network is a graph with real numbers associated with each of its edges, and if the graph is a digraph, the result is a directed network.^[8] A flow graph is more general than a directed network, in that the edges may be associated with gains, branch gains or transmittances, or even functions of the Laplace operator s, in which case they are called transfer functions.^[2]

There is a close relationship between graphs and matrices and between digraphs and matrices.^[9] «The algebraic theory of matrices can be brought to bear on graph theory to obtain results elegantly», and conversely, graph-theoretic approaches based upon flow graphs are used for the solution of linear algebraic equations.^[10]

Deriving a flow graph from equations[edit]

An example of a flow graph connected to some starting equations is presented.

The set of equations should be consistent and linearly independent. An example of such a set is:^[2]

Consistency and independence of the equations in the set is established because the determinant of coefficients is non-zero, so a solution can be found using Cramer’s rule.

Using the examples from the subsection Elements of signal-flow graphs, we construct the graph In the figure, a signal-flow graph in this case. To check that the graph does represent the equations given, go to node x₁. Look at the arrows incoming to this node (colored green for emphasis) and the weights attached to them. The equation for x₁ is satisfied by equating it to the sum of the nodes attached to the incoming arrows multiplied by the weights attached to these arrows. Likewise, the red arrows and their weights provide the equation for x₂, and the blue arrows for x₃.

Another example is the general case of three simultaneous equations with unspecified coefficients:^[11]

To set up the flow graph, the equations are recast so each identifies a single variable by adding it to each side. For example:

Using the diagram and summing the incident branches into x₁ this equation is seen to be satisfied.

As all three variables enter these recast equations in a symmetrical fashion, the symmetry is retained in the graph by placing each variable at the corner of an equilateral triangle. Rotating the figure 120° simply permutes the indices. This construction can be extended to more variables by placing the node for each variable at the vertex of a regular polygon with as many vertices as there are variables.

Of course, to be meaningful the coefficients are restricted to values such that the equations are independent and consistent.

See also[edit]

• Coates graph
• Signal-flow graph

Further reading[edit]

• Richard A. Brualdi, Dragos Cvetkovic (2008). «Determinants». A Combinatorial Approach to Matrix Theory and Its Applications. Chapman & Hall/CRC. pp. 63 ff. ISBN 9781420082234. A discussion of the Coates and the Mason flow graphs.

References[edit]