УДК 004.3:519.6                                                                                  

Г.С.  Иванова

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

·       определить набор моделей, используемых для представления объектов, процесса решения и результатов задач структурного синтеза;

·       установить соответствие между компонентами объекта и элементами модели;

·       сопоставить связи компонентов объекта отношениям элементов моделей;

·       а также, выполнить анализ элементов и свойств используемых моделей.

При проектировании технических средств вычислительной техники решаются следующие классы задач структурного синтеза [2]: моделирования, позиционирования, коммутации/маршрутизации, декомпозиции/композиции и установления идентичности.

Для решения этих задач независимо от природы объектов в моделях необходимо отобразить следующую информацию:

для задач моделирования и установления идентичности структур – компоненты структуры, связи между ними и функциональное назначение, как элементов, так и связей между ними;

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

для задач коммутации/маршрутизации – для каждой связи (цепи): компоненты структуры, их количество, характеристики (в том числе и положение элемента в монтажной области) и топологические свойства, способы или правила соединения элементов, а также характеристики и топологические свойства линий коммутации;

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

Для решения указанных задач структурного синтеза в этом случае предлагаются [1, 2] модели в виде ориентированного или неориентированного графа или мультиграфа, а также ориентированного и неориентированного гиперграфа или ультраграфа.

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

Ориентированные графы и мультиграфы позволяют отобразить логику функционирования схем. Такое представление необходимо при решении задач моделирования, покрытия и идентификации. Однако при переходе от схемы к модели соответствие между цепями схемы и ребрами графа не является взаимнооднозначным. В этом случае необходимая информация о логике функционирования отображается посредством взвешивания вершин и дуг указанных моделей. В качестве весов при этом могут выступать идентификаторы цепей, сигналов, номера контактов и т. п. [2, 3].

В общепринятой трактовке гиперграфа n-местные отношения обладают свойством симметричности, поэтому гиперграф позволяет показать принадлежность элементов цепям, не фиксируя порядка их соединения. Для задач композиции/декомпозиции и позиционирования гиперграф также обеспечивает точную оценку по модели числа связей между элементами схемы или ее частями. Однако такой гиперграф не позволяет отобразить информацию о порядке соединения выводов при решении задачи трассировки. Ориентированный гиперграф позволяет указать эту информацию [1].

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

Таблица 1 – Модели задач структурного синтеза

Класс задач	Отображаемая информация	Модели	Ограничения	Примечания
Моделирование и установление идентичности	Компоненты, связи и их функциональное назначение	1. Ориентированный граф с взвешенными  вершинами и дугами	При отсутствии кратных связей	При соединении более чем двух элементов соответствие между цепями схемы и дугами графа не является взаимнооднозначным, что требует задания информации о цепи в виде весов дуг
		2. Ориентированный мультиграф с взвешенными  вершинами и дугами	При наличии кратных связей
		3. Ультраграф с взвешенными  вершинами	При соединении более чем двух элементов
Позиционирование (размещение)	Компоненты, связи, их метрические параметры и топологические свойства	Неориентированный граф с взвешенными вершинами и ребрами	При попарном соединении элементов
		Гиперграф с взвешенными вершинами и ребрами	При соединении более чем двух элементов одной цепью
Позиционирование (назначение)	Компоненты, возможные связи, их метрические параметры и функциональное назначение	Неориентированный или ориентированный двудольный граф с взвешенными вершинами
Коммутация	Для каждой связи (цепи): компоненты, их количество, характеристики и топологические свойства	Неориентированный граф с взвешенными  вершинами и дугами	Если рассматривается одна цепь
		Гиперграф с взвешенными  вершинами и ребрами	Если рассматривается множество цепей	При решении задачи трассировки не позволяет отобразить информацию о порядке соединения выводов
		Ориентированный гиперграф	Если рассматривается множество цепей и необходимо отобразить информацию о порядке соединения выводов
Композиция/ декомпозиция	Компоненты, связи, их функциональное назначение, метрические характеристики и топологические свойства компонентов	Неориентированный граф с взвешенными  вершинами и дугами	При попарном соединении элементов
		Гиперграф с взвешенными  вершинами и ребрами	При соединении более чем двух элементов одной цепью	Обеспечивает точную оценку по модели числа связей между частями объекта

 

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

