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

ВВЕДЕНРШ.

I. ПРОБЛЕМЫ И СОВРЕМЕННЫЕ МЕТОДЫ

ПРОЕКТИРОВАНИЯ ПЕЧАТНЫХ ПЛАТ.

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

1.2. Проблемы прокладки трасс.

1.3. Проблемы минимизации числа межслойных переходов.

1.4. Выводы.

ГЛАВА П. МИНИМИЗАЦИЯ ЧИСЛА МЕЖСЛОЙНЫХ ПЕРЕХОДОВ.

2.1. Расслоение совмещённой топологии.

2.2. Редукция графа доменов.

2.3. Пример редукции графа доменов.

2.4. Дополнительный набор преобразований.

2.5. Точки разветвления трасс и планарные контактные площадки

2.6. Выводы.

ГЛАВА Ш. ЗАДАЧА ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ РАССЛОЕНИЯ НА ЭТАПЕ МАКРОТРАССИРОВКИ.

3.1. Разбиение монтажного пространства на клетки.

3.2. Минимизация числа требуемых слоев.

3.2.1. Ориентация рёбер. Сведение к полиномиальной задаче.

3.2.2. Алгоритм минимизации числа слоев.

3.3. Минимизация количества межслойных переходов.

3.3.1. Комбинаторная постановка задачи.

3.3.2. Ориентация рёбер. Задача о распределении ресурсов в сетевом графике работ.

3.3.3. Алгоритм минимизации числа переходов.

3.4. Однослойная технология.

3.5. Планарные клеммы.

3.6. Выводы.

ГЛАВА IV. КОНТРОЛЬ ГЕОМЕТРИЧЕСКИХ

СООТНОШЕНИЙ МЕЖДУ ОБЛАСТЯМИ ТОПОЛОГИИ.

4.1. Анализ традиционных алгоритмов.

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

4.3. Выводы.

ГЛАВА V. РЕДАКТИРОВАНИЕ ТОПОЛОГИИ.

5.1. Плавно изгибающиеся проводники.

5.2. Перемещение элементов с сохранением разводки.

5.3. Выводы.

ГЛАВА VI. ПРАКТИЧЕСКОЕ ПРИПМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ. ПРОГРАММНЫЙ

КОМПЛЕКС ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ

Ггее81у1еКои1е.

6.1. Технические характеристики Ргее81у1еКои1е.

6.2. Режимы и функции Егее81у1еКои1е.

6.3. Сравнение с другими системами.

6.4. Выводы.

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

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

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

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

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

На защиту выносятся следующие новые научные положения:

1. Эффективный (линейный по числу операций и требуемой памяти) алгоритм точного решения задачи расслоения совмещенной топологии проводящего рисунка с целью минимизации количества меж-слойных переходов для случая двух трассировочных слоев.

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

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

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

Но мнению автора, основная практическая ценность работы заключается в создании программного комплекса Ргее81у1еКои1е, зарегистрированный в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) под номером 980492 от 14.08.1998 г.

Комплекс тестировался и показал отличные результаты на платформах: MS-DOS ver 5-7; OS/2 v3, сессия DOS; Windows 95, 98, сессия DOS; Windows NT v.4.0, сессия DOS.

Результаты диссертационной работы в виде программного комплекса Free Styl eRoute используются для разводки печатных плат на предприятиях Санкт-Петербурга, Москвы, Одессы, Арзамаса и Рыбинска. Кроме того, комплексом пользуется большое количество частных лиц. Результаты диссертационной работы используются в учебном процессе СПбГУТ им. проф. М.А. Бонч-Бруевича, СПбГЭТУ (ЛЭТИ), СЗТУ и Одесского Политехнического Института. Комплекс доступен в сети INTERNET на сайтах: http://Steve.skv.net.ua, http : //akuiin. npi. m su. su. http : //hardwl . virtualave. net, ftp : //ftp .rdd.usart. ru/pub/ и др.

Основные положения диссертационной работы докладывались и обсуждались на зональной НТК "Автоматизация проектирования РЭА и ЭВА" (Пенза, 1990 г.); всесоюзной НТК "Совершенствование технических средств связи для решения проблем информатизации обш;ества в новых условиях хозяйствования" (Ленинград, 1991 г.); зональной НТК "Автоматизация проектирования РЭА и ЭВА" (Пенза, 1991 г.); зональной НТК "Автоматизация проектирования РЭА и ЭВА" (Пенза, 1992 г.); международной НТК "Современные технологии обучения" (С.Петербург, 1997 г.); международной НПК "Системы и средства передачи и обработки информации" (Одесса, 1997 г.); международной НТК "Современные технологии обучения" (С.-Петербург, 1998 г.); II международной НТК студентов, аспирантов и молодых специалистов стран СНГ "Техника и технология связи" (С.-Петербург, 2000 г.); 6-й международной НТК "Современные технологии обучения" (С.-Петербург, 2000 г.); международной НПК "Современные информационные и электронные технологии" (Одесса, 2000 г.); 4-й международной НПК конференции "Системы и средства передачи и обработки информации" (Одесса, 2000 г.); 2-й международной НПК "Современные информационные и электронные технологии" (Одесса, 2001 г.).

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

Диссертация состоит из введения, шести глав, заключения и списка литературы, включаюп];его 131 наименование. Основная часть работы изложена на 73 страницах машинописного текста, содержит 39 рисунков и 2 таблицы.

6.4. Выводы

1. Разработан программный комплекс трассировки печатных плат FreeStyleRoute (FSR), зарегистрированный в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) под номером 980492 от 14.08.1998 г.

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

