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

• Кузьмин, Борис Алексеевич
• кандидат технических наук
• 1985

Оглавление диссертации кандидат технических наук Кузьмин, Борис Алексеевич

Введение.

Гл. I Проблемы автоматизации решения задач размещения и трассировки при проектировании РЭА.

Гл. 2 Алгоритм размещения с моделированием конфигурации межэлементных связей.

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

Гл. 4 Алгоритмы трассировки связей.

Гл. 5 Система автоматизированного конструирования печатных плат.

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

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

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

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

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

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

РЭА, ее решение с помощью алгоритмов, основанных на глобальном переборе вариантов, практически неосуществимо ни сейчас, ни в обозримом будущем. Объясняется такое положение слишком большой размерностью тех математических задач, к которым можно было бы свести многие конкретные задачи размещения и трассировки. До сих пор не удавалось получить удовлетворительного решения такой задами и другими методами. Единственный доступный в настоящее время подход к решению задачи состоит в разбиении единой задачи на две: размещения элементов и трассировки связей.

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

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

Следовательно, представляется актуальной задача нахожде

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

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

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

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

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

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

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

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

3. Разаработать алгоритмы реализации связей на дискретном рабочем поле с повышенным быстродействием и меньшими потребностями в оперативной памяти ЭВМ.

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

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

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

Система внедрена на ряде предприятий с годовым экономическим эффектом 80 тыс. руб.

Основные результаты работы докладывались и обсуждались на всесоюзных и зарубежных конференциях, в том числе: на II Всесоюзном совещании "Автоматизация проектирования и конструирования" (Ленинград, 1983), на Всесоюзном совещании-семинаре "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации САПР РЭА (Москва, 1981), на X Всесоюзном совещании-семинаре "Теория, методы и программные комплексы автоматизации проектирования современных ЭВМ и их элементов" (Крымская область, 1982), на У1 Международной конференции по исследованиям в промышленности (Нови-Сад, Югославия, 1981), на 29 Международном коллоквиуме Высшей технической школы в Ильме-нау (Ильменау, ГДР, 1984), на 1У Международном коллоквиуме "Интертехно-81" (Будапешт, ВНР, 1981).

По теме диссертации опубликовано 10 работ.

Диссертация состоит из введения, пяти глав, заключения и списка литературы.

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

Заключение

В диссертационной работе получены следующие результаты:

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Кузьмин, Борис Алексеевич, 1985 год

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

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

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

4. Бойко В.Н. .Герасименко Е.П. .Кот В.И. Волновой алгоритм размещения модулей произвольной формы. Управляющие системы и машины, 1977, № I, с. 120-123.

5. Quirm Sr, Breuer М. A Forced Directed Component Placement Procedure for FOB,- I SEE Trans, on Circuits and Systems, 1979» vol, CAS-26» So.6, p. 377-388.

6. The Dissection of Rectangles into Squares / P. Brooks, G. Smith» A. Stone» V, Tutte.- Duke Math. J. Suly, 1940,vol. 7» Ho.3> p. 312-340.

7. Qhtsuki T.» Sugiyama H. > Kawaniahi H. An Optimization Technique for Integrated Circuit Layout Design.- Proc. ICCST-Kyota, Sept., 1970, p. 67-68.

8. Steinberg L. The Back Board Wiring Problem: A Placement Algorithm.- SJAIi Rev., 1961, vol. 3» No, 1, p. 37-50.

9. Ueda К,, Koxpataubara I., Hoaaka T. JL Parallel Processing Approach for bogie Module Placement,- IEEE Trans, on Computer-Added Design, 1983» vol. САД-3» No,1, p. 39-47.

10. Melladi R. Serrего G., Verdillon 1. Automatic Placement of Rectangular Blocks with Interconnection Channels.-Proc. of the 18th DAG, 1981, p. 419-425.

11. Рычков Л.А. Кузьмин Б.А.Эйдео A.A. Алгоритм размещения элементов разной формы. Приборы и системы управления, 1979, № 2, с. 1-3.

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

13. Линский В.С. Алгоритмическое проектирование вычислительных устройств. М.: ВЦ АН СССР, 1963. - 134 с.

14. Г7. Stark P.A. Introduction to Numerical Methods.- Hew

15. Yorki Macmillan, 1970.- 6Ю p.

16. Scanlon g. Automated Placement of Multi-Terminal Components»- Proc. of the 8th DA Workshop, 197U p. 143-154*

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

18. Lauther U. A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph Representation.- Journal of Digital Systems, 1980, vol. 4э Ho. 1, p. 21-34.

19. Rutman R. An Algorithm for Placement of Interconnected Element Based on Minimum lire Length.- Proc. 1964 A3?IDS SJCC, p. 477-491.

