Анализ и разработка методов автоматизированного размещения компонентов электронных схем тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Зудин, Станислав Владимирович

• Зудин, Станислав Владимирович
• кандидат технических наук
• 2004

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

ВВЕДЕНИЕ.

I. КРИТЕРИИ КАЧЕСТВА МОНТАЖНО-КОММУТАЦИОННОГО ПРОЕКТИРОВАНИЯ РЭС

1.1. Размещение для получения минимальной длины соединений

1.2. Размещение для получения равномерного заполнения монтажного пространства

1.3. Частные оценки размещения

1.4. Формирование эффективного критерия качества размещения.

Выводы

II. ОПТИМИЗАЦИЯ МОДЕЛИ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ

2.1. Минимизация числа ребер графа модели схемы

2.2. Построение модели схемы на основе линейного размещения независимых цепей

2.3. Построение модели схемы на основе решения задачи о кратчайшем покрытии. ф Выводы

III. РАСЧЕТ ЭЛЕКТРОМАГНИТНЫХ ПОМЕХ

В ПЕЧАТНЫХ ПЛАТАХ.

3.1. Допущения, принятые при расчете электромагнитных помех

3.2. Одиночные линии

3.3. Связанные линии линии

3.5. Удельные электрические параметры линий передачи на печатных платах

3.6. Формулы расчета

3.7. Метод расчета сигналов и помех

3.8. Использование подсхем и компактного хранения параметров

3.9. Редукция многополюсников, представленных

Y - параметрами

3.10. Редукция эквивалентных схем путем преобразований «звезда - многоугольник». щ Выводы

IV. СОВМЕСТНОЕ РЕШЕНИЕ ЗАДАЧ РАЗМЕЩЕНИЯ

И ТРАССИРОВКИ

4.1. Создание условий для качественной детальной трассировки

4.2. Начальное размещение

4.3. Выбор конфигурации цепей

4.4. Разбиение областей

4.5. Назначение ячеек на области и установка размеров новых областей. ф 4.6. Предварительная трассировка

Выводы

V. РАЗРАБОТКА И ЭКСПЛУАТАЦИЯ ПРОГРАММНОЙ ПОДСИСТЕМЫ РАЗМЕЩЕНИЯ

5.1. Входные - выходные данные.

5.2. Структура данных.

5.2.1. Сущности.

5.2.2. Конструктив и схема соединений. ф 5.2.3. Принадлежность ячеек областям.

5.2.4. Графы горизонтального и вертикального разбиений.

5.2.5. Лес цепей.

5.2.6. Граф смежности областей для макротрассировки.

5.3. Пользовательский интерфейс.

5.4. Экспериментальная оценка качества машинного размещения.

5.4.1. Сравнительные результаты расчета электромагнитных помех.

5.4.2. Сравнение результатов автоматического размещения компонентов в программах

Бресс^а и АиТОР

Выводы.

Введение диссертации (часть автореферата) на тему «Анализ и разработка методов автоматизированного размещения компонентов электронных схем»

Техническое проектирования является важнейшим этапом разработки радиоэлектронных средств (РЭС) различного назначения.

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

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

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

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

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

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

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

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

Заметный вклад в исследование проблемы эффективности автоматизированных методов МКП внесли Л.Б.Абрайтис, Р.П., Базилевич, A.M. Бершадский, В.М. Глушков, Б.Н. Деньдобренко, В.М. Курейчик, С.А. Майоров, Н.Я. Матюхин, А.Н. Мелихов, К.К. Морозов, А.И. Петренко, Г.Г. Рябов, В.А. Селютин, А.Я. Тетельбаум, Г.Р. Фридман, М.Е. Штейн, Г.Э. Широ и многие другие.

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

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

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

- анализ применяемых моделей объектов и критериев МКП узлов РЭС на печатных платах, микросборках и СБИС; формирование эффективной оценки качества размещения ЭРЭ в монтажном пространстве;

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

- разработка методики расчета электромагнитных помех в устройствах с печатным монтажом;

- разработка эффективного метода размещения компонентов с учетом ф оценочного уровня электромагнитных помех и загруженности монтажного пространства;

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

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

