Содержание к диссертации
Введение
1. Основные определения. Постановка задачи оптимизации на основе автоматной модели 20
1.1 Основные определения 20
1.1.1 Конечные автоматы 20
1.1.2 Операции над автоматами и полуавтоматами 26
1.1.3 Синхронная композиция двух автоматов 29
1.1.4 Многокомпонентная синхронная композиция 34
1.2 Постановка задачи оптимизации на основе решения автоматных
уравнений 36
1.2.1 Задача оптимизации 36
1.2.2 Определение автоматного уравнения для двухкомпонентной сети.. 38
1.3 Методы решения бинарных автоматных уравнений 41
1.3.1 Решение уравнения на основе безразличных последовательностей. 42
1.3.2 Решение уравнения на основе Е-автомата 43
1.3.3 Языковый подход к решению автоматных уравнений; 44
1.4 Критерии оптимизации 49
1.5 Выводы по главе 50
2. Использование автоматных уравнений для оптимизации многокомпонентной композиции 52
2.1 Многокомпонентная синхронная композиция 52
2.1.1 Методы построения многокомпонентной синхронной композиции. 52
2.1.2 Свойства многокомпонентной композиции 57
2.2 Автоматные уравнения для многокомпонентной композиции 61
2.2.1 Решение автоматных уравнений для многокомпонентной
композиции 61
2.2.2 Сведение автоматного уравнения для многокомпонентной композиции к бинарному автоматному уравнению 65
2.2.3 Разрешимость автоматного уравнения относительно различных алфавитов 67
2.3 Упрощенные методы решения автоматных уравнений для оптимизации
автоматных сетей 70
2.3.1 Комбинационное решение автоматного уравнения 71
2.3.2 Экспериментальные результаты по нахождению комбинационного решения 75
2.3.3 Решение автоматного уравнения на основе безразличных последовательностей 76
2.3.4 Экспериментальные результаты по нахождению безразличных последовательностей 79
2.4 Основные результаты главы 80
3. Покомпонентная оптимизация дискретных систем относительно различных критериев 82
3.1 Глобальная оптимизация 82
3.2 Локальная оптимизация 85
3.2.1 Локальная оптимизация посредством решения множества автоматных уравнений 86
3.2.2 Локальная оптимизация посредством решения системы уравнений 89
3.3 Критерии оптимизации 94*
3.3.1 Число связей в автоматной сети 95
3.3.1.1 О минимизации числа связей на основе решения автоматного уравнения 95
3.3.1.2 Нахождение наибольшего решения автоматного уравнения с заданным множеством входных алфавитов 97
3.3.1.3 Минимизация числа входных переменных компоненты 98'
3.3.2 Отказоустойчивость компоненты 103
3.3.3 Число вентилей в логической реализации компоненты 106
3.4 Основные результаты главы 108
4. Прогрессивные решения автоматных уравнений и систем автоматных уравнений 109
4.1 Наибольшее прогрессивное решение автоматного уравнения 109
4.2 Характеризация прогрессивных решений 121
4.3 Прогрессивные решения системы уравнений 125
4.4 Экспериментальные результаты по существованию прогрессивных решений 129
4.5 Основные результаты главы 130
Заключение 132
Литература 134
Приложение ...144
- Основные определения
- Многокомпонентная синхронная композиция
- Глобальная оптимизация
- Наибольшее прогрессивное решение автоматного уравнения
Введение к работе
Актуальность проблемы
Автоматизация синтеза дискретных систем [1-3], в частности, цифровых схем, таких как большие интегральные схемы (БИС) и сверхбольшие интегральные схемы (СБИС) [4-9], была и остается одной из актуальных задач систем автоматизированного проектирования (САПР). Как известно, большинство из существующих автоматизированных методов [10-13] синтеза многокомпонентных дискретных систем не позволяют синтезировать оптимальную систему. Проблема осложняется тем, что понятие оптимальности зависит от целей решаемой задачи, и, соответственно, задача оптимизации является многокритериальной. В некоторых случаях система должна соответствовать сразу нескольким критериям, причем некоторые из них являются взаимоисключающими. Например, отказоустойчивость систем обеспечивается за счет введения избыточности, таким образом, отказоустойчивая система не может иметь минимальное число элементов. Достаточно часто в качестве критерия оптимальности выступают число внутренних состояний системы [14-17], число различных библиотечных модулей [11, 12], количество связей между модулями [18 - 20] и другие [21, 22]. Однако и для данных критериев задача построения оптимальной системы не является решенной. Одним из подходов к оптимизации является итеративный подход, когда компоненты оптимизируются последовательно, и на каждом шаге проверяется, что новая реализация компоненты сохраняет внешнее поведение системы и улучшает предыдущую реализацию. Как известно [23 - 26], при использовании автоматной модели все допустимые реализации компоненты содержатся в наибольшем решении соответствующего автоматного уравнения. Поэтому исследование возможностей оптимизации дискретных систем и разработка соответствующих алгоритмов на основе решения автоматных уравнений является актуальной задачей.
Цель работы
Разработка методов оптимизации многокомпонентных дискретных систем на основе решения автоматных уравнений.
Основные задачи
Разработка методов решения автоматных уравнений для многокомпонентной композиции конечных автоматов.
Разработка упрощенных алгоритмов решения автоматных уравнений и оптимизации многокомпонентных автоматных сетей.
Исследование различных критериев оптимизации и разработка алгоритмов оптимизации компонент автоматной сети согласно заданным критериям.
Полное описание прогрессивных решений автоматных уравнений и систем автоматных уравнений. Только такие решения находят практическое применение.
Методы исследования
Для решения поставленных задач применяется аппарат дискретной математики, в частности, теории автоматов, математической логики, а также проводятся компьютерные эксперименты с целью исследования эффективности предлагаемых методов.
Научная новизна
Для снижения сложности оптимизации многокомпонентных дискретных систем предложен локальный подход, при котором компонента оптимизируется не относительно всей системы, а относительно соседних с нею компонент. Показано, что в этом случае для более эффективной оптимизации компоненты можно использовать совокупность автоматных уравнений и/или систему автоматных уравнений.
Предложен алгоритм нахождения наибольшего решения в наибольшем алфавите многокомпонентного автоматного уравнения. Такое
наибольшее решение содержит все оптимальные решения как специальные редукции.
3. Предложен метод нахождения наибольшего, в том числе наибольшего
прогрессивного, решения системы автоматных уравнений. Метод
нахождения наибольшего прогрессивного решения системы автоматных
уравнений расширяет известный метод нахождения наибольшего
прогрессивного решения одного автоматного уравнения.
4. Сформулированы необходимые и достаточные условия того, что
полностью определенная редукция наибольшего прогрессивного решения
является прогрессивным решением.
Разработан алгоритм минимизации числа связей в автоматной сети на основе синтеза компоненты, которая зависит от меньшего числа входных переменных.
Предложены методы полиномиальной сложности для оптимизации компонент автоматной сети на основе решения уравнения. В частности, метод оптимизации автоматных сетей на основе безразличных последовательностей расширен на автоматные сети с обратными связями; сформулированы достаточные условия существования комбинационного решения автоматного уравнения.
Основные положения, выносимые на защиту
Метод нахождения наибольшего решения в наибольшем алфавите для многокомпонентного автоматного уравнения. Такое наибольшее решение содержит все оптимальные решения как специальные редукции; в частности, наибольшее решение в заданном алфавите (если такое решение существует) может быть получено как специальная редукция наибольшего решения в наибольшем алфавите.
Алгоритм минимизации числа связей в автоматной сети на основе нахождения полностью определенной редукции недетерминированного
автомата, поведение которой существенно зависит от меньшего числа входных переменных.
3. Необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения является прогрессивным решением, и метод нахождения наибольшего прогрессивного решения системы автоматных уравнений. Именно прогрессивные решения интересны с практической точки зрения.
Достоверность результатов
Все научные положения и выводы, содержащиеся в работе, основаны на утверждениях, доказанных с использованием аппарата дискретной математики. Эффективность предложенных алгоритмов подтверждается компьютерными экспериментами.
Практическая значимость работы
Предложенные в работе методы могут быть использованы на этапе логического проектирования для синтеза и оптимизации многокомпонентных дискретных систем. В частности, метод, основанный на использовании безразличных последовательностей, был опробован на контрольных примерах из сети Интернет (benchmarks). Результаты показали, что число не определенных переходов в соответствующем частичном автомате для оптимизируемой компоненты Л'может достигать 80% от числа возможных переходов, и, соответственно, использование автоматных безразличных последовательностей в ряде случаев приводит к более эффективной реализации компоненты по числу вентилей.
Реализация полученных результатов
Исследования, результаты которых изложены в диссертации, проводились в рамках следующих грантов и научно-исследовательских проектов.
Проект УР.04.01.018 «Алгебра автоматов и полуавтоматов: отношения, операции, решения уравнений и неравенств» по программе «Университеты России», 2002-2003 гг.
Грант конкурса исследовательских проектов в области автоматизации проектирования интегральных схем компании INTEL, НИР «Оптимизация цифровых схем на основе решения автоматных уравнений», 2003 г.
НИР «Оптимизация декомпозиций конечных автоматов на основе
решения автоматных уравнений» по гранту №А04-2.8-730 для поддержки
научно-исследовательской работы аспирантов государственных
образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию, 2004 г.
НИР «Синтез цифровых узлов схем управления многофазными инверторами» по заказу НПО «Полюс» в рамках Студенческого научно-исследовательского инкубатора по программе Международной организации IREX (International Research & Exchanges Board), 2004-2005 гг.
Совместный российско-тайваньский проект «Оптимизация цифровых схем посредством решения автоматных уравнений» по гранту РФФИ-NSC 06-08-89500, 2006-2008 гг.
НИР «Оптимизация цифровых схем посредством решения уравнений для структурных автоматов» по гранту РФФИ 07-08-12243, 2007-2008 гг.
Апробация работы
Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры программирования и кафедры защиты информации и криптографии 'факультета прикладной математики и кибернетики ТГУ.
Результаты работы докладывались на Международных конференциях: «Euromicro symposium on digital system design» (Турция, 2003; Франция,
2004); «Дискретные модели в теории управляющих систем» (Москва, 2004); «East-west design and test workshop» (Сочи, 2006); «Синтез и сложность управляющих систем» (Новосибирск, 2004); Всероссийской конференции с международным участием «Новые информационные технологии в исследовании сложных структур» (Томск, 2000, 2002; Иркутск 2004); Сибирской научной школе-семинаре «Проблемы компьютерной безопасности и криптография» (Томск, 2003, 2005).
По результатам проведенных исследований опубликовано 9 статьей в научных журналах [27-35], а также 16 докладов и тезисов докладов на конференциях различного уровня [36 - 51].
Структура и объем диссертации
Диссертация состоит из введения, 4 глав, заключения и списка литературы из 93 наименований; изложена на 145 страницах текста, набранного в редакторе MS Word (шрифт - Times New Roman, размер шрифта - 14 pt, междустрочный интервал - 1,5 строки), включая 72 рисунка, 5 таблиц.
Краткое содержание
Во введении дается общая характеристика работы, обосновывается актуальность исследований, определяется тематика и формулируется цель работы, кратко излагаются основные задачи и результаты, выносимые на защиту.
Первая глава диссертации содержит необходимые определения теории конечных автоматов, постановку задачи и обзор литературы по теме диссертации.
Одной из широко используемых моделей при синтезе и анализе дискретных систем является конечный автомат, который описывает поведение системы, переходящей под действием входных воздействий из состояния в состояние и производящей при этом выходные сигналы [1, 52-
55]. Конечный автомат также используется для представления специального класса словарных отображений (последовательностных функций), сопоставляющих каждому слову (последовательности) в одном (входном) алфавите одно или несколько слов той же длины в другом (выходном) алфавите. Автоматы, реализующие равные отображения, называются эквивалентными.
Сложные дискретные системы обычно представляются в виде сети из взаимодействующих компонент. Если поведение каждой компоненты описано конечным автоматом, то совместное поведение всех компонент сети описывается композицией конечных автоматов (автоматной сетью). Автоматные сети используются для описания поведения цифровых схем [56 - 58], телекоммуникационных протоколов [59 — 62], поведения игроков в логической игре [63], а также для решения задач автоматизированного' анализа и синтеза таких систем [3, 6, 11, 12].
В данной работе в качестве модели функционирования рассматривается синхронная композиция конечных автоматов, то есть предполагается наличие синхросигнала, позволяющего всем компонентам системы по этому сигналу переключиться из текущего состояния в следующее и произвести выходной сигнал.
Формально синхронная композиция двух автоматов определяется через операции над соответствующими полуавтоматами с последующим возвращением к автомату [64]. Синхронная композиция автоматов есть приведенный наблюдаемый автомат, язык которого есть синхронная композиция языков автоматов-компонент. Такое определение синхронной і композиции автоматов обобщает все известные ранее определения [56, 65 -68].
Известно [56, 67], что существует множество автоматов, которые могут заменить компоненту, не изменяя внешнее поведение автоматной сети. Задача описания множества таких автоматов сводится к решению автоматного уравнения [23-25, 67, 69-71]. Формально автоматным
уравнением называется выражение А Х= S относительно неизвестной переменной X, где автоматы А и 5 описывают поведение известной части системы (называемой контекстом) и спецификации соответственно, есть операция синхронной композиции автоматов, = - отношение, в котором должны находиться синтезируемая система и спецификация. Автомат является решением уравнения, если его композиция с контекстом эквивалентна спецификации. Известно [23 - 26], что разрешимое автоматное уравнение имеет наибольшее решение, которое содержит все решения уравнения, и из которого можно выбрать оптимальное решение. Таким образом, задачу оптимизации дискретных систем в ряде случаев можно свести к решению автоматного уравнения.
Впервые автоматное уравнение появилось в работе [57] и использовалось для оптимизации хвостовой компоненты последовательной бинарной автоматной сети. Показано, что в этом случае общим решением автоматного уравнения является частичный детерминированный автомат Largest, то есть в качестве хвостовой компоненты можно использовать любой автомат, квазиэквивалентный автомату Largest.
Методы решения автоматного уравнения для головной компоненты последовательной сети [69, 73] появились значительно позже и основывались на использовании входо-выходных последовательностей компоненты, которые являются эквивалентными с точки зрения внешнего поведенияхети.
Методы решения уравнения, соответствующего двухкомпонентной сети с обратными связями, предложены в работах [24, 26, 74].
В работе [24] для решения автоматного уравнения используется специальный недетерминированный Е-автомат, который эквивалентен наибольшему решению уравнения. Для построения Е-автомата используется вычисление с неподвижной точкой.
В работе [26] предложен метод нахождения наибольшего решения автоматного уравнения на основе решения уравнения в алгебре регулярных языков.
Наибольшее решение Largest уравнения можно рассматривать как резервуар, из которого выбирается оптимальное решение согласно некоторому критерию. Однако не каждое решение уравнения интересно с практической или теоретической точки зрения. Если поведение компоненты должно быть определено для любой входной последовательности, то в качестве решений могут быть выбраны только полностью определенные решения. При логическом синтезе систем с обратными связями необходимо гарантировать отсутствие тупиков в рассматриваемой системе, то есть потребовать, чтобы на любую внешнюю входную последовательность. система вырабатывала внешний выходной сигнал. Решение автоматного уравнения с таким свойством называется прогрессивным. Достаточные условия синтеза двухкомпонентной автоматной сети без тупиков хорошо известны [56, 67]. В частности, таким условием является использование1 автоматов Мура или, по крайней мере, наличие автомата Мура в каждой цепи обратной связи. Прогрессивные решения автоматного уравнения не. исчерпываются автоматами Мура, однако полное описание всех прогрессивных решений остается не известным. Известно только [72], что если прогрессивное решение существует, то существует и наибольшее прогрессивное решение.
Любое решение автоматного уравнения является редукцией наибольшего решения уравнения. Обратное не всегда верно, то есть [26] не всякая полностью определенная редукция такого решения также является решением уравнения. Кроме того, не каждое решение автоматного уравнения подходит для практической реализации. Таким образом, с теоретической точки зрения остается открытым вопрос о полном описании решений автоматного уравнения, а именно, какие из редукций наибольшего решения можно использовать при оптимизации соответствующей компоненты.
С практической точки зрения, существующие методы нахождения наибольшего решения автоматного уравнения имеют экспоненциальную сложность, что затрудняет их применение для систем большой размерности.
Поэтому, с одной стороны, необходимо уменьшить размерность автоматов-коэффициентов уравнения, а, с другой стороны, находить, возможно, часть наибольшего решения, которая является достаточно представительной и может быть найдена за достаточно короткое время. Необходимо также отметить, что до сих пор в качестве единственного критерия при использовании автоматных уравнений с целью оптимизации компоненты автоматной сети рассматривается число состояний компоненты [14-16, 24, 67]. Данный критерий представляет скорее теоретический интерес, так как уменьшение числа состояний не всегда приводит к упрощению логической реализации. Необходимо исследовать другие критерии оптимизации, такие как число связей в автоматной сети, отказоустойчивость компоненты и т.д., и разработать алгоритмы оптимизации компоненты на основе использования этих критериев.
Вторая глава диссертации посвящена решению автоматных уравнений! для многокомпонентной автоматной сети. Напомним, что практически все методы решения автоматных уравнений разработаны для двухкомпонентной композиции автоматов. Обычно [24, 26, 67] понятие автоматного уравнения вводится для бинарной автоматной сети конкретной заданной структуры;, тогда как в общем случае дискретная система может быть представлена композицией более чем двух компонент. Поэтому в данной работе мы вводим понятие автоматного уравнения для автоматной сети с произвольной структурой и произвольным числом компонент. Для этого в параграфе 2.1 дается формальное определение операции синхронной композиции для многокомпонентной автоматной сети, и исследуются свойства такой композиции. Показывается, что операция синхронной композиции является коммутативной и ассоциативной; Следствием последнего результата является тот факт, что для каждого автоматного уравнения для многокомпонентной композиции существует эквивалентное (равносильное) бинарное уравнение. Однако переход к такому уравнению требует построения автомата, описывающего поведение автоматной сети из
нескольких компонент, и построение такого автомата возможно только для небольших автоматных сетей.
В параграфе 2.2 определяется автоматное уравнение для многокомпонентной автоматной сети относительно оператора синхронной композиции и предлагается алгоритм построения наибольшего решения уравнения без перехода к двухкомпонентному уравнению.
Разрешимость автоматного уравнения существенно зависит от выбора алфавитов решения. Мы показываем (раздел 2.2.3), что существует в некотором смысле наибольший алфавит для неизвестной компоненты, в котором автоматное уравнение разрешимо. Если уравнение не разрешимо в этом алфавите, то оно не разрешимо и в любом другом алфавите. Если все автоматы-компоненты и требуемая спецификация автоматной композиции являются полностью определенными и детерминированными автоматами; то-сложность решения уравнения в наибольшем алфавите является полиномиальной, так как не требует операции детерминизации. Более того, сформулирована теорема, согласно которой из этого решения можно получить решение уравнения в любых алфавитах (если такое решение существует). Решение автоматного уравнения в заданных алфавитах есть специальная проекция решения в наибольшем алфавите на эти алфавиты.
Существующие методы нахождения наибольшего решения автоматного уравнения имеют экспоненциальную сложность, что затрудняет их применение для систем большой размерности. Поэтому в параграфе 2.3 предлагаются упрощенные алгоритмы, доставляющие не наибольшее решение автоматного уравнения, а только часть наибольшего решения, которая может быть вычислена за полиномиальное время, и из которой можно выбрать оптимальную реализацию интересующей нас компоненты. В частности, предлагаются достаточные условия существования комбинационного решения, то есть решения с одним состоянием, а также метод решения автоматного уравнения на основе безразличных последовательностей, имеющие полиномиальную сложность. Решение
уравнения, полученное на основе безразличных последовательностей, является частичным детерминированным автоматом, и можно использовать известные алгоритмы [14, 75] для нахождения оптимального квазиэквивалентного автомата. Компьютерные эксперименты, проведенные на контрольных примерах из сети Интернет, показали, что в выделенном фрагменте схемы безразличными могут быть до 80% переходов.
В третьей главе диссертации рассматриваются различные подходы к оптимизации компоненты автоматной сети на основе решения автоматных уравнений и исследуются различные критерии оптимизации
В параграфе 3.1 рассматривается известный глобальный подход [67], когда каждая компонента оптимизируется относительно всей автоматной' сети. Оптимизация осуществляется итеративным перебором компонент сети. Процесс прекращается, когда удовлетворены требования к оптимизации, или^ ни одна компонента не может быть оптимизирована.
Достоинством данного подхода является ( существование общего (наибольшего) решения уравнения, которое описывает все возможные (допустимые) замещения интересующей нас компоненты. Однако, как отмечалось выше, существуют как теоретические, так и практические* препятствия для применения данного подхода к оптимизации многокомпонентных автоматных сетей. В частности, данный подход требует построения автомата, описывающего совместное поведение всех компонент, за исключением оптимизируемой. Для уменьшения объема вычислений в параграфе 3.2 предлагается использовать локальную оптимизацию, то есть рассматривать не всю автоматную сеть, а только фрагмент, содержащий оптимизируемую компоненту и непосредственно связанные с ней компоненты. Такой подход используется при оптимизации комбинационных схем и известен под названием «window approach» [11]. Показывается (раздел 3.2.1), что в этом случае задача оптимизации сводится к решению множества автоматных уравнений, причем в качестве оптимального решения можно выбрать решение любого уравнения из этого множества. Однако если
все входы и выходы компоненты являются внешними полюсами выделенного фрагмента, то все решения уравнения эквивалентны исходному автомату. В этом случае более эффективным является решение не множества, а системы автоматных уравнений. Наибольшее решение системы уравнений* можно найти как пересечение наибольших решений всех уравнений системы. Как показали компьютерные эксперименты [40], результаты локальной оптимизации компонент сети по числу состояний близки к результатам глобальной оптимизации.
Параграф 3.3 посвящен описанию критериев оптимизации компоненты, таких как число связей в автоматной сети, отказоустойчивость компоненты, число вентилей в логической реализации.
В разделе 3.3.1 в качестве критерия оптимизации рассматривается число связей в автоматной сети. Если поведение компоненты существенно не, зависит от переменной, соответствующей некоторому входному алфавиту, то есть реакции автомата на любые две последовательности, которые отличаются значениями переменной, соответствующей данному входному алфавиту, совпадают, то компоненту сети можно заменить компонентой с меньшим числом существенных входных переменных. При этом внешнее, поведение автоматной сети не изменится. Все допустимые замещения компоненты описываются редукциями наибольшего решения автоматного уравнения. Таким образом, задача минимизации связей в автоматной сети сводится к задаче поиска редукции наибольшего решения уравнения, которая существенно зависит от меньшего числа входных переменных. Предлагается алгоритм выбора специальной редукции недетерминированного автомата (наибольшего решения), поведение которой существенно не зависит от переменных, соответствующих некоторым входным алфавитам (если существует). Если существует редукция, которая не зависит хотя бы от одной входной переменной, то соответствующая линия связи в многокомпонентной системе является избыточной, и может быть удалена.
В разделе 3.3.2 в качестве критерия оптимизации рассматривается отказоустойчивость компоненты относительно выходных неисправностей. Все автоматы, которые могут заменить компоненту без изменения внешнего поведения сети, суть редукции недетерминированного автомата Largest, который является наибольшим решением соответствующего автоматного уравнения. Любая редукция автомата Largest, являющаяся решением уравнения, описывает не обнаружимую неисправность. Чем больше выходных неисправностей компоненты описываются редукциями автомата Largest, тем устойчивее композиция к выходным неисправностям компоненты.
В разделе 3.3.3 в качестве критерия рассматривается число вентилей в логической реализации, и приводятся результаты экспериментов по локальной оптимизации контрольных примеров из сети Интернет., (benchmarks) на основе нахождения безразличных последовательностей.
Четвертая глава диссертации посвящена разработке методов нахождения прогрессивных решений автоматных уравнений и систем автоматных уравнений. Обычно одним из условий функционирования системы является отсутствие тупиков в рассматриваемой системе. Это* значит, что на любую внешнюю входную последовательность система вырабатывает внешнюю выходную последовательность. Решение автоматного уравнения с таким свойством называется прогрессивным. Если автоматное уравнение решается для последовательной композиции автоматов, то любое решение уравнения является прогрессивным и может быть использовано для практической реализации. Проблемы возникают при наличии обратных связей в автоматной сети. При оптимизации компоненты в сети с обратными связями в качестве оптимального решения может быть выбрано только прогрессивное решение. Известно [67], что наличие в каждой цепи обратной связи автомата Мура гарантирует отсутствие тупиков в композиции. Таким образом, любой автомат Мура, являющийся решением
уравнения, есть прогрессивное решение. Однако все прогрессивные решения не исчерпываются автоматами Мура.
В работе [72] доказывается, что если автоматное уравнение имеет прогрессивное решение, то уравнение имеет и наибольшее прогрессивное решение. В общем случае наибольшее прогрессивное решение является редукцией, но не подавтоматом наибольшего решения. Для нахождения наибольшего прогрессивного решения в параграфе 4.1 предлагается способ, основанный на удалении «плохих» последовательностей из наибольшего решения. Если наибольшее решение Largest уравнения прогрессивное, то Largest — наибольшее прогрессивное решение; однако не всякая его редукция является прогрессивным решением. Если решение Largest не является прогрессивным, то язык автомата Largest «подстригается» таким образом, чтобы получить его наибольшее подмножество, обеспечивающее, прогрессивное решение. Для построения наибольшего прогрессивного' решения предлагается использовать специальный автомат, эквивалентный наибольшему решению, такой, что наибольшее прогрессивное решение является его подавтоматом. Следуя работе [76], такой автомат называется совершенным в контексте автомата А и используется для описания всех. прогрессивных решений уравнения. Показано, что если при построении наибольшего решения не объединять эквивалентные состояния в одно, ТО' такое наибольшее решение будет совершенным.
Как известно [72], не всякая полностью определенная редукция наибольшего прогрессивного решения является решением. Отсюда возникает задача описания всех прогрессивных решений автоматного уравнения. Языковых свойств автомата недостаточно для описания всех прогрессивных решений уравнения. В параграфе 4.2 для описания множества всех прогрессивных решений каждому состоянию наибольшего прогрессивного решения приписывается система подмножеств входо-выходных пар. И формулируются необходимые и достаточные условия того, что полностью
определенная редукция наибольшего прогрессивного решения также является прогрессивным решением.
Так как в некоторых случаях (раздел 3.2.2) для оптимизации компоненты автоматной сети предпочтительнее решать систему автоматных уравнений вместо одного уравнения, то в параграфе 4.3 предлагается алгоритм нахождения прогрессивного решения для системы автоматных уравнений. Чтобы система уравнений имела прогрессивное решение необходимо, чтобы решение было прогрессивным для каждого уравнения системы. Согласно алгоритму решения системы уравнений, наибольшее решение системы находится как пересечение наибольших решений всех уравнений системы. Наибольшее прогрессивное решение строится на основе совершенного автомата. Поэтому показывается, что операция пересечения совершенных автоматов сохраняет свойство совершенности решения.. Для нахождения наибольшего прогрессивного решения совершенные автоматы пересекаются и язык пересечения «подстригается» таким образом, чтобы получить его наибольшее подмножество, которое является прогрессивным решением для каждого уравнения системы.
В параграфе 4.4 приведены экспериментальные результаты1 по существованию наибольшего прогрессивного решения автоматного уравнения для случайно сгенерированных автоматов.
В заключении диссертации представлены основные результаты и выводы работы.
Основные определения
Одной из широко используемых моделей при синтезе и анализе дискретных систем является конечный автомат, который описывает поведение системы, переходящей под действием входных воздействий из состояния в состояние и производящей при этом выходные сигналы. Конечный автомат также используется для представления специального класса словарных отображений (последовательностных функций), сопоставляющих каждому слову (последовательности) в одном (входном) алфавите одно или несколько слов той же длины в другом (выходном) алфавите Автоматы, реализующие равные отображения, называются эквивалентными. В данной работе мы рассматриваем только инициальные автоматы, то есть автоматы, описывающие поведение дискретных систем, обладающих сигналом сброса.
Конечным автоматом или просто автоматом называется пятерка А = {А, I, О, ТА, ао), где А - конечное множество состояний с выделенным начальным состоянием ао, I - входной алфавит, О - выходной алфавит, и TAczIxAxAxO - отношение переходов. Отношение состоит из четверок (i,a,a ,o), которые называются переходами.
Четверка (і,а,а ,о) є ТА описывает переход в автомате А из состояния а в состояние а под действием входного символа і с выходным символом о. В общем случае, в текущем состоянии для данного входного символа может существовать более одного перехода или не существовать ни одного перехода.
Заметим, что входной (и/или выходной) алфавит автомата может быть декартовым произведением нескольких алфавитов; в этом случае говорят о множестве входных (и/или выходных) алфавитов автомата и о входных (и/или выходных) переменных, соответствующих этим алфавитам.
Максимальным автоматом (относительно входного алфавита / и выходного алфавита О) с одним состоянием называется автомат А = ({а0}, I, О, ТА, ао), в котором переходы определены для каждого входного символа со всеми возможными выходными символами, то есть для любых (і,о)єІхО [(і,ао}ао,о) є ТА]. Для краткости мы будем называть такой автомат максимальным 10 — автоматом.
Автомат называется наблюдаемым, если для любой тройки (ї,а,о) є ІхАхО существует не более одного состояния а є А такого, что (і,а,а ,о) е ТА.
Если для каждой пары (і,а) є ІхА существует хотя бы один переход (і,а,а ,о) є ТА, то автомат называется полностью определенным. В противном случае автомат называется частично определенным или частичным.
Автомат называется детерминированным, если для любой пары (і,а) є ІхА существует не более одной пары (а ,о) є АхО такой, что (і,а,а ,о) є ТА- В противном случае автомат называется недетерминированным.
Иногда отношение переходов в автомате заменяют функцией поведения h, отображающей декартово произведение ІхА в множество подмножеств декартового произведения АхО. Множество h(i,a) содержит пару (а ,о), если и только если четверка (і,а,а ,о) є ТА. Если для некоторой пары (і,а) є ІхА имеет место h(i,a) = 0, то считается, что поведение автомата А в состоянии а не определено для входного символа і. Отношение переходов, и функция поведения распространяются на входные последовательности обычным образом. Формально для входной последовательности a = i\...ik и выходной последовательности $ = 0\...Ok четверка (а,а, з ,Р) є ТА, если и только если существует последовательность состояний а,а\,...,ак-\,а таких, что {і\,а,а\,о{) є ТА,..., (ік,ак.\,а ,Ок) є ТА. Множество h(a,a) содержит пару (а ,Р), если и только если четверка (а,а,а ,Р) є Тл. По определению, (s,a,a,s) є ТА, где є - пустая последовательность, для любого состояния аєА. Соответственно, для любого состояния аєА функция h(z,a) содержит пару (а,е). Функция поведения имеет две проекции: функцию переходов next_state, отображающую подмножество декартова произведения (І хА) в множество А, и функцию выходов out, отображающую данное подмножество в множество О . Формально для входной последовательности а, а є next_state(a,a), если ЗРєО [(# ,(3) є h(a,a)]; 3 є out(a,a), если За єА [(а ,Р) є h(a,a)].
Полностью определенный детерминированный автомат А называется муровским, или автоматом Мура, если его функция выходов не зависит существенно от входного символа, то есть \/аєА \/і\,і2єІ \put{i\,a) = out(iba)].
Языком автомата А в состоянии а, обозначение: LA(CL), называется множество последовательностей входо-выходных пар в алфавите IxO, получаемых при последовательных переходах из состояния а. Далее через (1x0) обозначается множество всех последовательностей конечной длины в алфавите IxO, включая пустую последовательность є. Формально, язык LA(O) есть подмножество (IxO) , и последовательность (i\0\)...(iifik) є LA(a), если и только если За єА \(i\...ik,a,a\o\...Ok) є ТА]. По определению, язык LA(O) содержит пару (є,є). Язык LA(ao) автомата в начальном состоянии а0 называется языком автомата А и обозначается LA.
Автомат А = (А, I, О, ТА, яо) называется связным, если любое состояние достижимо из начального состояния, то есть \/аєА За є/ [а є next_state(a,ao)]. Автомат В= (В, I, О, Тв, bo) называется подавтоматом автомата А, если В QA, bo = а0 и Тв Я ТА. Состояние b недетерминированного автомата В=(В,1,0,Тв,Ьо) называется редукцией состояния а недетерминированного автомата А = (А, I, О, Тл, ао) (обозначение b а), если LB(b) с LA(a).
Многокомпонентная синхронная композиция
В работе [56] предлагается построение автомата, описывающего поведение автоматной сети, компонентами которой являются детерминированные автоматы Мура. В предыдущей главе были представлены методы описания поведения двухкомпонентной сети, компонентами которой могут быть детерминированные автоматы или/и недетерминированные автоматы. В данном разделе мы распространяем-эти методы на произвольные многокомпонентные композиции автоматов.
В общем случае дискретная система может быть представлена композицией более чем двух компонент. Рассмотрим систему из п конечных автоматов Аъ ..., Ап(рис. 2.1).
Пусть Г = {G\, ..., Gm} есть множество всех входных и выходных алфавитов компонент системы. Внешние алфавиты системы задаются подмножеством 6 множества Г. Для автоматной сети на рисунке 2.1 множество внешних алфавитов есть Q = {1\, 12 0\, 02, Оз}. Распределение алфавитов по автоматам-компонентам определяет структуру системы, так как предполагается, что все полюсы, которым соответствует один и тот же алфавит, отождествлены между собой. Мы далее рассматриваем так называемые правильно построенные системы из полностью определенных автоматов, то есть системы, которые обладают следующими свойствами.
1. Один и тот же алфавит С7уєГ не может быть сопоставлен выходным полюсам различных компонент.
2. Среди алфавитов множества Г существует хотя бы один алфавит, который является только входным алфавитом автоматов-компонент.
3. Множество 0 содержит все алфавиты, которые являются только входными алфавитами автоматов-компонент, и хотя бы один алфавит, который сопоставлен выходному алфавиту некоторой компоненты.
4. Кроме того, мы полагаем, что ни одна из компонент не имеет изолированных полюсов. Иными словами, если входной (выходной) алфавит некоторой компоненты не содержится в множестве 9, то этот алфавит обязательно совпадает хотя бы с одним выходным (входным) алфавитом другой компоненты.
Мы вводим операцию многокомпонентной синхронной композиции г,в( і, ..., Ап), которая в нашей работе часто называется просто композицией. Входными алфавитами автомата г,в(Аъ ..., А ) являются алфавиты множества 9, которые являются только входными алфавитами компонент. Выходными алфавитами автомата г,е(Аъ ..., А ) являются алфавиты множества 0, которые являются выходными алфавитами автоматов-компонент.
Композиция, описывающая поведение многокомпонентной сети, может быть построена через операции над полуавтоматами [74, 50]. Пусть языки автоматов компонент представлены соответствующими полуавтоматами, известны множества Г и 0 с Г. Язык, описывающий синхронное поведение автоматной сети, можно построить следующим образом: 1. Описать поведение компоненты как части системы. 2. Описать совместное поведение компонент системы. 3. Описать внешнее (наблюдаемое) поведение системы. Алгоритм 2.1. Построение многокомпонентной композиции на основе операций над полуавтоматами. Вход: Автоматы-компоненты Аъ ..., Ат множество всех алфавитов Г и множество внешних алфавитов 9сГ.
Выход: Композиция г.еИъ ..., Ап). 1. Для каждой компоненты А7- строим полуавтомат Р ., который представляет язык автомата А-,-. 2. Каждый полуавтомат Р расширяем на те алфавиты из множества Г, которых нет в автомате А7-. При расширении сохраняется порядок алфавитов, как он определен в множестве Г. 3. Пересечение полуавтоматов (Рл.)\г определяет все возможные слова, которые могут появиться на полюсах компонент системы. Чтобы найти внешнее поведение системы, находим проекцию пересечения на внешние алфавиты сети, то есть на алфавиты множества 0. Приведенная форма автомата, соответствующего полученному полуавтомату )4-e, есть синхронная композиция »г е(Аъ ..., Ап).
Глобальная оптимизация
Пусть поведение системы описывается композицией конечных автоматов Аъ ..., Ат и 5- автомат-спецификация системы (рис. 3.1). Рисунок 3.1 - Многокомпонентная сеть из автоматов Как отмечалось в главе 1, во многих случаях компоненту Aj можно заменить не эквивалентным ей автоматом Bj так, что сети Ах ... Aj ... Ап и А± ... By ... Ап являются эквивалентными. Задача оптимизации заключается в выборе автомата Bj с лучшими свойствами (согласно некоторому критерию).
Множество компонент, которые могут заменить компоненту Aj без изменения внешнего поведения системы, может быть найдено посредством решения соответствующего автоматного уравнения Context Х S, где контекстный автомат Context= Аг ... Aj_x Aj+1 ... Ап есть композиция всех остальных компонент сети. Таким образом, при покомпонентной оптимизации автоматной сети возникает задача выбора по недетерминированному автомату (наибольшему решению) некоторой оптимальной редукции автомата в интересующем нас смысле. Наибольшее решение содержит все решения уравнения, поэтому любое требуемое оптимальное решение может быть выбрано из наибольшего решения, если компонента оптимизируется глобально, то есть относительно всех остальных компонент сети (рис. 3.2).
Проблема покомпонентной оптимизации автоматной сети может быть решена итеративным перебором всех компонент сети [67]. Начинаем с компоненты А± и полагаем, что все остальные компоненты .реализованы оптимально. Множество компонент, которые могут заменить компоненту Аг без изменения внешнего поведения сети, может быть найдено посредством решения автоматного уравнения Context Х= S, где контекстный автомат Context = А2т ...»Ап есть композиция всех остальных компонент сети. Оптимальное решение выбирается среди детерминированных редукций наибольшего решения. Аналогично оптимизируем, если возможно, компоненты А2, ..., Ат после чего возвращаемся к компоненте А±. Процесс прекращается, когда ни одна из компонент не может быть оптимизирована. Таким образом, на каждом шаге задача оптимизации сводится к нахождению наибольшего решения соответствующего автоматного уравнения и выбору его оптимальной редукции.
Достоинством данного подхода является существование общего (наибольшего) решения уравнения, которое описывает все возможные (допустимые) замещения интересующей нас компоненты. Однако данный подход требует большого объема промежуточных вычислений, в частности, при описании одним автоматом поведения многокомпонентной автоматной сети (автомат Context А2 ... А,). Для уменьшения объема вычислений предлагается использовать локальную оптимизацию, то есть «разрезать» автоматную сеть на части и оптимизировать ее по частям.
Ввиду ассоциативности операции композиции, можно использовать так называемую локальную оптимизацию (window approach). При локальном подходе каждая компонента оптимизируется не относительно всей сети, а только относительно непосредственно связанных с ней компонент. При этом размеры автоматов, коэффициентов уравнения, существенно меньше, чем в случае глобального подхода. В зависимости от топологии сети локальная оптимизация может быть осуществлена посредством решения множества автоматных уравнений или системы автоматных уравнений.
Наибольшее прогрессивное решение автоматного уравнения
Рассмотрим автоматную сеть на рисунке 4.1 и автоматное уравнение А Х= 5, где А и S- конечные автоматы с входными и выходными алфавитами 0\xU и 0\ Oi соответственно, X — неизвестная компонента. Так как в автоматной сети имеется обратная связь, то при синтезе неизвестной компоненты необходимо гарантировать отсутствие тупиков в синтезируемой системе. Полностью определенное решение автоматного уравнения с таким свойством называется композиционно прогрессивным или просто прогрессивным.
Рисунок 4.1- Автоматная сеть с обратной связью Формально, решение Prog уравнения называется прогрессивным, если-Prog есть полностью определенный автомат и полуавтомат А ti хо п pprog f і хо соответствует полностью определенному автомату с входным алфавитом І\ХІ2. Таким образом, если Prog -прогрессивное решение уравнения, то в любом состоянии полуавтомата РА Тг хо n Pprog tixo 5, которое достижимо из начального состояния, существует переход по любому входному символу из алфавита І\ХІ2, то есть поведение автоматной сети определено на любой входной последовательности. Более того, ни одна внешняя входная последовательность не может быть «блокирована», то есть независимо от выполняемого набора согласованных внутренних символов система сможет выдать выходной сигнал. Известно, что любое муровское решение является прогрессивным. Однако множество прогрессивных решений автоматного уравнения включает в себя не только автоматы Мура.
Согласно определениям операций над полуавтоматами справедлива следующая лемма о множестве последовательностей полуавтомата
Лемма 4.1. Последовательность р є I\xI2xUxVxO\x02 переводит полуавтомат РА х х0 n Pprog z х0 из начального состояния в состояние ар, если и только если (IixUxVxO\)-npoQKiw% (3 переводит контекстный автомат А из начального состояния в состояние а, а (/гхС/хКхОгЗ-проекция р переводит автомат Ргодиз начального состояния в состояние/?.
В работе [72] доказывается, что если автоматное уравнение имеет прогрессивное решение, то уравнение имеет и наибольшее прогрессивное решение. В общем случае, наибольшее прогрессивное решение является редукцией, но не подавтоматом наибольшего решения. Для нахождения наибольшего прогрессивного решения предлагается способ, основанный на удалении «плохих» последовательностей из наибольшего решения. Если наибольшее решение Largest уравнения прогрессивное, то Largest -наибольшее прогрессивное решение; но не всякая его редукция является прогрессивным решением. Если решение Largest не является прогрессивным, то язык автомата Largest «подстригается» таким образом, чтобы получить его наибольшее подмножество, обеспечивающее прогрессивное решение. Поскольку число последовательностей недетерминированного автомата бесконечно, основная сложность состоит в доказательстве сходимости предлагаемого алгоритма. Поскольку в общем случае наибольшее прогрессивное решение не всегда является подавтоматом наибольшего решения, то в работах [50, 76, 93] предлагается способ преобразования наибольшего решения в эквивалентный не приведенный автомат таким образом, что наибольшее прогрессивное решение является его подавтоматом. Построенный автомат называется совершенным в контексте автомата А и используется для описания всех прогрессивных решений уравнения. В данной главе мы показываем, что автомат, соответствующий полуавтомату (РА Ps) после удаления нефинальных состояний, построенный для получения наибольшего решения, является совершенным в данном контексте. Кроме того, используя подход, описанный выше, показываем, как для любого решения So 7 уравнения можно построить эквивалентный совершенный автомат Perfsol такой, что наибольшая прогрессивная редукция решения Sol (если существует), является подавтоматом автомата PerfSol.
Решение Perf= (Р, hxU, O2XV, Тр,ро) неравенства А Х S назовём совершенным в контексте A=(A,I\XV,0\XU,TA,CIO), если для любого состояния ар полуавтомата PA\t ю Pperffixo множество foxUxVxOz) проекций последовательностей, переводящих полуавтомат из начального состояния в состояние ар, совпадает с множеством последовательностей, которые переводят полуавтомат Ре гfиз начального состояния в состояние
