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

V.' 1;

На правах рукописи

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ПОСТРОЕНИЯ ОТКРЫТЫХ, ГЛУБОКО ИНТЕГРИРОВАННЫХ САПР СБИС

Специальность 05.13.12 - системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени доктора технических наук

Москва - 1997

Работа выполнена в Научно-исследовательском институте систем автоматизированного проектирования радиоэлектронной аппаратуры и сверхбольших интегральных схем Российской академии наук (НИИСАПРАН).

Официальные оппоненты:

- доктор технических наук, профессор Норенков И.П.

- доктор технических наук, профессор Ильин В.Н.

- доктор технических наук, профессор Широ Г.Э.

Ведущее предприятие - Институт точной механики и вычислительной техники им. С.А.Лебедева

Защита состоится "_"_1997г. в_час._мин.

на заседании диссертационного совета Д142.06.02 Научно-исследовательского института Микроприборов, Москва, 103460

С диссертацией можно ознакомиться в библиотеке НИИМП. Автореферат разослан "_"_ 1997г.

Ученый секретарь

диссертационного совета, д.т.н., профессор

Блинов Г.А.

Общая характеристика работы

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

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

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

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

САПР СБИС. -

Основные задачи работы:

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

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

• Комплексная проработка интегрированного представления проекта в ИБД, а именно: формализация основных аспектов предметной области СБИС, необходимых для иерархического проектирования; создание на основе формального описания предметной области и исследование метода тесной интеграции проектной информации; разработка информационной модели предметной области САПР; решение проблемы эффективного упорядочения больших объемов геометрических данных.

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

• Создание и исследование нового подхода к конструированию проектных потоков, обеспечивающего их быструю генерацию в процессе проектирования: формализация предметной области управления потоками, создание теоретического базиса для автоматической генерации потоков, разработка и исследование алгоритмов генерации.

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

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

Научная вовнзаа:

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

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

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

с

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

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

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

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

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

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

Защищаемые в работе положения:

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

• Оригинальная иерархия моделей данных, обеспечивающая представление проектной информации на альтернативных уровнях абстракции и тем самым поддерживают;« гибкость в представлении информации.

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

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

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

• Метод иерархической сортировки топологической информации, являющийся обобщением известных методов иерархической сортировки д позволяющий получить известные методы как частные случаи. Ои дополнительно предоставляет возможности поиска компромисса между временем выполнения операций над топологией и объёмом требуемой памяти.

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

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

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

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

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

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

Реализация научно-технических результатов работы. Результаты диссертации нашли практическое применение при создании отраслевых систем проектирования в НИИ Автоматики и НИИ Молекулярной

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

Апробация работы. Результаты диссертации докладывались и обсуждались на Научно-техническом семинаре "Машинные методы проектирования электронных схем" (МДНТП, Москва, 1975), на Втором Всесоюзном координационном совещании по проблеме автоматизации проектирования интегральных схем (Киев, 1977), на Отраслевой конференции "Автоматизация проектирования изделий электронной техники" (Москва, 1977), на Восьмой Всесоюзной научно-технической конференции по микроэлектронике (Москва, 1978), на Республиканской конференции "Методологические и прикладные аспекты систем автоматизированного проектирования" (Ташкент, 1981), на Научно-техническом семинаре "Разработка и применение информационных систем на основе баз данных сложной структуры" (Севастополь, 1981), на Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем" (Ереван, 1983), на Научно-техническом семинаре "Автоматизация проектирования в рэдноэлектррнике и вычислительной технике" (МДНТП, Москва, 1984), на Второй Республиканской конференции "Методологические и прикладные аспекты зистем автоматизированного проектирования и управления в отраслях народного хозяйства" (Ташкент, 1985), на Всесоюзной конференции 'Теоретические и прикладные вопросы разработки и экснлуагации САПР ?ЭА и БИС" (Москва, 1986), на Республиканской школе-семинаре "Методы штоматизированнсго проектирования электронно-вычислительной шпаратуры и СБИС" (Черновцы, 1987), на Третьей Республиканской сонференции "Методологические и прикладные аспекты систем

автоматизированного проектирования" (Ташкент, 1987), на Межреспубликанском семинаре "Интеллектуальные САПР СБИС" (Ереван, 1988), на школе-семинаре молодых ученых и специалистов "Актуальные проблемы интеллектуальных САПР РЭА и СБИС" (Гурзуф, 1989), на Всесоюзной конференции "Теория я практика построения интеллектуальных интегрированных САПР РЭА и БИС" (Звенигород, 1989), на Всесоюзной школе-семинаре ''Методы искусственного интеллекта в САПР" (Гурзуф, 1990), на совместном симпозиуме ИПИАН, НИИСАПАН и фирмы Сименс (Германия) "Information Processing and Software System Design Automation" (Москва, 1990), на Международной школе молодых ученых и специалистов "Новые информационные технологии в проектировании" (Гурзуф, 1991), на Третьем Международном семинаре по автоматизации проектирования "Russian Workshop'93" (Москва, 1993), на Европейской конференции по автоматизации проектирования EuroDAC'93 (Германия, ,1993), на научных семинарах университета Карнеги-Меллона (США, 1993-94), на Российской конференции "Микроэлектроника-94" (Звенигород, 1994), на . Второй Международной научно-технической конференции "Микроэлектроника и информатика" (Москва, 1995), на Европейской конференции по автоматизации проектирования EuroDAC'96 (Швейцария, 1996).

Публикации. По теме диссертации опубликованы 63 печатные работы, в том числе монография "Системная среда САПР СБИС".

Структура и объём диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы из 202 наименований и приложения. Материал диссертации изложен на 343 страницах, включая рисунки, графики и таблицы.

Содержание работы

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

В первой главе в целях обоснования и уточнения направлений

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

Для первого поколения (60-е годы) характерно отсутствие какой-либо системной организации.

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

В САПР третьего поколения (конец 70-х - начало 80-х годов) прослеживается попытка создать, единое хранилище проектных данных на основе общего представления предметной области проектирования ИС. Для поддержания общей базы данных использовались, как правило, коммерческие системы управления базами данных (СУБД).

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

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

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

роль играет консорциум CAD Framework Initiative (CFI).

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

Рис.1. Архитектура системной среды

В то время как ядро, интерфейс пользователя и некоторые другие компоненты системной среды хорошо проработаны, этого нельзя сказать о представлении проектной информации, обеспечении эффективного доступа к ней, управлении методологией. Этим важнейшим компонентам посвящен обзор, приведённый в главе 1. В заключение обзора в качестве примера рассмотрена системная среда Falcon Framework фирмы Mentor Graphics.

Анализ, выполненный в главе 1, показал, что современные

инфраструктуры обладают целым радом недостатков:

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

• имеются трудности с решением сложных задач, требующих обработки информации сразу по нескольким аспектам представления БИС;

• методы оптимизации структур для хранения больших объёмов данных недостаточно проработаны;

