Прикладные математические проблемы САПР СБИС А.М.Марченко

9/26/20122 План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/20123 Топология СБИС в разрезе

9/26/20124 ITRS03: размеры затворов

9/26/20125 ITRS03: задержки

9/26/20126 Межсоединения доминируют над транзисторами: Задержка Задержка в транзисторе Задержка в линии, L int =1mm 1.0 µm (Al, SiO2) ~ 20 ps~ 1 ps 100 nm ( Cu ) ~ 5 ps ~ 30 ps Технология 35 nm (Cu) ~ 2.5 ps ~ 250 ps

9/26/20127 Технологические тенденции Задержка на межсоединениях становится доминирующей Логический синтез без учета реализации схемы в кремнии неэффективен Изготовление транзисторов усложняется, что делает критическим методы проверки Рассеиваемая мощность становится определяющим фактором

9/26/20128 План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/20129 Критическая длина Prashant Saxena, Noel Menezes, Pasquale Cocchini, Desmond A. Kirkpatrick The Scaling Challenge: Can Correct-by-Construction Design Help?, ISPD03, April 6-9, 2003, Monterey, California, USA.

9/26/ Процент цепей, требующих буферизации

9/26/ ITRS05: задержки

9/26/ Принципы проектирования Декомпозиционный (по количественным признакам) Итерационный (последовательное приближение к ТЗ) Иерархический (по степени подробности) Унификации Контролируемости

9/26/ Традиционный маршрут синтеза СБИС СБИС Полное описание Архитектура RTL Логическое Электрическое Топология

9/26/ Традиционный маршрут синтеза СБИС СБИС Структура Полное описание Архитектура RTL Логическое Электрическое Топология

9/26/ Маршрут эволюционного синтеза СБИС СБИС Структура Полное описание Архитектура RTL Логическое Электрическое Топология

9/26/ Абстрактный эволюционный метод Пространство условий Пространство решений Множество решенных задач Новое условие Новое решение «Похожее» условие «Похожее» решение

9/26/ Задачи эволюционного синтеза 1.Определение функций расстояния на множествах условий и решений задачи синтеза. Пример: сравнение графов. 2.Разработка алгоритмов построения нового решения из «похожего».

9/26/ План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/ Влияние структуры электрической схемы на качество размещения Malgorzata Marek-Sadowska, Qinghua Liu A Study of Netlist Structure and Placement Efficiency, ISPD04, April 6-9, 2004, California, USA. Параметры структуры схемы: 1.Связность цепи 2.Число цепей 3.Значение экспоненты Рента Выводы: Эффективность размещения коррелирует со сложностью схемы Различные алгоритмы размещения демонстрируют разную чувтсвительность к различным схемам.

9/26/ Список параметров Генератор Измерение параметров размещения Измерение параметров схемы CapoDragonmPL Benchmarks Сравнение результатов Цель исследований – найти минимальное число параметров схемы, полученных на этапе логического синтеза, достаточное для однозначной оценки качества размещения данной схемы при топологическом синтезе С.Уланов, Исследование эффективности методов размещения элементов СБИС в зависимости от структуры схемы. дипломная работа, МФТИ, 2004.

9/26/ Входные и выходные параметры Геометрические параметры библиотечных элементов Параметры связности схемы (гиперграфа) Структура схемы с учетом направления сигналов Площадь кристала Длины соединений Длины путей от входа к выходу Трассируемость Характеристики качества размещения: Параметры, задающие схему:

9/26/ Геометрические параметры библиотечных элементов Высота элемента h Мат. ожидание ширины элемента w Дисперсия ширины элемента δw

9/26/ Гиперграф Гиперграф – пара множеств (V, E), где V – множество вершин (vehicles), E – множество ребер (edges). Схема (circuit) – гиперграф, в котором вершины соответствуют элементам схемы, а ребра – соединительным цепям Входы Выходы Внутренние элементы Цепи

9/26/ Параметры гиперграфа Валентность цепей: Валентность элементов: Длина пути: Количество элементов:

9/26/ Структурные параметры схемы Схема представлена множеством конусов Конус – вход и множетво выходов, с которыми он соединен Длина основания конуса – количество выходов с которыми соединен соответствующий вход Входы Выходы

9/26/ Оценки качества размещения Площадь Задержки прохождения сигналов: Длина пути от входа к выходу Длины соединений (объяснить, в чем отличие от предыдущего) Трассируемость: Плотность cоединений (congestion)

9/26/ Экспонента Рента p – экпонента Рента (Rents exponent) Зависимость числа соединений модуля с остальной частью схемы (T) от количества элементов в этом модуле (G):

9/26/ Сравнение качества размещения исскусственых схем и их прототипов Плотность соединений Capo mPL Dragon

9/26/ Сравнение качества размещения исскусственых схем и их прототипов Средняя длина соединения Capo mPL Dragon

9/26/ Сравнение качества размещения исскусственых схем и их прототипов Средняя длина пути Capo mPL Dragon

9/26/ Сравнение экспоненты Рента для исскусственых схем и их прототипов

