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

• Львов, Николай Павлович
• кандидат технических наук
• 1984

Оглавление диссертации кандидат технических наук Львов, Николай Павлович

Введение

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

1.1. Основные проблемы и методы синтеза топологии интегральных микросхем.

1.2. Структура процесса топологического проектирования ИМС.

1.3. Входной язык системы топологического проектирования

1.4. Архитектура программной системы топологического проектирования ИМС.

Выводы.

2. Математические модели и алгоритмы топологического этапа проектирования.

2.1. Задача построения топологических моделей ИМС

2.2. Коммутационные поверхности.

2.3. Алгебраические модели элементов ИМС.

2.4. Анализ шанарности графов.

2.5. Вложение потенциального графа в коммутационную поверхность.

2.6. Алгоритм синтеза шгоского модифицированного потенциального графа

Выводы.

3. Алгоритмические методы синтеза эскизов топологии

3.1. Анализ методов метризации.

3.2. Метод поэтапной метризации.

3.3. Построение нерегулярных целочисленных решеток

3.4. Генерация и коррекция изображений плоских графов ИМС.

3.5. Оценки эскизов топологии ИМС.

3.6. Алгоритм внутренней трассировки.

3.7. Алгоритм размещения доменов.

3.8. Построение соединений ИМС

Выводы.

4. Организация информационного и программного обеспечения.

4.1. Информационное обеспечение СТП.

4.2. Организация вычислительного процесса в СТП.

4.3. Транслятор входного языка.

4.4. Программные компоненты СШ.

4.5. Экспериментальное исследование СТП.

Выводы.

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

