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

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 2 Глава 8 – Оптимизация Производительности Схем 8.1 Введение 8.2 Временной анализ и требования производительности схем Статический временной анализ (SТA) Бюджеты задержки и алгоритм распределения временного запаса (ZSA) 8.3 Размещение с временной оптимизацией Методы с упором на сети Вложение STA в линейные программы для размещения 8.4 Трассировка с временной оптимизацией Алгоритм ограниченного радиуса и стоимости Компромисс Прима-Дейкстры Минимизация задержки от источника до стока 8.5 Физический синтез схем Масштабирование вентилей Буферизация Перестройка сетей 8.6 Маршрут проектирования с оптимизацией производительности схемы 8.7 Заключение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 3 8Оптимизация производительности схем 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 8: Timing Closure © KLMH Lienig 4 Раскладка интегральных схем (ИС) должна выполнять геометрические, ограничения, электрические ограничения, ограничения по мощности и тепловым характеристикам а также временные ограничения ограничения установки сигнала (соотв. длинным путям на схеме) ограничения удержания сигнала (соотв. коротким путям на схеме) Проектировщики должны завершить оптимизацию временных характеристик выполнить временные ограничения процесс сочитает индивидуальнуе оптимизации обсуждаемые в предыдущих главах (размещение, трассировку, и т.д.) со специализированными методами улучшения производительности схемы 8.1Введение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 5 Этапы оптимизации производительности схем освещённые в этой лекции: Размещение с временной оптимизацией (Sec. 8.3) уменьшает задержки сигналов при определении местоположения элементов схемы Трассировка с временной оптимизацией (Sec. 8.4) уменьшает задержки сигналов при выборе тополий сетей и прокладке маршрутов Физический синтез (Sec. 8.5) уменьшает задержки перестраивая схему Масштабирование транзисторов и вентилей: изменение соотношения длины и ширины транзисторов чтобы увеличить или уменьшить задержку или ведущую силу вентиля Вставка буферов в сети чтобы уменьшить задержки сигнала Перестройка сетей вдоль критических путей Маршрут проектирования с оптимизацией производительности схемы (Sec. 8.6) 8.1Введение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 6 Оптимизация производительности схем требует точной и быстрой оценки задержек распостранения сигналов в схеме Для оценки временных характеристик схемы, задержки распостранения сигналов через элементы схемы просчитываются в разных точках схемы. Учитываются два типа временных ограничений: Ограничения установки сигнала (огр. длинных путей) для элементов памяти (триггеров и защёлок) указывают как долго входной сигнал должен оставаться неизменным перед фронтом синхросигнала Ограничения удержания сигнала (огр. коротких путей) для элементов памяти указывают как долго сигнал должен оставаться неизменным после фронта синхросигнала 8.1Введение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 7 Оптимизация временных характеристик выполняет временные ограничения, меняя раскладку и перестраивая схему Жаргон: the design has closed timing - «проект закрыт по времени» 8.1Введение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 8 8.2Временной анализ и временные ограничения 8.1 Введение 8.2 Временной анализ и требования производительности схем Статический временной анализ (SТA) Бюджеты задержки и алгоритм распределения временного запаса (ZSA) 8.3 Размещение с временной оптимизацией Методы с упором на сети Вложение STA в линейные программы для размещения 8.4 Трассировка с временной оптимизацией Алгоритм ограниченного радиуса и стоимости Компромисс Прима-Дейкстры Минимизация задержки от источника до стока 8.5 Физический синтез схем Масштабирование вентилей Буферизация Перестройка сетей 8.6 Маршрут проектирования с оптимизацией производительности схемы 8.7 Заключение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 9 Последовательная схема, развёрнутая во времени Синхросигнал FF Комбина- ционная схема ( Копия 1) FF Ячейки памятиКомбинационные схемы 8.2Временной анализ и требования производительности схемы © 2011 Springer Verlag Комбина- ционная схема ( Копия 2) Комбина- ционная схема ( Копия 3)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 10 Главные компоненты задержки в последовательных схемах Задержки в вентилях связанные с переменой сигнала Задержки в проводах связанные с распостранением сигнала в длинных проводах Перекос синхросигнала определияет разницу во времени активации элементов памяти Чтобы быстро оценить производительность последовательной схемы используется статический временной анализ (STA) пренебрегаем перекосом синхросигнала (поправка на поздних стадиях) 8.2Временной анализ и требования производительности схемы

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 11 Рассмотрим худший случай, в котором каждый вентиль переключается Представим комбинационную схему направленным ацикличным графом (DAG) Каждое ребро и вершина несут на себе вес - задержка проводов и вентилей Для каждой вершины, вычислим запас = RAT – AAT RAT это трeбуемое время прибытия, т.е. самое позднее время переключения допустимое требованиями производительности схемы AAT это фактическое время прибытия По договорённости, AAT изначально определён на входных контактах схемы и прощитывается на выходе каждого элемента схемы Отрицательный запас в любой точке схемы означает что схема не выполняет требования производительности Положительный запас на всех выходах озанчает что схема выполняет требования 8.2.1Статический временной анализ

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 12 Комбинационная схема представленная графом (DAG) (0.15) (0.1) (0.3) (0.2) b a c f y (2) w (2) (0.1) (0.2) (0.1) (0.25) x (1) z (2) (0.15) (0.1) (0.2) (0.25) (0.2) (0) (0.6) (0.3) x (1) y (2) z (2) w (2) f (0) a (0) b (0) c (0) s 8.2.1Статический временной анализ © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 13 Вычислим AATs в каждой вершине: где FI(v) это множество вершин на входе вентиля v (fanin), а t(u,v) это задержка мехду u и v A 0.6 A 5.85A 5.65 A 0 A 1.1A 0 A 3.4 A Статический временной анализ © 2011 Springer Verlag (значения AAT на входных контактах заданы сначала) (0.15) (0.1) (0.2) (0.25) (0.2) (0) (0.6) (0.3) x (1) y (2) z (2) w (2) f (0) a (0) b (0) c (0) s

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 14 Вычислим RATs в каждой вершине: где FO(v) это множество вершин на выходе вентиля v (fanout), а t(u,v) это задержка между u и v (0.15) (0.1) (0.2) (0.25) (0.2) (0) (0.6) (0.3) x (1) y (2) z (2) w (2) f (0) a (0) b (0) c (0) s R 0.95 R 5.5 R 3.1 R 5.3 R R 0.75 R 3.05 R Статический временной анализ © 2011 Springer Verlag (значения RAT на выходных контактах заданы сначала)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 15 Вычислим запас (slack) в каждой вершине: (0.15) (0.1) (0.2) (0.25) (0.2) (0) (0.6) (0.3) x (1) y (2) z (2) w (2) f (0) a (0) b (0) c (0) s A 0 R 0.95 S 0.95 A 0 R S A 0 R S A 0.6 R 0.95 S 0.35 A 1.1 R 0.75 S A 3.4 R 3.05 S A 3.2 R 3.1 S -0.1 A 5.65 R 5.3 S A 5.85 R 5.5 S Статический временной анализ © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 16 Назначим временной бюджет для каждой сети Задержки вентилей и проводов должны быть оптимизированы при раскладке Задержки проводов зависят от длин проводов Длины проводов неизвестны до размещения и трассировки Расчёт бюджетов с алгоритмом распределения временного запаса Рассмотрим вентили v i Рассмотрим сети e i Задержки вентилей DELAY(v) и сетей DELAY(e) Бюджет вентиля TB(v) включает DELAY(v) + DELAY(e) 8.2.2Распределениe временного запаса по бюджетам задержки

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 17 Исходные данные: временной граф G(V,E) Результат: временной бюджет TB для каждого v V 1. do 2. (AAT,RAT,slack) = STA(G) 3.foreach (v i V) 4. TB[v i ] = DELAY(v i ) + DELAY(e i ) 5. slack min = 6.foreach (v V) 7. if ((slack[v] 0)) 8. slack min = slack[v] 9. v min = v 10. if (slack min ) 11. path = v min 12. ADD_TO_FRONT(path,BACKWARD_PATH(v min,G)) 13. ADD_TO_BACK(path,FORWARD_PATH(v min,G)) 14. s = slack min / |path| 15. for (i = 1 to |path|) 16. node = path[i]// распределить поравну 17. TB[node] = TB[node] + s// запас вдоль пути path 18. while (slack min ) 8.2.2Распределениe временного запаса по бюджетам задержки

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 18 Forward Path Search (FORWARD_PATH(v min,G)) Исходные данные: вершина v min с минимальным положительным запасом slack min ; временной граф G Результат: максимальный путь path вниз по течению от v min такой что вершины v V не влияют на запас на пути path 1. path = v min 2. do 3. flag = false 4. node = LAST_ELEMENT(path) 5. foreach (fanout node fo of node) 6. if ((RAT[fo] == RAT[node] + TB[fo]) and (AAT[fo] == AAT[node] + TB[fo])) 7. ADD_TO_BACK(path,fo) 8. flag = true 9. break 10. while (flag == true) 11. REMOVE_FIRST_ELEMENT(path)// удалить v min 8.2.2Распределениe временного запаса по бюджетам задержки

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 19 Backward Path Search (BACKWARD_PATH(v min,G)) Исходные данные: вершина v min с минимальным положительным запасом slack min ; временной граф G Результат: максимальный путь path вверх по течению от v min такой что вершины v V не влияют на запас на пути path 1. path = v min 2. do 3. flag = false 4. node = FIRST_ELEMENT(path) 5. foreach (fanin node fi of node) 6. if ((RAT[fi] == RAT[node] – TB[fi]) and (AAT[fi] == AAT[node] – TB[fi])) 7. ADD_TO_FRONT(path,fi) 8. flag = true 9. break 10. while (flag == true) 11. REMOVE_LAST_ELEMENT(path)// удалить v min 8.2.2Распределениe временного запаса по бюджетам задержки

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [0] [0] [0] [0] [0] [0] [0] [0] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] Найдём путь с минимальным ненулевым запасом 3 0 I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [0] [0] [0] [0] [0] [0] [0] [0] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] Найдём путь с минимальным ненулевым запасом Распределим запасы и обновим бюджеты 3 0 I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [1][1] [0] [1][1] [1][1] [0] [0] [0] [1][1] [0] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] Найдём путь с минимальным ненулевым запасом Распределим запасы и обновим бюджеты 3 0 I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [1] [2][2] [1] [1] [0] [0] [0] [1] [0] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] Найдём путь с минимальным ненулевым запасом Распределим запасы и обновим бюджеты 3 0 I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [1] [2] [1] [1] [2][2] [0] [2][2] [1] [0] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] Найдём путь с минимальным ненулевым запасом Распределим запасы и обновим бюджеты 3 0 I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [1] [2] [1] [1] [3][3] [0] [3][3] [1] [0] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Распределениe временного запаса по бюджетам задержки Пример: алгоритм распределения временного запаса Формат:, [бюджет] Найдём путь с минимальным ненулевым запасом Распределим запасы и обновим бюджеты 3 0 I1I1 I2I2 I3I3 I4I4 O1O1 O2O2 [1] [2] [1] [1] [3] [1][1] [3] [1] [4][4] O 1 : O 2 :

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Размещение с временной оптимизацией 8.1 Введение 8.2 Временной анализ и требования производительности схем Статический временной анализ (SТA) Бюджеты задержки и алгоритм распределения временного запаса (ZSA) 8.3 Размещение с временной оптимизацией Методы с упором на сети Вложение STA в линейные программы для размещения 8.4 Трассировка с временной оптимизацией Алгоритм ограниченного радиуса и стоимости Компромисс Прима-Дейкстры Минимизация задержки от источника до стока 8.5 Физический синтез схем Масштабирование вентилей Буферизация Перестройка сетей 8.6 Маршрут проектирования с оптимизацией производительности схемы 8.7 Заключение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 28 Размещение с временной оптимизацией оптимизирует задержку схемы чтобы выполнить требования производительности Рассмотрим множество T всех временных точек схемы (контактов) Выполнение требований производительности можно оценить с помощью наименьшего отрицательного запаса (WNS) Или суммарного отрицательного запаса (TNS) Типы оптимизации: с упором на сети, с упором на пути, интегрированные 8.3 Размещение с временной оптимизацией

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 29 Добаляем вес к каждой сети – размещение оптимизирует взвешенную длину проводов Статические веса сетей: вычислены перед размещением (не изменяются) Дискретные веса: где ω 1 > 0, ω 2 > 0, и ω 2 > ω 1 Непрерывные веса: где t это задержка длиннейшего пути α – параметр критичности С использованием чуствительности TNS и запаса задержки к данной сети 8.3.1Временная оптимизация с упором на сети

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 30 Динамические веса сетей: обновляются в течении размещения Оцениваем запас на каждой итерации: где ΔL это изменение длины Обновим параметр срочности сети: Обновим вес сети: Варианты: веса обновляются через j итераций, с использованием других критериев и формул если среди 3% самых критичных сетей иначе 8.3.1Временная оптимизация с упором на сети

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 31 Выведем линейные органичения для размещения с временной оптимизацией Геометрические ограничения определяют координаты ячеек Временные ограничения контролируют запас Оптимизация функций Увеличить наименьший отрицательный запас (WNS) Увеличить суммарный отрицательный запас (TNS) Увеличить линейную комбинацию WNS и TNS 8.3.2Вложение STA в линейные программы для размещения

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 32 Переменные для геометрических ограничений: x v и y v задают центр ячейки v V V e множество ячеек присоединённых к сети e E left(e), right(e), bottom(e), и top(e) отвечают координатам левой, правой, нижней и верхней границ объемлющего прямоугольника для e δ x (v,e) и δ y (v,e) задают смещение контактов v с e в расчёте от x v и y v 8.3.2Вложение STA в линейные программы для размещения

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 33 Для всех v V e : Определим полупериметровую длину проводов (HPWL) для e: 8.3.2Вложение STA в линейные программы для размещения

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 34 Для временных ограничений, рассмотрим t GATE (v i,v o ): задержка вентиля v от входного контакта v i до выходного контакта v o t NET (e,u o,v i ): задержка сети e от выходного контакта u o вентиля u до входного контакта v i вентиля v AAT(v j ): время фактического прибытия сигнала на контакт j вентиля v 8.3.2Вложение STA в линейные программы для размещения

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 35 Для всех входных контактов v i вентиля (ячейки) v : Для всех выходных контактов v o вентиля (ячейки) v : Для всех контактов τ p в элементе памяти τ: Нужно убедиться что все значения slack(τ p ) Вложение STA в линейные программы для размещения

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 36 Оптимизация суммарного отрицательного запаса: Оптимизация наименьшего отрицательного запаса : Оптимизация линейной комбинации нескольких параметров: 8.3.2Вложение STA в линейные программы для размещения

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Трассировка с временной оптимизацией 8.1 Введение 8.2 Временной анализ и требования производительности схем Статический временной анализ (SТA) Бюджеты задержки и алгоритм распределения временного запаса (ZSA) 8.3 Размещение с временной оптимизацией Методы с упором на сети Вложение STA в линейные программы для размещения 8.4 Трассировка с временной оптимизацией Алгоритм ограниченного радиуса и стоимости Компромисс Прима-Дейкстры Минимизация задержки от источника до стока 8.5 Физический синтез схем Масштабирование вентилей Буферизация Перестройка сетей 8.6 Маршрут проектирования с оптимизацией производительности схемы 8.7 Заключение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 38 Трассировка с временной оптимизацией должна минимизировать: Наибольшую задержку до стока: задержу из источника до любого стока сети Суммарную длину проводов: с учётом конкретных маршрутов (трасс) Для сигнальной сети net, рассмотрим источник s 0 стоки sinks = {s 1, …,s n } соответвтующий граф с весами G = (V,E) где V = {v 0,v 1, …,v n } представлюет источник и стоки (контакты) сети net, и вес ребра e(v i,v j ) E отвечает длине маршрута от v i до v j 8.4Трассировка с временной оптимизацией

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 39 Для любого остовного дерева T в G, рассмотрим: radius(T) : max длина пути из источника к стоку в T cost(T) : суммарный вес рёбер T Компромисс между неглубокими и короткими деревьями У неглубоких деревьев малый радиус древо кратчайших путей строится алгоритмом Дейкстры У коротких деревьев малый суммарный вес рёбер минимальное остовное дерево (MST) строится алгоритмом Прима 8.4Трассировка с временной оптимизацией

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 40 radius(T) = 8 cost(T) = 20 Неглубокое дерево s0s s0s radius(T) = 13 cost(T) = 13 Лёгкое дерево s0s radius(T) = 11 cost(T) = 16 Компромисс между длиной и глубиной 8.4Трассировка с временной оптимизацией © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 41 Компромисс между радиусом и стоимостью находится при помощи наложения верхних границ на оба параметра В контексте алгоритм ограниченного радиуса и стоимости рассмотрим: Дерево кратчайших путей T S Минимальное остовное дерево T M Дерево T BRBC построенное для параметра ε>0 выполняет: При ε = 0, T BRBC достигает минимального радуса Когда ε =, T BRBC достигает минимальной стоимости and Алгоритм ограниченного радиуса и стоимости

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 42 Компроисс Прима-Дейкстры базируется на алгоритмах Прима и Дейкстры Из множества стоков S, итеративно выбираем сток s с использованием одной из функций для алгоритма Прима: для алгоритма Дейкстры: для компромисса Прима-Дейкстры: с константой γ между 0 и 1: линейная комбинация двух «чистых» алгоритмов 8.4.2Компромисс Прима-Дейкстры

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 43 s0s s0s radius(T) = 19 cost(T) = 35 γ = 0.25 radius(T) = 15 cost(T) = 39 γ = Компромисс Прима-Дейкстры © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 44 Итеративно строим дерево добавляя стоки, с оптимизацией срочных стоков Задача о маршрутном дереве со срочными стоками (CSRT) минимизирует где α(i) - это оценки срочности стоков s i, а t(s 0,s i ) - это задержка от s 0 до s i 8.4.3Минимизация задержки от источника до стоков

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 45 В задаче о дереве Штейнера с одним срочным стоком, нужно построить дерево Штейнера минимальной длины которое соединяет все стоки кроме самого срочного s c Присоединяем самый срочный сток одим из способов H 0 : прямой провод из s c до s 0 H 1 : кратчайший провод присоединяющий s c к T, при условии что полученный путь от s 0 до s c имеет наименьшую возможную длину H Best : опробовать кратчайшие связки от s c до рёбер T и от s c до s 0. Выполнить временной анализ на каждом из полученных деревьев и выбрать дерево с наименьшей задержкой до s c 8.4.3Минимизация задержки от источника до стоков

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Физический синтез схем 8.1 Введение 8.2 Временной анализ и требования производительности схем Статический временной анализ (SТA) Бюджеты задержки и алгоритм распределения временного запаса (ZSA) 8.3 Размещение с временной оптимизацией Методы с упором на сети Вложение STA в линейные программы для размещения 8.4 Трассировка с временной оптимизацией Алгоритм ограниченного радиуса и стоимости Компромисс Прима-Дейкстры Минимизация задержки от источника до стока 8.5 Физический синтез схем Масштабирование вентилей Буферизация Перестройка сетей 8.6 Маршрут проектирования с оптимизацией производительности схемы 8.7 Заключение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 47 Физический синтез это набор временных оптимизаций для увеличения отрицательного запаса Примеры: расчёт временных бюджетов и исполнение временных правок Этапы бюджетирования: расчитать целевые задержки для сетей и/или вдоль путей зачастую перед размещением и трассировкой (где бюджеты используются) также может использоваться при временных правках Временные правки: Масштабирование вентилей Вставка буферов Перестройка сетей 8.5Физический синтез схем

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 48 Рассмотрим вентиль v с тремя возможными размерами A, B, C: У больших вентилей меньше сопротивление выходного контакта При больших нагрузочных ёмкостях У меньших вентилей больше сопротивление выходного контакта При меньших нагрузочных ёмкостях : Масштабирование вентилей

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Задержка (ps) Нагрузочная ёмкость (fF) C B A Масштабирование вентилей Рассмотрим вентиль v с тремя возможными размерами A, B, C : © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 50 b a d e f C(d) = 1.5 C(e) = 1.0 C(f) = 0.5 v b a d e f C(d) = 1.5 C(e) = 1.0 C(f) = 0.5 t(v A ) = 40 vAvA b a d e f C(d) = 1.5 C(e) = 1.0 C(f) = 0.5 t(v C ) = 28 vCvC Масштабирование вентилей

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 51 Буфер: два инвертера соединённых последовательно Вставив буфер, можно изменить задержку схемы изменить времена переключения экранировать ёмкостную нагрузку ускорить схему или вставить элемент задержки Недостатки: Увеличивается площадь схемы Увеличивается мощность энергопотребления 8.5.2Буферизация

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 52 d e f g h C(e) = 1 C(d) = 1 C(f) = 1 C(g) = 1 C(h) = 1 b a vBvB b a d e f g h C(e) = 1 C(d) = 1 C(f) = 1 C(g) = 1 C(h) = 1 vBvB y C(v B ) = 5 fF t(v B ) = 45 ps C(v B ) = 3 fF t(v B ) = 33 ps C(y) = 3 fF t(y) = t(v B ) + t(y) = 66 ps 8.5.2Буферизация

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 53 Перестройка схем меняет вентили схемы, но сохраняет функцию схемы без изменений Примеры преобразований схем клонирование: дублирование вентилей переделка входного или выходного дерева вентиля: меняет топологию соединений между вентилями обмен коммутативных контактов: меняет соединения декомпозиция вентилей: например заменить AND-OR на NAND-NAND Булева перестройка: замена вентилей по законам Булевой алгебры Обратные преобразования сокращение размеров вентилей, слияние вентилей, и т.д Перестройка схем

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 54 Клонирование может сократить ёмкость разветвления выхода вентиля и сократить ёмкость вниз по течению d e f g h C(e) = 1 C(d) = 1 C(f) = 1 C(g) = 1 C(h) = 1 b a b a d e f g h vBvB vAvA vBvB C(e) = 1 C(d) = 1 C(f) = 1 C(g) = 1 C(h) = 1 d e f g h b a b a d e f … v v … g h v … 8.5.3Перестройка схем © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 55 Переделка дерева разветвления входа может изменить значения AAT (1) a b c d f (1) a b c d f 8.5.3Перестройка схем © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 56 Переделка дерева разветвления выхода может изменить задержки на конкретных путях путь 1 путь 2 (1) y 1 (1) y 2 (1) (1) путь 1 путь 2 y 2 (1) (1) 8.5.3Перестройка схем © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 57 Обмен коммутативных контактов может изменить задержку схемы (1) (2) (1) a b c f (1) (2) (1) a b c f 8.5.3Перестройка схем © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 58 Декомпозиция вентилей может изменить структуру схемы 8.5.3Перестройка схем © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Перестройка схем Булева перестройка использует законы Булевой алгебры, например, закон дистрибутивности, чтобы изменить топологию схемы (a + b)(a + c) = a + bc (1) a b c (1) x y x(a,b,c) = (a + b)(a + c) y(a,b,c) = (a + c)(b + c) (1) x y a b c x(a,b,c) = a + bc y(a,b,c) = ab + c © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования 8.1 Введение 8.2 Временной анализ и требования производительности схем Статический временной анализ (SТA) Бюджеты задержки и алгоритм распределения временного запаса (ZSA) 8.3 Размещение с временной оптимизацией Методы с упором на сети Вложение STA в линейные программы для размещения 8.4 Трассировка с временной оптимизацией Алгоритм ограниченного радиуса и стоимости Компромисс Прима-Дейкстры Минимизация задержки от источника до стока 8.5 Физический синтез схем Масштабирование вентилей Буферизация Перестройка сетей 8.6 Маршрут проектирования с оптимизацией производительности схемы 8.7 Заключение

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Базовый маршрут физического проектирования 1.Планирование кристалла, размещение контактов I/O, планирование сетей питания и земли 2.Логический синтез и технологическая специализация 3.Глобальное размещение и легализация элементов памяти 4.Синтез деревьев синхорсигнала 5.Глобальная трассировка и определение уровней металлизации 6.Легализация и детальное размещение с учётом перегруженности 7.Детальная трассировка 8.Производственные оптимизации 9.Физическая верификация 10.Создание и оптимизация фотошаблонов

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Главный процессор для приложений Память Baseband DSP PHY Блок защиты Baseband MAC/Control Контроллер для обработки данных Поддержка коммуни- кационных протоколов Аналоговые схемы Аудио кодек Аудио пре-/пост- проссесинг Видео пре-/пост- проссесинг; управление потоком Видео кодек цифровая обработка Аналого-цифровой преобразователь (АЦП) Пример: плана кристалла © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Пример: глобальное размещение © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Пример: дерево синхросигнала © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Пример: перегруженность при глобальной трассировке © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Logic Synthesis and Technology Mapping Power PlanningI/O Placement Chip Planning Performance-Driven Block Shaping, Sizing and Placement Single Global Net Routes and Buffering fails passes RTL Timing Estimation With Optional Net Weights Trial Synthesis and Floorplanning Performance-Driven Block-Level Delay Budgeting Block-level or Top-level Global Placement Chip Planning and Logic Design (полная блок-схема в Figure 8.26) © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Delay Estimation Using Buffers Buffer InsertionVirtual BufferingLayer Assignment OR fails Obstacle-Avoiding Single Global Net Topologies Physical Buffering passes with fixable violations Static Timing Analysis Global Placement With Optional Net Weights Block-level or Top-level Global Placement Physical Synthesis (полная блок-схема в Figure 8.26) © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Timing-Driven Restructuring Gate SizingTiming Correction fails Boolean Restructuring and Pin Swapping Redesign of Fanin and Fanout Trees Static Timing Analysis passes Routing AND Physical Synthesis (полная блок-схема в Figure 8.26) © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Clock Network Synthesis Timing-driven Legalization + Congestion- Driven Detailed Placement Static Timing Analysis Timing-Driven Routing (Re-)Buffering and Timing Correction Detailed RoutingGlobal Routing With Layer Assignment Routing Sign-off fails passes Legalization of Sequential Elements 2.5D or 3D Parasitic Extraction (полная блок-схема в Figure 8.26) © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig Маршруты проектирования Mask Generation Design Rule Checking Layout vs. Schematic Antenna Effects Electrical Rule Checking Sign-off Manufacturability, Electrical, Reliability Verification Static Timing Analysis ECO Placement and Routing fails passes (полная блок-схема в Figure 8.26) © 2011 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 71 Обзор Главы 8 – Временные ограничения и временной анализ Задержка схем оценивается на сигнальных путях От первичных входных контактов до элементов памяти; от элементов памяти до первичных выходных контактов Между элементами памяти Компоненты задержки на путях Задержки вентилей: верхняя оценка по худшему перекючению (чтобы обеспечить быстрый статический временной анализ) Задержки проводов: зависят от длины проводов и топологии (для сетей с >2 контактами) Временные ограничения Фактические врменя прибытия (AATs) в первичные входы и выходы элементов памяти Требуемые врменя прибытия (RATs) в первичные выходы и входы элементов памяти Статический временной анализ Два прохода считают AAT и RAT для каждого вентиля (и сети) за линейное время В каждой временной точке: запас = RAT-AAT Отрицательный запас = временное нарушение; срочные сети/вентили определяются по отрицательному запасу Бюджеты: делят задержку схемы на границы задержки сетей и вентилей

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 72 Обзор Главы 8 – Размещение с временной оптизацией Размещение вентилей/ячеек влияет на длину проводов, которая влияет на задержку сетей Размещение с врменной оптимизацией оптимизирует координаты вентилей/ячеек чтобы улучшить временные характеристики Временной анализ находит срочные сети, им уделяется особое внимание Длина проводов должна быть низкой, иначе трассировка провалится Временная оптимизация часто усугибляет перегруженность Размещение с контролем весов сетей Самый простой метод размещения с временной оптимизацией После начального размещения, запускает временной анализ и подсчитывает веса для сетей Размещение с бюджетами задержек сетей Назначает границы задерки для каждой сети; переводит границы задержки в границы длин Выполняет размещение с соблюдением границ длин сетей Размещение с использованием линейного программирования Сводится к системе уравнений и неравенств Временной анализ и оптимизация представлены особыми неравенствами

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 73 Обзор Главы 8 – Трассировка с временной оптимизацией Трассировка с временной оптимизацией многогранна Индивидуальные сети: компромисс между длиной и глубиной Ёмкость соединения и целостость сигнала: параллельные провода создают конденсаторы и могут замедлить/ускорить переключение сигналов Оптимизация всей схемы: определить очерёдность оптимизации сетей Оптимизация индивидуальных сетей Крайний случай: независимые трассы от источника до каждого стока (высокая длина, возможно низкая задержка) Крайний случай: минимальное остовное дерево (низкая длина, выс. задержка) Компромисс: гибрид алгоритмов Прима и Дейкстры Ёмкость соединений и целостность сигнала Параллельные провода требуют особого внимания когда они переключаются одновременно Определив срочные сети, ограничить перекрёстный шум на них отдалив соседние провода Оптимизация всей схемы После предварительной трассировки, временной анализ находит срочные сети Оптимизировать индивидуальные сети, повторить

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 8: Timing Closure © KLMH Lienig 74 Обзор Главы 8 – Физический синтез схем В прошлом, размещение и трассировка использовали завершёную схему Сегодня, неперспективно рано фиксировать размеры вентилей и топологии сетей – это не учитывает более точного временного анализа Координаты вентилей и трассы сетей ещё не доступны Физический синтез перестраивает схему с использованием предварительного размещения Буферизация сетей: разбивает сеть на меньшие куски (~равной длины) Длиная сеть может иметь слишком высокую ёмкость, ведущий вентиль может быть слишком слабым Масштабирование вентилей/буферов: повышает силу ведушего вентиля & его физические размеры У больших вентилей высокая ёмкость входного контакта, но малое сопротивление выходного контакта Большие вентили могут вести больше вентилей, длиные сети; переключаются быстрее Большие вентили требуют больше места, большие ведущие вентили вверх по течению Клонирование вентилей: разделяет большие разветвления выхода Дублированые вентили могут быть разнесены (чего один вентиль не позволяет)