автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование алгоритмов двухмерного сжатия топологии СБИС

ВВЕДЕНИЕ.

1. ОБЗОР И АНАЛИЗ АЛГОРИТМОВ СЖАТИЯ ТОПОЛОГИИ СБИС.

1.1 Постановка задачи сжатия.

1.2 Классификация алгоритмов сжатия топологии СБИС.

1.3 Одномерное сжатие.

1.4 1.5-мерное сжатие.

1.5 Двухмерное сжатие.

1.6 Иерархическое сжатие.

1.7 Выводы.

2. РАЗРАБОТКА ПОДХОДА К ЗАДАЧЕ СЖАТИЯ ТОПОЛОГИИ СБИС.

2.1 Постановка задачи.

2.2 Подход к решению задачи.

2.3 Пример процесса сжатия ячейки мультиплексора.

2.4 Выводы.

3. РАЗРАБОТКА МЕТОДОВ ОПИСАНИЯ ТОПОЛОГИИ СБИС НА БАЗЕ НАБОРА ПРИМИТИВОВ.

3.1 Общие сведения.

3.2 Разработка методов создания и описания примитивных геометрических объектов.

3.3 Разработка метода описания слоев и конструкторских правил.

3.4 Построение абстрактных объектов для компонентов СБИС.

3.5 Разработка методики описания технологических правил для изготовления СБИС.

3.6 Методика расчета основных параметров ячеек.

3.7 Выводы.

4. РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ МОДИФИКАЦИИ ТОПОЛОГИИ СБИС.

4.1 Разработка алгоритма перемещения узла.

4.1.1 Разработка алгоритма определения возможности перемещения узла

4.1.2 Разработка алгоритма построения очереди примитивов для модификации топологии.

4.2 Определение временной сложности алгоритмов модификации топологии

4.3 Выводы.

5. РАЗРАБОТКА АЛГОРИТМА ДВУХМЕРНОГО СЖАТИЯ ТОПОЛОГИИ СБИС НА ОСНОВЕ МЕТОДА ИМИТАЦИИ ОТЖИГА.

5.1 Общие сведения.

5.2 Разработка алгоритма сжатия топологии СБИС на основе метода имитации отжига.

5.3 Выбор целевой функции.

5.4 Выводы.

6. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО АЛГОРИТМА СЖАТИЯ ТОПОЛОГИИ СБИС.

6.1 Выбор параметров целевой функции.

6.2 Выбор значений управляющих параметров процесса имитации отжига

6.3 Определение временной сложности алгоритма сжатия топологии СБИС

6.4 Сравнение предложенного алгоритма с аналогами.

6.5 Выводы.

Возникшая в 60-х годах XX века технология создания интегральных схем развилась, за короткое время, от создания интегральных схем, объединяющих несколько транзисторов, до интеграции миллионов транзисторов в одной схеме. Первые интегральные схемы (ИС) представляли собой объединение одиночного транзистора с набором сопротивлений, предназначенное для выполнения какой-либо логической функции. ИС способны выполнять сложнейшие функции. В настоящее время, элементы могут иметь геометрические размеры до 0.25 микрона. Современная технология позволяет разместить 10-15 миллионов транзисторов на схеме размером 25мм. X 25мм. Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [1]. Сейчас, на всех стадиях проектирования топологии сверхбольших ИС (СБИС) интенсивно используют средства автоматизации проектирования и многие фазы могут быть полностью или частично автоматизированы [1-25].

Цикл проектирования СБИС включает следующие основные фазы: спецификация системы, функциональное проектирование, логическое проектирование, схемное проектирование, конструкторское проектирование, изготовление, сборка, тестирование и контроль.

Спецификация системы заключается в разработке описания системы. Основными определяющими факторами являются производительность, функции и физические размеры системы. Спецификация системы - это компромисс между -рыночными требованиями, технологическими и экономическими возможностями Г ~ Результатом спецификации является описание размеров, производительности и функциональных возможностей системы.

На этапе функционального проектирования определяются основные функциональные устройства системы, определяются взаимосвязи между ними. Основной задачей ставится определение поведения входов, выходов и задержек каждого компонента системы, без определения его внутренней структуры.

