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

Г":" ОД 2 5 СЕН ..ЮГ,5

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

КУЛАГИН Владимир Петрович

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

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

' АВТОРЕФЕРАТ

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

!И«км-1У95

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

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

■ - доктор технических наук, профессор И. П. НОРЕНКОВ.

- доктор технических наук, профессор А.Н. КАРМАЗИНСКИЙ.

- доктор технических наук, профессор А.Ю. ТАТАРНИКОВ

Ведущее предприятие:

Научно-исследовательский институт "Квант"

Зашита состоится " ^ " 1995 г. в /У часов на

заседании Специализированного Совета Д063.68.03 ¡Московского государственного института электроники и математики (технического университета) (109028, Москва, Ж-28, Б.Вузовский пер., д.3/12).

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

Ученый секретарь Специализированного Совета, к.Т.Н., доцент ЛГ п.Л. ИЖВАНОВ

¿Г*

Подписано к дечага 12.09.95 Зак.ЭЗ Пр. 100 Объём 2 д.л.

МГИШ, Москва, М. ¡ионерская ул., 12

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТи

а

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

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

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

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

' - выработка ряда гипотез, касающихся структур подсистем, из которых будет состоять проектируемая ВС;

- формирование из полученных подсистем альтернативных структур-кандидатов:

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

В силу НР-слокности задачи синтеза альтернативных вариантов проектируемой ВС, автоматизация структурного и параметрического синтез« является трудно реализуемой даке с использованием систем. проектирования, реализованных на высокопроизводительных ЭВМ, Поэтому большинств( из существующих подходов.к решений задачи синтеза носят эвристически! характер и предусматривают включение в контур машинного прогчтированш человека. . .

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

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

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

- строить простые методы отображение результатов исследования от дельных подсистем на общую модель ВС;

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

Одним из таких является подход, основанный на тензорных метода) ^Впервые' данный подход систематически изложил американский иннеж _ Г. Крон, который использовал тензорные метода при анализе элёктричесю

яаиин. В дальнейшем тензорные методы развивались как в работах отечественных ученых (в области расчета задач электродинамики - A.B. Гапо-нов-Грехов, В.п. Веников, И.П.Копылов и др., в области исследования экономических систем - А.Е.Петров, в области проектирования баз данных и систем искусственного интеллекта - Л.Т.Кузин, А.Е.Арменский, для построения и анализа -лгоритмов обработки структур данных интересный подход предложен в работах В.П.Панферова), так и в работах зарубежных ученых (исследование инвариантов - 0. Веблен» исследование сложных систем по частям - X.Хепп, Д.Цуганский, использование тензорных методов для решения задач символьной обработки - Дж. Орр).

Вышеизложенное позволяет составить представление о состоянии теории и практики проектирования структур параллельных ВС. Оно сводится к следующему:

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

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

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

В соответствии с по ставленной целью основными 'задачами работы являются: ■ ' '

- обоснование выбора сетевых моделей для формализованного описания и тензорного подхода к проектированию структур параллельных ВС;

- формулировка задачи проектирования структур параллельных ВС в терминах тензорного исчисления сетевых моделей;

■ - разработка нового формализма для исследования сетевых моделей, основанного на теории структур; '

- разработка подхода к анализу и синтезу сетевых моделей, основанных на тензорном исчислении;

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

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

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

Достоверность результатов подтверждена математическими выводами, моделированием на ЭВМ. промышленной проверкой разработанных средств.

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

- обоснование эффективности использования тензорного подхода и сетевого представления моделей структур параллельных ВС;

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

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

- разработку нового формализма - структуры сетей Петри (СП) - для исследования сетевых моделей;

- разработку нового подхода к анализу и синтезу СП-структур, основанного на тензорной методологии;

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

Основные положения, выносимые на защиту, заключаются в следующем.

1. На основе обобщения существующего опыта и проведенных исследований разработаны теоретические основы тензорного исчисления сетевых моделей структур параллельных ВС. В рамках теоретических основ:

- сформулирована задача проектирования структур параллельных ВС в терминах тензорного исчисления сете"ых моделей;

- разработаны оригинальные методы и языковые Средства формализованного описа"ия сетевых моделей структур ВС;

- разработан новый ф.рмализм для исследования сетевых моделей -структуры гетей Петри;

- доказаны теоремы, позволяют!": построить эффективные алгоритмы генерации сетевых моделей ЕС;

- разработана методология анализа и синтеза СП-структур, основанная на тензорном исчислении.

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

Реализация и внедрение результатов работы. На основе полученных теоретических результатов разработаны: методика анализа и синтеза структур параллельных ВС: средства описания сетевых моделей структур ВС; организация, структура базы знаний и базы данных, алгоритмы интеллектуальной системы проектирования структур параллельных ВС. Первая версия системы проектирования сдана в Государственный фонд алгоритмов •и программ (регистрационный номер П008080 от 14.02.85 г.).

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

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

Апробация работы. Основные результаты диссертационной работы докладывались, обсуждались и были одобрены на. Всесоюзном семинаре "Автоматизация проектирования в радиоэлектронике и вычислительной технике" (Москва, МДНТП, 1984), Третьей Всесоюзной конференции "Перспективы и опыт внедрения статистических методов в АСУ ТП" (Тула, 1987), Пятой Всесоюзной конференции "КОМПАК-87" (Рига, 1987), • Всесоюзной конференции "Проектирование внешних запоминающих устройств на подвижных носителях" (Пенза, 1988), Всесоюзной конференции "Повышение эффективности средств обработки информации на базе математического и машинного моде-