3. Проведён сравнительный анализ результатов разводки, полученных с помощью трассировщиков FreeStyleRoute и Specctra (Cadence Design Systems, US A). Показано несомненное преимущество FreeStyleRoute.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Разработан и исследован способ перемещения компонентов на от-трассированной печатной плате с сохранением целостности цепей и

99 соблюдением заданных зазоров с целью уменьшения длины трасс и занимаемой плош;ади или с целью увеличения зазоров.

6. Разработан программный комплекс трассировки печатных плат FreeStyleRoute (Р8К), зарегистрированный в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) под номером 980492 от 14.08.1998 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18. Бурцев С.Г., Полубасов О.Б. Автоматизация формирования принципиальных схем. Материалы 6-й международной конференции "Современные технологии' обучения", С.-Петербург, 2000, т. 1, с. 290-291.

19. Бурцев С.Г., Полубасов О.Б. Задача автоматического формирования чертежа принципиальных схем. Труды международной НПК "Современные информационные и электронные технологии", Одесса, 2000, с. 63.

20. Бурцев С.Г., Полубасов О.Б. Алгоритм размещения при формировании чертежа принципиальной схемы. Материалы 4-й международной НПК "Системы и средства передачи и обработки информации" («ССПОИ»), Одесса, 2000, с. 63-64.

21. Бурцев С.Г., Полубасов О.Б. Задача размещения и трассировки БИС. Материалы 4-й международной НПК "Системы и средства передачи и обработки информации" («ССПОИ»), Одесса, 2000, с. 72-73.

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

23. Вичес С.А. Асимптотический оптимальный алгоритм перечисления пересечений ребер двудольного графа. Авт. и телемеханика, вып. 12. 1984, с.133-137.

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

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

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

27. Гндоян А.К, Об одном алгоритме покрытия внешних связей печатных ПЛАТ. Вопросы радиоэлектроники, сер. ЭВТ, 1979, Вып.9, С. 52-53.

28. Голов A.B., Лузин С.Ю., Полубасов О.Б. Алгоритм назначения внешних контактных площадок. Материалы международной НТК "Системы и средства передачи и обработки информации". - Одесса, 1998, с. 145.

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

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

31. Деньдобренко E.H., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. ~384с.

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

33. Ершов А. П. Введение в теоретическое программирование. М.: Наука. 1977. - 288с.

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

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

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

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

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

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

40. Карзанов А. В. Алгоритм максимальной упаковки нечетнополюсных разрезов и его приложения. Исследования по прикладной теории графов. - Новосибирск: Наука, 1986, с. 126-140.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

65. Полубасов О.Б., Алексеев A.A., Ежов Ф.С. Решение проблемы большого объёма данных в системах САПР. Материалы 4-й международной НПК "Системы и средства передачи и обработки информации", Одесса, 2000, с. 78-79.

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

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

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

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

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

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

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

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

74. Ренькас И.В., Полубасов О.Б. Синтез изображений принципиальных электрических схем. Доклады 2-й международной НТК студентов, аспирантов и молодых специалистов стран СНГ "Техника и технология связи", 1-3 февраля 2000 г., С.-Петербург, 2000, с. 337-338.

75. Ренькас И.В., Полубасов О.Б. Автоматическое создание изображения принципиальной электрической схемы. Материалы 6-й международной конференции "Современные технологии обучения", С.Петербург, 2000, Т. 1, с. 289-290.

76. Ренькас И.В., Полубасов О.Б. Автоматическое построение чертежа схемы. Труды международной НПК "Современные информационные и электронные технологии", Одесса, 2000, с. 58.

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

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

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

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

81. Сергиенко И.В., Рош;ин В.А. Один метод решения задачи о покрытии. -ДАН УССР , 1983, №9, сер.А, с.73-75.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

96. М. 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.

97. S. C. Chang, K. T. Cheng, N. S. Woo, M. Marek-Sadowska, Layout Driven Logic Synthesys, Proc. DAC. 1994, pp. 308-313.

98. J. Cong and B. Pleas: "A new algorithm for standard cell global routing." Proc. ofICCAD88. pp. 176-179 (1988).

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

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

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

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

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

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

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

106. 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).

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

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

109. M. JChellah. S. Brown, and Z. Vraneaic, "Modelling Routing Delays in SPlAM-based FPGAs," Canadian Conf on VLSI, 1993.

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

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

112. 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.

113. K. Mehlhom, 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.

114. M. Marek-Sadowska. New approach for channel routing.

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

116. R. Nair, C. L. Berman, P. S. Hauge, and E. J. Yoffa. "Generation of Performance Constraints for Layout". IEEE Transactions on Computer Aided Design, CAD-8(8):860-874, August 1989.

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

118. 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.

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

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

121. 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.

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

123. 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.

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

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

126. A. Srimvasan, et aL: "RITUAL: A performance driven placement algorithm for small cell ICs," Proc. ofICCAD9 1. pp. 48-51 (1991).

127. W. Swaitz and C Sechen: "A new generalized row-based global router," Proc. ofIC CAD93. pp. 491-498 (1993).

128. Szymanski T.G. Dogleg Channel Routing is NP-Complete. IEEE Trans. Computer-Aided Des., Vol. CAD-4, No.l, JANUARY 1985, p. 3141.

129. T. Yoshimura, E. S. Kuh, "Efficient algorithms for channel routing," IEEE Trans. Computer-Aided Design, vol. CAD-1, pp. 25-35, 1982.