Фаза логического проектирования заключается в определении размера слов, распределения регистров и управляющих потоков, арифметических и логических операций. Для логического описания систем используют язык УНБЬ. Логическое описание включает минимизированные булевы функции и описание временных задержек. При логическом проектировании делается моделирование и тестирование системы для проверки корректности построенной системы.

Целыо схемного проектирования является преобразование результатов логического проектирования в схемы. На этом этапе выполняется схемное моделирование для проверки корректности и задержек каждого компонента. Результатом схемного проектирования является подробное схемное представления системы.

Следующим этапом является конструкторское проектирование. На этом этапе схемное представление системы преобразуется в геометрическое представление. Строится множество геометрических образов, которые выполняют требуемые логические функции представленных компонентов. Соединения между различными компонентами также представляют в виде геометрических образов. Конструкторское проектирование - это комплексный процесс, включающий в себя множество шагов. Результатом этого этапа является проверенное описание топологии схемы.

После верификации топология схемы преобразуется в набор масок. Использование масок, во время различных технологических процессов, позволяет изготовить твердотельную структуру схемы. Обычно на одной пластине кремния диаметров 20 см. удается разместить несколько сотен чипов.

На последних этапах производится тестирование и контроль полученных схем, осуществляется сборка, помещение в защитный корпус и маркировка.

Этап конструкторского проектирования подразделяется на разбиение, планирование, размещение, трассировку, сжатие и верификацию.

Поскольку сейчас ИС может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию вссп схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема разбивается группирование компонентов на блоки. В результате разбиения формируется множество блоков и множество соединений между блоками. Задача планирования заключается в определении взаимного расположения блоков относительно друг друга. Задачей размещения является определение конкретного места для каждого блока на кристалле. Трассировка заключается в конструктивной реализации связей между элементами.

После завершения детальной трассировки топология является функционально полной. На этом этапе топология готова для производства СБИС. Однако после алгоритмов размещения и трассировки в топологии остаются пустые места. Для того чтобы уменьшить себестоимость СБИС и увеличить производительность уменьшают площадь топологии путем уменьшения пустого места без изменения функциональности СБИС. Задачей сжатия топологии является уменьшение размеров топологии во всех направлениях для уменьшения общей площади схемы. Сжатие позволяет уменьшить длину связей и временные задержки между компонентами схемы. Уменьшение площади одного чипа с помощью сжатия позволяет размещать большее число чипов на площади одной подложки.

На последнем этапе делается верификация топологии спроектированной схемы. Она заключается в проверке геометрических размеров, ограничений, временных задержек и других параметров, влияющих на работоспособность схемы.

Цель сжатия топологии - минимизация общей площади топологии без нарушения производственных ограничений и ограничений, заданных проектировщиком. Существует три способа уменьшения площади:

- Уменьшение расстояний между элементами. Это выполняется перемещением элементов так близко друг к другу как это возможно. При этом необходимо соблюдать конструкторские ограничения расстояний между элементами.

- Уменьшение размеров элементов. При этом необходимо соблюсти конструкторские ограничения размеров элементов.

Изменение форм элементов. При этом необходимо сохранить электрические характеристики при изменении формы.

Ранние попытки автоматизированного сжатия топологии использовали только прямоугольники вдоль осей х и у. Эти методы минимизировали топологию вдоль каждой осп независимо. Такие методы известны, как одномерное сжатие. Основная проблема при таком подходе состоит в том, что сжатия по горизонтали и вертикали не являются взаимозаменяемыми и получаемая топология сильно зависит от исходной конфигурации. Двухмерные методы соединяли два одномерных сжатия в одно. Было доказано, что такой метод является ИР-сложным. Оба метода, ограничиваются проводниками, которые не могут изгибаться.

Сжатие топологии это сложный этап в цикле проектирования СБИС. На этом этапе используется информация о многочисленных деталях производственного процесса, таких как проектировочные правила и ограничения. Сжатие топологии важно для проектирования полностью заказных СБИС, особенно если необходима высокая производительность полученной СБИС.

