Наука и Образование: научно-техническое издание: Применение операций над гиперграфами для компоновки схем ЭВМ

УДК 004

УДК 004.3 + 519.6

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

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

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

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

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

– определить множества образов вершин ГX_l и рёбер ГU_l полученного куска относительно предикатов инцидентности и множество образов вершин F₁X_l относительно предиката смежности;

– удалить множества X_l, U_l, ГX_l, ГU_l и F₁X_l из множеств X^к, U^к, ГX^к, ГU^к и F₁X^к соответственно.

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

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

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

H_l^к(X_l, U_l, Г₁X_l, Г₂U_l, F₁X_l) := H^к(X, U, Г₁X, Г₂U, F₁X) ☼ x_q,

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

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

Таблица 1

Описание алгоритма в операциях над множествами	Описание алгоритма с использованием операций над графами
1. Включаем в формируемое множество X_l заранее заданную вершину: X_l := {x_q};	Формируем одновершинный кусок H₁^к := H^к ☼ x_q и удаляем его из модели схемы H^к := H^к \ H₁^к;
2. Определяем количество рёбер, соединяющих x_q с X\ x_q: S₀ := \| Г₁x_q \|;	Без изменений
3. Находим множество X_К вершин – кандидатов на включение в X_l как множество вершин, смежных вершине x_q: X_К := F₁x_q;	Без изменений
4. Организуем цикл определения для каждой вершины x_i X_К множества U_i^п и количества Δs_i⁺ рёбер, приходящих в разрез между кусками, множество вершин которых X_l и X \ X_l, и Δs_i^- – количества рёбер уходящих из этого разреза:	Без изменений
4.1. Находим множество рёбер, инцидентных вершине x_i, и осуществляем инициализацию параметров U_i^п, Δs_i^-, Δs_i⁺: U_i := Г₁x_i ; U_i^п := Ø; Δs_i^- := 0 ; Δs_i⁺ := 0;	Без изменений
4.2. Организуем цикл анализа рёбер множества U_i:	Без изменений
4.2.1. Определяем вершины, инцидентные ребру u_j: X_j := Г₂u_j;	Без изменений
4.2.2. Проверяем условие = «истина». Если условие удовлетворяется, то переход к п. 4.2.3, иначе – к п. 4.2.4;	Без изменений
4.2.3. Подсчитываем показатель Δs_i^- := Δs_i^- +1 и переходим к п. 4.2	Без изменений
4.2.4. Проверяем условие . Если условие удовлетворяется, то переход к п. 4.2.5, иначе – к п. 4.2;	Без изменений
4.2.5. Запоминаем ребро, приходящее в разрез, и подсчитываем показатель Δs_i⁺: U_i^п := U_i^п ۰ u_j ; Δs_i⁺ := Δs_i⁺ + 1;	Без изменений
4.3. Подсчитываем показатель Δs_i := Δs_i⁺ - Δs_i;	Без изменений
5. Находим вершину x_t X_К, для которой Δs минимально: Δs_t := min{Δs_i ΔS} ; x_t ↔ s_t;	Без изменений
6. Подсчитываем количество рёбер в разрезе: S₀ := S₀ + Δs_t;	Без изменений
7. Проверяем ограничение на количество внешних выводов l -й части схемы S₀ ≤ [s_l]_доп. Если условие выполняется, то переход к п. 8, иначе – к п. 12;	Без изменений
8. Включаем вершину в множество X_l := X_l x_t;	Формируем одновершинный кусок H₁^к:= H^к☼ x_t, добавляем его к модели l-й части схемы H_l^к := H_l^к H₁^к и удаляем из модели оставшейся схемы H^к := H^к \ H₁^к;
9. Поверяем условие \|X_l\| < n_l, где n_l – требуемое количество элементов l-й части схемы. Если условие выполняется, переход к п. 10, иначе – к п. 13;	Без изменений
10. Определяем множество вершин, инцидентных рёбрам множества U_i^п:	Без изменений
11. Корректируем множество вершин X_К := {X_К X_t^п} \ x_t и возвращаемся к п. 4;	Без изменений
12. Дальнейшее формирование невозможно из-за нарушения ограничений, переход к п. 14;	Без изменений
13. Вывод результатов –подмножество вершин X_l.	кусок гиперграфа H_l^к.
14. Конец алгоритма.

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

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

