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

   

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

   

Рисунок 6. Алгоритм FBB для примера на рис. 5 для значений r= 1/2, e = 0,15 и единичного веса каждой вершины. Алгоритм завершает работу после нахождения разреза (X2

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

== Применение ==

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