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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОННОЙ ТЕХНИКИ (технический университет)

На правах: рукописи . Экз *______

ВАРАНКИН НИКОЛАЙ ВАСИЛЬЕВИЧ

РАЗРАБОТКА АДАПТИВНОЙ ИНТЕРАКТИВНОЙ ОБОЛОЧКИ РЯ ЗАКАЗНЫХ САПР

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

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

А

и.

1

Москва - 1993 г

Работа выполнена в Московской государственном институте электронной техники.

Научный руководитель:

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

Ведущая организация:

доктор технических наук, профессор А. Г. Соколов

доктор технических наук, Профессор А. Е, Костин кандидат технически* наук В. П. Золотое

НИИ "Аргон"

Защита состоится "__" _____________ 1994 г, на заседании

специализированного совета Д.053,02.01 Московского государственного института электронной техники (103498, Москва).

С диссертацией можно ознакомиться в библиотеке МГИЭТ. Автореферат разослан "____"____________ 1994 г.

Ученый секретарь специализированного совета

к.т.н., профессор Н.6.Воробьев

/П

ВВЕДЕНИЕ

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

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

Для достижения поставленной цели в работе решаются следующие сноеные задачи:

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

2. Анализ графических пакетов и разработка спецификации буфер-эго интерактивно-графического интерфейса.

3. Анализ систем управления динамической памятьо и разработка Зобщенной модели с целью определения унифицированного набора про-рами управления памятьо.

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

»

5. Проверка разработанных концепций, методов и алгоритмов на

примере графического редактора для топологического проекгировани заказных СБИС.

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

Новые научные результаты и основные положения, выносимые н. защиту:

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

2. Инвариантные к вычислительным средам структуры данных инте рагтивно-графического интерфейса, уменьшавшие количество функци! управления интерфейсом.

3. Алгоритмы и схема передачи управления в приложении Windows реализующие интерактивно-графический интерфейс, что позволяет ис пользовать стандартное построение прикладных программ для сред|

: Microsoft Windows(NT).

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

5. Оригинальная структура компактной графической базы данных, ориентированная на обработку иерархически организованных данных.

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

7. Оригинальные алгоритмы контроля проектных норм топологии н; 1 основе разработанной СУБД, не требующие развертывания иерархии t • одноуровневое представление.

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

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

Работа выполнена в инициативном порядке.

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

Результаты диссертационной работы внедрены на предприятиях: НИИ Научный Центр, Российский НИИ технологий микроэлектроники, в/ч 11135 и СП ВБС/вШсои. В виде учебной САПР результаты работы внедрены в учебный процесс в Московском государственном институте электронной техники.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научно-технической конференции "Автоматизированноз проектирование радиоэлектронной аппаратуры", г. Каунас, Литва, 1992 г.

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается теоретические основы построения интерфейсов заказных САПР (ЗакСАПР). Анализируится особенности интеграции современных САПР на примере оболочек GARDEN, TeamNet, Falcon, Nelsis, Cadance и стандартов CFI (CAD Framework Initiative - инициатива no оболочкам САПР). Показано, что в условиях формирующегося стандарта на оболочку САПР электроники концепция модульных заказных САПР [7] позволяет аффективно использовать ранее разработанное программное обеспечение.

6 то время как в рамках оболочек САПР успешно решаются задачи комплексирования программных средств, для самой ЗакСАПР должны выполняться следующие обязательные требования: 1) ЗакСАПР должна функционировать в рамках той Э8М и ОС, в среде которых работает оболочка; 2) форматы входных-выходных данных должны согласовываться с БД оболочки.

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

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

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

МЕТОДИКА ПРОЕКТИРОВАНИЯ

ПРОГРАММЫ ЗАКАЗНОЙ САПР

ИНТЕРАКТИВНО-ГРАФИЧЕСКИЙ ИНТЕРФЕЙС

ГРАФИЧЕСКАЯ СУБД

ФАЙЛОВЫЙ СЕРВИС

УПРАВЛЕНИЕ ПАМЯТЬЮ

БАЗОВЫЕ ГРАФИЧЕСКИЕ СРЕДСТВА

ОПЕРАЦИОННАЯ СИСТЕМА

АППАРАТНЫЕ СРЕДСТВА

Рис. 1

Структура оболочки заказной САПР

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

