Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
Модели объектов задач структурного синтеза
#12 декабрь 2006 УДК 004.3:519.6Г.С. ИвановаФормализованное решение задач структурного синтеза заключается в выполнении комплекса необходимых преобразований моделей объектов. Информация, имеющаяся по структурным моделям объектов в литературе, не обладает необходимой для создания языка описания алгоритмов решения этих задач степенью полноты и детализации, что особенно касается редко применяемых и мало изученных моделей, таких как гиперграфы, ультраграфы и иерархическая модель. Поэтому необходимо: · определить набор моделей, используемых для представления объектов, процесса решения и результатов задач структурного синтеза; · установить соответствие между компонентами объекта и элементами модели; · сопоставить связи компонентов объекта отношениям элементов моделей; · а также, выполнить анализ элементов и свойств используемых моделей. При проектировании технических средств вычислительной техники решаются следующие классы задач структурного синтеза [2]: моделирования, позиционирования, коммутации/маршрутизации, декомпозиции/композиции и установления идентичности. Для решения этих задач независимо от природы объектов в моделях необходимо отобразить следующую информацию: для задач моделирования и установления идентичности структур – компоненты структуры, связи между ними и функциональное назначение, как элементов, так и связей между ними; для задач позиционирования – компоненты структуры, существующие или возможные связи между ними, метрические параметры и топологические свойства компонентов, связей и монтажного пространства, а также, возможно, функциональное назначение компонентов; для задач коммутации/маршрутизации – для каждой связи (цепи): компоненты структуры, их количество, характеристики (в том числе и положение элемента в монтажной области) и топологические свойства, способы или правила соединения элементов, а также характеристики и топологические свойства линий коммутации; для задач декомпозиции/композиции – компоненты структуры, связи между ними, функциональное назначение, метрические характеристики и топологические свойства элементов структуры и связей между ними. Для решения указанных задач структурного синтеза в этом случае предлагаются [1, 2] модели в виде ориентированного или неориентированного графа или мультиграфа, а также ориентированного и неориентированного гиперграфа или ультраграфа. Так неориентированные графы используют в качестве моделей при решении задач коммутации и декомпозиции, когда направления прохождения сигналов несущественны и компоненты объекта соединяются только попарно. При необходимости учесть множественность связей используют мультиграфы. Ориентированные графы и мультиграфы позволяют отобразить логику функционирования схем. Такое представление необходимо при решении задач моделирования, покрытия и идентификации. Однако при переходе от схемы к модели соответствие между цепями схемы и ребрами графа не является взаимнооднозначным. В этом случае необходимая информация о логике функционирования отображается посредством взвешивания вершин и дуг указанных моделей. В качестве весов при этом могут выступать идентификаторы цепей, сигналов, номера контактов и т. п. [2, 3]. В общепринятой трактовке гиперграфа n-местные отношения обладают свойством симметричности, поэтому гиперграф позволяет показать принадлежность элементов цепям, не фиксируя порядка их соединения. Для задач композиции/декомпозиции и позиционирования гиперграф также обеспечивает точную оценку по модели числа связей между элементами схемы или ее частями. Однако такой гиперграф не позволяет отобразить информацию о порядке соединения выводов при решении задачи трассировки. Ориентированный гиперграф позволяет указать эту информацию [1]. Ультраграф в основном используют при решении задач моделирования и установления идентичности схем, так как эта модель позволяет указать источники и приемники цепи, соединяющей более двух элементов, получить точную оценку числа связей и не задавая порядка их подключения к цепи (см. таблицу 1). Таблица 1 – Модели задач структурного синтеза
При проектировании средств вычислительной техники задачи структурного синтеза могут решаться не отдельно, а в некоторых последовательностях. Так, например, проектирование устройства на ПЛИС предполагает функциональный синтез по описанию, размещение (выбор одного из элементов с фиксированными позициями), коммутацию элементов и моделирование (верификацию) схемы. Таким образом, целесообразно иметь обобщенную модель, которая позволяет отображать всю имеющуюся информацию. Такой моделью для перечисленных классов задач является ультраграф с кратными дугами и отношением порядка на ультрадугах. Перечисленные структурные модели строятся на базе одного или двух универсумов. В первом варианте в основе модели структуры – универсум вершин X = {xi}, i Î, каждый элемент которого xi сопоставлен некоторому блоку или элементу схемы эi. Связи элементов при этом представляют в виде отношений на универсуме X. Так цепи, соединяющей два элемента, в модели с учетом направления сигнала сопоставляют бинарное отношение порядка на универсуме Х, обозначаемое упорядоченной парой – (xi, xj) = {xi, {xi, xj}}. Той же цепи в модели без учета направления сигнала сопоставляют бинарное отношение, обладающее свойством симметричности, которое можно представить в виде подмножества {xi, xj}. Во втором варианте для построения модели используют два универсума – вершин X = {xi}, i Î и ребер U = {uj}, j Î. Каждый элемент второго универсума uj сопоставляют линии связи элементов (цепи) cj. Структура объекта при этом задается отношениями на универсумах X и U. Проанализируем представление компонентов объектов в моделях обоих типов (см. таблицы 2 и 3). Таблица 2 – Представление компонентов объекта в структурных моделях
* – Параметры линии связи в модели с одним универсумом сопоставляют элементам отношений, отображающим данную связь. Таблица 3 – Представление связей в структурных моделях
* Связь n элементов отображается мультимножеством, если существуют вершины, которые входят в гиперребра или ультрадуги несколько раз. Анализ показывает, что модель с двумя универсумами, которая позволяет явно отображать в структурной модели линии связи, требует представления в памяти дополнительного универсума и отображает каждую связь элементами нескольких отношений, и, соответственно, при выполнении операций над ней приходится корректировать большее количество отношений. Однако отсутствие информации о ребрах в модели с одним универсумом сокращает возможный набор операций над ней. Так в этой модели нельзя выполнить операцию нахождения ребер, инцидентных конкретной вершине, поскольку идентификация ребер отсутствует. Однако, операция нахождения смежных вершин, в такой модели выполняется за один шаг, в отличие от модели с двумя универсумами, в которой для этого необходимо сначала определить ребра, инцидентные вершине, а затем вершины, инцидентные найденным ребрам. Очевидно, что модель с двумя универсумами всегда может быть преобразована в модель с одним универсумом. Для обыкновенных графов возможно и обратное преобразование. Это связано с тем, что модель с одним универсумом не содержит информации о линиях связи, а восстановить эту информацию перечислением ребер можно только для двуместных отношений ориентированных и неориентированных графов. Таким образом, модель с двумя универсумами целесообразно применять при наличии в алгоритме операций, требующих идентификации, как вершин, так и ребер. А для снижения вычислительной сложности выполнения операций со смежными вершинами и ребрами дополнительно можно определить отношения смежности, как на множестве вершин, так и на множестве ребер. Однако, следует иметь в виду, что избыточное описание, снижая вычислительную сложность алгоритма, повысит его емкостную сложность. В рассмотренных выше моделях не нашел отражения тот факт, что проектирование средств вычислительной техники выполняется с использованием блочно-иерархического подхода, в соответствии с которым компоненты объекта i-го уровня проектирования представляют собой соединение некоторого множества компонентов i-1-го уровня детализации. Например, при решении задачи композиции/декомпозиции вершине гиперграфа соответствует множество вершин куска гиперграфа и внутренних связей между ними, полученного при решении соответствующей задачи на предыдущем уровне. Таким образом, появляется необходимость применения иерархических моделей. Однако эти модели в литературе практически не упоминаются и на настоящий момент почти не исследованы. Построим иерархические модели на одном и двух универсумах и исследуем их свойства. Как указано выше, в иерархической модели помимо связей между элементами одного уровня необходимо отобразить связи элементов соседних уровней. В модели с одним универсумом такая связь отображается множеством бинарных отношений элементов i-1-го уровня элементу i-го уровня детализации: {(,)/Î} Ì Ri Ì ´ , (1) где , – вершины i-го и i-1-го уровня соответственно; – подмножество вершин i-1-го уровня, соответствующее , т. е. k-ой вершине i-го уровня; , – множества вершин i-го и i-1-го уровня соответственно; Ri – отношение вхождения между вершинами i-1-го и i-го уровней. При этом = X, |X| = n, = {/k = }, || = ni , 0 < ni £ n, (2) (", Î B()) (Ç= Æ ) , =, где ni – количество вершин 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.
Публикации с ключевыми словами: графовые модели, синтез правил, иерархические модели Публикации со словами: графовые модели, синтез правил, иерархические модели Смотри также: Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|