Рис.1.3. Нерегулярная целочисленная решетка. - 15 мости шло.Дяя матричных Ш С характерна фиксированная площадь базового кристалла и заранее заданное число и местоположение элементных ячеек. Все соединения должны быть реализованы в каналах с ограниченной пропускной способностью. Проектирование топологии таких ИМС связано с решением комбинаторных задач большой размерности, вследствие чего при разработке алгоритмов синтеза топологии следует уделять особое внимание снижению их временной сложности.В настоящее время в практике автоматизированного проектирования топологии ИМС ШЕфОко используется так называемый классический подход, особенностью которого является последовательное выполнение этапов размещения элементов и трассировки соединений. В целом ряде работ был дан анализ цричин нецригодности классического подхода для решения задач синтеза топологии ИМС с одним слоем коммутации /59,70,7,94,102/. Результатом этого анализа является вывод о несогласованности топологического критерия минимума числа пересечений, реализуемого на этапе трассировки, и метрических критериев (минимум площади кристалла, суммарной длины соединений, длины сигнальных связей) этапа размещения.Специфика подхода и методов синтеза топологии оказывают определяющее влияние на технологию автоматизированного проектирования, и, тем самыьл, на трудоемкость всего цроцесса проектирования и качество результатов проектирования. Ни один из алгоритмов трассировки не гарантирует стопроцентную реализацию соединений при фиксированном размещении элементов, даже если возможно использование нескольких коммутационных слоев. Для ИМС большой степени интеграции число неразведенных соединений может быть весьма значит ельныгл. Учитывая высокую плотность ком- 16 поновки эскиза топологии и большое число геометрических фрагментов эскиза, можно утверждать, что цроцесс коррекции эскиза топологии, необходимый для реализации непроведенных соединений, является крайне сложным и длительным /70,76/. Кроме того, коррекция эскиза топологии в интерактивном режиме ведет к появлению ошибок в топологии ЙМС, выявление которых также увеличивает длительность и трудоемкость цроцесса проектирования.Задача автоматической коррекции (создание топологического редактора) в общем случае еще не решена /68/.Конструктивные особенности матричных БИС, такие, как наличие каналов фиксированной емкости для прокладки соединений, делают еще более тесной связь между этапами размещения и трассировки. В случае невозможности трассировки процедура размещения может неоднократно повторяться с новыми начальными условиями. Алгоритмы размещения элементов имеют достаточно высокую временную сложность (порядка П , где П - число элементов), поэтому процесс получения удовлетворительного размещения, для которого возможна реализация соединений, связан с большими затратами машинного времени.Перечисленные проблемы не могут быть адекватно решены в рамках классического подхода, поэтому необходимо искать принципиально иные пути их решения.Альтернативным классическому является так называемый топологический или теоретико-графовый подход к автоматизированному цроектированию топологии. В рамках теоретико-графового подхода были получены интересные результаты, имеющие как теоретическое, так и практическое значение. В работах /8,59,69, 70,105/ наиболее подробно изложена сущность теоретико-графового подхода и пути его практической реализации.Основные положения теоретико-графового подхода заключают- 17 ся в ел едущем. Исходной принципиальной электрической или функциональной схеме сопоставляется топологическая модель - граф, при построении которого учитываются некоторые конструктивные особенности ШЛО. К таким особенностям относятся заданный порядок соединения проводников с контактами элемента , наличие внешних контактных площацок и эквипотенциальных контактов (то есть связанных проводниками внутри элемента). Далее строится плоское представление графа, задаваемое множеством граней. Если граф не может быть уложен на плоскости без пересечения ребер, то удаляется некоторое минимальное подмножество ребер (так называемые неплоские ребра) и выделяется максимальная планарная часть графа. На следующем этапе (этапе планаризации) неплоские ребра добавляются в построенный плоский граф с учетом возможностей ликвидации пересечений, предоставляемые технологией. Результатом планаризации является плоский модифици-) рованный граф, для которого должно быть построено изображение на плоскости. Процесс сопоставления вершинам и ребрам модифицированного графа точек и линий на плоскости называется метризацией, а изображенный на плоскости граф - метризованным. Метризованный граф преобразуется в реальное изображение конструкции микросхемы, представляющее собой чертеж элементов и межсоединений.При традиционной реализации теоретико-графового подхода этап построения плоской укладки графа и этап планаризации выполняются последовательно. Этим нарушается одно из основных преимуществ теоретико-графового подхода, состоящее в возможности параллельного решения задач размещения и трассировки, поскольку этапы укладки графа на плоскости и планаризации при традиционном теоретико-графовом подходе соответствуют этапам размещения и трассировки. - 18 При вложении графа в плоскость происходит построение множества граней, образущих топологическое рабочее поле. Тем самым осуществляется размещение вершин плоского графа в гранях. Общие свойства задач планаризации - трассировки отмечались в работах /8,105,108/, причем для решения задачи планаризации предлагались аналоги волнового и лучевого алгоритмов трассировки /76,77/. Отметим, что на этапе построения плоской укладки ни один из известных алгоритмов вложения графов в плоскость не создает условий для последущего проведения неплоских ребер по граням, поэтому использование указанных методов планаризации влечет за собой появление большого числа дополнительных вершин, разбивающих ребра плоской укладки. Таким образом, при достаточно большом числе неплоских ребер традиционный теоретико-графовый подход плохо учитывает критерий минимума числа пересечений. Этот подход, кроме того, неприменим к проектированию топологии ИМС с несколькими слоями коммутации и, также как и классический, жестко реализует последовательность цроектных операций.Разработка адекватного подхода к решению задач автоматизированного синтеза топологии ИМС должна производиться на основе анализа целей, объектов и процессов цроектирования.1.2. Структура процесса топологического проектирования ИМС Топология ИМС характеризуется целым рядом параметров, значения которых должны лежать в определенных пределах, зависящих от технологических ограничений и заданных рабочих характеристик ИМС. К таким параметрам относятся, нацример, число пересечений проводников одного слоя, число межслойных переходов, число коммутационных слоев, площадь подложки, длина соединений, требуемая равномерность тепловыделения и паразитные - 19 электромагнитные взаимодействия в схеме. Заметим, что граничные значения электрофизических параметров могут быть вьфажены в геометрических терминах как минимальные допустимые расстояния между определенными элементами и проводниками. Некоторые из указанных параметров могут быть использованы при оптимизации в процессе топологического проектирования, другие же выступать в качестве ограничений. Так, например, задача проектирования топологии М С может быть связана с минимизацией площади подложки и числа пересечений проводников, как в случае биполярных полупроводниковых ИС, размещением всех элементов на подложке заданного размера при условии планарной реализации для однослойных тонкопленочных ми1фосборок, получением топологии в минимальном числе коммутационных слоев при ограничениях на длину сигнальных проводников - для толстопленочных микросборок, размещением элементов в заданных позициях при условии ограниченной емкости каналов для реализации соединений - для матричных БИС. Параметры топологии ИМС тесно связаны друг с другом, вследствие чего коррекция решения, направленная на улучшение характеристики ИМС по какому-либо из параметров, может цривести к ухудшению других характеристик проектируемой ИМС. Эта взаимосвязь обуславливает многокритериальный характер оптимизации при синтезе топологии, а ее характер в значительной степени зависит от используемых методов проектирования. Так, при классическом подходе к синтезу топологии число пересечений (переходов во второй слой) определяется на этапе трассировки и зависит от предварительного размещения. При теоретико-графовом подходе число пересечений определяется на этапе вложения графа и не меняется при любом размещении на этапе метризации. Вследствие значительных вычислительных трудностей, возникающих при - 20 решении задач многокритериальной оптимизации, целесообразно разделить решение таких задач на этапы, характеризующиеся независимыми критериями оптимальности. При теоретико-графовом подходе к синтезу топологии ИМС такими этапами являются топологический этап, связанный с оптимизацией по критериям минимума числа пересечений, числа межслоиных переходов и ограничениями на взаимное расположение некоторых компонентов в ИМС, и метрический этап, минимизируемыми параметрами на котором являются площадь подложки, длина соединений и число точек перегиба проводников.Разбиение на этапы определяет структуру цроцесса синтеза топологии игле. Кажцый этап характеризуется классом промежуточных цредставлений проектируемого объекта (частичных решений).Кроме требования независимости критериев оптимальности, к процессу автоматизированного проектирования предъявляются следующие общесистемные требования: на каждом из этапов процесса должна сохраняться целостность проектируемого объекта, а частичные решения должны быть абстрактными цредставлениями проектируемого объекта; промежуточные цредставления должны допускать возможность генерации частичных решений на основе некоторого начального и внесения локальных изменений с целью оптимизации, допускающих эффективную алгоритмическую реализацию.Первое требование обусловлено невозможностью достижения оптимальных характеристик для объекта в целом, если оптимизация производится изолированно при синтезе каждой из его частей.Причина этого обусловлена зависимостью взаимного расположения компонентов ИМС. Второе требование связано с принципиальной множественностью допустимых решений, оптимальных по тем или иным пара- 21 метрам. Выбор определенного частичного решения является результатом компромисса, что цредлагает анализ различных решений одного класса. Синтез различных решений путем повторения циклов проектирования при вариациях параметров исходного объекта является весьма трудоемким и малоэффективным. Именно поэтому механизмы быстрого порождения частичных решений одного уровня являются необходимыми элементами системы автоматизированного проектирования.Отметим, что ни классический, ни традиционный теоретикографовый подходы в достаточной степени не удовлетворяют указанным требованиям. Действительно, размещение и трассировка являются процессами синтеза различных частей ИМС, поэтому удовлетворительные решения при классическом подходе могут быть получены только при очень слабых ограничениях на топологию ИМС. В традиционном теоретико-графовом подходе имеет место аналогичная ситуация. На этапе вложения графа строится часть промежуточного объекта - плоский подграф. Каждый шаг метризации также носит локальный характер - построение топологии осуществляется на основе небольшого фрагмента плоского графа, без учета остальной его части. Генерация решений при классическом подходе возможна только на этапе размещения путем использования метода парных перестановок, и только для случая одногабаритных элементов.Возможности генерации частичных решений при теоретикографовом подходе значительно шире, чем при классическом. Так, на основе единственной плоской уЕсладки графа могут быть получены все остальные, различающиеся принадлежностью вершин к различным граням. Плоскому графу может быть сопоставлено множество различных ориентации его дуг. Указанные различия отразятся на уровне эскизов топологии как различия во взаимном по- 22 ложении элементов и проводников Ш С . Эти возможности, однако, не были в достаточной степени цриняты во внимание в существующих реализациях теоретико-графового подхода. Можно лишь отметить ряд алгоритмов генерации размещений разногабаритных элементов при синтезе топологии ЙМС с одним слоем коммутации, основанных на построении различных специальных ориентации плоского графа /109,122/.Таким образом, потенциальные возможности теоретико-графового подхода для синтеза топологии ИМС могут быть реализованы только цри условии разработки эффективных методов вложения графа ИМС в плоскость параллельно с планаризацией, генерации частичных решений на уровне плоских графов, снабженных дополнительными структурами для решения задачи метризации, и непосредственного перехода от метризованного графа к эскизу топологии ИМС. в настоящее время наиболее перспективной признана концепция иерархического цроектирования, на основе которой создается новое поколение С Ж Р /56,68,80,90,92/. Согласно этой концепции, синтез должен осуществляться как путем пошаговой отработки исходного задания для его реализации через промежуточные представления, так и путем детализации и получения различных вариантов решения на каждом из промежуточных уровней представления проекта. Можно утверадать, что концепция иерархического проектирования применительно к синтезу топологии ШЮ может быть наиболее последовательно реализована при использовании теоретико-графового подхода.Рассмотрим следующие уровни детализации проектных решений: потенциальный граф (кенигово представление гиперграфа), однозначно задающий связи между элементами и цепями исходной - 23 схемы (рис. 1.2); шгоский модифицЕфОванный граф (МГ), однозначно оцределяющий топологические характеристики ШЛО: число перемычек, ликвидирующих пересечения соединений, число межслойных переходов, а также их расположение с точностью до непрерывных деформаций плоскости; нерегулярная целочисленная решетка (ЩР), изображающая МГ, и представлящая собой влножество точек плоскости с целочисленными координатами, которые соответствуют элементам и цроводникам ИМС (рис. 1.3); размещение элементарных составляющих эскиза топологии (доменов) на параллельных уровнях; эскиз топологии ИМС (рис. 1.4).К числу наиболее важных особенностей указанных представлений относятся: возможность интерцретации МГ в виде топологии, выполненной в одном и более коммутационных слоях; реализация топологических критериев (критериев минимизации числа пересечений и числа межслойных переходов) на этапе построения МГ; возможность генерации различных Щ Р ; возможность автоматического редактирования топологии путем преобразований Щ Р и параллельных сдвигов доменов.

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Львов, Николай Павлович, 1984 год

