Содержание к диссертации
Введение
1. Задачи логического управления и их решение в базисе логических мультиконтроллеров ...20
1.1. Задачи, алгоритмы и устройства логического управления 20
1.2. Архитектура логических мультиконтроллеров 26
1.2.1. Принципы организации логических мультиконтроллеров 26
1.2.2. Архитектура контроллеров ЛМК 28
1.2.3. Организация коммуникационных средств ЛМК 31
1.3. Реализация алгоритмов логического управления в мультиконтроллерах 39
1.3.1. Особенности и описание класса реализуемых алгоритмов 39
1.3.2. Отображение алгоритмов управления на ЛМК 48
1.3.3. Синтез и размещение компонентных микропрограмм 52
1.3.4. Организация взаимодействия компонентных микропрограмм 56
Выводы 69
2. Организация распределенного децентрализованного управления координацией микропрограмм в логических мультиконтроллерах 71
2.1. Обобщенная математическая модель коллектива устройств управления координацией 71
2.1.1. Формализация представления процесса координации параллельных ветвей (микропрограмм) 72
2.1.2. Синтез топологической структуры коллектива устройств управления координацией 87
2.1.3. Обобщенная математическая модель устройства управления координацией 88
2.1.4. Синтез модели коллектива устройств управления координацией 91
2.1.5. Интерпретация модели коллектива устройств управления координацией 95
2.2. Процедуры распределенного децентрализованного управления координацией микропрограмм 96
2.2.1. Процедура распределенной циклической рассылки 97
2.2.2. Процедура активизации 98
2.2.3. Обоснование корректности процедур управления координацией 101
Выводы 108
3. Организация и синтез устройств управления координацией микропрограмм и контроллеров на их основе 110
3.1. Архитектура устройств управления координацией 111
3.1.1. Организация коллектива устройств управления координацией 111
3.1.2. Обобщенная архитектура устройства управления координацией 113
3.1.3. Особенности организации блоков управления активизацией микропрограмм 118
3.1.4. Интерфейс управления координацией микропрограмм 119
3.2. Метод синтеза устройств управления координацией 121
3.2.1. Этапы синтеза и особенности их выполнения 123
3.2.2. Схемная интерпретация переходов и позиций объединенной сети Петри 125
3.3. Структурно-функциональная организация контроллеров с устройствами управления координацией 128
3.3.1. Функциональные схемы контроллера матричного ЛМК 129
3.3.2. Форматы микрокоманд контроллера 135
3.3.3. Процесс функционирования контроллера в составе матричного ЛМК 136
Выводы 152
4. Сравнительная оценка быстродействия и аппаратной сложности коммуникационных средств контроллеров с устройствами управления координацией микропрограмм 154
4.1. Порядок проведения сравнительной оценки 155
4.1.1. Порядок оценки быстродействия коммуникационных средств 155
4.1.2. Порядок оценки аппаратной сложности коммуникационных средств 158
4.2. Результаты аналитического исследования 160
4.2.1. Оценка быстродействия коммуникационных средств ЛМК 160
4.2.2. Оценка аппаратной сложности коммуникационных средств ЛМК 164
4.3. Организация и результаты вычислительного эксперимента 170
4.3.1. Порядок проведения вычислительного эксперимента 170
4.3.2. Архитектура инструментальных программных средств имитационного моделирования 171
4.3.3. Результаты имитационного моделирования 186
Выводы 189
5. Декомпозиция и преобразование параллельных алгоритмов логического управления в коллектив параллельных микропрограмм 191
5.1. Постановка задач декомпозиции 192
5.2. Параллельно-последовательный редукционный метод декомпозиции 200
5.2.1. Общая характеристика метода. Основные определения 200
5.2.2. Поиск базового сечения 206
5.2.3. Организация перебора смежных сечений 214
5.2.4. Межблочное распределение вершин сечений 218
5.2.5. Особенности разбиения алгоритмов с циклами 225
5.2.6. Процедура синтеза разбиения 228
5.2.7. Синтез частных алгоритмов 232
5.3. Синтез коллектива компонентных микропрограмм 247
5.3.1. Типизация, структурирование, форматирование и распределение микрокоманд 247
5.3.2. Правила разметки микропрограмм. Идентификация адресов перехода 254
Выводы 261
6. Сравнительная оценка методов декомпозиции алгоритмов логического управления 264
6.1. Исследование качества получаемых решений 265
6.1.1. Методика оценки качества решений. Постановка вычислительного эксперимента 265
6.1.2. Архитектура инструментальных программных средств 266
6.1.3. Результаты вычислительного эксперимента 269
6.2. Оценка затрат времени на формирование разбиений. 276
6.2.1. Аналитическая оценка временной сложности процедур разбиения 276
6.2.2. Оценка трудоемкости формирования разбиения 278
Выводы 281
Заключение 283
Библиографический список
- Принципы организации логических мультиконтроллеров
- Формализация представления процесса координации параллельных ветвей (микропрограмм)
- Обобщенная архитектура устройства управления координацией
- Порядок оценки аппаратной сложности коммуникационных средств
Введение к работе
Создание устройств логического управления (УЛУ) остается одной из важных проблем современной науки, техники и технологии вследствие широкого распространения объектов логического управления на практике. Такие объекты часто встречаются в машиностроении, химической промышленности, энергетике и на транспорте. К ним относятся многие устройства бортовой автоматики, вычислительные и коммуникационные системы, а также устройства нижнего уровня иерархии АСУТП.
Проблемы анализа и синтеза УЛУ на протяжении нескольких десятков лет остаются в центре внимания отечественных и зарубежных ученых. Их решению посвящено значительное число теоретических исследований, получен ряд важных для науки и практики результатов. Первые крупные научные результаты, послужившие основой современной теории логического управления, были достигнуты В.И.Шестаковым, М. А.Гаврил овым, К.Э.Шенноном и А.Накашимой. Весомый вклад в развитие теории УЛУ внесли М.А.Айзерман, В.Л.Артюхов, О.Л.Бандман, СИ.Баранов, В.И.Варшавский, А.Гилл, В.А.Горбатов, В.В.Девятков, А.Д.Закревский, О.П.Кузнецов, В.Г.Лазарев, А.А.Ляпунов, Е.И.Пийль, Д.А.Поспелов, И.В.Прангишвили, Е.И.Пупырев, В.А.Скляров, А.А.Таль, А.А.Шалыто, В.С.Харченко, С.А.Юдицкий, Э.А.Якубайтис и др, Результаты выполненных исследований предоставляют мощную теоретическую основу для создания устройств логического управления объектами широкого класса.
Анализ показывает, что традиционные подходы к построению УЛУ в условиях быстро растущей сложности современных объектов управления, распараллеливания задач управления, появления особых требований к гибкости управляющих устройств (таких, как оперативная настраиваемость и наращиваемость) оказываются малоэффективными. В связи с этим возникает необходимость поиска более эффективных архитектур УЛУ, аппаратного базиса для их реализации и разработки формализованных методов анализа и синтеза параллельных управляющих устройств.
Успехи современной микроэлектронной технологии дают возможность реализации полнофункционального перепрограммируемого логического управляющего устройства на одной специализированной СБИС. В ближайшей перспективе возможно интегральное исполнение коллективов параллельно функционирующих однотипных УЛУ. Подобные СБИС-системы позволят строить перенастраиваемые модульные СБИС-автоматы (логические мультиконтроллеры), способные выполнять параллельные управляющие алгоритмы теоретически неограниченной сложности за счет их представления коллективом распределенных между модулями параллельных микропрограмм, взаимодействующих через соответствующий коммуникационный механизм.
Существенным препятствием на пути практической реализации логических мул ьтиконтролл еров (ЛМК) является высокая сложность организации взаимодействия (координации) параллельных микропрограмм (далее - коммуникационная сложность координации параллельных микропрограмм). Указанная сложность проявляется в трех аспектах: а) значительное время координации микропрограмм; б) существенные аппаратные затраты на построение локальных коммуникационных блоков модулей ЛМК (контроллеров); в) высокая трудоемкость синтеза распределенных коммуникационных блоков. Значительное время координации микропрограмм в ЛМК обусловлено необходимостью обмена сообщениями при межмодульных передачах управления и синхронизации. Существенная аппаратная сложность коммуникационных блоков связана с поддержкой функций маршрутизации и коммутации указанных сообщений. Высокая трудоемкость синтеза коммуникационных блоков вызвана необходимостью минимизации их сложности и коммуникационных затрат при распределении (размещении) микропрограмм между контроллерами ЛМК.
Научно-техническая проблема, решаемая в диссертационной работе, заключается в снижении коммуникационной сложности координации параллельных микропрограмм в ЛМК.
Научный аспект сформулированной проблемы заключается в необходимости развития теории логического управления в части разработки и исследования методов управления координацией параллельных микропрограмм в ЛМК с различными видами топологических структур.
Практическая часть проблемы связана с разработкой принципов функционирования быстродействующих устройств управления координацией микропрограмм, применимых при построении контроллеров ЛМК с наиболее распространенными топологическими структурами, а также с созданием методов, алгоритмов и специализированных программных средств для анализа и верификации этих устройств.
Объект исследования диссертации - коммуникационные средства координации параллельных микропрограмм контроллеров ЛМК.
Предмет исследования - методы, процедуры и устройства управления координацией параллельных микропрограмм в составе указанных коммуникационных средств.
Связь темы диссертации с научно-техническими программами. Диссертационная работа выполнена в рамках программы П.Т.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 таблицами.
Содержание работы
Во введении обоснована актуальность работы, сформулированы цель и задачи исследований, перечислены основные положения, выносимые на защиту, отражена их научная новизна и практическая ценность.
В первой главе рассматриваются принципы организации ЛМК и архитектура контроллеров, уточняется класс реализуемых алгоритмов логического управления и определяется ряд ключевых понятий. Проводится анализ влияния различных факторов на коммуникационную сложность координации параллельных микропрограмм в ЛМК и намечаются пути ее снижения.
Во второй главе строится обобщенная математическая модель коллектива устройств управления координацией параллельных микропрограмм, рассматриваются процедуры распределенного децентрализованного управления координацией, осуществляется доказательство их корректности.
В третьей главе дается описание метода синтеза, формализующего построение схем устройств управления координацией микропрограмм, формулируются принципы структур но-функциональной организации указанных устройств, разрабатываются форматы микрокоманд и функциональные схемы контроллеров ЛМК, рассматривается процесс функционирования контроллеров.
В четвертой главе выполняется комплексная сравнительная оценка быстродействия и аппаратной сложности устройств управления координацией. Рассматривается организация инструментальных программных средств имитационного моделирования, применяемых для автоматизации оценки.
В пятой главе обсуждается метод декомпозиции и преобразования параллельных алгоритмов логического управления в коллектив параллельных микропрограмм, формулируются правила разметки микропрограмм, позволяющие организовать их взаимодействие путем включения дополнительных коммуникационных микрокоманд, выполняемых устройствами управления координацией, доказывается корректность используемых преобразований.
В шестой главе проводится сравнительный анализ созданного метода декомпозиции с точки зрения числа лишних микропрограмм, логических условий, микроопераций и связей между микропрограммами, а также исследование асимптотической временной сложности и трудоемкости процедуры декомпозиции. Рассматривается архитектура инструментальных программных средств, используемых для автоматизации анализа. В заключении перечислены основные результаты и выводы диссертации.
В приложения вынесены громоздкие доказательства ряда утверждений, сформулированных в диссертации, приведены листинги основных модулей инструментальных программных средств. Также приложения содержат акты о внедрении результатов исследований в промышленность и справки об их использовании в учебном процессе.
Принципы организации логических мультиконтроллеров
В основе организации логических мультиконтроллеров лежат принципы параллельности, конструктивной однородности, настраиваемое, логической распределенности и территориальной сосредоточенности [108, 182], Параллельность ЛМК заключается в возможности одновременной независимой работы любого числа его контроллеров. Конструктивная однородность определяется использованием идентичных модулей, связанных регулярной топологической структурой. Настраиваемость ЛМК выражается в возможности перепрограммирования контроллеров и перенастройки их интерфейсных схем. Логическая распределенность вытекает из способа реализации в ЛМК алгоритмов управления, связанного с их преобразованием в коллектив взаимодействующих компонентных микропрограмм, распределяемых между контроллерами. Территориальная сосредоточенность мулыиконтроллера заключается в соизмеримости физических размеров контроллеров и длины каналов связи между ними.
Обобщенная структурная схема логического мулыиконтроллера представлена на рис. 1,1. Базовыми функциональными составляющими ЛМК являются коллектив однотипных модулей (контроллеров), а также коммуникационная сеть (КС), обеспечивающая их взаимодействие. Каждый контроллер (выделен пунктирным квадратом) включает функциональный (ФЭ) и коммуникационный (КЭ) элементы. ФЭ является ядром контроллера и выполняет функции автономного МУУ, способного реализовать последовательный алгоритм логического управления (микропрограмму) ограниченной сложности. Совокупность КЭ служит для подключения ФЭ к коммуникационной сети и организации взаимодействия (координации) микропрограмм, выполняемых разными контроллерами.
Контроллеры ЛМК подключаются к управляемому объекту (объектам) с помощью коммутатора связи с объектом управления (КСОУ). Назначение КСОУ - установить требуемые соединения между отдельными объектами и контроллерами путем коммутации соответствующих входов и выходов, В простейшем случае КСОУ вырождается в совокупность не связанных друг с другом устройств сопряжения [177]. Однако в общем случае, поскольку любой контроллер может управлять сразу несколькими объектами и, наоборот, всякий объект может принимать управляющие воздействия от нескольких контроллеров, КСОУ должен поддерживать различные режимы соединения входов и выходов [176].
Для организации связи ЛМК с верхним уровнем управления используется коммутатор связи с верхним уровнем (КСВУ). Основной информацией, передаваемой с верхнего уровня через КСВУ, являются коды выполняемых операций. Кроме того, верхний уровень может формировать условия, непосредственно влияющие на ход управляющих процессов в ЛМК. Контроллеры, в свою очередь, вырабатывают и передают на верхний уровень признаки завершения операций, слова состояния, признаки окончания настройки и т.д.
Следует отметить, что схема на рис. 1.1 позволяет описать общую структурную организацию ЛМК в широком смысле (см. определение 1.1). Например, в эту структурную модель вписываются многопроцессорные и транспьютерные системы логического управления [72, 115], а также сети ПЛМ [39,79]иПМЛ[170].
Процесс функционирования ЛМК включает несколько фаз [182], основными из которых являются: 1) инициализация; 2) выполнение алгоритма; 3) финализация. В ходе инициализации контроллеры получают с верхнего уровня начальные значения для загрузки в элементы памяти, а также код выполняемой операции (микропрограммы). Перечень инициализируемых элементов памяти зависит от архитектуры контроллеров, организации интерфейсных схем (КЭ) и других факторов. Инициализация завершается активизацией одного или нескольких контроллеров, реализующих начальные ветви алгоритма. Фаза выполнения алгоритма связана с последовательным и/или параллельным исполнением всех ветвей выбранного алгоритма вплоть до достижения конечной последовательной ветви. В ходе финализации контроллеры индицируют завершение назначенных им ветвей алгоритма и переходят в исходное состояние. Финализация контроллеров происходит асинхронно и момент ее начала зависит от способа распределения ветвей между ними.
За последние три десятилетия были разработаны десятки схемных решений микропрограммных контроллеров, способных функционировать в составе ЛМК с наиболее распространенными видами топологических структур [I, 3-9, 18, 19, 21, 23, 82, 153, 154], Начиная с 80-х годов XX века был налажен серийный выпуск СБИС МІЖ [198].
В настоящее время МПК и подобные им приборы серийно выпускаются многими известными производителями [206, 207, 213], в том числе фирмами «Advanced MicroDevices», «Monolithic Memories Inc.», «Texas Instruments», «Philips Semiconductors» и др. В силу архитектурной близости к классу МПК можно отнести ряд БИС, выпускаемых отечественной промышленностью, в частности, БИС управляющей памяти К587РП1, К588ВУ2. Современные микропрограммные контроллеры выпускаются на основе как униполярной, так и биполярной микроэлектронной технологии (в частности, с использованием технологий ТТЛ и ТТЛШ), имеют разное число выводов на корпусе, характеризуются различной длительностью цикла микрокоманды. Некоторые микроконтроллеры позволяют задавать полярность входов и выходов. Память микропрограмм МПК изготавливается как в виде ПЗУ (как правило, перепрограммируемого), так и в виде ПЛМ (последнее характерно, например, для прибора PSG507 фирмы «Texas Instruments»).
Структурная организация автономного МПК весьма проста (см. рис. 1.2) [40, 186]. Основным блоком такого МПК является БПМП - блок памяти микропрограмм. После считывания из БПМП микрокоманда фиксируется в регистре микрокоманд (РМК)2. Операционная часть считанной микрокоманды, содержащая (как правило, в кодированном формате) микрооперации (МО), через дешифратор микроопераций (ДМО) передается на объект управления. Адрес очередной микрокоманды формируется в блоке формирования адреса микрокоманды (БФАМК)3 в зависимости от КОп, адреса перехода (АП), получаемого из предыдущей микрокоманды, и от результатов проверки логических условий (ЛУ). Синхронизация работы МПК обеспечивается генератором тактовых импульсов (ГТИ), который оборудован внешним входом запуска.
Формализация представления процесса координации параллельных ветвей (микропрограмм)
Представим мультиконтроллер топологической моделью в виде связного графа Н = (М,и) , множество вершин М которого соответствует контроллерам, а множество ребер UczMxM - межмодульным связям. Будем полагать, что реализуемый алгоритм управления (не нарушая общности, выбираем один из реализуемых алгоритмов) представлен иерархически корректной параллельной граф-схемой GU={VU,EU) (см. определение 1.9), для которой получена ПарГСА без замыкающих дуг G = \Vu9E }. Будем далее считать, что в Gu имеется множество ветвей Du -f8,,iS2v,.,BrJ, Ва сК„ \а = \уи), при этом на множестве Du определены отношения параллельности о и альтернативы цг. Определение множеств синхронизируемых и активизируемых ветвей
Пусть в результате декомпозиции ПарГСА Gu получено отображение Си: Vu - М, определяющее межмодульное распределение ее вершин между контролерами ЛМК (решению задачи декомпозиции посвящена глава 5). Будем полагать, что это отображение удовлетворяет условию: VvE,vg eVu vgO)ve:
Cu[ve) Cu(vg) (параллельные вершины назначаются на разные контроллеры). Тогда для ветвей рассматриваемой ПарГСА можно получить отображение Q\ \DU -+М. Отображение ы в общем случае не является однозначным, т.е. ЗВа єОн\\І{Ва) U поскольку допускается разбиение ветвей на «части», размещаемые в разных контроллерах. В связи с этим каждую ветвь Ва, для которой (5в) 1, разобьем на фрагменты В[а,Вга,...,В с5а так, что (Vv(lvee fre{l,2f... e},(ve,ve)e:CB(v,) = Ce(vg))A A(Vv,e ,vAeJ9;,((vA,ve)e11)v((v,tvA)6:i():C(vA) (ve)).
Обозначив множество ветвей Ва GDU, ДЛЯ которых KJ(-) = 1, и всех выделенных фрагментов через ! , получим функциональное отображение t l .Dl -M, задающее межмодульное распределение ветвей алгоритма управления Gu. В дальнейшем (если это не приводит к неоднозначности) условимся выделенные фрагменты ветвей также называть ветвями.
Определим отношение частичного порядка JCJDJXD . Будем говорить, что ветвь Ва предшествует ветви Вр, т.е. BaJBpi если и только если 3veeBa9vg єВрі(уе9уЛєЩ, В таких ветвях любая вершина v еВ следует за любой вершиной vceBa: ydvyc.
Определение 2.1. Всякое максимальное по включению подмножество попарно параллельных ветвей JQDU такое, что \/B(ieJ:BaJB B eDis\J, будем называть множеством синхронизируемых ветвей , или J-множеством. Определение 2,2, Всякое максимальное по включению подмножество попарно параллельных ветвей FczD u такое, что VBaeF,B eJ:B JBa, где J- некоторое J-множество, назовем множеством активизируемых ветвей для J, или / -множеством.
Каждой паре множеств {F9J) такой, что (J с Du)v (Fa,Du), соответствует некоторая вершина синхронизации (барьер) vh. В то же время парам множеств (F J)t для которых (JQDI\DU)A(FQDI\DU)9 не соответствует вершин синхронизации, поэтому поставим в соответствие таким парам (F,J) фиктивные вершины синхронизации ygW Пусть Vu множество всех вершин синхронизации ПарГСА Gu, включая фиктивные. Тогда соответствующее вершине vaeVu /-множество обозначим как J(ya), a F множество как F(ya).
Для иллюстрации определенных понятий рассмотрим граф-схему, представленную нарис. 1.14. В ней имеются вершины синхронизации 14, 15, ..., 18; /-множествами являются /(14) = {(0,l)}, /(15) = {(2),(3)}, ./(16)=((5),(6)), /(17) = {(7),(4,8)}, /(18) = {(9),(10),(П)}; F-множества: F(14) = {(2),(3),(4,8)}, (15) = ((5),(6),(7)), F (16) = {(9),(10)}, F(l7)={(ll)}? F(l8) = {(12,13)}. В рассматриваемую граф-схему при заданном варианте распределения ветвей не требуется вводить фиктивные вершины синхронизации. Однако если ветвь (4,8) была бы разбита на фрагменты (4) и (8), назначенные на разные контроллеры, то между этими фрагментами понадобилась бы фиктивная вершина синхронизации.
Условия и фазы синхронизации/восстановления
Каждую ветвь алгоритма условимся характеризовать текущим состоянием «активна» или «пассивна». Состояние «активна» означает, что ветвь в данный момент выполняется, а состояние «пассивна» указывает, что ветвь не выполняется. Если ветвь не принадлежит циклам, то «пассивность» означает, что она еще не выполнялась или уже завершена; если ветвь входит в циклыэ то ее «пассивность» будем рассматривать только в пределах одной итерации наиболее вложенного из них.
Формально состояние каждой ветви Ва eD u будем задавать индикаторной функцией: ga(t) = \, если ветвь Вс в момент t активна, ga[t) иначе. Определим для каждой вершины vQ =Vu индикаторную функцию і (/)є{0,і}, удовлетворяющую следующим условиям: 2Д/) = 0, если хотя бы одна ветвь Ва eJ{ya) в момент t активна, Z (/) = 1 иначе, Zfl(0) = 0. Будем говорить, что синхронизация ветвей J{va) выполнена, если в некоторый момент f ш 0) л (/ со)) выполняется следующее условие синхронизации: 2о(г )-0-И, где запись О-И (1- 0) означает переход значения функции из 0 в 1 (из 1 в 0). Если ПарГСА Gu включает циклы, то возможно несколько актов синхронизации ветвей /(va). Поэтому в общем случае необходимо, чтобы выполнялось условие восстановления: 3t\(t f)b(tf u)\Za(t ) = \- Q.
Замечание 2.1. Условие восстановления позволяет корректно описать процесс координации ветвей при наличии циклических ветвлений и должно быть выполнено до момента очередной активизации первой ветви множества У(уд) (в противном случае не обеспечивается реентерабельность процесса координации, т.е. в дальнейшем станет невозможным событие Za = G- 1).
Определение 2.3. Промежуток времени от момента нарушения условия синхронизации (Za (f) 1 - 0) до ближайшего момента его выполнения (Zu(f ) 0-H) назовем циклом (фазой) синхронизации. Условно считаем, что Ze(0) = l- 0. Определение 2 А. Промежуток времени от момента выполнения условия синхронизации (Za (tf) = 0 - 1) до ближайшего момента его нарушения (Za (/") = 1 - 0) назовем циклом (фазой) восстановления.
Обобщенная архитектура устройства управления координацией
На рис, 3.2 показана конфигурация входов и выходов секции QJKA устройства Qn требуемых независимо от вида модели Н для ее подключения к другим секциям этого устройства, к одноименным секциям соседних устройств и к ФЭ і-го контроллера. Для удобства идентификации эти входы и выходы обозначены именами функций и переменных, введенными в главе 2 (см. п. 2ЛЛ). Сплошными стрелками на рис, 3,2 показаны входы и выходы, подключаемые к другим устройствам, а пунктиром изображены связи секции Qi(Kp) с ФЭ і го контроллера и входы настройки. Вход cpt служит для установки режима работы секции (возможные режимы обсуждаются далее), вход reset предназначен для сброса элементов памяти, через т обозначен вход для приема тактовых импульсов от ГТИ контроллера (функции остальных входов и выходов следуют из их обозначений).
На рис. 33 изображена обобщенная функциональная схема устройства ., соответствующая произвольной топологической модели Н. Секции Qi\Kpj этого устройства выделены пунктиром- Множество секций ІЩА Н всех устройств Qt є Q с соответствующими связями представляет собой однородную среду, обеспечивающую распределенное вычисление и распространение значений индикаторной
Группа входов 1 функции Zp (t) и реализующую процедуру CyCast для множества вершин К .устройства (см. рис, 33) служит для приема значений индикаторных функций { (f)} от множества соседних устройств ША9 определяемого положительной полуокрестностью +( )- Группа выходов 2 устройства обеспечивает передачу значений индикаторных функций [Zp(/)1 множеству соседних устройств 1()ґ , определяемому отрицательной полуокрестностью к (гп;). Группа 1 объединяет j k+(mi) -разрядных входов, а группа 2 - / = \к [тЛ z-разрядных выходов, р-е линии этих входов и выходов обеспечивают передачу значений функции Zp (/) - z-разрядный вход предназначен для приема значений компонент векторов соответствия [с1 \ \ компоненты вектора Ґр поступают из ФЭ на р-ю линию входа 3. z-разрядный вход 4 служит для приема значений индикаторных функций ветвей (р {/); значение для ветви Byejlv, А подается из ФЭ на р-ю линию входа 4.
Триггер хранит общее для всех секций устройства Qt значение сигнала срй. Установка триггера осуществляется импульсом setjzp, а сброс обеспечивается сигналом reset. Оба эти сигнала поступают в контроллер тк от устройства управления верхнего уровня (УУВУ) через КСВУ в момент инициализации ЛМК, причем set_cp подается с небольшой задержкой относительно reset. Сигнал cpi с триггера определяет режим работы всех секций устройства Qi9 что уже отмечалось выше. Возможны два режима. Первый из них, называемый режимом инвертирования и действующий при cpt=l? устанавливается только для устройства Qki которому в модели Й соответствует вершина тк (см. рис. 2.5), Второй, именуемый режимом ретрансляции и действующий при ср, =0, устанавливается для всех остальных устройств Qf (і к). В режиме ретрансляции значения функции Zp(t) передаются устройством Qi непосредственно, без преобразования. Отличием режима инвертирования является инвертирование значений функции Zp (/) перед выдачей на соответствующие выходы устройства.
Инвертирование значений Zp[t) устройством Qk позволяет каждому устройству коллектива Q идентифицировать текущую фазу координации по виду перепада сигнала (синхронизация или восстановление). Появление переднего фронта сигнала на р й линии по крайней мере одного из входов группы 1 (см. рис. 3.3) является признаком выполнения фазы синхронизации, а задний фронт сигнала на р-и линии - признак фазы восстановления. Таким образом, устройство ), а значит и контроллер тп может независимо от других модулей ЛМК определить номер wp текущей фазы.
Порядок оценки аппаратной сложности коммуникационных средств
Аппаратная сложность коммуникационных средств ЛМК измеряется количеством ЭВ, входящих в состав КЭ каждого контроллера. Для обеспечения объективности оценки понятие ЭВ необходимо уточнить. Будем считать, что контроллер (или, возможно, ЛМК в целом) выполняется в виде СБИС и каждый его блок в конечном счете может быть представлен схемой из вентилей (например, в базисе {И, ИЛИ, НЕ}). Такие схемы стандартны и хорошо известны для большинства типовых функциональных узлов вычислительной техники (триггеров, регистров, шифраторов и дешифраторов, мультиплексоров и демультиплексоров, счетчиков, и т.д.) [181].
Каждый вентиль имеет несколько выводов и занимает определенную площать на кристалле микросхемы. Два вентиля назовем эквивалентными, если они занимают одинаковую площадь СБИС, и именно в таком контексте уточним понятие ЭВ, Ясно, что (/?н-1)-входовый вентиль будет занимать несколько большую площадь, чем /г-входовый, и хотя это отличие невелико по сравнению с общей площадью /j-входового вентиля, будем представлять каждый /i-входовый вентиль (h 2) последовательным соединением h -\ двухвходовых вентилей. При наличии инверсии на входе вентиля представим ее отдельным двухвходовым элементом И-НЕ либо ИЛИ-НЕ. Таким образом, определим понятие ЭВ следующим образом.
Определение АЛ. Под эквивалентным вентилем условимся понимать двухвходовыи вентиль, реализующий любую булеву функцию двух переменных из множества {И, ИЛИ, И-НЕ, ИЛИ-НЕ}.
Замечание 4.1. Площадь, занимаемая схемой на кристалле СБИС, включает не только суммарную плошадь элементов, но и общую площадь связей между ними. Однако, учет площади связей на этапе логического синтеза УЛУ затруднителен в силу влияния на нее результатов трассировки соединений в рамках технического проектирования, Поэтому будем для упрощения считать, что площадь ЭВ включает соответствующую долю площади связей схемы (условно полагаем, что площадь связей распределяется между ЭВ в равных долях).
Однотипность контроллеров ЛМК позволяет ограничиться оценкой аппаратной сложности КЭ одного контроллера WK3. Для коммуникационных средств ЛМК в целом указанная сложность будет определяться произведением NWK3. Интерес представляет также оценка относительной аппаратной сложности КЭ, выражаемая как W ф = о_юо,(%) W где через Wm обозначена аппаратная сложность ФЭ контроллера. Оптимальным следует считать такое решение МПК, которое (при фиксированном значении Wm) обеспечивает Ф = min.
Аппаратную сложность WK3 будем оценивать аналитически по функциональной схеме путем подсчета в ней количества ЭВ. В ходе оценки исследуем зависимости WK3 от величин, характеризующих сложность ЛМК и выполняемых алгоритмов управления. В частности, интерес представляет анализ зависимости ГГ0 от числа вершин синхронизации в алгоритме /?, количества контроллеров в составе ЛМК N и числа взаимодействующих ветвей (которое будем определять так же, как и при оценке быстродействия КЭ). Полученные результаты сопоставим с наиболее простым по числу элементов известным аналогом [15].
Первоначально оценим величины / ах и Т т, Для этого проведем анализ функциональных схемы секции Qi[Kp) и блока Q t представленных на рис. 3.7. За единицу измерения ґ м и t примем задержку ЭВ /эв, считая задержки элементов И, ИЛИ5 И-НЕ, ИЛИ-НЕ примерно одинаковыми и приравнивая их к в. Замечая, что задержка ЭВ не зависит от числа входов вентиля, понятие ЭВ (согласно определению 4.1) в данном случае можно расширить на произвольное число входов.
Согласно схеме рис. 3.7,а tmx = fFF2+/v + f-, где /FF2 - время переключения триггера 2, fv - задержка элемента ИЛИ, t- - задержка элемента ИЛИ-НЕ. Учитывая, что tF2-4t3Q, tv=t-=t3U, получим: / 1ах=6/эв. В соответствии со схемами рис, 3.7 / (1+ л+/у-3(ЭВ) где tL - задержка фронта импульса одновибратора, /Л - задержка элемента И. Длина интервала Ar (vfl) зависит oi задержки (Ш К)] распространения сигнала Zp через секцию QiKp\. По схеме рис. 3.7,а устанавливаем, что при ср. = 1 (т.е. для устройства Qk, і = к, соответствующего вершине m f.) tiQ:[Kpj) = t +t- +tn +tv = 4t,B, а при cp,=0 (т.е. для устройств Qt, іФк) f(fi(Kp)) = fA+fA+/v=3f3B. Задержки переключения триггера 1 (см. рис. 3.7,а) и записи значений {Л/, ,1 в регистр RG (см. рис. 3.7,6) не влияют на величины / , Т т и t(Q Kp)), поскольку совмещены во времени с выполнением ветвей микропрограмм
