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

ВОРОНЕЖСКАЯ ГОСУДАРСТВЕННАЯ ЛЕСОТЕХНИЧЕСКАЯ АКАДЕМИЯ

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

специальности

05.13.11 -"Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей"

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

Диссертация

на соискание ученой степени кандидата технических наук

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

Медведкова Ирина Евгеньевна

у Научный руководитель лауреат Государственной премии СССР доктор технических наук, профессор Межов В.Е.

Воронеж -1999

ВВЕДЕНИЕ........................................................................................................................5

1. ИССЛЕДОВАНИЕ ПРОБЛЕМ ИЕРАРХИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРИ ПРОЕКТИРОВАНИИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ..............................................11

1.1 Иерархическое моделирование сложных систем..............................................11

1.2 Исследование лингвистических средств иерархического поведенческого моделирования................................................................................................................16

1.2.1 Требования к лингвистическим средствам.......................................................16

1.2.2 Классификация языков проектирования и представление их с помощью формальных грамматик...............................................................................................18

1.2.3 Оценочные критерии проблемно - ориентированных языков.........................22

1.2.4 Краткий обзор и сравнительный анализ проблемно - ориентированных языков.............................................................................................................................23

1.3 Анализ методов преобразования исходной информации ...............................29

1.4 Классификация и анализ алгоритмов дискретного моделирования..............33

1.5 Исследование систем иерархического моделирования..................................36

1.6 ВЫВОДЫ......................................................................................................................42

2. РАЗРАБОТКА ЛИНГВИСТИЧЕСКОГО ОБЕСПЕЧЕНИЯ ИЕРАРХИЧЕСКОГО МОДЕЛИРОВАНИЯ.........................................................................................................43

2.1 Разработка лингвистических средств иерархического моделирования.......43

2.1.1 Разработка требований к лингвистическому обеспечению ИАМ............................44

2.1.2 Обоснование выбора проблемно-ориентированных понятий языка описания функционирования............................................................................................................50

2.2 Разработка системы целочисленного кодирования и хранения исходной информации..................................................................................................................... 57

2.3 Преобразование исходного описания проекта..................................................64

2.4 ВЫВОДЫ......................................................................................................................69

3. РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И ОРГАНИЗАЦИОННОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ ИЕРАРХИЧЕСКОГО МОДЕЛИРОВАНИЯ................70

3.1 Разработка требований и основных принципов организации системы иерархического моделирования..................................................................................70

3.2 Обоснование схемы компиляции моделирующего модуля............................73

3.3 Особенности построения и организации моделирующего модуля...............75

3.4 Разработка структуры имитатора и процесс, его компиляции........................77

3.4.1 Алгоритм формирования дерева глобальных обявлений имитатора.........80

3.4.2 Анализ алгоритма ПДИ.......................................................................................88

3.5 Разработка алгоритма моделирования ................................................................92

3.6 Разработка структуры данных моделятора..........................................................96

3.7 Разработка алгоритма формирования очереди будущих событий...................99

3.8 Организация временного круга............................................................................100

3.9 Моделирование процессов....................................................................................102

3.9.1 Методика активизации и планирования процессов................................................103

3.9.2 Организация изменения состояния процесса..........................................................104

зло выводы..................................................................................................................110

4. ПРОГРАММНЫЙ КОМПЛЕКС СИСТЕМЫ ИЕРАРХИЧЕСКОГО АЛГОРИТМИЧЕСКОГО МОДЕЛИРОВАНИЯ И ОСОБЕННОСТИ ЕГО ПРИМЕНЕНИЯ..............................................................................................................113

4.1 Общая структура пакета ........................................................................................114

4.2 Организация сервисного обслуживания............................................................117

4.3 Программное обеспечение работы с базами данных.......................................119

4.4 Программное обеспечение компиляции имитатора........................................124

4.5 Реализация инициализации проекта.................................................................132

4.6 Результаты опытной эксплуатации и внедрение пакета................................134

4.7 Методика использования пакета........................................................................137

4.8 ВЫВОДЫ....................................................................................................-...............142

ЗАКЛЮЧЕНИЕ...................................................................................................................144

СПИСОК ЛИТЕРАТУРЫ.............................................................................................146

ПРИЛОЖЕНИЕ А. ПОЛНЫЙ СИНТАКСИЧЕСКИЙ ГРАФ ЯЗЫКА АЛОС..........154

ПРИЛОЖЕНИЕ В. ПРИМЕР ОПИСАНИЯ НА ЯЗЫКЕ АЛОС УСТРОЙСТВА КОДИРОВАНИЯ ИНФОРМАЦИИ, ПЕРЕДАВАЕМОЙ СПУТНИКУ.....................160

ПРИЛОЖЕНИЕ С. ПОЛНЫЙ СИНТАКСИЧЕСКИЙ ГРАФ ЯЗЫКА УПРАВЛЕНИЯ................................................................................................................165