1. Абрайтис Л.Б., Елонскис И.С. Машинный метод цроектирования топологического рисунка БИС. - Управляющие системы и машины, 1980, № 4, с.79-84.

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

3. Абрайтис Л.Б., Шимайтис А.П. Разбиение произвольных графов, отображенных в прямоугольную решетку, на плоские суграфы.-В кн.: Вычислительная техника, Каунас, 1976, с.102-105.

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

5. Александрии Р.А., Мирзаханян Э.А. Общая топология. М.: Высшая школа, 1979, 336 с.

6. Атре Ш. Структурный подход к организации баз данных. М.: Финансы и статистика, 1983, 317 с.

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

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

9. Барила А.К. 0 некоторых требованиях к системе автоматизированного проектирования топологии БИС. В кн.: Вычислительная техника, Каунас, 1982, с.36-37.

10. Барила А.К., Елонскис И.С. Развитие метода автоматизированного проектирования топологии БИС. Межвузовский тематический сборник научных трудов, Вильнюс, 1981, т.1, с.73-78.

11. Барила А.К., Елонскис И.С., Раудуве А.И. Алгоритм решения задачи сжатия топологического рисунка БИС. В кн.: Вычислит ольная техника. Материалы Всесоюзной конференции, Вильнюс, 1979, с.129-133.