20. Kubiak R., Ciesielski M. Placement Algorithm for

21. Automatic 1С Layout Design System.- Design Automation & Fault-Tolerant Computing, 1978, p. 249-267.

22. Jayakomar V» A Data Structure for Interactive Placement of Rectangular Objects.- Proc. of the 17th DAC, 1980,p.237-249.

23. Jfcmkres J* Algorithms for the Assignment and Transportation Problem®.- J. SIAM, 1957» vol. Ко. 1, p. 32-38*

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

25. Kernighan В., Lin S. An Efficient Procedure for Partitioning Graphs.- Bell Syst. Tech. J., 1970, Febr.» p. 291-307.

26. Hanan li., Wolff P., Agule B. Some Experimental Results on Placement Techniques.- Proc. of the 13th DAC, 1976, p.214-224

27. Garside R,, Nicholson. . Permutation Procedure for the Backboard Wiring Problem.- Proc. of IEB, 1968, Jan., p.27-39.

28. Cote I»., Pafcel A. The Interchange Algorithms for Circuit Placement Problems.- Proc. of the 17th DAC, 1980» p. 528-534.

29. Gilmore P. Optimal and Suboptimal Algorithms; for the Quadratic Assignment Problem«- J. Soc. Ind. Appl. Math., 1962, vol. 10, No. 2, p. 305-313.

30. Reiter S.f Sherman G. Discreet Optimising.- SIAM J., 1.965» vol. 13» Ho. 4» P. 864-889.

31. Goto S. A Two-Dimensional Placement Algorithm for the Master Slice LSI layout Problem.-Proc. of the 16Ш DAC, 1979» p.11-1'

32. Koopmans T., Beokman M. Assignment Problems and the Locations of Economic Activities.- Econometrica, 1967, vol. 25» Ho. U P. 53-79.

33. Akers S. On the Use of the Linear Assignment Algorithm in Module Placement.- Proc. of the 18th DAC, 1981, p.137-144.35, Kohn H. The Hungarian Method for the Assignment Problem. Kaval Res. Log. Quart, 1955, vol.12, Ho. 1, p. 83-97.

34. Barr R., Glover P.» KLingman D. The Alternating Path Algorithm for Assignment Problems.- Math. Prog., 1977, vol. 13, Но» 1, p. 1-13.37« Hung M., Rom f. Solving the Assignment Problem by Relaxation.- Operations Res., 1980, vol. 28, p. 969-982,

35. Carter H., Breuer M., Syed Z. Incremental Processing Applied to Steinberg's Placement Procedure.- Proc. of the 16th BAG, 1979. P. 26-31.39* Breuer И. Incremental Processing in Design Automation.-SIGDA Newsletter, 1976, vol.6, Но. 4э p. 3-9.

36. Рао-Tsin Wang. A Placement Technique Based on Minimization and Even Distribution of Crossovers«- SISDA Hewsletter,1980, vol. 10, p. 9-aO.0 <

37. Gupta H., Sharma J. A Two-Dimensional Placement Algorith for the Layout of Electronic Circuits.- Microelectronics & Reliability, 1980, vol.ZO, Ho. 3» p. 323-328.

38. Балтрушайтис P.И. Задача оценки размещения. Тезисы докладов республиканской конференции "Автоматизированное техническое проектирование электронной аппаратуры"« - Каунас: Каунасский политехнический институт, 1982, с.65.

39. PAS-LOPt An Automatic Module Location System for ШВ/ G. Odowara, K. Iijima» N. Ichihara, T. Kiyomatsu.-Proc. of the 16th DAG, 1981, p. 153-159.

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

41. Breuer M. A Glass of Min-Cut Placement Algorithms.

42. Proc. of the 14th SAC» 1977» p. 284-2:90.

43. Corrigan L. A Placement Capability Based on Partitioning.- Proc. of the 16th DAC» 1979» p. 406-413*49* Chandraeekhar M., Breuer M. Optimum Placement of Two Reotangular Blocks.- Proc. of the 19th DAC, 1982:, p. 879 886.

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

45. Ьее С. An Algorithm for Path Connections and Its Applications«- IRE Trans, on Electronic Computers, 1961» vol. EC-10» Ho. 3, p. 346-366»

46. Hong S., flair R.» Shapiro B. A Physical Design Machine.-VLSI ai, 1981, p. 401-416.55« Litaige D. Trace automatique de plaquettes de circuits imprimes.- Automatisme, 1973, vol.XVIII, N0. 1, p. 7-15.

47. Soukup J., Rovle J. On Hierarchical Routing.-Journal of Digital Systems, 1981, vol. 4, No, 3» p. 265-289.

