автореферат диссертации по электронике, 05.27.01, диссертация на тему:Нейросетевые модели обучаемых алгоритмов автоматизированного конструирования специализированных КМОП БИС

Введение.

1. Глава 1. АНАЛИЗ КОНСТРУКЦИИ И ТЕХНОЛОГИИ ИЗГОТОВЛЕНИЯ КМОП

СпецБИС И ВОЗМОЖНОСТЕЙ АДАПТАЦИИ МО ДЛЯ РЕШЕНИЯ ЗАДАЧ

АВТОМАТИЗИРОВАННОГО КОНСТРУИРОВАНИЯ.

1 Л. Конструкция и технология современных КМОП БИС.

1.2. Анализ применимости методов ИИ для проектирования КМОП СИС и методов обучения для адаптации МО САПР.

1.2.1. Знания о синтезе топологии ИС.

1.2.2. Методы обучения в адаптации МО САПР.

1.2.3. Нейросетевая модель знаний.

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

2. Глава 2. РАЗРАБОТКА И ИССЛЕДОВАНИЕ НЕЙРОСЕТЕВОЙ

МАТЕМАТИЧЕСКОЙ МОДЕЛИ ТРАССИРОВКИ.

2.1. Обучаемая модель трассировки.

2.2. Трассировка в дискретном рабочем поле.

2.3. Структура базы знаний.

2.4. Параметры управления процессом трассировки.

2.5. Выводы.

3. Глава 3. ОБУЧЕНИЕ МОДЕЛИ УПРАВЛЕНИЯ ТРАССИРОВКОЙ, ПРИ

ПОМОЩИ ИЗВЛЕЧЕНИЯ И АДАПТАЦИИ ПРЕЦЕДЕНТОВ.

3.1. База знаний на основе нейронной сети.

3.1.1. Выбор топологии сети.

3.1.2. Обучение нейронной сети.

3.2. Методика извлечения знаний о правилах проектирования.

3.2.1. Определение конфигурации отдельных проводников в топологическом образе ИС.

3.2.2. Синтез базы прецедентов.

3.2.3. Классификация прецедентов.

3.3. Выводы.

4. Глава 4. РЕАЛИЗАЦИЯ ОБУЧАЕМОЙ СИСТЕМЫ В ВИДЕ ПРОГРАММНОГО

КОМПЛЕКСА И ПРОВЕРКА ЭФФЕКТИВНОСТИ ЕГО РАБОТЫ.

4.1. Комплексация программного модуля трассировки в составе маршрута автоматизированного проектирования КМОП ИС.

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

4.3. Выводы.

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

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

Стремительный рост степени интеграции (Таблица 1.1.1. [72]) сопровождается непрерывным совершенствованием технологического процесса производства СБИС, что в свою очередь ведет к постоянному варьированию технологических норм проектирования.

Таблица 1.1.1. Рост сложности современных БИС

Технология, мкм 0,35 0,25 0,18 0,13 0,10 0,07

Год 1995 1998 2001 2004 2007 2010

Число тр-ров на кристалле 12М 28М 64М 150М 350М 800М

Тактовая частота, МГц 300 450 600 800 1000 1100

Площадь кристалла, мм2 250 300 360 430 520 620

Число слоев металлизации 4-5 5 5-6 6 6-7 7-8

Возникает необходимость разработки новых версий МО и ПО, оптимизированных для синтеза топологии в новом базисе ТНП. Существующая тенденция опережающего развития микроэлектроники по сравнению с развитием средств САПР обуславливает важность решения проблемы адаптации САПР к изменениям ТНП. В настоящее время проблема адаптации решается в основном путем создания специализированного МО и ПО, ориентированного на конкретные изделия [14]. В рамках этого 7 подхода совершенствование конструкций ИС и появление их новых технологических вариантов приводит к необходимости переработки моделей, алгоритмов и программ автоматизированного синтеза топологии, что существенно увеличивает сроки разработки ПО (до -20-30 чел/лет).

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

Определение: Искусственный интеллект [13] - область информатики, которая занимается разработкой интеллектуальных компьютерных систем, т.е. систем, обладающих возможностями, традиционно связываемыми с человеческим разумом - понимание языка, обучение, способность рассуждать, решать проблемы и т.д.