12. Бежанова М.М. Входные языки пакетов прикладных программ. -Новосибирск, ВЦ СО АН СССР, 1979, прецринт 168, 30 с.

13. Бежанова М.М. Спецификация модели проблемно-ориентированной системы. Новосибирск, ВЦ СО АН СССР, 1982, црецринт № 361, 28 с.

14. Берж В. Методы рекурсивного программирования. М.: Машиностроение, 1983, 248 с.

15. Березин Ш.Т. Алгоритм построения плоского чертежа двухсвязного планарного графа. В кн.: Вычислительная техника, Каунас, 1981, с.99-100.

16. Берштейн Л.С. Применение гиперграфов для расслоения схем.-В кн.: Вычислительная техника, Каунас, 1976, с.106-108.

17. Берштейн Л.С. Определение возможности плоской реализации схемы с помощью гиперграфов. В кн.: Автоматизация проектирования средств автоматики и вычислительной техники, Изд. СГУ, Саратов, 1976, с.32-34.

18. Бесшапов В.П., Песков М.И. Подход к проектированию архитектуры САПР. В кн.: Вычислительная техника, Каунас, 1982, с.6.

19. Бойко В.В., Савинков В.М. Проектирование информационной базы автоматизированной системы на основе СУБД. М.: Финансы и статистика, 1982, 174 с.

