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

   4.1. сколлапсировать все вершины в X в s;

   5.1. сколлапсировать все вершины в <math>\bar{X}</math> в t;

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

''Таблица соединений схемы'' определяется как диграф 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> и (2) размер разреза <math>net(X, \bar{X}) \;</math> минимален среди всех разрезов, удовлетворяющих условию (1). Если r = 1/2, задача превращается в задачу сбалансированного биразбиения с минимальным разрезом.

'''Сбалансированное биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока'''

3. Для каждой вершины <math>u \in {v; v_1, ..., v_l} \;</math>, инцидентной сетке n, добавить два ребра <math>(u, n_1) \;</math> и <math>(n_2, u) \;</math> в E'.

| Ave

! EIG1

! PB

В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [13]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими из десяти прогонов. В среднем FBB превзошел EIG1 и PARABOLI на 58,1% and 11,3%, соответственно. Для схемы S38417 субоптимальный результат FBB может быть улучшен за счет (1) увеличения количества прогонов и (2) применения техник кластеризации к схеме на базе знания имеющихся соединений (до выполнения разбиения).

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

В таблице 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 не сравнивалось, поскольку они исполнялись на разных рабочих станциях.

* [[Монтаж схемы]]

* [[Коррекция временных параметров схемы]]