В этой связи, тема работы, связанная с разработкой новых методов сжатия топологии СБИС является АКТУАЛЬНОЙ.

ЦЕЛЬЮ диссертационной работы является разработка новых и модифицированных методов и алгоритмов сжатия топологии СБИС, позволяющих уменьшать площадь топологии и длину соединительных проводников.

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

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

Для достижения поставленной цели были поставлены следующие задачи: 1. Разработка схемы процесса эволюционного поиска для задач сжатия топологии СБИС.

2. Разработка структур!,I данных для представления топологии в криволинейном виде.

3. Разработка процедур перехода от одного решения к другому.

4. Разработка целевой функции для оценки качества решения.

5. Исследование эволюционных алгоритмов для сжатия топологии СБИС.

Для решения поставленных задач были использованы следующие МЕТОДЫ ИССЛЕДОВАНИЙ: элементы теории множеств, элементы теории алгоритмов, элементы теории эволюционного поиска.

ОСНОВНЫЕ ПОЛОЖЕНИЯ И РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ:

1. Новый метод описания топологии СБИС, имеющей криволинейную структуру.

2. Новый алгоритм видоизменения и модификации топологии СБИС, с учетом выполнения конструкторских ограничений.

3. Новый общий подход и алгоритм сжатия топологии СБИС, основанный на методе имитации отжига.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1. Впервые представлен метод описания топологии СБИС, имеющей криволинейную структуру, упрощающий процедуру видоизменения и модификации топологии СБИС.

2. Разработан алгоритм видоизменения и модификации топологии с учетом выполнения конструкторских ограничений, имеющий линейную временную сложность.

3. Создан общий подход и алгоритм сжатия топологии СБИС, основанный на методе имитации отжига.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1. Метод представления топологии СБИС в криволинейном виде.

2. Алгоритм п программа сжатия топологии СБИС, позволяющие уменьшить площадь топологии СБИС и длину соединительных проводников.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Результаты работы внедрены в РОСНИИ ИТ и АП (Москва) и НИИ ТКБ (Таганрог) в качестве ПО САПР проектирования топологии СБИС.

Кроме того, материалы диссертации использованы в учебном процессе тта кафедре САПР ТРТУ при проведении практических занятий и курсовом проектировании по курсам «Методы генетического поиска» и «Автоматизация конструирования ЭВА».

АПРОБАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные результаты диссертационной работы обсуждались и были одобрены на научных семинарах ТРТУ «Генетические алгоритмы», на IV Всероссийской конференции студентов и аспирантов ТРТУ, на Всероссийской конференции "Интеллектуальные САПР-97", на XLIII студенческой научной конференции ТРТУ (секция Интеллектуальный САПР).

ПУБЛИКАЦИИ.

Результаты диссертации отражены в 6 печатных работах. СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, шести глав, заключения, списка литературы. Работа содержит 164 страницы, включая 133 рисунков, 8 таблиц, список литературы из 108 наименований, 25 страниц приложений с актами об использовании работы, примерами топологий, полученных в результате экспериментальных исследований и примерами топологий, полученных для стандартных тестов.

6.5 Выводы

С помощью серии экспериментов были подобраны параметры целевой функции. Проведено исследование влияния размера центрального потенциала'на"" результат сжатия топологии СБИС. Установлено, что наилучшие результаты получаются при размере центрального потенциала равном идеальной площади ячейки.

Для оптимизации процесса поиска в результате экспериментальных исследований произведен выбор расписания отжига, который состоит из выбора первоначальной температуры, скорости уменьшения температуры и условия останова процесса отжига для каждой температуры.

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

Оценена теоретическая и экспериментальная ВСА алгоритма. Теоретическая временная сложность алгоритма пропорциональна 0(N*log(A)), где N - количество узлов, а А - площадь ячейки. Экспериментальная ВСА получилась такого же порядка, что и теоретическая.

Эксперименты показывают, что основным параметром, влияющим на временную сложность, является центральный потенциал. Будущие исследования должны привести к созданию метода управления центральным потенциалом, который приведет к лучшим результатам сжатия и ограничит рост времени работы до 0(N*log(A)).

