Содержание к диссертации
Введение
1. Принципы построения и лингвистическое обеспечение системы топологического проектирования 12
1.1. Основные проблемы и методы синтеза топологии интегральных микросхем 12
1.2. Структура процесса топологического проектирования ИМС 18
1.3. Входной язык системы топологического проектирования 26
1.4. Архитектура программной системы топологического проектирования ЙМС . 33
Выводы 36
2. Математические модели и алгоритмы топологического этапа проектирования 38
2.1. Задача построения топологических моделей ИМС . 38
2.2. Коммутационные поверхности 44
2.3. Алгебраические модели элементов ИМС . 53
2.4. Анализ планарности графов 56
2.5. Вложение потенциального графа в
коммутационную поверхность 68
2.6. Алгоритм синтеза плоского модифицированного потенциального графа 92
Выводы 97
3. Алгоритмические методы синтеза эскизов топологии . 98
3.1. Анализ методов метризации 98
3.2. Метод поэтапной метризации 101
3.3. Построение нерегулярных целочисленных решеток . 105
3.4. Генерация и коррекция изображений плоских графов ИМС 108
3.5. Оценки эскизов топологии ИМС 118
3.6. Алгоритм внутренней трассировки 123
3.7. Алгоритм размещения доменов 127
3.8. Построение соединений ИМС 131
Выводы 135
4. Организация информационного и программного обеспечения 136
4.1. Информационное обеспечение СТП 136
4.2. Организация вычислительного процесса в СТП 142
4.3. Транслятор входного языка 154
4.4. Программные компоненты СТП 164
4.5. Экспериментальное исследование СТП 169
Выводы 172
Заключение 174
.Литература
- Основные проблемы и методы синтеза топологии интегральных микросхем
- Задача построения топологических моделей ИМС
- Анализ методов метризации
- Информационное обеспечение СТП
Введение к работе
Научно-технический прогресс в области создания новых типов электронной аппаратуры в значительной степени зависит от успешного решения проблемы автоматизации проектно-конструктор-ских работ. Наиболее сложной задачей в процессе конструкторского проектирования является задача синтеза топологии основных компонентов электронной аппаратуры - интегральных микросхем (ИМС).
Эффективное решение данной задачи возможно только при создании автоматизированных систем конструкторского проектирования (АСКП), позволяющих наиболее полно реализовать процесс проектирования на основе комплексного учета различных конструкторских критериев и ограничений. Исследования, направленные на создание АСКП, развиваются по двум направлениям. Первое направление связано с разработкой общесистемных принципов организации АСКП, созданием лингвистического и информационного обеспечения. Второе направление ориентируется на развитие математических методов, разработку алгоритмов и создание программного обеспечения, предназначенного для решения задач проблемной области.
Современные АСКП предназначены для синтеза топологии ИМС как на компонентном, так и на ячеечном уровне. К наиболее известным отечественным системам относятся такие АСКП, как Кау-нас-2, РАПИРА 5.3, АСП-І2, СИМПАС, МАРАТ, АСДГИС, описание которых можно найти в работах /1,9,18,38,55,66,70,74,82,83/. Среди зарубежных АСКП, известных в настоящее время, можно отметить такие, как SLIP, SHARPS, ALFA, VOILA,MILD, COMPAQ , обзор которых приводится в работах /4,56,58,91,92, 110,115,123/.
Широкое использование АСКП наталкивается на значительные трудности, возникающие при проектировании топологии ИМС различных классов. Методы синтеза топологии ИМС, реализованные в существувдих АСКП, не позволяют удовлетворительно решать задачу проектирования ИМС с одним основным коммутационным слоем (биполярных и гибридно-пленочных ИМС). Основной проблемой при проектировании является, в данном случае, получение шганарной реализации схемы при условии минимизации числа специальных перемычек, устраняющих пересечения. Разногабаритность элементов и нерегулярность соединений еще более усложняют задачу автоматизации проектирования топологии таких схем /76,80,90/.
Другой класс проблем связан с проектированием топологии больших интегральных схем (ШС), разрабатываемых по методу базового кристалла (матричных ШС). Наибольшие трудности при этом возникают из-за необходимости реализации всех соединений при жестких ограничениях на площадь кристалла и пропускную способность каналов, предназначенных для прокладки соединений, для получения топологии матричной ШС может потребоваться повторение циклов проектирования, а также доработка машинного решения в интерактивном режиме, что является весьма трудоемким процессом и связано с возможностью внесения ошибок в топологию схемы /68,69,76,115/.
Методы синтеза топологии ИМС, реализованные в промышлен-но используемых АСКП, составляют так называемый классический подход /2,33,55,70/, связанный с выполнением двух этапов синтеза топологии: размещения элементов и трассировки соединений. Последовательный характер решения задач размещения и трассировки, присущий классическому подходу, является основным препятствием на пути к удовлетворительному решению проблем проектирования топологии ИМС с одним слоем коммутации и матрич ных БИС.
Альтернативным классическому является теоретико-графовый подход, впервые предложенный для решения задач синтеза топологии ИГЛС с одним слоем коммутации /7,8,54,59,70/. Особенностью этого подхода является наличие двух основных этапов проектирования: топологического, на котором осуществляется построение плоского графа ИМС, и метрического, связанного с преобразованием плоского графа в эскиз топологии ИМС. Параллельность решения задач размещения и трассировки, свойственная теоретико-графовому подходу, делает целесообразным его выбор в качестве методологической основы для создания системы топологического проектирования (СТП) ИМС рассмотренных классов. Несмотря на значительное число работ, посвященных разработке и развитию теоретико-графового подхода, основные проблемы этого научного направления еще далеки от своего окончательного решения. К наиболее важным из них относится проблема создания адекватных топологических моделей ИМС и их конструктивного использования в алгоритмах синтеза плоских графов ИМС, построения эскиза топологии по плоскому графу, и обобщения теоретико-графового подхода на случай проектирования топологии ИМС на нескольких коммутационных слоях.
Принципиальные возможности для решения указанных проблем состоят в использовании методов топологии двумерных многообразий /15,20,63/ при построении моделей топологического этапа и разработки специальных преобразований плоских графов, изменяющих их порядковую и метрическую структуры. Эффективность применения новых алгоритмических методов синтеза топологии ИМС в значительной степени зависит от структуры процесса автоматизированного проектирования. При разработке такой структуры должны учитываться современные концепции иерархического проектирования /80,92,110/.
Только на основе решения перечисленных задач теоретико-графовый подход может быть использован в практике проектирования топологии ИМС.
Таким образом, актуальной является задача дальнейшего развития и реализации теоретико-графового подхода. При этом должны быть разработаны новые математические методы синтеза топологии, а также система топологического проектирования, в основу которой положен теоретико-графовый подход.
Целью диссертационной работы является разработка и исследование математических методов синтеза топологии ШС, а также разработка программного, лингвистического и информационного обеспечения системы топологического проектирования и ее реализация на ЕС ЭВМ.
Для достижения этой цели необходимо решить следующие ос-новные задачи:
1. Разработать нетрадиционную схему теоретико-графового подхода к синтезу топологии ИМС различных классов, в том числе для микросборок, биполярных интегральных схем, матричных ШС.
2. Разработать адекватные математические модели ЩС для решения задач синтеза топологии ИМС, учитывающие конструктивные особенности элементов ИМС.
3. Разработать алгоритмические методы синтеза плоских графов ИМС и построения на их основе эскизов топологии ИМС в одном и двух коммутационных слоях при условии минимизации числа введенных перемычек ж, соответственно, числа межслойных переходов.
4. Разработать и исследовать алгоритмические методы генерации различных конструкторских решений (эскизов топологии)
и автоматического редактирования топологии.
5. На основе принципов гибкого автоматизированного проектирования разработать архитектуру системы топологического проектирования, ориентированную на диалоговый режим работы; исследовать вопросы построения информационного обеспечения такой системы.
6. Разработать лингвистическое обеспечение СТЇЇ, включающее язык описания объектов проектирования и язык директив пользователя-конструктора, а также транслятор с входного языка.
7. Осуществить программную реализацию разработанных алгоритмов на НС ЭВМ.
При решении указанных задач использован аппарат теории графов, топологии, лямбда-исчисления, методы символьной обработки алгебраических выражении, теории формальных языков и структурного программирования.
К новым научным результатам относятся:
1. Предложены новые математические модели топологического и метрического этапов проектирования топологии ИМС (коммутационные поверхности и нерегулярные целочисленные решетки), адекватно учитывающие реальные проектные ситуации, такие, как наличие в ИМС ячеек со сложными отношениями инвариантности и эквипотенциальности на множестве контактов, разногабаритность элементов, жесткие ограничения на число пересечений (межслой-ных переходов); предложенные модели являются универсальными и могут быть использованы в различных алгоритмах синтеза топологии.
2. Впервые предложен алгоритмический метод синтеза плоских графов ИМС, осуществлякщий построение плоской укладки графа МО на основе решения задачи вложения гиперграфа исход - 9 -ной принципиальной схемы в многосвязную коммутационную поверхность; предложенный метод позволяет минимизировать число перемычек при построении плоской укладки ИМС или число межслой-ных переходов при построении топологии ШС в двух коммутационных слоях.
3. Предложен ж реализован новый метод решения задачи построения эскизов топологии на основе плоского графа ШС, позволяющий производить плотное размещение элементов и построение всех соединений в одном или двух коммутационных слоях, в зависимости от заданной интерпретации плоского графа ИМС за время, линейно зависящее от размерности задачи. Особенностью метода является использование промежуточного представления топологии ШС - нерегулярной целочисленной решетки.
4. Впервые предложены алгоритмические методы генерации и автоматической коррекции эскизов топологии, позволяющие с минимальными вычислительными затратами осуществлять случайный и направленный поиск оптимальных конструкторских решений.
5. Впервые применительно к системам топологического проектирования предложена архитектура программной системы, а также организация информационного и программного обеспечения, ориентированные на реализацию технологии гибкого автоматизированного проектирования на основе нетрадиционной схемы теоретико-графового подхода.
Практическая ценность работы состоит в создании СТП "Граф-І", реализованной на ЕС ЭВМ и предназначенной для проектирования эскизов топологии ИМС широкого класса.
Разработанная СТП позволяет синтезировать эскизы топологии ИМС в автоматическом и интерактивном режимах, осуществлять автоматическое редактирование топологии, а также обеспечивает генерацию и оценку различных вариантов топологии. Использова -ние СТЇЇ "Граф-І" в качестве подсистемы АСКП обеспечивает улучшение качества разработки ИМС и сокращение сроков проектирования.
Теоретические и практические результаты диссертационной работы использованы в четырех научно-исследовательских работах, проводимых в НПО "Позитрон" и на кафедре микрорадиоэлек-троники и технологии радиоаппаратуры ЛЭТИ им.В.И.Ульянова (Ленина) в 1975 - 1983 годах.
Результаты диссертационной работы внедрены в инженерную практику и используются на промышленных предприятиях городов Ленинграда, Риги и Ярославля с общим экономическим эффектом : 816 тыс. рублей, а также в учебном процессе для студентов специальностей 0705 и 0608 ЛЭТЙ им.В.И. Ульянова (Ленина) и слушателей отраслевого института повышения квалификации.
Основное содержание диссертации изложено на 140 страницах машинописного текста и иллюстрируется 53 рисунками.
Во введении отражена актуальность темы, дан краткий обзор состояния вопроса, сформулированы основные положения диссертационной работы, методы исследований и структура работы.
В первой главе излагаются принципы, на основе которых должна строиться СТП, проводится анализ критериев оптимальности, используемых в процессе проектирования топологии ИМС, рассматривается архитектура и лингвистическое обеспечение СТП "Граф-І", обсуждаются вопросы, связанные с технологией автоматизированного проектирования.
Вторая глава посвящена разработке математических моделей и алгоритмов топологического этапа проектирования, положенных в основу предлагаемой реализации теоретико-графового подхода. Рассматриваются математические модели - коммутационные поверхности и функции, описывающие топологические свойства элементов ШО. Предлагается алгоритмический метод построения плоской укладки графа, при котором планаризация производится в процессе вложения графа. В разработанном методе учитываются топологические особенности моделей элементов ИМС.
Третья глава посвящена разработке алгоритмов метризации плоских графов и построения эскизов топологии ИМС. Доказываются теоремы о свойствах специальных ориентации плоских графов. Вводится понятие нерегулярной целочисленной решетки, представляющей результат метризации плоского графа и предлагается алгоритм генерации и коррекции таких решеток. Предлагаются алгоритмы синтеза эскизов топологии по критериям максимально плотного размещения элементов и минимального числа точек перегиба.
В четвертой главе рассматриваются вопросы построения информационного обеспечения и программного обеспечения СТП Траф-1П, особенности построения транслятора входного языка, организация вычислительного процесса в СТП и результаты экспериментального исследования работы системы.
В заключении отмечаются основные результаты, полученные автором. Обсуддаются вопросы дальнейшего развития разработанной СТП "Граф-1".
В приложении дается детальное описание процедуры нормализации, используемой в алгоритме синтеза плоских графов ИМС, приводятся результаты экспериментального исследования работы СТП "Граф-I" и сведения о внедрении результатов диссертационной работы.
Основные проблемы и методы синтеза топологии интегральных микросхем
Интегральные микросхемы различных типов являются плоскими конструкциями, что позволяет рассматривать задачу синтеза их топологии с единой ПОЗИЦИЙ. Топология ИМС представляется в виде множества послойных двумерных изображений, компонентами которых являются ортогональные фигуры, составляющие микрогеометрии элементов, и соединяющие их проводники. Компоненты каждого слоя, соответствующие различным микрогеометриям и проводникам, не должны пересекаться. Б дальнейшем будут рассматриваться ИМС, топология которых удовлетворяет следукщим дополнительным ограничениям: 1. Изображения элементов представляются в виде прямоугольников с контактными площадками, расположенными по периметру. 2. сйементы расположены в одном слое. 3. Проводники параллельны сторонам подложки.
При замене прямоугольников, соответствующих проводникам, осевыми линиями, а контактных площадок - точками, получим рисунок ИМС, называемый эскизом топологии. Фрагмент топологии ИМС и соответствующий эскиз изображены на рис. І.І.
Проектирование топологии ИМС заключается в решении двух основных задач. Первая задача связана с построением эскиза топологии, а вторая состоит в покрытии точек и осевых линий эскиза прямоугольниками, размеры которых определяются спецификациями точечных контактных площадок, геометрией эскиза и технологическими нормами на ширину проводников /4,65,66,78/.
Наиболее сложные проблемы возникают при построении эскиза топологии, заключавдемся в определении взаимного расположения элементов и их соединений. Решение этой задачи связано с реализацией комбинаторных процессов поиска и перебора, тогда как задача покрытия эскиза топологии хорошо формализуема ж решается однозначно. Проблема автоматизации синтеза топологии особенно остро споит для ИМС с одним слоем коммутации и матричных БИС /69/.
В однослойных ИМС разводка проводников может быть выполнена без пересечений с помощью таких технологических приемов, как переходы в дополнительный коммутационный слой (биполярные ИС с проводниками в слое диффузии), введение различного рода перемычек (тонкопленочные микросборки) и специальных элементов, предназначенных для ликвидации пересечений и перекоммутации входных сигналов. Наиболее важным критерием, используемым при проектировании топологии таких ЙМС, является критерий ми-нимизации средств ликвидации пересечении, называемый также критерием минимума числа пересечений /59,69,70/. Невыполнение данного критерия ведет к снижению надежности, технологичности, ухудшению электрофизических характеристик и увеличению стой мости ИМС.
Для матричных ЕИС характерна фиксированная площадь базового кристалла и заранее заданное число и местоположение элементных ячеек. Все соединения должны быть реализованы в каналах с ограниченной пропускной способностью. Проектирование топологии таких ИМС связано с решением комбинаторных задач большой размерности, вследствие чего при разработке алгоритмов синтеза топологии следует уделять особое внимание снижению их временной сложности.
Б настоящее время в практике автоматизированного проектирования топологии ИМС широко используется так называемый классический подход, особенностью которого является последовательное выполнение этапов размещения элементов и трассировки соединений. В целом ряде работ был дан анализ причин непригодности классического подхода для решения задач синтеза топологии ИМС с одним слоем коммутации /59,70,7,94,102/. Результатом этого анализа является вывод о несогласованности топологического критерия минимума числа пересечении, реализуемого на этапе трассировки, и метрических критериев (минимум площади кристалла, суммарной длины соединений, длины сигнальных связей) этапа размещения.
Специфика подхода и методов синтеза топологии оказывают определяющее влияние на технологию автоматизированного проектирования, и, тем самым, на трудоемкость всего процесса проектирования и качество результатов проектирования. Ни один из алгоритмов трассировки не гарантирует стопроцентную реализацию соединении при фиксированном размещении элементов, даже если возможно использование нескольких коммутационных слоев. Для ИМС большой степени интеграции число неразведенных соединений может быть весьма значительным.
Задача построения топологических моделей ИМС
Вопрос построения адекватных топологических моделей ИМС является ключевым для реализации топологического подхода, о чем свидетельствует целый ряд работ /8,40,45,59,60,61,69,72, 105,117,118,120/, посвященных данному вопросу. Эти модели должны отражать следующие конструктивно-технологические особенности ИМС: ограничения на порядок соединения проводников с контактными площадками; возможность проведения ограниченного числа проводников через область элемента, наличие эквипотенциальных контактов.
Последнюю группу особенностей будем называть планаризаци-онными особенностями (ПО). Традиционные топологические модели не обеспечивают в полной мере учет особенностей каждой группы, что в значительной степени сокращает область применимости теоретико-графового подхода. Отсутствие адекватной топологической модели является основной причиной того, что эффективный с вычислительной точки зрения теоретико-графовый подход практически не применяется в существующих системах автоматизированного проектирования. Создание адекватных топологических моделей и соответствующих им алгоритмов топологического этапа синтеза, позволяющих учесть реальные конструктивно-технологические особенности ИМС, является наиболее методологически важным этапом при разработке системы топологического проектирования.
Для того, чтобы выяснить специфику топологических моделей, построим граф, взяв за основу некоторый эскиз топологии. Елемента ИМС на эскизе представим в виде прямоугольников с точечными контактными площадками, расположенными по периметру элемента, а соединения .- осевыми линиями. На рис. 2.1а изображен эскиз топологии. Стянем все прямоугольники в точку, считая внешние контактные площадки контактами некоторого фиктивного элемента S (рис. 2.16). Удалим точки, соответствующие элементам, вместе с их малыми окрестностями - открытыми дис-ками 33 . При этом вся конфигурация разбивается на множество непересекающихся деревьев, каждое из которых соответствует некоторой цепи схемы. Вершины деревьев, принадлежащие границе удаленных дисков, назовем терминальными. Гомотопическая деформация, связанная на терминальных вершинах, переводит эти деревья в звезды /5/.
Возвращая удаленные диски на свои места, получим плоский граф & (рис. 2.1в). Граф 0- является кениговым представлением гиперграфа, вершины которого соответствуют элементам ИМС, а ребра - цепям. В соответствии с терминологией, введенной в работе /105/, граф (г ямяется потенджальнш графом. Определим некоторые понятия, характеризующие плоский потенциальный граф. Пусть V - множество вершин, a R - множество ребер графа G- . Множество V можно разбить на два подмножества V=cUP, где Е - множество вершин, соответствующих элементам, а множество Р - цепям схемы. Вершины множества V будем называть элементными, а вершины множества Р - потенциальными.
Определение. Пусть ї)" Е . Вращением вершины УҐ назовем циклическую перестановку терминальных вершин. Каждой терминальной вершине можно сопоставить смежную с ней потенциальную вершину. Вращение будем обозначать
Rot Ctr).
Вращению элементной вершины и" соответствует некоторая" перестановка цепей, связанных с контактами элемента в . Эту перестановку также назовем вращением и обозначим Rot С ) .
Определение. Пусть Rot (V) = С Pi 9 Ра , ... , PnJ , Pi С 1--1,2,..., П) - потенциальная вершина, соответствующая цепи С,-. Будем говорить, что вращение вершины 1 допустимо, если элемент Є с вращением Rot (е) - CC-i, Съ ..., CfJ) физически реализуем.
Поясним последнее определение. Для некоторых элементов ИМС, в силу их функциональных или конструктивных особенностей, возможно присоединение проводников, реализующих цепи Сі , в различном порядке. Так, логический вентиль допускает все возможные перестановки входных сигнальных шин, подходящих к его контактам, поскольку его срабатывание не зависит от порядка входных сигналов. Транзистор в ИС допускает две зеркально симметричные физические реализации, что также соответствует всемвозможнымпереетановкамцепей,-связанных с его контактами.
Анализ методов метризации
Основными метрическими критериями, которым должен удовлетворять эскиз ТОПОЛОГИЙ электронной схемы, являются критерии минимума занимаемой площади, суммарной длины соединений или длины отдельных проводников, равномерного заполнения монтажного пространства и минимума числа точек перегиба проводников. При этом должны выполняться ограничения на минимально допустимые расстояния между элементами и проводниками и ширину проводников.
Во реем многообразии штааов к реванш задачи метризации можно выделить два основных направления.
Первое направление заключается в использовании для решения задач размещения и трассировки чисто топологической информации о плоской укладке. Плоский граф при этом является лишь вспомогательным оредством, используемым для улучшения качества результатов размещения и трассировки, которые осуществляются классическими методами. Анализ плоского графа на этапе размещения позволяет определить порядок установки элементов для улучшения условий трассировки. При трассировке на основе плоского графа может быть определен порядок проведения трасс. Такой подход используется в работах /7,30,44,52,59/.
В работе /116/ показано „ что при любом расположении на плоскости точек, соответствующих вершинам пяанарного графа, их можно соединить непересекающимися ребрами, хотя конфигурации соединений при этом могут оказаться весьма сложными. Естественно предположить, что информация о циклическом порядке расположения вершин в соответствии с гранями плоского графа позволит построить эскиз топологии, удовлетворяющий основным метрическим критериям. Данный метод метризации является последовательным, то есть координаты очередного размещаемого элемента и расположение очередной прокладываемой трассы ВЫЧИСЛЯЮТСЯ без учета последующих шагов. Таким образом, решения, оптимизирующие процесс на данном шаге, могут препятствовать оптимизации на последующих шагах. Принимая во внимание метрические ограничения - ширину :проводников и минимально допустимые расстояния между элементами и проводниками, следует ожидать, что фрагменты эскиза топологии, построенные на предшествующих этапах синтеза, могут блокировать проведение соединений на последующих этапах. В рамках данного направления разработаны методы метризации, направленные на последовательное построение по граням изображения плоского графа /21,73,101,107/, и на синтез эскиза топологии /31,105,124/.
Следует остановиться на методе метризации, основанном на аналогии Татта между плоскими графами и рассечениями прямоугольника на прямоугольники меньших размеров /88/. Особенностью данного подхода является то, что переход с топологического уровня на метрический имеет точное аналитическое выражение. А именно: решая систему нелинейных уравнений, задаваемую на основе плоского графа и размеров элементов, получают плотное размещение элементов, которые, в принципе, могут быть соединены без пересечений проводников. Развитие этого метода и особенности его реализации приводятся в работах /24,25,87,122/, Недостатком метода являются значительные вычислительные трудности,связанные с решением системы нелинейных уравнений. Кроме того, при использовании данного метода не решается задача трассировки.
Альтернативным подходом к задаче метризации является получение изображения плоского графа в качестве промежуточного этапа при построении эскиза топологии. Построение эскиза топологии при этом производится в интерактивном режиме на основе изображения соответотвувдего плоского графа. Данный подход рассматривается в работах /24,25,41,112/.
Информационное обеспечение СТП
Состав и структура информационного обеспечения (ИО) СТП тТраф-1" соответствуют требованиям, предъявляемым к современным АСКГЇ, но имеют также рад особенностей,, обусловленных технологией проектирования, реализуемой в системе "Граф-Г\ Изложение основных концепций построения АСКІЇ приводится в работах /18,34,57,69.80,81,83,123/.
Так же как и в других АСМ, информационное обеспечение СТП "Граф-Г1 включает в себя базу данных системы (БД), пакеты программ обмена модулей системы с Щ, управления Щ. В состав Щ входят оперативный банк данных (05Ц) сеанса проектирования, библиотека исходных текстов на Я00, библиотека внутренних представлений исходных объектов я библиотека маршрутов проектирования (ШП). функцией ОВД является хранение данных, полученных в результате работы проблемных модуле! СТП, и являющихся, в свою очередь, исходными для других модулей. В библиотеке исходных текстов хранятся описания фрагментов заданий на проектирование, таких как принципиальные схемы, иикрогеометрии и модели. Различные проектные процедуры находятся в ВШ и представляют собой наборы текстов на ЯОД. Программы обмена предназначены для передачи данных между файлами Щ и рабочим областями пакетов проблемных программ. Программы управления БД служат дяя модификации ДЦ, поиска данных, выдачи справочной информации о ее составе и характеристиках объектов, входяищх в ОБД. Специфические черты ИО СТП "Граф-І" относятся прежде всего к организации Щ.
Наличие естественной иерархии в структуре процесса автоматизированного проектирования топологии, реализуемого системой, делает целесообразным выбор иерархической организации данных.
Действительно, многовариантность решения задачи синтеза эскизов топологии, отношение подчиненности различных уровней детализации проектных решений, иерархия компоновочных блоков базового кристалла, позволяют представить информационные связи в СТП в виде древовидной структуры, узлами которой являются объекты, порождаемые в ходе процесса проектирования.
Для эффективной реализации иерархических моделей данных в СТП "Граф-1" использованы принципы организации данных, принятые в операционной системе UNIX . Идеология системы U Л/IX признана наиболее перспективной при создании САПР ШС нового поколения. Примером применения этой идеологии является система SPLt С Е, /но/.
Рассмотрим основные понятия, связанные с иерархической организацией данных /6,19/. Основными структурными компонентами иерархической модели данных являются узлы и направленные связи, образующие дерево. Связь, направленная от узла X к узлу Y , определяет отношение подчиненности объекта Y объекту X . Узел, для которого все связанные с ним узлы являются подчиненными, называется корнем дерева- Положение любого узла относительно корня определяет уровень иерархии этого узла. Узлы, не имевдие подчиненных, называются терминальными. Узел характеризуется совокупностью атрибутов, задающих некоторый объект ЕД.
Диаграмма Бахмана /19/, изображенная на рис. 4.1, задает логическую схему БД СТП "Граф-І". Логическая схема является представлением ДЦ с точки зрения пользователя системы. Каждый прямоугольник диаграммы соответствует сегменту информации. Надписи в прямоугольниках характеризуют поля сегментов. Двойные стрелки, входящие в сегменты, изображают отношение "один ко многим", что отражает подчиненность нескольких экземпляров нижнего сегмента одному экземпляру верхнего сегмента.
В логической схеме БД СТП "Граф-I" экземпляр сегмента I представляет собой фрагмент ФЗ на ЯОО, описыващий входные объекты. Внутреннее цредставление каждого объекта является экземпляром сегмента 2. Проектная процедура, представляющая собой последовательность директив, является экземпляром сегмента 3, Из различных внутренних представлений входных объектов могут быть собраны различные задания на проектирование. Задание на проектирование однозначно соответствует плоскому модифицированному графу, вследствие чего эта пара задает поля экземпляра сегмента 4.