котором написана САПР. В качестве математической модели системы может использоваться представление е виде направленного графа 6= {в, О, в котором узлы э соответствует подсистемам, а ребра f -связям. В основе такого представления лежит аппарат конечных автоматов или машин Тьоринга.

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

коэффициенты расположить е матрице К - [Г¡у], то суммарную трудоемкость можно выразить как норму этой матрицы:

нн

о = И = £!>«;■ г<>*° <»

1=1

где Ги - трудоемкость разработки' модуля; Г^, 1 & ] -трудоемкость взаимной увязки модулей 1 и

Точного определения метрики Гц не найдено. Условимся считать,

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

. - 7 -

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

Используя классический подход по построению заказных САПР [7], требуется учесть Р вариантов для I программ, т.е. в общем случае вариантов. Для уменьшения (1) в работе [8] было предложено минимизировать функциональный состав системно-зависимых компонент. Это было вполне оправдано при низких требованиях к диалоговому интерфейсу того периода. 8 настоящее время при разработке ПО САПР /добные процедуры взаимодействия с программой рассматриваются как иощный фактор автоматизации. Однако большая трудоемкость програм-иирования диалога и его системно-зависимый характер приводят к существенному возрастанию затрат на разработку заказных САПР, Это объясняется тем, что все большее число модулей задействуется в диалоговых процедурах, носящих отпечаток вычислительных платформ. В результате теряется основное преимущество подхода ЗакСАПР, когда изменениям или замене подвергается небольшое число модулей.

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

Для математической постановки задачи составим матрицу трудоемкости Я - [Г^], в которой учтем влияние интерфейсного ПО, еео-

дением дополнительного столбца и строки (индекс для неблочногс вида).

К,] «

а*

лСАПР

я,

ст

я

инт

я„

я я:

О О Я;

р

зав

р

аи Р ВС

(г;

Охарактеризуем вновь введенные элементы,

ЯсАПР = С0Л51 отражает затраты на разработку "абстрактного" САПР, 1 Р

Я

ВС

= COПSt в силу того, что вычислительные системы берутс:

"как есть". Я^ отражает затраты на использование интерфейсны:

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

ЯИ

сз к Р различным средам. Я^т выражает затраты на обобщение исполь зуемых в 1 программах возможностей вычислительных сред и выработк

—Р

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

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

ЗАПР по [7]:

т, = т! л Я

р

зав

(3)

я

ад

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

"напрямую" к вычислительной среде и равна Г т, 2) трудоемкость разработки интерфейсов одинакова для различных сред и равна Г.„ и

Сл

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

Га„ <

№-ФЦ+Ы)

» 1г -

исп

р

яг II + ,

с г |Г 'к

(4)

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

предложенного подхода.

В главе 2 рассматриваются интерактивно-графические средства оболочки ЗакСАПР - одной из самых важных ее частей. Проведенный в работе анализ показывает, что существующие графические пакеты и оболочки не обеспечивают полного охвата вычислительной техники и операционных систем, используемой отечественными предприятиями и НИИ. Более того, в последние годы наблюдается тенденция динамичного развития аппаратных и программных средств машинной графики, что привело te появлению ряда несовместимых графических пакетов, среди которых следует выделить: 1) X Window System - графическая среда для машин под управлением операционных систем (ОС) UNIX или VMS; 2) Microsoft Windows (WindowsKT) - графическая среда для персональных и RISC-компьютеров; 3) многочисленные пакеты графических программ (ПГП), не требующие многозадачной ОС: GKS, GL, GRAF0B, MFB (Model Frame Buffer), графика для ЭВМ типа Apollo и IBM PC/AT, а также многие другие.

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

i

' различных пакетов графических программ (ПГП) на уровне некоторого фиксированного программного интерфейса. Отметим, что это решение в корне отличается от традиционной стратегии проектирования ПГП, : ориентированной на обмен данными непосредственно с устройством или сервером, вторая решаемая задача обусловлена■современными требованиями к разработке программного обеспечения и заключается в обеспечении открытости, адаптивности и системной независимости. Дополнительным требованием выступает поддержка национальных языков для прикладных программ:

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

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

должна подвергнуться сумма |ЯИ | + |. Заметим, что влияние Ян

уменьшается по мере увеличения количества поддерживаемых платформ Р по причине однократности затрат.

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

платформы. Соответствующая подматрица затрат Я* имеет размерность