20. Боланд Дж.Ч. Вложение графов в ориентируемые поверхности.-Киб. сборник, вып.7, М.: Мир, 1970, с.118-132.

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

22. Гайфуллин Э.Ш., Климов В.Е., Старостина Л.А. Метод автоматизированного проектирования топологии гибридных интегральных схем. В кн.: Вычислительная техника, Каунас, 1981, с.103-104.

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

24. Гридин В.Н. Язык автоматизации технического проектирования МЭА. В кн.: Вычислительная техника, Каунас, 198I, с.71-72.

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

26. Грисс М., Лантен А. Теория формальных грамматик. М.: Мир, 294 с.

27. Дамбит Я.Я., Матисоне Э.К. Алгоритм автоматизированного построения плоского чертежа графа. В кн.: Вычислительная техника, Каунас, 1978, т.10, с.8-9.

28. Демьяхин В.А., Арустамов С.А. Алгоритм размещения компонентов цифровых систем, использующий плоскую укладку пла-нарного графа. Матер, сем. "Микроэлектроника в вычислительной технике", Л., 1974, с.83-84.

29. Деньдобренко Б.Н., Арбузов В.А. Алгоритм автоматического синтеза топологии гибридных полупроводниковых интегральных схем. В кн.: Вычислительная техника, Каунас, 1978, т.10, с.129-132.

30. Деньдобренко Б.Н., Львов Ы.П., Вольберг А.Л. Конструктивное доказательство теоремы Холла и его использование в задаче размещения элементов микросхем. В кн.: Вычислительная техника, Каунас, 1982, с.61-62.

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

32. Деркач В.П., Сосницкий А.В., Миросенко Д.А. Принципы построения и реализации универсального банка данных для автоматизированного конструирования РЭА. В кн.: Вычислительная техника, Каунас, 1981, с.78-79.

33. Зепс Д.А. Испытание алгоритма нахождения плоской части графа. В кн.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике, Вильнюс, 1982, т.2, с.24-29.

34. Зепс Д.А. Пакет программ для обработки графов: планар-ность и укладка графа. В сб.: Методы и программы решения оптимизационных задач на графах и сетях. Часть: Тезисы докладов П Всесоюзного совещания, Новосибирск, 1982, с.75-78.