48. Rubin g. The Lee Path Connection Algorithm.- IEEE Trans* on Computers» 19741» vol. G—2.3» Ho. 9» p. 907-914.

49. Hoel J. Some Variations of bee's Algorithm.- IEEE Trans, on Computers, 1976» vol. С-25» No. 1, p. 19-24.

50. Рябов Г.Г.Зиман Ю.Л. Волновой алгоритм и электрические соединения. М.: ИТМ и ВТ, 1965. - 130 с.

51. Вгаков Л.А. Алексеева Р.П.Автоматизация трассировки соединений на многослойных печатных платах. Приборы и системы управления, 1977, № 9, с. 7-9.

52. Korn An Efficient Variable-Cost Маге Router.- Proc. of the 19th ВАС» 1,982, p. 425-431.

53. Soukup J. Past Maze Router.- Proc. of the 15th DAC, 1978» p. 100-102.63» A gast Hase Router with Iterative Use of Variable Serch Space Restriction.- Proc. of the 17th DAC, 1980» p. 250-254.

54. Hadlock P. A Shortest Path Algorithm for Grid Graphs.-Networks, 1977» vol. 7, Ho. 4» p. 323-334.65* Heinisch J. Aiming at a General Routing Strategy.-Proc. of the 18th Dac, 1981, p. 668-675.

55. Hightower D. A Generalized Channel Router.- Proc. of the 17th DAC, 1980, p. 12-21.

56. Gupta U. » Lee D.y Leung J. An Optimal Solution for the Channel-Assignment Problem,- IEEE Trans, on Computers, 1979, vol. C-28, No. 11, p. 807-810.

57. Yoahimura T., Euh E. Efficient Algorithm for Channel Routing.- IEEE Trans, on CAD of Integr. Cire, and Systems, 1982, vol. CAD-1, Ho. 1, p. 25-35«

58. Peas 1.» Kar^er £. Automated. Rip-up and Reroute techniques. Proc. of the 19th. DAG, 1982, p. 432-439.

59. Wilson B., Smith R. An Analitic Technique for Router Comparison. Proc. of the 13th DAC, 1976-, p. 251-253.

60. Agraval Р.» Breuer M. A Probabilistic Model for the Analysis of the Routing Process for Circuits. Hetworks» 1930, vol. 10» »0.2.^11-128.

61. Rubin P. An Iterative technique for Printed lire Routing. Proa*of the 11th Design Automation Workshop, 1974»p.303«-31;73» Bollinger M. A Mature DA. System for PC Layout. Proc. International Printed Circuits Conference» 1979» p.85-89.

62. Marvili B.A. An Interactive Routing Program with on-line Clean-up of Sketched Routes» Proc. of the 16th ВАС» 1979»p. 500-505.

63. Kopotkob A.C. Модель печатной платы, учитывающая технологические требования. Обмен опытом в радиопромышленности, 1975, вып. 6, с. 125-127.

64. Кузьмин Б.А. Применение волнового алгоритма для решения задач трассировки большой размерности, В кн.: Автоматизация проектирования систем управления. М.: Финансы и статистика,1982 с,

65. Интегрированные САПР печатных штат. Тематическая подборка. Приборы и системы управления, 1979, Ш 1-3.

66. Зелковиц М. Шоу А. .Гэннон Дж. Принципы разработки программного обеспечения. М.: Мир, 1982. - 368 с.

67. Йодан Э. Структурное проектирование и конструирование программ. 1VL: Мир, 1979. - 296 с.80. gernigan В., Plau^er P. The Elements of Programming Style. McGraw-Hill, 1979» - 168 p.

68. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ, М.: Мир, 1981. - 320 с.

69. Ford В. The Evolving MG Approach, to Software Portability. Cambrige University Press, t977. - 177 p.

70. Lecture Botes in Computer Science.Ho.57. Portability of Numerical Software. Springer-Verlag, 1977. - 366 p.

71. Браун П. Макропроцессоры и мобильность программного обеспечения. М.: Мир, 1977. - 253 с.

72. Хуоаинов Б. С. Макросредства в языке Ассемблера ЕС ЭЕМ.-М.: Статистика, 1978. 94 с.

73. Ifcbeod J. ME/1 a FQRTRÄH Macr coprocessor. - Computer Journal» 1971» vol. 14» Ho. 3> P- 222-231.

74. Браун П. Обзор макропроцессоров. M.: Статистика, 1975. - 80 с.

75. Siwards 0.» Broadwell В. Data Processing. -ladaworth Publishing Company, 1980. 520 p.89. fflo M. Влияние идей абстракции на современные языки программирования. ТШЭР, 1980, т.68, № 9, с. 99-112.

76. Лебедев В.Н. Соколов А.П. Введение в систему программирования ОС ЕС. М.: Статистика, 1978. - 144 с.

