4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
Строка 338: | Строка 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 или алгоритма имитации отжига с низкой температурой. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == |
правок