Существует множество направлений исследования ИИ: экспертные системы, нейросети, нечеткая логика и т.д [13]. Реализация методов обучения предполагает использование т.н. подхода, основанного на примерах (case-based). В этом случае описание предметной области осуществляется путем самонастройки адаптивной системы с заданной степенью достоверности при помощи достаточного количества примеров. Классическим примером реализации такого подхода являются нейронные сети.

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

Цель диссертационной работы:

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

Задачи диссертации:

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

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

3. Разработать и исследовать методики обучения алгоритмов синтеза топологии путем автоматического создания правил решения задачи при накоплении опыта проектирования в базе знаний САПР.

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

5. Разработать инструментальные средства автоматического обучения моделей и алгоритмов, позволяющие проектировщику СпецБИС самостоятельно, без привлечения программиста решать задачи адаптации и настройки математического обеспечения САПР.

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

Научная новизна работы заключается в следующем:

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

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

3. Разработана и исследована методика обучения алгоритмов синтеза топологии путем автоматического создания правил решения задачи при накоплении опыта проектирования в базе знаний САПР. Данная методика в отличие от традиционных методов параметрической настройки алгоритмов позволяет автоматизировать процесс получения управляющих параметров за счет обработки статистического материала результатов проектирования методами ИИ.

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

На защиту выносятся:

1. Математические модели накопления знаний о правилах синтеза топологии.

2. Структура базы знаний проектировщика СпецБИС.

3. Методика обучения алгоритмов синтеза топологии для конструирования СпецБИС.

4. Математическое обеспечение позволяющее реализовать накопление знаний.

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

Практическая ценность и результаты внедрения:

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

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

3. Разработанное программное обеспечение внедрено на предприятии электронной промышленности РНИИ Космического Приборостроения и получен эффект за счет снижения сроков подготовки САПР к работе на новом этапе эволюции конструкции и технологии КМОП СпецБИС.

10

4.3. Выводы.

1. Разработана методика включения режимов обучения и самообучения алгоритмов синтеза топологии в программный комплекс АК СпецБИС и предложен маршрут проектирования, включающий как одно из звеньев обучаемый программный комплекс трассировки СБИС.

2. На базе предложенной методики адаптации средств автоматизированного проектирования СБИС и аппаратных средств IBM РС-АТ Pentium-II в операционной системе Windows, разработано МО и ПО, включающее:

• Интерактивный иерархический редактор топологии, реализующий графический интерфейс пользователя для ввода исходных данных, оценки и коррекции полученной конструкции;

• Адаптируемую систему автотрассировки, интегрированную в редактор;

• Модуль LVS-верификации для проверки соответствия электрической схемы и топологии;

• Подсистему адаптации трассировки, реализующую метод обучения;

• Конверторы EDIF-II и SOURCE форматов для стыковки с другими промышленными САПР (OrCAD, ПУЛЬТ, КОВЧЕГ, ОТТО и т.д.).

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

4. Разработанное программное обеспечение внедрено на предприятии РНИИКП. Его использование дало положительный эффект за счет снижения сроков подготовки САПР к работе на новом этапе эволюции конструкции и технологии КМОП СпецБИС. Время настройки МО и ПО на различные конструктивно-технологические варианты СИС составило 0.5. 1 мин. Внедрение подтверждается соответствующим актом

5. Созданный программный комплекс САПР был использован при разработке топологии ИС Е5212КП0004, Е5212ВИ0003, Е5212ХЛ0001, Е5252НР0001, Е5212НР0002 в рамках НИР по темам "Русь", Яхта", "БИТС2Ц-5" и и показал

122 свою работоспособность и эффективность за счет применения обучаемых моделей трассировки соединений. Результаты эксплуатации позволяют включить ПО в стандарт предприятия "Система автоматизированного проектирования. Разработка КМДП больших интегральных схем" СТП ИЮ0.091.167-86.

123

5. Заключение

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

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

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

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

124

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

5. Исследованы нейронные сети различных типов, что позволило выбрать оптимальную конфигурацию сети и методы обучения. Показано, что из известных в настоящее время НС требованиям поставленной в диссертации задаче удовлетворяет многослойный персептрон, который предлагается использовать в качестве базовой модели обучаемых алгоритмов. Произведенные исследования базовой модели выявили состав параметров МСП нейросетевой модели, при выборе которых она удовлетворяет поставленным к базе знаний требованиям: по диапазону входных и выходных воздействий (областям определения и значения ФП), сложности ФП и скорости обучения.

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

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