9/26/ Выбранный набор параметров достаточно хорошо описывает схему, что позволяет качественно оценивать результаты размещения непосредственно после логического синтеза. В большинстве случаев сгенерированные схемы хорошо соотносятся с реальными схемами, имеющими те же параметры. Проведены экпериментальные исследования зависимости качества размещения от структурных параметров логических схем, которые показали:

9/26/ План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/ Применение абстрактного эвплюционного метода для построения деревьев Штейнера Дано дерево Штейнера T 1 (P 1 S 1,E 1 ), состоящее из P 1 основных точек двух типов (источник и сток), и S 1 дополнительных точек, связанных между собой ребрами E 1, удовлетворяющее критерию C, и множество точек P 2 двух типов (источник и сток). Необходимо определить множество S 2 дополнительных точек, таких, что дерево T 2 (P 2 S 2,E 2 ) будет удовлетворять критерию C. М.А. Марченко Метод построения деревьев Штейнера, основанный на знаниях // Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS02)» и «Интеллектуальные САПР CAD-2002». – 2002

9/26/ Алгоритм оценки деревьев Штейнера, адаптирующийся к критериям трассировки Средний радиус множества точек на плоскости есть Характеристической функцией множества M точек на плоскости называется функция

9/26/ График характеристической функции

9/26/ Метод оценки деревьев Штейнера, адаптирующийся к критериям трассировки Расстояние между множествами есть расстояние в пространстве L p между их характеристическими функциями Применение характеристической функции в явном виде не имеет смысла из-за вычислительной сложности, поэтому была разработана приближенная функция Пусть G подмножество M размерности l, тогда приближенная характеристическая функция определяется индуктивно

9/26/ Результат работы алгоритма + = + =

9/26/ Часть 2

9/26/ План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/ Проблема размещения

9/26/ Критерии и ограничения для задачи размещения Суммарная длина соединений (HPWL) Конструкторско-технологические ограничения (DRC) Трассируемость (congestion) Задержка Рассеиваемая мощность

9/26/ Требования к размещению (1) Размерность 4-10M ячеек, 1000 макро-блоков Учет фиксированных элементов ports/pads/pins + fixed cells Размещение макро-блоков, например, с переменным отношением длина/ширина Ограничение длины цепи Учет ограничений на взаимное расположение Различная плотность упаковки (от 25% до 100% занятой площади), ICCAD `02

9/26/ Требования к размещению(2) ECO (Engineering Change Order) размещение Устранить перекрытия после после изменений схемы Дополнительно разместить небольшое количество элементов Инкрементальное размещение для итераций между отдельными этапами: Размещением и логическим синтезом Размещением и оптимизацией размеров логических элементов (sizing) Размещением и трассировкой

9/26/ Проблема трассировки

9/26/ Простые критерии трассируемости Horizontal vs. Vertical wirelength HPWL = WL H +WL V Два размещения с одинаковой HPWL могут иметь сильно отличающиеся WL H и WL V Вероятностные распределения трассируемости Bhatia et al – DAC 02 Lou et al - ISPD 00, TCAD 01 Carothers & Kusnadi – ISPD 99`

9/26/ Задача сжатия. Пример топологии ячейки СБИС До сжатияПосле сжатия

9/26/ Простые технологические правила

9/26/ Топологические ограничения

9/26/ Задача сжатия топологии в виде задачи линейного программирования

9/26/ Двумерное сжатие Двумерное сжатие – NP-сложгая задача (C. K. Wong, 1984)

9/26/ План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/ R. Kumar, W. K. Leong, R. J.Heath An Integer Programming Approach to Placement and Routing in Circuit Layout Аналитическое размещение Комбинаторная трассировка

9/26/ Классификация алгоритмов Дихотомические – Сapo Jarrod A. Roy, David A. Papa, Saurabh N. Adya, Hayward H. Chan, Aaron N. Ng, James F. Lu, Igor L. Markov Capo: Robust and scalable open- source min-cut floorplacer, ISPD05, 2005, p Моделирования отжига – Dragon Taraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi Dragon2005: large-scale mixed-size placement tool, ISPD05, 2005, p Аналитические – mPL5 Tony Chan, Jason Cong, Kenton Sze Multilevel generalized force-directed method for circuit placement, ISPD05, 2005, p

9/26/ Результаты, полученные на тестах от 210K до 2.1M gates

9/26/ mPL5: формулировка задачи

9/26/ Гладкая аппроксимация целевой функции 1. Квадратичная аппроксимация суммарной длины соединений Kahng A. Implementation and Extensibility of an Analytical Placement 2. log-sum-exp аппроксимация (Kahng A. Implementation and Extensibility of an Analytical Placement) Cong J. Multilevel Generalized Force-directed Method for Circuit Placement) 3. Lp – аппроксимация (Cong J. Multilevel Generalized Force-directed Method for Circuit Placement)

