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

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

Зотов Игорь Валерьевич

4

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

05.13.05 — Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Курск - 2006

Работа выполнена в Курском государственном техническом университете на кафедре «Вычислительная техника»

Научный консультант:

доктор технических наук, профессор

В.С. Титов

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

доктор технических наук, профессор доктор технических наук, профессор доктор технических наук, профессор

В.Г. Домрачев ВЛ. Бурковский А.С. Сизов

Ведущая организация: Институт проблем управления им. В.А. Трапезникова РАН

Защита состоится 7 декабря 2006 г. в ]5 часов на заседании диссертационного совета Д212.105.02 при Курском государственном техническом университете по адресу: 305040, Курск, ул. 50 лет Октября, 94 (конференц-зал).

С диссертацией можно ознакомиться в библиотеке университета.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 305040, Курск, ул. 50 лет Октября, 94, КурскГТУ, ученому секретарю диссертационного совета Д212.105.02.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

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

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

Проблемы анализа и синтеза УЛУ на протяжении нескольких десятков лет остаются в центре внимания отечественных и зарубежных ученых. Их решению посвящено значительное число теоретических исследований, получен ряд важных для науки и практики результатов. Первые крупные научные результаты, послужившие основой современной теории логического управления, были достигнуты В.И.Шестаковым, М.А.Гавриловым, К.Э.Шенноном и А.Накашимой. Весомый вклад в развитие теории УЛУ внесли М.А.Айзерман, ВЛ.Артюхов, О.Л.Бандман, С.И.Баранов, В.И.Варшавский, А.Гилл, В.А.Горбатов, В.В.Девятков, А.Д.Закревский, О.П.Кузнецов, В.Г.Лазарев, А.А.Ляпунов, Е.И.Пийль, Д.А.Поспелов, И.В.Прангишвили, Е.И.Пупырев, В.А.Скляров, А.А.Таль, А.А.Шалыто, В.С.Харченко, С.А.Юдицкий, Э.А.Якубайтис и др. Результаты выполненных исследований предоставляют мощную теоретическую основу для создания устройств логического управления объектами широкого класса.

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

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

Существенным препятствием на пути практической реализации логических мультиконтроллеров (ЛМК) является высокая сложность организации взаимодействия (координации) параллельных микропрограмм (далее — коммуникационная сложность координации параллельных микропрограмм).

Указанная сложность проявляется в трех аспектах: а) значительное время координации микропрограмм; б) существенные аппаратные затраты на построение локальных коммуникационных блоков модулей ЛМК (контроллеров); в) высокая трудоемкость синтеза распределенных коммуникационных блоков. Значительное время координации микропрограмм в ЛМК обусловлено необходимостью обмена сообщениями при межмодульных передачах управления и синхронизации. Существенная аппаратная сложность коммуникационных блоков связана с поддержкой функций маршрутизации и коммутации указанных сообщений. Высокая трудоемкость синтеза коммуникационных блоков вызвана необходимостью минимизации их сложности и коммуникационных затрат при распределении (размещении) микропрограмм между контроллерами ЛМК.

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

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

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

Объект исследования диссертации — коммуникационные средства координации параллельных микропрограмм контроллеров ЛМК.

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

Связь темы диссертации с научно-техническими программами. Диссертационная работа выполнена в рамках программы П.Т.614 «Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности», приказ Министерства общего и профессионального образования Российской Федерации №572 от 02.03.98, а также совместных НИР с ОКБ «Авиаавтоматика» ОАО «Прибор» (г. Курск) по теме №1.121.03 от 22.08.03 и по договору подряда №19/480 от 01.07.04. Исследования поддержаны грантом Минобразования РФ «Столетовские фанты-2003».

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

Задачи исследований: 1. Выявление и анализ основных причин роста коммуникационной сложности координации параллельных микропрограмм в ЛМК.

2. Разработка обобщенной математической модели коллектива устройств управления координацией микропрограмм в ЛМК и формальных правил ее построения.

3. Создание формализованного метода синтеза устройств управления координацией для широкого класса топологических структур ЛМК.

4. Разработка аппаратно-ориентированных процедур распределенного децентрализованного управления координацией и доказательство их корректности.

5. Разработка функциональных схем устройств управления координацией и контроллеров ЛМК на их основе.

6. Сравнительная оценка быстродействия и аппаратной сложности устройств управления координацией.

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

Научная новизна работы:

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

2. Сформулированы формальные правила построения модели коллектива устройств управления координацией и метод синтеза указанных устройств, применимые к ЛМК с различными топологическими структурами.

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

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

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

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

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

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

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

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

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

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

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

2. Созданный метод декомпозиции вместе с правилами разметки микропрограмм обеспечивают сквозной логический синтез контроллеров ЛМК от алгоритмического описания объекта управления до набора непосредственно реализуемых компонентных микропрограмм, содержащих микрокоманды управления координацией, и позволяют минимизировать число образующихся лишних микропрограмм, логических условий, микроопераций и дополнительных микрокоманд. На основе вычислительного эксперимента установлено, что число решений без лишних микропрограмм, микроопераций, логических условий и дополнительных микрокоманд возрастает соответственно с 80% до 99%, с 40% до 80%, с 84% до 91% и с 60% до 65%.

3. Разработаны функциональные схемы контроллеров с устройствами управления координацией, обеспечивающие возможность реализации логических мультиконтроллеров в базисе СБИС (патенты №2111528, №2112269, №2112272, №2116665, №2145434, №2146064, №2151421, №2152071, №2166793, №2168198 и др.).

4. Создана визуальная программная система декомпозиции алгоритмов

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

5. Разработана объектно-ориентированная визуальная программная среда имитационного моделирования, позволяющая выполнять автоматизированное исследование динамических характеристик и верификацию дискретных систем. Среда была успешно использована при оценке времени координации параллельных микропрограмм в ЛМК.

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

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

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

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

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

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

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

• оценки асимптотической временной сложности и трудоемкости процедуры декомпозиции;

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

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

7. Результаты сравнительной оценки разработанных процедур и устройств

управления координацией, включая:

• аналитическую верхнюю границу времени координации микропрограмм;

• зависимости времени координации микропрограмм от числа контроллеров в составе JIMK;

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

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

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

Реализация результатов работы. Основные научные положения и выводы диссертационной работы реализованы при разработке комплекта программно-технических средств системы автоматического управления котлами малой мощности «Котел-М2М» в рамках совместных работ с ОКБ «Авиаавтоматика» ОАО «Прибор» (г. Курск, 2003-2005 гг.). Ряд результатов работы был использован при производстве изделий специализированным КБ программоуправляемых средств ОАО «Счетмаш» (г. Курск, 2001 г.). Кроме того, показана возможность практического применения метода декомпозиции алгоритмов логического управления при синтезе устройства управления роботизированной ячейкой для сборки электродвигателей малой мощности.

Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс на кафедре «Вычислительная техника» Курского государственного технического университета и используются при проведении занятий по дисциплинам «Организация ЭВМ и систем», «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров», а также в курсовом и дипломном проектировании, при подготовке магистерских диссертаций. Положения диссертации были использованы в качестве научно-методического пособия шестью выпускниками КурскГТУ при подготовке кандидатских диссертаций.

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

1. На Международной конференции «Параллельные вычисления и задачи управления» (Москва) в 2001 и 2004 годах.

2. На Международной конференции «Идентификация систем и задачи управления» (Москва) в 2000 и 2006 годах.

3. На Международной конференции «Information and Telecommunication Technologies in Intelligent Systems» (Барселона, Катанья) в 2004 и 2006 годах.

4. На Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза) в 1996, 1998 и 2000 годах.

5. На Международной электронной научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж) в 2000 году.

6. На Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (Нижний Новгород) в 1999 и 2000 годах.

7. На межвузовской научно-технической конференции «Управляющие и вычислительные системы. Новые технологии» (Вологда) в 2000 году.

8. На Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (Курск) в 1997, 1999, 2001, 2003, 2005 годах.

9. На научных семинарах кафедры вычислительной техники Курского государственного технического университета с 1998 по 2006 год.

Публикации. Содержание диссертации опубликовано в 85 работах, среди которых 3 монографии, 24 статьи, 20 патентов на изобретение, 3 свидетельства о государственной регистрации программы для ЭВМ. Основные из указанных публикаций перечислены в конце автореферата.

Личный вклад соискателя. Все выносимые на защиту научные положения разработаны соискателем лично. В основных научных работах по теме диссертации, опубликованных в соавторстве, личный вклад соискателя определяется следующим образом: в [1-4,10,34,36] разработаны теоретические основы создания устройств управления координацией параллельных микропрограмм в ЛМК, в [35] сформулированы правила определения адресов перехода при осуществлении межмодульных передач управления, в [8,13,15,19] произведена оценка сложности и быстродействия коммуникационных процедур и блоков, в [1-3,5,6,14,16-18,37,40] сформулированы основные положения созданного метода декомпозиции и преобразования управляющих алгоритмов в коллектив параллельных микропрограмм, в том числе в [2,3,5] проведен анализ корректности редукционных преобразований, в [39,41,42] сформулирована методика сравнительной оценки различных методов декомпозиции, в [2,11] описано применение разработанного метода декомпозиции при синтезе устройства управления роботизированной сборочной ячейкой.

В совместно разработанных технических решениях по теме диссертации личный вклад соискателя заключается в следующем: в [20,23,24] спроектированы блоки управления синхронизацией микропрограмм, в [21,25] предложены схемные решения по организации межмодульных взаимодействий в ЛМК, минимизирующие аппаратную сложность контроллеров, в [22,33] разработаны форматы микрокоманд и схемы вычисления адресов переходов, в [31,32] предложены схемы координации смежных модулей коммутатора ЛМК.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, приложений и списка литературы из 228 наименований. Работа содержит 383 страницы текста (с учетом приложений) и поясняется 75 рисунками и 10 таблицами.

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

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

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

Успехи современной микроэлектронной технологии предопределили возникновение целого ряда новых архитектурных решений параллельных устройств логического управления (В.А.Горбатов, А.Д.Закревский, В.В.Соловьев, В.С.Харченко и др.). К их числу относятся и ЛМК. Логический мультиконтроллер — однородная многомодульная система логического управления с аппаратной поддержкой межмодульных взаимодействий. Его базовыми функциональными составляющими являются коллектив

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

взаимодействие (см. рис.1). Каждый контроллер включает функциональный (ФЭ) и коммуникационный (КЭ)

элементы. ФЭ представляет собой процессор, способный реализовать частный

последовательный алгоритм логического управления

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

ЛМК реализует комплексные параллельные алгоритмы логического управления. Их класс ограничивается алгоритмами, имеющими одну начальную и одну конечную вершины, не содержащими недостижимых вершин (требование живости), не допускающими активизацию операции во время ее выполнения (требование безопасности) и не включающими разветвлений со свободным (не зависящим от условия) выбором направления (требование устойчивости). Реализуемый алгоритм может включать произвольное число параллельных и последовательных ветвей, ветвлений (в том числе многоальтернативных) и

И_I

КСОУ

1 КС 1

гт

КСВУ

Рис.1

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

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

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

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

При межмодульной передаче управления перед осуществлением перехода и активизацией микропрограммы необходимо получение адреса перехода. В известных решениях (А.А.Гремальский, В.А.Колосков, В.С.Харченко и др.) указанные адреса задаются передатчиками управления и передаются через КС в виде сообщений приемникам управления. Синхронизация также вызывает необходимость межмодульных обменов сообщениями. Передача сообщений при реализации процедур координации микропрограмм требует организации сеансов межмодульного обмена информацией через КС. Эту задачу решают средства маршрутизации и коммутации (ретрансляции) сообщений. Средства маршрутизации обеспечивают выбор маршрутов в КС ЛМК в соответствии с ее топологией и организуют перемещение по ним сообщений. Задачей средств коммутации является асинхронный прием сообщений от соседних КЭ и их выдача в требуемые выходные каналы согласно заданным маршрутам с учетом принятой дисциплины обслуживания.

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

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

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

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

2. Переход к распределенной децентрализованной аппаратной синхронизации без обмена многоразрядными сообщениями.

3. Осуществление межмодульных передач управления на основе единой процедуры синхронизации по п.2.

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

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

Мультиконтроллер представим топологической моделью в виде связного графа Н = (М,и), множество вершин М которого соответствует контроллерам, а множество ребер ЦсМхМ — межмодульным связям. Будем считать, что с каждым контроллером т1 е А/ связано устройство управления координацией

микропрограмм 0. Коллектив таких устройств опишем парой (я,п), где н = {м,и) (О^и) — топологическая модель, П — множество процедур управления координацией. Модель Н получим из графа Н путем ориентации всех его ребер таким образом, чтобы выполнялись следующие условия:

• в Н присутствует одна вершина тк, не имеющая исходящих дуг;

• в Н имеется как минимум одна вершина т" без входящих дуг;

• все пути, соединяющие вершину т" с вершиной т\ в графе Н, простые. Офаничим класс допустимых топологических структур ЛМК такими, для которых указанные условия выполнимы. Рис.2 иллюстрирует построение модели Н для топологических структур «матрица» (рис.2,а) и «гиперкуб» (рис.2,б).

б)

Рис.2

Множество процедур управления координацией П определим, используя аппарат сетей Петри. Каждой вершине т,&М поставим в соответствие сеть Петри А>=(7;,^,*5„5(*,/,) (см. рис.3) с множествами переходов = —П—я<

позиций К1={р'1,р~,р),р*,...,р('}, дуг Ц^ ^р) ^р] *5,=/^х7;х{1,2}, 5,*=Т;х^х{1)2}, и с функцией маркировки /(—>№и{сс), где я N — множество натуральных чисел, — константа, зависящая от вида топологической модели Н: =|/с+ (ш,)|, «-*(т,)сМ - ОрГ максимальное по включению множество

вершин такое, что е (ш],т,}еО. тт я" Рис.3

