НАУКА и ОБРАЗОВАНИЕ

УДК 004.3:519.6                                                                                  

Г.С.  Иванова

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Перечисленные структурные модели строятся на базе одного или двух универсумов. В первом варианте в основе модели структуры – универсум вершин 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.