аИ

п*р, где п - количество модулей в интерфейсе, ар- количество задействованных модулей (средств) вычислительной среды.

• Уменьшение числа функций п приводит к пропорциональному умень-_ ^ _ р

шению нормы матрицы паи и, соответственно, пан. Также уменьшается

размерность матрицы но при этом нельзя с той же уверенностью

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

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

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

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

такого подмножества V! С IV, которое инвариантно для любого опыта (эксперимента, реализаиии и т.п.) из множества опытов О ~ Путем последовательного применения метода можно до-

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

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

Для решения этой проблемы в данной работе предложено осуществить двойную буферизацию описания для все* ресурсов, а в качество инварианты использовать целые числа - индекс (класс) ресурса и ин1

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

1) Появляется возможность отделить установку (активизации) ресурса от его определения, а формирование ресурса - от исполнительного кода программы.

2) Функции запроса и установки предельных и текущих значений индексов становятся во многом инвариантными к реализации.

Систекно-завнсиныа данные

Схема двойной буферизации описания ресурсов

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

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

Обцее представление:

[ <форм«т> <дямне> <кояичество> ... ] <даннм>

Цвет:

[ООО <к(мсныИ> <ве*бниЯ> <синмй> ]

Шрифт:

[ <фор*вт> <мина> 258 <»ир.> <»нс.> <б/стр.> <бам> <подч.> ]

<симвод к 0> ... <символ К 265>

Таблица перекодировки:

Запивка и штриховка:

[ <фсрмвт> <мин«> 1 <*мр.> <вис.> ] <двнныв>

Курсор:

[ <форм»т> <дяин«> 2 <»мр.> <вис.> <Х> <Т> <цовт> <фон> ]

<д»жие ц»вта> <д»ннм фона>

Рис. 3

Отображение логического представления ресурсов на обобщенную битовую кзрту

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

Размер матриц по каждому из измерений есть параметры, характеризующие соответствугшгí ресурс. Эти параметры битовой карты (БК) положены в основу обобщенного описания. Для ряда ресурсов могут понадобиться дополнительные параметры. Обобщая эти требования, установим, что в описании ресурсов входит как БК, так и список параметров (рис.3). Для удобства эти параметры объединены в заголовок фиксированного формата.

Особое внимание было уделено разработке Н-интерфейса для среды Windows(NT), т.к. программирование для Windows требует полного отказа от традиционной концепции программирования с явной передачей управления от одной подпрограммы (функции) к другой. Автором разработана модифицированная схема передачи управления в приложении Windows, с помощью которой удалось сохранить обычный порядок передачи управления в ранее разработанной или разрабатываемой прикладной программе. С точки зрения программиста управление по-прежнему передается от вычислительной среды в функцио main(), где после инициализации Н-интерфейса можно выполнять рисование, запрос событий и другие действия согласно программируемым алгоритмам. В основе модифицированной схемы передачи управления пежит разбиение и перенос частей стандартных функций WinMaínO и WndProcO по функциям Н-интерфейса.

Как показала практика, наиболее эффективный вариант реализации интерфейса - отдельный программный код для каждой графической платформы. Необходимые модули компилируются и подключаются к программе обычным для систем программирования образом. Все имеющиеся на сегодня варианты интерфейса написаны на языке программирования Си. Разработаны варианты для X Window System, Microsoft Windows (NT), Apollo и дпя различных систем программирования для MS-DOS (Microsoft C/C++ и QuickC, Borland C/C++, Zortech C/C++).

Также в гларе 2 оассмотрены согтае и алгоритмы функциоечрпвч-

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

Глава 3 посвящена проблемам управления динамической памятью (ДП), Системно-независимое управление ДП необходимо для обеспечения совместимости разрабатываемых программ с. различными вычислительными средами. Стандартная для ОС UNIX и языка Си схема претерпевает сильные изменения для ЭВМ IBM PC/AT под управлением MS-DOS с поддержкой расширенной памяти и в среде Microsoft Windows. Это означает не только синтаксические, .но и семантические различия в функциях. Для решения проблемы была сформирована обобщенная модель управления ДП. Внутреннее единство и непротиворечивость модели гарантируют стабильность программного интерфейса.

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

Для решения проблемы перемещения блоков необходимо исключить зависимость описания блока памяти от адреса. Для этого переда-

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

некоторая инвариантная к перемещению блока величина п. Образуются тройки чисел (п,э,2) или (п,з,е) - множество "описателей" блоков памяти. При изменении начального адреса блока инвариантный индекс остается неизменным. Определение памяти может быть записано в виде:

М = { {%),{%},{(п.Ъ.гъ)} },

(5)

В* и В' =М, Ва п В( =0

где N - количество адресуемых элементов (байт) ДП, причем зир(П= =зир(]')=М; В - блок памяти, верхний индекс "а" использован для

занятых блоков, а "Г' - для свободных, - инвариантное

описание к-го бпока.

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

где

Ва =Вахи#м, ВахпАав =0

Функционирование системы управления памятыо в терминах теории множеств можно охарактеризовать как выполнение операций деления и объединения подмножеств (блоков). Объявление только трех типов блоков порождает шесть возможных операций по перемещение блоков, изображенных на рис.4.

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

Свободные блоки

Фиксирован блоки

Перемещаемые блоки

Рис. 4

Типы блоков памяти и операции управления

^ дат 1ос¡с ^ах ип1ос^ ^ат fre^ ^

1 (7.1)

ßf aiio^ ßax fre^ gf

ßf aiio^ ßax uniocjc ßam ioc{c ßäx fre| gf

(7.2)

В данной работе предлагается 2 набора Функций, реализующих управление динамической памятью на основе модели: управление низкого уровня для сложных программ и эмуляция функций mallocO и free() для простого управления небольшими объемами памяти Использование низкоуровневой схемы при разработке программ в ОС UNIX или в стандартной (до 640 кбайт) ОС HS-DOS выглядит достаточно необычно, однако гарантирует переносимость программы. Точная спецификация для языка Си основного набора функций определяет тип данных для индекса, константу - нулевой индекс и 6 новых Функций.

В отличие от известных моделей, используемых для описания управления памятью в рамках аппаратных средств, в данной модели использован уровень абстракции на уровне отношений, возникающих между прикладной программой и ее системным окружением. За счет этого удается сократить число рассматриваемых аспектов и описать операции управления ДП, различные для систем программирования в ОС UNIX, HS-DOS и среде Microsoft Windows, как операции с множествами блоков памяти. Каждая из перечисленных систем реализует только часть ' из этих операций, остальные могут быть доопреае"ены на основе модели

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

образом:

1) Проанализировать частоту использования структур данных, для которых используется ДП. При необходииости модифицировать алгоритмы, настроив их на динаиическое использование небольших объемов данных.

2) Использовать двухуровневую схему доступа (индекс-адрес) для динамически используемых данных.

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

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

В главе 4 проведен анализ внутренних структур оперативных баз данных (БД) графических объектов, используемых в САПР электроники. Эти БД служат ядром многих..программ САПР и поэтому могут бить отнесены к элементам универсальной оболочки ЗакСАПР. Основные" классы управляющих структур данных (УСД) и оценки времени поиска произвольного элемента БД безотносительно к графическим приложениям были рассмотрены еще Мартином, однако современные графические БД используют более сложные решения. Следует отметить: двумерный массив ячеек (2-0 bin structure), R-дерево, квадро-дерево, k-D дерево (бинарное дерево), тайповую структуру (cornec stiching - сшивание углов).

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

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

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

1. БД должна обеспечивать минимальную компактную структуру УСД для обработки больших иерархических проектов.

2. Алгоритмы СУБД должны быть адаптивными к параметрам, определяющим структуру БД.

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

При разработке БД на основании вышеперечисленных критериев был принят во внимание тот факт, что организация БД по принципу квздро- или МхМ-дерева обеспечивает наиболее оптимальное сочетание высокой скорости выполнения запросов с небольшими затратами памяти на УСД. Это позволяет строить достаточно эффективные САПР на базе вычислительной техники среднего класса и даже на персональных ЭВМ типа IBM PC/AT. Разработанная БД основывается на принципах НуМ дерева, но имеет ряд принципиальных отличий.

1. Критерий минимальной длины списка объектов в ячейке ^'Г.Д заменен критерием минимальных габаритов ячейки., Детернитюогпннопть размеров ячеек УСД позволяет упростить вычисление их гябтнтор, i также сэкономить память за счет отказа от хранения пчетчига опьек-

тов в ячейке, либо, при отсутствии такого, исключить подсчет количества уже существующих в списке объектов.

2. Чтобы исключить перебор и анализ уже внесенных обьектов при динамической модификации дерева УСД, обьекты сразу вводятся в минимальную покрывающую ячейку. Такое . решение позволяет сократить время включения нового ближлежащего объекта, т, к. включение новых экземпляров происходит в (почти) готовую структуру. Появляется возможность решить проблемы Q-D деревьев, возникающие при разделе списка ячейки на списки подъячеек при сильной близости обьектов. С другой стороны, исключается проблема включения в БД объектов, попадаыцих на границы ячеек - они просто включаются в ячейку приемлемого верхнего уровня, ß сделанной реализации БД остается лишь одна "резиновая" ячейка на все дерево, в которую включаются обьекты, пересеченные осями координат.

УРОВвНЬ

и

уровень

Рис.5

Уни&ерсальный элемент структур данных

Для упрощения структур данных и, соответственно, алгоритмов обхода дереээ принято решение об организации иодьячеек е виде списка, 'яо позволяет зафиксировать правила обхода дерева УСД и

устанавливать произвольные параметры БД. Выбор неравных сторон ячеек особенно актуален для информации с выраженными канальными свойствами, например, для матричных СБИС. В результате каждая ячейка содержит три указателя: один на ячейку данного уровня, один на список подьячеек и один на список объектов, не вошедших в ячейки нижнего уровня (рис.5). Такая структура позволяет экономить память за счет создания не МхМ подьячеек, а только необходимого их количества. Сравнивая представленные в литературе алгоритмы обхода дерева УСД, можно заметить, что большинство из них в явном или неявном виде включает проверку критерия поиска для всех ячеек УСД данного уровня. 9 итоге это эквивалентно просмотру полного списка в разработанной БД, Более того, т.к. БД не вклочает пустые УСД, длина списка может быть короче максимальной, сокращая время поиска.

4. Организация дерева УСД в виде связанных списков позволяет повысить быстродействие апгоритмов за счет отказа от рекурсии, предлагаемой в литературе для перехода на следуощий уровень иерархии дерева УСД- Так как в большинстве ЭВМ для хранения контекста используется стек, могут возникнуть ситуации его переполнения при большой глубине рекурсии для машин класса IBM PC/AT, где стек вместе со статическими данными не может превышать' 64-х килобайт для многих коммерческих компиляторов■ В осноее предложенного алгоритма лежит использование стека указателей на ячейки - единстрен-ного изменявшегося параметра. Максимальная глубина этого ст-зкч легко оценивается как 1од»(Макс. размер ячейки / Минин ра?мег> ячейки), чтг> пвппетг.ч небольшим значением. Данный подход позволяет срободно пользоваться рекурсивным вызовем процедур, при проходе иераруии высшего порядка - иерархии проектнух единиц.

5. Основные метояи ускорения зпговигмов обход л flip<?pri УСД базируются на избирательном, вычислении критериев гесметриче-.кого по-

иска. Они используют детерминированность изменения размеров ячеек УСД в дереве и поэтому применимы ко всем деревьям класса ИхМ. В отличие от известных методов, в БД применена троичная логика для вычисления результата пересечения двух прямоугольников (поиска и габаритного): 0 - отсутствие пересечения; 1 - габариты УСД полностью покрываются прямоугольником поиска; 2 - все -остальные случаи пересечения. Этот метод позволяет разрешить дилемму, свойственную многим схемам БД, когда параметры базы данных для быстрого локального поиска не обеспечивают высокой скорости для глобальной обра-1 сотки объектов, и наоборот.

Эффект, получаемый описанным выше методом, обусловлен тем, что имея некоторую обобщенную информацию, можно принять решение об упрощенной проверке критерия. Обобщая и развивая этот подход дальше, можно выделить другие наиболее часто используемые характеристики объектов, которые следует накапливать в управляющих структурах данных. Эти признаки в сильной степени определяются спецификой приложения базы данных. В разработанной БД, больше ориентированной на проектирование СБИС, дополнительно к охватывающему прямоугольнику используется информация о типе объекта и признаки состояния объекта. Имея подобную информацию для каждой отдельно взятой ячейки в иерархически организованном проекте, можно легко накапливать необходимые признаки с учетом привязанных ячеек, и причем на всю глубину иерархии. Для "прозрачной" выборки это дает 1,5-2 -кратный эффект по скорости выполнения запросов к БД.

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

зоссийского парка компьютеров - машин ряда VAX и младших моделей ЕВМ PC/AT - вычисления дробей дают выигрыш, однако для перспективных современных ЭВМ на базе RISC-процессоров (Magnum, Iris Indigo, Sparc) вычисления следует выполнять с плавающей точкой.

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

1) экономия памяти эа счет использования БД "как есть", без эазвертывания информации в одноуровневое представление;