Асимптотическая оценка вычислительной сложности первой версии алгоритма получена в [3] и равна О(n^5/2). Вычислительная сложность операции формирования куска гиперграфа равна О(m²) или О(n×m), так как |X_l| ограничена n_l = n / const, |U_l| = m ¤ const, |Гx_i| = const и |Гu_j| = const (см. статья 2 в эл. Ж.). Учитывая, что для схем ЭВМ, представленных в функциональных элементах невысокой степени интеграции, n = m с точностью до константы, будем использовать оценку О(n²).

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

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

О_рез = О(n^5/2) + О(n²) + О(n^3/2) = О(n^5/2).

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

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

Г{U^к\U₁_int}= {Гu_j : u_j {U^к_ext ۰ U₁} Гu_j \ X₁ : u_j U^к_ext / u_j {U^к\U₁_int}, Гu_j ГU^к}.

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

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

Напомним, что результатом работы алгоритма в варианте без операций над гиперграфами является подмножество вершин куска гиперграфа X_l^к, а с использованием операций формирования, объединения и дополнения – аналитическое представление куска в форме H_l^к(X_l, U_l, Г₁X_l, Г₂U_l, F₁X_l).

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

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

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

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

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

Для снижения размера гиперграфа могут использоваться алгоритмы уравновешенной двоичной или n-арной (неуравновешенной и уравновешенной) свёртки. При n-арной свёртке объединяются вершины не смежных рёбер. Результатом работы алгоритма свёртки на r-м уровне детализации является аналитическое представление гиперграфа H(Y^r, V^r), где y_j^r = Y_j^r^-1_св Y^r^-1 и множество кусков {H_j^к_св(Y_j^r^-1_св, V_j^r^-1_св)}, j = 1, 2,…, |Y^r| (после первого применения алгоритма свёртки, т.е. на первом уровне детализации, получается гиперграф H(Y¹, V¹), где y_j¹ = X_j_св = {x_i, x_k,…, x_t} X).

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

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

Таблица 2

N	Выполняемый алгоритм или операция	Комментарии
1.	A_Д(H(Y^r, V^r)) → {Y₁^r, Y₂^r}	Разбиение множества Y^r на два подмножества случайным или последовательным алгоритмом
2.	H₁^к(Y₁^r, V₁^r) = H(Y^r, V^r) ¤ Y₁^r, H₂^к(Y₂^r, V₂^r) = H(Y^r, V^r) ¤ Y₂^r	Получение полного аналитического представления кусков H₁^к и H₂^к на r-ом уровне детализации операцией формирования
3.		Получение аналитического представления кусков H₁^к и H₂^к на r–1-ом уровне детализации применением операции дефакторизации к вершинам множеств Y₁^r и Y₂^r
4.	H(Y^r^-1, V^r-¹) = H₁^к(Y₁^r^-1, V₁^r-¹) H₂^к(Y₂^r-¹, V₂^r-¹)	Получение аналитического представления гиперграфа на r–1-ом уровне детализации операцией объединения кусков
5.	A_ИТ(H₁^к(Y₁^r^-1, V₁^r^-1), H₂^к(Y₂^r^-1, V₂^r^-1)) → {Y_1у^r^-1, Y_2у^r^-1}	Улучшение разрезания итерационным алгоритмом
6.	H₁^к(Y₁^r-1, V₁^r-1) = H(Y^r-1, V^r-1) ¤ Y₁_у^r-1, H₂^к(Y₂^r-1, V₂^r-1) = H(Y^r-1, V^r-1) ¤ Y₂_у^r-1	Получение аналитического представления кусков H₁^к и H₂^к на 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.

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

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

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