лирования" (Тамбов, 1989), Международном симпозиуме "1№0-89" (Минск, 1989), Второй Всесоюзной конференции "Микропроцессорные системы автоматики" (Новосибирск, 1990), Всесоюзном семинаре "Информатика в технологии приборостроения"(Москва, 1990), Всесоюзной конференции "Моделирование, проектирование и производство систем ВЗУ ЭВМ" (Пенза, 1990), Первом Всесоюзном школе-семинаре "Современное состояние теории и разработки программного обеспечения СУ с ЭВМ" (Самарканд, 1990), Второй Всесоюзной конференции "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1991). Всесоюзном семинаре "Интеллектуальные средства диагностировали». РЭА" (Ленинград, 1991), Всесоюзной конференции "Математическое и машинное моделирование" (Воронен. 1991), Всесоюзном семинар*- "Новые ин-. Формационные технологии в планировании, управлении и в производстве" (Москва, 1991), конференции "Информационные технологии и системы. Технологические задачи механики сплошных сред" (Воронён, 1992), конференции с международным участием "Микросистема-93" (Москва, 1Г93), Всесоюзных и Международных школах-семинарах (Крымская область, 1984-94 гг.).

Публикации по работе. По теме диссертации опубликованы 62 печатные работы, из которых 36 в соавторстве.

Структура диссертации. Основное содержание диссертационной работы изложено на 298 страницах машинописного текста, иллюстрированного 156 рисунками. Диссертация состоит из 6 глав, введения, заключения, списка использованной литературы (362 наименования) и 10 приложений

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

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

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

Анализируя современное состояние развития вычислительных структур, можно сделать следующие выводы:

1. СуперЭВМ на скалярных операциях имеют предел (100 млн. оп/с).

2. Вычислительные комплексы типа ОКОД и ОВД, построенные на традиционных принципах организации вычислительного процесса, даже, с увеличением числа исполнительных устройств не могут повысить среднюю производительность ЭВМ более чем в 10 раз.

3. Многомашинные vo^!п.^^eкcы типа МКОД и МКМД не могут обеспечить требуемую производительность: во-перзых, из-за невозможности выполнения требования локализации данных. Что приводит к большим временным затратам на поиск и локализацию: во-вторых, увеличение' числа процессоров приводит к росту времени доступа к общей памяти, что снижает производительность каждого процессора.

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

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

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

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

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

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

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

1) возможность формализованного описания как однородных структур, так и протекающих в них процессов для эффективного представления в ЭВМ;

2) наличие развитой теории, позволяющей исследовать модели и объекты. представленные в терминах данного аппарата;

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

4) способность поддерживать методы исследования по час.лм;

5) способность строить простые» методы отображения результатов исследования отдельных подсистем на общую модель ВС;

6) возможность количественной оценки исследуемых вариантов.

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

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

1) возможность построения и исследования широкого класса современных ВС;

2) возможность многоуровневого представления моделей с различной степенью детализации;

^ 3) возможность проведения анализа и синтеза по частям: ч . 4) возможность использования единого подхода к исследованию сложных систем различной природы;

5) простота получения всего множества альтернативных 'вариантов;

6) простота отображения результатов исследования отдельных подсистем на общую:

7} возможность получения количественной оценки сетевой модели.

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

Для формализованного описания сетевых моделей структур параллельных ВС разработан .язык алгебраического описания иерархических СП, грамматика которого представлена на рис. 1. На рис.2 продемонстрирована выразительная мощность СП: представлены, структура синхронного процессора с архитектурой ОКОД, СП-модель данной структуры и соответствующее алгебраическое описание.

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

Множество последовательностей срабатывания переходов Б(Ы). в СП N будем называть языком СП 1ЛЮ. СП Н4 и Мг будем считать эквивалентными 1?, ~ !1г, если эквивалентны языки этих сетей: Ш,) - Ь(Нг).

Определение 1.'СП и И2 называются структурно изоморфными, если существует взаимно однозначное отображение «р множеств Рц и Рг. Т, и Тг друг ла друга, при котором для любых р^ Р1, р3 €?г и ЦбТ5 и 1и€Тг' из условия ф: р! р3 следует, что <р : роэЦр!) «-» роз^р.,) & & $ : рге(р4) рге(р3) , а из условия ф : «-» 1;п следует, .что Ф : розЩ„У «-* розЦ^) & ф : ргеик) — рге(гп) ... ..

Определение 2. СП Н, и 11г называются динамически изоморфными, если существует взаимно однозначное отображение множеств Т4 и Тг друг на друга, при котором из условия -ц> : Т, Тг следует, что ф : Ь(Н,) КОД) .

■Нахождение структурного изоморфизма заключается в поиске таких подстановок Ор и которые ставят во взаимно однозначное соответствие вершины изоморфных СП. Имеют место следующие утверждения, которые связывают существование изоморфизма СП N1 и N2 с '• подстановками Ор и й4. ' '

Лемма 1.- Если СП и структурно изоморфны, то существуют, по крайней мере, две подстановки Ор и ( О,, : Р, Рг, 01: Т^ - Т5), которые ставят во взаимно однозначное соответствие всем вершинам Р! 6 Р,

< иерархическая сеть >:: = < идентификатор сети >: < описание сети>#

< описание сети >:: = < выражение > < список ИПР > | < выражение > | < список ИПР >

< список ИПР > :: = < список ИПР > | < ИПР »

< ИПР >:: = < идентификатор ИПР>: < описание сети »

« выражение »:: = < терн * < операция > < выражение > | « операция > < выракенкэ > | < терм >

< терм >:: = (< выражение ») | « идентификатор сета > | < идентификатор ИПР »|

< идентификатор перехода » «операция > :: = «число >> |, |;|$|+1*|-|" |«число»ч |<число>|)

< идентификатор сети >:: = N < число >

< идентификатор ИПР> :: = О < число »

< идентификатор перехода »:: - Т < указатель перехода »

< ухазатель перехода > :: = < число > | N « числом. < число > | <3 < число >. < число »

< число цифра > < число »| « цифра *

< цифра >:: = 0|1|2|ЗН|5|6|7|8|9

Рис.1. Грамматика языка алгебраического описания сетей Петри

по

Л

✓ ч

ог —; 1

ПЭ 1

Чр

Ор«

¿и

I руг л

(р р01

аз -ив

р02

а) б)

■К* +</Ык:

