4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 20 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Разбиение схемы является фундаментальной задачей в сфере проектирования и разработки СБИС. ''Сбалансированное биразбиение с минимальным разрезом'' представляет собой задачу разбиения схемы на два отдельных компонента с равными весами, такого, что количество сеток, соединяющих эти два компонента, минимально. Было показано, что задача сбалансированного биразбиения с минимальным разрезом является NP-полной [5]. Эта задача была решена при помощи эвристических алгоритмов, таких как методы итеративного улучшения Кернигана и Лина (эвристика K&L) [4, 11], алгоритм имитации отжига [10] и аналитические методы для рационального разреза [2, 7, 13, 15]. Несмотря на то, что техника нахождения максимального потока и минимального разреза [6, 8] представляется естественным способом поиска минимального разреза, она практически не использовалась в контексте разбиения схем. В работе [16] был предложен метод точного моделирования таблицы соединений сети (или, что эквивалентно, ее гиперграфа) при помощи транспортной сети, а также алгоритм нахождения сбалансированного биразбиения на основе неоднократного применения алгоритма нахождения максимального потока и минимального разреза. Представленный здесь алгоритм имеет ту же асимптотическую сложность, что и вычисление минимального потока. | Разбиение схемы является фундаментальной задачей в сфере проектирования и разработки СБИС. ''Сбалансированное биразбиение с минимальным разрезом'' представляет собой задачу разбиения схемы на два отдельных компонента с равными весами, такого, что количество сеток, соединяющих эти два компонента, минимально. Было показано, что задача сбалансированного биразбиения с минимальным разрезом является NP-полной [5]. Эта задача была решена при помощи эвристических алгоритмов, таких как методы итеративного улучшения Кернигана и Лина (эвристика K&L) [4, 11], алгоритм имитации отжига [10] и аналитические методы для рационального разреза [2, 7, 13, 15]. Несмотря на то, что техника нахождения [[Теорема_Форда_и_Фалкерсона|максимального потока и минимального разреза]] [6, 8] представляется естественным способом поиска минимального разреза, она практически не использовалась в контексте разбиения схем. В работе [16] был предложен метод точного моделирования таблицы соединений сети (или, что эквивалентно, ее [[гиперграф|гиперграфа]]) при помощи [[транспортная сеть|транспортной сети]], а также алгоритм нахождения сбалансированного биразбиения на основе неоднократного применения алгоритма нахождения максимального потока и минимального разреза. Представленный здесь алгоритм имеет ту же асимптотическую сложность, что и вычисление минимального потока. | ||
Строка 20: | Строка 20: | ||
4. '''if''' <math>w(X) < (1 - \epsilon)rW \;</math> | 4. '''if''' <math>w(X) < (1 - \epsilon)rW \;</math> | ||
4.1. сколлапсировать все вершины в X | 4.1. сколлапсировать все вершины в X с s; | ||
4.2. выбрать вершину <math>v \in \bar{X}</math>, смежную с C, и сколлапсировать ее с s; | 4.2. выбрать вершину <math>v \in \bar{X}</math>, смежную с C, и сколлапсировать ее с s; | ||
Строка 28: | Строка 28: | ||
5. '''if''' <math>w(X) > (1 + \epsilon)rW \;</math> | 5. '''if''' <math>w(X) > (1 + \epsilon)rW \;</math> | ||
5.1. сколлапсировать все вершины в <math>\bar{X}</math> | 5.1. сколлапсировать все вершины в <math>\bar{X}</math> с t; | ||
5.2. выбрать вершину <math>v \in X \;</math>, смежную с C, и сколлапсировать ее с t; | 5.2. выбрать вершину <math>v \in X \;</math>, смежную с C, и сколлапсировать ее с t; | ||
Строка 40: | Строка 40: | ||
Процедура инкрементного вычисления потока | Процедура инкрементного вычисления потока | ||
1. '''while''' <math>\exists</math> добавочный дополняющий путь из s в t | 1. '''while''' <math>\exists</math> добавочный дополняющий путь из s в t | ||
увеличить величину потока вдоль дополняющего пути; | |||
2. пометить все вершины u, такие, что <math>\exists</math> дополняющий путь из s в u; | 2. пометить все вершины u, такие, что <math>\exists</math> дополняющий путь из s в u; | ||
Строка 57: | Строка 58: | ||
''Таблица соединений схемы'' определяется как | ''Таблица соединений схемы'' определяется как [[орграф]] 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> | Говоря формально, пусть даны пропорция <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, задача превращается в задачу сбалансированного биразбиения с минимальным разрезом. | |||
== Основные результаты == | == Основные результаты == | ||
''' | '''Биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока''' | ||
Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | ||
Строка 71: | Строка 78: | ||
2. Для каждой сетки <math>n = (v; v_1, ..., v_l) \;</math> в N добавить две вершины <math>n_1 \;</math> и <math>n_2 \;</math> в V' и ''мостовое ребро'' <math>bridge(n) = (n_1, n_2) \;</math> в E'. | 2. Для каждой сетки <math>n = (v; v_1, ..., v_l) \;</math> в N добавить две вершины <math>n_1 \;</math> и <math>n_2 \;</math> в V' и ''мостовое ребро'' <math>bridge(n) = (n_1, n_2) \;</math> в E'. | ||
3. Для каждой вершины <math>u \in {v; v_1, ..., v_l} \;</math>, инцидентной сетке n, добавить два ребра <math>(u, n_1) \;</math> и <math>(n_2, u) \;</math> в E'. | 3. Для каждой вершины <math>u \in \{ v; v_1, ..., v_l \} \;</math>, инцидентной сетке n, добавить два ребра <math>(u, n_1) \;</math> и <math>(n_2, u) \;</math> в E'. | ||
4. Положить s источником N', а t – стоком N'. | 4. Положить s источником N', а t – стоком N'. | ||
Строка 92: | Строка 99: | ||
[[Файл:CP_6.png]] | [[Файл:CP_6.png]] | ||
Рисунок 6. Алгоритм FBB для примера на рис. 5 для значений r = 1/2, <math>\epsilon</math> = 0,15 и единичного веса каждой вершины. Алгоритм завершает работу после нахождения разреза <math>(X_2, \bar{X_2}) \;</math>. | Рисунок 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) | Таблица 1. Сравнение алгоритмов SN, PFM3 и FBB (r = 1/2, <math>\epsilon \;</math> = 0,1) | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! Схема | ! colspan="4" | Схема | ||
! Средний размер сетевого разреза | ! colspan="3" | Средний размер сетевого разреза | ||
! Биразбиение FBB | ! Биразбиение FBB | ||
! Улучшение (%) | ! colspan="2" | Улучшение (%) | ||
|- | |- | ||
! Название | ! Название | ||
Строка 113: | Строка 120: | ||
! PFM3 | ! PFM3 | ||
! FBB | ! FBB | ||
! | ! (отношение) | ||
! К SN | ! К SN | ||
! К PFM3 | ! К PFM3 | ||
Строка 138: | Строка 145: | ||
| 28,5 | | 28,5 | ||
| 19,3 | | 19,3 | ||
|- | |||
| C3540 | |||
| 1667 | |||
| 1695 | |||
| 2,7 | |||
| 90,3 | |||
| 71,0 | |||
| 79,8 | |||
| 1:1,11 | |||
| 11,6 | |||
| -12,4 | |||
|- | |||
| C7552 | |||
| 3466 | |||
| 3565 | |||
| 2,7 | |||
| 44,3 | |||
| 81,8 | |||
| 42,9 | |||
| 1:1,08 | |||
| 3,2 | |||
| 47,6 | |||
|- | |||
| S838 | |||
| 478 | |||
| 511 | |||
| 2,6 | |||
| 27,1 | |||
| 21,0 | |||
| 14,7 | |||
| 1:1,04 | |||
| 45,8 | |||
| 30,0 | |||
|- | |||
| Среднее | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| 1:1,10 | |||
| 24,5 | |||
| 19,0 | |||
|} | |} | ||
Таблица 2. Сравнение алгоритмов EIG1, PB и FBB (r = 1/2, <math>\epsilon \;</math> = 0,1). Все допускают отклонение <math>\le 10%</math> | |||
{| class="wikitable" | |||
|- | |||
! colspan="4" | Схема | |||
! colspan="3" | Лучший размер сетевого разреза | |||
! colspan="2" | Улучшение (%) | |||
! FBB продолж. | |||
|- | |||
! Название | |||
! Вентили и триггеры | |||
! Сетки | |||
! Средн. степ. | |||
! EIG1 | |||
! PFB | |||
! FBB | |||
! К EIG1 | |||
! К PB | |||
! (сек) | |||
|- | |||
| S1423 | |||
| 731 | |||
| 743 | |||
| 2,7 | |||
| 23 | |||
| 16 | |||
| 13 | |||
| 43,5 | |||
| 18,8 | |||
| 1,7 | |||
|- | |||
| S9234 | |||
| 5808 | |||
| 5805 | |||
| 2,4 | |||
| 227 | |||
| 74 | |||
| 70 | |||
| 69,2 | |||
| 5,4 | |||
| 55,7 | |||
|- | |||
| S13207 | |||
| 8696 | |||
| 8606 | |||
| 2,4 | |||
| 241 | |||
| 91 | |||
| 74 | |||
| 69,3 | |||
| 18,9 | |||
| 100,0 | |||
|- | |||
| S15850 | |||
| 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, привязаны к <math>n_1 \;</math>, а также к ним привязана <math>n_2 \;</math> в N'. Следовательно, построение транспортной сети симметрично относительно всех вершин, инцидентных сетке. Это построение можно провести также в случае, если таблица соединений представлена гиперграфом. | |||
Очевидно, что N' является [[сильно связный орграф|сильно связным орграфом]]. Это свойство является определяющим для сведения задачи нахождения двунаправленного минимального сетевого разреза к задаче разреза с минимальной пропускной способностью, учитывающей только пропускную способность прямых ребер. | |||
'''Теорема 1. N имеет разрез величиной не более C в том и только том случае, если N' имеет разрез с пропускной способностью не более C.''' | |||
Следствие 1. Пусть <math>(X', \bar{X'}) \;</math> – разрез с минимальной пропускной способностью C в N'. Пусть <math>N_{cut} = \{ n | bridge(n) \in (X', \bar{X'}) \} \;</math>. Тогда <math>N_{cut} = (X, \bar{X}) \;</math> является минимальным сетевым разрезом в N и <math>|N_{cut}| = C \;</math>. | |||
Следствие | Следствие 2. Минимальный сетевой разрез в схеме N = (V, E) можно найти за время O(|V| |E|). | ||
'''Эвристика для сбалансированного биразбиения с минимальным разрезом''' | |||
Эвристика для сбалансированного биразбиения с минимальным разрезом | |||
Вначале неоднократно применяется эвристический алгоритм вычисления максимального потока и минимального разреза, затем выполняется сбалансированное биразбиение потока (FBB) для нахождения r-сбалансированного биразбиения, минимизирующего количество пересекаемых сеток. Затем разрабатывается эффективная реализация FBB, имеющая ту же асимптотическую сложность, что и однократное вычисление минимального потока. Ради упрощения представления алгоритм FBB излагается здесь в формулировке для исходной схемы, а не для транспортной сети, построенной из этой схемы. Эвристический алгоритм представлен на рис. 1, на рис. 6 приведен пример использования. | Вначале неоднократно применяется эвристический алгоритм вычисления максимального потока и минимального разреза, затем выполняется сбалансированное биразбиение потока (FBB) для нахождения r-сбалансированного биразбиения, минимизирующего количество пересекаемых сеток. Затем разрабатывается эффективная реализация FBB, имеющая ту же асимптотическую сложность, что и однократное вычисление минимального потока. Ради упрощения представления алгоритм FBB излагается здесь в формулировке для исходной схемы, а не для транспортной сети, построенной из этой схемы. Эвристический алгоритм представлен на рис. 1, на рис. 6 приведен пример использования. | ||
В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [ ]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими | В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [13]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими для десяти прогонов. В среднем FBB превзошел EIG1 и PARABOLI на 58,1% and 11,3%, соответственно. Для схемы S38417 субоптимальный результат FBB может быть улучшен за счет (1) увеличения количества прогонов и (2) применения техник кластеризации к схеме на базе знания имеющихся соединений (до выполнения разбиения). | ||
Строка 188: | Строка 329: | ||
Теорема 2. Алгоритм FBB имеет временную сложность O( | '''Теорема 2. Алгоритм FBB имеет временную сложность O(|V| |E|) для связной схемы N = (V, E).''' | ||
Теорема 3. Количество итераций и финальный размер сетевого разреза представляют собой невозрастающие функции от | '''Теорема 3. Количество итераций и финальный размер сетевого разреза представляют собой невозрастающие функции от <math>\epsilon \;</math>.''' | ||
На практике алгоритм FBB завершается намного быстрее, чем указывает временная сложность для наихудшего случая, как показано в разделе «Экспериментальные результаты». Теорема 3 позволяет повысить эффективность FBB и качество разбиения для больших значений | На практике алгоритм FBB завершается намного быстрее, чем указывает временная сложность для наихудшего случая, как показано в разделе «Экспериментальные результаты». Теорема 3 позволяет повысить эффективность FBB и качество разбиения для больших значений <math>\epsilon \;</math>. Это неверно для других подходов к разбиению – таких как эвристика K&L. | ||
== Применение == | == Применение == | ||
Разбиение схемы является фундаментальной задачей в сфере проектирования СБИС и автоматизации разработки. Алгоритм FBB представляет собой первое эффективное прогнозируемое решение задачи сбалансированного разбиения схемы с минимальным разрезом. Установлена прямая зависимость эффективности и качества решения, производимого алгоритмом, от коэффициента отклонения | Разбиение схемы является фундаментальной задачей в сфере проектирования СБИС и автоматизации разработки. Алгоритм FBB представляет собой первое эффективное прогнозируемое решение задачи сбалансированного разбиения схемы с минимальным разрезом. Установлена прямая зависимость эффективности и качества решения, производимого алгоритмом, от коэффициента отклонения <math>\epsilon \;</math>. Алгоритм можно легко расширить для применения к сеткам с различными весами, присваивая вес сетки ее мостовому ребру в транспортной сети. K-стороннее разбиение с минимальным разрезом для K > 2 можно получить при помощи рекурсивного применения FBB либо положив r = 1/K и затем используя FBB для поиска разбиений по одному. Метод прямого решения задачи с использованием потоков приводится в [12]. Кластеризацию схемы перед разбиением с использованием данных о связях или расчетов времени можно легко встроить в алгоритм FBB, рассматривая кластер как вершину. Для дальнейшей настройки решения можно использовать эвристические техники на базе эвристики K&L или алгоритма имитации отжига с низкой температурой. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Алгоритм FBB был внедрен в SIS/MISII [1] и протестирован на наборе больших тестовых схем ISCAS и MCNC на рабочей станции SPARC 10 с процессором с тактовой частотой 36 МГц и 32 МБ памяти. | Алгоритм FBB был внедрен в SIS/MISII [1] и протестирован на наборе больших тестовых схем ISCAS и MCNC на рабочей станции SPARC 10 с процессором с тактовой частотой 36 МГц и 32 МБ памяти. | ||
В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [ ]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB | |||
В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [3]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB выполнялся 10 раз с различными случайным образом выбранными s и t. За единственным исключением FBB показал себя лучше SN и PFM3 на пяти схемах. В среднем FBB удалось найти биразбиение с количеством пересечений сеток на 24,5% и 19,0% меньше, чем SN и PFM3, соответственно. Время выполнения алгоритмов SN, PFM3 и FBB не сравнивалось, поскольку они выполнялись на разных рабочих станциях. | |||
== См. также == | == См. также == | ||
* [[Приближенное решение задачи о максимальном потоке]] | * [[Приближенное решение задачи о максимальном потоке]] | ||
* [[ | * [[Компоновка схемы]] | ||
* [[ | * [[Ресинхронизация схемы]] | ||
* [[Максимальный разрез]] | * [[Максимальный разрез]] | ||
* [[Минимальная бисекция]] | * [[Минимальная бисекция]] |
правок