Проведено сравнение результатов «ручного» сжатия и результатов автоматического сжатия с помощью предложенного алгоритма на шести разных ячейках. Показано, что предложенный метод уменьшает площадь топологии в среднем на 7 % по сравнению с «ручным» или полуавтоматическим сжатием.

ЗАКЛЮЧЕНИЕ

1. Представлена область применения и приведена постановка задачи сжатия топологии СБИС, ориентированная на современные технологии.

2. Проведен анализ существующих подходов к решению задач сжатия топологии СБИС. На основе проведенного анализа для решения задачи сжатия топологии была выбрана криволинейная геометрия и стохастический метод имитации отжига. Это позволяет получать качественные результаты за приемлемое время.

3. Разработана новая структура данных для представления криволинейной топологии СБИС. Структура данных специально оптимизирована для метода имитации отжига.

4. Разработаны методы модификации топологии, позволяющие учитывать конструкторские ограничения и недопускающие их нарушения.

5. Разработана структура поискового процесса на основе метода имитации отжига для сжатия топологии СБИС с учетом специфики решаемой задачи.

6. Сформирована целевая функция, позволяющая минимизировать площадь топологии и длину проводников, в зависимости от материала.

7. Создан программный комплекс на языке С++ для компилятора Borland Builder 5.0, реализующий разработанные алгоритмы.

8. С помощью проведенных экспериментальных исследований подобраны числовые значения для управляющих параметров.

9. На этапе исследований разработанных алгоритмов была экспериментально определена временная сложность алгоритма. Временная сложность алгоритма пропорциональна 0(N*log(A)), где N — количество узлов, а А — площадь ячейки.

10. Проведенные исследования показывают, что применение криволинейной геометрии и метода имитации отжига позволяет уменьшить площадь топологии на 5-10% по отношению к ранее используемым методам.

1. Sherwani N.A. Algorithms for VLS1.Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

2. S. Kirkpatrick, C. Gelatt and M Vecchi, "Optimization by Simulated Annealing," Science,220(4598), May 1983, pp. 671-680.

3. Schlag M., Liao Y.-Z. and Wong C.K., "An Algotithm for optimal two-dimensional compaction of VLSI layouts", North-Holland INTEGRATION, the VLSI journal 1 (1983) pp. 179-209.

4. Boyer D.G., "Symbolic Layout Compaction Review", 25th ACM/IEEE Design Automation Conference (1988), Paper 26.1, pp. 383-389.

5. Dai W., Eschermann В., Kuh E.S., Pedram M., "Hierarchical Placement and Floorplanning in BEAR", IEEE Transaction on Computer-Aided Design, Vol. 8, No. 12, 1989, pp. 1335-1348.

6. Hsieh T.M., Leong H.W., Liu C.L., "Two-Dimensional Layout Compaction by Simulated Annealing", in Proc. IEEE International Symposium on Circuits and Systems, June 1988, Espoo, Finland, vol.3, pp. 2439-2443

7. Liao Y.-Z., Wong C.K., "An Algorithm to compaction a VLSI symbolic layout with mixed constraint", IEEE Trans. On CAD of Integrated Circuits and Systems, 1983, vol.CAD-2, no.2, pp.62-69.

8. Курейчик B.M. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М., Радио и связь, 1990.

9. Корячко В.П., Курейчик В.М., Норепков И.П. Теоретические основы САПР: Учебник для Вузов. М., Энергоатомиздат, 1987. 400 с.

10. Разработка САПР. Под ред. А.В. Петрова. М., Высшая школа, 1990.

11. Абрайтис JI.A. Автоматизация проектирования топологии цифровых интегральных микросхем. М., Радио и связь, 1985. 200 с.

12. Вермишев Ю.Х. Основы автоматизации проектирования. М., Радио и связь, 1988.

13. Казенов Г.Г., Сердобинцев E.B. Проектирование топологии матричных БИС. M., Высш. шк., 1990. 112 с.

14. Петренко А.И., Лошаков В.М., Тительбаум А. и др. Автоматизированое проектирование СБИС на базовых кристаллах. М., Радио и связь, 1988.

15. Селютин В.А. Машинное конструирование электронных устройств. М., Советское радио, 1977.

