VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 1 Глава 2 – Разбиение графов с приложениями Авторы книги: Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu Физическое Проектирование СБИС: от Разбиения Графов до Оптимизации Временных Характеристик

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 2 Глава 2 – Разбиение графов с приложениями 2.1Введение 2.2Терминология 2.3Цели оптимизации 2.4Алгоритмы разбиения (гипер)графов Алгоритм Кернигана-Лина (KL) Улучшенные варианты алгоритм Кернигана-Лина Алгоритм Фидуччи-Маттейсеса (FM) 2.5Многоуровневые алгоритмы Кластеризация Многоуровневое разбиение (гипер)графов 2.6Разбиеие систем на несколько кристаллов ПЛИС для эмуляции

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 3 1.2Маршруты проектирования СБИС ENTITY test is port a: in bit; end ENTITY test; DRC LVS ERC Проектирование схем Функциональное проектирование Физическое проектирование Физическая верификация Производство Спецификация систем Архитектурное проектирование Коммерческий продукт Упаковка и тестирование Планированние кристалла Размещение Трассировка сигналов Разбиение Временная оптимизация Синтез синхросигналов © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 4 Схема: Разрез c a : четыре внешних соединения Разрез c a Разрез c b Блок AБлок B Блок AБлок B Разрез c b : два внешних соединения 2.1Введение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 5 2.2Терминология Граф G 2 : Вершины 1, 2, 6. Граф G 1 : Вершины 3, 4, 5. Разрезанные рёбра Разрез: (1,3), (2,3), (5,6), Блок (компонента) Ячейки

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 6 2.3Задачи оптимизации Дан граф G(V,E) с |V| вершин и |E| рёбер где каждая вершина v V и каждое ребро e E. У каждой вершины есть площадь s(v) и каждое ребро имеет стоимость или вес w(e). Требуется разбить граф G на k непересекающихся подграфов так чтобы минимизировать данные функции и сохранить отношения инцидентности.

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 7 2.3Задачи оптимизации Оптимизируемые функции Количество соединений между всеми компонентами Ограничения на размеры компонент (суммарная площадь, количесто соединений) Нарушение баланса размера компонент Многие такие задачи NP-трудные Быстрые эвристики были разработаны в 1970s и 1980s. Они позволияют найти неплохие решения важных задач. 7

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Алгоритмы разбиение (гипер)графов 2.1Введение 2.2Терминология 2.3Задачи оптимизации 2.4Алгоритмы разбиение (гипер)графов Алгоритм Кернигана-Лина (KL) Улучшенные варианты алгоритма Кернигана-Лина Алгоритм Фидуччи-Маттейсеса (FM) 2.5Многоуровневые алгоритмы Кластеризация Многоуровневое разбиение (гипер)графов 2.6Разбиение систем на несколько кристаллов ПЛИС для эмуляции

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 9 Даётся: Граф с 2n вершинами одинакого веса Найти: Разбиение графа на два непересекающихся подмножества A и B, |A| = |B| = n, с минимальной стоимостью разреза Пример: n = 4 Блок A Блок B Алгоритм Кернигана-Лина (KL)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 10 Стоимость D(v) передвижения вершины v D(v) = |E c (v)| – |E nc (v)|, где E c (v) множество разрезаных рёбер инцидентных к v, E nc (v) множество разрезаных рёбер не инцидентных к v. Вершины с высокой стоимостью (D > 0) желательно передвинуть, а вершины с низкой стоимостью (D < 0) лучше оставить в той же компоненте Вершина 3: D(3) = 3-1=2 Вершина 7: D(7) = 2-1= Алгоритм Кернигана-Лина (KL) - терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 11 Прирост связанный с обменом пары вершин a и b g = D(a) + D(b) - 2 * c(a,b), где D(a), D(b) – это стоимости передвижения вершин a, b c(a,b) – это вес соединения между a и b: Если существует ребро между a и b, то c(a,b) = вес ребра (например 1), иначе, c(a,b) = 0. Прирост g указывает насколько полезен обмен данных двух вершин Чем выше прирост g, тем сильнее сократится разрез Алгоритм Кернигана-Лина (KL) - терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 12 Прирост связанный с обменом пары вершин a и b g = D(a) + D(b) - 2 * c(a,b), где D(a), D(b) – это стоимости передвижения вершин a, b c(a,b) – это вес соединения между a и b: Если существует ребро между a и b, то c(a,b) = вес ребра (например 1), иначе, c(a,b) = Алгоритм Кернигана-Лина (KL) - терминология Node 3: D(3) = 3-1=2 Node 7: D(7) = 2-1= g (3,7) = D(3) + D(7) - 2 * c(a,b) = – 2 = 1 => Обмен вершин 3 и 7 сократит разрез на 1 ребро

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 13 Прирост связанный с обменом пары вершин a и b g = D(a) + D(b) - 2 * c(a,b), где D(a), D(b) – это стоимости передвижения вершин a, b c(a,b) – это вес соединения между a и b: Если существует ребро между a и b, то c(a,b) = вес ребра (например 1), иначе, c(a,b) = Алгоритм Кернигана-Лина (KL) - терминология Node 3: D(3) = 3-1=2 Node 7: D(7) = 2-1=1 g (3,5) = D(3) + D(5) - 2 * c(a,b) = – 0 = 3 => Обмен вершин 3 и 5 сократит разрез на 3 ребра

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 14 Прирост обмена пар вершин a и b Ищем пары вершин a и b такие чтобы их обмен максимизировал g Алгоритм Кернигана-Лина (KL) - терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 15 Максимальный положительный прирост G m за проход Максимальный положительный прирост G m соответствует наилучшему префиксу m обменов, в последовательности обменов данного прохода. Эти m обменов приводят к разбиению с наименьшим разрезом найденному за проход. G m вычисляется как сумма значений Δg за первые m обменов прохода; m выбирается так чтобы максимизировать G m Алгоритм Кернигана-Лина (KL) - терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Алгоритм Кернигана-Лина (KL) – один проход

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7, Алгоритм Кернигана-Лина (KL) - пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 Стоимость D(v) для каждой вершины: Вершины ведущие к максимальному приросту Алгоритм Кернигана-Лина (KL) - пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 =3 Вершины ведущие к максимальному приросту Прирост в текущем проходе Стоимость D(v) для каждой вершины: Прирост после обмена вершин Алгоритм Кернигана-Лина (KL) - пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 20 Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7, D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 = Алгоритм Кернигана-Лина (KL) - пример Вершины ведущие к максимальному приросту Прирост в текущем проходе Прирост после обмена вершин

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 21 Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 Разрез: 6 Не фиксированы: 1,2,4,6,7,8 D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 = Алгоритм Кернигана-Лина (KL) - пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 22 D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 =3 D(1) = -1D(6) = 2 D(2) = -1D(7)=-1 D(4) = 3D(8)= Алгоритм Кернигана-Лина (KL) - пример Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 Разрез: 6 Не фиксированы: 1,2,4,6,7,8

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 =3 D(1) = -1D(6) = 2 D(2) = -1D(7)=-1 D(4) = 3D(8)=-1 g 2 = = 5 Обмен (4,6) G 2 = G 1 + g 2 =8 Вершины ведущие к максимальному приросту Прирост в текущем проходе Прирост после обмена вершин Алгоритм Кернигана-Лина (KL) - пример Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 Разрез: 6 Не фиксированы: 1,2,4,6,7,8

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 24 Разрез: 1 Не фиксированы: 1,2,7, Разрез: 7 Не фиксированы: 2,8 D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 =3 D(1) = -1D(6) = 2 D(2) = -1D(7)=-1 D(4) = 3D(8)=-1 g 2 = = 5 Обмен (4,6) G 2 = G 1 + g 2 =8 D(1) = -3D(7)=-3 D(2) = -3D(8)=-3 g 3 = = -6 Обмен (1,7) G 3 = G 2 + g 3 = 2 Прирост в текущем проходе Вершины ведущие к максимальному приросту Прирост после обмена вершин Алгоритм Кернигана-Лина (KL) - пример Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 Разрез: 6 Не фиксированы: 1,2,4,6,7,8

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Разрез: 9 Не фиксированы: – D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 =3 D(1) = -1D(6) = 2 D(2) = -1D(7)=-1 D(4) = 3D(8)=-1 g 2 = = 5 Обмен (4,6) G 2 = G 1 + g 2 =8 D(1) = -3D(7)=-3 D(2) = -3D(8)=-3 g 3 = = -6 Обмен (1,7) G 3 = G 2 + g 3 = 2 D(2) = -1 D(8)=-1 g 4 = = -2 Обмен (2,8) G 4 = G 3 + g 4 = Алгоритм Кернигана-Лина (KL) - пример Разрез: 1 Не фиксированы: 1,2,7,8 Разрез: 7 Не фиксированы: 2,8 Разрез: 9 Не фиксированы: 1,2,3,4,5,6,7,8 Разрез: 6 Не фиксированы: 1,2,4,6,7,8

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 26 Максимальный положительный прирост G m = 8 при m = 2. D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Обмен (3,5) G 1 = g 1 =3 D(1) = -1D(6) = 2 D(2) = -1D(7)=-1 D(4) = 3D(8)=-1 g 2 = = 5 Обмен (4,6) G 2 = G 1 + g 2 =8 D(1) = -3D(7)=-3 D(2) = -3D(8)=-3 g 3 = = -6 Обмен (1,7) G 3 = G 2 + g 3 = 2 D(2) = -1 D(8)=-1 g 4 = = -2 Обмен (2,8) G 4 = G 3 + g 4 = Алгоритм Кернигана-Лина (KL) - пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 27 D(1) = 1D(5) = 1 D(2) = 1D(6) = 2 D(3) = 2D(7) = 1 D(4) = 1D(8) = 1 g 1 = = 3 Swap (3,5) G 1 = g 1 =3 D(1) = -1D(6) = 2 D(2) = -1D(7)=-1 D(4) = 3D(8)=-1 g 2 = = 5 Swap (4,6) G 2 = G 1 + g 2 =8 D(1) = -3D(7)=-3 D(2) = -3D(8)=-3 g 3 = = -6 Swap (1,7) G 3 = G 2 + g 3 = 2 D(2) = -1 D(8)=-1 g 4 = = -2 Swap (2,8) G 4 = G 3 + g 4 = 0 Поскольку G m > 0, выполняются первые m = 2 обмена (3,5) и (4,6) Алгоритм Кернигана-Лина (KL) - пример Пока G m > 0, проходы продолжаются. Максимальный положительный прирост G m = 8 при m = 2.

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Улучшеные варианты алгоритма Кернигана-Лина (KL) Компоненты неравного размера На каждом проходе алгоритма KL выполняются только min(|A|,|B|) обмена Неравные площади вершин Постараться умножить/поделить все площади на костанту, чтобы получить малые целые числа, например 2х, 3х наименьших общих делителя всех плошадей Поддерживать баланс площади, возможно разрешая отклонение на одну вершину Разбиение на k компонент Применить двух-компонентный KL ко всем парам компонент Рекурсивное разбиение (особенно удобно когда k явлияетсся степенью двойки) Существуют алгоритмы для разбиения на k компонент напрямую 28

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 29 Ячейки передвигаются по одной вместо обмена пар --- при этом невозможно и не нужно поддерживать компоненты равного размера Учитывается площадь каждой ячейки Продолжает работать в случае компонент разного размера, а также фиксированых ячеек Понятие разреза расширено чтобы учитывать гиперграфы сети с 2+ контактами В то время как алгоритм KL уменьшает разрезы по рёбрам, алгоритм FM уменьшает разрезы по сетям (гипер-рёбрам) Вершины и подграфы переименованы в ячейки и блоки, соответственно Алгоритм Фидуччи-Маттейсеса (FM)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 30 Даётся: гиперграф G(V,H) с вершинами и взвешенными гипер-рёбрами, ограничения на размер компонент Требуется: распределить все вершины в непересекающиеся компоненты, так чтобы минимизировать общую стоимость (вес) разрезанных сетей, выполнив ограничения на размер компонент Алгоритм Фидуччи-Маттейсеса (FM)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 31 Прирост g(c) для ячейки c g(c) = FS(c) – TE(c), где движущая сила FS(c) это количество сетей связанных с c но не связанных с другими ячейками компоненты c, т.е., разрезаных сетей связаных только с c, сила удержания TE(c) это количество неразрезаных сетей связаных с c. Чем выше прирост g(c), тем выше приоритет для передвижения ячейки c в другую компоненту. Ячейка 2: FS(2) = 0TE(2) = 1 g(2) = a b c d e 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 32 Прирост g(c) для ячейки c g(c) = FS(c) – TE(c), где движущая сила FS(c) это количество сетей связанных с c но не связанных с другими ячейками компоненты c, т.е., разрезаных сетей связаных только с c, сила удержания TE(c) это количество неразрезаных сетей связаных с c.. Cell 1: FS(1) = 2TE(1) = 1 g(1) = 1 Cell 2: FS(2) = 0TE(2) = 1 g(2) = -1 Cell 3: FS(3) = 1TE(3) = 1 g(3) = 0 Cell 4: FS(4) = 1TE(4) = 1 g(4) = 0 Cell 5: FS(5) = 1TE(5) = 0 g(5) = a b c d e a b c d e 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 33 Максимальный положительный прирост G m в течении прохода Максимальный положительный прирост G m это общий прирост m шагов ведуших к минимальному разрезу. G m определяется как максимальная сумма приростов ячеек g за префикс прохода состоящий из m шагов 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 34 Фактор баланса Частное размеров (сумм площадей ячеек) двух компонент Используется чтобы не допустить назначение всех ячеек в одну компоненту Определяется по формуле где area(A) и area(B) - это суммы площадей компонент A и B 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 35 Критерий баланса Близок к фактору баланса Дополнительно учитывает максимальную площадь ячейки area max (V) Разбиение V на компоненты A и B считается сбалансированым если [ r area(V) – area max (V) ] area(A) [ r area(V) + area max (V) ] 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 36 Базовая ячейка Базовая ячейка c обладает наибольшим приростом g(c) среди всех незафиксированных ячеек таких что их можно передвинуть не нарушив критерий баланса. Cell 1: FS(1) = 2TE(1) = 1 g(1) = 1 Cell 2: FS(2) = 0TE(2) = 1 g(2) = -1 Cell 3: FS(3) = 1TE(3) = 1 g(3) = 0 Cell 4: FS(4) = 1TE(4) = 1 g(4) = 0 Базовая ячейка Алгоритм Фидуччи-Маттейсеса (FM) – терминология

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Алгоритм Фидуччи-Маттейсеса (FM) – один проход

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig A B a b c d e 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – пример Шаг 0: Оценить критерий баланса [ r area(V) – area max (V) ] area(A) [ r area(V) + area max (V) ] 0,375 * 16 – 5 = 1 area(A) 11 = 0,375 * Исходные данные: Фактор баланса r = 0,375 area(Cell_1) = 2 area(Cell_2) = 4 area(Cell_3) = 1 area(Cell_4) = 4 area(Cell_5) = 5.

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig A B a b c d e Шаг 1: Вычислить прирост каждой ячейки Cell 1: FS(Cell_1) = 2TE(Cell_1) = 1 g(Cell_1) = 1 Cell 2: FS(Cell_2) = 0TE(Cell_2) = 1 g(Cell_2) = -1 Cell 3: FS(Cell_3) = 1TE(Cell_3) = 1 g(Cell_3) = 0 Cell 4: FS(Cell_4) = 1TE(Cell_4) = 1 g(Cell_4) = 0 Cell 5: FS(Cell_5) = 1TE(Cell_5) = 0 g(Cell_5) = Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig A B a b c d e Cell 1: FS(Cell_1) = 2 TE(Cell_1) = 1 g(Cell_1) = 1 Cell 2: FS(Cell_2) = 0 TE(Cell_2) = 1 g(Cell_2) = -1 Cell 3: FS(Cell_3) = 1 TE(Cell_3) = 1 g(Cell_3) = 0 Cell 4: FS(Cell_4) = 1 TE(Cell_4) = 1 g(Cell_4) = 0 Cell 5: FS(Cell_5) = 1 TE(Cell_5) = 0 g(Cell_5) = 1 Шаг 2: Найти базовую ячейку Возможные базовые ячейки Cell 1 и Cell 5 Критерий баланса после передвижения Cell 1: area(A) = area(Cell_2) = 4 Критерий баланса после передвижения Cell 5: area(A) = area(Cell_1) + area(Cell_2) + area(Cell_5) = 11 В обоих случаях критерий баланса соблюдён, но мы выбираем и передвигаем Cell Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig A B a b c d e Шаг 3: Зафиксировать базовую ячейку, обновить приросты g Cell 2: FS(Cell_2) = 2TE(Cell_2) = 0 g(Cell_2) = 2 Cell 3: FS(Cell_3) = 0TE(Cell_3) = 1 g(Cell_3) = -1 Cell 4: FS(Cell_4) = 0TE(Cell_4) = 2 g(Cell_4) = -2 Cell 5: FS(Cell_5) = 0TE(Cell_5) = 1 g(Cell_5) = -1 После итерации i = 1: Компонента A 1 = 2, Конпонент B 1 = 1,3,4,5, ячейка 1 фиксирована Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig A B a b c d e Cell 2: FS(Cell_2) = 2 TE(Cell_2) = 0 g(Cell_2) = 2 Cell 3: FS(Cell_3) = 0 TE(Cell_3) = 1 g(Cell_3) = -1 Cell 4: FS(Cell_4) = 0 TE(Cell_4) = 2 g(Cell_4) = -2 Cell 5: FS(Cell_5) = 0 TE(Cell_5) = 1 g(Cell_5) = -1 Итерация i = 2 Cell 2 с максимальным приростом g 2 = 2, area(A) = 0, критерий баланса не соблюдён Cell 3 со следующим приростом g 2 = -1, area(A) = 5, критерий баланса не соблюдён. Cell 5 со следующим приростом g 2 = -1, area(A) = 9, критерий баланса не соблюдён. Передвигаем Cell 3; компоненты: A 2 = {2,3}, B 2 = {1,4,5}, фиксированые ячейки: {1,3} Итерация i = Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 43 Cell 2: g(Cell_2) = 1 Cell 4: g(Cell_4) = 0 Cell 5: g(Cell_5) = -1 Итерация i = 3 Cell 2 с максимальным приростом g 3 = 1, area(A) = 1, критерий баланса соблюдён Передвигаем cell 2, компоненты: A 3 = {3}, B 3 = {1,2,4,5}, фиксированые ячейки: {1,2,3} A B a b c d e Итерация i = Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 44 Cell 4: g(Cell_4) = 0 Cell 5: g(Cell_5) = -1 Итерация i = 4 Cell 4 с максимальным приростом g 4 = 0, area(A) = 5, критерий баланса соблюдён. Передвигаем cell 4, компоненты: A 4 = {3,4}, B 3 = {1,2,5}, фиксированые ячейки {1,2,3,4} B A a b c d e Итерация i = Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 45 Cell 5: g(Cell_5) = -1 Итерация i = 5 Cell 5 с максимальным приростом g 5 = -1, area(A) = 10, критерий баланса соблюдён. Передвигаем cell 5; компоненты A 4 = {3,4,5}, B 3 = {1,2}, все ячейки {1,2,3,4,5} зафиксированы B A a b c d e Итерация i = Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 46 Шаг 5: Найти лучший префих прохода c 1 … c m G 1 = g 1 = 1 G 2 = g 1 + g 2 = 0 G 3 = g 1 + g 2 + g 3 = 1 G 4 = g 1 + g 2 + g 3 + g 4 = 1 G 5 = g 1 + g 2 + g 3 + g 4 + g 5 = 0. Максимальный суммарный прирост найден in итерациях 1, 3 and 4. Выбран префикс m = 4 благодая лучшему фактору баланса (area(A) = 5); Передвигаем четыре ячейки 1, 2, 3 and 4. Результат Прохода 1: Компоненты: A = {3,4}, B = {1,2,5}, разрез сокращён с 3 до B A a b c d e 2.4.3Алгоритм Фидуччи-Маттейсеса (FM) – пример

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 47 Разница во времени работы KL и FM Время работы алгоритмов разбиения для KL важно количество вершин и рёбер для FM важно количество вершин и сетей (гипер-рёбер), а также размеры гипер-рёбер (количество контактов) Асимптотическая сложность алгоритмов разбиения сложность одного прохода KL кубическая сложность одного прохода FM линейная 47

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Многоуровневые алгоритмы разбиения графов 2.1Введение 2.2Терминология 2.3Задачи оптимизации 2.4Алгоритмы разбиение (гипер)графов Алгоритм Кернигана-Лина (KL) Улучшенные варианты алгоритма Кернигана-Лина Алгоритм Фидуччи-Маттейсеса (FM) 2.5Многоуровневые алгоритмы Кластеризация Многоуровневое разбиение (гипер)графов 2.6Разбиение систем на несколько кристаллов ПЛИС для эмуляции

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Кластеризация 49 Чтобы упростить задачу, группы тесно связанных вершин можно объединить в кластеры, поглотив соединения между ними Размер каждого кластера обычно ограничен чтобы предотвратить вырожденую иерархию, т.е. один large кластер гораздо больше остальных Уточнение кластеров (refinement) должно соблюдать критерии баланса

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Кластеризация a b c d e a,b,ca,b,c d e a b d c,ec,e Начальный граф Две возможные иерархии графа © 2011 Springer

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Многоуровневое разбиение © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig Разбиение систем на несколько кристаллов ПЛИС FPGA FPIC FPGA RAMLogic Система с реконфигурацией состоящая из нескольких кристаллов ПЛИС (FPGA) Отображение архитектуры системы на несколько кристаллов ПЛИС © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 53 Обзор Главы 2 Представление схем графами и гиперграфами Разбиения графа: распределение вершин по непересекающимся компонентам Размер каждой компоненты (число/площадь вершин) ограничен Требуется: минимизировать количество соединений между компонентами Основные алгоритмы разбиения Пошаговые/итеративные методы; шаги собаны в проходы KL переставляет пары вешин из разных компонент FM передвигает вершины по одной FM работает быстрее, обычно получает лучшие результаты Многоуровневое разбиение Кластеризация На самом дальнем уровне - используем FM, начиная со случайного разбиения Уточнение кластеров на каждом уровне – также используем FM Приложение: разбиение систем на кристаллы ПЛИС для эмуляции Каждый кристалл ПЛИС представлен компонентой разбиения