77. Катцан Г. Язык Фортран-77. М.: Мир, 1982. - 208 с.

78. Грогоно П. Программирование на языке Паскаль. М.: Мир, 1982. - 384 с.

79. Kernigaa В., Ritchie D. Hie С Programming Language. -Prentice-Hall, 1978. 228 p.

80. Якубайтис Э.А. Архитекрута вычислительных сетей. М.: Статистика, 1980. - 279 с.95. *eil Ü. Information Systems in the 80«a. Prentice-Hall, 1982. - 383 P.

81. Курбатов А.В.Лазарев М.И. Программное управление распределением памяти в Фортране. Программирование, 1980, № 5 с. 87-89.

82. Бояршинова И.А.Корченко С.Н.Кузин С.Г. О реализации динамического распределения оперативной памяти в Фортране. -Программирование, 1979, № 2, с. 68-72.

83. Rader J. Ûinamic Allocation of Arrays in Fortran. -Proc. of the 11th Annu.Asilomar Conf., 1978» p» 295-298.

84. Sackman H. Computers» System Science and Evolving Society. John Wiley & Sons, 1967. - 638 p.

85. Irimberger S. Combining Graphics and a Layout Language i a Single Interactive System.-Proc*of the 18th. û&C»198t» p. 234.

86. Seppanen J. Pragmatic Problems of Man/Computer Dialogues. Helsinki University of Technology, 1979» - 22 p.

87. Фоли Дж. Уоллес В. Искусство организации естественного графического диалога человек-машина. ТИИЭР, 1974, т. IX, Л 4,106. billèhagen F», Rieaenfeld H. New Dimensions in Man-lachine Comminications. Computers in Industry, 1980, Ho. 1» P» 131.

88. Dehning »., Easlg H. » Haass S. The Adaptation of Virtual Man-Computer Interfaces to User Requirements in Dialogs.-Springer-Tferlag» 198t. 141 p.

89. Эйдес А.А. Автоматизированная система конструкторской и технологической подготовки производства радиоэлектронной аппаратуры. Препринт. М.: ИПУ, 1981. - 50 с.

90. Гилой В. Интерактивная машинная графика. М.: Мир, 1981. - 384 с.

91. HQ, Sahara К. »Kobori К* > Hisbioka X. Ал Interactive Layout System оf Analog Printed Wiring Boards. Eroc. of the 16th. DAG, 1979» p. 506-512*

92. IfcLeod J. Module Lets CAD System Respond to Designer's Voice. Electronic Design» 1980» vol„28,Mo,24» p.35-36.

93. Bebditch. D* Design of Dialogues for Interactive Commercial Applications. Man/Computer Gonmrun. Infortecb. State Art Sept., 1979» vol. 2» Я© 2, p. 171-192.

94. ИЗ. Ньюмен У.Спрулл P. Методика разработки программного обеспечения для систем машинной графики. ТИИЭР, 1974, т. IX, 16 4, с. 67-83.

95. Артамонов Е.И. Лебедев B.C.Варшавский А.Д.Система программ для проектирования и изготовления конструкторской документации. Препринт. М.: ИПУ, 1976. - 50 с.

96. Банковский Ю.М. Дяховишшй Б.А.Михайлова Т.Н. ГРАФОР: комплекс графических программ на ФОРТРАНе. Вып. 5. Структура и основные принципы. Препринт № 90. М.: ЙПМ АН СССР, 1975. - 72 с.

97. File Structure® and Data Bases for CAD. Horth-H oil and Publ* Co.* 1982. - 380 p.

98. Sidle T. Weaknesses of Commercial Data Base Management Systems in Engineering Applications.- Design Automation Conference» t980, pr 57-61.

99. S* Комплекс общеотраслевых руководящих методических материалов по созданию АСУ и САПР. М.: Статистика, 1980. - 119 с.

100. Брукс Ф.П. Как проектируются и создаются программные комплексы. М.: Наука, 1979. - 152 с.

101. Гантер Р. Методы управления проектированием программного обеспечения. М.: Мир, 1981. - 392 с.

102. Лебедев В.Н. Введение в системы программирования. -М.: Статистика, 1975. 311 с.

103. Кнут Д. Искусство программирования для ЭШ. М.: Мир, 1976-1978.

104. Трамбле Ж.,Сореноен П. Введение в структуры данных. -М.:Машиностроение, 1982. 784 с.

105. Gomputer-Alded Design Techniques» E* Wolfendale (edi, Butterworth, 1970.- 32.1 p.

106. Mettdows Д. Training in Use of a Computer Aided Circuit Board Design System.- Int. Conf. Comp. Aided Design Educ.» 1977» p. гэз-гоо.

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