35. Истмэн Ч.М. Средства баз данных для инженерного проектирования. ТИИЭР, 1981, т.69, №10, с.79-100.

36. Казеннов Г.Г. Структура, основные требования и принципы построения систем автоматизированного проектирования микроэлектронных приборов. М.: Машиностроение, 1978, 64 с.

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

38. Кдыгина Л.А. Планаризация укладки графовых моделей принципиальных электрических схем. Деп. в ВИНИТИ, № 5364-80, 20 с.

39. Кяыгина Л.А. Графическое представление эскиза топологии биполярных ИМС. В кн.: Вычислительная техника, Каунас, 1982, с.40-41.

40. Кяыгина Л.А., Павлов Н.Н. Подсистема синтеза топологии. Язык описания принципиальных электрических схем. Деп. в ЦНИИ Электроника, й 6265/79, 1979, 14 с.

41. Кузин Л.Т. Основы кибернетики. М.: Энергия, 1979, т.2, 327 с.

42. Лисаускас Л.М. Начальное размещение топологических образований БИС. В кн.: Вычислительная техника, Каунас, 1979, с.44-47.

43. Львов Н.П. Топологические модели для задачи планарной реализации интегральных схем. В кн.: Вычислительная техника, Каунас, 1981, с.102.

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

45. Львов Н.П. Метризация плоского представления графа интегральной схемы. Известия ЛЭТИ. Науч. тр. /Ленингр. элек-тротехн. ин-т им.В.И.Ульянова (Ленина), вып.277, 1980,с.29-33.

46. Львов Н.П. Реализация основных этапов автоматизированногосинтеза топологии РЭА с помощью методов теории графов. -Известия ЛЭТИ. Науч. тр. /Ленингр. электротехн. ин-т им.В.И.Ульянова (Ленина), вып.294, 1981, с.11-19.

47. Маклейн С. Комбинаторное условие для плоских графов. -Киб. сборник, М.: Мир, 1970, вып.7, с.133-144.

48. Мазур С.Г. Использование графов для минимизации числа меж-слойных переходов. В сб.: Методы и программы решения оптимизационных задач на графах и сетях. Часть I: Тезисы докладов П Всесоюзного совещания, Новосибирск, 1982, с.120-123.

49. Матулюкштис Л.И. Эскизная трассировка топологии ШС. В кн.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике, Вильнюс, 1982, т.2, с.35-45.

50. Маурер У. Введение в программирование на языке ЛИСП. М.: Мир, 1976, 104 с.

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

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

53. Ниссен К. Методология и средства иерархического проектирования СБИС. ТИИЭР, 1983, т.71, № 3, с.81-94.

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

55. Ньютон А.Р. Автоматизация проектирования сверхбольших интегральных схем. ТИИЭР, 1981, т.69, № 10, с.7-19.

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

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

58. Пратусевич М.Л., Селютин В.А. Построение плоских реализаций схем с учетом конструктивных ограничений. Микроэлектроника, 1980, т.9, вып.З, с.203-208.

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

60. Рохлин В.А., Фукс Б.Д. Начальный курс топологии. М.: Наука, 1977, 488 с.

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

62. Ряйза О.В. Транслятор^данных САПРа. В кн.: Вычислительная техника, Каунас, 1981, с.69-70.

63. Секен К.Х. Управление сложностью СБИС. Современное состояние и перспективы. ТИИЭР, 1983, т.71, № I, с.184-211.

64. Селютин В.А. Автоматизированное проектирование топологии БИС. М.: Радио и связь, 1983, 112 с.

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

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

67. Селютин В.А. Топологические модели для задач проектирования коммутационных схем. Электронная техника. Сер. 6. Микроэлектроника, 1969, вып.6, с.66-72.

68. Селютин В.А., Львов Н.П., Першурич А.А., Сердюк Т.В. Реализация теоретико-графового подхода к автоматизированному синтезу топологии интегральных микросхем. В кн.: Вычислительная техника, Каунас, 1976, с.22-25.