125

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

9. Разработана методика включения режима обучения алгоритмов синтеза топологии в программный комплекс АК ИС и предложен маршрут проектирования, включающий как одно из звеньев обучаемый программный комплекс трассировки СБИС.

10. На базе предложенных моделей и алгоритмов разработано адаптируемое МО и ПО автоматизированного конструирования, обеспечивающее возможность автоматической настройки на заданные КТН. ПО внедрено на предприятии РНИИКП. Опробование разработанных методик, алгоритмов, моделей и программ произведено на задаче синтеза конструкции 5-и кристаллов БИС, которое показало уменьшение времени адаптации МО и ПО трассировки САПР на новые нормы производства с 20-30 чел*дней, требующихся при ручной параметрической настройке ПО до 0,5. 1-й минуты при использовании предложенных автоматических методов.

126

1. "1592ХМ1 Базовый матричный кристалл, 100000 вентилей" - М: Зеленоград ОАО

2. АНГСТРЕМ http://www.angstrem.ru, 11 с.

3. Абрайтис Л.Б. "Автоматизация проектирования топологии цифровых интегральных микросхем" . М: Радио и связь, 1985. 193 с.

4. Авенье Ж.П. "Обзор методов проектирования топологии ИС" ТИИЭР т.71, №1,январь 1993г. с 60-70.

5. Бачманов В.А., Кемарский П.А., Мухин Ю.А., Сошнев В.И., Трудновская Е.А.

6. Логико-электрическое моделирование в маршруте САПР БИС" Электронная промышленность, 1987 №5. стр.70-72.

7. Высоцкий Б.Ф, Сретенский В.Н. под ред. "Конструирование аппаратуры на БИС и

8. СБИС". М: Радио и связь, 1989. 272 с.

9. Гаврилова Т.А., Хорошевский. В.Ф. "Базы знаний интеллектуальных систем"1. СПб: Питер, 2000г.

10. Гилл Ф., Мюррей У., Райт М. "Практическая оптимизация" М.: Мир, 1985. 509 с.

11. Гмурман В.Е. "Теория вероятностей и математическая статистика" М.:

12. Высш.шк., 2002. 479 е.: ил.

13. Горбань А.Н. "Обучение нейронных сетей" М: СП ПараГраф, 1991

14. Гридин В.Н. "Теоретические основы построения базовых адаптируемых компонентов САПР МЭА" 1989 г.

15. Давиденко В.Н., Курейчик В.М. "Генетический алгоритм для трассировки двухслойных каналов" Автоматизация проектирования №1 1999 г.

16. Дегтярев Ю.И. "Методы оптимизации" М.: Сов. радио, 1980 272 с.

17. Джексон П. "Введение в экспертные системы" М.: Издательский дом "Вильяме",2001 -624с.

18. Ермак. В.В. под ред. "Проектирование К-МОП БИС на основе 5501ХМ2."1. М:МГИЭТ (ТУ), 1996, 180с.

19. Казеннов Г.Г. "Автоматизация проектирования БИС" в 6-ти томах М.: Высш.шк, 1990 г.

20. Каншин. М. "Последние из могикан, или Отечественные САПР заказных БИС"1. PC WEEK №26-27 1999г.

21. Каллан Р. "Основные концепции нейронных сетей" М.: Издательский дом "Вильяме", 2001 г.-288 с.

22. Каплин А.В. "Проектирование топологии СБИС методом инкапсулированныхбиблиотек", диссертация на соискание ученой степени к.т.н. М.: МГАИ 2000г.

23. Кондратьев В.В. "Адаптивные методы и алгоритмы проектирования топологии

24. БИС" Доклад VIII международный научно-технический семинар "Современные технологии в задачах управления, автоматики и обработки информации", Алушта, 1999 г. стр. 388.

25. Кондратьев В.В. "Проектирование топологии специализированных БИС на основе самообучающихся алгоритмов" Доклад Третья международная научно-техническая конференция "Электроника и информатика XXI век", Москва, 2000 г. стр. 231.

26. Кондратьев В.В. , Дембицкий H.JI. "Построение обучаемой САПР БИС на основеиспользования элементов экспертных систем"; МАИ. М.,2001 г - Рус.Деп. В ВИНИТИ. 31.05.01 № 1384-В2001.

27. Кондратьев В.В., Дембицкий H.JI. "Математическая модель обучаемой трассировки БИС"; МАИ. М.,2002 г - 18с.:ил. - Рус.Деп. В ВИНИТИ. 17.07.02 № 1349-В 2002.

28. Кондратьев В.В., Дембицкий H.JI. "Обучение подсистемы трассировки на основеметодов адаптации прецедентов"; Владимир, ВГПУ журнал "Информационные технологии" 2002 г, №2.128

29. Круглов В.В., Борисов В.В. "Искусственные нейронные сети. Теория и практика"

30. М: Горячая линия Телеком, 2001г. 382 с.

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

32. Лебедев Б.К. "Глобальная трассировка на основе генетической эволюции" Таганрог: ТРТУ Электронный Интернет-журнал. "Перспективные информационные технологии и интеллектуальные системы" 2000. №3 с.77-91. http://pitis.tsure.rur810 l/files3/PDF/s 12.pdf

33. Лорьер. Ж. -Л. «Системы искусственного интеллекта». -М.: «Мир», 1991, 586 с.

34. Лузин С.Ю., Полубасов О.Б. "САПР печатных плат "FreeStyle Route". Тез. докл.междунар. НТК "Современные технологии обучения", СПб, 1997, ТЭТУ, с. 178-180.

35. Лузин С.Ю., Полубасов О.Б. "Пакет гибкой топологической трассировки

36. FreeStyle Route". Материалы междунар. НТК "Системы и средства передачи и обработки информации". - Одесса, 1997, с.35.

37. Мкртчян С.О. "Нейроны и нейронные сети. (Введение в теорию формальныхнейронов)" — М.: Энергия, 1971. — 232 с.

38. Морозов К.К., Одиноков В.Г., Курейчик В.М. "Автоматизированное проектирование радиоэлектронной аппаратуры" М: Радио и связь, 1983. 280 с.

39. Назаров А.В., Фомин А.В., Дембицкий Н.Л. и др.; Под ред. Фомина А.В. "Автоматизация проектирования матричных КМОП БИС" М.: Радио и связь, 1991. -256с.

40. Нильсон Н. "Принципы искусственного интеллекта" М.: Радио и связь, 1985.337 с.

41. Нильсон Н. "Искусственный интеллект. Методы поиска решений" М.: Мир,1973. 270 с.

42. Новиков Ф.А. "Дискретная математика для программистов" СПб.: Питер, 2001.304 с.

43. Осовский С. "Нейронные сети для обработки информации" М.: "Финансы и статистика", 2002 г. 344 с.

44. Осуга. С."Обработка знаний" Москва «Мир» 1989, 293 с.

45. Осуга С. Саэки Ю. (ред.) "Приобретение знаний" М: Мир 1990129

46. Поспелов Д.А. "Фантазия или наука: на пути к искусственному интеллекту" М.:1. Наука, 1982.-224 с.

47. Разевиг. В.Д. "Система проектирования цифровых устройств OrCAD" М: «Солон-Р», 2000

48. Рябчук С.Г. "Модели и алгоритмы автоматизированного топологического синтеза, адаптирующиеся к конструктивно-технологическим вариантам цифровых микросборок интегральных РЭУ", диссертация на соискание ученой степени к.т.н. М.: МАИ 1988г.

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

50. Селютин В.А. "Автоматизированное проектирование топологии СБИС" 1983 г.

51. Сигорский В.Г. "Проблемная адаптация в системах автоматизированного проектирования" Известия высших учебных заведений: Радиоэлектроника. Том 31, №6, 1988 г.

52. Тизенберг А.Р., Михалева Л.П., Рыжкова О.В. "Система АСКТ для логическогопроектирования микропроцессорных СБИС и вычислительных систем на их основе". Электронная промышленность, 1987. №5. с.70-72.

53. Уоссермен Ф. "Нейрокомпьютерная техника" М: Мир, 1992 -240с.

54. Уотермен Д. "Руководство по экспертным системам" М: Мир, 1989. -388с.

55. Цыпкин Я.З. "Адаптация и обучение в автоматических системах" М.: Наука,1975.

56. Шахиди А. "Деревья решений" www.basegroup.ru/trees/description.html

57. Эйрис Р. "Проектирование СБИС: Метод кремниевой компиляции" М.: Наука1988 г. 456с.

58. Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992.

59. Borah M. Owens R. and Irwin M. "An edge-based heuristic for Steiner routing." IEEE

60. Trans, on Computer-Aided Design, vol. 13. pp 1563-1568. Dec. 1994.

61. Buchanan B.G. et al. "Constructing an expert system In Building Expert Systems",

62. Chapter 5. Reading, MA: Addison-Wesley

63. Cohoon J. and Richards D., "Optimal two-terminal a = 3 wire routing," Integration,

64. The VLSI J., vol. 6, no. 1, pp. 35-57, May 1988.

65. Cong J., He L., Khoo K.-Y., Koh C.-K., and Pan D. Z., "Interconnect design for deepsubmicron ICs," in Proc. Int. Conf. on Computer Aided Design, pp. 478^185, 1997.

66. Cong J., Kahng A. and Leung K. "Efficient algorithms for the minimum shortest path

67. Steiner absorbence problem with applications to VLSI physical design." IEEE Trans, on Computer-Aided Design, vol. 17, pp. 24-39, Jan. 1999.

68. Cong J., Fang J. and Zhang Y. "Multilevel Approach to Full-chip Multilevel Routing"

69. Cong J. and Yuan X. "Routing tree construction under fixed buffer locations." In Proc.37th Design Automation Conference, pp. 379-384, Jun. 2000.

70. Cong J. and Madden P. H. "Performance driven multi-layer general area routing for

71. PCB/MCM designs". In Proc. Design Automation Conf, pages 356-361, 1998.

72. Goering R. "Virage pioneers EPROM compilation" EE Times; June 26, 1998, EE1. Times Online.

73. Jaja J. and Wu S., "On routing two-terminal nets in the presence of obstacles," IEEE

74. Trans. Computer-Aided Design, vol. 8, no. 5, pp. 563-570, May 1989.

75. Kawamura K., Shindo Т., Shibuya Т., Miwatari H., and Ohki Y. "Touch and crossrouter" In Proc. Int. Conf. on Computer Aided Design, pages 56-59, 1990.

76. Koh C.-K., Madden P. H. "Manhattan or Non-Manhattan? A Study of Alternative

77. VLSI Routing Architectures"

78. Linsker R. "An iterative-improvement penalty-function-driven wire routing system"

79. M J. Research and Development, 28(5):613-624, September 1984.

80. Maniva T. "Focus report: Physical verification" Integrated System Design magazine1. Jan 2000, pp. 34-4272. "National Technology Roadmap for Semiconductors", Semiconductor Industry Association, 1997

81. Ohtsuki Т., "Gridless routers—new wire routing algorithms based on computationalgeometry," in Int. Conf Circuits Systems, 1985.131

82. Richard P. Lippmann, An Introduction to Computing with Neural Nets, IEEE Acoustics, Speech, and Signal Processing Magazine, April 1987.

83. Santarini M. "Virage re-architects SRAM compilers for 0.18 micron" EE Times;

84. March 29, 1999, EE Times Online.

85. Shervani N. "Algorithms for VLSI physical design automation". Kluwer academicpublishers, London 1995.

86. Shragowitz E. and Keel S. "A global router based on a multi-commodity flow model"1.tegration, the VLSI Journal, 5:3-16,1987.

87. Shin H. and Sangiovanni-Vincentelli A. "A detailed router based on incremental routing modifications: Mighty" IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, CAD-6(6):942-955, November 1987.

88. SPECCTRA. Version 5.3. Tutorial & User Reference. Cooper & Chyan Technology,1.c., 1994.

89. Wu Y., Widmayer P., Schlag M., and Wong C., "Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles," IEEE Trans. Computers, vol. C-36, no. 1, pp. 321-311, 1987.

90. Zheng S., Lim J. S., and Iyengar S., "Finding obstacle-avoiding shortest paths usingimplicit connection graphs," IEEE Trans. Computer-Aided Design, vol. 15, no. 1, pp. 103-110, Jan. 1996.132