16. Петухов Г. А. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М., Радио и связь, 1987. 57 с.

17. Курейчик В.М. Математическое обеспечение КТП с применением САПР. М., Радио и связь, 1990. 352 с.

18. Файзулаев Б.Н., Шагурин И.П. Быстродействующие матричные БИС и СБИС. Теория и проектирование. М., Радио и связь, 1989.

19. Деньдобренько Б.П., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980.

20. Готра З.Ю., Григорьев Л.М. Сквозное проектирование микроэлектронной аппаратуры, М., Радио и связь, 1989.

21. Норенков И.П. Системы автоматизированного проектирования в радиоэлектронике. М., Радио и связь, 1986.

22. Петренко А.И., Тетельбаум А. Автоматизация проектирования БИС. Киев, Виша школа, 1983.

23. Карберри П.П. Персональные компьютеры в автоматизированном проектировании. М., Машиностроение, 1989.

24. Сорокопуд В. А. Автоматизированное конструирование мпкроэлектронпых блоков с помощью малых ЭВМ. М., Радио и связь, 1988.

25. Ульман Дж.Д. Вычислительные аспекты СБИС. М., Радио и связь, 1990.

26. Казенов Г.Г. Автоматизация проектирования БИС. М., Высшая школа,1990.

27. Ведерникова О.Г., Чернышев 10.0. Исследование алгоритма имитации отжига для решения задач размещения при проектировании БИС. Таганрог, ТРТУ, 1995.

28. Курейчик В.М., Родзин С.И. Контролепрнгодное проектирование и самотестирование СБИС. Проблемы и перспективы. М., Радио и связь, 1994.

29. Бондалетов А.В., "Двухмерная упаковка со связями. I часть.", Известия ТРТУ №3, г.Таганрог 1999.

30. Бондалетов А.В., "Двухмерная упаковка со связями. II часть.", Известия ТРТУ №3, г.Таганрог 1999.

31. S. Chow, Н. Chang, J. Lam, and Y. Liao, "The Layout Synthesizer: An Automatic BlockGeneration System," in proc. 1992 CICC., pp. 11.1.1-11.1.4.

32. V. Friedman and S. Liu, "Dynamic Logic CMOS Circuits," IEEE J. Solid State Circ., 19(2),Apr. 1984, p. 265.

33. M. Garey, D. Johnson, "Computers and Intractability: A Guide to the Theory ofNP-Completeness," W. H. Freeman, 1979.

34. A. Gupta and J. Hayes, "Width Minimization of Two-Dimensional CMOS Cells Using Inte-ger Linear Programming," in proc. 1996 ICCAD, pp. 660-667.

35. A. Gupta and J. Hayes, "CLIP: An Optimizing Layout Generator for Two-DimensionalCMOS Cells," in proc. 34th DAC, 1997, pp. 452-455.

36. A. Gupta and J. Hayes, "Optimal 2-D Cell Layout with Integrated Transistor Folding," inproc. 1998 ICCAD, pp. 128-135.

37. M. Guruswamy, R. Maziasz, D. Dulitz, S. Raman, V. Chiluvuri, A. Fernandez and L. Jones,"CELLERITY: A Fully Automatic Layout Synthesis System ^for Standard Cell Libraries," in proc. 1997 DAC, pp. 327-332.

38. A. Conn, P. Coulman, R. Haring, G. Morrill and C. Visweswariah, "Optimization of CustomMOS Circuits by Transistor Sizing," in proc. 1996 ICCAD, pp. 174-180.

39. T. Corman, C. Lciserson and R. Rivest, "An Introduction to Algorithms," The MIT Press,Cambridge, 1990.

40. S. Devadas, "Optimal Layout Via Boolean Satisfiability," in proc. 1989 ICCAD, pp. 294-297.

41. S. Hambrusch and H. Tu, "Minimizing Total Wire Length During 1-Dimensional Compaction," INTEGRATION, 14(2), 1992, pp. 113-144.

42. N. Hedenstierna and K. Jeppson, "CMOS Circuit Speed and Buffer Optimization," IEEETrans. on CAD, 6(2), March 1987, pp. 270-281.