2) быстрый поиск соседних фигур, основанный на свойствах БД;

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

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

Как показапи практические испытания, метод хорошо рэбогзет цаже на персональных ЭВМ, Контроль 60 правил для аналого-цифровой зхемы площадью 3 кв. мм (3 мкм проектные нормы, КМОП) выполнялся п течение 5 мин. на ,ЧВМ IBM PC/AT-48fi.

В главе 5 опи«.ан графический редактор, названный Uyo'i«. Uj» lows, разработаный с целью экспериментальной проверки все* пр«п

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

Редактор Layout Windows написан на языке С и содержит около 25000 строк исходного текста. Редактор использует описанную выше СУБД многослойного типа, что обеспечивает хранение и обработку элементов одного класса в одном "срезе" базы данных. Это, во-первых, упростило и ускорило ряд алгоритмов, в частности рисование. Во-вторых, многослойная структура обеспечивает наиболее естественную селекцию слоев по признакам "активный" - "видимый" - "все слои", которые организуется вне БД. В качестве параметров базы данных используются размеры минимальной ячейки УСД и коэффициент размножения ячеек, одинаковый по обеим осям координат. Подсистема контроля проектных норм функционирует в ручном или автоматическом режиме,

Сравнение с редакторами Chipgraph, К 1С. и Пульт показало лучшие скоростные характеристики при локальной выборке данных.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