ПРИЛОЖЕНИЕ В. ПРИМЕР ИМИТАТОРА, ГЕНЕРИРУЕМОГО ПРОГРАММОЙ СБОРКА...........................................................................................................................170

ПРИЛОЖЕНИЕ Е. АКТ ВНЕДРЕНИЯ........................................................................173

Список сокращений

БД - база данных

ВС - вычислительные системы

НАМ - иерархическое алгоритмическое моделирование

КПМ - комплекс программ моделирования

КС - контекстно-свободные (грамматики)

ЛО - логическое описание

МК К - модуль коммутации компонентов

ММ - моделирующий модуль

ОБС - очередь будущих событий

ИДИ - (алгоритм) построения дерева идентификатора

ПП1Е - порождающие программные единицы

СЛКС - список справочников линий контрольного списка

ТНС - таблица нетерминальных символов

Введение

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

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

• не подлежат развитию, необходимость в котором неизбежно возникает в процессе проектирования;

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

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

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

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

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

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

• приближение лингвистических средств к естественной терминологии пользователя.

Диссертационная работа является частью комплексной работы, проводимой в рамках важнейших работ департамента электронной промышленности Миноборонпрома РФ и плана создания новой техники НПО "Электроника".

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

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

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

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

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

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

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

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

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

Научная новизна. В диссертации получены следующие основные результаты, характеризующиеся научной новизной:

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

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

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

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

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

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

1) каждому событию соответствуют два типа активностей: процессов и линий;

2) активности процесса реализуются с учетом трех факторов: состояния процесса, предиката, определенного на множестве выводов и деклараций модели, и квалификатора, определенного на множестве {список линий, задержка, синхронизатор};

3) возможна инициация активности процесса параллельными процессами модели;

4) список последователей линии определен на объединенном множестве процессов и линий.

Практическая ценность'. На основе полученных результатов разработан пакет программ иерархического алгоритмического моделирования (ПРИАМ). Пакет позволяет осуществлять нисходящее проектирование системы, содержащей произвольную комбинацию уровней абстракции, и предоставляет при этом широкие возможности по отладке. Анализируемый проект может содержать до 5000 линий, до 3000 элементов произвольной сложности с максимальным числом выводов каждого элемента 200; а описание функционирования на любом уровне абстракции

составляется непосредственно разработчиком на языке описания аппаратуры АЛ ОС с использованием привычной терминологии. Количественные и качественные характеристики пакета не уступают параметрам аналогичных западных пакетов и полностью удовлетворяют современным задачам проектирования. Пакет ПРИАМ может быть поставлен на любой ЭВМ с операционной системой, поддерживающей виртуальную адресацию страниц. Конкретно пакет реализован на ЭВМ семейства VAX (фирма DEC) с операционной системой VMS и на ЭВМ семейства PC (фирма IBM) с операционной системой UNIX и совместимых с ними. Объем памяти для хранения пакета - 1,5 Мгб: объем памяти для работы определяется проектом, но не менее 0,5 Мгб.

Реализация результатов работы. Научные результаты, изложенные в диссертации, реализованы автором в ходе выполнения госбюджетных НИР (шифр "Турнир-3") и ОКР (шифр "Турнир-4"), выполненных в ОКБ при з-де "Процессор", результатом которых явилось создание пакета ПРИАМ. Данный пакет внедрен на ряде предприятий электронной промышленности, в частности, в ОКБ завода "Процессор" (г. Воронеж) и в НИИРП (г. Москва), где используется при проектировании БИС и блоков ЭВМ, а также при проектировании заказных схем предприятиями г. Свердловска; кроме того включен в учебный процесс на кафедре САПР и И С ВГТУ.

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

устройств и автоматизированных систем на персональных ЭВМ" (Воронеж, 1991 г.); научно-технической конференции " Автоматизированное проектирование и схемотехника МДП СБИС" (Новосибирск, 1991 г.); Между народной научно-технической конференции "Методы и средства оценки и повышения надежности приборов, устройств и систем" (Пенза, 1995 г.); М ежду народной научно-технической конференции "Актуальные проблемы анализа и обеспечения наглядности и качества приборов, устройств и систем" (Пенза, 1996 г.); II Республиканской электронной научной конференции "Современные проблемы информатизации" (Воронеж, 1997 г.); семинарах кафедры математического моделирования технологических систем ВГТА 1996, 1997, 1998 гг.; семинаре кафедры автоматизированных и вычислительных систем ВГТУ 1998 г.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, пяти приложений и списка литературы, включающего 81 наименование. Содержание работы изложено на 145 страницах машинописного текста, иллюстрировано 30 рисунками и 4 таблицами.

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

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

1.1 Иерархическое моделирование сложных систем.

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