• отсутствуют возможности быстрого формирования проектных процедур и др.

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

Концепция базируется на новых методах построения САПР, обеспечивающих:

1) гибкость в представлении и обработке проектных данных;

2) интегрированность и эффективность представления проекта;

3) гибкость в подключении прикладных программных модулей и в управлении ими.

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

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

RULE

1 RULEj— i

lRESULTH*^j EXPRESSION

Л

Ш

RESULT

NAME

NF

NF

TRT TRF

Реляционный Семантический

Гибридный

CN

оми 801

DMU

Многоуровневая модель Система манипулирования

данных данными

Рис.2. Гибкость в представлении и обработке данных

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

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

Для достижения необходимой эффективности при оперативной обработке больших объемов информации в ИБД предусматриваются специальные методы сортировки данных.

Гибкость в подключении прикладных программных модулей и о управлении ими состоит в том, что, во-первых, поддерживается необходимый набор стандартизованных методов подключения прикладных программ к ИБД (рис.4). Это обеспечивает возможность компромисса "эффективность-

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

Рис.3. Интегрированность представления проекта

Рис.4. Гибкость в подключении прикладных программ

Концепция гибкой интеграции является развитием современных методов построения системной среды САПР. Что касается проблемы представления проекта, то 3d счёт более тесной координации различных аспектов его описания обеспечиваются лучшие условия для анализа. Действительно, в современных системах проектирования, таких, как САПР Mentor Graphics, это весьма сложно реализовать, поскольку проектные данные хранятся в( виде набора слабо связанных файлов.

Концепция гибкой интеграции даёт также дальнейшее развитие средств управления проектными данными: появляются возможности работы с альтернативными решениями; обеспечивается представление проекта на нескольких разных уровнях абстракции, поддерживаемых иерархией моделей данных и иерархией средств доступа к данным. Тем самым обеспечиваются возможности как инкапсуляции, так и интеграции различных классов прикладных программ.

В области управления проектной методологией концепция гибкой интеграции предлагает добавление новых методов подключения прикладных программ к САПР и методов управления ими в процессе проектирования.

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

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

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

Четвертый, гибридный уровень является базовым в иерархии моделей. Он ассоциирует принципы организации реляционной и сетевой моделей данных. На этом уровне информационные сегменты трансформируются в

плоские таблицы, аналогичные реляционным отношениям н(^А1,А2,...,А^, которые состоят нз кортежей Т. = {а( (г 2, ...,а. п).

СЕМАНТИЧЕСКИЙ

РЕЛЯЦИОННЫЙ

ШБРИД11ЫЙ (РЕЛЯЦИОННО-СЕТЕВОЙ)

СЕГМЕНТНЫЙ

ФАЙЛОВАЯ СИСТЕМА

ДИСКОВОЕ ПРОСТРАНСТВО

Верхний уровень

Нижние уровни

Рис.5. Иерархия моделей данных

Атрибут А) кортежа Т0 содержит ссылку на ближайший свободный кортеж А[ - тт{!л(т^, <= Тугее), где Т^ее - множество свободных

кортежей, Г.} - логический адрес Т(. В свою очередь первый атрибут

свободного кортежа содержит ссылку на следующий свободный кортеж. Если свободный кортеж является последним, то ссылка ставится на нулевой кортеж л. = о, А. <= Г(, Т. е Тугее, Таким образом формируется кольцо

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

Индекс, например, обеспечивает связь "один-к-одному" мезвду двумя

отношениями и Ку Она организована за счет хранения в ссылочном атрибуте логического адреса сопряженного кортежа, т.е.:

Т*,1 = <°/.Га2,ги{гь,).....°,М>'

На рис.6 приведен пример индексной связи.

Логический адрес

Атрибут, содержащий индекс сопряженного кортежа

1 Т0_1 5 1.23 566

2 Т0 2 0 2.65 1204

3 тс_з 1 гх 4.32 432

4 КЕО_1 " 4 . л. 5.23 897

5 Ш£0_2 2 / ч 12.43 343

. . . ... ...

Рис.6. Пример организации связи с помощью индекса

Сочетание реляционных и сетевых методов организации данных обеспечивает альтернативные возможности в плане достижения нужной эффективности при хранении и обработке информации. В частности, когда взаимосвязи между данными не могут быть четко опрг.и*т-ч»:. пячпабгтчик БД может выбрать "мягкие связи", реализуемые реляционна;1 составляющей модели. В противном случае лучше использовать сетевые методы доступ.!, обладающие более высокой эффективностью.

В табл.1 приведены сравнительные характеристики реляционной, сетевой и гибридной моделей. В ней N - общее количество записей данного типа в файле; т - количество записей в наборе (цепочке); л - количество сопряженных записей; символ " ' " означает, что в сетевой модели перемешаны. записи различных типов, и, следовательно, система будет тратить больше времени на чтение записей одного типа.

Последний, верхний уровень иерархии моделей состоит из двух частей - реляционной и семантической. На реляционном уровне файл

представляется в виде одной таблицы, состоящей только из информационных атрибутов. Семантический уровень представляет собой модель, названную HSM (Hierarchical Semantic Model).

Таблица 1. Сравнение моделей данных

Реляционная Сетевая Гибридная

модель CODASYL CADS

Коддз

Выбрать все записи N N' N

данного тина

Выбрать несколько записей m*N/(mM) т' т

по критерию отбора

Получить | найдена 0.5 N 0.5 т' 0.5 in

уникальную | не найдена N т' т

Занести заш;;ь 1 1 + п' 1 + п

Удалить запись 1 1 + п' 1 + п

Затраты памяти 100% 70% 60 %

Построение описания предметной области (информационной модели) в рамках ШМ базируется на принципах фрагментации, иерархии и дублирования. Последний означает дублирование информации при наличии перекрёстных ссылок между фрагментами. Такой подход позволяет избежать ссылок между внутренним подфрагментами составных фрагментов и устранить разорванные связи. '

Уровни рассмотренной иерархии моделей тесно взаимосвязаны. Они обеспечивают доступ к данным »на нескольких уровнях абстракции. Такой подход позволяет сочетать быстрое макетирование системы на высоком уровне абстракции с эффективным, но более трудоёмким программированием на нижних уровнях."

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

На самом нижнем (базовом) уровне программисты пользуются библиотекой, назначение которой - низкоуровневые операции над сложными

объектами. Средний (гибридный) уровень взаимодействия с БД обеспечивается библиотекой манипулирования данными, поддерживающей всю обработку информации через мета-описания (типы) объектов. Она не только упрощает работу программиста, но и обеспечивает более высокую степень достоверности информации. Верхний уровень состоит из двух частей: прекомлилятора реляционного языка запросов и программного интерфейса.

Средства доступа из прикладных программ

Специализированные Общего назначения

Обработка иерархии Обработка графических объектов (GEOPROC) Прекомпилятор языка SQL Программный интерфейс (Библиотека OMU)

Манипулирование данными на гибридном уровне иерархии моделей данных (Библиотека DMU)

Базовые средства доступа к данным

Рис.7. Средства доступа к базе данных из прикладных программ

Проблема манипулирования данными на реляционном уровне исследована на примере языка SQL (Structural Query Language), являющегося стандартом ISO. Доступ к базе данных из прикладных программ через SQL осуществляется в режиме прекомпиляции. Это равносильно применению генератора программных модулей. Именно в поддержании возможностей обработки достаточно сложных и заранее не определенных запросов, что удобно при быстром создании прототипа САПР, заключается смысл обеспечения доступа к данным из языка SQL. .

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

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

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

Пусть А = {А.} - множество всех информационных атрибутов файла;

А. = {й(. j) - подмножество информационных атрибутов, принадлежащих i -му сегменту; G = (X.U) - граф схемы данных, где X = {х;.) - множество взвешенных вершин (сегментов), и = [н.} - множество ориентированных взвешенных ребер, задающих связи между сегментами, a^i/J - вес ребра; p(x.J - вес вершины; r^rj = А. - отображение вершины-сегмента на

множество атрибутов; Г '(л,) " х. - обратное отображение. Модель одного из файлов ИБД, описывающего список соединений, показана на рис.8.

Рис.8. Модель файла "Список соединений"

Модель обладает следующими свойствами:

1) возможна ситуация, когда Г^х-J = 0;

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

4) вес вершины (Р) характеризует трудоемкость поиска заданного кортежа в соответствующем отношении.

Запрос на языке SQL имеет следующее формальное представление:

Select А^ from <имя мета-файла> where obj = <нмя фанла>, aad {a'kjfixp,Val} , где: А® ~ множество искомых атрибутов, а^ ¡^ А1' - множество

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

Для SQL запроса, заданного таким выражением и сформулированного для информационного файла, имеющего описанную выше графовую модель, требуется найти часть С - (Л', U') графа G = (X, II), такую, что:

J) Все вершнны, входящие в запрос, связны. Для любой пары вершин имеется маршрут (причем только один), соединяющий эти две вершины, а

2) Суммарная длина маршрута, соединяющего все вершины, входящие

В диссертации разработан ориганатьный алгоритм решения этой

задачи, имеющий вычислительную сложность ), где N - число вершин.

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

в запрос, минимальна:

min.

(библиотека OMU - Object Manipulation Utilities), который является дальнейшим развитием международного стандарта CFI, а также методика его использования проработаны в диссертации.

В табл.2 приведена сравнительная характеристика уровней доступа.

Таблица 2. Срангсьиэ уровней доступа

Метод Эффек- Удобство Незави- Дополнительно

доступа тивность исполь- симость

кода зования

Базовый 1 0.2 0.1 Нет контроля за дей-

ствиями пользователя

Гибридный 0.6 0.5 t Обработка через

метаописанпе

SQL 0.6 0.8 0.8 Высокая скорость

программирования.

Сложности при отладке

ПИ (OMU) 0.8 0.9 0.8 Большой набор функций

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

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

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

др.), вспомогательные предметные понятия (сетки размещения, трассировки и регулярности, постоянная часть кристалла, базовая точка и др.).

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

' т

множество областей с заданным разбиением по подмоделям А - А/,

I ~ 1

множество типов областей РА и функцию их типизации ц/ :А -> РА; группу контуров <3, определяющую границу модели; привязку фрагмента к конструктиву, заданную парой ц = (-ру, иЗ; предикат ...,хт),

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

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

Соответствие ВТ, установленное между множествами типов

схемных (ТСФ) и топологических (ТТФ) фрагментов и Вт, называется топологической реализацией. При этом структурная схема СБИС, задаваемая кортежем <Л6, В<,, <ру Р5>, и структура топологических фрагментов удовлетворяют следующему условию:

е й'^лУб^е (34(йл)3й7,е В7[ф7(&г) е Ж<рл(6х))] л

' ' «а-

Здесь: - множество всех схемных фрагментов, р

определяет соответствие вложенности, Л^ - соответствие типизации

схемных фрагментов, ф?,:/?7,-> - соответствие типизации топологических

фрагментов. Показано, что соответствие X порождает также взаимосвязи между множествами фигур ТТФ й полюсами или цепями ТСФ.

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

схемы представляется кортежем (В^Е^Е^Ф^ С'Л, />х>, где Е3 = {Еь\Ь е В$) - полюса ТСФ; = е /??} - составы ТСФ; Фу = {<рА|й е -

типизация составов ТСФ; С5= {С4|6 е В,.} - коммутации ТСФ; = {¡'ье В3} - внешние параметры ТСФ. Здесь Еь = {еь} - множество

псевдосхемных фрагментов, <р Ь:ЕЬ->В5 - типизация псевдосхемных фрагментов.

Математическая модель конструктива кристалла представляется кортежем (Б^А^а^ {Тк}, {/^1, {Лд.}, где компоненты кортежа,

соответственно, множества: топологических слоев; областей, определяющих постоянные части кристалла; ак:Ак->Я - соответствие принадлежности

слою; множества сеток трассировки Тк, размещения Рк и регулярности Кк, а также привязок сеток Тк, 1'к, 1<к к базовой точке кристалла.

Математическая модель топологии СБИС представляется кортежем {Вр ЕрФТ,Аг г|г), где В?. - множество типов топологических

фрагментов; Ду = {Пь\Ье.Вт} - составы ТТФ; г- {<р4 \ЬТ е

типизация составов ТТФ; Ат= {АЪ\Ь е Иг) - области ТТФ;

= {ай|/) е Ит) - соответствие принадлежности областей топологическому слою; = ('сь е Вт\ - соответствие областей полюсам и цепям типа

схемного фрагмента; 11 т = {ць^>&Вт} - векторы смещения ТТ<

относительно узлов сетки регулярности.

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

5 (V,

Рис.9. Взаимосвязи составных частей предметной области

Показано, что введённых понятий достаточно для построения процесс Иерархического проектирования ИС, состоящего в образовании типо топологических фрагментов и их состава, в создании и постепенно; уточнении топологических моделей ТТФ вплоть до получения полнот описания топологии. *

Формализованное описание предметной области являете теоретической основой для создания схемы интегрированной базы данны? Ключевым моментом ИБД, структура которой показана на рис.10, являете тесное сочленение схемы и топологии. Узлами в дереве иерархии схемн являются типы схемных фрагментов, а в иерархии топологических подсисте! - типы топологических фрагментов. В ИБД поддерживаются два вида связе] .между ТСФ и ТТФ: по атрибутам, устанавливающая соответствие межд цепями, полюсами и подфрагментами; между ТСФ и множеством ег альтернативных ТТФ.

Информация для программ | моделирования

Библиотечные элементы

¡"иформлиия для программ | синтеза топологии

Каталог связи "Схема - Топология"

ТСФ (интерфейс, структура, спецификация) Цепи

Полюса

Подфраг-менты

Полюса ПФ

Библиотеки

-Каиисушии_

Проектные нормы

А

......

ДПЙ----

I

-----Кб"

Модели

Каталоги

Цепи ТТФ (интерфейс, ядро)

Полюса

Подфраг-менты

Полюса ПФ

Модели

Каталоги

Временные файлы

Развертка схемы

Топология активного _фрагмента

Конструкция фрагмента

Рис.10. Интегрированная база данных

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

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

описанные предмегные области, позволяющая работать с версиями и альтернативными решениями.

Информационная модель состоит из двух основных частей (рис.11) -системной и проектной информации. Системная информация включает: доступные технологии, множество конструктивов кристаллов, множество стандартных решений. Проектная информация включает часть выбранной разработчиком СБИС системной информации и проектируемые фрагменты.

Рис.11. Головной фрагмент информационной модели •

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

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

Определим иерархическую систему квадрантов в виде множества W = {(Г.), где каждый элемент представляет собой множество квадрантов IF, = \wjj}, составляющих i-i\ уровень иерархии. Подмножество 1Уд состоит из одного квадранта нулевого уровня, которым является вся площадь топологии. Система W обладает свойством: Vie {/, г, /} [/. = a/. + /J , где

п - количество уровней иерархии в W; а - целая положительная константа. Будем считать, что система квадрантов определена, если для нее задано число уровней иерархии п, а для любого i е {/, 2, задана величина I..

Пусть дана топология К = {Л.}. Обозначим б - окрестность квадранта

w.. через (f{w При е = О справедливо = w..; при е = /

подмножество 0Е(и> ) будет включать w.. и смежные квадранты, имеющие с

ним общую сторону или угловую точку и т.д. Охарактеризуем каждый контур k. s К некоторой базовой точкой Ь^.

Особенностью метода является то, что контур относится только к

некоторой совокупности квадрантов И?(к) с (Г., где /' = max (0,1,2,...,п), при

выполнении условий:

3 W. .6 W. >J I

Л6 "и) Л U = k

V». . 1-»Л (*) м<. . л •«>. . е О °Ги». .) .

Здесь е - целое неотрицательное число, определяющее количество Р'

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

Е - Е ,

проанализировать квадранты из О

Таким образом, манипулируя параметрами л, а, г^ и сц, можно

конструировать новые, не известные ранее методы иерархической сортировки и выбирать наиболее подходящие для реализации в САПР. Для решения задачи выбора в диссертации созданы модель метода сортировки, механизм и инструментальные средства оценки получаемых вариантов. Их использование проиллюстрировано на рис.12, где представлены результаты для случая варьирования п, гр, ед при а=2. Решение п=6, гр = 1, е^ = 1

является наилучшим по времени вырезания окна из топологии, но объем хранимых данных возрастает более, чем пятикратно по сравнению со случаем е = 0.

к

У\ V \ \ \

V—

\

Рис.12. Вариант фиксации а=2

Практическое испытание метода сортировки показало, что в результате совершенствования структур данных скорость обработки может быть повышена не менее, чем в 3-4 раза по сравнению с известными методами.

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

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

Прикладные программы по степени их открытости можно разбить на внешние, разработанные без учёта требований системной среды, и заказные, разработанные с учётом возможностей системной среды или специально для неё. Последние используют для хранения и обработки проектной информации либо непосредственно ИБД и СУПД (встроенные пакеты), либо, собственные базу данных и средства доступа к ней (автономные пакеты).

КЛАССЫ ПРИКЛАДНЫХ ПРОГРАММ

Заказные Внешние

Встроенные Автономные

* 1

1 Объектно-1 ориентированный интерфейс Языковый интерфейс

СРЕДСТВА МАНИПУЛИРОВАНИЯ ДАННЫМИ

Рис.13. Схема подключения прикладных программ

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

информационного взаимодействия с ИБД. При этом обработка информации может осуществляться как непосредственно в ИБД (такой режим является основным), так и во внутренних структурах программы. В первом варианте обеспечивается прямой доступ ко всем аспектам представления проектной информации в их взаимосвязи. За счёт использования низкоуровневых средств манипулирования данными эффективность интерфейса САПР со встроенной прикладной программой повышается по сравнению с автономными программами в 1,5-2 раза при увеличении затрат на программирование приблизительно в 2 раза.

г ~ —---------------- ---_ —.--

. а)

Г — —----—----'--------— 1

I Прикладная программа I

Ь)

Рис.14. Схемы подключения встроенных прикладных программ: с использованием ИБД (а) или внутренних структур данных (б)

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

поток создаётся автоматически на базе математической модели схемы задач.

В целях построения модели и алгоритма генерации потока выполнена формализация предметной области: исследовано представление схемы задач в виде сущностей и связей, введены понятия графа виртуальной сущности

= (л^', (/'') и графа простой проектной задачи <7(Г = (л^, У7), в

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

отображению соответствует подстановка:

со со

СЕ

-хГ'хи,1> го

7/- С£> ,х. ,х. ,, > 1,П' у,/'

ТР СО

Х/, /•"•■ Хк, /,/'"•' хи п'Х], I'

С£>

ТВ

— ■"у, 1,1>—'Х1,1,п>

' У,

ко о

77П ТУ'

Теоретико-графовая модель схемы задач определена как граф являющийся результатом склеивания графа простых проектных задач О7 = {х1, (/) с использованием графа виртуальных сущностей О

Пример теоретико-графовой модели схемы

задач показан на рис. 16.

В диссертации показано, что предложенная графовая модель способы; играть роль стандартизованного, наиболее общего представления схемь задач. Другие) специальные представления могут быть получены из этог< стандартизованного представления. Одним из таких представлений, удобны» для автоматической генерации потоков,' является предложенньп

расширенный граф схемы задач GSE - lfE). Вершины XSE --этого графа соответствуют простым сущностям и копиям простых проектных

задач. Следовательно, имеем /£ = '/Ни/ЕГ, где XSf'E {х*ЕЕ} -

,SET , SET,

множество вершин, отвечающих простым сущностям, X Ц. } -

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

проектного потока G 7 - {/.if) - это часть расширенного графа схемы

SE

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

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

„SE '( SE rlSE] „ _ „ ЕС

О = , и / в определяющий набор цепей R .

Алгоритм гарантирует формирование наилучшего потока в том смысле,

что минимизируется сумма всех расстояний между всевозможными парами

'входная листовая вершина - конечная листовая вершина", т.е.

„ J SE SE)

L 4*, <xj ) - m,n-

EC( SE SE) EC

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

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

Рис.17. Пример расширенного графа схемы задач

ПС), Т]4, Ю, ТЮ,А1, (£<), Т7, ЕхС (С() ; Ш, Т КО, Т10,А1 (И), Тр ЕхС{С1) ; Яг,ТшА1(и), Ту, ЕхС (С!) \СЕх,Т7,ЕхС(С1) ; 1>Е<1,Г15,Е(11>(1>1), Т]0,АЬ(и),Г7,ЕхС(С1) ; Ес}}>(РО,Т]5,Ес1Р(Р1),Т10,АЦ11),Т7,ЕхС(С1)-, . ОШ, Т[7, йШ, Т,2, N11, Т!0> АЕ (11), Тт, ЕхС (С/) ; ОМЕа, Тп, ОШ, Тп, N11, Т1(], А1 (И), Т7, ЕхС (СI) ; МС, Г12, N11, ГЮ,АЬ (¿0, Т7, ЕхС (С<) ; Е4С(а),Г6,£с1С(С1),Т12,т1,ТшАЕХЕ1),Т7,ЕхС(С1) ; СЕс1, Т6, Ее/С (СI) ,Тп, N11, Т10, АЕ (¿0, Гр ЕхС (С/) ;

/ж*, г17, ош, г12, ян, т5, а\ т,, рр-,оша, т]7, имь, т12, т, т5, ср, г;, рр,

МС, т[2, N11, т5, СР, Г,, РР;СЛя, Т5, СР, Т{,РР,Р1г, 7), РР; ЕПС (С/), Г6, Е(1С (С/), Т12, N11, Г5, СР, Тр РР; СЕс1, Тб, Ес1С(С1), Т]2,'М1, Ту СР, Т,,РР.

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

количеством целей. Как видно из таблицы, применение метода автоматической генерации даёт выигрыш по скорости конструирования не менее, чем в 10 раз по сравнению с методом интерактивного конструирования.

Таблица 3. Сравнение методов конструирования потоков

Количество типов программ и файлов в САПР Количество сущностей/ целей в потоке Трудоёмкость кодирования вспр! (строк/дней) Трудоёмкость интерактивного конструирования (операций/часов) Трудоёмкость автоматической генерации (операций/минут)

100 50с./5ц. 350стр./35дн. 300оп./15час. 16оп./50мин.

100 25с./3ц. 175стр./18дн. 150оп./7,5час. 9оп./25мин.

30 20с./2ц. 140сгр./7дн. 80оп./2,7час. 7оп./15мин.

30 Юс./ 1ц. 70стр./3,5дн. 40оп./1,4час. 4оп./10м1ш.

В шестой главе диссертации рассмотрена системная среда САП!», в которой концепция гибкой интеграции нашла своё воплощение. Дано

. описание следующих составных частей CADS: структура интегрированной базы данных на гибридном и семантическом (информационная модель) уровнях; система управления проектными данными (библиотеки DTSWR, DMU, SMU, SRV, TRZ, OMU, QEOPROC); система генерации проектных задач.

Заключение

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

В рамках предложенной концепции разработана и исследована новая иерархия моделей данных. Она является органичным объединением ряда известных моделей с оригинальными моделями, предложенными в \ диссертации. Иерархия моделей обеспечивает представление тесно интегрированной проектной информации на разных, альтернативных уровнях абстракции, что даёт пользователю возможность выбора наиболее подходящего уровня в каждой конкретной ситуации.

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

Для обеспечения непроцедурного доступа к интегрированной базе данных разработан и воплощён оригинальный алгоритм преобразован™ запросов с языка SQL в команды алгоритмического языка и функции

библиотеки гибридного уровня. Такое нетрадиционное использование SQL для организации доступа к проектной информации позволяет существенно (в два и более раз по сравнению с использованием средств нижних уровней) сократить время напасают программного кода, что удобно при макетировании приложений.

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

В отличие от известных СУПД, предложенная система управления проектными данными содержит оригинальные средства работы с иерархическими объектами и с графической информацией. Среда GEOPROC позволяет вычислять сложные теоретико-множественные выражения, операндами. которых являются плоские геометрические фигуры. Таким . образом, системная среда предоставляет нетрадиционный инструментарий автоинтерактивных топологических редакторов, программ контроля топологии и восстановления схемы по топологии.

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

Метод глубокой интеграции основан на организации интегрированной базы данных, позволяющей: поддержать необходимые связи между схемными и топологическими фрагментами; облегчить создание и использование альтернативных решений за счёт многоуровневого представления схемных и топологических фрагментов; работать с раздичными видами топологических моделей; обеспечить возможности настройки ИБД. Для представления

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

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

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

Предложен новыц подход к решению проблемы управления

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

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

Воплощением предложенной концепции гибкой интеграции является системная среда CADS, созданная под руководством и ' при непосредственном личном участии автора. Она содержит средства глубоко интегрированного хранения проекта, представления проектных данных на нескольких уровнях абстракции и доступа к этим данным, манипулирования геометрическими данными, управления проектными потоками.

Интегрированная база данных CADS поддерживает тесно сочленённые базы данных моделирования и топологического синтеза, позволяющие работать со стандартизованными фрагментами, а также создавать и использовать альтернативные решения в процессе проектирования.

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

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

В состав CADS входит система управления проектными потоками, которая даёт новые возможности автоматической генерации и редактирования потоков, что не менее чем на порядок повышает скорость генерации.

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

1. Баталов Б.В., Осипов JI.Б., Шепелев В.А. Проверка топологии интегральных схем с помощью ЭВМ. Микроэлектроника. Под ред. А.А.Васенкова. - М., Сов. радио. 1974, вып. 7, с.133-143.

2. Осипов Л.Б., Шепелев В.А., Щемелишш В.М Контроль топологии БИС с помощью дисплея. Материмы семинара "Машинные методы проектирования электронных схем". - М., МДНГП, 1975, с.223-229.

3. Шепелев В.А., Стемпковский А.Л., Стенченков В.Т. Комплексный контроль топологии и фотошаблонов. Микроэлектроника. Под ред. АА.Васенкова. - М., Сов. радио. 1976, вып. 9, с.296-305.

4. Казенное Г.Г., Шепелев В.А., Попова Т.М., Власенко В.А. Система контроля топологии интегральных схем на базе мини-ЭВМ с использованием дисплеев. Микроэлектроника. Под ред. А.А.Васенкова. - М., Сов. радио. 1976, вып. 9, с.289-296.

5. Шепелев В.А. Система контроля топологии БИС. Управляющие системы и машины. - Киев. Наукова дуика. 1976, вып. 6, с. 121-124.

6. Оганесьянц Л.Г., Шепелев В.А. Подсистема графического редактирования топологии БИС. Электронная техника. Сер.З. Микроэлектроника. 1978, вып. 4(76), с.70-75.

7. Шепелев В.А., Оганесьянц Л.Г., Попова Т.М. Функциональные возможности, структура и особенности интерактивной системы отладки топологии БИС. Электронная техника. Сер. 10, Микроэлектронные устройства. - 1978, вып.2(8), с.104-111.

8. Оганесьянц Л.Г., Попова Т.М., Шепелев В.А. Принципы построения подсистемы контроля топологии. Электронная техника. Сер.З. Микроэлектроника. - 1978, вып. 6(78), с.71-73.

9. Баталов Б.В., Козлов 6.11., Нслюбин В.Н., Оганесьянц Л.Г., Попова Т.М. О разработке интерактивной системы проектирования топологии БИС. Тезисы докладов 8-й Всесоюзной конференции по микроэлектронике. - М., 1978, с.249.

10. Оганесьянц Л.Г., Попова Т.М., Шепелев В.А. Подсистема контроля

топологии БИС и получения информации для генераторов изображений. Тезисы докладов и рекомендаций научно-технических конференций. Электронная техника. Сер.З. Микроэлектроника. Автоматизация проектирования изделий электронной техники. - 1978, вып. 5(118), с.61-62.

11. Оганесьянц Л.Г., Шепелев В.Д. Подсистема графического редактирования топологии БИС. Тезисы докладов и рекомендаций научно-технических конференций. Электронная техника. Сер.З. Микроэлектроника. Автоматизация проектирования изделий электронной техники. - 1978, вып. 5(118), с.33-34.

12. Оганесьянц Л.Г., Попова Т.М., Шепелев U.A. Интерактивная система полного контроля топологии БИС. Электронная промышленность. - 1979, вып.4, с.74-80.

13. Оганесьянц Л.Г., Шепелев В.А. Интерактивная система синтеза топологии БИС. Электронная промышленность. - 1979, вып.4, с.57-65.

14. Шепелев В.А. Метод формирования соединительных проводников в топологии БИС. Электронная промышленность. - 1979, вып.4, с.65-68.

15. Шепелев В.А. Специализированная операционная система для интерактивного проектирования топологии на мини-ЭВМ. Техника средств связи. Сер. Микроэлектронная аппаратура. - 1981, вып.1, с.76-85.

16. Шепелев В.А., Попова Т.М. Структура графических данных для интерактивного проектирования го полоти БИС. Техника средств связи. Сер. Микроэлектронная аппаратура. - 1981, вып.1, с.85-90. '

17. Шепелев В.А., Щемелинин В.М., Щавлев H.Ii., Хабаров А.Н. Концепции построения системы "сквозного" проектирования БИС и СБИС. Тезисы докладов Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем". Часть 1. - Ереван, 1983, с.162-163.

18. Шепелев В.А., Щавлев Н.И., Моисеев A.C., Баринов С.Н. Система интерактивного проектирования топологии БИС СПЕКТР-1. Материалы семинара "Автоматизация проектирования в радиоэлектронике и вычислительной технике". -М..-МДНТП, 1985, с. 124-129.

19. Баталов Б.В., Шепелев В.А., Щемелинин В.М., Щавлев Н.И. Концепции построения и архитектура САПР СБИС. Микроэлектроника и полупроводниковые приборы. Под ред. А.А.Васенкова и Я.А.Федотова. - М., Радио и связь, 1984, вып. 9, с. 16-25.

20. Шепелев В.А., Щемелинин В.М., Щавлев Н.И. Об одном подходе к построению модели САПР СБИС. Микроэлектроника и полупроводниковые приборы. Под ред. АА.Васенкова и Я. А.Федотова. - М., Радио и связь, 1984, вып. 9, с.75-84.

21. Шепелев В.А., Щавлев Н.И., Черноусов В.А., Гуляева В.Ф. Организация банка данных САПР СБИС. Микроэлектроника и полупроводниковые приборы.' Под ред. А.А.Васенкова и Я А.Федотова. - М., Радио и связь, 1984, вып. 9, с.53-68.

22. Шепелев В.А., Моисеев A.C., Баринов С.Н. Комплекс программ интерактивного проектирования топологии БИС. Микроэлектроника и полупроводниковые приборы. Под ред. ААВасенкова и Я.А.Федотова. - М., Радио

и связь, 19S4, вып. 9, с.269-277.

23. Шепелев H.A. Принципы организации банка данных САПР СБИС Техника средств связи. Сер. Микроэлектронная аппаратура. - 1984, вып. 1(5), с.4-6

24. Козни Г.В., Щемелшшн В.М., Шепелев В А., Гуляева В.Ф., Федоров В J Язык, и структура базы данных подсистемы топологического проектированы! Техника "срсдсгь связи. Сер. Микрозлектронная аппаратура. - 1984, вып. 1(5), с.22 26.

25. Шепелев ILA., Щаьлев Н.И. Принципы организации банка данных САП СБИС. Аннотации докладов 2-й республиканской коиференци *• Методологические и прикладные аспекты систем автоматизирование! проектирования и управления в отраслях народного хозяйства". - Ташкент, 198: с.35.

26. Баталов Б.В., Немудрое В.Г., Шепелев ВА., Корнилов А.И. Основнь вопросы разработки САПР СБИС для РЭА. Микроэлектроника, АН СССР, т. 16. М-, 1987, аып.2,с.175-180.

27. Моисеев АС., Шепелев ВА. Выбор структуры графических данных д.' интерактивного проектирования топологии. Техника средств связи. Се Мнкроэлектронная аппаратура. - 1987, вып. 1-2, с.48-54.

2S. Шепелев В.А., Моисеев АС., Власов A.B. Поисковая сгрукту! графических данных. Техника средств связи. Сер. Микроэлектронная аппаратура. 1988, вып. 1-2, с.15-21.

29. Моисеев A.C., Лапинский B.C., Баринов С.Н., Шепелев В., Интерактивная графическая система проектирования топологии БИС СПЕКТР-Техника средств связи. Сер. Мшсроэлеиронная аппаратура. - 1988, вып. 1-2, с.З 40.

30. Стемпковский АЛ., Шепелев В.А., Лазарев A.B. Авпиштерактиьиь иерархически1! синтез топологии сверхБИС. Интеллектуальные САПР СБИС. Tí докл. межреспубликанского семинара. - Ереван, 1988, с.10-11.

31. Стемпковский АЛ., Шепелев В.А Методология аиоинтерактивно иерархического синтеза топологии СБИС. Электронная техника. Сер Микроэлектроника. - 1989, вып.2(131), с.10-13.

32. Лазарев A.B., Шепелев В.А. Предметная область и модели фрагментов д автоинтерактивного иерархического синтеза топологии СБИС. Электронн техника. Сер.З. Микроэлектроника. - 1989, вып.2(131), с.14-23.

33. Аванесов Ю.В., Корнилов А.И., Лазарев A.B., Шепелев ВА. Сит топологии квазирегулярных структур в фиксированном базисе библиотечт элементов. Электронная техника. Сер.З. Микроэлектроника. - 1989, вып.2(13 с.30-32.

34. Власов A.B., Шепелев В.А. Метод сортировки топологической иифориащ в структурах графических данных. Электронная техника. Сер.З. Микроэлектронш - 1989, вып.2(131), с.64-69.

35. Горбунов Ю.З., Шепелев В.А. Язык описания предметной области CAI СБИС. Техника средств связи. Сер. Микроэлектронная аппаратура. - 1989, вып.1-

36. Стемпковский А.Л., Шепелев В.А. Унифицированный интерфейс САПР и САИФ СБИС. Техника средств связи. Сер. Микроэлектронная аппаратура. - 1989, вып.1-2.

37. Баталов Б.В., Стемпковский А.Л., Шепелев В.А. Концепция нового поколения САПР СБИС и УБИС. Актуальные проблемы создания интеллектуальных САПР РЭА и СБИС. Тез. докл. школы-семинара молодых ученых и специалистов. - Воронеж, 1989, с.3-11.

38. Шепелев В.А., Горбунов Ю.З. Системная оболочка САПР СБИС. Актуальные проблемы создания интеллектуальных САПР РЭА и СБИС. Тез. докл. школы-семинара молодых ученых и специалистов. - Воронеж, 1989, с. 16-23.

39. Шепелев В.А., Горбунов Ю.З., Власов A.B. Системная оболочка САПР СБИС. Теория и практика построения интеллектуальных интегрированных САПР РЭА и СБИС. Тез. докл. Всесоюзной конференции. - М, 1989, с. 144-146.

40. Моисеев A.C., Шепелев В.А. Оптимизация представления структур графических данных в интерактивных системах проектирования топологии. Методы искусственного интеллекта в САПР. Тез. докл. школы-семинара молодых ученых. - Воронеж, 1990, с.62-63.

41. Y.Z.Gorbimov, V.A.Sliepelev, A.V.Vlasov. System Shell for VLSI CAD. Proceedings of a Joint Symposium, Information Processing and Software Systems Design Automation. - Springer-Verlag, 1990, pp.390-397.

42. Шепелев B.A., Горбунов Ю.З., Абашкин И.Ю. Пакет программ манипулирования геометрическими данными. Новые информационные технологии в проектировании. Тез. докл. Международней школы молодых ученых и специалистов. - Минск, 1991, с.73-75.

43. Стемпковский А.Л., Шепелев В.А., Власов A.B. CADS: системная среда, базирующаяся на концепции гибкой интеграции. Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации Российской академии наук, т.З. - М., 1993, с.91-111.

44. Шепелев В.А Проблема организации framework САПР СБИС. Системы и средства телекоммуникаций. - М., 1993, вып.5-6, с.4-17.

45. Стемпковский AJI., Шепелев В.А., Власов A.B., Лапинский B.C. Системная среда CADS: framework для глубоко интегрированных САПР. Системы и средства телекоммуникаций. - М., 1993, вып.5-6, с.18-23.

46. Стемпковский А.Л., Шепелев В.А. Представление топологических данных в интегрированной базе данных CADS. Системы и средства телекоммуникаций. -М., 1993, вып.5-6, с.24-29.

47. Шепелев В.А. Представление информации о технологических нормах в интегрированной базе данных CADS. Системы и средства телекоммуникаций. - М., ¡993, вып.5-6, с.29-32.

. 48. Шепелев В.А. Представление информации о конструкции кристалла в интегрированной базе данных CADS. Системы и средства телекоммуникаций. - М., 1993, вып.5-6, с.32-35.

49. Шепелев В.А. Представление информации об ограничениях

проектируемого фрагмента в интегрированной базе данных CADS. Системы и средства телекоммуникаций. - М., 1993, вып.5-6, с.35-37. .

50. Шепелев В.А. Представление информации о топологических фрагментах в интегрированной базе данных CADS. Системы и средства телекоммуникаций. - М., 1993, вып.5-6, с.38-44.

51. Шепелев В.А. Обработка геометрических данных в CADS. Системы и средства телекоммуникаций. - М., 1993, вып.5-6, с.50-53.

52. Попов С.Б., Шепелев В.А. Лингвистическое обеспечение системной среды CADS. Системы и средства телекоммуникаций. - М„ 1993, вып.5-6, с.54-59.

53. V.A.Shepelev, A.V.Vlasov. Implementation of the Conception of Flexible Integration within the Framework CADS. Proceedings of 3-rd International Design Automation Workshop (Russian Workshop'93). - Moscow, Russia, 1993, pp.90-103.

54. V.A.ShepeIev, A.V.Vlasov. Implementation of the Conception of Flexible Integration within the CADS Framework. Proceedings of the ACM/IEEE European Conference on Design Automation EuroDAC'93. - 1993, pp.366-371.

55. Шепелев В.А. Проблема организации framework САПР СБИС. Тезисы докладов Российской конференции с участием зарубежных ученых "Микроэлектроника-94". Часть 1. - М., 1994, с.117-118.

56. Стемпковский АЛ., Шепелев В.А., Власов А.В. Системная среда САПР СБИС. - М., "Наука", 1994, 251с.

57. Шепелев В.А. Метод автоматической генерации проектных задач. Тезисы докладов Второй международной научно-технической конференции "Микроэлектроника и информатика". - М., 1995, с.43-44.

58. Стемпковский А.Л., Шепелев В.А. Управление проектными задачами в САПР. Информационные технологии. - М., 1996, вып.1, с.25-30.

59. Шепелев В.А. Теоретический базис управления проектными задачами в САПР. Информационные технологии и вычислительные системы. - М., РАН, 1996, вып.2, с.87-95.

60. Шепелев В.А. Автоматическая генерация проектных задач в САПР. Информационные технологии. - М., 1996, вып.5, с.16-20.

61. V.A.Shepelev, S.W.Director. Automatic Workflow Generation. Proceedings of the ACM/IEEE European Conference oil Design Automation EuroDAC'96 - 1996, pp.104109.

62. Шепелев В.А. Метод автоматической генерации проектных задач. Труды Второй международной научно-технической конференции "Микроэлектроника и информатика". - М., 1996.

63. Шепелев В.А. Проблема создания системной среды САПР изделий зяектроники. Ашомашмппя проектирования. - М., ОИВТА РАН, 1997, вып.1(2), с.24-30.

7 > * ' • « \ лг

( / # ■ * 4

Научно-исследовательский институт систем автоматизированного проектирования радиоэлектронной аппаратуры и сверхбольших интегральных схем Российской академии наук (НИИСАПРАН)

На правах рукописи

Шепелев Владимир Алексеевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ПОСТРОЕНИЯ ОТКРЫТЫХ, ГЛУБОКО ИНТЕГРИРОВАННЫХ САПР СБИС

Специальность 05.13.12 - системы автоматизации

проектирования

Диссертация на соискание ученой степени доктора

технических наук

Москва - 1996

Оглавление

Введение..................................................................................................4

1 Проблема организации системной среды САПР....................................10

1.1 Формирование представлений о системной среде............................10

1.1.1 Поколения САПР.......................................................................10

1.1.2 Международная деятельность в области системной среды.....15

1.1.3 Современное представление о системной среде......................16

1.2 Представление и обработка проектной информации.......................17

1.2.1 Методы представления проектной информации.....................17

1.2.2 Методы обработки проектной информации............................24

1.2.3 Представление и обработка геометрической информации.....34

1.3 Управление проектной методологией.................................................40

1.3.1 Подключение прикладных программ........................................41

1.3.2 Проектные задачи.......................................................................44

1.3.3 Методы управления проектными задачами..............................45

1.4 Системная среда Falcon Framework....................................................54

1.5 Цель и задачи исследования................................................................58

2 Концепция гибкой интеграции..............................................................62

2.1 Суть концепции гибкой интеграции..................................................62

2.2 Гибкость в представлении и обработке данных................................64

2.3 Интегрированность представления проекта......................................65

2.4 Гибкость в сборке и управлении САПР.............................................67

2.5 Особенности концепции гибкой интеграции....................................68

3 Представление и обработка проектных данных.....................................71

3.1 Иерархия моделей данных...................................................................71

3.1.1 Структура иерархии моделей.....................................................71

3.1.2 Нижние уровни...........................................................................72

3.1.3 Гибридный уровень....................................................................73

3.1.4 Верхний уровень.........................................................................78

3.2 Манипулирование проектными данными..........................................82

3.2.1 Общая схема СУПД....................................................................82

3.2.2 Обработки данных на базовом уровне......................................86

3.2.3 Обработки данных на гибридном уровне.................................87

3.2.4 Обработки данных с использованием языка SQL...................90

3.2.5 Обработки данных через программный интерфейс.................97

3.2.6 Сравнительный анализ методов обработки данных..............101

3.2.7 Специализированные средства манипулирования.................104

Выводы......................................................................................................110

4 Интегрированное представление проекта............................................112

4.1 Метод глубокой интеграции данных................................................112

4.1.1 Предметные области схемы и топологии...............................113

4.1.2 Связь схемы и топологии.........................................................133

4.2 Интегрированная база данных..........................................................142

4.2.1 Структура интегрированной базы данных..............................142

4.2.2 Особенности интегрированной базы данных.........................143

4.2.3 Информационная модель.........................................................148

4.3 Сортировка геометрических данных.................................................153

Выводы......................................................................................................173

5 Подключение прикладных программ и управление ими........................174

5.1 Подключение пакетов прикладных программ.................................174

5.2 Математическая модель схемы задач................................................182

5.2.1 Граф проектной сущности.......................................................184

5.2.2 Граф простой проектной задачи..............................................188

5.2.3 Подключение сущности к простой проектной задаче...........196

5.2.4 Склеивание простых проектных задач....................................204

5.2.5 Граф схемы задач......................................................................211

5.3 Автоматическая генерация проектных потоков...............................216

5.3.1 Расширенный граф схемы задач..............................................217

5.3.2 Маршруты в схеме задач..........................................................227

5.3.3 Проектный поток и проектная история.................................233

5.3.4 Метод конструирования потоков............................................238

5.3.5 Оценка метода конструирования потоков..............................252

Выводы......................................................................................................254

6 Системная среда CADS.....................................................................256

6.1 Интегрированная база данных..........................................................256

6.1.1 Представление данных на гибридном уровне........................256

6.1.2 Информационная модель.........................................................277

6.2 Система управления проектными данными DDMS.......................297

6.2.1 Библиотека DTSWR..................................................................297

6.2.2 Библиотека DMU......................................................................299

6.2.3 Библиотека SMU......................................................................303

6.2.4 Библиотека SRV........................................................................304

6.2.5 Библиотека TRZ........................................................................306

6.2.6 Библиотека OMU......................................................................308

6.3 Геометрический процессор................................................................313

6.3.1 Общая характеристика..............................................................313

6.3.2 Функции....................................................................................315

6.3.3 Возможности GEOPROC.........................................................316

6.4 Система генерации проектных задач................................................318

6.4.1 Базовые возможности системы................................................318

6.4.2 Примеры генерации потоков...................................................321

Выводы......................................................................................................326

Заключение..........................................................................................327

Литература..........................................................................................331

Приложение: Акты внедрения результатов диссертации..........................344

Введение

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

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

Ситуация существенно изменилась в конце 80-х, когда из-за большого количества применяемых прикладных программ и сложных связей между ними встала проблема эффективной организации САПР. На этом этапе своего развития системы проектирования претерпели качественное изменение: из наборов каким-то образом связанных между собой прикладных программ они начали превращаться в мобильные и стройно организованные открытые системы, способные к настройке на особенности предметной области и на требования конечного пользователя, допускающие расширение функциональных возможностей за счёт сравнительно простого подключения новых прикладных программных модулей и обеспечивающие поддержку групповой разработки сложных интегральных схем коллективом проектировщиков. В основе современной открытой САПР, как правило, лежат сервисные программные средства, обеспечивающие инфраструктуру, или системную среду, помогающую быстро развивать и эффективно использовать САПР. Она поддерживает проектные данные и обеспечивает управление ими, предоставляет средства интеграции прикладных программ и управления проектными процедурами, обеспечивает интерфейс с пользователем. Такая системная среда получила название framework [1,2].

История эволюции системной среды САПР как отдельного направления исследований насчитывает всего около десяти лет. Первые промышленные framework, появившиеся на зарубежном рынке, были созданы фирмами Cadence Design Systems [3] и EDA Systems [4] во второй половине 80-х годов. Благодаря повышенному интересу к исследованиям в области framework со стороны не только поставщиков коммерческих САПР (Cadence, Mentor Graphics, ViewLogic и др.), но и крупных фирм -пользователей САПР (IBM, Motorola, INTEL, PHILIPS и др.), за последующие несколько лет были исследованы наиболее важные для промышленности аспекты организации системной среды, разработан ряд стандартов, ориентированных главным образом на сборку САПР из коммерческих программ, накоплен опыт создания открытых САПР на основе framework и сформирована начальная концепция системной среды.

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

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

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

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

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

• разработана новая многоуровневая организация средств управления проектными данными, поддерживающая доступ к информации на уровнях абстракции, предоставляемых иерархией моделей данных, и обеспечивающая гибкость в выборе средств обработки проектной информации, отсутствующую в известных СУПД;

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

• для представления проектной информации на семантическом уровне разработана оригинальная информационная модель предметной

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

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

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

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

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

Автор выносит на защиту следующие основные положения:

• оригинальную концепцию построения системной среды для открытой, глубоко интегрированной САПР СБИС. Концепция сформулирована как совокупность методов, обеспечивающих: гибкость в представлении и обработке проектных данных, интегрированность и эффективность представления проекта, гибкость в подключении прикладных программных модулей и управлении ими. Она позволяет сохранить достоинства и в значительной мере избежать недостатков современных подходов к построению САПР;

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

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

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

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

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

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

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

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

В первой главе дан обзор проблемы организации системной среды САПР.

Во второй главе сформулирована новая концепция организации системной среды для построения открытой, глубоко интегрированной САПР.

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

о о _

В четвертой главе предложе