Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Применение операций над гиперграфами для компоновки схем ЭВМ

# 07, июль 2011
Файл статьи: О©╫О©╫О©...©╫_P.pdf (274.93Кб)
авторы: профессор Овчинников В. А., Пламадялов А. А.

 

 

УДК 004

УДК 004.3 + 519.6

МГТУ им. Н.Э. Баумана

vaovchinnikov@gmail.com

Задача компоновки состоит в определении состава конструктивных модулей ЭВМ. Рассмотрим решение задачи компоновки декомпозицией структуры объекта, например функциональной схемы, на части таким образом, чтобы критерий оптимальности достигал экстремального значения. Корректной моделью схемы является гиперграф, представленный в форме H (X, U, ГX, ГU, F1X) или кусок гиперграфа Hк(Xк, Uк, ГXк, ГUк, F1Xк), а задача декомпозиции состоит в разрезании H(X, U) или Hк(Xк, Uк) на совокупность B(Hlк) кусков Hlк(Xl, Ul), l = 1, L, где L – требуемое количество частей структуры. Будем считать, что моделью схемы является кусок гиперграфа Hк, который задан аналитически в форме Hк(Xк, Uк, ГXк, ГUк, F1Xк).

Описанные в литературе алгоритмы декомпозиции решают задачу разбиения множества вершин гиперграфа X или его куска Xк на совокупность непересекающихся подмножеств XlB(Xl) = {Xl}, l = 1, L таких, что:

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

– определить множество рёбер куска Ul, разделить его на подмножества внутренних Ulint и внешних Ulext;

– определить множества образов вершин ГXl и рёбер ГUl полученного куска относительно предикатов инцидентности и множество образов вершин F1Xl относительно предиката смежности;

– удалить множества Xl, Ul, ГXl, ГUl и F1Xl из множеств Xк, Uк, ГXк, ГUк и F1Xк соответственно.

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

Основными процедурами, используемыми проектировщиком при решении задачи компоновки, являются: выделение части схемы и удаление её из разрезаемой схемы. Данным проектным процедурам соответствуют операции формирования куска гиперграфа, объединение кусков и дополнения куска до гиперграфа или его куска [1, 2].

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

Hlк(Xl, Ul, Г1Xl, Г2Ul, F1Xl) := Hк(X, U, Г1X, Г2U, F1X) x,

которую в алгоритме будем записывать сокращённо как H1к := Hк x.

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

Таблица 1

Описание алгоритма в операциях над множествами

Описание алгоритма с использованием операций над графами

1. Включаем в формируемое множество Xl заранее заданную вершину:

Xl := {xq};

Формируем одновершинный кусок H1к := Hк  xq и удаляем его из модели схемы Hк := Hк \ H1к;

2. Определяем количество рёбер, соединяющих xq с X\ xq:

S0 := | Г1xq |;

Без изменений

3. Находим множество XК вершин – кандидатов на включение в Xl как множество вершин, смежных вершине xq:

XК := F1xq;

Без изменений

4. Организуем цикл определения для каждой вершины xi  XК множества Uiп и количества Δsi+ рёбер, приходящих в разрез между кусками, множество вершин которых Xl и X \ X, и Δsi- – количества рёбер уходящих из этого разреза:

Без изменений

4.1. Находим множество рёбер, инцидентных вершине x, и осуществляем инициализацию параметров Uiп, Δsi-, Δsi+:

Ui := Г1xi ; Uiп := Ø; Δsi- := 0 ; Δsi+ := 0;

Без изменений

4.2. Организуем цикл анализа рёбер множества Ui:

Без изменений

4.2.1. Определяем вершины, инцидентные ребру uj:

Xj := Г2u;

Без изменений

4.2.2. Проверяем условие = «истина». Если условие удовлетворяется, то переход к п. 4.2.3, иначе – к п. 4.2.4;

Без изменений

4.2.3. Подсчитываем показатель Δsi- := Δsi- +1 и переходим к п. 4.2

Без изменений

4.2.4. Проверяем условие . Если условие удовлетворяется, то переход к п. 4.2.5, иначе – к п. 4.2;

Без изменений

4.2.5. Запоминаем ребро, приходящее в разрез, и подсчитываем показатель Δsi+: Uiп := Uiп ۰ uj ; Δsi+ := Δsi+ + 1;

Без изменений

4.3. Подсчитываем показатель Δsi := Δsi+ - Δsi;

Без изменений

5. Находим вершину xt  XК, для которой Δs минимально:

Δst := min{Δsi  ΔS} ; xt st;

Без изменений

6. Подсчитываем количество рёбер в разрезе:

