Математическое обеспечение интеграции процессов оптимизации и редактирования топологии печатного монтажа в системе гибкой топологической трассировки тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Петросян, Геворг Самвелович

• Петросян, Геворг Самвелович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Петросян, Геворг Самвелович

ВВЕДЕНИЕ

I. СРАВНЕНИЕ ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКИ С ДРУГИМИ МЕТОДАМИ

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

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

1.3. Технология Shape-based

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

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

1.6. Выводы

II. МОДЕЛИ ПЕЧАТНОГО МОНТАЖА

2.1. Диаграммы «сущность - связь».

2.2. Топологическая модель печатного монтажа

2.3. Геометрическая модель печатного монтажа

2.4. Выводы.

III. СИНТЕЗ ГЕОМЕТРИЧЕСКОЙ МОДЕЛИ ПО ДАННЫМ ТОПОЛОГИЧЕСКОЙ И СИНТЕЗ ТОПОЛОГИЧЕСКОЙ МОДЕЛИ ПО ДАННЫМ ГЕОМЕТРИЧЕСКОЙ

3.1. Синтез геометрической модели печатного монтажа по данным топологической.

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

3.1.2. Прокладка ребра

3.1.3. Добавление в триангуляцию межслойных переходов

3.2. Синтез топологической модели печатного монтажа по данным геометрической.

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

3.2.2. Построение триангуляции рабочего поля

Введение диссертации (часть автореферата) на тему «Математическое обеспечение интеграции процессов оптимизации и редактирования топологии печатного монтажа в системе гибкой топологической трассировки»

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

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

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

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

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

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

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

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

2. Методика синтеза топологической модели печатного монтажа по данным геометрической модели.

3. Методика синтеза геометрической модели печатного монтажа по данным топологической модели.

4. Методика отбора вариантов при многокритериальной оптимизации разводки соединений.

По мнению автора, основная практическая ценность работы заключается в создании системы автоматизированного проектирования топологии печатного монтажа "TopoR", зарегистрированной в

Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) под номером 2005611893 от 29.07.2005 г.

Результаты диссертационной работы в виде программного комплекса "TopoR" используются для разводки печатных плат на предприятиях Санкт-Петербурга, Москвы, Одессы, Нижнего Новгорода, Тулы и Рязани. Кроме того, комплексом пользуется большое количество частных лиц. Результаты диссертационной работы используются в учебном процессе СПбГУТ им. проф. М.А. Бонч-Бруевича, СПбГЭТУ (ЛЭТИ), СПбГУАП и Одесского Политехнического Института. Комплекс доступен в сети INTERNET на сайте: www.freestyleteam.com.

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

- III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;

- VI международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2002 г.;

- 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;

- 4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.;

- VII международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2003 г.;

- Международной научно-технической конференции MTIH(CALS)

2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003 г.;

- Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.-Петербург, 2004 г.;

- 5-й международной НПК "Современные информационные и электронные технологии", Одесса, 2004 г.;

- III международном симпозиуме "Аэрокосмические приборные технологии", С.-Петербург, 2004 г.;

- Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;

- VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса,

2004 г.;

- 6-й международной НПК "Современные информационные и электронные технологии", Одесса, 2005 г.

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Петросян, Геворг Самвелович

5.4. Выводы

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

2. Отладочная система интегрирована в САПР "TopoR".

3. Проведён сравнительный анализ результатов разводки, полученных с помощью систем автоматизированного проектирования печатного монтажа ("TopoR", "PCAD", "Protel DXP", "SPECCTRA", "Power PCB"). Показано несомненное преимущество системы "TopoR".

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

ГЛОССАРИЙ

Крест - пересечение проводника с ребром триангуляции (крест WA) или с другим проводником (крест WW). Триангуляция — разбиение плоскости на треугольные грани. Триангуляция Делоне — разбиение плоскости на такие треугольные грани, что окружность, описанная вокруг любой грани не содержит внутри себя вершин других граней.

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

Список литературы диссертационного исследования кандидат технических наук Петросян, Геворг Самвелович, 2005 год

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. Некоторые задачи синтеза планарных топологий. В кн.: Вычислительная техника. Вильнюс, 1979, Т. 12, с. 16-23.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28. Жилинскас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности. // М.: Наука. 1989. - 128 С.

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

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

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

32. Картер Б. Техника разводки печатных плат. Часть 1. // Chip News. 2004. - №7. - С.63-70.

33. Картер Б. Техника разводки печатных плат. Часть 2. // Chip News.-2004.- №10.- С.46-51.

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

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

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

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

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

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

40. Медведев А. Печатные платы. Конструкции и материалы. М.: Техносфера. - 2005. - 302 С.

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

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

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

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

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

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

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

48. Петросян Г.С. и др. Система автоматизированного проектирования FreeStyle 2.0. // Труды второй международной научно-практической конференции "Современные информационные и электронные технологии". — Одесса. — 2001. -С.210.

49. Петросян Г.С. и др. Интегрированная система автоматизированного проектирования "FreeStyle EDA" // Труды V международной научно-практической конференции "Системыи средства передачи и обработки информации". Одесса. - 2001. -С.105-106.

