Учебное пособие 1587

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ОПИСАНИЯ МОДЕЛЕЙ КОНСТРУКЦИЙ СВТ

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

Определение:

Графом G называется математический объект, представленный двумя множествами вершин X и ребер U, соотносящихся друг с другом G=(X,U).

Или: это множество вершин X, отображающих самих себя ГХ в Х; G=(X,ГX).

Любую схему можно рассматривать как множество элементов Х={x1,...,xn}, их соединений Е={е1,...,еm} (цепей). Такое представление называется схемой соединений. Каждый элемент схемы имеет выводы - контакты C={c1,…,cs}. Внешние контакты для связи с другими схемами обозначается через C0. Два контакта считаются связанными, если они соединены одной электрической цепью.

Рассмотрим фрагмент схемы:

e2

x0

Пусть схема будет задана в виде графа

G = (X E C, U) ,

где X - множество элементов, E - множество цепей, C - множество контактов, U = F W - множество ребер, F - элементных, W - сигнальных. F определяет принадлежность элементам X контактов C: F={xi, сs}. W задает вхождение контактов C в цепи E: W={сs,ее}.

Введем условную вершину x0, объединяющую все внешние контакты:

x4

c4

c22

x2

c33 x3

c31

c03

e4

c0

x0

G = (X C E, U)

Граф G принято представлять двумя матрицами: A1 и A2 : A1 для E C; A2 для X C .

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

Матрица А1:

Матрица A2:

Каждый столбец содержит только одну единицу, т.е. контакт может принадлежать только одному элементу. В строке может быть несколько единиц, т.е. элемент может содержать несколько контактов.

Матрицы A1 и A2 содержат много нулей, поэтому их можно хранить в виде списков:

Для A1: e1: 1, 5 e2: 6, 9

e3: 7, 8, 12 e4: 2, 11

e5: 2, 10, 13, 14

e6: 4, 15

Граф можно задать в виде матрицы цепей T = {tij}n*s. Строки соответствуют элементам схемы, а столбцы - контактам.

Матрица не разряженная, компактная, но для ее составления необходима нумерация цепей.

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

Определение:

Двудольным называется граф, множество вершин которого разбито на два непересекающихся подмножества X'и X"

X' X"=X, X' X"= ,

так что каждое ребро соединяет вершину из X' с вершиной X".

Задание: Обозначение дуг графа продолжить самостоятельно.

Двудольному графу соответствует гиперфраф.

Определение:

Гиперграф задается множеством вершин и семейством подмножеств множества ребер.

x0

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

Ниже на рисунке представлена часть схемы

S1

S6 a2

S4 a3

Эта схема может быть представлена двудольным ориентированным

S8

С двудольным ориентированным графом можно связать матрицу B, описывающую отношение инцидентности логических элементов сигналам. Если каждому элементу ai сопоставить строку матрицы, а каждому сигналу Sj – столбец матрицы, то элемент bij матрицы следующим образом:

1, если S j есть выходной сигнал элемента ai ,

1, если S j есть входной сигнал элемента ai .

Матрица инцидентности для рассмотренного выше графа имеет вид

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

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

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

d++d- 15,

где d+ и d- обозначают соответственно число входящих и число исходящих дуг.

2. Степень логического элемента, такого, как И, ИЛИ, НЕ, не превышает некоторой величины (обычно 6 или 7):

d+ 2, d- 5.

3. Известны средние величины степеней вершин, соответствующие как сигналам, так и элементам: для большинства схем степень сигнальных вершин лежит в пределах 2,0 – 4,0, а степень логических элементов – в пределах 3,0 –

5,0.

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

Рассмотрим задачу компоновки по конструктивным единицам. В наиболее общем виде задачу компоновки можно поставить так.

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

1)подсистема первого уровня помещалась в стойку приемлемого размера;

2)промежуточные конструктивные единицы второго уровня могли служить основными элементами построения подсистем первого уровня;

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

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

Задан двудольный ориентированный граф системы. С каждой вершиной графа a свяжем две оценки S(a) и E(a), соответствующие физическому объему элемента и числу внешних сигналов, связаных с этим элементом. Каждому подмножеству А1 вершин поставим в соответствие две величины:

Множество внутренних сигналов Аi , обозначенное через I(Ai), состоит из всех вершин сигналов, инцидентных только узлам элементов из Ai. Множество внешних сигналов Ai , обозначаемое через В(Ai), состоит из вершин сигналов, инцидентных хотя бы одному элементу из Ai и одновременно являющихся входными или выходными сигналами элемента, не входящего в множество Ai и инцидентных вершине s , обозначим через d (s). Определим разбиение множества А всех вершин элементов как множество подмножеств А:

{AJ}, j=1,2,…,m,

такое, что