Рис.2. Пример описания синхронного конвейерного процессора: >) структурная схема; 6) СП-модель; в) алгебраическое описание СП-модали.

ш

и Ц € Тл в СП М, соответственно вершины р3 <£ Р2 и Т2 в СП * Мг (0р = Р1 - Р;|. V* -* так, что

(рге(р1)) = рге(р3) О1(розкр1)) - розКр^ и ' Ор (рге(^)) - ргеС^) 8, Ор (розЦЦ)) - роэК^) .

Лемма 2. Если существуют подстановки Ор и переводящие СП N1 в СП . то есть такие, что для любых Р1 € Р1 и р3 € Р2 из условия Ор : р, - р., следует, что (^(розМр,)) « розКр;,) & (рге(р1) > = рге(р;)), или для любых ^ € Т, и Т2 из условия : 1К — ^ следует, что Ор (розг(Ск)) = розЪ(Ъп) & 0р(рге(1;к)) рге(1п), то СП Н, и N2 структурно 'изоморфны.

Теорема 1. Для того чтобы СП N1 была структурно изоморфна сети N2, необходимо и достаточно существование, по крайней мере, двух подстановок Ор: Р, -* Р2 и Т, - Тг , для которых справедливо: .

01(рге(р1)) = рге(рл) & а( (роз1(р!)) = роэ1(р3) при Ор: р^ - р3 и Ор(рге(^)) = рге(^) & Ор(роэгс^)) = роз1(Ёв) при ^ - 1В.

Лемма.3. Если СП Я, и Н2 динамически изоморфны, то существует подстановка 0{ : ^ - Т2, для которой СЬ(М,)] = Ь(112).

Лемма 4. Если существует подстановка : Тд -» Тг, для которой справедливо ) 3 » Ь(Л2), то СП-структуры Н, и ?12 являются дина-

мически изоморфными. ■

Теорема 2. Для того, чтобы СП И! и М2 были динамически изоморфны, необходимо и достаточно существование подстановки : Т, - Т2, для которой 01[Ь(М1)] =

Рассмотренные утверкдения позволяют построить эффективные алгоритмы поиска эквивалентных СП-структур.

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

Определение 3. Объединением в СП будем называть такую операцию, в результате выполнения которой вершины VI и у3 заменяются одной верши-

