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

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

         пусть X – подсхема, достижимая из s по дополняющим путям в сети потока, а <math>\bar{X}</math> – остальная часть схемы;

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

Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. Сетевой поток N0 = (V0, E0) строится из N = (V, E) следующим образом (см. рис. 4 и 5):

Рисунок 4. Моделирование сетки в N в сети потока N'

Рисунок 5. Сеть потока для рис. 3

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

Вначале неоднократно применяется эвристический алгоритм вычисления максимального потока и минимального разреза, затем выполняется сбалансированное биразбиение потока (FBB) для нахождения r-сбалансированного биразбиения, минимизирующего количество пересекаемых сеток. Затем разрабатывается эффективная реализация FBB, имеющая ту же асимптотическую сложность, что и однократное вычисление минимального потока. Ради упрощения представления алгоритм FBB излагается здесь в формулировке для исходной схемы, а не для сети потока, построенной из этой схемы. Эвристический алгоритм представлен на рис. 1, на рис. 6 приведен пример использования.

При реализации алгоритма FBB был выбран метод коллапсирования вершин, а не более постепенный (например, из [9]), чтобы гарантировать, что пропускная способность разреза всегда отражает реальный размер сетевого разреза. При выборе вершины на шагах 4.2 и 5.2 задан порог R для количества вершин в несколлапсированной подсхеме. Вершина выбирается случайным образом, если количество вершин больше R. В противном случае проверяются все вершины, смежные с C, и выбирается та, коллапс которой порождает минимальный сетевой разрез наименьшего размера. Прямолинейная реализация шага 2, заключающаяся в вычислении максимального потока начиная с нулевого, приведет к резкому росту временной сложности. Вместо этого сохраняется значение потока в сети потока и исследуется дополнительный поток для насыщения мостовых ребер минимального сетевого разреза между двумя итерациями. Процедура представлена на рис. 2. Вначале сеть потока сохраняет функцию потока, вычисленную на предыдущей итерации. Поскольку вычисление максимального потока при помощи метода приращения путей нечувствительно к изначальным знамениям потока и порядку нахождения дополняющих путей, вышеописанная процедура корректно находит максимальный поток с тем же значением потока, что и у максимального потока, вычисленного в коллапсированной сети потока из нулевого значения.

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