- в выявлении закономерностей, определяющих влияние параметров (Ф модели электрической схемы, используемой для решения задачи размещения компонентов, на плотность и равномерность заполнения монтажного пространства;

- в разработке моделей электрических схем, адекватных требованиям топологического синтеза РЭС;

- в разработке эффективного алгоритма размещения компонентов электронных схем в плоском коммутационном пространстве.

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

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

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

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

- Н-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г. (2 доклада);

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

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

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

- 8-й международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика", Москва, 2002г.;

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

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

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

- Научно-технических конференциях профессорско-преподавательского состава СПбГУТ им. проф. М.А.Бонч-Бруевича, г. Санкт-Петербург, 1998г., 1999г.

По теме диссертации опубликовано 20 работ. Получено авторское свидетельство на программное средство, зарегистрированное в Государственном фонде.

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

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

Выводы

АиТОР.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. Показана необходимость использования методов редукции схем для уменьшения размерности задачи.

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

Список литературы диссертационного исследования кандидат технических наук Зудин, Станислав Владимирович, 2004 год

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. Балтрушайтис Р.И. Задача и оценки размещения. В сб.: Вычислительная техника. Каунас, КПИ, 1982, с.65-66.

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

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

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

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

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

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

19. Варшавский А.Д. Универсальный алгоритм размещения связных объектов в двухмерном пространстве. Экспресс-информация, ТС-9, Экономика и технология приборостроения, М.: 1979. Вып.5. - 16с.

20. Васильев 1 O.A., Глаголев В.В. Метрические свойства дизъюнктивных нормальных форм. В ст.: Дискретная матем. и матем. вопр.кибернетики, М. Наука, 1974, с.99-148.

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

22. Гаевенко А.Ю. Критерий качества и алгоритм размещения элементов РЭА. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, 1J1., 1983, с.251-252.

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

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

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

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

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

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

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

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

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

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

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

34. Казеннов Г. Г., Сердобинцев Е. В. Автоматизация проектирования БИС. Кн. 6. Проектирование топологии матричных БИС. Под ред. Г. Г. Казеннова. М.: Высш. шк., 1990. - 112 с.

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

36. Карапетян М.А. Система алгоритмов многокритериальной оптимизации при размещения элементов регулярных структур. В сб.: Автоматизация проектирования электронной аппаратуры. Межведомственный тематический сборник. - Таганрог.: ТРТИ. 1984. Вып.З. С.115-119.

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

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

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

40. Кузьмин Б.А., Эйдес A.A. О критериях качества размещения. Управляющие системы и машины, №13, 1982, с.53-55.

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

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

43. Лузин С.Ю., Полубасов О.Б. Топологическая трассировка: реальность или миф? // EDA Expert. 5(68). - 2002. - С. 42-46.

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

45. Мелихов Л.П., Берштейн Л.С. к др. Применение гиперграфов для компоновки схем ячейки. Изв. АН СССР, Техн. кибернетика, 1971, № 3, с.202-207.

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

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

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

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

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

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

52. Островский В.М. К исследованию свойств кратчайших покрытий. В сб.: Синтез дискретных автоматов и управляющих устройств.

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

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

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

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

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

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

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

60. Рощин В.А., Сергиенко И.В. Об одном подходе к решению задачи о покрытии. Кибернетика, 1984, № 6. с.65-69.

61. Рузаев E.H., Канунов А.И., Муравьев C.B. Алгоритмы нахождения минимального покрытия булевой матрицы. Изв. ВУЗов, Радиоэлектроника, 1981, № 8. с.92-94.

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

63. Сачков В.Е. Введение в комбинаторные методы дискретной математики. М.: Наука, 1983. - 384с.

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

65. М.: Советское радио, 1977, 384с.

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

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

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

69. Соловьев H.A. Тесты (Теория, построение, применение). Новосибирск.: Наука. 1978.- 189с.

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

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

72. Тетельбаум Л.Я. Последовательно-параллельный алгоритм размещения электронных компонентов. Управление системы и машины. 1977, №5. с.118-122.

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

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

75. Толстун А.И., Мельничук И .Г., Горощенко А.Г. Программа направленной компоновки модулей. УСиМ. 1985, № 2, с. 29-33.

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

77. Фридман А., Менон П. Теория и проектирование переключательныхсхем. М.: Мир, 1978. - 580с.

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

79. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем. Труды матем. ин-та АН СССР, 1958, т.51. с.270-330.

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

81. Aurenhammer F. On-line sorting of twisted sequences in linear time. BIT28(1978), 194-204.

82. Brown A. D. Automated Placement and Routing. Computer-Aided Design, vol. 20, no. 1, pp. 39-44, January 1988.

83. E. S. David et al, "Meshach: Matrix Computations in C". Proceedings of the Center/or Mathematics and its Applications. Australian National University, vol. 32,1994.

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

85. Phiroze N. Parakh, Richard B. Brown, Karem A. Sakallah, "Congestion Driven Quadratic Placement", 35th DAC, 1998, pp.275-278.

86. P. R. Suaris et. al, "A quadrisection-based combined place and route scheme for standard cells". 1989. IEEE TCADICS, vol.8, no.3, pp. 234244.

87. S. Yousef, "Iterative methods for sparse linear systems". PWS Publishing Company.