4430
правок
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями
Материал из WEGA
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока (посмотреть исходный код)
Версия от 14:35, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 64: | Строка 64: | ||
(1) <math>(1 - \epsilon) rW \le W(X) \le (1 + \epsilon) rW \;</math>; | (1) <math>(1 - \epsilon) rW \le W(X) \le (1 + \epsilon) rW \;</math>; | ||
(2) размер разреза <math>net(X, \bar{X}) \;</math> минимален среди всех разрезов, удовлетворяющих условию (1). | (2) размер разреза <math>net(X, \bar{X}) \;</math> минимален среди всех разрезов, удовлетворяющих условию (1). | ||
| Строка 69: | Строка 70: | ||
== Основные результаты == | == Основные результаты == | ||
''' | '''Биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока''' | ||
Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | ||
| Строка 77: | Строка 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'. | ||
| Строка 178: | Строка 179: | ||
| 30,0 | | 30,0 | ||
|- | |- | ||
| | | Среднее | ||
| | | | ||
| | | | ||
| Строка 208: | Строка 209: | ||
! PFB | ! PFB | ||
! FBB | ! FBB | ||
! EIG1 | ! К EIG1 | ||
! PB | ! К PB | ||
! (сек) | ! (сек) | ||
|- | |- | ||
| Строка 322: | Строка 323: | ||
В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [13]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими | В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [13]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими для десяти прогонов. В среднем FBB превзошел EIG1 и PARABOLI на 58,1% and 11,3%, соответственно. Для схемы S38417 субоптимальный результат FBB может быть улучшен за счет (1) увеличения количества прогонов и (2) применения техник кластеризации к схеме на базе знания имеющихся соединений (до выполнения разбиения). | ||
| Строка 337: | Строка 338: | ||
== Применение == | == Применение == | ||
Разбиение схемы является фундаментальной задачей в сфере проектирования СБИС и автоматизации разработки. Алгоритм FBB представляет собой первое эффективное прогнозируемое решение задачи сбалансированного разбиения схемы с минимальным разрезом. Установлена прямая зависимость эффективности и качества решения, производимого алгоритмом, от коэффициента отклонения <math>\epsilon \;</math>. Алгоритм можно легко расширить для применения к сеткам с различными весами, присваивая вес сетки ее мостовому ребру в транспортной сети. K-стороннее разбиение с минимальным разрезом для K > 2 можно получить при помощи рекурсивного применения FBB либо положив r = 1/K и затем используя FBB для поиска разбиений по одному. Метод прямого решения задачи с использованием потоков приводится в [12]. Кластеризацию схемы перед разбиением | Разбиение схемы является фундаментальной задачей в сфере проектирования СБИС и автоматизации разработки. Алгоритм 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 со свободными перемещениями, как описано в [3]. На каждой схеме 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 не сравнивалось, поскольку они выполнялись на разных рабочих станциях. | |||
== См. также == | == См. также == | ||
* [[Приближенное решение задачи о максимальном потоке]] | * [[Приближенное решение задачи о максимальном потоке]] | ||
* [[ | * [[Компоновка схемы]] | ||
* [[ | * [[Ресинхронизация схемы]] | ||
* [[Максимальный разрез]] | * [[Максимальный разрез]] | ||
* [[Минимальная бисекция]] | * [[Минимальная бисекция]] | ||
