4430
правок
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями
Материал из WEGA
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока (посмотреть исходный код)
Версия от 23:13, 6 апреля 2017
, 6 апреля 2017→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Разбиение гиперграфа; разбиение таблицы соединений == Пост…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Разбиение схемы является фундаментальной задачей в сфере проектирования и разработки СБИС. Сбалансированное биразбиение с минимальным разрезом представляет собой задачу разбиения схемы на два отдельных компонента с равными весами, такого, что количество сеток, соединяющих эти два компонента, минимально. Было показано, что задача сбалансированного биразбиения с минимальным разрезом является NP-полной [5]. Эта задача была решена при помощи эвристических алгоритмов, таких как методы итеративного улучшения Кернигана и Лина (эвристика K&L) [4, 11], алгоритм имитации отжига [10] и аналитические методы для рационального разреза [2, 7, 13, 15]. Несмотря на то, что техника нахождения максимального потока и минимального разреза [6, 8] представляется естественным способом поиска минимального разреза, она практически не использовалась в контексте разбиения схем. В работе [ ] был предложен метод точного моделирования таблицы соединений сети (или, что эквивалентно, ее гиперграфа) при помощи сети потока, а также алгоритм нахождения сбалансированного биразбиения на основе неоднократного применения алгоритма нахождения максимального потока и минимального сечения. Представленный здесь алгоритм имеет ту же асимптотическую сложность, что и вычисление минимального потока. | Разбиение схемы является фундаментальной задачей в сфере проектирования и разработки СБИС. ''Сбалансированное биразбиение с минимальным разрезом'' представляет собой задачу разбиения схемы на два отдельных компонента с равными весами, такого, что количество сеток, соединяющих эти два компонента, минимально. Было показано, что задача сбалансированного биразбиения с минимальным разрезом является NP-полной [5]. Эта задача была решена при помощи эвристических алгоритмов, таких как методы итеративного улучшения Кернигана и Лина (эвристика K&L) [4, 11], алгоритм имитации отжига [10] и аналитические методы для рационального разреза [2, 7, 13, 15]. Несмотря на то, что техника нахождения максимального потока и минимального разреза [6, 8] представляется естественным способом поиска минимального разреза, она практически не использовалась в контексте разбиения схем. В работе [16] был предложен метод точного моделирования таблицы соединений сети (или, что эквивалентно, ее гиперграфа) при помощи сети потока, а также алгоритм нахождения сбалансированного биразбиения на основе неоднократного применения алгоритма нахождения максимального потока и минимального сечения. Представленный здесь алгоритм имеет ту же асимптотическую сложность, что и вычисление минимального потока. | ||
Алгоритм | Алгоритм сбалансированного биразбиения на базе потока (Flow-Balanced-Bipartition, FBB) | ||
1. выбрать пару вершин s и t в N; | 1. выбрать пару вершин s и t в N; | ||
2. найти минимальный сетевой разрез C в N; | 2. найти минимальный сетевой разрез C в N; | ||
пусть X – подсхема, достижимая из s по дополняющим путям в сети потока, а X – остальная часть схемы; | пусть X – подсхема, достижимая из s по дополняющим путям в сети потока, а <math>\bar{X}</math> – остальная часть схемы; | ||
3. if (1 - | 3. '''if''' <math>(1 - \epsilon)rW \le w(X) \le (1 + \epsilon)rW \;</math> | ||
вернуть C в качестве ответа; | вернуть C в качестве ответа; | ||
4. | 4. '''if''' <math>w(X) < (1 - \epsilon)rW \;</math> | ||
4.1. сколлапсировать все вершины в X в s; | 4.1. сколлапсировать все вершины в X в s; | ||
4.2. выбрать вершину v | 4.2. выбрать вершину <math>v \in \bar{X}</math>, смежную с C, и сколлапсировать ее с s; | ||
4.3. перейти к 1; | 4.3. перейти к 1; | ||
5. | 5. '''if''' <math>w(X) > (1 + \epsilon)rW \;</math> | ||
5.1. сколлапсировать все вершины в X в t; | 5.1. сколлапсировать все вершины в <math>\bar{X}</math> в t; | ||
5.2. выбрать вершину v | 5.2. выбрать вершину <math>v \in X \;</math>, смежную с C, и сколлапсировать ее с t; | ||
5.3. перейти к 1; | 5.3. перейти к 1; | ||