ной V , для которой справедливы следующие соотношения: pre(v) - pre(Vj) U pre(vj. post(v) - posUvJ U post(vj.

Определение 4. Разделением в СП будем называть такую операцию, в результате выполнения которой сложная вершина v заменяется двумя вершинами vL и v3. для которых справедливы следующие соотношения: pre(vj U pre(v3) - pre(v), post(vj U post(Vj) - post(v).

Обозначим через Л, = СЫ4. Na.....NJ множество СП. которое может

быть получено путем объединения вершин СП. состоящей из ш элементарных сетей.

Определение 5. Под "частично упорядоченным множеством" СП будем понимать систему X = (Л,,, 8). в которой на множестве Ли определено бинарное отношение 8 >= ">=" (больше или равно), удовлетворяющее следующим свойствам:

1. Для всех N € Ла : N >= N (рефлексивность).

. 2. Если Nt >« и Nj >= Nt', то = (антисимметричности).

3. Если ^ >- N3 и Nj >= Nk. то Mj >= NK (транзитивность).

Определение 6. Выражение "СП N, «покрывает СП N3 " означает, что Ht > Н3 и что условие N4 > NK > N3 не выполняется ни для какого Ns .

Рассмотрим физическую сущность отношения ">- " для множества СП. , Для этого каждому элементу Mt множества Л,,, поставим в соотретствие некоторое число которое определяется суммой вершин СП Н4. Сумму вершин СП Mt будем обозначать как INJ ( kj - INJ ). Тогда Nt >- Nj. если INJ >= |N31. Запись Ht »- N3 означает, что СП Nt изоморфна СП N3. Сгевидно, что если N4 = N3 . то |Nj I » |N31 . однако обратное не справедливо.

Очевидно, что операции объединения и разделения влияют на величину INI путем изменения числа вершин в СП N . Отсюда следует:

Утверждение 1. СП N, покрывает СП Н3 тогда и только тогда, когда INJ - INJ - 1 .

Проверим, удовлетворяет ли наша "интерпретация" отношения ">-" . свойствам определения 5.

1). Если число вершин в СП N обозначить через К , т.е. k = |N| . то очевидно, что к >= к . Следовательно рефлексивность соблюдается.

2). Пусть задана некоторая СП N . рассмотрим СП Nt и N3 . причем Nj получена из К в результате объединения двух позиций, а N3 :;олучена из N путем объединения двух переходов. Следовательно, можно составить следующие соотношения: '

■ INJ - INI - 1 , INJ = |N| - 1 . т.е. |HJ - INJ .

Отсюда N, >= N3 и Nj >= Nj. но N, * N3 по условиям построения СГ Nj и Nj. Следовательно, свойство антисимметричности не выполняется.

3). Доказательство выполнения свойства транзитивности очевидно.

Математические системы, обладающие отношением, для которого выполняются только свойства 1 и 3 определения 5, а свойство 2 не выполняется. называются квазиупорядоченными.

Под верхней гранью к-го уровня подмножества Л' квазиупорядоченно-го множества СП Л-, будем понимать подмножество СП Л[С Д, такое,_ что |М1 |=к для всех Л, и К > 1^1 для всех ^бЛ'. Наименьшая верхняя грань (наим.в.гр.), есть верхняя грань с минимальным уровнем. Под нижней гранью 1-го уровня подмножества Л' будем понимать подмножество СП Л0с /V такое, что |Н1|=1 для всех ^бЛ) и 1<|Н3| для всех Н.,6 Л'.Наибольшая нижняя грань (наиб. н.гр.), есть нижня грань с максимальным уровнем.

Определение 7. Структура СП Л' есть квазиупорядоченное подмножес- " тво Л'£ д,, любой элемент которого, удовлетворяющий условию Л, > N4 > > Н0. имеет наим. в.гр., которая содержит-элементы, полученные в результате выполнения одной операции разделения, и наиб, н.гр., которая содержит элементы, полученные в результате выполнения одной операции объединения.

Если Л' = Л,, . то структура называется полной.

Теорема 3. Полная структура СП обладает только одним наибольшим и только одним наименьшим элементами.

Определение 8. Число элементарных сетей, которое включает максимальный элемент полкой структуры, назовем рангом структуры.

Теорема 4. Полная структура СП ранга г включает все' структуры СП с рангом г4 < г . •

Используя определение 8 и утверждение 1 можно построить графичес- ■ . кое представление (диаграмму) множества СП. На рис.3 представлена диаграмма множества СП, построенная для двух элементарных сетей.'

Одним из ключевых понятий теории структур СП" является пространство структур СП. Рассмотрим основные определения и свойства пространства структур СП.

Ранее мы выделили множество СП Ла и отношение частичного порядка ">-" . Дополнительно введем множество Р других отношений эквивалентности, Тогда пространством структур СП назовем тройку: Л = <ДГ1, Р.,6>. где 9 - отношение частичного порядка ">»".

Любое из отношений эквивалентности ре Р может служить для разбиения множества Д, на смежные классы и построения некоторой шкалы путем сопоставления данных классов. Дробность■шкалы можно определить числом к , таким, что р - р, & р2 Л ... & рх , где р - отношение эквивалентности, по которому осуществлено разбиение Лп, на смежные классы.

Расстоянием Гливенко от A 6 А,, до Л'б Д, произвольной квазиметрической (или метрической) структуры является функция

б(Л.Л') » v[A3 - Ш'3 .

Квазиметрическое пространство (или пространство Гливенко) есть пространство, в котором ыожет быть определена функция 5(А,Л') со следующими свойствами: ' (1) б(А.А)'« О;

(2) б(Л'.А) > 0 при А" * Л ;

(3) б(Л'.Л) - б(Л.Л') :

(4) б(А.А') + б(Л'.Л") >- 6(Л,Л")-

Очевидно, что оценка v[Al является одинаковой для всех элементов Л , т.к. данная оценка является критерием для построения семейства смежных классов. Если функции оценки VIA) поставить в соответствие число вершин в СП-структуре и рассмотреть семейство Д, - {Л,) . то нетрудно заметить, что свойства (1)-(4) выполняются. Таким образом, пространство структур СП, разбитое на семейство смежных кла:сов Да -• {Aj} , является пространством Гливенко.

На диаграмме структур СП, представленной рис.3, оценка v[N]=|N| для всех N€ An ( при m=2 ) разбивает множество А„ на 5 классов эквива-• лентности. Каждый класс объединяет множество СП-Структур с одинаковым числом вершин. Класс эквивалентности отображается величиной уровня грани. Внутри каждого класса построена еще одна шкала v, iAj] . которая оценивает сумму весов головных- и хвостовых позиций каждой СП-структуры К 6 А, в соответствии со следующим выражением:

v, [N] = s, -Ipi + s2-Ip3 , где Ipj - ЧИСЛО ГОЛОВНЫХ ПОЗИЦИЙ, Zpj - ЧИСЛО ХВОСТОВЫХ ПОЗИЦИЙ. St, Sj>

- веса головных и хвостовых позиций соответственно.

Видно, что оценка v, [А,] также разбивает каждый класс эквивалентности на подклассы. Например, класс А3 - {Nj5.N16.N17.Nj-e.N19} разбит на подклассы: А3, - {N1S,NJ6}. Азг = (Nt1). А33 « {Nie}, А34 - {N,9}.

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

n' + m' + w - Зг = const для всех СП-структур, принадлежащих множеству Л^, . Иначе можно сказать, что сумма числа позиций, числа переходов и числа операций обь-единения, необходимых для построения любой СП-структуры Nj6 Аш,является величиной постоянной и равна утроенному рангу структуры СП. Описанная сумма величин является инвариантом в СП-структуре.

Теорема 5. В любой полной структуре СП с рангом г можно построить

VI [ Ь| ] а 811 • £ Р1 + 82 • £ р]; где - 2 р! = число головных позиций;

£р| ■ число хвостовых позиций ;

81,32 • веса головных и хвостовых позиций , соответственно.

Рис.3. Диаграмма множества СП-структур ранга 2

систейу оценочных шкал, при которых существуют инварианты с численным значением равным Зг .

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

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

• В рамках пространства структур СП и на основе алгебры структур СП введем операции преобразования СП-структур.

Определение 8. Изменением разметки СП-структуры N (а N) будем называть изменение числа меток в головных позициях N по следующему правилу: |í+ M(Pi). если pt £ pre(N).

М' íPt > - I M(Pi). если pj ^ рги(Н) .

Определение 9. Вес входных и выходных дуг к Еершине v определяется на основе следующего правила:

если v является переходом t, то: g(a)-t = a-I(t) . (i(a)-t - a-O(t) ; если v является позицией р, то: g(a)-p = а-О(р) . h(a)-p - a-I(t) ;

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

* Делению могут быть подвержены те вершины, которые удовлетворяют следующим условиям: |pre(t) | +■ |post(t) | > 2 .

jpre(p)| > i или |post(p)I > 1 .

Схемы выполнения операций деления переходов и позиций приведены на рис.4. рис.5. Рассмотрим основные операции объединения СП-структур.

Определение 10. Сцеплением головных (хвостовых) позиций р' и р" перехода г будем называть позицию р = р' (1 р", для которой:

НрД) - ш1п(1 (р'. О. Кр'М)) (0(р. О = ш1п(0(р'. Ь),0(р", ) и ц(р) - тахС1пНд(р')/1(р\и). 1пИд(р")/1(р". П)]. где 1ги - функция, принимающая значение целой части от дроби.

Определение 11. Объединением переходов Ъ, и Ъ;, (обозначим I! + + в СП-структуре N является переход . который получается в результате следующей последовательности действий:

а) ргеии) = рге(Ц) иргец,) ;

б) определяется множество Р' головных позиций перехода (в оби;ам случае: Р 'е рге ()}:

еслу Р* = (Pk.Pi) (|Р'!>1). то выполняется сцепление позиций рк и ; в противном случае позиция множества Р' удаляется;

в) роэШц) = роэчг,) и рогШ;)) :

