Разбиение интегральной схемы (1132268), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Этогонедостаточно для применения к схемам, т.к. размеры блоковнеодинаковы.Разбиение должно быть строго сбалансировано. Длярасширения нужно ввести фиктивные изолированные вершины.Алгоритм не может быть применен к гиперграфам.Сложность алгоритма слишком высока.Эвристика включает в себя неопределенность, что можетприводить к выбору плохих обменов и попаданию в локальныйминимум.Алгоритм эффективен для плотных графов (с большим числомребер у вершины).Математические методы проектированиятопологии СБИСАлгоритм Федуччи-Маттеуса (FM, 1982)Главные отличия FM от KL:Перемещается один модуль за одну итерацию,что позволяет получать несбалансированныерешенияПонятие gain расширено до гиперграфовСпециальный способ для выбора вершинснижает вычислительную сложность алгоритмаСложность алгоритма – O(n)Математические методы проектированиятопологии СБИСАлгоритм Федуччи-Маттеуса(определения)Определение 9: External hyperedge cost - длявершины viA:Определение 10: Internal hyperedge cost - длявершины viA:E (i )  c(e)eEext ,iI (i)  c ( e)eEint,i Eext,i={eE|{vi}=eF\A} – множество гиперребер, которые будутудалены после переноса вершины; Eint,i={eE|vie и eB=} – множество добавленных гиперреберМатематические методы проектированиятопологии СБИСАлгоритм Федуччи-МаттеусаАлгоритмprocedure FMbegin Инициализировать D while перемещения вершин возможны do Выбрать разрешенную вершину v Обновить структуру данных с учетом перемещения v Расширить список перемещений Вычислить префикс последовательности перемещений,достигающих минимального сеченияendМатематические методы проектированиятопологии СБИСПример (1)1Начальноеразбиение:{A,B};00ab-11cdeg2fh30Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8);Математические методы проектированиятопологии СБИСПример(2)1-20ab-31cegd2fh-2Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); gМатематические методы проектированиятопологии СБИСПример(3)-1-2ab-1-2cdeg0fh0Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4);Математические методы проектированиятопологии СБИСПример(4)-1-2ab-1-2cegdfh-2Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); fМатематические методы проектированиятопологии СБИСПример(5)-3-2a0bcegdfh0Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); f, c (5);Математические методы проектированиятопологии СБИСПример(6)-1a0bcdegfh0Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); f, c (5); bМатематические методы проектированиятопологии СБИСПример(7)-1abcegdfh0Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); f, c (5); b, e (7);Математические методы проектированиятопологии СБИСПример(8)abcdegfh0Перемещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); f, c (5); b, e (7); aМатематические методы проектированиятопологии СБИСПример(9)abcegdfhПеремещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); f, c (5); b, e (7); a, h (8)Математические методы проектированиятопологии СБИСПример(10)abВыбирается наилучшийвариантcegdfhПеремещенные вершины (и стоимость разреза после перемещения каждойпары):none (8); g, d (4); f, c (5); b, e (7); a, h (8)Математические методы проектированиятопологии СБИСПример(11)abПроцесс итеративногоулучшения повторяется.Улучшение не найдено.cegМатематические методы проектированиятопологии СБИСdhfFM: недостатки алгоритмаFM порождает многонеопределенныхвариантов, также как и KL.Вершины, которые FM неможет различить: v1 ? v2Какую вершину выгоднеепереместить?V7e16V1e25e3V4V3Математические методы проектированиятопологии СБИСV2e4.

Характеристики

Список файлов лекций