69. Селютин В.А., Гуревич Д.З., Куклане А.Н., Львов Н.П. Комплексная автоматизированная система конструирования топологии электронных схем МАРАТ. В сб.: Авт. проект, и произв. электронно-вычисл. аппарат., Л.: Изд. ЛДНТП, 1978, с.20-30.

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

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

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

73. Фролов Г.Д., Олюкин В.Ю. Практический курс црограммирова-ния на языке PL -I. М.: Наука, 1983, 384 с.

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

75. Шива С.Г. Автоматизированный синтез аппаратных средств. -ТШЭР, 1983, т.71, lb 3, с.95-110.

76. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969, 316 с.- 185

77. Щубарев В.А., Маркаров Ю.К. Система автоматизированного проектирования микросборок на базе ЕС ЭВМ. В сб.: Автоматизация проектирования и производства электронно-вычислительной аппаратуры, Л.: Изд. ДЩГГП, 1978, с. 12-20.

78. Юрин О.Н. Единая система автоматизации проектирования ЭВМ. М.: Сов. радио, 1976, 176 с.

79. Allen J., Penfield P. VLSI Design Automation Activities at M.I.T. IEEE Trans, on Circ. and Syst., 1981, v.CAS-28, N7, p.645-653.

80. Auslander L., Parter S.V.,Siewiorek D.P., Thomas D.E.On imbedding graphs in the plane. J.Math, and Mech.,1961,mo, p.517-523.

81. Baubock E. Ein Verfahren zur Abbildung eines planar en Gra-phen mit ziklisch geordneten Nachbarshften in der Ebene.Angewandte Informatic, 1978, N1, p.9-14.

82. Brincmann E.-D. Qas Chip-Netz ein Hilfsmittel fur den Layout von MSI und LSI-Schaltungen. - Microwellentechnik, ntz Bd.30, 1977, Heft 12, p.929-935.

83. Brooks R.L., Smith C.A.B. The dissection of rectangles into sqares. Duke J. of Math., 1940, N7, p.312-340.

84. Bruno J., Steiglitz K., Weinberg L. A new planarity test based on 3-connectivity. IEEE Trans, on Circ. Theory, 1970, v.CT-17, N2, p.197-206.

85. Director S.W., Parker A.C., Siewiorec D.P., Thomas D.E.A Design Methodology and Computer Aids for VLSI Systems. -IEEE Trans, on Circ. and Syst., 1981, v.CAS-28, N7,p.634-635.

86. Dunlop A.E. SLIP: Symbolic layouj of integrated circuits with compaction. Computer Aided Design, 1978, v.10, N6, p.387-392.

87. Dutton R.W. Stanford Overview in Research, IEEEвTrans, on Circ. and Syst., 1981, v.CAS-28, N, p.654-665.

88. Fisher C.J. f Wing 0. Computer recognition and extraction of a plane graphs from incedence matrix. IEEE Trans, on Circ. Theory, 1966, N6, p.154-165.

89. Goldstein A. J. An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In: Proc. of Graph and combinatorics Conf., Princeton V., May 16-18, 1965, P.2.

90. Goldstein A.J., Schweicert D.G. A proper model for testing the planarity of electrical circuits. Bell Syst. Tech. J., 1975, N1, v.52, p.125-142.

91. Hopcroft J., Tarjan R. Efficient Algorithms for Graph Manipulation H . Common, of ACM, 1975» v.16, N6, p.572-578.

92. Hopcraft J., Tarjan R. An efficient planarity testing. -J. of ACM, 1974» v.21, N4, p.549-568.

93. Hopcraft J., Tarjan R. Planarity testing in VlogV steps: Extended abstract. In&: Proc. Conf. Ljubljana, Aug. v1971, p.18-22.

94. Hope A.K. A planar graph drowing program. Software practice and experience, 1971, v.1, p.85-91.