Из множества сетей {л,} построим сеть Петри Л = (Г,Л,*5,5*,/) с множествами переходов Т (Ггэ ^7}), позиций Л (Л=> ^), ДУГ

♦5сДхГх{ 1,2}, 5*сГх/?х{1,2}, и функцией маркировки /:Л->Ми{оо}, отображающую коллектив устройств управления координацией микропрограмм. Сеть Л сформируем, используя следующие правила композиции.

Правило объединения сетей. В каждую сеть Л, ввести множество новых дуг

2,...,/,})} такое, что У^.р/Л), (яу ,pf, l) е , / * j": г'* г" ,н положить S* = S,* uSf.

Правило зацикливания. Выбрать подмножество вершин М'с M\{m't} таких, что V/n, е М': f. < max {лг+ (т. )}. Добавить в сеть Л, позицию р0 и переход л"0: Я* = Rt V-J {уО0}, Tt = rt , а также множество новых дуг

е ^ т, е Л/') и положить = =

Графическая иллюстрация правил объединения сетей и зацикливания дана на рис.4 и рис.5 соответственно (новые дуги выделены). На рис.4 через лг~(/я,) обозначено множество вершин такое, что V/я, е к'{т,):е U.

Рис.4

На рис.6 показано построение сети Петри Л для матричной топологической модели ЛМК (см. рис.2,а). Поскольку в матрицах принята двойная нумерация вершин, отражающая их принадлежность определенным строке и столбцу, элементы сетей {Л,} также перенумерованы двойными индексами. Через Nl и Л^ обозначены соответственно число строк и число столбцов матрицы.

Определим предметную интерпретацию элементов синтезированной модели.

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

ТР

▼▼ р\ р\ (■

оР\р 9 ... у

Рис.5

Ои с множествами вершин Уи, логических условий Х„, микроопераций

микрокоманд 1Уи, и с множеством дуг Еы. На множестве Уу определим отношения связи (р, альтернативы цг и параллельности т. Пусть в йи имеется множество максимальных по длине линейных участков (ветвей) 0„={В„В2,...,В,}, Вас=Уы(а = ТТи).

Пусть в результате декомпозиции алгоритма О,, получено отображение Си:Кудовлетворяющее условию:

Тогда для ветвей можно получить отображение С'и: £>„ —» М. Каждую ветвь Ва, для которой )| > 1,

разобьем на фрагменты В'а,В*,...,В£" с Ва так, что

ег>6 {1,2,...,//„},6 Еи: С (ге) = (у,))л

л(уу. е т £„м(у„уй)е £.): с. ы *£•>.))•

Обозначив множество всех ветвей ¿?а е Ц, и полученных фрагментов через £>,*, получим функциональное отображение : £>и* —> Л/, задающее межмодульное распределение ветвей алгоритма. Путем кодирования всех ветвей (фрагментов) Ва,Връ.Г>ш таких, что С'и(Ва) = = т,, и введения коммуникационных

микрокоманд формируется микропрограмма контроллера т,.

Определим отношение частичного порядка «-1с £>* х£>*. Будем говорить, что ветвь Ва предшествует ветви Вр, т.е. ВаЛВр, если и только если

Эуе е Ва,у^ е Вр ЕЦ, где Е~ - подмножество множества дуг Еи, не

включающее «замыкающие» дуги циклов.

Определение 1. Всякое максимальное по включению множество попарно параллельных ветвей ./с£>* такое, что \/Ва е./ : Вр е Г\ \ J, будем

называть множеством синхронизируемых ветвей (./-множеством).

Определение 2. Всякое максимальное по включению множество попарно параллельных ветвей Е с Ц' такое, что \/Ва е Е, В^ е 3: В^Ва, где J— некоторое У-множество, назовем множеством активизируемых ветвей для 3 (/•'-множеством).

Каждой паре множеств У) такой, что соответствует

некоторая вершина синхронизации (барьер). В то же время, парам множеств