43. M. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, "An Efficient General Cooling Schedule for Simulated Annealing," in proc. 1986 ICCAD, pp. 381-384.

44. S. Hustin and A. Sangiovanni-Vincentelli, "TIM, a New Standard Cell Placement ProgramBased on the Simulated Annealing Algorithm," unpublished Master's Thesis, University of California at Berkeley.

45. M Kang, W. Dai, "Arbitrary Rectilinear Block Packing Based on Sequence Pair," in proc. 1998 ICCAD, pp. 259-266.

46. J. Kleinhaus, G. Sigl, F. Johannes, and K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Trans, on CAD, 10(3), March 1991.

47. G. Lakhani and R. Varadarajan, "A Wire-Length Minimization Algorithm for Circuit LayoutCompaction," in proc. 1987 ISCAS, pp. 276-279.

48. J. Lam and J. Delosme, "An Efficient Simulated Annealing Schedule: Derivation," Yale Uni-versity, New Haven, Connecticut, Technical Report 8816, Sept. 1988.

49. E. Malavasi and D. Pandini, "Optimum CMOS Stack Generation with Analog Constraints,"IEEE Trans, on CAD, 14(1), Jan. 1995, pp. 107-122.

50. R. Maziasz and J. Hayes, "Layout Optimization of Static CMOS Functional Cells," IEEETrans. on CAD, 9(7), July 1990, pp. 708-719.

51. R. Maziasz and J. Hayes, "Exact Width and Height Minimization of CMOS Cells," in proc.28th DAC, 1991, pp. 487-493

52. R. Maziasz and J. Hayes, "Layout Minimization of CMOS Cells," Kluwer Academic Pub-lishers, Boston, 1992.

53. C. Mead and L. Conway, "Introduction to VLSI Systems," Addison-Wesley, Reading, Mass., 1980.

54. H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "Rectangle Packing Based ModulePlacement," in proc. 1995 ICCAD, pp. 472-479.

55. H. Onodera, Y. Taniguchi, and K. Tamaru, "Branch-and-Bound Placement for BuildingBlock Layout," in proc. 28th DAC, 1991, pp. 433-439.

56. R. Rutenbar, "Simulated Annealing Algorithms: An Overview," IEEE Circ. and Dev. Mag.,January 1989, pp. 19-26.

57. R. Saigal, "Linear Programming: A Modern Integrated Analysis," Kluwer Academic Pub-lishers, Boston, 1995.

58. S. Sait and H. Youssef, "VLSI Physical Design Automation, Theory and Practice," McGrawHill Book Company, London, 1995.

59. L. Scales, "Introduction to Non-Linear Optimization," Springer-Verlag, New York, 1985.

60. W. Schiele, "Improved Compaction by Minimized Length of Wires," in proc. 20th DAC, 1983, pp. 121-127.

61. C. Sechen, "Chip-Planning, Placement, and Global Routing of Macro/Custom Cell Inte-grated Circuits using Simulated Annealing," in proc. 25th DAC, 1988, pp. 73-80.

62. R. Statnikov and J. Matusov, "Multicriteria Optimization and Engineering," Chapman &Hall, New York, 1995.

63. K. Tani, K. Izumi, M. Kashimura, T. Matsuda and T. Fujii, "Two-Dimensional Layout Synthesis for Large-Scale CMOS Circuits", in proc. 1991 ICCAD,pp. 490-493.

64. T. Uehara and W.M. VanCleemput, "Optimal Layout of CMOS Functional Arrays," IEEETransactions on Computers, C-30(5), May 1981, pp. 305-312.

65. T. Wang and D. Wong, "An Optimal Algorithm for Floorplan Optimization," in proc. 27thDAC, 1990, pp. 180-186.

66. D. G. Boyer. Symbolic Layout Compaction Benchmarks Results. In IEEE International Conf. on Computer Design, 1987.

67. F. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. Rulling, and C. Storb. On Continuous Homotopic One Layer Routing. In Proceedings of 4th Annual Symposium on Computational Geometry, 1988.