95. Kojjima Т., Tanagi M., Uehara T. Compute re-aided design of hibrid 1С mask. Fajutsu Sci. and Techn. J., 1974, N2,P.75-95.

96. Kubiak R., Ciesielski M. Placement Algorithm for Automatic 1С Layout Design System. J. of Design Automation and Fault-tolerant computing, 1978, v. 2, N3, p.249-267.

97. Lempel A., Even A., Cederbaum I. An algorithm for plana-rity testing of graphs. Ins Theory of Graphs, Int. Symp., Rome, p.215-232.

98. Van Lier M.C., Otten R. Automatic 1С Layout: The model and technology. IEEE Trans., 1975» v.CAS-22, N11,p.845-855.

99. Van Lier M.C., Otten R. Automatic 1С Layout: some planarization algorithms» In: Proc. IEEE Int. Symp. Circ. and Syst•, Munich, 1976, p.662-665.

100. Maly W. An Algorithm for Obtaining the Planar Drawing of Planar Graph. In: IEEE Int. Symp. on Circ. and Syst. Proc., New York, May 1978, N.-Y., 1978, p.83-87.

101. Marek-Sadowska M. Planarization algorithm for integrated circuits engineering. In: IEEE Int. Symp. on Circ. and Syst. Proc., New York, May 1978, N.-Y., 1978, p.910-923.

102. Mlynski von D.A. Das Problem des Topologischen Schalt-ungsentwurfs. Feinwerktechnik, 1971, N10, p.297-402.

103. Newton A.R., Pederson D.O., Sangiovanni-Vincentelli A.L., Sequin C.H. Design Aids for VLSI: The Berkley Perspective. IEEE Trans on Circ. and Syst.,1981, v.CAS-28,N7, p.666-680.

104. Nichlson T.A.J. Permutation procedure for minimizing the number of crossing in a network, Proc. IEEE, 1968, v.115, N1, p.21-26.

105. Otten R., van Mijk J.G. Graph presentation in interactive layout design. In: Proc. of IEEE Int. Symp. on Circ. and Syst., New York, May 1978, N.-Y,, 1978, p.914-918.

106. Rabin P. An improved algorithm for testing the planarity of a graph. IEEE Trans, on Comput,, v.C-24, N2, 1975» p.113-121.

107. Thomson K. The UNIX programming system, Bell Syst. Techn. J., 1980, v.57, N6, Part 2, p.1931-1969.

108. Trimberger S., Rouson J.A., Lang C.R., Gray G.P. A Strac-tured Design Methology and Associated Software Tools. IEEE Trans, on Circ. and Syst., 1981, v.CAS-28, N7» p.618-634.

109. Vancleemput W.M. Mathematical models for the circuit layout problem. IEEE Trans., 1976, v.CAS-23, Я^2, p.759-767.

110. Vancleemput W.M. An algorithm for testing the planarity of partially oriented graphs. Ins IEEE Proc. Int. Symp. on Circ. and Syst., 1977, p.813-817»

111. Uehara Т., Shiraishi H., Takahashi 0., Kojima T. Embedding a graph in a plane with local constraints. Ins Proc. IEEE Int. Symp. on Circ. and Syst., San Francisco, 1974, p.181-185.

112. Uehara Т., van Cleemput W.M. Optimal layout of CMOS functional arrays.- IEEE Trans, on Computers, 1981, v.30,N5, P.305-312.

113. Uehara Т., Takahashi 0., Shiraishi H. Problem of automatic circuit drawing for mask making system. Pujutsu Sci. and Techn. J., 1972, v.8, N3, p.35-58.

114. Wilmore J.A, The use of bit maps in designing efficient data bases for integrated circuits layout systems, J, of Dig. Syst., 1980, v.IV, N1, p.71-595.

115. Zibert K.f Saal R. On computer aided hybrid circuit layout, In: Proc. IEEE Int. Symp.on Circ.and Syst,, San Francisco, May 197^, 1974, p.314-318.