Перечисленные структурные модели строятся на базе одного или двух универсумов. В первом варианте в основе модели структуры – универсум вершин X = {x_i}, i Î, каждый элемент которого x_i сопоставлен некоторому блоку или элементу схемы э_i. Связи элементов при этом представляют в виде отношений на универсуме X. Так цепи, соединяющей два элемента, в модели с учетом направления сигнала сопоставляют бинарное отношение порядка на универсуме Х, обозначаемое упорядоченной парой – (x_i, x_j) = {x_i, {x_i, x_j}}. Той же цепи в модели без учета направления сигнала сопоставляют бинарное отношение, обладающее свойством симметричности, которое можно представить в виде подмножества {x_i, x_j}.

Во втором варианте для построения модели используют два универсума – вершин X = {x_i}, i Î и ребер U = {u_j}, j Î. Каждый элемент второго универсума u_j сопоставляют линии связи элементов (цепи) c_j. Структура объекта при этом задается отношениями на универсумах X и U.

Проанализируем представление компонентов объектов  в моделях обоих типов (см. таблицы 2 и 3).

Таблица 2 – Представление компонентов объекта в структурных моделях

* – Параметры линии связи в модели с одним универсумом сопоставляют элементам отношений, отображающим данную связь.

Таблица 3 – Представление связей в структурных моделях

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

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

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

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

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

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

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

{(,)/Î} Ì  Rⁱ Ì ´ ,                                                     (1)

где , – вершины i-го и i-1-го уровня соответственно;

– подмножество вершин i-1-го уровня, соответствующее , т. е. k-ой вершине i-го уровня;

, – множества вершин i-го и i-1-го уровня соответственно;

 Rⁱ – отношение вхождения между вершинами i-1-го и i-го уровней.

При этом

= X, |X| = n,

= {/k = }, || = nⁱ , 0 < nⁱ £ n,                                                            (2)

(", Î B()) (Ç= Æ ) , =,

где nⁱ – количество вершин i-го уровня,

      B() – разбиение множества вершин i-го уровня, т. е. B() = {/ k = }.

Связи между вершинами i-1 уровня, представляемые в данной модели элементами двуместных и n-местных отношений, при переходе на i-й уровень разделятся на связи внутри множества вершин и связи между вершинами разных множеств. Первые на следующем уровне рассматриваться не будут, а вторые – отобразят связи между вершинами следующего уровня. Таким образом, вершины i-го уровня будут находиться:

1) в бинарном симметричном отношении смежности {,} Î, если

·       связанные бинарным симметричным отношением смежности вершины i-1-го уровня попали в разные подмножества, т. е. {,}Î, Î , Î, r¹q;

·       связанные n-арным симметричным отношением смежности вершины i-1-го уровня оказались в двух подмножествах и, т. е. {,…,,…,} = {{,…}.{,…,}} = {.}Î, Í, Í, r¹q;

2) в бинарном отношении смежности (,) Î, если

·       связанные  бинарным отношением смежности вершины i-1-го уровня попали в разные подмножества, т. е. (,)Î,Î, Î, r¹q, где ,  – подмножества вершин i-1 уровня, которым на i-м уровне соответствуют вершины , ;

·       связанные n-арным отношением смежности вершины i-1-го уровня оказались в двух подмножествах: первая часть – в , а оставшаяся  – в , т. е. (,…,,…,) = (,…). (,…,) = (,)Î, Í, Í, r¹q;  

·       связанные  бинарным отношением смежности подмножества , вершин i-1-го уровня оказались в разных подмножествах, т. е. (,)Î, Í, Í, r¹q;

3) в n-арном симметричном отношении смежности {,,, …} Î, если связанные таким же отношением на i-1-м уровне вершины попали в более чем два подмножества (см. рисунок 1, а), т. е.

{,,,,…} = {{,…},{,…},{,…},…} = {,,,…}Î,

Í, Í, Í, … и |{,, , …} |>2;

4) в n-арном отношении смежности (,,,…) Î, если связанные таким же отношением на i-1-м уровне вершины попали в более чем два подмножества, т. е.

(, …,, …, ,,…) = ((, …),(, …),(, …), …) = (,,,…)Î,

 Í, Í, Í,…,  |{,, ,…} |>2;

5) в бинарном отношении смежности подмножеств вершин источникови вершин-приемников: (,)Î, если связанные таким же отношением на i-1-м уровне вершины-источникиÍ {,,,…} и вершины-приемники Í {,,,…} не попали в два разных подмножества или попали в большее количество подмножеств (см. рисунок 1, б), т. е. (,) Îи  ($Î B())(Ç¹Æ &ǹÆ) или