(/*",./), для которых (У с Д* \ /?„) л (/" с £>„* \ ), не соответствует вершин синхронизации, поэтому поставим в соответствие каждой такой паре фиктивную вершину синхронизации. Обозначим через Ух множество вершин синхронизации алгоритма . Пусть е Уы. Тогда соответствующее вершине ха ./-множество обозначим как а ^-множество — как

Каждую ветвь Ва е й'и условимся характеризовать текущим состоянием «активна» или «пассивна». Формально состояние ветви Ва будем задавать индикаторной функцией: да (/) = 1, если ветвь Ва в момент I активна, да (/) = О иначе. Определим для каждой вершины у„ е Уи индикаторную функцию ZiI(/)e{0,1}, удовлетворяющую следующим условиям: 2а(/) = 0, если хотя бы

одна ветвь Ва ej(va) в момент t активна, Za(t) = 1 иначе, Ze(0) = 0.

Будем говорить, что синхронизация ветвей j(vo) выполнена, если в некоторый момент /' ((/' > 0) л (/' ф от)) имеет место: Z0 (/') = 0 —> 1 (условие синхронизации), где запись 0 -> 1 (1 —>0) означает переход значения из 0 в 1 (из 1 в 0). Если реализуемый алгоритм включает циклы, то возможно несколько актов синхронизации ветвей j(vo). Поэтому в общем случае необходимо 3/",(<" > t') л 0' * °о): Za ( /") = 1 —> 0 {условие восстановления).

Определение 3. Промежуток времени от момента нарушения ( Za (t") = 1 —> 0) до ближайшего момента выполнения условия синхронизации (Z„(/') = 0 —>1) назовем циклом синхронизации.

Определение 4. Промежуток времени от момента выполнения условия синхронизации (Za (/') = 0 —»1) до ближайшего момента нарушения этого условия ( Za (t") = 1 —> 0 ) назовем циклом восстановления.

Процесс координации микропрограмм представляется последовательностью чередующихся циклов синхронизации и восстановления. Пронумеруем указанные циклы числами vv = 1,2,3,... в порядке их следования. Тогда циклы синхронизации получат нечетные номера, а циклы восстановления четные.

Уточним условия завершения циклов синхронизации и восстановления.

Определение 5. Будем говорить, что вершина синхронизации vb следует за вершиной синхронизации va (vfc i—» v0), если и только если существует простой путь ¿(v„,vft)c:£;.

Определение 6. Вершины синхронизации v„,vbeVll назовем параллельными (v„||vt), если и только если существуют две другие нефиктивные вершины синхронизации vc,vdeVu и простые пути ¿(v,.,^), ¿(vc,v4), ¿(v,,^), L(vh,vd)ci E'u такие, что:

[(¿(v„»I)ni(v[1vt))\{vc}=0]A[(L(»1,vi)ni(n,v<))\{»<}=0].

Введем в рассмотрение ориентированный граф Г,, вершины которого поставим в соответствие множеству Va, а множество дуг определим отношением I-» (Г„ =(K„,i-»)). Назовем Г„ графом следования вершин синхронизации.

В графе Г„, очевидно, найдутся вершины синхронизации v, такие, что -i(vt к» у.) Vv, е F , а также вершины синхронизации v_ такие, что -i(vA (—> v_) VvA е . Выделим в Г„ множество путей, начинающихся в v, и завершающихся в v_; Пусть найдено z таких путей LI,L1,...,LI с множествами вершин Кх,К1,...,Кг соответственно. Потребуем, чтобы выполнялось условие: Кр гл К q=Q), p,q = \,z, p^q. Для этого удалим из множеств K„K2,...,KZ все повторения вершин. Каждое множество К , p = l,z, как следует из построения, будет содержать только попарно непараллельные вершины синхронизации.

Каждому т,еМ поставим в соответствие г двоичных векторов вида

К = .....где И = Ы: <^=0,если D'u(ml)r>J(va)*0, ^ = 1

иначе, где О* (т1) — множество ветвей, назначенных на контроллер т,.

Обозначим через г*(&„) и моменты активизации и последующего

завершения ветви Ва соответственно. Рассмотрим произвольное У-множество У (гв) и соответствующее ему /^множество Р(у„). Введем обозначения:

г". (О = т,п }{г- (В,)}; ^ (V.) = т^г* (Вг)}.

Потребуем, чтобы выполнялось условие согласованности: г*ах(у<1)<г^п(у0). Тогда процесс координации ветвей У(у<,)и/Г(у<1) будет локализован на интервале = и состояние ветви В^ & Dl(mí)r^J(va) можно

уточнить следующим образом: ^ (') = £>(')> если *еДг(ув); ^(/) = 0 иначе.

Таким образом, условия завершения циклов синхронизации и восстановления для ветвей можно записать в виде конъюнкции

2°= „Ш(')' в К0Т0Р0Й г'а0) = V , причем Вр е (т,)r\J(y<1).

С учетом сказанного дадим интерпретацию элементам построенной модели.

Обозначим через к*(т,) _/-ю вершину множества к*(от,), ] = Пусть

О) — значение индикаторной функции £„(') в вершине т:еМ, а —

значение этой функции в вершине к* (от,), и пусть и» - номер цикла синхронизации/восстановления. Тогда переходы и позиции сети А, можно интерпретировать в определенных выше терминах в соответствии с табл.1.

Событиям и условиям в сети А, соответствует следующая предметная интерпретация: срабатывание перехода л] моделирует завершение микропрограммы (ветви) /-м контроллером; позиция р] представляет факт завершения микропрограммы ;'-м контроллером; срабатывание перехода ж" отображает начало активизации микропрограммы в /-м контроллере; позиция р" моделирует разрешение перехода к активизации для /-го контроллера.

На основе разработанной модели с учетом принятой интерпретации ее элементов определим процедуры управления координацией микропрограмм. Первая, называемая распределенной циклической рассылкой и обозначаемая СуСа$1, описывает последовательность циклов синхронизации/восстановления для множеств вершин синхронизации К1,К2,...,Кг. Вторая - процедура активизации — определяет порядок активизации микропрограмм (ветвей) при выполнении условия синхронизации и обозначается \Vakeup.

Таблица 1

Элемент модели Интерпретация

•* г:0) = 1->о

2' (0 ' нечетном ° [1 —» 0 при четном м>

Р*

Р? ,, . ("1 при нечетном IV; З^'Нп [0 при четном и*

р/»у'=П7 1 при нечетном " —> 0 при четном XV

2. 0) ' П'ЗИ нечетном [1 -> 0 при четном м>.

Ро , . ("1 при нечетном тс; , ч 2.0) = Г г.(о)=о [0 при четном и».

Для формального описания процедуры СуСси/ каждому множеству вершин синхронизации Кр(р = 1,г) ставится в соответствие сеть Петри Л^Л^), получаемая применением правил объединения сетей и зацикливания. Пусть для каждой сети Л(Кр} установлена следующая начальная маркировка позиций:

4 = (/о(ро)=1»/о(р;)=ол„(р;')=о,/Др/) = о(г = й7,; = й)), ы*\м\.

Тогда процедура СуСля/ будет вполне определена совокупностью достижимых маркировок сетей =

Для описания процедуры \Vakeup каждому контроллеру т, ставится в соответствие сеть свободного выбора П, с нулевой начальной маркировкой (см. рис.7). Переходы и позиции сети С2, интерпретируются так, как указано в табл.2. Через обозначена текущая вершина синхронизации множества Кг, выбираемая согласно отношению ь-».

Срабатывание перехода ж, сети П, отображает событие активизации одной из ветвей е £>*(лг,); в диссертации показано, что выбор ветви однозначен. Размещение ветви Ва в памяти контроллера т, идентифицируется разработанными правилами разметки микропрограмм.

Доказано, что сеть Петри Л, получаемая применением правил объединения сетей и зацикливания, является живой и 2-ограниченной, а сеть О, жива и ограничена. Из полученных доказательств выведено, что разработанные процедуры управления координацией не порождают тупиковых ситуаций.

Элемент модели Интерпретация

переход л" сети Петри = 1,г)

существование ветви

р'и

р% условие синхронизации для vaU) выполнено и (/) = 1 —» 0

разрешение активизации ветви

р, разрешение активизации ветвей

Щ (/)=о->1

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

Синтез коллектива устройств управления координацией формализуется следующей последовательностью этапов.

1. По граф-схеме алгоритма Си задается отношение (-».

2. Формируется граф следования вершин синхронизации Г„.

3. В графе Г„ выделяются подмножества вершин К, (.$ = 1,г) так, что

Крг\Кя=0, р,д = 1,2, р*д.

4. По графу Н = (М,1/) строится топологическая модель Н = (м,0).

5. Формируются сети Петри ЛиД.

6. Из сетей (.г = 1,г) и £2, (/ = 1,л0 строится объединенная сеть Е.

7. Путем интерпретации сети Е в элементах заданного базиса формируется функциональная схема коллектива устройств управления координацией.

На основе созданного метода синтеза разработано несколько схемных решений, применимых в ЛМК с различными видами топологии (матричной, кольцевой и др.). Активность сети Е в этих решениях отображается перепадом уровня сигнала: в цикле синхронизации активен положительный перепад, а в цикле восстановления — отрицательный.

На рис.8 изображена ______

структурная схема матричного ЛМК, включающего коллектив устройств управления координацией

(указанные устройства показаны кружками, а контроллеры ЛМК-квадратами). Каждое устройство

состоит из множества параллельно работающих секций (бД^.)}» соответствующих множествам К, (5 = 1,2). Функциональная схема секции (20{К,) представлена на

рис.9. На рис.10 изображена функциональная схема устройства в целом.

щж. - _щ

■Щ

|| 4. й- 41

15;: БВ Гй > ^ Б*-

Рис.8

Внешние входы и выходы подключают устройство Q¡¡ (рис.10) к контроллеру т0-, а также к соседним устройствам согласно схеме рис.8: входы

{г;ГК)(0}, соединяются с выходами {¿^ (*)}, {^'Ч')}

устройств и б,(у-|) соответственно (при (/ > 1) л(у > 1)) или с выходами

^"'"'(г)} устройства (ПРИ 0 = 1^(у' = 1)). Сигнал срц является

настроечным и равен логической единице только при (/ = М,)л(у =

На рис.11 изображена функциональная схема контроллера матричного ЛМК, включающего устройство управления координацией микропрограмм, представленное на рис.10 (патент №2168198). Контроллер (рис.11) включает блок 1 памяти микропрограмм, регистр 2 адреса, регистр 3 микрокоманд, мультиплексор 4 логических условий, регистр 5 вектора соответствия, коммутатор 6 адреса, регистр 7, дешифраторы 8 и 9, блок 10 синхронизации, элементы И 11.1-11.п, 12.1-12.П, элементы ИЛИ 13.1-13.п, 14, 15-17, одновибраторы 18 и 19, элемент 20 задержки. Вход 21 используется для приема сигналов логических условий от объекта управления, а выход 22— для выдачи сигналов микроопераций на объект управления. Входы 23-26 предназначены для приема сигналов инициализации с верхнего уровня управления. Входы 27, 28 и выходы 29 обеспечивают подключение к соседним контроллерам ЛМК согласно

схеме рис.8 и соответствуют входам , и выходам {-¿^ (г)|

устройства на рис.10.

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

Быстродействие устройств управления координацией в диссертации оценивается на основе исследования зависимостей времени координации ветвей (микропрограмм) от числа взаимодействующих микропрограмм и числа контроллеров в составе ЛМК.

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

тах||У(уа)|,^(у<1)и. Для упрощения считается = ^(ч,)) в предположении,

что — средняя мощность ./-множеств. С учетом сказанного быстродействие

устройств управления координацией оценивается по длине интервала А гЧО = (гтаДу»)>^т»ДО)- Аналитически установлено, что указанная длина не зависит от |-/(ч,)| и ограничена сверху диаметром графа Н.

Для исследования зависимостей Дг'(тл) был проведен вычислительный эксперимент с использованием программной среды, разработанной под руководством соискателя (свидетельство о государственной регистрации №2006610308). В ходе эксперимента выполнялась имитация взаимодействия случайно завершающихся ветвей в матричном ЛМК. Размещение ветвей предполагалось равномерно распределенным, а моменты их завершения вычислялись согласно усеченному распределению Гаусса.

На рис.12 представлены зависимости Дг'(уа) от полученные для

матричного ЛМК, содержащего 100, 400 и 900 контроллеров. Эти зависимости подтверждают отсутствие роста Д г'(ув) при увеличении Полученные

зависимости Дг'(ув) от числа контроллеров ЛМК показывают преимущество разработанных устройств по быстродействию не менее чем в 1,5 раза. В частности, значения Дг'(у„) для матричного ЛМК, содержащего 1000 контроллеров, при задержке вентиля равной 10 + 3 не не превышают 3 мкс.

Дг'(у„), тактов 90

80 70 60 50 40 30 20 10

Н кч

20

35

50 65 Рис.12

80

95

^ N = 900

-- N = 400 ^ ^ = 100

Аппаратная сложность разработанных устройств оценивалась путем подсчета числа эквивалентных вентилей (ЭВ). Для матричного ЛМК, в частности, аппаратная сложность одного устройства (см. рис.10) составляет IV = 12г + 6, т.е. О(г). Для реальных алгоритмов управления ^ = 0(Ю)...0(100), поэтому ^ = 1000... 10000 ЭВ. Подобные оценки для известных аналогичных устройств в 2 и более раз превышают полученные значения IV.

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

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

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

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

=у»г * 0>у* п =0> г'г'>г"=п^у *г(»)

г-1

= (2) где £,и — число полученных частных алгоритмов (микропрограмм); Уиг -множество вершин г-го алгоритма.

Также должны выполняться технологические ограничения:

IV (у;) < Я, |*(к;)| < х,\у (к;)| ¿г(г = Т£), (3)

где 1У(КГ) ~ число микрокоманд г-го алгоритма; х(Уи'^, У{К) ~ множества

логических условий и микроопераций г-го алгоритма соответственно; IV, X,У -предельно допустимые значения числа микрокоманд, логических условий и микроопераций частного алгоритма соответственно.

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

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

Разработанный автором метод декомпозиции позволяет разбивать параллельные управляющие алгоритмы в соответствии с ограничениями (1)-(3) и с минимизацией числа лишних микропрограмм, условий, микроопераций и связей между микропрограммами (дополнительных микрокоманд). Декомпозиция осуществляется с применением новых редукционных преобразований и процедур, включая размыкание циклов (ОгсусПпд), формирование базового сечения (ВазеБес!), перебор смежных сечений (БиЬзШБеМ, 8иЬз108еа) и размещение вершин сечения (АПосЗеМ).

Метод базируется на следующих определениях.

Определение 7. Сечением будем считать всякое подмножество множества вершин алгоритма С1сУи, удовлетворяющее условию

[(И = 1) V е П, а * Ь: -,{уа<ру4))] л^гПЗу.еП: Vс<ру, ].

Определение 8. Любое подмножество назовем субсечением.

Определение 9. ©-мощностью (суб)сечения О., назовем максимальное число его попарно параллельных вершин, («-мощность будем обозначать через |

Определение 10. Сечение такое, что Г< Г,

назовем максимальным, Э? — семейство всевозможных сечений алгоритма Ои. Определение 11. Сечения 0.к и О.,, смежны, если и только если

е С1к, е = v ((у„,у8) е Е') v )].

при этом назовем ы-сечением для й,,ай,- ¿/-сечением для П^. Далее и- и <1-сечения будем помечать верхними индексами Т и 4- соответственно. Процедура декомпозиции описывается следующим алгоритмом.

1. Используя преобразование Оесус!привести исходную граф-схему к

ациклической форме С~.

2. Сформировать базовое сечение Птах, применяя преобразование 5гюе5ес/.

3. Принять К = Уи; £ НОтах Г; , = 1, О0Т=П„;=Отах.

4. Распределить вершины сечения Пт>х, используя процедуру АПосБес!.

5. Положить Уи = ^). Если Уи =0,то перейти к п.13.

6. Сформировать и-сечение : если у*еП,т_, (V* — начальная вершина алгоритма), то положить

иначе построить Г2, путем применения

процедуры БиЬзШБеа.

7. Положить П,т = П,т п Уи. Если П,т = 0, то перейти к п.9.

8. Распределить вершины сечения Г2,т, используя процедуру АИосБесг.

9. Сформировать (/-сечение О*: если V** е(у" — конечная вершина алгоритма), то положить = , иначе построить путем применения процедуры ЗиЬ$!ОЗес1.

10. Положить П,1 = П,1 Г) Уи. Если О,1 = 0, то перейти к п. 12.

11. Распределить вершины сечения О.), используя процедуру АНосБесг.

12. Считая / = / +1, перейти к п.5.

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

Назначение и сущность использованных выше преобразований и процедур Decycling, ВшеБес!, ЗиЬзМБес!, БиЬзгОЗес!, АНосЯес! сводится к следующему.

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

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

Преобразование обеспечивает быстрое нахождение одного из

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

Основу преобразования ВазеБеа составляют разработанные соискателем редукционные правила ¡/-поглощения, ¿/-поглощения и ^перегруппировки-Первые два правила обеспечивают замещение всех субсечений в текущем сечении субсечениями большей (»-мощности с реконфигурацией связей между вершинами. Последнее правило применяется при неоднозначности поглощения.

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

Процедуры БиЬзМБеМ и 5г<6.уЮ5ес/ формализуют переход от произвольных исходных сечений £1,т_, и к сечениям П* и О.) соответственно при переборе вершин алгоритма управления. Доказано, что последовательное применение этих процедур относительно базового сечения Птах обеспечивает перебор всех вершин алгоритма за конечное число шагов. При этом на каждом шаге в рассмотрение берутся только попарно параллельные или альтернативные вершины. Установлено, что при использовании процедур БиЬниЗес! и просмотр

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

Процедура АПосЗгсС описывает порядок размещения вершин базового сечения П„„ и сечений П,\ п/ в формируемых частных алгоритмах. Каждое размещаемое сечение разбивается на подмножества попарно несвязанных вершин. Оценка целесообразности включения выделенных подмножеств в частные алгоритмы производится путем построения и анализа таблицы оптимальности включения. Каждый элемент этой таблицы соответствует определенной паре «подмножество вершин - частный алгоритм» и рассчитывается по формуле, увязанной с критериями качества декомпозиции (минимум лишних микропрограмм, условий, микроопераций и связей между микропрограммами) и учитывающей ограничения (1)-(3).

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

Определим на множестве £>* функцию индексации Ои: £>* —> N \ {0}. Пусть Вр е причем е Кг. Пронумеруем вершины множества К, в порядке их

следования i—> индексами, начиная с 1. Тогда вершине будет сопоставлен индекс ¡а. Положим 0„ (Вр) = /„ •

Индексация ветвей номерами вершин синхронизации дает возможность однозначного определения моментов их активизации. Для идентификации размещения этих ветвей в памяти контроллеров выполняется разметка микропрограмм по описанным ниже правилам.

Пусть Н(/я,) — множество адресов памяти микропрограмм контроллера л?, е Л/. Тогда каждой ветви Ва е £>' (от,) будет соответствовать начальный адрес '9^ еН(от,) (адрес первой микрокоманды) и финальный адрес 9£ еН(/и,) (адрес последней микрокоманды). Таким образом, всякую ветвь Ва е (/и,) п К, можно представить четверкой Ва={Ои{^Ва),К:!,'9'а,9'^. Адреса '9'а идентифицируют переходы в контроллер т1 из других контроллеров при передаче управления и синхронизации, поэтому назовем их адресами переходов. Микрокоманды, размещенные по адресам '9'а и 9'^, обозначим для краткости М1(*^) и М1(,5£*) соответственно. Через МР(и,/") обозначим фиктивную микрокоманду начального запуска контроллера /я, при выполнении алгоритма О,,, а через МГ(«,;') -микрокоманду индикации завершения контроллером т1 этого алгоритма.

Правило 1. Если для некоторой ветви Ва е £>* (/и,) имеет место ->[Ва I—> \/Вд е О*(/я,), то припишем индекс Ои (Ва) и адрес '9'а микрокоманде

МГ(м,/).

Правило 2. Если Ва 1-> Вр, Ва,Вр е Д'(т,), причем МВ7 е ££(/?»,), У*Р'. Вг ь» Вр => Вг ь-> Ва, то припишем индекс Ои(Ва) и адрес '9'а микрокоманде М1(<9^*).

Правило 3. Если для ветвей Ва,В/1 е 0*(т,) выполняется Ва,Вр сС(где См бС(С„), С{р„) - множество циклов в Си), причем ы» Вр,аФр)\/(а = Р) и е£>*(т,.), ВгсСм: (уе{а,/?}) v[(B;. В^) л(Ва то припишем индекс

Ои{Вр} и адрес '9'д микрокоманде М1(<%*).

Правило 4. Припишем микрокоманду МГ(«,г) микрокомандам М1(|5£") всех ветвей Ва е £>*(/«,), удовлетворяющих любому из условий:

[УС„ € С(С„): Ва <£ С„] л [ V*, е £>; (от,), р * а: -.(В, ■-» Ва )];

[ЭС„ 6 ): Ва с / „] А [ТО, е £>; ), (Вр с/„)у(Вг Я„)];

[ЭС, е С(СМ): Д, с 7^] л [ЧВ, е ££ (и,), Р * «: (В, <г /„ )] л

А['е Д! (ц ), Г * Ву с 7;: к* 5а )],

где ¡м, 1М — соответственно предусловная и постусловная части цикла С^. Считаем, что приписывание микрокоманде М1(|9^*) микрокоманды МГ(м,/) эквивалентно назначению произвольного адреса и такого индекса 0'и, который . отличается от индексов |Оц (В/з)} всех ветвей (например, 0[ =0).

В результате выполнения правил 1-4 возможно появление микрокоманд, которым приписаны сразу несколько начальных адресов. Для устранения подобной неоднозначности применяется следующее дополнительное правило. Правило 5. Выделим множество всех микрокоманд = {М1(|9^")},

которым приписаны индексы и адреса некоторого множества ветвей ¿'(/и,)с О*(от,). Выберем произвольную ветвь Ва е £>* (/я,), Ва ={Ои(Ва),К,,'&1,Зафиксируем адрес '9'а как базовый для множества ¿'(от,) и обозначим его через '£(Ь'и (от,)). Изменим начальные адреса ветвей ии(т,) (рФа) таким образом, чтобы выполнялось соотношение 'З'р = '9(Ь[ (от,)) + Д.9^ (¿„' (от,)), где Д^Д/У (от,))*0 - смещение ветви Вр относительно ветви Ва такое, что "9'0 еЕ(от,), причем А9у(£>1 (/и,)) Ф А9п (¿*(от,)) VВг, Вц е ¿'(от ),уФГ). Для каждой микрокоманды из М1Й. заменим ранее приписанный ей адрес парой ('^(¿^ (от,)), Д (¿,' (от,))),

полагая Д5а(о*(т,)) = 0.

После применения описанных правил конечные микрокоманды всех ветвей алгоритма будут помечены тройками вида |(о„(5;,),'5(Д,(от,)),Д|9а(^(/л1)))|

(каждая такая тройка кодируется отдельной микрокомандой управления координацией). Индекс Оа (В^) идентифицирует очередное множество

активизируемых ветвей, а пара ((¿„' (/я,)), А ( ¿* (от,))) задает их начальные

адреса с учетом значений логических условий. Адрес "^(¿¿(от,)) при этом

фиксирован, а смещение Д¿^(¿¿(от,)) однозначно определяется индексом 5

множества Кг такого, что (Вр е (у„ е Кх), А,^(¿¿(от,)) = $. Момент

активизации ветви Вр устанавливается аппаратно путем сравнения индекса

Оь (Д^) и номера цикла восстановления м;, для множества К1 (с учетом

вхождения вершины у„ в циклы) по формуле: 0„(Дв) = 1 + (и', сНу2-1)то<1|/^|.

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

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

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

Оценка созданного метода декомпозиции выполнялась на основе вычислительного эксперимента в программной среде, разработанной под руководством соискателя (свидетельство о государственной регистрации №2005613091). В ходе эксперимента осуществлялась генерация 1000 случайных ациклических алгоритмов и их декомпозиция разработанным методом, а также известными методами С.И.Баранова и А.Д.Закревского. Число вершин в каждом алгоритме— около 30, логических условий- 20, микроопераций- 20, число микрокоманд в микропрограмме не ограничивалось. Результаты декомпозиции сравнивались по числу лишних частных алгоритмов (микропрограмм), логических условий, микроопераций и связей между микропрограммами.

На рис.13 представлены полученные экспериментальные кривые распределения алгоритмов по числу лишних микропрограмм (кривая 1 соответствует разработанному методу, кривая 2 — методу А.Д.Закревского, кривая 3 — методу С.И.Баранова). Минимально возможное число микропрограмм определялось по (»-мощности базового сечения алгоритма.

Из рис.13 видно, что разработанный метод практически всегда (в 99% случаев) дает минимально возможное число микропрограмм. Метод Закревского лишь в 80% случаев обеспечивает декомпозицию без лишних микропрограмм, а метод Баранова— только в 26% случаев. Таким образом, число решений без лишних микропрограмм возрастает с 80% до 99%. Следует также отметить, что созданный метод порождает максимум одну лишнюю микропрограмму, в то время как аналоги нередко дают 2 и более таких микропрограмм. Избыточность в числе микропрограмм требует введения в мультиконтроллер дополнительных контроллеров, что увеличивает его аппаратную сложность. Кроме того, возрастает сложность сети связей между микропрограммами, что обусловливает рост числа коммуникационных микрокоманд и затрат памяти микропрограмм.

Аналогичные представленным на рис.13 распределения были получены для числа лишних логических условий, микроопераций и связей между микропрограммами. Установлено, что число решений без лишних логических условий увеличивается с 84% до 91%, число решений без лишних микроопераций повышается с 40% до 80%, а число решений без лишних связей возрастает с 60% до 65%. Дублирование логических условий, микроопераций и наличие избыточных связей может привести к нарушению технологических ограничений (3) и необходимости введения лишних микропрограмм.

Вывод асимптотической временной сложности процедуры декомпозиции выполнялся путем аналитической оценки предельной трудоемкости всех составляющих ее редукционных преобразований и процедур. Трудоемкость декомпозиции без учета размыкания циклов и поиска базового сечения асимптотически составляет о(ь>3 + иш1 + эквивалентных операций (ЭО), где и— число вершин алгоритма управления, а со — средняя су-мощность сечений

Предельная трудоемкость преобразования BaseSect равна о[и3/<у3] ЭО. Трудоемкость размыкания циклов зависит, кроме и и ¿у, от числа циклов е = ¡0(0,,)], и составляет в пределе о(и3е/ш2) ЭО.

Порядок полученных оценок совпадает с порядком предельной трудоемкости известных процедур декомпозиции. Абсолютные значения трудоемкости разработанной процедуры (по результатам вычислительного эксперимента на ПЭВМ с процессором Intel Celeron III, работающим на частоте 850 МГц, и объемом памяти 384 Мбайт) составляют 50...200 мс для алгоритмов, содержащих порядка 30-40 вершин, что вполне приемлемо для практики.

Число алгоритмов

1 ООО

Число лишних микропрограмм Рис.13

В заключении перечислены основные результаты и выводы диссертации.

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

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

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

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

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

2. Разработанная обобщенная математическая модель коллектива устройств управления координацией микропрограмм на основе композиции сетей Петри позволяет формализовать синтез и верификацию таких устройств для широкого класса топологических структур ЛМК.

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

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

5. Разработанные принципы структурной и функциональной организации устройств управления координацией микропрограмм и функциональные схемы контроллеров позволяют строить СБИС ЛМК для управления объектами широкого класса (патенты №2111528, №2112269, №2112272, №2116665, №2145434, №2146064, №2151421, №2152071 и др.).

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

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

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

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

9. Созданная визуальная программная среда имитационного моделирования (свидетельство о государственной регистрации №2006610308) обеспечивает возможность автоматизированного исследования динамических характеристик устройств ЛМК и дискретных систем более широкого класса. Среда построена на базе объектного подхода, что позволяет расширять ее функциональные возможности путем наращивания поддерживаемой иерархии абстракций.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Монографии

1. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления / И.В.Зотов, В.А.Колосков, В.С.Титов, И.В.Абузова. - Тула: ТулГУ, 1997.-226 с.

2. Организация и синтез микропрограммных мультимикроконтроллеров / И.В.Зотов, В.А.Колосков, В.С.Титов [и др.]. - Курск: КурскГТУ, 1999. - 368 с.

3. Архитектура и синтез параллельных логических мультимикроконтроллеров: в 2 ч./ И.В.Зотов, В.С.Титов, В.И.Штейнберг [и др.]. - Курск: КурскГТУ, 2006. -359 с.

Статьи

4. Зотов, И.В. Синхронизация параллельных параллельных процессов в микроконтроллерных сетях / И.В.Зотов, В.А.Колосков // Известия ТулГУ. Вычислительная техника. Автоматика. Управление. 1997. Т.1, вып.1. С. 33-36.

5. Зотов, И.В. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей / И.В.Зотов, В.А.Колосков, В.С.Титов // Автоматика и вычислительная техника. 1997. №5. С. 51-62.

6. Zotov, I.V. Allocation of control algorithms in unidirectional ring-type microcontroller networks / I.V .Zotov, V.A.Koloskov, V.S.Titov // Automatic Control and Computer Sciences. 1998. Vol.32, №3. P. 16-24.

7. Zotov, I.V. Procedure-logical routing model in microcontroller networks with matrix organization / I.V.Zotov // Automatic Control and Computer Sciences. 1999. Vol.33, №3. P. 48-56.

8. Зотов, И.В. Процедурно-логическая модель ретрансляции сообщений для распределенных вычислительных сетей / И.В.Зотов, Ю.В.Беляев // Телекоммуникации. 2000. №6. С. 18-23.

9. Зотов, И.В. Модель синхронизации параллельных управляющих процессов в

микроконтроллерных сетях с матричной организацией / И.В.Зотов // Автоматика и вычислительная техника. 2001. №3. С. 44-55.

Ю.Зотов, И.В. Модель синхронизации параллельных ветвей алгоритмов в микроконтроллерных сетях с шинной организацией / И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2001. №1. С. 26-30.

П.Зотов, И.В. Применение параллельных логических мультимикроконтроллеров в управлении роботизированными ячейками / И.В.Зотов, В.С.Титов // Известия ТулГУ. Вычислительная техника. Автоматика. Управление. 2001. Т.З, вып.1. С. 124-135.

12.Zotov, I.V. Model of fault-tolerant message routing for matrix-type microcontroller networks / I.V.Zotov // Automatic Control and Computer Sciences. 2002. Vol.36, №2. P. 15-26.

13.Борзов, Д.Б. Аппаратная реализация алгоритмов в параллельных системах с кольцевой структурой / Д.Б.Борзов, И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2003. Т.46, №3. С. 28-34.

Н.Ватутин, Э.И. Построение множества сечений в задаче оптимального разбиения параллельных управляющих алгоритмов / Э.И.Ватутин, И.В.Зотов, В.С.Титов // Известия ТулГУ. Вычислительная техника. Информационные технологии. Системы управления. 2003. Т.1, вып.2. С. 70-77.

15.Борзов, Д.Б. О субоптимальном размещении процессов и данных в кольцевых сетях / Д.Б.Борзов, И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2003. Т.46, №11. С. 48-54.

16.Ватутин, Э.И. Идентификация и разрыв последовательных циклов в задаче субоптимального разбиения параллельных управляющих алгоритмов / Э.И.Ватутин, И.В.Зотов // Известия ТулГУ. Вычислительная техника. Информационные технологии. Системы управления. 2004. Т.1, вып.З. С. 51-55.

17.Ватутин, Э.И. Параллельно-последовательный метод формирования субоптимальных разбиений / Э.И.Ватутин, И.В.Зотов // Информационные технологии моделирования и управления. 2004. Вып.12. С. 64-71.

18.Борзов, Д.Б. К задаче субоптимального разбиения параллельных алгоритмов / Д.Б.Борзов, Э.И.Ватугин, И.В.Зотов, В.С.Титов Н Известия вузов. Приборостроение. 2004. Т.47, №12. С. 34-39.

19.Абдель-Джалил, Дж.Н. Организация отказоустойчивого межпроцессорного взаимодействия в матричных мультикомпьютерах / Дж.Н.Абдель-Джалил, А.Аль-Хади, И.В.Зотов [и др.] // Известия ТулГУ. Бизнес-процессы и бизнесс-системы. 2006. Вып. 4. С. 3-9.

Изобретения

20.Патент №2110827, МКИ 6 G05B19/1S, G06F9/28. Дискретная микроконтроллерная сеть / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). — №97102528/09; заявлено 18.02.97; опубл. 10.05.98, Бюл. №13. - 24 с.

21.Патент №2111528, МКИ 6 G06F9/22. Микропрограммное устройство управления / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). - №97104623/09; заявлено 25.03.97; опубл. 20.05.98, Бюл. №14. - 21 с.

22.Патент №2112269, МКИ 6 G05B19/18. Модульное устройство для

программного управления / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). — №97105566/09 ; заявлено 9.04.97; опубл. 27.05.98, Бюл. №15. - 17 с.

23.Патент №2112272, МКИ 6 G06F9/22, 9/28. Модуль микроконтроллерной сети / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). - №97104368/09; заявлено 20.03.97; опубл. 27.05.98, Бюл. №15. - 20 с.

24.Патент №2116665, МКИ 6 G06F9/22. Модуль мультимикропрограммной системы / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). - №97102631/09; заявлено 18.02.97; опубл. 27.07.98, Бюл. №21. - 21 с.

25.Патент №2120135, МКИ 6 G05B19/18, G06F9/22. Мультимикроконтроллерная система / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97104702/09; заявлено 25.03.97; опубл. 10.10.98, Бюл. №28. - 24 с.

26.Патент №2145434, МКИ 7 G05B19/18, G06F9/22. Модуль системы программного управления / И.В.Зотов (РФ). - №98119803/09; заявлено 2.11.98; опубл. 10.02.2000, Бюл. №4. - 23 с.

27.Патент №2146064, МКИ 7 G05B19/18, G06F9/22. Устройство программного управления / И.В.Зотов (РФ). - №99101272/09; заявлено 19.01.99; опубл. 27.02.2000, Бюл. №6. - 18 с.

28.Патент №2151421, МКИ 7 G06F9/22. Модуль мультимикроконтроллерной сети / И.В.Зотов (РФ). - №99103655/09; заявлено 25.02.99; опубл. 20.06.2000, Бюл. №17.-24 с.

29.Патент №2152071, МКИ 7 G06F9/22, 9/28. Модуль системы микропрограммного управления / И.В.Зотов (РФ). - №99109080/09; заявлено 5.05.99; опубл. 27.06.2000, Бюл. №18. - 20 с.

30.Патент №2168198, МКИ 7 G05B19/05, G06F9/28. Микроконтроллерная сеть / И.В.Зотов (РФ). - №99119676/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15.-21 с.

31.Патент №2222044, МКИ 7 G06F15/173. Модуль для ретрансляции сообщений в коммутационной структуре / Ю.В.Беляев, Е.Г.Анпилогов, И.В.Зотов (РФ). -№2002108943/09; заявлено 8.04.2002; опубл. 20.01.2004, Бюл. №2. - 16 с.

32.Патент №2249849, МКИ 7 G06F15/163. Модуль для обмена сообщениями / А.А.Иванов, Е.Г.Анпилогов, И.В.Зотов, В.В.Ефремов (РФ). - №2003129963/09; заявлено 08.10.2003; опубл. 10.04.2005, Бюл. №10. - 19 с.

33.Патент №2280887, МКИ 8 G05B19/18, G06F9/28. Микроконтроллерная сеть / А.А.Иванов, Дж.Н.Абдель-Джалил, И.В.Зотов, С.В.Виноградов (РФ). -№2005104065/09; заявлено 15.02.2005; опубл. 27.07.2006, Бюл. №21.-26 с.

Материалы и тезисы докладов конференций

34.3отов, И.В. Организация средств синхронизации параллельных процессов в микроконтроллерных сетях / И.В.Зотов, В.А.Колосков, В.С.Титов // Электроника и информатика - 97: тезисы докладов 2-й Всероссийской научно-технической конференции с международным участием, Зеленоград, 25-26 ноября 1997 г. - М.: МИЭТ, 1997. 4.2. - С. 33.

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

технологии в науке, проектировании и производстве: тезисы докладов 1-й Всероссийской научно-технической конференции, Н. Новгород, 3-4 февраля 1999 г. - Н. Новгород: НГТУ, 1999. Ч. 12. - С. 29.

36.Зотов, И.В. Модель координации управляющих процессов в микропрограммных мультимикроконтроллерах с матричной организацией / И.В.Зотов, В.С.Титов И Идентификация систем и задачи управления: труды Международной конференции, Москва, 26-28 сентября 2000 г. — М.: ИПУ РАН, 2000. CD-ROM. - С. 2474-2482.

37.3отов, И.В. Морфологический синтез параллельных логических мультимикроконтроллеров / И.В.Зотов, В.С.Титов // Параллельные вычисления и задачи управления: труды Международной конференции, Москва, 2-4 октября 2001 г. - М. : ИПУ РАН, 2001. CD-ROM. - С. 101 -111.

38.3отов, И.В. Аппаратно-ориентированная процедура для разбиения параллельных алгоритмов / И.В.Зотов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы 6-й Международной научно-технической конференции, Курск, 22-25 октября 2003 г. - Курск: КурскГТУ, 2003. 4.2. -С. 225-227.

39.Vatutin, E.I. Method for the separation of a class of parallel algorithms with intermodule traffic optimization / E.I.Vatutin, Gihad Abdel Galil, I.V.Zotov // Proc. 2 Int. Conf. Information and Telecommunication Technologies in Intelligent Systems, Spain, Barcelona, 2004 May 22-29. - Barcelona, 2004. - P. 105-106.

40.Ватутин, Э.И. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов / Э.И.Ватутин, И.В.Зотов // Параллельные вычисления и задачи управления: труды Международной конференции, Москва, 4-6 октября 2004 г. - М.: ИПУ РАН, 2004. CD-ROM. - С. 884-917.

41.Ватутин, Э.И. Программная система для построения разбиений параллельных управляющих алгоритмов / Э.И.Ватутин, И.В.Зотов // Идентификация систем и задачи управления: труды Международной конференции, Москва, 28 января — 2 февраля 2006 г. - М.: ИПУ РАН, 2006. CD-ROM. - С. 2239-2250.

42. Vatutin, E.I. Comparison of methods for getting separation of parallel logic control algorithms / J.N.Abdel-Jalil, M.H. Najajra, I.V. Zotov // Proc. 4 Int. Conf. Information and Telecommunication Technologies in Intelligent Systems, Italy, Katania, 2006 May 27 - June 03. - Katania, 2006. - P. 92-94.

Подписано в печать 24 октября 2006 г. Формат 60x84 1/16.

Печ. л. 2.0. Тираж 100 экз. Заказ_.

Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета. 305040, г. Курск, ул. 50 лет Октября, 94.

Введение.

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

1.1. Задачи, алгоритмы и устройства логического управления.

1.2. Архитектура логических мультиконтроллеров.

1.2.1. Принципы организации логических мультиконтроллеров.

1.2.2. Архитектура контроллеров ЛМК.

1.2.3. Организация коммуникационных средств ЛМК.

1.3. Реализация алгоритмов логического управления в мультиконтроллерах.

1.3.1. Особенности и описание класса реализуемых алгоритмов.

1.3.2. Отображение алгоритмов управления на ЛМК.

1.3.3. Синтез и размещение компонентных микропрограмм.

1.3.4. Организация взаимодействия компонентных микропрограмм.

Выводы.

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

2.1. Обобщенная математическая модель коллектива устройств управления координацией.

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

2.1.2. Синтез топологической структуры коллектива устройств управления координацией.

2.1.3. Обобщенная математическая модель устройства управления координацией.

2.1.4. Синтез модели коллектива устройств управления координацией.

2.1.5. Интерпретация модели коллектива устройств управления координацией.

2.2. Процедуры распределенного децентрализованного управления координацией микропрограмм.

2.2.1. Процедура распределенной циклической рассылки.

2.2.2. Процедура активизации.

2.2.3. Обоснование корректности процедур управления координацией.

Выводы.

3. Организация и синтез устройств управления координацией микропрограмм и контроллеров на их основе.

3.1. Архитектура устройств управления координацией.

3.1.1. Организация коллектива устройств управления координацией.

3.1.2. Обобщенная архитектура устройства управления координацией.ИЗ

3.1.3. Особенности организации блоков управления активизацией микропрограмм.

3.1.4. Интерфейс управления координацией микропрограмм.

3.2. Метод синтеза устройств управления координацией.

3.2.1. Этапы синтеза и особенности их выполнения.

3.2.2. Схемная интерпретация переходов и позиций объединенной сети Петри.

3.3. Структурно-функциональная организация контроллеров с устройствами управления координацией.

3.3.1. Функциональные схемы контроллера матричного JIMK.

3.3.2. Форматы микрокоманд контроллера.

3.3.3. Процесс функционирования контроллера в составе матричного JIMK.

Выводы.

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

4.1. Порядок проведения сравнительной оценки.

4.1.1. Порядок оценки быстродействия коммуникационных средств.

4.1.2. Порядок оценки аппаратной сложности коммуникационных средств.

4.2. Результаты аналитического исследования.

4.2.1. Оценка быстродействия коммуникационных средств JIMK.

4.2.2. Оценка аппаратной сложности коммуникационных средств JIMK.

4.3. Организация и результаты вычислительного эксперимента.

4.3.1. Порядок проведения вычислительного эксперимента.

4.3.2. Архитектура инструментальных программных средств имитационного моделирования.

4.3.3. Результаты имитационного моделирования.

Выводы.

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

5.1. Постановка задач декомпозиции.

5.2. Параллельно-последовательный редукционный метод декомпозиции.

5.2.1. Общая характеристика метода. Основные определения.

5.2.2. Поиск базового сечения.

5.2.3. Организация перебора смежных сечений.

5.2.4. Межблочное распределение вершин сечений.

5.2.5. Особенности разбиения алгоритмов с циклами.

5.2.6. Процедура синтеза разбиения.

5.2.7. Синтез частных алгоритмов.

5.3. Синтез коллектива компонентных микропрограмм.

5.3.1. Типизация, структурирование, форматирование и распределение микрокоманд.

5.3.2. Правила разметки микропрограмм. Идентификация адресов перехода.

Выводы.

6. Сравнительная оценка методов декомпозиции алгоритмов логического управления.

6.1. Исследование качества получаемых решений.

6.1.1. Методика оценки качества решений. Постановка вычислительного эксперимента.

6.1.2. Архитектура инструментальных программных средств.

6.1.3. Результаты вычислительного эксперимента.

6.2. Оценка затрат времени на формирование разбиений.

6.2.1. Аналитическая оценка временной сложности процедур разбиения.

6.2.2. Оценка трудоемкости формирования разбиения.

Выводы.

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

Проблемы анализа и синтеза УЛУ на протяжении нескольких десятков лет остаются в центре внимания отечественных и зарубежных ученых. Их решению посвящено значительное число теоретических исследований, получен ряд важных для науки и практики результатов. Первые крупные научные результаты, послужившие основой современной теории логического управления, были достигнуты В.И.Шестаковым, М.А.Гавриловым, К.Э.Шенноном и А.Накашимой. Весомый вклад в развитие теории УЛУ внесли М.А.Айзерман, В.Л.Артюхов, О.Л.Бандман, С.И.Баранов, В.И.Варшавский,

A.Гилл, В.А.Горбатов, В.В.Девятков, А.Д.Закревский, О.П.Кузнецов,

B.Г.Лазарев, А.А.Ляпунов, Е.И.Пийль, Д.А.Поспелов, И.В.Прангишвили, Е.И.Пупырев, В.А.Скляров, А.А.Таль, А.А.Шалыто, В.С.Харченко,

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

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

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

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

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

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

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

Объект исследования диссертации - коммуникационные средства координации параллельных микропрограмм контроллеров ЛМК.

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

Связь темы диссертации с научно-техническими программами. Диссертационная работа выполнена в рамках программы П.Т.614 «Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности», приказ Министерства общего и профессионального образования Российской Федерации №572 от 02.03.98, а также совместных НИР с ОКБ «Авиаавтоматика» ОАО «Прибор» (г. Курск) по теме №1.121.03 от 22.08.03 и по договору подряда №19/480 от 01.07.04. Исследования поддержаны грантом Минобразования РФ «Столетовские гранты - 2003».

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

Задачи исследований'.

1. Выявление и анализ основных причин роста коммуникационной сложности координации параллельных микропрограмм в ЛМК.

2. Разработка обобщенной математической модели коллектива устройств управления координацией микропрограмм в ЛМК и формальных правил ее построения.

3. Создание формализованного метода синтеза устройств управления координацией для широкого класса топологических структур ЛМК.

4. Разработка аппаратно-ориентированных процедур распределенного децентрализованного управления координацией и доказательство их корректности.

5. Разработка функциональных схем устройств управления координацией и контроллеров ЛМК на их основе.

6. Сравнительная оценка быстродействия и аппаратной сложности устройств управления координацией.

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

Научная новизна работы:

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

2. Сформулированы формальные правила построения модели коллектива устройств управления координацией и метод синтеза указанных устройств, применимые к ЛМК с различными топологическими структурами.

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

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

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

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

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

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

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

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

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

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

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

2. Созданный метод декомпозиции вместе с правилами разметки микропрограмм обеспечивают сквозной логический синтез контроллеров ЛМК от алгоритмического описания объекта управления до набора непосредственно реализуемых компонентных микропрограмм, содержащих микрокоманды управления координацией, и позволяют минимизировать число образующихся лишних микропрограмм, логических условий, микроопераций и дополнительных микрокоманд. На основе вычислительного эксперимента установлено, что число решений без лишних микропрограмм, микроопераций, логических условий и дополнительных микрокоманд возрастает соответственно с 80% до 99%, с 40% до 80%, с 84% до 91% и с 60% до 65%.

3. Разработаны функциональные схемы контроллеров с устройствами управления координацией, обеспечивающие возможность реализации логических мультиконтроллеров в базисе СБИС (патенты №2111528, №2112269, №2112272, №2116665, №2145434, №2146064, №2151421, №2152071, №2166793, №2168198 и др.).

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

5. Разработана объектно-ориентированная визуальная программная среда имитационного моделирования, позволяющая выполнять автоматизированное исследование динамических характеристик и верификацию дискретных систем. Среда была успешно использована при оценке времени координации параллельных микропрограмм в ЛМК.

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

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

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

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

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

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

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

• оценки асимптотической временной сложности и трудоемкости процедуры декомпозиции;

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

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

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

• аналитическую верхнюю границу времени координации микропрограмм;

• зависимости времени координации микропрограмм от числа контроллеров в составе ЛМК;

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

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

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

Реализация результатов работы. Основные научные положения и выводы диссертационной работы реализованы при разработке комплекта программно-технических средств системы автоматического управления котлами малой мощности «Котел-М2М» в рамках совместных работ с ОКБ «Авиаавтоматика» ОАО «Прибор» (г. Курск, 2003-2005 гг.). Ряд результатов работы был использован при производстве изделий специализированным КБ программоуправляемых средств ОАО «Счетмаш» (г. Курск, 2001 г.). Кроме того, показана возможность практического применения метода декомпозиции алгоритмов логического управления при синтезе устройства управления роботизированной ячейкой для сборки электродвигателей малой мощности.

Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс на кафедре «Вычислительная техника» Курского государственного технического университета и используются при проведении занятий по дисциплинам «Организация ЭВМ и систем», «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров», а также в курсовом и дипломном проектировании, при подготовке магистерских диссертаций. Положения диссертации были использованы в качестве научно-методического пособия шестью выпускниками КурскГТУ при подготовке кандидатских диссертаций.

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

1. На Международной конференции «Параллельные вычисления и задачи управления» (Москва) в 2001 и 2004 годах.

2. На Международной конференции «Идентификация систем и задачи управления» (Москва) в 2000 и 2006 годах.

3. На Международной конференции «Information and Telecommunication Technologies in Intelligent Systems» (Барселона, Катанья) в 2004 и 2006 годах.

4. На Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза) в 1996, 1998 и 2000 годах.

5. На Международной электронной научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж) в 2000 году.

6. На Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (Нижний Новгород) в 1999 и 2000 годах.

7. На межвузовской научно-технической конференции «Управляющие и вычислительные системы. Новые технологии» (Вологда) в 2000 году.

8. На Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (Курск) в 1997, 1999, 2001, 2003, 2005 годах.

9. На научных семинарах кафедры вычислительной техники Курского государственного технического университета с 1998 по 2006 год.

Публикации. Содержание диссертации опубликовано в 85 работах, среди которых 3 монографии, 24 статьи, 20 патентов на изобретение, 3 свидетельства о государственной регистрации программы для ЭВМ. Основные из указанных публикаций перечислены в конце автореферата.

Личный вклад соискателя. Все выносимые на защиту научные положения разработаны соискателем лично. В основных научных работах по теме диссертации, опубликованных в соавторстве, личный вклад соискателя определяется следующим образом: в [33, 92, 94, 97, 104, 119, 182] разработаны теоретические основы создания устройств управления координацией параллельных микропрограмм в ЛМК, в [91] сформулированы правила определения адресов перехода при осуществлении межмодульных передач управления, в [27,45, 50, 100] произведена оценка сложности и быстродействия коммуникационных процедур и блоков, в [33, 47, 57-59, 64, 86, 96, 119, 182, 226] сформулированы основные положения созданного метода декомпозиции и преобразования управляющих алгоритмов в коллектив параллельных микропрограмм, в том числе в [33, 86, 119] проведен анализ корректности редукционных преобразований, в [65, 222, 223] сформулирована методика сравнительной оценки различных методов декомпозиции, в [99, 119] описано применение разработанного метода декомпозиции при синтезе устройства управления роботизированной сборочной ячейкой.

В совместно разработанных технических решениях по теме диссертации личный вклад соискателя заключается в следующем: в [121, 124, 126] спроектированы блоки управления синхронизацией микропрограмм, в [122, 127] предложены схемные решения по организации межмодульных взаимодействий в ЛМК, минимизирующие аппаратную сложность контроллеров, в [123, 140] разработаны форматы микрокоманд и схемы вычисления адресов переходов, в [137, 139] предложены схемы координации смежных модулей коммутатора ЛМК.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, приложений и списка литературы из 228 наименований. Работа содержит 383 страницы текста (с учетом приложений) и поясняется 75 рисунками и 10 таблицами.

Выводы

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

2. В результате вычислительного эксперимента установлено, что число разбиений без лишних микроопераций, логических условий и межблочных связей (дополнительных микрокоманд) возрастает по сравнению с рассмотренными аналогами соответственно с 40% до 80%, с 84% до 91% и с 60% до 65%.

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

Заключение

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

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

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

2. Разработанная обобщенная математическая модель коллектива устройств управления координацией микропрограмм на основе композиции сетей Петри позволяет формализовать синтез и верификацию таких устройств для широкого класса топологических структур ЛМК.

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

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

5. Разработанные принципы структурной и функциональной организации устройств управления координацией микропрограмм и функциональные схемы контроллеров позволяют строить СБИС ЛМК для управления объектами широкого класса (патенты №2111528, №2112269, №2112272, №2116665, №2145434, №2146064, №2151421, №2152071 и др.).

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

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

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

9. Созданная визуальная программная среда имитационного моделирования (свидетельство о государственной регистрации №2006610308) обеспечивает возможность автоматизированного исследования динамических характеристик устройств ЛМК и дискретных систем более широкого класса. Среда построена на базе объектного подхода, что позволяет расширять ее функциональные возможности путем наращивания поддерживаемой иерархии абстракций.

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

1. A.c. 1108447 СССР, МКИ 3 G06F9/22. Микропрограммное устройство управления модуля вычислительной системы / В.С.Харченко, В.А.Мельников, С.Н.Ткаченко и др. (СССР). №3538705/18-24; заявлено 11.01.83; опубл. 15.08.84, Бюл. №30. - 12 с.

2. A.c. 1133594 СССР, МКИ 4 G06F9/22. Мультимикропрограммная управляющая система / Н.Ф.Сидоренко, В.М.Свищ, Б.В.Остроумов и др. (СССР). -№3540119/24-24; заявлено 13.01.83; опубл. 07.01.85, Бюл. №1. 14 с.

3. A.c. 1133595 СССР, МКИ 4 G06F9/22, G06F11/00. Микропрограммное устройство управления / В.С.Харченко, В.А.Мельников, Г.Н.Тимонькин, С.Н.Ткаченко (СССР). №3587867/24-24; заявлено 04.05.83; опубл. 07.01.85, Бюл. №1.- Юс.

4. A.c. 1142832 СССР, МКИ 4 G06F9/22, G06F11/00. Микропрограммное устройство управления с контролем / В.С.Харченко, Г.Н.Тимонькин, С.Б.Никольский, С.Н.Ткаченко (СССР). №3587382/24-24; заявлено 04.05.83; опубл. 28.02.85, Бюл. №8. - 16 с.

5. A.c. 1168936 СССР, МКИ 4 G06F9/22. Микропрограммное устройство управления / В.С.Харченко, С.Б.Никольский, Г.Н.Тимонькин и др. (СССР). -№3599829/24-24; заявлено 03.06.83; опубл. 23.07.85, Бюл. №27. 11 с.

6. A.c. 1193675 СССР, МКИ 4 G06F9/22. Микропрограммный модуль / В.А.Мельников, В.Н.Самошин, Г.Н.Тимонькин, В.С.Харченко (СССР). -№3738231/24-24; заявлено 04.05.84; опубл. 23.11.85, Бюл. №43,- 14 с.

7. A.c. 1325477 СССР, МКИ 4 G06F9/22. Микропрограммное устройство для управления обменом управляющей информации в распределенной системе

8. Символами (*) помечены статьи соискателя, опубликованные в научных журналах из перечня ВАК

9. В.С.Харченко, В.А.Мельников, С.Б.Никольский и др. (СССР). -№4017608/24-24; заявлено 05.02.86; опубл. 23.07.87, Бюл. №27. 10 с.

10. A.c. 1427366 СССР, МКИ 4 G06F9/22. Микропрограммный модуль У В.С.Харченко, В.П.Улитенко, С.Н.Ткаченко и др. (СССР). №4117522/24-24; заявлено 22.05.86; опубл. 30.09.88, Бюл. №36. - 7 с.

11. A.c. 1508228 СССР, МКИ 4 G06F15/16. Устройство для формирования маршрута сообщения в однородной вычислительной системе / В.А.Мельников, В.С.Харченко, П.И.Кныш, С.Б.Кальченко (СССР). №4390961/24-24; заявлено 14.01.88; опубл. 15.09.89, Бюл. №34. - 8 с.

12. A.c. 1546979 СССР, МКИ 5 G06F9/22, 11/00. Мультимикропрограммное устройство для контроля и управления / В.С.Харченко, С.Б.Кальченко, Г.Н.Тимонькин и др. (СССР). №3975518/2424; заявлено 12.11.85; опубл. 28.02.90, Бюл. №8. - 17 с.

13. A.c. 1575167 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора / В.А.Мельников, П.И.Кныш, Ю.Н.Силантьев и др. (СССР). -№4486837/24-24; заявлено 26.09.88; опубл. 30.06.90, Бюл. №24. 6 с.

14. A.c. 1605212 СССР, МКИ 5 G05B19/18. Распределенная система для программного управления технологическими процессами / В.А.Мельников,

15. B.С.Харченко, С.А.Вуколов и др. (СССР). №4479408/24-24; заявлено 02.09.88; опубл.07.11.90, Бюл. №41. - 15 с.

16. A.c. 1631542 СССР, МКИ 5 G06F9/22, 9/00. Мультимикропрограммная управляющая система / А.А.Гремальский (СССР). -№4657004/24; заявлено 28.02.89; опубл. 28.02.91, Бюл. №8. 12 с.

17. A.c. 1647519 СССР, МКИ 5 G05B19/18. Модульное устройство для программного управления и контроля / В.С.Харченко, Г.Н.Тимонькин,

18. C.Н.Ткаченко и др. (СССР). №4615340/24; заявлено 02.12.88; опубл. 07.05.91, Бюл. №17.-9 с.

19. A.c. 1647566 СССР, МКИ 5 G06F9/22. Микропрограммное устройство управления / А.А.Гремальский (СССР). №4699062/24; заявлено 18.04.89; опубл. 07.05.91, Бюл. №17. - 10 с.

20. A.c. 1784940 СССР, МКИ 5 G05B19/18. Многоканальное устройство для программного управления технологическими процессами / В.А.Мельников, А.В.Галицкий, В.А.Леоненко, А.В.Дигоран (СССР). №4836146/24; заявлено 16.04.90; опубл. 30.12.92, Бюл. №48. - 12 с.

21. A.c. 1784943 СССР, МКИ 5 G05B19/18, 19/08. Устройство для программного управления и контроля / О.А.Лученко, А.В.Бек, М.А.Чернышов и др. (СССР). №4911769/24; заявлено 15.02.91; опубл. 30.12.92, Бюл. №48. -10 с.

22. A.c. 1793436 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора / В.А.Мельников, А.В.Галицкий, В.В.Копылов и др. (СССР). -№4893395/24; заявлено 30.10.90; опубл. 07.02.93, Бюл. №5. 8 с.

23. A.c. 1800445 СССР, МКИ 5 G05B19/18. Устройство для программного управления / Н.К.Байда, В.Н.Середа, В.С.Харченко и др. (СССР). -№4911773/24; заявлено 15.02.91; опубл.07.03.93, Бюл. №9. 10 с.

24. Абдель-Джалил, Дж.Н. Алгоритмы межпроцессорного взаимодействия в отказоустойчивых многопроцессорных системах Текст. / Дж.Н.Абдель-Джалил, Э.И.Ватутин, И.В.Зотов, А.А.Иванов // Методы и системы обработки информации. Муром, 2004. С. 117-125.

25. Абдель-Джалил, Дж.Н. Организация отказоустойчивого межпроцессорного взаимодействия в матричных мультикомпьютерах Текст. У Дж.Н.Абдель-Джалил, А.Аль-Хади, И.В.Зотов [и др.] // Известия ТулГУ. Бизнес-процессы и бизнесс-системы. 2006. Вып. 4. С. 3-9. (*)

26. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах Текст. / Под. ред. В.И. Варшавского. М.: Наука, 1986. -400 с.

27. Амбарцумян, А. А. Событийное логическое управление производственными процессами поточного типа Текст. / А. А. Амбарцумян, А. И. Потехин. М.: Ин-т проблем упр-я им. В.А.Трапезникова РАН, 2006. - 99 с.

28. Арсеньев, Ю.Н. Проектирование систем логического управления на микропроцессорных средствах Текст.: учеб. пособие / Ю.Н.Арсеньев. В.М.Журавлев. М.: Высшая школа, 1991. -319 с.

29. Артамонов, Г.Т. Топология регулярных вычислительных сетей и сред Текст. / Г.Т.Артамонов. М.: Радио и связь, 1985. - 192 с.

30. Архитектура и синтез параллельных логических мультимикроконтроллеров: в 2 ч. Текст. / И.В.Зотов, В.С.Титов,

31. B.И.Штейнберг и др.. Курск: КурскГТУ, 2006. - 359 с.

32. Ахо, А. Построение и анализ вычислительных алгоритмов Текст.: пер. с англ. / А.Ахо, Дж.Хопкрофт, Дж.Ульман. М.: Мир, 1979. - 536 с.

33. Баранов, С.И. Выбор разбиения при декомпозиции граф-схем алгоритмов Текст. / С.И.Баранов, Л.Н.Журавина, В.А.Песчанский И Автоматика и вычислительная техника. 1982. №2. С. 27-35.

34. Баранов, С.И. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем Текст. /

35. C.И.Баранов, Л.Н.Журавина, В.А.Песчанский // Автоматика и вычислительная техника. 1984. №5. С. 74-81.

36. Баранов, С.И. Обобщенный метод декомпозиции граф-схем алгоритмов Текст. / С.И.Баранов, Л.Н.Журавина, В.А.Песчанский // Автоматика и вычислительная техника. 1982. №5. С. 43-51.

37. Баранов, С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы) Текст. / С.И.Баранов. Л.: Энергия, 1979. - 232 с.

38. Баранов, С.И. Цифровые устройства на программируемых БИС с матричной структурой Текст. / С.И.Баранов, В.А.Скляров. М.: Радио и связь, 1986.-272 с.

39. Баркалов, A.A. Микропрограммные устройства управления с неявным заданием логических условий Текст. / А.А.Баркалов, С.И.Юсифов // Препр. АН УССР. Киев: Ин-т кибернетики им. В.М.Глушкова, 1990. - 27 с.

40. Беляев, Ю.В. Выбор оптимальных направлений ретрансляции сообщений в матричной коммуникационной сети Текст. / Ю.В.Беляев,

41. И.В.Зотов, П.В.Сусин // Управляющие и вычислительные системы. Новые технологии: материалы межвузовской электронной научно-технической конференции, Вологда, январь 2001 г. Вологда: ВоГТУ, 2001. - С. 47-48.

42. Борзов, Д.Б. Аппаратная реализация алгоритмов в параллельных системах с кольцевой структурой Текст. / Д.Б.Борзов, И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2003. Т.46, №3. С. 28-34. (*)

43. Борзов, Д.Б. К задаче субоптимального разбиения параллельных алгоритмов Текст. / Д.Б.Борзов, Э.И.Ватутин, И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2004. Т.47, №12. С. 34-39. (*)

44. Борзов, Д.Б. О субоптимальном размещении процессов и данных в кольцевых сетях Текст. / Д.Б.Борзов, И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2003. Т.46, №11. С. 48-54. (*)'

45. Васильев, В.В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем Текст. / В.В.Васильев, В.В.Кузьмук. Киев: Наукова думка, 1990. - 216 с.

46. Ватутин, Э.И. Параллельно-последовательный метод формирования субоптимальных разбиений Текст. / Э.И.Ватутин, И.В.Зотов // Информационные технологии моделирования и управления. 2004. Вып.12. С. 64-71. (*)

47. Ватутин, Э.И. Поиск базового сечения в задаче разбиения параллельных алгоритмов Текст. / Э.И.Ватутин, И.В.Зотов; Курск, КурскГТУ, 2003. 30 с. - Деп. в ВИНИТИ 24.11.2003, №2036-В2003.

48. Ватутин, Э.И. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов Текст. / Э.И.Ватутин, И.В.Зотов // Известия КурскГТУ. 2004. Т.13, №2. С. 85-89.

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

50. Международной конференции, Москва, 28 января 2 февраля 2006 г. - М.: Инт проблем упр-я им. В.А.Трапезникова РАН, 2006. CD-ROM. - С. 2239-2250.

51. Вашкевич, Н.П. Синтез микропрограммных управляющих автоматов Текст.: учеб. пособие / Н.П.Вашкевич. Пенза: ППИ, 1990. - 115 с.

52. Виноградов, C.B. Система имитационного моделирования средств барьерной синхронизации Текст. / С.В.Виноградов, И.В.Зотов // Системы управления и информационные технологии. Межвуз. сб. науч. трудов. Воронеж, 2002. Вып.9. С. 50-54.

53. Гаврилов, М.А. Логическое проектирование дискретных автоматов (языки, методы, алгоритмы) Текст. / М.А.Гаврилов, В.В.Девятков, Е.И.Пупырев. М.: Наука, 1977. - 352 с.

54. Гаврилов М.А. Теория релейно-контактных схем. Анализ и синтез структуры релейно-контактных схем. М., Л.: Изд-во АН СССР, 1950. - 255 с.

55. Горбатов, В.А. Логическое управление распределенными системами Текст. / В.А.Горбатов, М.И.Смирнов, И.С.Хлытчиев. М.: Энергоатомиздат, 1991.-288 с.

56. Горбатов, В.А. Логическое управление технологическими процессами Текст. / В.А.Горбатов, В.В.Кафаров, П.Г.Павлов. М.: Энергия, 1978. - 272 с.

57. Жинтелис, Г.Б. Автоматизация проектирования микропрограммируемых структур Текст. / Г.Б.Жинтелис, Э.К.Карчяускас, Э.К.Мачикенас. Л.: Машиностроение, 1985. - 216 с.

58. Закревский, А.Д. Декомпозиция параллельных алгоритмов логического управления по заданному разбиению множества предложений Текст. / А.Д.Закревский, Ю.В.Поттосин // Автоматика и вычислительная техника. 1985. №4. с. 65-72.

59. Закревский, А.Д. К теории параллельных алгоритмов логического управления Текст. / А.Д.Закревский // Известия АН СССР. Техн. кибернетика. 1989. №5. С. 179-191.

60. Закревский, А.Д. Логические уравнения с приложениями в автоматизированном проектировании и управлении Текст. / А.Д.Закревский // Автоматика и телемеханика. 2004. №4. С. 173-184.

61. Закревский, А.Д. О корректности параллельных алгоритмов логического управления Текст. / А.Д.Закревский // Известия АН СССР. Техн. кибернетика. 1987. №4. С. 106-112.

62. Закревский, А.Д. Реализация на программируемых логических матрицах параллельных алгоритмов логического управления Текст. / А.Д.Закревский // Автоматика и телемеханика. 1983. №7. С. 116-123.

63. Закревский, А.Д. Параллельные алгоритмы логического управления Текст. / А.Д.Закревский. М.: УРСС: Едиториал УРСС, 2003. - 200 с.

64. Закревский, А.Д. Полиномиальная реализация частичных булевых функций и систем Текст. / А.Д.Закревский, Н.Р.Торопов. М.: УРСС, 2003. -200 с.

65. Заявка WO 86/04700, МКИ 4 G06F9/22. Microprogrammable devices using transparent latch / D.Garde (США). №PCT/US86/00243; заявлено 04.02.86; опубл. 14.08.86.-32 с.

66. Зотов, И.В. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов // Автоматика и вычислительная техника. 1997. №5. С. 51-62.

67. Зотов, И.В. Метод размещения алгоритмов логического управления в микроконтроллерных сетях с кольцевой структурой Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов; Курск, КурскГТУ, 1997. 26 с. - Деп. в ВИНИТИ 14.05.97, №1599-В97.

68. Зотов, И.В. Модель синхронизации параллельных ветвей алгоритмов в микроконтроллерных сетях с шинной организацией Текст. / И.В.Зотов, В.С.Титов // Известия вузов. Приборостроение. 2001. №1. С. 26-30. (*)

69. Зотов, И.В. Модель синхронизации параллельных управляющих процессов в микроконтроллерных сетях с матричной организацией Текст. / И.В.Зотов // Автоматика и вычислительная техника. 2001. №3. С. 44-55.

70. Зотов, И.В. Организация средств синхронизации параллельных процессов в микроконтроллерных сетях Текст. / И.В.Зотов, В.А.Колосков,

71. B.С.Титов // Электроника и информатика 97: тезисы докладов 2-й Всероссийской научно-технической конференции с международным участием, Зеленоград, 25-26 ноября 1997 г. - М.: МИЭТ, 1997. 4.2. - С. 33.

72. Зотов, И.В. Применение параллельных логических мультимикроконтроллеров в управлении роботизированными ячейками Текст. / И.В.Зотов, В.С.Титов // Известия ТулГУ. Вычислительная техника. Автоматика. Управление. 2001. Т.З, вып.1. С. 124-135, (*)

73. Зотов, И.В. Процедурно-логическая модель ретрансляции сообщений для распределенных вычислительных сетей Текст. / И.В.Зотов, Ю.В.Беляев // Телекоммуникации. 2000. №6. С. 18-23. (*)

74. Зотов, И.В. Псевдопараллельный метод декомпозиции параллельных алгоритмов логического управления Текст. / И.В.Зотов, В.А.Колосков,

75. B.С.Титов; Курск, КурскГТУ, 1996. 22 с. - Деп. в ВИНИТИ 17.07.96, №2438-В96.

76. Зотов, И.В. Синхронизация параллельных параллельных процессов в микроконтроллерных сетях Текст. / И.В.Зотов, В.А.Колосков // Известия ТулГУ. Вычислительная техника. Автоматика. Управление. 1997. Т.1, вып.1. С. 33-36. (*)

77. Кёниг, Р. Декомпозиция сети Петри при проектировании дискретных устройств на основе стандартных модулей Текст. / Р.Кёниг, Г.Ф.Фрицнович И Автоматика и вычислительная техника. 1984. №1. С. 82-91.

78. Ковалев, A.B. К декомпозиции параллельных алгоритмов логического управления Текст. / А.В.Ковалев, Ю.В.Поттосин // Автоматика и вычислительная техника. 1988. №1. С. 8-13.

79. Колосков, В.А. Архитектура отказоустойчивых сетей самонастраиваемых микроконтроллеров Текст. / В.А.Колосков, В.С.Титов. -Курск: КурскГТУ, 1995. 176 с.

80. Кондратьев, В.Н. Реализация систем булевых функций с использованием линейных арифметических полиномов Текст. / В.Н.Кондратьев, А.А.Шалыто // Автоматика и телемеханика. 1993. №3. С. 135151.

81. Котов, В.Е. Сети Петри. М.: Наука, Гл. ред. физ.-мат. л-ры, 1984. -160 с.

82. Кравцов, Л.Я. Проектирование микропрограммных устройств управления Текст. / Л.Я.Кравцов, Г.И.Черницкий. Л.: Энергия, 1976. - 148 с.

83. Кристофидес, Н. Теория графов. Алгоритмический подход Текст. / Н.Кристофидес. М.: Мир, 1978. - 432 с.

84. Кузнецов, Б.П. Метод независимых фрагментов для построения линеаризованных структурированных граф-схем алгоритмов, реализующих системы булевых формул Текст. / Б.П.Кузнецов, А.А.Шалыто // Автоматика и телемеханика. 1998. №9. с. 142-154.

85. Кузнецов, Б.П. Реализация булевых формул линейными бинарными графами. I. Синтез и анализ Текст. / Б.П.Кузнецов, А.А.Шалыто // Изв. РАН. Техн. кибернетика. 1994. №5. С. 132-142.

86. Кюблер, Ф.-Д. Системы логического управления на базе транспьютерных сетей Текст. / Ф.-Д.Кюблер, К.Х.Пагиев, П.Б.Панфилов // Информационные процессы, технологии, системы, коммуникации и сети. М.: Международная академия информатизации, 1995. С. 54-59.

87. Лазарев, В.Г. Построение программируемых управляющих устройств Текст. / В.Г.Лазарев, Е.И.Пийль, Е.Н.Турута. М.: Энергоатомиздат, 1984. -192 с.

88. Лазарев, В.Г. Синтез управляющих автоматов Текст. / В.Г.Лазарев, Е.И.Пийль. М.: Энергоатомиздат, 1989. - 328 с.

89. Организация и синтез микропрограммных мультимикроконтроллеров Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов [и др.]. Курск: КурскГТУ, 1999. -368 с.

90. Палагин, A.B. Реализация микропрограммных автоматов на ПЛИС Текст. / А.В.Палагин, А.А.Баркалов, С.И.Юсифов [и др.] // Управляющие системы и машины. 1991. №8. С. 18-22.

91. Патент №2110827 РФ, МКИ 6 G05B19/18, G06F9/28. Дискретная микроконтроллерная сеть / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97102528/09; заявлено 18.02.97; опубл. 10.05.98, Бюл. №13. 24 с.

92. Патент №2111528 РФ, МКИ 6 G06F9/22. Микропрограммное устройство управления / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97104623/09; заявлено 25.03.97; опубл. 20.05.98, Бюл. №14.-21 с.

93. Патент №2112269 РФ, МКИ 6 G05B19/18. Модульное устройство для программного управления / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97105566/09 ; заявлено 9.04.97; опубл. 27.05.98, Бюл. №15. 17 с.

94. Патент №2112272 РФ, МКИ 6 G06F9/22, 9/28. Модуль микроконтроллерной сети / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97104368/09; заявлено 20.03.97; опубл. 27.05.98, Бюл. №15.-20 с.

95. Патент №2116664 РФ, МКИ 6 G06F7/00, G06F15/163. Модуль матричного коммутатора / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№96108431/09; заявлено 24.04.96; опубл. 27.07.98, Бюл. №21. 13 с.

96. Патент №2116665 РФ, МКИ 6 G06F9/22. Модуль мультимикропрограммной системы / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97102631/09; заявлено 18.02.97; опубл. 27.07.98, Бюл. №21.-21 с.

97. Патент №2120135 РФ, МКИ 6 G05B19/18, G06F9/22. Мультимикроконтроллерная система / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97104702/09; заявлено 25.03.97; опубл. 10.10.98, Бюл. №28. 24 с.

98. Патент №2133054 РФ, МКИ 6 С05В19/18, 006Р9/28. Распределенная система для программного управления / Л.М.Миневич, А.В.Медведев, М.В.Медведева, И.В.Зотов и др.. (РФ). №98108934/09; заявлено 13.05.98; опубл. 10.07.99, Бюл. №19. - 16 с.

99. Патент №2145434 РФ, МКИ 7 С05В19/18, С06Р9/22. Модуль системы программного управления / И.В.Зотов (РФ). №98119803/09; заявлено 2.11.98; опубл. 10.02.2000, Бюл. №4.-23 с.

100. Патент №2146064 РФ, МКИ 7 005В19/18, 006Р9/22. Устройство программного управления / И.В.Зотов (РФ). -№99101272/09; заявлено 19.01.99; опубл. 27.02.2000, Бюл. №6. 18 с.

101. Патент №2151421 РФ, МКИ 7 С06Р9/22. Модуль мультимикроконтроллерной сети / И.В.Зотов (РФ). №99103655/09; заявлено 25.02.99; опубл. 20.06.2000, Бюл. №17. - 24 с.

102. Патент №2152071 РФ, МКИ 7 С06Р9/22, 9/28. Модуль системы микропрограммного управления / И.В.Зотов (РФ). №99109080/09; заявлено 5.05.99; опубл. 27.06.2000, Бюл. №18.-20 с.

103. Патент №2168198 РФ, МКИ 7 С05В19/05, 006Р9/28. Микроконтроллерная сеть / И.В.Зотов (РФ). №99119676/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15.-21 с.

104. Патент №2168204 РФ, МКИ 7 С06Р15/173; Н03К17/56. Модуль матричного коммутатора / К.А.Попов, И.В.Зотов, В.С.Титов (РФ). № 99119675/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15.-11 с.

105. Патент №2168755 РФ, МКИ 7 С06Р13/14, 15/163. Модуль матричной коммуникационной сети / И.В.Зотов (РФ). №2000106883/09; заявлено 20.03.2000; опубл. 10.06.2001, Бюл. №16.-41 с.

106. Патент №2222044 РФ, МКИ 7 G06F15/173. Модуль для ретрансляции сообщений в коммутационной структуре / Ю.В.Беляев, Е.Г.Анпилогов, И.В.Зотов (РФ). №2002108943/09; заявлено 8.04.2002; опубл. 20.01.2004, Бюл. №2.- 16 с.

107. Патент №2249848 РФ, МКИ 7 G06F15/163. Модуль для передачи и вещания сообщений в матричном коммутаторе / Е.Г.Анпилогов, Ю.В.Беляев, И.В.Зотов (РФ). №2003104071/09; заявлено 11.02.2003; опубл. 10.04.2005, Бюл. №10.-23 с.

108. Патент №2249849 РФ, МКИ 7 G06F15/163. Модуль для обмена сообщениями / А.А.Иванов, Е.Г.Анпилогов, И.В.Зотов, В.В.Ефремов (РФ). -№2003129963/09; заявлено 08.10.2003; опубл. 10.04.2005, Бюл. №10. 19 с.

109. Патент №2280887 РФ, МКИ 8 G05B19/18, G06F9/28. Микроконтроллерная сеть / А.А.Иванов, Дж.Н.Абдель-Джалил, И.В.Зотов, С.В.Виноградов (РФ). №2005104065/09; заявлено 15.02.2005; опубл. 27.07.2006, Бюл. №21.-26 с.

110. Патент №4719565 США, МКИ 4 G06F13/32. Interrupt and trap handling in microprogram sequencer / O.H.Moller (С1ПА). №667242; заявлено 01.11.84; опубл. 12.01.88.-13 с.

111. Патент №4799151 США, МКИ 4 G06F9/22. Microprogram control circuit / Toshio Iwao (Япония). №942785; заявлено 17.12.86; опубл. 17.01.89. - 9 с.

112. Патент №4821183 США, МКИ 4 G06F9/30. A microsequencer circuit with plural microprogram instruction counters / J.F. Hauris (США). №937772; заявлено 04.12.86; опубл. 11.04.89. - 9 с.

113. Патент №4984151 США, МКИ 5 G06F9/26. Flexible, next-address generation microprogram sequencer / V.Dujari (США). №227452; заявлено 02.08.88; опубл. 08.01.91.- 12 c.

114. Патент №5144628 США, МКИ 5 G06F11/10. Microprogram controller in data processing apparatus / S.Sekiguchi (Япония). №416977; заявлено 04.10.89; опубл. 01.09.92.- Юс.

115. Патент №5148525 США, МКИ 5 G06F9/22. Microprogram-controlled type bus control circuit / S.Ohga, T.Yamazaki (Япония). №817997; заявлено 09.01.92; опубл. 15.09.92. - 8 с.

116. Патент №5151996 США, МКИ 5 G06F15/16. Multi-dimensional message transfer router / W.D.Hillis (США). №497003; заявлено 20.03.90; опубл. 29.09.92. - 44 с.

117. Патент №5333279 США, МКИ 5 G06F13/14. Self-timed mesh routing chip with data broadcasting / D.Dunning (США). №892535; заявлено 01.06.92; опубл. 26.07.94.- 17 c.

118. Патент №5345570 США, МКИ 5 G06F9/30. Microprogram control circuit / Y.Azekawa (Япония). №862010; заявлено 01.04.92; опубл. 06.09.94. - 19 с.

119. Патент №5434995 США, МКИ 6 G06F15/16, 15/80. Barrier synchronization for distributed memory massively parallel processing systems / S.M.Oberlin, E.C.Fromm (США).-№165265; заявлено 10.12.93; опубл. 18.07.95.-25 с.

120. Патент №5553301 США, МКИ 6 G06F13/20. Programmable sequencer having internal components which are microprocessor read/write interfacable / B.J.New, P.Freidin (США). №024819; заявлено 01.03.93; опубл. 03.09.96. - И с.

121. Патент №5752066 США, МКИ 6 G06F9/00. Data processing system utilizing programmable microprogram memory controller / R.Bealkowski, B.M.Ozaki (США). -№695946; заявлено 13.08.96; опубл. 12.05.98. 7 с.

122. Патент №5765007 США, МКИ 6 G06F9/22. Microinstruction sequencer having multiple control stores for loading different rank registers in parallel / M.M.Rahman, R.W.Horst, R.Harris (США). №976304; заявлено 13.11.92; опубл. 09.06.98.-38 с.

123. Патент №5941986 США, МКИ 6 G06F9/22. Micro-code sequencer with branch-taken and branch-not-taken micro-code vectors sharing common address to eliminate taken branch penalties / U.M.Kulkarni (США). №055971; заявлено 03.04.93; опубл. 24.08.99. - 18 с.

124. Патент №6085303 США, МКИ 7 G06F15/16. Serialized race-free virtual barrier network / G.Thorson, R.S.Passint, S.L.Scott (США). №972010; заявлено 17.11.97; опубл. 04.07.2000. - 22 с.

125. Патент №6715065 США, МКИ 7 G06F9/00, 9/44. Micro program control method and apparatus thereof having branch instructions / A.Ebata, M.Yamamoto, T.Kato (Япония). -№539898; заявлено 31.03.2000; опубл. 30.03.2004. 28 с.

126. Патент №7058062 США, МКИ 8 H04L12/56. Packet switching system having self-routing switches / S.Tanabe, T.Suzuki, S.Gohara et al. (Япония). -№040466; заявлено 09.01.2002; опубл. 06.06.2006. 29 с.

127. Патент №7080156 США, МКИ 8 G06F15/173. Message routing in a torus interconnect / W.S.Lee, N.Talagala, F.Chong(Jr.) et al. (США). №104923; заявлено 21.03.2002; опубл. 18.07.2006. - 17 с.

128. Прангишвили, И.В. Основы построения АСУ сложными технологическими процессами Текст. / И.В.Прангишвили, А.А.Амбарцумян. -М.: Энергоатомиздат, 1994. 305 с.

129. Свидетельство о регистрации программы для ЭВМ №2006610308. Библиотека классов для имитационного моделирования коммуникационных сетей / Э.И.Ватутин, И.В.Зотов (РФ). М.: РосПатент; заявлено 22.10.2005; дата регистрации 16.01.2006.

130. Скляров, В.А. Синтез автоматов на матричных БИС Текст. / В.А.Скляров. Минск: Наука и техника, 1984. - 287 с.

131. Советов, Б .Я. Моделирование систем Текст.: учеб. пособие / Б.Я.Советов, С.А.Яковлев. М.: Высшая школа, 2005. - 343 с.

132. Соловьев, В.В. Программируемые логические интегральные схемы и их применение Текст. / В.В.Соловьев, А.Г.Васильев. Минск: Беларуская навука, 1998.-270 с.

133. Соловьев, В.В. Реализация на программируемых матрицах логики параллельных алгоритмов логического управления Текст. / В.В.Соловьев II Управляющие системы и машины. 1995. №6. С. 24-30.

134. Соловьев, В.В. Синтез иерархических схем параллельных устройств логического управления из ПЛИС Текст. / В.В.Соловьев // Автоматика и вычислительная техника. 1995. №6. С. 3-15.

135. Соловьев, В.В. Синтез конечных автоматов на программируемых матрицах логики Текст. / В.В.Соловьев // Автоматика и вычислительная техника. 1997. №2. С. 65-74.

136. Степанян, С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. / С.О.Степанян // Автоматика и вычислительная техника. 1987. №3. С. 31-43.

137. Сусин, П.В. Коммутатор с распределенными выходными очередями для параллельных систем логического управления: дис.канд. техн. наук: 05.13.05: защищена 20.06.2003: утв. 14.11.2003 / Сусин Павел Викторович. -Курск, 2003.-220 с.

138. Сусин, П.В. Модель буферного элемента коммутационной структуры Текст. / П.В.Сусин, И.В.Зотов, В.С.Титов // Современные проблемы информатизации в непромышленной сфере и экономике: труды 5-й

139. Международной электронной научной конференции, Воронеж, октябрь 1999 г. -апрель 2000 г. Воронеж: ЦЧКИ, 2000. - С. 133-134.

140. Тимонькин, Г.Н. Методы аппаратной поддержки логических алгоритмов в микропроцессорных системах Текст. / Г.Н. Тимонькин, С.Ф.Тюрин, В.С.Харченко // Управляющие системы и машины. 1993. №1. С. 55-62.

141. Ш.Угрюмов, Е.П. Цифровая схемотехника Текст.: учеб. пособие / Е.П.Угрюмов. СПб.: БХВ-Петербург, 2004. - 800 с.

142. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов, И.В.Абузова. Тула: ТулГУ, 1997. - 226 с.

143. Харченко, B.C. Декомпозиция параллельных матричных схем алгоритмов в задачах синтеза микроконтроллерных сетей Текст. / В.С.Харченко, С.Б.Кальченко, А.Е.Сазонов // Автоматика и вычислительная техника. 1990. №4. С. 81-89.

144. Харченко, B.C. Один подход к синтезу дискретных микроконтроллерных сетей Текст. / В.С.Харченко, С.Б.Никольский,

145. A.Е.Сазонов// Автоматика и вычислительная техника. 1989. №4. С. 87-95.

146. Харченко, B.C. Принципы построения и оценка эффективности встроенных микроконтроллеров с программируемой синхронизацией Текст. /

147. B.С.Харченко, П.Е.Марков // Управляющие системы и машины. 1992. №3/4.1. C. 53-59.

148. Хассон, С. Микропрограммное управление Текст.: пер. с англ. / С.Хассон. М.: Мир, 1974. - 717 с.

149. Черемисинова, Jl.Д. Реализация параллельных алгоритмов логического управления Текст. / Л.Д.Черемисинова. Минск: Ин-т техн.кибернетики НАН Беларуси, 2002. - 246 с.

150. Шалыто, А.А. Алгоритмизация и программирование задач логического управления Текст. / А.А.Шалыто. СПб: СПбГУ ИТМО, 1998. -56 с.

151. Шалыто, А.А. Логическое управление. Методы аппаратной и программной реализации Текст. / А.А.Шалыто. СПб.: Наука, 2000. - 780 с.

152. Юдицкий, С.А. Логическое управление дискретными процессами. Модели, анализ, синтез Текст. / С.А.Юдицкий, В.З.Магергут. М.: Машиностроение, 1987. - 176 с.

153. Юдицкий, С.А. Проектирование дискретных систем автоматики Текст. / С.А.Юдицкий, А.А.Тагаевская, Т.К.Ефремова. М.: Машиностроение, 1980.-232 с.

154. Arenstorf, N.S. Comparing barrier algorithms Текст. / N.S.Arenstorf, H.F.Jordan // Parallel Comput. 1989. №12. P. 157-170.

155. Axelrod, T.S. Effects of synchronization barriers on multiprocessor performance Текст. / T.S.Axelrod // Parallel Comput. 1986. №3. P. 129-140.

156. Chu, W.W. Task allocation in distributed data processing Текст. / W.W.Chu, L.J.Holloway, M.-T.Lan, K.Efe // IEEE Computer. 1980. №11. P. 57-69.

157. Cohen, W.E. An optical bus-based distributed dynamic barrier mechanism Текст. / W.E.Cohen, D.W.Hyde, R.K.Gaede // IEEE Trans. Comput. 2000. Vol.49, №12. P. 1354-1365.

158. Cole, B.C. Altera makes it easier to build fast state machines Текст. / B.C.Cole // Electronics. 1987. №6. P. 76-78.

159. Feldmann, A. Subset barrier synchronization on a private-memory parallel system Текст. / A.Feldmann, T.Gross, D.O'Hallaron, T.M.Stricker // Proc. ACM Symp. Parallel Algor. Architect. (SPAA92), San Diego, June 29 July 1 1992. -ACM, 1992.-P. 209-218.

160. Hensgen, D. Two algorithms for barrier synchronization Текст. / D.Hensgen, R.Finkel, U.Manber // Intl J. Parallel Programming. 1988. Vol.17, №1. P. 1-12.

161. Keshav, S. Issues and trends in router design Текст. / S.Keshav, R.Sharma // IEEE Communications Magazine. 1998. Vol.36, №5. P. 144-151.

162. Kunde, M. Packet routing on grids of processors / M.Kunde // Lecture Notes in Computer Science. 1988. Vol.401. P. 129-136.

163. Mekkittikul, A. A practical scheduling algorithm to achieve 100% throughput in input-queued switches Текст. / A.Mekkittikul, N.McKeown // Proc. INFO

164. COM-98, San Francisco, 29 March 2 April 1998. - San Francisco, 1998, Vol.2. -P. 792-799.

165. Microprogram controller CAST C49410 Altera megafunction. Datasheet. -CAST Inc., 2004.-2 p.

166. Microprogram controller IA2910A. Preliminary datasheet. InnovASIC Inc., 1999.-19 p.

167. Moh, S. Four-ary tree-based barrier synchronization for 2d meshes without nonmember involvement Текст . / S.Moh, C.Yu, B.Lee [et al]. // IEEE Trans. Corn-put. 2001. Vol.50, №8. P. 811-823.

168. Muntean, T. Methodes de placement statique des processus sur architectures paralleles Текст. / Т. Muntean, E.-G.Talbi // Techn. et Sci. Inf. (TSI). 1991. Vol.10, №5. P. 355-373.

169. O'Boyle, M. Compile time barrier synchronization minimization Текст. / M.O'Boyle, E.Stohr // IEEE Trans. Parallel Distrib. Systems. 2002. Vol.13, №6. P. 529-543.

170. O'Keefe, M.T. Hardware barrier synchronization: dynamic barrier MIMD (DBM) Текст. / M.T.O'Keefe, H.G.Dietz // Proc. Intl Conf. Parallel Processing, August 1990, Urbana-Champaign. Pennsylvania State University Press, 1990. Vol.1.-P. 43-46.

171. O'Keefe, M.T. Hardware barrier synchronization: static barrier MIMD (SBM) Текст. / M.T.O'Keefe, H.G.Dietz // Proc. Intl Conf. Parallel Processing, August 1990, Urbana-Champaign. Pennsylvania State University Press, 1990. Vol.1. -P. 35-42.

172. Programmable logic sequencers PLUS405-37/-45. Product specification. 1С 13 Data Handbook. Philips Semiconductors, 1996. - 20 p.

173. Programming Languages С++. International Standard. - ISO/IEC 14882, 1998.-776 p.

174. Sampson,J. Fast synchronization for chip multiprocessors Text. / J.Sampson, R.Gonzalez, J.-F.Collard [et al] // SIGARCH Computer Architecture News. 2005. Vol.33, №4. P. 64-69.

175. Shang, S.S. Distributed hardwired barrier synchronization for scalable multiprocessor clusters Текст. / S.S.Shang, K.Hwang // IEEE Trans. Parallel Distrib. Systems. 1995. Vol.6, №6. P. 591-605.

176. Sivaram, R. A reliable hardware barrier synchronization scheme Текст. / R.Sivaram, C.B.Stunkel, D.K.Panda // Proc. 11 Intl Parallel Processing Symp. (IPPS-97), Geneva, 1-5 April 1997. Los Alamitos: IEEE Computer Society, 1997. -P. 274-280.

177. Stratix II. 90-nm high-performance & high-density FPGAs. Stratix II Brochure. February 2004. ALTERA, 2004. - 8 p.

178. Sun, Y. Barrier synchronization on wormhole-routed networks Текст. / Y.Sun, P.Y.S.Cheung, X.Lin // IEEE Trans. Parallel Distrib. Systems. 2001. Vol.12, №6. P. 583-597.

179. Tarek, E.-G. A general framework for developing adaptive fault-tolerant routing algorithms Текст. / E.-G.Tarek, Y.Abdou // IEEE Trans. Reliab. 1993. Vol.42, №2. P. 250-258.

180. Tobagi, F.A. Fast packet switch architectures for broadband integrated services digital networks Текст. / F.A.Tobagi // Proc. IEEE. 1990. Vol.78, №1. P. 133167.

181. Wu, S.S. Heuristic algorithms for task assignment and scheduling in a processor network Текст. / S.S.Wu, D.Sweeting // Parallel Computing. 1994. №20. P. 1-14.

182. Yang, J.S. Designing tree-based barrier synchronization on 2D mesh networks Текст. / J.S.Yang, C.T.King // IEEE Trans. Parallel Distrib. Systems. 1998. Vol.9, №6. P. 526-533.

183. Zotov, I.V. Allocation of control algorithms in unidirectional ring-type microcontroller networks Текст. / I.V.Zotov, V.A.Koloskov, V.S.Titov // Automatic Control and Computer Sciences. 1998. Vol.32, №3. P. 16-24.

184. Zotov, I.V. Model of fault-tolerant message routing for matrix-type microcontroller networks Текст. / I.V.Zotov // Automatic Control and Computer Sciences. 2002. Vol.36, №2. P. 15-26.

185. Zotov, I.V. Procedure-logical routing model in microcontroller networks with matrix organization Текст. / I.V.Zotov // Automatic Control and Computer Sciences. 1999. Vol.33, №3. P. 48-56.315