7. Разработаны оригинальные алгоритмы контроля проектах н^рм топологии на основе разработанной СУБД, не требующие га?Р<?рП!В.1и»я иерархии в одноуровневое представление.

8. Разработанные методы, алгоритмы и интерфейса примерны f графическом редакторе топологии Layout Windows, иг попы^'?'«'. »<. г составе САПР СБИС, микросборок и печатных пг.ат,

- 28 -

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

1. В.В. Бравов, Н.В. Варанкин, Л.Л. Савченко, "Реалии и перспективы развития графических редакторов для IBM PC". СБ. научных трудов МИЭТ. САПР СБИС: проблемы автоматизации. М., 1991.

2. Варанкин Н.В., Кораблев И.С., Орсич И.А,, Соколов А.Г. Применение интеллектуальных систем для проектирования элементной базы БИС. В сб. науч. трудов МИЭТ "САПР СБИС: Проблемы автоматизации", И, МИЭТ, 1991.

3. Варанкин Н, В.., Орсич И. А., Соколов А. Г., Шумилов в. в. Комплекс программ, многоуровневого моделирования фрагментов КИОП БИС на ПЭВМ IBM PC, В сб, науч. трудов МИЭТ "САПР СБИС: Проблемы автоматизации", И, ИИЭТ, 1991, ,

4. Н.В.Варанкин, А.Г.Соколов, ОГ.Тютюкин, Адаптивный графический интерфейс обеспечивает переносимость программных средств. Материалы конф. "Автоматизированное проектирование радиоэлектронной аппаратуры". Каунас, июнь 1992.

5. Н.В.Варанкин, А.Г.Соколов, Высокоскоростная графическая БД для САПР электронных' изделий. Материалы конф. "Автоматизированное проектирование радиоэлектронной аппаратуры". Каунас, июнь 1992.

6. Н.В. Варанкин, А.Г. Соколов, "Система проектирования топологии заказных БИС". Электронная промышленность, И 3, 1993.

Справочная литература:

7. Соколов А.Г,, Бравов В.В., и др, Гибкие системы автоматизированного схемотехнического проектирования. Электронная промышленность, №4, 1987.

8. Бравов В.В. Исследование и разработка алгоритмов управления проблемными модулями и обработки информации в интерактивных системах проектирования фрагментов СБИС. Диссертация ..'. ученой степени канд. технич. наук. - И., МИЭТ, 1986.

Огпетянр & тип. ИГНАТУ U^lX м>