Математические вопросы

синтеза интегральных схем

С.А.Ложкин, А.М.Марченко

Общая характеристика и аннотация

Общая характеристика курса

Курс «Математические вопросы синтеза интегральных схем» является обязательным

для всех студентов специальности 01.02.09.01 (математическая кибернетика). Он

читается в 7 семестре в объеме 32 часов лекций, сопровождаемых 16 часами

практических занятий, и завершается зачетом. Чтение курса обеспечивается кафедрой математической кибернетики при поддержке фирмы «Интел». В 2005-2006 учебном году лекции по данному курсу читали профессор Ложкин С. А. и профессор Марченко А. М. (Интел), а практические занятия проводил доцент Романов Д. С.

Аннотация Курс «Математические вопросы синтеза интегральных схем» посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи размещения модулей СБИС и трассировки межсоединений. В рамках практических занятий осуществляется знакомство с базовыми пакетами программ логического и топологического синтеза СБИС, формируются навыки работы с этими пакетами.

Математические вопросы проектирования 12/27/2005 интегральных схем Программа курса I. Задача синтеза СБИС и связанные с ней модели дискретных управляющих систем.

1. Полевые транзисторы, принцип их работы. Основные сведения о КМОП-технологии и проектирование СБИС.

a. n- и p-канальные транзисторы, их проводимость;

b. логическая схема инвертора и двухвходовых НЕ-И, НЕ-ИЛИ;

c. представление об интегральной КМОП-технологии;

d. стандартные ячейки, топология инвертора и двухвходового НЕ-И;

e. задача проектирования СБИС и маршрут ее решения.

2. Функционирование и классификация КМОП-схем.

a. построение КМОП-схемы на основе контактных схем для булевской функции и ее отрицания;

b. функционирование КМОП-схемы общего вида, правильные комбинационные КМОП-схемы;

c. комбинационные КМОП-схемы с проблемами переключения, схемы с нагрузочными транзисторами.

3. КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами.

a. логическая и транзисторная схемы RS-триггера, его функционирование;

b. логическая и транзисторная схемы асинхронной ячейки памяти, ее функционирование;

c. схема D-триггера и его связь с единичной задержкой;

d. общая структура автоматных схем.

4. Представление об RC-схемах и их задержке. Быстродействие КМОП-схем.

a. распространение сигнала в КМОП-схемах на примере открытого транзистора;

b. RC-схемы из дискретных элементов и их задержка, представление об RC-схемах с непрерывным распределением емкости и сопротивления;

c. Основные факторы, влияющие на быстродействие КМОП-схем.

5. Синтез правильных комбинационных КМОП-схем на основе структурного моделирования основных типов дискретных управляющих систем.

a. моделирование контактных схем;

b. моделирование схем из функциональных элементов;

c. моделирование итеративных контактных схем;

d. примеры и сравнительный анализ разных типов структурного моделирования.

Клеточные схемы как «грубая» топологическая модель СБИС. Противоречие между сложностью и площадью, соотношения типа AT2.

6.

a. клеточные схемы из функциональных и коммутационных элементов в стандартном базисе;

b. клеточная реализация дешифратора, построенного по совершенной ДНФ;

c. нижняя оценка площади дешифратора, построенного асимптотически наилучшим по числу функциональных элементов методом;

d. соотношения типа AT2.

Математические вопросы проектирования 12/27/2005 интегральных схем Программа курса II. Основные подходы и методы логического синтеза СБИС.

7. Двухуровневый логический синтез и ДНФ. Основные подходы к двухуровневой оптимизации.

a. реализация функций в виде ДНФ и ее связь с ПЛМ;

b. простые импликанты и неизбыточные покрытия;

c. кофакторы и разложение Шеннона;