9/26/ Сглаживание стандартных функций: β -сглаживание для модуля Ross Baldick, Andrew B. Kahng, Andrew kennings, Igor L. Markov Function Smoothing with Applications to VLSI Layout /1 )))((()( xfxf 2 || ),max( baba ba 2 || ),min( baba ba Пример β-сглаживания для функции с β=0.01 и α=2 |4.0|||2|1|)(xxxxf

9/26/ Сравнение аппроксимаций WL Cong J. Multilevel Generalized Force-directed Method for Circuit Placement СхемаLogSumExp WL, runtime Lp-norm WL, runtime Quadratic WL, runtime ibm11, 11.05, , 0.81 Ibm21, 11.02, , 1.65 Ibm31, 10.99, , 0.64 Ibm41, 10.98, , 0,47 Ibm51, 11.06, , 1.17 Ibm61, 11.03, , 0.50 Ibm71, 11.04, , 0.67 Ibm81, 11.01, , 0.72 Ibm91, 11.05, , 0.53 Ibm101, 11.03, , 0.72 Ibm111, 11.04, , 0.52 Ibm121, 11.02, , 0.67 Ibm131, 11.03, , 0.63 Ibm141, 11.03, , 0.71 Ibm151, 11.04, , 0.80 Ibm161, 11.04, , 0.79 Ibm171, 11.03, , 0.85 Ibm181, 11.07, , 0.97 среднее1, 11.03, , 0.77

9/26/ R. Kumar, W. K. Leong, R. J.Heath An Integer Programming Approach to Placement and Routing in Circuit Layout Аналитическое размещение Комбинаторная трассировка

9/26/ Задача трассировки формулируется как задача линейной псевдобулевой оптимизации A. Samoilov Constraint Programming for Difficult Routing Problems – 2006

9/26/ Однослойная трассировка

9/26/ Формулировка задачи 1. Терминальные ячейки: цепь пересекает только одну сторону ячейки 2. Проходные ячейки: цепь пересекает 0 или 2 стороны

9/26/ Ограничения: 4. Критерии оптимизации:

9/26/ Задача Соукупа

9/26/ Решение

9/26/ Пример трассировки многоконтактных цепей

9/26/ Трассировка в многосвязной области

9/26/ Трассировка свитчбокса

9/26/ Трассировка с минимизацией задержки

9/26/ Топологии одной и той же цепи с разным сопротивлением драйвера

9/26/ План доклада Технологические тенденции и проблемы проектирования цифровых СБИС Эволюционные методы синтеза. Взаимосвязь этапов логического и топологического синтеза СБИС. Алгоритм построения д.Штейнера, основанный на знаниях Задачи синтеза топологии Аналитические методы в задачах топологического синтеза Методы вычислительной геометрии

9/26/ E. Papadopoulou and D. T. Lee Critical Area Computation via Voronoi Diagrams – ISPD-2000 Проверка правил проектирования (DRC) ТрассировкаСжатие

9/26/ Классическая диаграмма Вороного ДВ: не более 2n – 5 вершин 3n – 6 рёбер Размер O(n) Сложность построения O(n log n) Ячейка Вороного VR(p,S) для точки p набора S – локус точек на плоскости, расположенных ближе к p, чем к любой другой точке S: VR(p,S)={r 2 | qp d(r,p)d(r,q)}, где d(x,y) – евклидово расстояние Диаграмма Вороного для набора точек {p 1,…,p n }: VD(S)={VR(p 1 ),…,VR(p n )} Граф (триангуляция Делоне) набора точек – планарный граф DT(S), двойственный к диаграмме Вороного Диаграмма Вороного и граф Делоне (пунктир)

9/26/ Алгоритм построения дерева Штейнера с обходом препятствий Zhe Feng, Yu Hu,Tong Jing, X. Hong, X.Hu, G. Yan An O(nlogn) Algorithm for Obstacle-Avoiding Routing Tree Construction in the λ-Geometry Plane – ISPD-2006

9/26/ Триангуляция с обходом препятствий

9/26/ Связывающее дерево с обходом препятствий

9/26/ Тестовый пример:1000 контактов препятствий

9/26/ Построение связывающего дерева с помощью диаграмм Вороного K.K.Malinauskas, A.M.Marchenko VORONOI DIAGRAMS BASED ROUTING QUALITY ESTIMATE FOR THE PLACEMENT TASK

9/26/ E. Papadopoulou and D. T. Lee Critical Area Computation via Voronoi Diagrams – ISPD-2000 Проверка правил проектирования (DRC) ТрассировкаСжатие

9/26/ Henyi Li, Victor Milenkovic. A Compaction Algorithm for Non-Convex Polygons and Its Application. 9th Annual Computational Geometry, 5/93/CA, USA, 1993 Применение разности Минковского для оптимального раскроя ткани

9/26/ В данной интерпретации разность Минковского M есть геометрическое место точек, которые определяют допустимые расположения фигуры F внутри ячейки B диаграммы Вороного. А.М. Марченко, М.А. Удовихин. ПРИМЕНЕНИЕ МЕТОДОВ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ В ЗАДАЧЕ ДВУМЕРНОЙ ОПТИМИЗАЦИИ ТОПОЛОГИИ, Применение диаграмм Вороного и разности Минковского для двумерного сжатия топологии