Ç (È) ¹Æ, Ç (È) ¹Æ, Ç (È) ¹Æ, …,

 |{,, ,…}| > 2.

Рисунок 1 – Связи между вершинами i-го и i-1-го уровней:

а – n-арное симметричное отношение смежности вершин уровня;  б – бинарное отношение смежности подмножеств вершин уровня

В модели с двумя универсумами каждой вершине  i-го уровня также сопоставлено подмножество вершин. Соответствующая иерархическая связь отображается множеством симметричных отношений (1) при условии (2).

Вершины и подмножество ребер i-1-го уровня, инцидентных этим вершинам, образуют кусок графа такой, что (,) Î B(), где B() = {(, )/ k = } – разрезание графа (, ) на куски, каждый из которых включает множество вершин Î B() = {/ k = }. Причем часть ребер куска  являются внутренними , поскольку связывают вершины куска, а часть – внешними , так как связывают куски, т. е. =È.

Внутренние ребра куска на следующий уровень не отображаются, а внешние – = находятся во взаимнооднозначном соответствии с множеством ребер i-го уровня: «. Следовательно, ребра i-1-го и i-го уровней находятся в отношении инъекции:

(,) Î Ì ´ или  (,) Î ()^-1 Ì ´,

где  , – ребра i-1 и i-го уровней соответственно,

        , ()^-1 – прямая и обратная функции соответствия, причем функция – частичная, т. е. определена не на всем множестве , а только на множество внешних ребер кусков , в то время как функция ()^-1 – тотальная.

Тип ребра при отображении на следующий уровень может измениться. Так в модели с двумя универсумами две вершины i-го уровня связаны:

1) дугой , такой что {(, ) Î, (,) Î}, если

·       связанные дугой на i-1-м уровне вершины попали в разные куски, т. е. {(, ) Î, (,) Î}, Î, Î, r¹q;

·       вершины гипердуги  i-1-го уровня оказались в двух кусках: первая часть – в, а оставшаяся – в, т. е.

({, } Î ) = ({, } Î ).({, } Î ), Î,  Î, Î, r¹q;

·       вершины-источники ультрадуги  i-1-го уровня оказались в одном куске, а вершины-приемники – в другом, т. е.

{(, ) Î} È {(, ) Î}, Î, Î, r¹q;

2) ребром , таким что {{, } Î, {,} Î}, если

·       связанные ребром на i-1-м уровне вершины попали в разные куски, т. е.

{{, } Î , {,} Î}, где Î, Î, r¹q;

·       вершины гиперребра i-1-го уровня оказались в двух кусках и, т. е.

{{,} Î } = {, }Î È{, }Î , где Î, Î, Î, r¹q;

3) гиперребром , таким что {{, }Î }, если связанные гиперребром на i-1-м уровне вершины попали в более чем два куска (см. рисунок 1, а), т. е.

{{,}Î}={,}ÎÈ{, }ÎÈ{, }ÎÈ…,

где Î,  Î, Î, Î и |{,, , …} |>2;

4) гипердугой , такой что ({, } Î ), если связанные гипердугой на i-1-м уровне вершины попали в более чем два куска, т. е.

({, } Î ) = ({, } Î ).({, } Î ).({, } Î ). …,

где Î,  Î, Î,Î и  |{,, ,…} |>2;

5) ультрадугой , такой что {(, ) Î} È {(, ) Î}, если  связанные ультрадугой на  i-1-м уровне вершины-источникиÍ{,,,…} и вершины‑приемники Í {,,,…} не попали в два разных куска или попали большее чем в два куска (см. рисунок 1, б), т. е.

{(, ) Î} È {(, ) Î},

где Î, Î и  ($Ì)(Ç¹Æ &ǹÆ) или

Ç (È) ¹Æ &Ç (È) ¹Æ &Ç (È) ¹Æ & …,

 |{,, ,…}|>2.

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

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

 

Литература

1. Бершадский А.М. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. – Саратов: Изд-во Саратовского ун-та, 1983.  

2. Овчинников В.А. Автоматизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.

3. Овчинников В.А. Конструирование ЭВМ и систем: Учеб. для вузов. – М.: Высш. шк., 1989.