VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 2: Netlist and System Partitioning © KLMH Lienig 1 Глава 2 – Разбиение графов с. - презентация

1 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 Физическое Проектирование СБИС: от Разбиения Графов до Оптимизации Временных Характеристик

2 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Разбиеие систем на несколько кристаллов ПЛИС для эмуляции

3 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

4 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Введение

5 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), Блок (компонента) Ячейки

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 непересекающихся подграфов так чтобы минимизировать данные функции и сохранить отношения инцидентности.

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

8 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Разбиение систем на несколько кристаллов ПЛИС для эмуляции

9 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)

10 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) - терминология

11 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) - терминология

12 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 ребро

13 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 ребра

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

15 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) - терминология

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

17 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) - пример

18 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) - пример

19 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) - пример

20 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) - пример Вершины ведущие к максимальному приросту Прирост в текущем проходе Прирост после обмена вершин

21 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) - пример

22 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

23 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

24 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

25 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

26 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) - пример

27 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.

28 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

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

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

31 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) – терминология

32 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) – терминология

33 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) – терминология

34 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) – терминология

35 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) – терминология

36 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) – терминология

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

38 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.

39 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) – пример

40 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) – пример

41 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) – пример

42 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) – пример

43 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) – пример

44 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) – пример

45 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) – пример

46 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) – пример

47 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

48 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Разбиение систем на несколько кристаллов ПЛИС для эмуляции

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

50 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

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

52 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

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