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

Разбиение схемы является фундаментальной задачей в сфере проектирования и разработки СБИС. ''Сбалансированное биразбиение с минимальным разрезом'' представляет собой задачу разбиения схемы на два отдельных компонента с равными весами, такого, что количество сеток, соединяющих эти два компонента, минимально. Было показано, что задача сбалансированного биразбиения с минимальным разрезом является NP-полной [5].  Эта задача была решена при помощи эвристических алгоритмов, таких как методы итеративного улучшения Кернигана и Лина (эвристика K&L) [4, 11], алгоритм имитации отжига [10] и аналитические методы для рационального разреза [2, 7, 13, 15]. Несмотря на то, что техника нахождения максимального потока и минимального разреза [6, 8] представляется естественным способом поиска минимального разреза, она практически не использовалась в контексте разбиения схем. В работе [16] был предложен метод точного моделирования таблицы соединений сети (или, что эквивалентно, ее гиперграфа) при помощи транспортной сети, а также алгоритм нахождения сбалансированного биразбиения на основе неоднократного применения алгоритма нахождения максимального потока и минимального разреза. Представленный здесь алгоритм имеет ту же асимптотическую сложность, что и вычисление минимального потока.

   4.1. сколлапсировать все вершины в X в s;

   5.1. сколлапсировать все вершины в <math>\bar{X}</math> в t;

   1. '''while''' <math>\exists</math> добавочный дополняющий путь из s в t, увеличить величину потока вдоль дополняющего пути;

''Таблица соединений схемы'' определяется как диграф N = (V, E), где V – множество вершин, представляющих логические вентили и регистры, а E – множество ребер, представляющих провода между вентилями и регистрами. Каждая вершина <math>v \in V \;</math> имеет вес <math>w(v) \in R^+ \;</math>. Общий вес подмножества <math>U \subseteq V \;</math> определяется как <math>w(U) = \sum_{v \in U} w(v) \;</math>. W = w(V) обозначает полный вес схемы. Сетка <math>n = (v, v_1, ..., v_l) \;</math> представляет собой множество ребер, исходящих из вершины v в N. Пусть даны две вершины s и t в N; ''s-t-разрез'' (далее для краткости просто «[[разрез]]») <math>(X, \bar{X}) \;</math> графа N представляет собой биразбиение вершин V, такое, что <math>s \in X \;</math> и <math>t \in \bar{X} \;</math>. ''Сетевым разрезом'' <math>net(X, \bar{X}) \;</math> разреза является множество сеток в N, инцидентных вершинам одновременно в <math>X \;</math> и <math>\bar{X} \;</math>. Разрез <math>(X, \bar{X}) \;</math> является ''минимальным сетевым разрезом'', если значение <math>|net(X, \bar{X})| \;</math> минимально среди всех s-t-разрезов N. На рис. 3 представлены сетка <math>a = (r_1; g_1, g_2) \;</math>, сетевые разрезы <math>net(X, \bar{X}) = \{ b, e \} \;</math> и <math>net(Y, \bar{Y}) = \{ c, a, b, e \} \;</math> и минимальный сетевой разрез <math>(X, \bar{X}) \;</math>.

Говоря формально, пусть даны пропорция <math>r \;</math> и коэффициент отклонения <math>\epsilon \;</math>. Задача ''r-сбалансированного биразбиения с минимальным разрезом'' заключается в нахождении биразбиения <math>(X, \bar{X}) \;</math> таблицы соединений N, такого, что (1) <math>(1 - \epsilon) rW \le W(X) \le (1 + \epsilon) rW \;</math> и (2) размер разреза <math>net(X, \bar{X}) \;</math> минимален среди всех разрезов, удовлетворяющих условию (1). Если r = 1/2, задача превращается в задачу сбалансированного биразбиения с минимальным разрезом.

'''Сбалансированное биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока'''

3. Для каждой вершины <math>u \in {v; v_1, ..., v_l} \;</math>, инцидентной сетке n, добавить два ребра <math>(u, n_1) \;</math> и <math>(n_2, u) \;</math> в E'.