г) определяется множество Р" хвостовых позиций перехода Ьц (в общем случае Р'ЬровИЦ)):

если Р'с розШи) , то позиция множества Р" удаляется, если Р"- розЩи), то выполняется сцепление позиций множества Р".

Определение 12. Объединением позиций р4 и р3 (обозначим Р! + р5) . является позиция ри, для которой справедливо: рге(ри) - рге(р,) и рге(рл). роэКр^) = роБЬ(р±) и роэКр,). и ¿1(ри) = шахтер,). д(р1)) .

Определение 13. Объединением СП-структур к1 и Н2 по переходам ^бТ, и ^е Т2 будем называть СП-структуру Н = И, + Л2 Г^], которая получается в результате объединения переходов ^ и ^ :

т =. (Т,\сг1}) и {т2\(Ч}> и . где ^ = ц + ^ .

Определение 14. Объединением СП-структур М4 и по позициям Р! б Р, и Р] € Р2 будем называть структуру N = М, [р^ + [р3 ]. которая получается в результате объединения позиций Р! и р3: Р - (Р1\{р1>) и {Рг\{р3>) и ри . где р13 = р1 + р3 -.

Определение 15. Объединением СП-структур И, и И2 по множеству вершин (Т„ и Р0) будем называть СП-структуру

N = (Л, * НгИЗ(Т0). 0(Р0)] , которая получается в результате объединения Ы, и Н2 по переходам, задаваемым отношением Э на множестве Т0 и по позициям, задаваемым отношением 0 на множестве Р0 .

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

Делание порахода с выходной позицией

Р" О О'" »и О О

Даламн. парохода с одмиаковым числом 'входных и выходных позиций

!»■ ри ■>•

900

8 »--в

|31 ри (в

о

* 1 'Т

р!1 ри р(а

о

Депениа перехода с ах одной позицией

о1 ___оЧ

О" *

Ч, Ри ^ ^

Горизонтальное деление перехода

\.Г Х.Г. \.;Г

^ • -» •» 0Г9'

71?

Вортмкальмоа даланиа парохода

ри р|2 ри рп р!» г''-* ¡)

_

25 8

,11 /2ш

г» 'ц

Рис.4. Схемы разделения переходов

Ж

Ьс Ъ

Детмме голое ной позиции

й

Деление хвостовой позиции 111 ю

111 1С С 1а ш «а

Деление позиции с одинаковым числом входных мкыходных переходов

И1 ей На 111 (а п»

*« 9 п п

Г ормзоктальиое деление позмдой

(и И! ... 11« (и 111 ... 11^

Рис.5. Схемы разделения позиций

принадлежащей подмножеству . порождает СП-структуру N4 также принадлежащую подмножеству !?„.

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

Операция объединения переходов СП-структуры незамкнута относительно подмножества Я,,.

Операция объединения СП-структур по вершинам: некоммутативна относительно порядка объединения вершин, т.е.

+ N2) Ю<Р0),Э(Т0) 1 * (Л, + Мг) [Б(Т0),а(РЬ)] ; нгеассоциативна, т. е.

((М1^г)+Н3)[3(Т0).а(Р0)] * (Н1 + (Нг+К3))[5(Т0).0(Р0)] ; незамкнута относительно подмножества Р.т. ■ I Рассмотренные свойства позволяют строить более точные и быстродействующие алгоритмы синтеза новых СП-структур ВС.

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

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

Рассмотрим основные тензорные уравнения, описывающие преобразование систем координат пространства СП-структур. Исходным является уравнение состояния СП:

Д' = ¡х Б • Г (б) ,

где Г(б) - степень последовательности срабатывания, представляющая собой вектор, каждый элемент которого указывает на количество срабатываний соответствующего перехода СП-структуры; Ю - матрица инцидентности, составленная из векторов с1 . построенных для каждого перехода, то есть 0 = 0-1. Если учесть, что СП-структура начинает функционировать от начальной разметки, то

¡1 = Мо + Б • Г (б) .

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

М.Г- А»а + в/ - Иб)^ . где индексы К и (3 изменяются от 1 до п и от 1 до га соответственно; п -= |Р| , т = |Т| . Р и т - множества позиций и переходов СП-структуры.

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

Для использования полученных уравнений на практике'необходимо разработать эффективные методы построения тензоров преобразования (ТП).

Общий метод построения ТП основан на решении систем, образованных уравнениями (1) и (3) для ТП или (2) и (4) для ТП Решение

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

Алгоритм построения ТП

1. Сформировать матрицу С размерности п х п (или 2т х 2т)".

2. С = 0 .

3. Для всех 1 = 1,л выполнить: С(1,1) = 1.

4. Для всех 1 = 1,т-1 выполнить: С(21.21+2) - -1 .

5. Конец алгоритма.

Алгоритм построения ТП Е^/'.

1. Сформировать матрицу Е размерности п х п (или 2т х 2га)

2. Е = о .

3. Для всех 1 = 1,п выполнить: Е(1,1) = 1.

4. Для всех 1 = 1,т выполнить:

для всех ¿1 = 1,ш выполнить: Е(21.23) = 1 .

!

5. Для всех 1 * 1.т-1 выполнить:

для всех 3 = 1.ш выполнить: Е(21+1,2,3) = -1 .

6. Конец алгоритма.

Третий метод построения ТП основан на использовании декомпозиции СП-структуры. С этой целью уравнение (1) представляется в виде

(0< 1 >/.' + Ю<2 »С +... ♦ Б< »'/,') - • (0<1 >/+...+ 0<кЧ ). (5)

где слагаемые представляют собой матрицы инцидентности базовых фрагментов, на которые разложена исходная СП-структура. Уравнение (5) может быть сведено к уравнению (6).

_ оу - с*;?/'- о/ . (6)

где (а.а') = 1,к . Из уравнения (6) могут быть получены частные ТП. Общие ТП получаются в результате суммирования частных ТП: . ' . р _ с аг', г /""+ + г аг'

Аналогично можно получить, что:

п^Г » £иА'Г . п*'г гА'К = г1/>'г + р2.«V + + гк^'Г

Ч» Ь'рг и ьм' ь />г' ■

Располагая основными методами и алгоритмами теьзорной методологии

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

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

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

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

-ЭО

!к-1 (к

VI

р к+1

я—1 — I

Чщ

: — - 1 | Чк+1

_ А(Рз) + пз-дз , _ —______ г

<Ь

_ А +

Рис.6. Определение достижимости разметки для линейно-циклического

фрагмента

= О

? 8

о »

Як '-1

I к—1 к—\

(-2

4-1

П;

г-|

Рис.7. Определение достижимости разметки для линейного фрагмента

Обозначения: ч»-весвходной дуги позиции ри ; ср-вес выходной дуги позиции рк; Пк - число срабатываний перехода Ь ,

«1-1(р',И)/0(р-, Ь); Д(рк)» ц'(р«)-ц(р*); 1 = = Г»-Г

Р

Методика определении достижимости разметки на основе тензорных методов

1. Для исследуемой СП-структуры Ni в соответствии с правилами деления вершин строится система линейных базовых фрагментов (ЛБФ) Nl .

2. Между позициями СП-структур Ni и Nl определяется отношение Q , на основе которого строится оператор G .

3. Между переходами СП-структур Ni и Nl определяется отношение S , на основе которого строится оператор F.

4. Для СП-структур Ni и Nl строится тензор преобразования С^ф ■

5. О помощью оператора G для СП-структуры Nl строится множество начальных разметок Mt = {jioi, p02,...,puq) и множество искомых разметок М'= (цг, ц2',...,цг'| .

i б. Для' каждой начальной разметки рм из множества Ме определяется степень последовательности срабатывания í(<n ) для достижения каждой разметки pj' е М' . Если для всех элементов множества М', нн одна из разметок множества М« не достижима, то разметкч Ц' не достижима егт цо .

Определение степени последовательности срабатывания í(cn) выполняется в следующей последовательности.

6.1. В каждой фрагменте системы ЛБФ определяются все последовательности переходов 5? ~ jai, сгг,..., стк | , срабатывание которых приводит к искомой разметке, начиная либо от начальной разметки, либо от разметки альтернативно зависимых позиций, либо от комбинаций данных разметок. _

6.2. Для всех ЛБФ формируется множество разметох М элементы которого задают исходную разметку для срабатывания соответствующей последовательности переходов из множества 9Í. _

6.3. Для хавдой разметки Ц. 6 М с помощью отношения Q в размеченных ЛБФ

строятся разм^ки jj. , от которых может быть получена .

6.4. С помощью уравнения р. = C^g * M¡ СТР0ИТСЯ эквивалентная разметка для

СП-структуры Ni м делается вывод о возможной достижимости исследуемой разметки. Если разметка достижима, то перейти к п.9; иначе перейти к п.б.

7. На основе полученных степеней f(cn ) и оператора F строятся степени последовательностей срабатывания переходов f(<n)' для СП-структуры Ni.

8. Если f(Ol)' корректна, то строится полученная разметка и сравнивается с искомой, на основе чего делается вывод о достижимости исследуемой разметки: если исследуемая разметка достижима, то перейти к п.9; иначе - перейти к п.ь и провести анализ очередного сочетания разметок из множества Мо и М'.

9. Разметка ц' достижима от разметки цо.

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

Поставим в соответствие примитивной системе некоторую последовательность V, состоящую из т + 2га ( га + п ) элементов. Первая часть последовательности (Уг) соответствует множеству переходов, вторая часть последовательности (УР) соответствует множеству, позиций. Будем считать, что элемент последовательности равен нулю, если соответствующая вершина примитивной .системы не принадлежит подмножеству объединяемых вершин, и элемент последовательности больше нуля, если соответствующая вершина принадлежит подмножеству объединяемых вершин. В зависимости от структурных особенностей синтезируемой модели объединение вершин может выполняться несколькими способами:

1) объединением между собой всего множества отмеченных вершин:

2) разбиением множества отмеченных вершин на систему подмножеств и объединением вершин внутри каждого подмножества.

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

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

Свойство 1. Комбинация V, содержащая лишь один элемент больший нуля (положительный) в части 7Т или в части УР. описывает эквивалентную структуру.

Свойство 2. Комбинация 7, содержащая один положительный элемент отличный от остальных в части 7Т или в части УР, описывает эквивалентную структуру.

Свойство 3. Комбинация V, которая содержит максимальный элемент Ч = О,Г( (или д = О,гр), но не содержит меньшего положительного эле-

мента q(q*Oиq<q). описывает эквивалентную структуру.

Свойство 4. Если существует некоторая подстановка Q с областью определения {1,2.....ге > и некоторая подстановка Г с областью определения {1,2.....гр}. которые переводят комбинацию V в комбинацию

7' * V: О : — V. Г : 7Р — V или (Й.Т) : V — V' . то комбинация V описывает программу синтеза эквивалентной СП-структуры ' Заканчивая изложение понятий тензорного исчисления сетевых моделей, отметим основные этапы анализа и синтеза СП-структур с использованием ТП (рис.8). Для анализа большого числа систем представляется логичным из всего многообразия систем выделить одну частную систему. В качестве подобной системы выберем примитивную систему, состоящую из мноке^Зтва элементарных сетей. Разложение СП-структуры на множество линейных* базовых фрагментов и построение примитивной системы составляют этап анализа СП-структуры ВС.

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

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

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

в -

Множество СП- структур в системе координат примитивной системы (эталонные модели) Яш

Рис.8. Этапы анализа и синтеза СП-структур с использованием тензоров преобразования

ре анализа СП-структуры исходной ВС и включает: ввод СП-структуры и структурных ограничений, исследование и коррекция введенной СП-структуры. декомпозицию СП-структуры, построение тензоров преобразования, формирование БД и БЗ. Исследование и коррекция СП-структуры.представляет собой итерационный процесс, который продолжается до тех пор, пока исходная СП-структура не будет удовлетворять требованиям хорошей сформированное™. БД формируется из множества событий, которые могут проЙ-зойти в ВС, и множества описаний аппаратной либо программной реализёй ции каждого события. Первая часть БД состоит из элементов примитивй^Й системы, вторая часть БД формируется экспертом путем интерпретации вершин СП-структуры ВС. Между частями БД существует взаимно однозначное соответствие.

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

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

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

В шестой главе описано практическое" использование разрастаний • методов и средств при проектировании структур сложных вычислительна систем. При этом рассмотрены вопросы проектирования контроллера ¡оптй'-ческого дискового воспроизводящего устройства (ОДВУ) и протокола управления работой информационного канала в вычислительной сетй.,

При исследовании контроллера ОДВУ в качестве исходного BàpiiaHTa была выбрана структура с последовательной обработкой данных всей;'Дб-рожки оптического диска. Анализ новых структур, полученный ад, основй тензорных методов проектирования, позволил сделать вывод о возможности построения контроллеров ОДВУ с более высокими сременными показателями. В качестве подобных можно привести структуры контроллера ОДВУ;^обрабатывающие дорожку оптического диска поблочно. В главе исслёдовАлйсь

Рис.9. Структура интеллектуальной системы автоматизированного проектирования

структуры контроллера ОДВУ с конвейерной и параллельной обработкой блоков дорожки оптического диска. Исследования показали, что подобные структуры повышают эффективность контроллера в среднем на 20% по сравнению с последовательным методом обработки данных.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

В рамках данного подхода:

- дано обоснование использования сетевых моделей (сетей Петри), как средства описания структур ВС на всех этапах проектирования, разработан язык описания СП-моделей;

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

- дана геометрическая интерпретация СП-структур, которая включает: ввод и описание пространства, задание размерности, системы координат. преобразования системы координат, инвариантов;

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

- разработаны методы оценки свойств СП-структур, в рамках которых: предложена методика построения эквивалентных СП-структур; выведе-

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

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

- разработаны алгоритмы для всех методов, входящих в предложенные методики.

3. Основным практическим результатом работы является разработка методов и инструментальных средств проектирования параллельных ВС, которые включают: ' •

- методы и средства составления формального описания СП-моделей

ВС;

- методику анализа структурных и динамических свойств СП-моделей,. основанную на теории структур и тензорной методологии;

- методику построения специальных программ для синтеза новых СП-структур ВС;

- методы отображения результатов анализа и синтеза СП-структур на исследуемые ВС.

На основе разработанных методов построен опытный вариант интеллектуальной системы автоматизированного проектирования параллельных ВС. который в качестве опытной эксплуатации внедрен на предприятиях различных отраслей России. . ■ .

Наиболее важные результаты диссертации опубликованы в следующих работах:

1. Вашкевич Н.П., Зинкин С.А., Кулагин В.П. Структурный"подход к проектированию мультипроцессорной вычислительной системы управления базой данных.//Известия ВУЗов. Приборостроение. - Т.24. - N 9. -1983. - С. 15-24.

2. Кулагин В.П. Система анализа ВЗУ на основе структурированных сетей. /Развитие теории и техники хранения информации; Всесоюзная конф, Пенза, ПДНГП. . - М.: Радио и связь,. 1983. - С.33-34.

3. Вашкевич Н.П., Зинкин С.А., Кулагин В.П. Синтез многоуровневш моделей вычислительных систем.// Вопросы радиоэлектроники. - Сер.ЭВТ. - Вып. И.' - 1983. - С. 83-91.

4. Вашкевич Н.П.', Зинкин С.А., Кулагин В.П. К вопросу автоматиза-

ции ' проектирования сложных вычислительных устройств на архитектурном уровне. /Автоматизация проектирования в радиоэлектронике и вычислительной технике: Матер, семинара. - М.:МДНТП. - 1984. - С.29-34.

5. Кулагин В. П. Формульное представление и правильность сетей Петри. // Вычислительная техника в автоматизированных системах контроля' и управления: Межвуз. сб. научн. тр. - Пенза: Пенз. политехи, ин-т,

1984. - Вып. 14. - С.34-39.

6. Вашкевич Н.П., Зинкин С.А.. Кулагин В.П. Комплекс программ для анализа, сложных вычислительных устройств в процессе проектирования.// Алгоритмы и программы. / Информац.бюллетень ГосФАП СССР. П008080. N2.

1985.

7»-Кулагин В. П. Анализ вычислительных структур с использованием иерзрхйческих сетей. // Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. научн. тр. - Пенза: Пенз. политехи, ин-т. 1986. - Вып.16. - С.31-35.

8. Вашкевич Н.П.. Зинкин С. А., Кулагин В.П. Вероятностные сети Петри./Вероятностные автоматы и их приложения. - Казань: Из-во Казанского университета. 1986. - С.73-77.

9. Кулагин В.П. Тензорная методология при анализе систем управления ' технологическими процессами.//III Всесоюзная конференция "Перспективы и опыт внедрения статистических методов в АСУ ТП"./Тула: ТПИ.

- 1987. - 4.2. - С. 90-91.

10. Вашкевич Н.П.. Кулагин В.П. Тензорный анализ сетевых моделей протоколов вычислительных сетей. // Пятая Всесоюзная конференция "КОМ-ПАК-87". / Рига: ИЭВТ. - 1987. - Т. 1. - С. 239-243.

11. Кулагин В.П. Проектирование вычислительных структур на основе тензорной методологии. // Всесоюзное совещание-семинар молодых ученых и специалистов "Интегрированные системы автоматизированного проектиро^ вания в гибких производственных системах"./ Воронеж: ВПИ. - 1988. -С 121-123.

12. Кулагин В. П. Сетевые' модели и структурный подход к проектированию сложных вычислительных систем.// Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. научн. тр.

- Пенза: Пенз. политехи, ин-т. 1988. - Вып. 18. - С. 4-10.

13. Кулагин В. П. Тензорные методы проектирования структур вычислительных систем.//АВТ. - 1989. - N2. - С. 6'-71.

14. Кулагин В,П.. Кулагина М.Ю. Моделирование функционирования расширенных сзтей Петри.// Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. научн. тр. - Вып.19. / Пенза: Печз. политехи, ин-т. - 1989.

15. Кулагин В. П. Аппарат сетей Петри и тензорная методология в проектировании микропроцессорных систем. //II Всесоюзная конференция "Микропроцессорные системы автоматики". Тез. докл. / Новосибирск: СНИ-ИМ. - 1990. - С.114-115.

16. Кулагин В. П. Интеллектуальная система автоматизированного проектирования микропроцессорных систем управления параллельными процессами. //Всесоюзный семинар "Информатика в технологии приборострое-ния"/Москва: ИНФОРМПРИБОР. - 1990. - С.90-93.

17. Кулагин В. П. Исследование моделей вычислительных систем методом преобразования координат. // Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. научн. тр. -Вып.20. / Пенза: Пенз. политехи, ин-т. - 1990. - С.4-7.

18. Вашкевич Н.П.. Кулагин В.П. Использование тензорного исчисления в интеллектуальных системах проектирования ьараллельных вычислительных .структур. //Вторая Всесоюзная конференция "Повышение эффективности средств обработки информации на базе математического и машинного моделирования"/Тамбов:ТВВАИУ. 1991. - С.246-247.

19. Кулагин В.П. Анализ параллельных процессов на основе сетевых моделей: Учебн. пособие. - Пенза: Пенз. политехи, ин-т, 1991. - 88 с.

20. Кулагин В.П. Использование операций преобразования графов для синтеза вычислительных структур.// Вопросы повышения эффективности систем управления технологическими процессами./ Сб. статей. - Ереван, АРМТЕГ, 1991. - С. 82-86.

21. Кулагин В.П. Вопросы проектирования параллельных многопроцессорных вычислительных структур. //Механизация и автоматизация производства. - 1991, N5. - С. 23-25.

22. Кулагин В. П. Язык описания многоуровневых моделей параллельных систем, основанный на аппарате сетей Петри. //Интеллектуальные средства диагностирования РЭА: Мат. краткосрочного семинара, 21-22 марта 1991 г., Ленинград. - Л.: ЛДНТП, 1991. - С.53-67.

23. Кулагин В.П. Анализ и синтез сложных структур как преобразование элементов линейного пространства.// Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. научн. тр. - Пенза: Пенз. политехи, ин-т. 1991. - Вып. 21. - С. 58-65.

24. Кулагин В.П. Интеллектуальная автоматизированная система для проектирования параллельных вычислительных структур.//Новые информационные технологии в планировании, управлении и в производстве: Мат. семинара. - М. :МДНТП, 1991. - С.126-133. ' ■

25. Кулагин В.П. Алгебраический метод анализа и синтеза параллельных структур.// Новые информационные технологии в проектировании:

Тез. докл. Международной школы-семинара. (4-13 мая, 1991. Гурзуф, СССР). -'Минск: БГУ, 1991. - С. 173-180.

26. Кулагин В.П. Тензорный анализ и сети Петри в технологии создания экспертных систем автоматизированного проектирования./САПР-92. Новые информационные технологии в науке, образовании и бизнесе: Тезисы докладов Международной конференции и школы молодых ученых и специалистов (Гурзуф, 4-13 мая 1992 г.). Воронеж: ВПИ, 1992. - С. 187-188.

. 27. Кулагин В. П. Методы анализа сетевых моделей вычислительных систем. //Автоматизация и современные технологии. - 1993. - HI. -С. 31-34.

28. Кулагин В.П. Алгебра сетевых моделей для описания параллельных вычислительных систем.// Автоматизация и современные технологии. -1993; - N2. - С. 25-30.

29. Вашхевич Н.П.. Кулагин В.П. Методы автоматизированного проектирования параллельных вычислительных структур. /INF0-89: Международный симпозиум, Минск. 1989. -■ Т. 2, ч. 1. - Минск, 1989. - С. 153-157.

30. Kulagln V.P. The analysis of the parallel computational structure network models used In the computer-aided design system. //CAD-93: Hew inform. Technologies for Science, Education and Business. - Yalta (Gurzuf). May 4-13, 1993. - M., 1993. - P.8-9.

31. Кулагин В.П. Анализ и синтез протоколов вычислительных сетей на основе сетевых моделей и тензорного анализа./"Михросистема-ЭЗ":-Тез. докл. научно-технической конф. с международн. участием (8-10 дек., 1993). - М. : МГИЭМ, 1993. - С.83-85.

32. Кухзгин В.П.. Щукина В.Е. Методы описания сетевых моделей параллельных вычислительных структур. //Автоматизация и современные технологии. - 19q4. - N3. - С. 27-32.

33. Kulagln V. P. Following tensor technology In design of concurrent computlrg system./CAD-94: New Inform. Technologies for Science, Education, Medicine and Business. - XXI School and International conference for young sclntlsts and professionals.' - Yalta (Gurzuf), May 4-13, 1994. - M.. 1994. - P. 87-89.

34. Bogatyr B.N., Kulagln V. P. The problem of information of hl-ger education In Russia./Proc. of First International Confer, on Distance Education in Russia ("ICDED'94"). - Russia, Moskow, 5-8 July, 1994: Mosko-w. Russian Асайылу of Sciences, 1994. - P. 124.