S0 := S0 + Δst ;

Без изменений

7. Проверяем ограничение на количество внешних выводов l -й части схемы S0 ≤ [sl]доп. Если условие выполняется, то переход к п. 8, иначе – к п. 12;

Без изменений

8. Включаем вершину в множество Xl := Xl  xt ;

Формируем одновершинный кусок H1к:= Hк ☼ xt , добавляем его к модели l-й части схемы Hlк := Hlк  H1к и удаляем из модели оставшейся схемы Hк := Hк \ H1к;

9. Поверяем условие |Xl| < nl, где nl – требуемое количество элементов l-й части схемы. Если условие выполняется, переход к п. 10, иначе – к п. 13;

Без изменений

10. Определяем множество вершин, инцидентных рёбрам множества Uiп:

Без изменений

11. Корректируем множество вершин XК := {XК  Xtп} \ xt и возвращаемся к п. 4;

Без изменений

12. Дальнейшее формирование невозможно из-за нарушения ограничений, переход к п. 14;

Без изменений

13. Вывод результатов –подмножество вершин Xl .

кусок гиперграфа Hlк.

14. Конец алгоритма.

 

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

Получим оценку вычислительной сложности процесса выделения одной подсхемы для обеих версий алгоритма. При использовании алгоритма в операциях над множествами вычислительная сложность процесса складывается из сложности алгоритма, операции формирования куска гиперграфа по множеству XlкHlк(Xl , Ul) := Hк(Xк, Uк) Xl и операции дополнения сформированного куска гиперграфа Hlк(Xl, Ul) до куска гиперграфа Hк(Xк, Uк) (модели оставшейся части схемы) Hк(Xк, Uк) := Hк(Xк, Uк) \ Hlк(Xl, Ul).

Асимптотическая оценка вычислительной сложности первой версии алгоритма получена в [3] и равна О(n5/2). Вычислительная сложность операции формирования куска гиперграфа равна О(m2) или О(n×m), так как |Xl| ограничена nl = n / const, |Ulm ¤ const, |Гxi| = const и |Гuj| = const (см. статья 2 в эл. Ж.). Учитывая, что для схем ЭВМ, представленных в функциональных элементах невысокой степени интеграции, n = m с точностью до константы, будем использовать оценку О(n2).

Для рассматриваемой задачи схемно-топологического проектирования средств ЭВТ асимптотическая оценка вычислительной сложности операции дополнения «в худшем» – существенно завышена. Представляется целесообразным получить реалистичную оценку. Анализ формального описания этой операции [2] показывает, что определяющий вклад в вычислительную сложность вносит определение образов ребер куска – результата операции. С учётом принятых обозначений соответствующее правило примет вид:

Так как |Ulint | < m и согласно закону Рента [4] |Ulext | ограничена n1/2, реалистичной оценкой вычислительной сложности операции дополнения будет О(n3/2). Приводя все оценки к переменной n, получаем:

Орез = О(n5/2) + О(n2) + О(n3/2) = О(n5/2).

Для реализации алгоритма с использованием операций над гиперграфами сопоставляемой с Орез величиной является вычислительная сложность самого алгоритма. Пунктами, имеющими различную вычислительную сложность, являются пункты 1 и 8.

Операция формирования одновершинного куска гиперграфа H1к(X1, U1) имеет вычислительную сложность О(1), дополнения его до куска HкО(n2×m) в худшем. Получим реалистичную оценку вычислительной сложности, учитывая, что в операции участвует одновершинный кусок гиперграфа. Для этого правило определения образов ребёр куска гиперграфа – результата этой операции запишем в виде:

Г{Uк\U1int}= {Гuj : uj  {Uкext ۰ U1}  Гuj \ X1 : uj  Uкext / uj  {Uк\U1int}, Гuj  ГUк}.

Так как |Uкext | ограничена n1/2, |U1 | < (uj) × (xi) = const и |X1к | = 1, асимптотическая оценка вычислительной сложности данной операции будет О(n3/2).

Вычислительная сложность операции объединения куска гиперграфа с одновершинным куском равна О(n). Все эти три операции в п. 8 выполняются (nl – 1) раз. Очевидно, что наибольший вклад в вычислительную сложность внесёт операция дополнения куска до куска в п. 8, который оценивается величиной О(n3/2) × О(n) = О(n5/2).

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

Напомним, что результатом работы алгоритма в варианте без операций над гиперграфами является подмножество вершин куска гиперграфа Xlк, а с использованием операций формирования, объединения и дополнения – аналитическое представление куска в форме Hlк(X, U, Г1X, Г2U, F1Xl).