d. использование областей неопределенности (don't care);

e. пакет ESPRESSO.

8. Многоуровневый логический синтез и связанные с ним представления функций.

a. скобочные формы, построенные на основе ДНФ;

b. определение двоичных решающих диаграмм (BDD) и представления функций в виде BDD;

c. связь BDD с контактными схемами и операции над BDD, различные типы BDD;

d. выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.

9. Основные подходы к многоуровневой оптимизации.

a. декомпозиция и другие структурные операции над булевскими сетями;

b. упрощение вершин и его основные приемы;

c. использование булевских и алгебраических делителей;

d. привязка к библиотечному базису (mapping).

10. Логический синтез СБИС в системе SIS.

a. способы представления систем частичных булевых функций в системе SIS;

b. задание библиотечных базисов в системе SIS;

c. способы задания автоматов, синхронный и асинхронный синтез в системе SIS;

d. описания логических схем в системе SIS;

e. оптимизация логических схем в системе SIS.

Математические вопросы проектирования 12/27/2005 интегральных схем Программа курса III. Основные подходы и методы размещения модулей СБИС и трассировки межсоединений.

11. Задача разбиения электрической схемы.

a. примеры формулировок задачи разбиения;

b. классификация алгоритмов;

c. алгоритм Кернигана-Лина и его расширения;

d. алгоритм моделирования отжига;

e. геометрические алгоритмы;

12. Задача размещения модулей СБИС.

a. классификация алгоритмов;

b. плотные укладки;

c. силовой алгоритм;

d. обратное размещение;

e. Gordian.

13. Задача трассировки соединений.

a. классификация алгоритмов глобальной трассировки;

b. задача глобальной трассировки;

c. MST и SMT деревья;

d. классификация алгоритмов детальной трассировки;

e. волновая трассировка;

f. лучевая трассировка;

g. канальная трасировка.

14. Современные проблемы топологического синтеза.

a. технологические тенденции;

b. mPL5; методы гладкой аппроксимации целевой функции.

1. Г. Г. Казеннов, В. М. Щемелинин. Топологическое проектирование нерегулярных БИС. — М.: Высшая школа, 1990. — 109 с.

2. С. А. Ложкин. Лекции по основам кибернетики. — М,: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.

3. R. К. Brayton. Logic Synthesis. — Univ. of California, Berkeley, 2000.

4. T. Lengauer. Combinatorial algorithms for integrated circuit layout. — Wiley, 1990, 694 p.

5. Naveed Sherwani. Algorithms for VLSI physical design automation. — Kluwer academic publishers, 1995,538р.

6. Т. Cormen, С. Leiserson, R. Rivest. Introduction to Algorithms. — The MIT Press, Second Printing, 1996. Chapter 24, Minimum Spanning Trees, pp. 503-513.

7. P. Winter. Steiner Problem in Networks: A Survey. // Networks, Vol. 17, 8. Cong, He, Koh, Madden. Performance Optimization of VLSI Interconnect Layout. — Integration, the VLSI Journal, Vol. 21, 1996, pp. 1-94 (Sect. 3) 9. A. Hashimoto and J. Stevens. Wire routing by optimization channel assignment within large apertures. // Proc. of the 8th Design automation workshop, pp. 155-163, 1971.

10. David N. Deutsch. A "DOGLEG" Channel Router. // Proc. 13th Design Automation Conf., 1976, pp. 425-433.

11. L. Reed, A. Sangiovanni-Vincentelli, and M. Santamauro. A new symbolic channel router: Yacr2. // IEEE Transactions on Computer-Aided design, CAD-4(3): 208-219, 1985.

12. H. H. Chen and E. S. Kuh. Glitter: A Gridless Variable-Width Channel Router. // IEEE Transactions on Computer-Aided design., CAD- 5(4):

pp. 459-465, 1986.

13. Bryan Preas. Channel Routing With Non-Terminal Doglegs. // Proc. the European Design Automation Conference, Glasgow, Scotland, 1990, pp. 451-458.

14. H.-P. Tseng, C. Sechen. A Gridless Multi-layer Channel Router Based on a Combined Constraint Graph and Tile Expansion Approach.

// Proc. ISPD-International Symposium on Physical Design, 1996, pp. 210-217.

15. С L. Alpert, A. B. Kahng. Recent directions in netlist partitioning. A survey. — UCLA, Los Angeles, CA 90024-1596, 1994, 93 p.

1 - Полевые транзисторы, принцип их работы Математические вопросы проектирования 1 - Полевые транзисторы, принцип их работы Математические вопросы проектирования 1 - Полевые транзисторы, принцип их работы Математические вопросы проектирования 1 - Основные сведения о КМОП-технологии Математические вопросы проектирования 1 - Основные сведения о КМОП-технологии и проектировании СБИС Математические вопросы проектирования 2 - Функционирование и классификация КМОП-схем Математические вопросы проектирования 2 - Функционирование и классификация КМОП-схем Математические вопросы проектирования 2 - Функционирование и классификация КМОП-схем U КМОП - класс правильных комбинационных КМОП-схем.

Предполагается, что схемы из U КМОП не имеют входных БП, подаваемых в каналы транзисторов.

Число транзисторов схемы обозначается через L() и называется ее сложностью.

Следующие схемы не входят в U КМОП :

3 - КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами Математические вопросы проектирования 3 - КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами Математические вопросы проектирования 3 - КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами Математические вопросы проектирования 3 - КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами Математические вопросы проектирования 4 - Представление об RC-схемах и их задержке. Быстродействие КМОП-схем Открытый транзистор – RC-схема следующего вида:

4 - Представление об RC-схемах и их задержке. Быстродействие КМОП-схем 5 - Синтез правильных комбинационных КМОП-схем F=(f1,…,fm) – реализуемая система БФ; LКМОП(F) и LКМОП(n) – сложность системы F и функция Шеннона для сложности схем в UКМОП соответственно;

(1,m) – КС ’ реализует F, (1,m) – КС ” реализует F => КМОП схема =(p, n), у которой p-часть p строится по ’, а n-часть n – по ”, реализует F и является правильной комбинационной КМОП-схемой;

Моделирование КС дает оценку:

5 - Синтез правильных комбинационных КМОП-схем существенную БФ i ( x1,… xki ), - исходная библиотека КМОП-схем.

Б = {1,…, b }, где функциональный элемент i, i = 1,…, b, реализует БФ i со сложностью L(i ) - соответствующий ей базис схем из функциональных элементов (СФЭ).

Каждой СФЭ S над Б соответствует логически эквивалентная ей схема При этом в получаемых схемах отсутствуют цепочки из (k + 1) и более последовательно соединенных транзисторов.

5 - Синтез правильных комбинационных КМОП-схем Моделирование итеративных КС(ИКС) происходит аналогично моделированию КС и является наиболее эффективным с точки зрения сложности полученных схем.

Недостатком моделирования КС является наличие в получаемых схемах длинных цепей из последовательно соединенных транзисторов 6 - Клеточные схемы как «грубая»

топологическая модель СБИС Клеточные СФЭ – вложение СФЭ в плоскую прямоугольную решетку с возможными поворотами ФЭ на углы, кратные /2, с использованием КЭ для соединения входов и выходов ФЭ, с расположением входов и выходов схемы на границе решетки.

6 - Клеточные схемы как «грубая»

топологическая модель СБИС Математические вопросы проектирования 6 - Клеточные схемы как «грубая»

топологическая модель СБИС n - дешифратор порядка n из U Б0, построенный на основе асимтотически оптимального по числу ФЭ дешифратора A( n ) c 23n / 2.

A( F ) = min A() A(n) = max A( f ) A(n) 7 – Двухуровневый логический синтез и Система ДНФ допускает естественное вложение в ПЛМ.

7 – Двухуровневый логический синтез и Подкуб (элементарная конъюнкция) С куба Bn – j = xi, j C, считается простой буквой подкуб C\{j} не является импликантой f.

Импликанта C БФ f – простая импликанта, если все её буквы простые.

является покрытием f.

Покрытие F считается неизбыточным (тупиковым) все его подкубы неизбыточные (соответственно простые и неизбыточные).

Математические вопросы проектирования 7 – Двухуровневый логический синтез и Для БФ f(x1,…,xn) и подкуба C, C B n fc - результат подстановки в f фиксированных в C значений БП если F={C1,…,Cn} – покрытие f, то FC = {(C1 )C,..., (Ck ) C }покрытие fc.

7 – Двухуровневый логический синтез и Набор F=(f,d,r), где F: B {0,1,*} и f = (" "), d = ("*", r = ("0") – БФ g – доопределение F Подкуб C (покрытие F) считается простым подкубом (соответственно неизбыточным покрытием) F, если C – простой подкуб f+d (соответственно неизбыточное покрытие доопределения f).

Проверка на простоту и неизбыточность:

если G={C1,…,Cn} – покрытие F, а D – покрытие d, то Ci 7 – Двухуровневый логический синтез и ESPRESSO - эвристическая программная среда для двухуровневой минимизации, которая использует унарность БФ.

БФ f(x1,…,xn) – (+)-унарна ((-)-унарна) по xi f монотонно не убывает (соответственно не возрастает) Унарная БФ, то есть БФ унарная по каждой БП, имеет единственную тупиковую ДНФ – её сокращенную ДНФ.

ESPRESSO использует этот факт для оптимизации унарных БФ, связанных с таблицами покрытия.

Математические вопросы проектирования 8 – Многоуровневый логический синтез и связанные с ним представления Скобочные формы – формулы с поднятыми отрицаниями в базисе {&,, ¬}, построенные с использованием тождеств коммутативности, ассоциативности и дистрибутивности на базе ДНФ.

BDD от БП x1,…,xn – ориентированный ациклический граф с 1 истоком и двумя стоками, в котором стоки помечены символами “0” и “1”, а любая другая вершина имеет пометку xi,1 i n, и две исходящих дуги с пометками “0” и “1”. Считается, что BDD реализует БФ f – БФ проводимости от истока к её стоку с пометкой “1” (заметим, что БФ проводимости от истока к её стоку с пометкой равна f ).

Математические вопросы проектирования 8 – Многоуровневый логический синтез и связанные с ним представления BDD представляет собой, по существу, специальный класс контактных схем (КС) – класс ациклических КС из ориентированных контактов с одним истоком – входом и двумя стоками – выходами, в которой из каждой невыходной вершины исходит два противоположных контакта.

Операции приведения BDD:

удаление вершины, у которой обе исходящие дуги идут в одну слияние (отождествление) двух вершин, обладающих тем свойством, что БФ проводимости от каждой из них к выходу 8 – Многоуровневый логический синтез и связанные с ним представления Приведенная BDD – BDD, к которой применены все возможные операции удаления и слияния.

Упорядоченная BDD (OBDD) от БП x1,…,xn – BDD, в которой на любом пути от входа к выходам переменные встречаются в одном и том же «глобальном» порядке, причем каждая БП встречается не более 1 раза. OBDD представляет собой, по существу, КС, построенную по методу каскадов.

Математические вопросы проектирования 8 – Многоуровневый логический синтез и связанные с ним представления Порядок переменных может очень сильно влиять на сложность получаемой OBDD для заданной БФ. Так для мультиплексорной БФ k ( x1,..., xk, y0,..., y2k 1 ) n+ асимптотика этой сложности варьируется от 2n до n, Проблема выбора для заданной БФ оптимального по сложности получаемой OBDD порядка БП является NPтрудной.

9 – Основные подходы к многоуровневой оптимизации Технологически независимое описание многоуровневой комбинационной схемы представляет собой логическую сеть, то есть, по существу, схему из функциональных элементов (СФЭ) в базисе из всех БФ. При этом БФ, вычисляемые в вершинах сети, могут быть заданы таблицами, ДНФ, BDD или аналогичными сетями.

Математические вопросы проектирования 9 – Основные подходы к многоуровневой оптимизации Оптимизация сети проводиться, обычно, в два этапа:

оптимизация структуры сети;

оптимизация вершин сети (локальная Основной операцией, используемой при оптимизации структуры сети, является операция декомпозиции и её частные случаи (экстракция, факторизация, подстановка и др.), а также обратные к ним операции.

Имеется много различных эвристических критериев целесообразности применения тех или иных структурных операций.

Математические вопросы проектирования 9 – Основные подходы к многоуровневой оптимизации После выбора структуры сети осуществляется оптимизация функций, связанных с её вершинами. Основным инструментом такой оптимизации является выделение реальной области определенности этих функций с учетом особенностей их совместного поведения и использования техники don’t care.

Математические вопросы проектирования 9 – Основные подходы к многоуровневой оптимизации Кроме того, на каждом из этапов оптимизации часто используется техника булевского деления, то есть некоторое «частное», а r – «остаток». При этом в случае так называемого алгебраического деления, когда БФ g,h,r не имеют общих существенных БП возможно эффективное применение алгебраических Математические вопросы проектирования 9 – Основные подходы к многоуровневой оптимизации После оптимизации сети выполняется её привязка к библиотечному базису (mapping), то есть замена каждой внутренней вершины сети той схемой, построенной из элементов базиса, которая реализует БФ, связанную с этой вершиной. В результате получается логическая схема, которая направляется на следующие этапы проектирования – размещение и трассировку.

Математические вопросы проектирования Маршрут проектирования топологии Начальное размещ ение Определение областей трассировки Глобальная трассировка Определение 1: Пусть дано множество модулей V={v1,…,vn}. Kpartitioning Pk={C1,…,Ck} состоит из k взаимно непересекающихся кластеров таких, что C1C2 …Ck=V.

Определение 2: Min-cut bipartitioning – минимизировать F(P2)=|E(C1)|=|E(C2)| при C1 0, C2 0.

Определение 3: Min-cut bisection - минимизировать F(P2)=|E(C1)| при |w(C1)-w(C2)|.

Определение 4: Size-constrained min-cut bipartitioning – минимизировать F(P2)=|E(C1)| при L w(Ci) U, для i=1,2.

Определение 5: Minimum ratio cut bipartitioning – минимизировать F(P2)=|E(C1)|/(w(C1)w(C2)) Классификация алгоритмов декомпозиции электрической схемы Итерационные Геометрические Комбинаторные Кластерные i. Структура соседства (neighborhood structure) – определяет способы локального изменения текущего ii. Предистория – может быть использована для Алгоритм Кернигана-Лина (KL, 1970) Каждый модуль двигается строго один раз. KL итеративно меняет местами пару модулей с максимальным значением Алгоритм Кернигана-Лина (определения) Определение 10: Internal edge cost - для вершины procedure KL begin Pair:array[1:n/2] of pair of [1:n];

Cost:array[0:n/2] of integer;

Locked:array[1:n] of Boolean;

D:array[1:n] of integer;

C:array[1:n,1:n] of integer;

BestChange: [1:n/2];

BestCost: integer;

BestCost Cost[0] cutsize(A,B);

1. Все вершины графа должны быть единичного веса. Этого недостаточно для применения к схемам, т.к. размеры блоков 2. Разбиение должно быть строго сбалансировано. Для расширения нужно ввести фиктивные изолированные вершины.

3. Алгоритм не может быть применен к гиперграфам.

4. Сложность алгоритма слишком высока.

5. Эвристика включает в себя неопределенность, что может приводить к выбору плохих обменов и попаданию в локальный 6. Алгоритм эффективен для плотных графов (с большим числом Алгоритм Федуччи-Маттеуса (FM, 1982) Перемещается один модуль за одну итерацию, что позволяет получать несбалансированные решения Понятие gain расширено до гиперграфов Специальный способ для выбора перемещяемых вершин снижает вычислительную сложность Математические вопросы проектирования может различить:

Математические вопросы проектирования Begin температура INIT-TEMP; решение INIT-SOLUTION; качество COST(решение);

компонент1 SELECT(часть1); компонент2 SELECT(часть2);

until (температура FINAL-TEMP) Сходимость зависит от начальной точки Работа при высоких температурах малоэффективна Геометрические кривые охлаждения (T = M T0 ) более эффективны по сравнению с другими неадаптивными альтернативами (логаримическое и линейное охлаждение) Адаптивные стратегии охлаждения наиболее эффективны Математические вопросы проектирования температура INIT-TEMP решение INIT-SOLUTION новое_решение PERTURB(решение) C=COST(новое_решение )-COST(решение) if (Cexp(C/температура)) then 1. Одномерное представление – линейное упорядочивание списка 2. Многомерное представление – это множество n точек в d – мерном пространстве, где каждая точка соответствует определенному модулю. Между каждой парой точек определяется расстояние, что позволяет применять алгоритмы геометрической кластеризации для получения искомого 3. Многомерное векторное пространство – n модулей отображаются в n векторов в d – пространстве.

Пусть схема представлена взвешенным неориентированным графом G(V,E) с матрицей смежности A=(aij). nn матрица рангов D, где dij=deg(vi), dij=0 при ij. nn матрица Лапласа графа G есть Q=D-A. n – мерный вектор есть собственный вектор Q с собственным значением Q• = •. Можно предположить, что собственные вектора нормализованы: ||j||2=1. Пусть d dd диагональная матрица собственных значений 1,2,...,n.

Пусть Ud=(ij) - nd матрица собственных векторов, заметим, что Если предположить, что дихотомия описывается с помощью двоичного вектора x=(0,1,…), то целевая функция разбиения может быть вычислена следующим образом:

Холл показал, что оптимальное одномерное размещение по критерию квадрата длины соединений получается при x=2.

Каждая окружность – клика из заданного числа модулей Математические вопросы проектирования Coarsening phase – грубая фаза, на которой строится последовательность грубых приближений гиперграфа.

Initial partitioning phase - на которой наименьший гиперграф подвергается декомпозиции.

Refinement phase - на которой решение для наименьшего графа проецируется на следующий уровень и уточняется итерационным алгоритмом типа KL или FM.

Математические вопросы проектирования Edge Coarsening – простейший способ группировки вершин состоит в выборе пары вершин, принадлежащих одному и тому же гиперребру.

Hyperedge Coarsening – выбирается независимое множество гиперребер, вершины, принадлежащие одному гиперребру, объединяются.

Modified Hyperedge Coarsening Математические вопросы проектирования Математические вопросы проектирования Маршрут проектирования топологии Начальное размещ ение Определение областей трассировки Глобальная трассировка Математические вопросы проектирования 1. Определение размеров поля для размещения блоков:

2. Собственно размещение: