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

ВВЕДЕНИЕ

1. СОВРЕМЕННЫЕ МЕТОДЫ И ПРОБЛЕМЫ ПРОЕКТИРОВАНИЯ ТОНКОПЛЕНОЧНЫХ МИКРОСБОРОК

1Л. Основные положения теоретико-графового подхода.

1.2. Модели представления схемы

1.3. Планаризация схемы и реализация непланарных соединений

1.4. Построение плоских чертежей схемы.

1.5. Разработка топологии с учетом размеров компонентов.

1.6. Выводы.

2. ПРЕДСТАВЛЕНИЕ СХЕМЫ, КОМПОНЕНТОВ

И КОММУТАЦИОННОГО ПРОСТРАНСТВА.

2.1. Триангуляция

2.2. Квазитриангуляция

2.3. Топологическая трассировка

2.3 Л. Чисто топологические методы

2.3.2. Метод гибкой трассировки

2.3.3. Shape-based трассировщики

2.3.4. Признак топологического трассировщика.

2.3.5. Недостатки метода гибкой трассировки

2.3.6. Два этапа - две модели.

2.4. Пленочные резисторы.

2.5. Навесные компоненты

2.6. Контакты и контрольные точки

2.7. Выводы.

3. РАЗРАБОТКА АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ . 58 3.1. Размещение компонентов.

3.2. Проверка наличия контрольных точек для измерения сопротивления каждого из резисторов.

3.3. Выделение в схеме контуров из резисторов и разрыв контуров

3.4. Выводы

4. ПРОГРАММНЫЙ КОМПЛЕКС ТРАССИРОВКИ

ТОНКОПЛЕНОЧНЫХ МИКРОСБОРОК "FreeStyle TF".

4.1. Состав программного комплекса автоматизированного проектирования микросборок

4.2.Технические характеристики комплекса

4.3. Создание новых корпусов элементов

4.4. Режимы работы и функции комплекса

4.4.1. Главное окно программного комплекса.

4.4.2. Создание нового проекта

4.4.3. Расчет параметров резисторов.

4.4.4. Ввод компонентов

4.4.5. Ввод цепей.ВО

4.4.6. Переход к режимам размещения и трассировки

4.4.7. Размещение компонентов.

4.4.8. Трассировка и редактирование.

4.4.9. Генерация документации.

4.5. Экспериментальная проверка результатов машинного проектирования.

4.6. Выводы.

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

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

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

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

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

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

Методы исследования

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

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

1. Адаптация метода гибкой топологической трассировки для проектирования устройств с однослойной коммутацией;

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

3. Методика вычисления оптимального расположения элемента, близкого к расположению, обеспечивающему минимум суммарной длины соединений, но обладающая меньшей комбинаторной сложностью;

4. Методы обеспечения контролепригодности топологии микросборки;

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

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

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

Реализация результатов работы

Результаты диссертационной работы в виде программного комплекса "FreeStyleTF" используются для проектирования тонкопленочных микросборок в АО "Авангард" (Санкт-Петербург).

Апробация результатов работы

Основные положения диссертационной работы докладывались и обсуждались на II международной НТК студентов, аспирантов и молодых специалистов стран СНГ "Техника и технология связи" (С.-Петербург, 2000г.); международной НПК "Современные информационные и электронные технологии" (Одесса, 2000г.); 4-й международной НПК конференции "Системы и средства передачи и обработки информации" (Одесса, 2000г.); 2-й международной НПК "Современные информационные и электронные технологии" (Одесса, 2001г.), 5-й международной НПК конференции "Системы и средства передачи и обработки информации" (Одесса, 2001г.); 8-й международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика" (Москва, 2002 г.); 6-й международной НПК конференции "Системы и средства передачи и обработки информации" (Одесса, 2002г.); 4-й международной НПК "Современные информационные и электронные технологии" (Одесса, 2003г.).

По материалам диссертации опубликовано 12 печатных работ, из них 12 тезисов докладов на научно-технических и научно-практических конференциях.

Структура и объем работы

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

4.5. Выводы

1. Разработана архитектура программного комплекса автоматизированного проектирования тонкопленочных микросборок с одним слоем коммутации.

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

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

4. Проведён сравнительный анализ результатов ручного и автоматизированного проектирования. Показано несомненное преимущество FreeStyleTF, заключающееся в сокращении в десятки раз сроков проектирования при одновременном существенном повышении качества и технологичности проектируемых изделий (сокращение суммарной длины проводников до 50%, уменьшение числа перемычек, возможность повышения степени интеграции без изменения проектных норм).

ЗАКЛЮЧЕНИЕ

Основные теоретические и практические результаты диссертационной работы заключаются в следующем:

1. Показано, что наиболее перспективным направлением проектирования устройств с однослойной коммутацией является применение метода гибкой топологической трассировки.

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

3. Разработан эффективный метод автоматизированного размещения компонентов.

4. Разработаны алгоритмические методы обеспечения контролепригодности микросборок.

5. Разработана архитектура программного комплекса автоматизированного проектирования тонкопленочных микросборок с одним слоем коммутации.

6. Разработан, оттестирован и передан в эксплуатацию в ОАО "Авангард "программный комплекс автоматизированного проектирования тонкопленочных микросборок.

7. Разработана методика проектирования устройств с однослойной коммутацией с использованием топологических методов.

1. Абакумов В.Г., Сербии С.А. Сравнительный анализ методов конструирования печатных плат. Управляющие системы и машины. 1981, Вып.5. С. 43-47.

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

3. Абрайтис Л.Б. Лучевой алгоритм для проведения печатных соединений. Вопросы радиоэлектроники. Сер. ЭВТ, 1968. Вып.З. С.35-45.

4. Абрайтис Л.Б., Блокскис И.С. Автоматизированный метод синтеза топологии интегральных схем. В сб.: Вычислительная техника, т. XII. - Вильнюс: Ред.- изд. совет МВССО Лит. ССТ, 1979, с. 12-128.

5. Абрайтис Л.Б., Гирнюс А.П. Канальная трассировка с учетом контактов разъемов и меняющейся ширины канала. Управляющие системы и машины, 1983. №6. С. 24-27.

6. Абрайтис Л.Б., Лянкявичус А.Н. Алгоритм параллельной глобальной трассировки двухслойных печатных плат. В сб.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике // КПИ. Вильнюс, 1983. Т.З., С. 12-20.

7. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичус В.А. Автоматизация проектирования ЭВМ. М.: Сов. радио, 1978. - 272 с.

8. Автоматизация проектирования цифровых устройств / Баранов С.И., Майоров С.А., Сахаров Ю.П., Селютин В.А. -Л.: Судостроение, 1979, -264с.

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

10. Автоматизированная система проектирования фотошаблонов на базе ЭВМ БЭСМ 6 / Г. Г. Казеннов, Б. В. Баталов, В. Е. Щербаков,

11. JI. В. Еремина. В кн.: Микроэлектроника / Под ред. А. А. Васенкова. - М.: Сов. радио, 1976, вып. 9, с. 22 - 26.

12. Автоматизация поискового конструирования (искусственный интеллект в машинном проектировании). Под ред. А.И. Половинкина -М.: Радио и связь, 1981, - 344с.

13. Автоматизация проектирования цифровых устройств./ Под ред. С.С. Бадулина. М.: Радио и связь, 1981. - 240с.

14. Аксенова Л.И., Бершадский A.M., Шигина Н.А. Задача оптимизации формы проводящего слоя аналоговых ГИС и ее решение. В сб.: Машинные методы конструкторского проектирования РЭА и ЭВА. - Изд. Саратовского у-та, 1983, с.44-46.

15. Арбузов В.А., Буркин Ю.В., Лебедев Б.В., Шигина Н.Н. Этап планаризации в топологическом проектировании микросборок с однослойной коммутацией. Автоматизация конструкторского проектирования РЭА и ЭВА. Пенза, ПДНТП, 1984, с. 62-63.

16. Арбузов В.А., Шокорова Н.Н. Решение задачи размещения при проектировании микросборок с одним слоем коммутации. В сб.: Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1986, с. 105-106.

17. Базилевич Р.П. Обобщенный подход к формализации задачи машинной трассировки межсоединений на плоскости.- Изв. Вузов СССР. Радиоэлектроника, 1974, т. 17, №6, с. 98-103.

18. Базилевич Р.П. Особенности использования аналогового рабочего поля для машинной трассировки межсоединений. Вычислительная техника. - Каунасский политехи, ин-т, 1974, т.4, с. 103-106.

19. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981. - 168 с.

20. Базилевич Р.П. Некоторые задачи синтеза планарных топологий. В кн.: Вычислительная техника, Вильнюс, 1979, Т. 12, с. 16-23.

21. Базилевич Р.П. Обобщённый подход к формализации задачи машинной трассировки межсоединений на плоскости. Изв. вузов СССР. Радиоэлектроника, 1974, N6, с. 98-103.

22. Базилевич Р.П., Гресько Ю.М. О топологическом построении множества не вошедших в плоские укладки соединений. Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1984, с. 63-65.

23. Балтрушайтис Р.И, Алгоритм снижения загруженности перегруженных областей монтажного пространства. В сб.: Вычислительная техника // КПИ, Вильнюс, 1982, т.16, с.15-17.

24. Баранов С.И., Майоров С.А. Сахаров Э.П., Селютин В.А. Автоматизация проектирования цифровых устройств. JL: Судостроение, 1979. -264с.

25. Барышникова Т.Н., Шигина Н.А. Модификация алгоритма Лемпела для плоской укладки графовой модели схем РЭА и ЭВА. В сб.: Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1986, с. 68-69.

26. Баталов Б.В., Магрупов Т.М. Определение соответствия топология большой интегральной схемы принципиальной электрической схеме. Микроэлектроника, 1974, т. 3, вып. 4, с. 305-311.

27. Батищев Д.И., Морозов В.Ф., Асланов А.А. Оптимальное размещение разногабаритных элементов на платах сложной конфигурации. -В сб.: Вычислительная техника, т. 9 Каунас: Изд. КПИ, 1976, с. 73-76.

28. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры. Л.: Энергия, 1979. - 120с.

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

30. Берштейн JI.C. Определений возможности плоской реализации схемы с помощью гиперграфов. В сб.: Автоматизация проектирования средств автоматики и вычислительной техники. - Изд. Саратовского у-та, 1976, с. 32.34.

31. Берштейн JI.C., Сапрыкин А.А. Минимизация наиболее длинных связей при линейном размещении элементов схемы. Изв. АН СССР, Техн. кибернетика, 1981, № 6, с.91-99.

32. Берштейн JI.C., Селянкин В.В. Линейное размещение гиперграфов. Изв. АН СССР, Техн. кибернетика, 1973. №> з? с.128 -135.

33. Бершадский A.M. Пакет прикладных программ системы автоматизации конструкторского проектирования гибридных БИС. В сб.: Вычислительная техника, т. 9. - Каунас: Изд. КПИ, 1976, с. 9-11.

34. Бершадский A.M., Лебедев В.Б., Фионова Л.Р. Размещение разногабаритных элементов микросборок средствами пакета прикладных программ "Компакт". Электронная техника, сер. 10 Микроэлектронные устройства, вып. 3(39), 1983, с.31-33.

35. Бурштейн М.И., Джибладзе Н.И., Сургуладзе Д.К. Расчет топологии интегральных микросхем. Электронная техника, сер. 3. Микроэлектроника, 1978, вып. 4 (76), с. 76-83.

36. Гайфуллин Э.Ш., Губарева О.И. Построение эскиза топологиигибридных интегральных микросборок с однослойной коммутацией. В сб.: Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1986, с. 107-108.

37. Гайфуллин Э.Ш., Губарева О.И., Старостина J1.A. Последовательный алгоритм размещения элементов ГИС. В сб.: Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1984, с. 111-112.

38. Гайфуллин Э.Ш., Старостина JI.A., Литвинова Л.Н. Размещение плоского графа ГИС, расположенного по концентрическим окружностям, с учетом метрики элементов. В сб.: Вычислительная техника // КПИ, Каунас, 1982, с.76.

39. Гайфуллин Э.Ш., Ярочкина Г.Я. Об одной задаче планариза-ции графа. В сб.: Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1986, с. 108-108.

40. Глориозов Е.Л., Иванников А.В., Сыпчук П.П. Автоматизация проектирования топологии интегральных схем. Обзоры по электронной технике, сер. 3. Микроэлектроника. - М.: ЦНИИ «Электроника», 1976, вып. 2 (362). - 76 с.

41. Гель П.П., Иванов-Есипович Н.К. Конструирование радиоэлектронной аппаратуры. Л.: Энергия, 1982, 232с.

42. Глушков В.М., Мясников В.А., Половинкин А.И. Автоматизация поискового конструирования. Вестник АН СССР, 1979, № 7. С.42-48.

43. Гндоян А.К. Об одном подходе к задаче трассировки. Вопросы радиоэлектроники, сер. ЭВТ, 1980, Вып.14, С. 43-47.

44. Горощенко А.Г. Сравнение критериев оптимизации межсоединений в радиоэлектронной аппаратуре. УСиМ, 1984, № 3, с.48-51.

45. Горощенко А.Г. Матричный метод проектирования межсоединений на типовых печатных платах. УСиМ, 1975, № 5, с. 128-132.

46. Григоровский Л.Ф., Куранов Б.В. Ускоренный последовательный алгоритм размещения конструктивных элементов. Тез. докл. Всесоюзного научно-технического совещания "Автоматизация проектирования микроэлектронной аппаратуры", Владимир, 1983, с. 223-224.

47. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. - 544 с.

48. Деньдобренко Б.Н., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. - 384 с.

49. Деньдобренко Б.Н., Селютин В.А. Опыт использования ЭВМ при конструировании радиоэлектронной аппаратуры. Л.: ЛДНТП, 1977. -32с.

50. Дмитриев П.И. Информационное обеспечение системы автоматизированного проектирования "FreeStyle EDA". Труды 3-й международной НПК "Современные информационные и электронные технологии"," Одесса, 2002, с. 171.

51. Дмитриев П.И., Елюсеев Д.В. Организация структур данных схемотехнического и топологического редакторов Материалы 5-й международной НПК "Системы и средства передачи и обработки информации", Одесса, 2001, с. 109-111.

52. Дмитриев П.И., Елюсеев Д.В., Рамме Ю.В. Автоматическая генерация изображений компонентов при чтении spice-файлов Материалы 5-й международной НПК "Системы и средства передачи и обработки информации", Одесса, 2001, с. 107-108.

53. Дмитриев П.И., Лячек Ю.Т., Потапова Т.В. Расширенный редактор принципиальных схем. Материалы 4-й международной НПК "Системы и средства передачи и обработки информации", Одесса, 2000, с. 83-84.

54. Дмитриев П.И., Лузин С.Ю., Полубасов О.Б. Проектирование устройств с однослойной коммутацией в комплексе FreeStyleTF. Материалы 6-й международной НПК "Системы и средства передачи и обработки информации", Одесса, 2002, с. 145-146.

55. Дмитриев П.И., Павлов С.Н., Потапова Т.В., Цветков П.Ю. Схемотехнический редактор XED. Труды международной НПК "Современные информационные и электронные технологии", Одесса, 2000, с. 6566.

56. Дмитриев П.И., Павлов С.Н., Цветков П.Ю. Схемотехнический редактор. // Доклады 2-й международной НТК студентов, аспирантов и молодых специалистов стран СНГ "Техника и технология связи", 1-3 февраля 2000 г., С.-Петербург, 2000, с. 237-238.

57. Евзович И.С., Шендерович Ю.И. Восстановление электрической схемы по чертежам ее конструкции. Электронная техника, сер. 7, Технология, организация производства и оборудование, 1973, вып. 4 (56), с. 45-46.

58. Зиман Э.Л., Рябов Г.Г. Волновой алгоритм и электрические соединения. В сб.: Электронные вычислительные машины / ИТМ и ВТ АН СССР. -М. 1965. - 104с.

59. Зудин С.В., Петросян Г.С., Полубасов О.Б., Лузин С.Ю. Система автоматизированного проектирования «FreeStyle 2.0». Труды 2-й международной НПК "Современные информационные и электронные технологии", Одесса, 2001, с. 198.

60. Зудин С.В., Полубасов О.Б. Современное решение задачи размещения. Труды международной НПК "Современные информационные и электронные технологии", Одесса, 2000, с. 71.

61. Зыков А. А. Теория конечных графов. Новосибирск: Наука, 1969. - 544 с.

62. Зыков А. А. Основы теории графов. М.: Наука, 1987. - 384 с.

63. Карапетян A.M. Автоматизация оптимального конструирования ЭВМ. М.: Сов. радио, 1973.

64. Кармазинский А. Н. Особенности системы проектирования БИС цифровых устройств на основе библиотечного набора элементов на полевых транзисторах. Микроэлектроника, 1973, т. 2, вып. 5, с. 442-447.

65. Климов В. Е., Неевина Н. П. Алгоритм укладки планарного графа на концентрических окружностях. Труды МЭИ, 1979, № 415, с. 9495.

66. Конструирование и расчет больших гибридных интегральных схем, микросборок и аппаратуры на их основе / Г. В. Алексеев, В. Ф. Борисов, Т. JI. Воробьев и др. Под ред. Б. Ф. Высоцкого. М.: Радио и. связь, 1981.-215 с.

67. Корбут А. А., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

68. Кристофидес Н. Теория графов. М.: Мир, 1978. - 423 с.

69. Кузьмин Б.А., Эйдес A.JL, Иругов Б.С. Адаптируемые системы автоматизированного проектирования печатных плат. М.: Радио и связь, 1984.- 140 с.

70. Курейчик В.М., Калашников В.А., Якшин В.В. Построение плоской укладки графа электрической схемы. Электронная техника, сер. 10 Микроэлектронные устройства, вып. 4(40), 1983, с.32-36.

71. Курейчик В.М., Королев А.Г. Применение алгоритма изоморфизма графов для контроля схем БИС. Микроэлектроника, 1976, т. 6, вып. 5, с. 400-406.

72. Курейчик В.М., Лисяк В.В., Перельман А.Л. Автоматизированные системы проектирования фотошаблонов БИС. Зарубежная радиоэлектроника, 1979, № 5, с. 74-89.

73. Лазарева Т.О., Крапчин Л.И., Покровский А.И. Алгоритм трассировки печатных соединений на основе представления о каналах. Автоматика и вычислительная техника, № 5, 1969, с. 12-15.

74. Литвинов З.Н. Об одном подходе к решению задачи минимизации длины связывающей сети при размещении геометрических объектов. В сб.: Размещение геометрических объектов и вопросы оптимального проектирования. ИК АН УССР, Киев, 1977. - 48с.

75. Лошаков В.Н. Параллельная трассировка соединений проводниками второго порядка. Электронная техника, сер. II. Комплексная микроминиатюризация радиоэлектронных устройств и систем, 1975, вып. 4, с. 66-66.

76. Лошаков В.Н., Широ Г.Э. Метод машинного проектирования топология функциональных образований комплементарных МОП БИС. -Электронная техника, сер. II. Комплексная микроминиатюризация радиоэлектронных устройств и систем, 1976, вып. 3 (6), с. 54-64.

77. Лузин С.Ю., Полубасов О.Б. САПР печатных плат "FreeStyle Route". Материалы международной конференции "Современные технологии обучения", С.-Петербург, 1997, с. 178-180.

78. Лузин С.Ю., Полубасов О.Б. Трассировка печатных плат. Новые методы решения старых проблем. "САПР и графика", 1997, №11, с. 58-59.

79. Лузин С.Ю., Полубасов О.Б. Визуализация алгоритмов трассировки. Материалы международной конференции "Современные технологии обучения", С.-Петербург, 1998, с. 127.

80. Лузин С.Ю., Полубасов О.Б., Холод И.И. Синтез планарной топологии ячеек БИС. Труды 2-й международной НПК "Современные информационные и электронные технологии", Одесса, 2001, с. 202-203.

81. Львов Н.П., Петрова Г.В. Использование плоского графа для синтеза топологии интегральной схемы. В сб.: Вычислительная техника // КПИ, Каунас, 1982, с.74-75.

82. Маркосян С.Е. О раскраске вершин графов интервалов. Вопросы радиоэлектроники, сер. 7. Электронная вычислительная техника, 1972, выл 4 с. 3-7.

83. Мелихов A.M., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. -304с.

84. Мелихов А.К., Берштейн Л.С., Селянкин В.В. Минимизация пересечений проводников в канале с помощью гиперграфов. АиВТ, 1977, № 4. С.77-82.

85. Мельничук И.Г., Толстун A.M., Горощенко Л.Г. Базовая программа оптимизации распределения связей и модулей. Управляющие системы и машины, 1983. №5. С.31-33.

86. Микстуров В.Н. Комбинаторика укладок. Киев: Изд. ин-та кибернетики АН УССР, 1975. - 53 с.

87. Модифицированная система автоматизированной разработки фотошаблонов МАРТ / Булин С.В., Кузнецова Л.Н., Куклане А.Н., Селютин В.А. В сб.: Машинные методы проектирования электронно-вычислительной аппаратуры. - JL: Изд. ЛДНТП, 1981, с. 29-32.

88. Морозов К.К. и др. Методы разбиения схем на конструктивно-законченные части. М.: Радио и связь, 1978. - 134с.

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

90. Морозов К.К. к др. Проектирование монтажных плат на ЭВМ. -М.: Советское радио, 1979. 224с.

91. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1979. -272с.

92. Пенней У., Jlay Л. Интегральные схемы на МДП-приборах. -М: Мир 1975.-628 с.

93. Петренко А.И. Основы автоматизации проектирования. Киев.: Техника, 1982. - 295с.

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

95. Петренко А.И., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Советское радио, 1979. -253с.

96. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологическая трассировка с переразмещением соединений. Вычислительная техника. -Каунасский политехи, ин-т, 1977, т.9, с.89-91.

97. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологические алгоритмы трассировки многослойных печатных плат. -М.: Радио и связь, 1983. 152с.

98. Подсистема автоматизированного проектирования топологии БИС ячеечного типа / JI. Б. Абрайтис, Д. А. Рубляускас, В. А. Штуйкис, И,-К. JI. Матицкас. Управляющие системы и машины, 1974, № 5, с. 79-81.

99. Подсистема машинного синтеза топологии МОП-БИС / Се-лютин В.А., Ромм Г.Р., Булин С.В., Гольдберг С.А. Управляющие системы и машины, 1976, № 4, с. 119-132.

100. Полубасов О.Б. Расслоение плоской реализации двудольного графа. В сб.: Автоматизация проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1990, с. 62-64.

101. Полубасов О.Б. Гибкий метод трассировки печатных плат. -Всесоюзная НТК "Совершенствование технических средств связи для решения проблем информатизации общества в новых условиях хозяйствования", Тез. докладов, Ленинград, 1991, с. 87-88.

102. Полубасов О.Б. Локальное редактирование топологии печатной платы. Всесоюзная НТК "Совершенствование технических средств связи для решения проблем информатизации общества в новых условиях хозяйствования", Тез. докладов, Ленинград, 1991, с. 89-90.

103. Полубасов О.Б. Декомпозиция задачи трассировки печатных плат. В сб.: Автоматизация проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1991, с. 53-55.

104. Полубасов О.Б., Алексеев М.И., Стекольщиков А.В., Зудин С.В. "FreeStyle Router" А.с. № 980492 от 14.08.1998 г.

105. Полу басов О.Б., Алексеев А. А. Оптимизация расположения элементов топологии. Труды 2-й международной НПК "Современные информационные и электронные технологии", Одесса, 2001, с. 204.

106. Полубасов О.Б., Зудин С.В. К вопросу о квадратичном размещении ячеек на БИС. Технология и конструирование в электронной аппаратуре, 1999, №5-6, с. 10-13.

107. Полу басов О.Б., Лузин С.Ю. Пакет гибкой топологической трассировки "FreeStyle Route". Материалы международной НПК "Системы и средства передачи и обработки информации" («ССПОИ»), Одесса, 1997, с. 35.

108. Полубасов О.Б., Стекольщиков А.В. Модель платы для автоматического редактирования печатного монтажа. В сб.: Автоматизация проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1992, с. 30-32.

109. Полубасов О.Б. Глобальная минимизация количества меж-слойных переходов. Технология и конструирование в электронной аппаратуре, 2001, №2, с. 3-9.

110. Полубасов О.Б. Математические модели и алгоритмы автоматизированной разводки соединений печатных плат и БИС. Диссертация на соискание ученой степени кандидата технических наук. СПбГЭТУ (ЛЭ-ТИ), 2001 г.

111. Помазанов В.М. К задаче о размещении ячеек в панели. В кн.: Применение вычислительных машин для проектирования цифровых устройств. Под ред. Н. Я. Матюхина. М., "Сов. радио", 1968.

112. Попов В. 3., Нефедов В. С. Структура и организация данных системы проектирования топологии специализированных БИС. В сб.: Применение вычислительной техники при управлении сложными объектами. - М.: Изд. ин-та проблем управления, 1978, № 15, с. 83-84.

113. Поса Дж. Вентильные матрицы: современное состояние техники и технологии. Электроника, 1980, т. 63, № 31, с. 54-74.

114. Пратусевич М.Л. Усовершенствованные математические модели для построения плоских реализации схем. В сб.: Автоматизация проектирования в электронике. - Киев, 1981, вып. 24, с. 30-36.

115. Пратусевич M.JI., Селютин В. А. Построение плоских реализации схем с учетом конструктивных ограничений. Микроэлектроника, 1980, №3, с. 202-208.

116. Пузина С.В., Рябов Л.П., Темницкий O.K. Повышение эффективности алгоритма рекапитуляции печатного монтажа. Обмен опытом в радиопромышленности, 1983. № 11, с. 56-57.

117. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М.: Мир, 1980. - 476с.

118. Романовский И.В. Алгоритмы решения экстремальных задач., -М.: Наука, 1977, 352 с.

119. Ромм Г. Р. Об алгоритмах предварительного машинного анализа топологии МОП-БИС, заданной ее эскизом. Электронная техника. Сер. 3. Микроэлектроника, 1976, вып. 4 (64), с. 3-10.

120. Рубцов В.П., Захаров В. П., Жижко В.А. Автоматизация проектирования больших интегральных схем. Киев: Техника, 1980. - 232 с.

121. Рябов Л.П., Темницкий Ю.Н. Деформация лабиринта при автоматической доразводке проводников печатных плат. Обмен опытом в радиопромышленности, 1978, вып. 4-5, с.88-89.

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

123. Селютин В.А. Автоматизированное проектирование БИС. М.: Радио и связь, 1982. - 113с.

124. Селютин В.А. Модели и алгоритмы синтеза топологии схем с одним слоем коммутации. Электронная техника, сер. 10. Микроэлектронные устройства, вып. 1 (7), 1978, с. 76-82.

125. Селютин В.А. О формальном методе конструирования схем с нерегулярной топологией. В сб.: Конструирование микроэлектронной аппаратуры. Материалы семинара. - Л.: Изд. ЛДНТП, 1976, с. 49-53.

126. Селютин В.А. Язык для описания топологии шаблонов МОП БИС. Микроэлектроника, 1973, т. 2, вып. 5, с. 448-453.

127. Селютин В.А., Булин С.В., Гуревич Д.З. Машинный контроль топологии шаблонов БИС. Микроэлектроника, 1975, т. 4, вып. 2, с. 125129.

128. Селютин В.А., Гуревич Д.З. Автоматизированная система разработки и изготовления фотошаблонов БИС. Управляющие системы и машины, 1974, № 5, с. 71-74.

129. Селютин В.А., Пратусевич M.JI. Подсистема автоматизированного синтеза топологии электронных схем с одним слоем коммутации. В сб.: Автоматизация технического проектирования, т. 1. - Вильнюс: Ред.-изд. совет МВССО ЛитССР, 1981, с. 20-28.

130. Система автоматизации проектирования многокристальных больших интегральных схем МБИС / Рябов Г. Г., Блинова Л. А., Васильева Г. Г. и др. В кн.: Вычислительная техника, т. VII. - Каунас: Изд. КПИ, 1974, т. 6, с. 14-18.

131. Система контроля топологии интегральных схем на базе мини-ЭВМ с использованием дисплеев. / Казеннов Г.Г., Шепелев В.А., Попова Т.П., Власенко В.А. В кн.: Микроэлектроника / Под ред. Васенкова А.А. -М.: Сов. радио, 1976, вып. 9, с. 289-296.

132. Система машинного проектирования топологий изделий электронной техники / Лошаков В.Н., Широ Г.Э., Осипов Л.Б., Брусникин Г.Н.- Электронная техника, сер. 10. Микроэлектронные устройства, 1977, вып. 6, с. 73-81.

133. Ситников А.Г., Добряков В.А., Сорокопуд В.А. Автоматизация проектирования тонкопленочных микросборок. Тез. докл. Всесоюзного научно-технического совещания "Автоматизация проектирования микроэлектронной аппаратуры", Владимир, 1983, с. 245.

134. Смолич Г.Г., Смолич Л.И. Минимизация числа переходных отверстий при проектировании двухсторонних печатных плат. Обмен опытом в радиопромышленности, 1984, вып.11. с.54-56.

135. Соколов В.А., Фридман М.Г., Шеин П.,Д. Состояние и перспективы развития систем автоматизированного проектирования двухсторонних печатных плат. Изв. АН СССР, Техническая кибернетика, 1982, №2, с.171-178.

136. Состав и организация специального программного обеспечения системы автоматизированного проектирования «заказных» больших интегральных схем / Тютин А.А., Попов Т.Е., Котенко Е.С. и др. Управляющие системы и машины, 4974, № 6, с. 119-124.

137. Соукуп И. Компоновка электронных схем. ТИИЭР, 1981. т.69, с.119-145.

138. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наумова думка, 1976. - 248 с.

139. Сухарев А.В., Золотов А.И. Модели и процедуры оптимизации в автоматизации проектирования. (Программный комплекс FreeStyle Router): Учеб. пособие. СПб.: СЗТУ, 2001. - 165с.

140. Теория и методы автоматизации проектирования вычислительных систем // Под ред. Бреуера М. М.: Мир, 1977. - 284с.

141. Тетельбаум А.Я. Об одном методе оптимального размещения конструктивных единиц и внешних контактных площадок. В кн.: Автоматизация проектирования в электронике. Вып.11., Киев.: Техника, 1975, с. 98-103.

142. Тетельбаум А.Я. О числе классов изотопных укладок графов. . -Изв. АН СССР. Техн. Кибернетика. 1980. №3. С. .

143. Тетельбаум А.Я. Силовое размещение планарного графа. Изв. АН СССР. Техн. Кибернетика. 1988. №3. С. 131-137.

144. Тетельбаум А.Я. Прямолинейная укладка графа с квазиминимальным числом пересечений ребер. Изв. АН СССР. Техн. кибернетика. 1989. №2. С. 173-175.

145. Тетельбаум А.Я., Шрамченко Б.Л. Применение гиперграфов при исследовании планарности электронных схем. Изв. АН СССР, Техн. кибернетика. 1978. №5. С. 127-136.

146. Фейнберг В.З., Рабинович Е.Б. Организация баз данных в геометрических задачах проектирования больших интегральных схем. -Докл. АН БССР, 1986, Т. XXX. №5. С. 406-409.

147. Фейнберг В.З. Геометрические задачи машинной графики больших интегральных схем. М.: Радио и связь, 1987, - 176 с.

148. Финкелынтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1973, - 231с.

149. Фионова Л.Р. Выбор и применение модели компонентов при решении задачи размещения разногабаритных элементов ГИС. В сб.: Машинные методы конструкторского проектирования РЭА и ЭВА. - Изд. Саратовского у-та, 1983, с.41-43.

150. Фойер М., Хохани К. X., Мехта Д. Программа автоматизированной трассировки связей кристалла с 5 тысячами, логических вентилей. -Электроника, 1980, т. 53, № 22, с. 35-38.

151. Фомин А.В., Боченков Ю.И., Сорокопуд В.А. Технология, надежность и автоматизация производства БГИС и микросборок. М.: Сов. Радио, 1981. -362 с.

152. Форд JI.P., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966, - с.

153. Харари Ф. Теория графов. М.: Мир, 1973. - 300с. 1978.

154. Хопкрофт Дж.Е., Тарьян П.Е. Изоморфизм планарных графов. -Кибернетический сборник, вып.12., 1975, с. 39-61.

155. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974,-520 с.

156. Шигина Н.Н., Арбузов В.А., Краснова Е.А. Алгоритм и программа укладки на плоскости графовой модели однослойной ГИС. В сб.: Автоматизация конструкторского проектирования РЭА и ЭВА. - Пенза, ПДНТП, 1984, с. 61-62.

157. Широ Г.Э. Метод проектирования печатного монтажа, основанный на эвристических принципах. В кн.: Методы разработки схем и конструкций цифровых систем. 4.2. - JL: ЛДНТП. 1967.

158. Широ Г.Э. Алгоритм трассировки, использующий деформацию ранее проложенных проводников. Вычислительная техника. - Каунасский политехи, ин-т, 1976, т.8, с. 136-139.

159. Шрамченко Б.Л., Абакумов В.Г. Об определении матрицы смежности модулей. В кн.: Автоматизация проектирования в электронике. Вып. 11., Киев.: Техника, 1975, с. 95-98.

160. С. J. Alpcrt "A direct combination of the Prim and Dijlcstra constructions for improved performance-driven global routing." Proc. Of ISCAD93. pp. 1869-1872 (1993).

161. M. L. Brady and D. J. Brown "Arbitrary planar routine with four layers," in Proc. Conf. on Advanced Research in VLSI. MIT, pp. 194-201, 1984.

162. S. С. Chang, К. Т. Cheng, N. S. Woo, M. Marek-Sadowska Layout Driven Logic Synthesys, Proc. DAC. 1994, pp. 308-313.

163. J. Cong and B. Pleas "A new algorithm for standard cell global routing." Proc. of ICCAD88. pp. 176-179 (1988).

164. J. Cong. A. Kahng, G. Robins. M. Sarrafzadeh, and С. K. Wong "Provably good performance-driven global routing," IEEE Trans. Computer-Aided Design, Vol. 11, No. 6, June 1992.

165. D. N. Deutsch "A Dogleg Channel Router," in Proc. 13th IEEE Design Automation Conf., pp. 425-433, 1976.

166. Duggal R., Holland Т., Messinger H. P. A comparision of new and existing placement algorithms for auto-print circuit board layout. "Proc. Nat. Electr. Conf.", 1968, vol. 29, pp. 694-700.

167. M. Edahiro and T. Yoshiroura "New placement and global routing algorithm for standard cell layouts," Proc. of 27th DAC, pp. 642-645 (1990).

168. A. Fallah and J. Rose, Timing-driven routing segment assignment in FPGAs," Canadian Conf. on VLSI, 1992.

169. R. C. Garden and C.K. Cheng: "A global rooter using an efficient approximate multicommodity multitennmal flow algorithm," Proc. of 28th DAC. pp. 316-321 (1991).

170. S. E. Hambrusch "Using overlap and minimizing contact points in channel routing" in Proc. 21st Ann. Atlerton Conf. on Comm., Contr., and Сотр., 1983.

171. Hambrusch S. E. Channel Routing Algorithm for Overlap Models. -IEEE Trans. Computer-Aided Des., Vol. CAD-4, No.l, JANUARY 1985, p.23-40.

172. J. Heisterman and T. Lengauer "The efficient solution of integer programs for hierarchical global routing," IEEE Trans. CAD, Vol. 10, No. 6. pp. 748-753 (1991).

173. Hitchock R.B. Cellular wiring and the cellular modeling technique. -Proc. 6-th Des. Autom. Worcshop: Miami Beach, June, 1969, p.25-41.

174. J.M. Ho, D. T. Lee, C.H. Chang, and С. K. Wong "Minimum diameter spanning trees and related problems," SIAM J. Compute, Vol. 20. No. 5, pp. 987-997, 1991.

175. J. Huang "An efficient timing-driven global routing algorithm," Proc. of 30th DAC pp. 596-600 (1993).

176. M. Khellah. S. Brown, and Z. Vraneaic "Modelling Routing Delays in SRAM-based FPGAs," Canadian Conf. on VLSI, 1993.

177. Lee C.I. An algorithm for path connections and its applications. -IRE Trans., 1961, v. EC-10, №3, p.345-365.

178. Leigthon F.T., Rosenberg A.L. Tree-Dimentional Circuit Layouts. SIAM J. Comput. Vol.15, No. 3, August 1986, p. 793-813.

179. Lempel A., Even A., Cederbaum I. An Algorithm for Planarity Testing of Graph. Theory of Graphs, International Symp. Rome, Gordon and Breach, 1966, p. 215.

180. R. Lin "Channel density reduction by routing over the cells." Proc. of 28th DAC. pp. 120-125 (1992).

181. S.P. Lin, M. Marek-Sadowska, and E.S. Kuh "Delay and Area Optimization in Standard Cell Design". In Design Automation Conference, pp. 349-352. IEEE/ACM, 1990.

182. K. Mehlhorn, F. P. Preparata, and M. Sarrafzadeh "Channel routing in knock-knee mode: simplified algorithms and proofs," Algorithmica vol. 1, no. 2, pp. 213-221, Oct. 1986.

183. G. Meixner and U. Lautfaer "A new global router based on a flow model and linear assignment" Proc. of ICCAD90. pp. 44-47 (1990).

184. R. Nair, C. L. Berman, P. S. Hauge, and E. J. Yoffa "Generation of Performance Constraints for Layout". IEEE Transactions on Computer Aided1.l

185. Design, CAD-8(8):860-874, August 1989.

186. F. P. Preparata and W. Lipski "Optimal three-layer channel routing," IEEE Trans. Computers, vol. C-33, pp. 427-437, 1984.

187. F. P. Preparata and M. Sarrafzadeh "Channel routing of nets of bounded degrees," in VLSI: Algorithms and Architectures. P. Bertolazzi and F. Luccio, Eds. New York: North-Holland, 1985, pp. 189-203.

188. Prim "Shortest connecting networks and some generalizations." Bell System Tech. J., pp. 1389-1401, 1957.

189. J. Reed. : "A new symbolic channel router YACR2." IEEE Tans. CAD. Vol. 4. No. 3. pp. 205-219 (1985).

190. R. L. Rivest, A. Baratz, and G. Miller, "Provably good channel routing algorithms," in Proc. 1981 CMU Conf. VLSI Syst. Computar., Oct. 1981, pp. 153-159.

191. R. L. Rivest, С. M. Fiduccia, "A "Greedy" channel router," in Proc. 19th IEEE Design Automation Conf., pp. 418-424, 1982.

192. Sarafzadeh M. Channel-Routing Problem in the Knock-Knee Mode is NP-Complete. IEEE Trans. Computer-Aided Des., Vol. CAD-6, No.4, JULY 1987, p.503-506.

193. M. Sarrafzadeh and F. P. Preparata, "Compact channel routing of multiterminal nets," Ann. Discrete Math., no. 25, pp. 255-279, Apr. 1985.

194. A. Sechen and A. Sangiovanni-Vincentelli. "A New Standard Cell Placement and Global Routing Package". In Design Automation Conference, IEEE, ACM, 1986. pp. 432-439.

195. A. Srimvasan "RITUAL: A performance driven placement algorithm for small cell ICs," Proc. of ICCAD91. pp. 48-51 (1991).

196. W. Swaitz and С Sechen: "A new generalized row-based global router," Proc. of 1С CAD93. pp. 491-498 (1993).