Использование операций над гиперграфами рассмотрим также на примере формализации многоуровневого (блочно-иерархического) подхода, реализованного в программном комплексе компоновки hMeTiS [5]. Данный программный комплекс предназначен для разрезания гиперграфов большого размера и может быть использован при проектировании СБИС, баз данных, систем управления транспортом и т.п. Задача компоновки ставится так же, как и выше. В простейшей версии основная процедура реализует проектные операции укрупнения модели, её начального разрезания, улучшения этого разрезания и разукрупнения модели, организованные по следующей схеме.

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

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

Далее на каждом уровне детализации, начиная с последнего, выполняется разукрупнение вершин гиперграфа, разрезание улучшается итерационным алгоритмом. Эти две процедуры повторяются до тех пор, пока не будет получено разрезание исходного гиперграфа H(X, U) на две части, т. е. на два куска H1к(X1, U1) и H2к(X2, U2).

Описанная основная процедура применяется к полученным кускам гиперграфа до получения совокупности B(Hlк) кусков Hlк(Xl, Ul) с требуемым количеством вершин.

Для снижения размера гиперграфа могут использоваться алгоритмы уравновешенной двоичной или n-арной (неуравновешенной и уравновешенной) свёртки. При n-арной свёртке объединяются вершины не смежных рёбер. Результатом работы алгоритма свёртки на r-м уровне детализации является аналитическое представление гиперграфа H (Yr, Vr), где yjr = Yjr-1св  Yr-1 и множество кусков {Hjксв(Yjr-1св, Vjr-1св)}, j = 1, 2,…, |Y r| (после первого применения алгоритма свёртки, т.е. на первом уровне детализации, получается гиперграф H(Y1, V1), где yj1 = Xjсв = {xi, xk,…, xt}  X).

Рассмотрим вариант, когда результатом работы алгоритмов начального разрезания и итерационного улучшения являются два подмножества вершин, соответствующего уровня. Для работы всех указанных алгоритмов гиперграф целесообразно задавать множествами вершин, рёбер и их образами относительно предикатов инцидентности и смежности. Как было условлено в разделе 3 для краткости исходный гиперграф и гиперграфы каждого уровня детализации будем обозначать в виде H (X, U) и H (Yr, Vr).

Для формального описания процесса интерес представляют этапы, следующие за свёрткой. Для r-го уровня детализации это описание с использованием операций над гиперграфами представлено в табл. 2. Здесь после обозначения алгоритма в круглых скобках указан вход, а после символа «→» – результат работы алгоритма.

Таблица 2

N

Выполняемый алгоритм или операция

Комментарии

1.

AД(H (Yr, Vr)) {Y1r, Y2r}

Разбиение множества Yr на два подмножества случайным или последовательным алгоритмом

2.

H1к(Y1r, V1r) = H(Yr, Vr) ¤ Y1r,

H2к(Y2r, V2r) = H(Yr, Vr) ¤ Y2r

Получение полного аналитического представления кусков H1к и H2к на r-ом уровне детализации операцией формирования

3.

Получение аналитического представления кусков H1к и H2к на r–1-ом уровне детализации применением операции дефакторизации к вершинам множеств Y1r и Y2r

4.

H (Yr-1, Vr-1) = H1к(Y1r-1, V1r-1)  H2к(Y2r-1, V2r-1)

Получение аналитического представления гиперграфа на

r–1-ом уровне детализации операцией объединения кусков

5.

AИТ(H1к(Y1 r-1, V1r-1), H2к(Y2r-1, V2r-1))

{Y1уr-1, Y2уr-1}

Улучшение разрезания итерационным алгоритмом

6.

H1к(Y1r-1, V1r-1) = H(Yr-1, Vr-1) ¤ Y1уr-1,

H2к(Y2r-1, V2r-1) = H(Yr-1, Vr-1) ¤ Y2уr-1

Получение аналитического представления кусков H1к и H2к на r–1-ом уровне детализации операцией формирования после перестановок вершин

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

 

Литература

 

1. Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: Эл. Науч. Издание. – 2009. – ╧ 11.

2. Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: Эл. Науч. Издание. – 2009. – ╧ 12.

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

4. Савельев А. Я., Овчинников В.А. Конструирование ЭВМ и систем: Учеб. для вузов по спец. «Выч. маш., компл., сист. и сети.» – 2-е изд., перераб. и доп. – М.: Высш. шк.,  – 312с.

5. G. Karypis, R. Aggarwal, V Kumar, S. Shekhar, «Multilevel Hypergraph Partitioning: Applications in VLSI Domain», IEEE Trans. VLSI Syst., vol. 7, NO 1, March 1999, pp. 69-79.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)