68. D. S. Harrison, P. Moore, R. L. Spickelmier, and A. R. Newton. Data Management and Graphics Editing in the Berkeley Design Environment. In 4th International Conference on Computer-Aided Design (ICCAD 86), pages 24-27.

69. Min-Yu Hsueh. Symbolic Layout and Compaction of Integrated Circuits. PhD thesis, University of California at Berkeley, Berkeley, California, December 1979.

70. E. Liu. Two Dimensional IC Layout Compaction. PhD thesis, University of Calgary, Calgary, Alberta, Canada, December 1986.

71. E. Liu, P. de Dood, R. Suaya, and J. Wawrzynek. A Topological Framework for Compaction and Routing. In Advanced Research in VLSI, 1991.

72. F. M. Maley. Single Layer Wire Routing. PhD thesis, Massachusetts Institute of Technology, August 1987.

73. R. C. Mosteller. REST-A Leaf Cell Design System. In Very Large Scale Integration, University of Edinburgh, Edinburgh, Scotland, August 1981. Academic Press.

74. R. C. Mosteller, A. Frey, and R. Suaya. 2-D Compaction a Monte Carlo Method. In Proceedings of the Stanford Conference on Advanced Research in VLSI. MIT Press, 1987.

75. F. Preparata and M. I. Shomos. Computational Geometry An Introduction. Springer-Verlag, 1985.

76. H. Shin and C. Lo. An efficient two-dimensional layout compaction algorithm. In 26th ACM/IEEE Design Automation Conference, 1989.

77. H. Shin, A. Sangiovanni-Vincentelli, and C. H. Sequin. Zone-Refining Techniques for IC Layout Compaction. IEEE Transactions on CAD of ICs and System, 9(2), February 1990.

78. J. Valainis, S. Kaptanoglu, E. Liu, and R. Suaya. Two Dimensional IC Layout Compaction Based on Topological Design Rule Checking. IEEE Transactions on CAD of ICs and System, 9(3), March 1990.

79. N. Weste. Virtual grid symbolic layout. In Proc. 18th Design Automation Conf., pages 225-233, 1981.

80. Петренко А.И., Тетельбаум А.Я. Автоматизация конструирования электронной аппаратуры (топологический подход). Киев. Виша школа, 1980.

81. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВМ. Саратов. 1983.

82. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М., Радио и связь, 1990. 216 с.

83. Лебедев Б.К. Канальная трассировка на основе динамических принципов и методов минимизации комбинаторной размерности. «Интеллектуальные САПР», выпуск 5, Таганрог, 1995.

84. Marek-Sadowska М. Switchbox routing, a retrospective. Integration, The VLSI Journal, 13, 1992.

85. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley publishing company Inc., Massachusetts, 1989. 412p.

86. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991.

87. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.

88. Курейчик В.М. Генетические алгоритмы и их применение в САПР. Интеллектуальные САПР, Таганрог, 1995.

89. Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. Proc. of the second Intl. Conf. Adaptive Computing in Engeneering, Design and Control, Plymouth, UK, 1996

90. Мину M. Математическое программирование. M., Наука, 1990.

91. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

92. Пападпмитрну X., СтаЛглнц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., Мир, 1985.

93. Зайчепко Ю.П. Исследование операций. Киев, Виша школа, 1975.

94. Страуструп Б. Язык программирования Си++. М., Радио и связь, 1991.

95. Подбельский В.В. Язык Си++: Учебное пособие. М., Финансы и статистика, 1995.

96. Голуб А.И. С и С++. Правила программирования. М., БИНОМ, 1996.

97. Бептли Д. Жемчужины творчества программистов. М., Радио и связь,1990.

98. Лэнгсам Й., Огенстайн М., Тетельбаум А. Структура данных для персональных ЭВМ. М., Мир, 1989.

99. Липский В. Комбинаторика для программистов / пер. с польского. М., Мир, 1988.

100. Львовский E.H. Статистические методы построения эмпирических формул. М., Высшая школа, 1988.

101. Митропольский А.К. Техника статистических вычислений. М., Наука,1971.

102. Останин А.Н. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учебное пособие. Минск Вышэйшая школа, 1989.

103. Адлер Ю.П. Введение в планирование эксперимента. М., Металлургия,1969.