50. Петросян Г.С., Зудин С.В. Интегрированная САПР печатных плат. // 8-я международная научно-техническая конференция студентов и аспирантов "Радиоэлектроника, электротехника и энергетика". Тезисы докладов. Т.1. - Москва. -2002. - С.76-77.

51. Петросян Г.С. и др. Учебная САПР тонкопленочных микросборок. // Материалы 9-й международной конференции "Современные технологии обучения". С.-Петербург. - 2003. -Т. 1.-С. 196-197.

52. Петросян Г.С., Полубасов О.Б. Интеграция процессов оптимизации и редактирования топологии. // Труды 4-й международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса.-2003.-С.208.

53. Петросян Г.С., Соколов В.Е., Лузин С.Ю. Декомпозиция задачи выделения в графе наибольшего полного подграфа. // Труды 4-й международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса.-2003.-С.212.

54. Петросян Г.С. и др. TopoR система автоматизированной трассировки печатных плат. // Труды VII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2003. - С. 137.

55. Петросян Г.С. и др. Система топологической трассировки печатных плат. // Труды международной научно-технической конференции ИПИ(САЬ8)-2003 "Информационные технологии в управлении жизненным циклом изделий". С.-Петербург. — 2003.-С.38.

56. Петросян Г.С. и др. Автоматизация синтеза топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. -С.166.

57. Петросян Г.С., Дюдин М.В., Полубасов О.Б. Использование функциональной эквивалентности на этапе пробной трассировки. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. -С.164.

58. Петросян Г.С. и др. Преимущества неортогональной топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". -Одесса.-2004.-С. 167.

59. Петросян Г.С. и др. Обеспечение электромагнитной совместимости на этапе размещения компонентов. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. — С. 163.

60. Петросян Г.С. и др. Система автоматизации синтеза топологии печатного монтажа. // Труды Всероссийской научно-практической конференции "Информационные технологии в российской промышленности". С.-Петербург. - 2004. - С.91-92.

61. Петросян Г.С. Воротынцев В.Ю., Лузин М.С., К оценке качества топологии печатного монтажа. // Труды III международногосимпозиума "Аэрокосмические приборные технологии". С.Петербург. - 2004. - С. 175.

62. Петросян Г.С. Воротынцев В.Ю., Лузин М.С., Пути повышении плотности печатного монтажа. // Труды Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения". Сочи. - 2004. - С. 29-30.

63. Петросян Г.С. и др. Обеспечение заданного качества топологии печатного монтажа. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". Одесса. - 2004. - С. 119-120.

64. Петросян Г.С. и др. Способ повышения плотности печатного монтажа. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". Одесса. - 2004. - С. 123-124.

65. Петросян Г.С. и др. Контроль констуктивно-технологических нарушений в системе TopoR. // Труды 6-й международной НПК "Современные информационные и электронные технологии". -Одесса. 2005.-С.212.

66. Петросян Г.С., Полубасов О.Б. Многовариантная оптимизация разводки соединений. // Труды 6-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2005. - С.211.

67. Петросян Г.С. и др. Система топологической трассировки печатного монтажа "TopoR" // Свидетельство об официальной регистрации программы для ЭВМ № 2005611893. М. Российское агентство по патентам и товарным знакам (РОСПАТЕНТ).-2005.

68. Петросян Г.С., Полубасов О.Б. Методика отбора вариантов при оптимизации разводки соединений // Технологии приборостроения. 2005. - №3 С. 16-19

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

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

71. Полу басов О.Б. Алгоритмы локальной оптимизации расслоения на этапе макротрассировки. // Технологии приборостроения. — 2004.-№3(11).-С. 23-36.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

86. Хигстон Д., Логхид Ф., Ирвин Р. Новый топологический автотрассировщик. — www.altium.com,www.electrade.ru.

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

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

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

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

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

92. F.F. Dragan, A.B. Kahng, I. Mondoiu, S. Muddu, A. Zelikovsky "Provably Good Global Buffering Using an Aviable Buffer Block Plan", Proc. of ICC AD 2001, pp. 104-109.

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

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

95. Hongbing Fan, Jiping Liu, Yu-Liang Wu "General Models for Optimum Arbitrary-Dimention FPGA Switch Box Designs", Proc. 1С CAD 2001, pp.93-98.

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

97. Toshiyuki Hama and Hiroaki Etoh "Single-layer automatic router" http://www.trl.ibm.com/proiects/optsim/opt/SLR/index e.htm

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

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

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

101. Jiang Hu, Sachin S. Sapatnekar "A Timing-constrained Algorithm for Simultaneous Global Routing of Multiple Nets", Proc. of ICC AD 2001, pp.99-103.

102. R.Kastner, E. Bozorgzadeh, M. Sarafzadeh "Predictable Routing", Proc. of ICC AD 2001, pp. 110-114.

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

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

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

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

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

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

109. A. Srimvasan, et aL: "RITUAL: A performance driven placement algorithm for small cell ICs," Proc. of ICCAD91. pp. 4851 (1991).

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