Рисунок 6. Алгоритм FBB для примера на рис. 5 для значений r = 1/2, <math>\epsilon</math> = 0,15 и единичного веса каждой вершины. Алгоритм завершает работу после нахождения разреза <math>(X_2, \bar{X_2}) \;</math>.

Таблица 1. Сравнение алгоритмов SN, PFM3 и FBB (r = 1/2, <math>\epsilon</math> = 0,1)

| Ave

Таблица 2. Сравнение алгоритмов EIG1, PB и FBB (r = 1/2, <math>\epsilon</math> = 0,1). Все допускают отклонение <math>\le 10%</math>

! FBB продолж. (сек)

! EIG1

! PB

!  

| S1

S1 5850 10310 10310 2,4 215 91 67 68,8 26,4 96,5

S35932 18081 17796 2,7 105 62 49 53,3 21,0 2808

S38584 20859 20593 2,7 76 55 47 38,2 14,5 1130

S38417 24033 23955 2,4 121 49 58 52,1 -18,4 2736

Среднее 58,5 11,3

Заметим, что все вершины, инцидентные сетке n, привязаны к n1, а также к ним привязана n2 в N0. Следовательно, построение транспортной сети симметрично относительно всех вершин, инцидентных сетке. Это построение можно провести также в случае, если таблица соединений представлена гиперграфом.

Эвристика для сбалансированного биразбиения с минимальным разрезом

В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [ ]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими из десяти прогонов. В среднем FBB превзошел EIG1 и PARABOLI на 58,1% and 11,3%, соответственно. Для схемы S38417 субоптимальный результат FBB может быть улучшен за счет (1) увеличения количества прогонов и (2) применения техник кластеризации к схеме на базе знания имеющихся соединений (до выполнения разбиения).

Теорема 2. Алгоритм FBB имеет временную сложность O(jVj jEj) для связной схемы N = (V; E).

Теорема 3. Количество итераций и финальный размер сетевого разреза представляют собой невозрастающие функции от e.

На практике алгоритм FBB завершается намного быстрее, чем указывает временная сложность для наихудшего случая, как показано в разделе «Экспериментальные результаты». Теорема 3 позволяет повысить эффективность FBB и качество разбиения для больших значений e. Это неверно для других подходов к разбиению – таких как эвристика K&L.

Разбиение схемы является фундаментальной задачей в сфере проектирования СБИС и автоматизации разработки. Алгоритм FBB представляет собой первое эффективное прогнозируемое решение задачи сбалансированного разбиения схемы с минимальным разрезом. Установлена прямая зависимость эффективности и качества решения, производимого алгоритмом, от коэффициента отклонения e. Алгоритм можно легко расширить для применения к сеткам с различными весами, присваивая вес сетки ее мостовому ребру в транспортной сети. K-стороннее разбиение с минимальным разрезом для K > 2 можно получить при помощи рекурсивного применения FBB либо положив r = UK и затем используя FBB для поиска разбиений по одному. Метод прямого решения задачи с использованием потоков приводится в [ ]. Кластеризацию схемы перед разбиением согласно данным о связях или расчетам времени можно легко встроить в алгоритм FBB, рассматривая кластер как вершину. Эвристические решения на базе эвристики K&L или алгоритма имитации отжига с низкой температурой могут использоваться для дальнейшей настройки решения.

В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [ ]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB исполнялся 10 раз с различными случайным образом выбранными s и t. За единственным исключением FBB показал себя лучше SN и PFM3 на пяти схемах. В среднем FBB удалось найти биразбиение с количеством пересечений сеток на 24,5% и 19,0% меньше, чем SN и PFM3, соответственно. Время исполнения алгоритмов SN, PFM3 и FBB не сравнивалось, поскольку они исполнялись на разных рабочих станциях.

* [[Монтаж схемы]]

* [[Коррекция временных параметров схемы]]