Оптимизация многокомпонентных дискретных систем на основе решения автоматных уравнений
На правах рукописи
Тихомирова Светлана Владимировна ОПТИМИЗАЦИЯ МНОГОКОМПОНЕНТНЫХ ДИСКРЕТНЫХ СИСТЕМ НА ОСНОВЕ РЕШЕНИЯ АВТОМАТНЫХ УРАВНЕНИЙ 05.13.01 – Системный анализ, управление и обработка информации (по отраслям информатики, вычислительной техники и автоматизации)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Томск – 2008
Работа выполнена на кафедре информационных технологий в исследова нии дискретных структур ГОУ ВПО «Томский государственный универси тет»
Научный консультант:
доктор технических наук, профессор Евтушенко Нина Владимировна
Официальные оппоненты:
доктор технических наук, профессор Каравай Михаил Федорович кандидат технических наук, доцент Громаков Евгений Иванович
Ведущая организация:
Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск
Защита состоится 17 апреля 2008 г. в 12 ч 30 мин на заседании диссертаци онного совета Д 212.267.12 при ГОУ ВПО «Томский государственный уни верситет» по адресу: 634050, г. Томск, пр. Ленина, 36.
С диссертацией можно ознакомиться в Научной библиотеке Томского го сударственного университета.
Автореферат разослан: 14 марта 2008 г.
Ученый секретарь диссертационного совета В.И. Смагин д.т.н., профессор
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы Автоматизация синтеза дискретных систем, в частности, цифровых схем, таких как большие интегральные схемы (БИС) и сверхбольшие инте гральные схемы (СБИС), была и остается одной из актуальных задач сис тем автоматизированного проектирования (САПР). Как известно, большин ство из существующих автоматизированных методов синтеза многокомпо нентных дискретных систем не позволяют синтезировать оптимальную схему. Проблема осложняется тем, что понятие оптимальности зависит от целей решаемой задачи, и, соответственно, задача оптимизации является многокритериальной. В некоторых случаях система должна соответство вать сразу нескольким критериям, однако некоторые из них являются взаи моисключающими. Например, отказоустойчивость систем обеспечивается за счет введения избыточности, таким образом, отказоустойчивая система не может иметь минимальное число элементов. Достаточно часто в качест ве критерия оптимальности выступают число внутренних состояний систе мы, число различных библиотечных модулей, количество связей между модулями и другие. Однако и для данных критериев задача построения оптимальной системы не является решенной. Одним из подходов к оптими зации многокомпонентных дискретных систем является покомпонентная оптимизация, когда компоненты оптимизируются последовательно и на каждом шаге проверяется, что новая реализация компоненты сохраняет внешнее поведение системы и улучшает предыдущую реализацию. Как известно, при использовании автоматной модели все допустимые реализа ции компоненты содержатся в наибольшем решении соответствующего автоматного уравнения. Поэтому исследование возможностей оптимизации дискретных систем и разработка соответствующих алгоритмов на основе решения автоматных уравнений являются актуальной задачей.
Цель работы Разработка методов оптимизации многокомпонентных дискретных сис тем на основе решения автоматных уравнений.
Методы исследования Для решения поставленных задач применяется аппарат дискретной ма тематики, в частности, теории автоматов, математической логики, а также проводятся компьютерные эксперименты с целью исследования эффектив ности предлагаемых методов.
Научная новизна 1. Для снижения сложности оптимизации многокомпонентных дис кретных систем предложен локальный подход, при котором компонента оптимизируется не относительно всей системы, а относительно соседних с нею компонент. Показано, что в этом случае для более эффективной оп тимизации компоненты можно использовать совокупность автоматных уравнений и/или систему автоматных уравнений.
2. Предложен алгоритм нахождения наибольшего решения в наиболь шем алфавите многокомпонентного автоматного уравнения. Такое наи большее решение содержит все оптимальные решения как специальные редукции.
3. Предложен метод нахождения наибольшего, в том числе наиболь шего прогрессивного, решения системы автоматных уравнений. Метод на хождения наибольшего прогрессивного решения системы автоматных уравнений расширяет известный метод нахождения наибольшего прогрес сивного решения одного автоматного уравнения.
4. Сформулированы необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения является прогрессивным решением.
5. Разработан алгоритм минимизации числа связей в автоматной сети на основе синтеза компоненты, которая зависит от меньшего числа вход ных переменных.
6. Предложены методы полиномиальной сложности для оптимизации компонент автоматной сети на основе решения уравнения. В частности, метод оптимизации автоматных сетей на основе безразличных последова тельностей расширен на автоматные сети с обратными связями;
сформули рованы достаточные условия существования комбинационного решения автоматного уравнения.
Основные положения, выносимые на защиту 1. Метод нахождения наибольшего решения в наибольшем алфавите для многокомпонентного автоматного уравнения. Такое наибольшее реше ние содержит все оптимальные решения как специальные редукции;
в ча стности, наибольшее решение в заданном алфавите (если такое решение существует) может быть получено как специальная редукция наибольшего решения в наибольшем алфавите.
2. Алгоритм минимизации числа связей в автоматной сети на основе нахождения полностью определенной редукции недетерминированного автомата, поведение которой существенно зависит от меньшего числа входных переменных.
3. Необходимые и достаточные условия того, что полностью опреде ленная редукция наибольшего прогрессивного решения является прогрес сивным решением, и метод нахождения наибольшего прогрессивного ре шения системы автоматных уравнений. Именно прогрессивные решения интересны с практической точки зрения.
Достоверность Все научные положения и выводы, содержащиеся в работе, основаны на утверждениях, доказанных с использованием аппарата дискретной ма тематики. Эффективность предложенных алгоритмов подтверждается ком пьютерными экспериментами.
Практическая значимость работы Предложенные в работе методы могут быть использованы на этапе ло гического проектирования для синтеза и оптимизации многокомпонентных дискретных систем. Метод, основанный на использовании безразличных последовательностей, был опробован на цифровых последовательностных схемах. Результаты показали, что число несущественных переходов в оп тимизируемой компоненте может достигать 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), Международном семинаре по проекту НАТО CBP.NR.CLG 982314 «Discrete event system optimization through automata/FSM equation solving» (Италия, 2007).
По результатам проведенных исследований опубликовано 9 статьей в научных журналах, а также 16 докладов и тезисов докладов на конферен циях различного уровня.
Структура и объем Диссертация состоит из введения, четырех глав, заключения и списка литературы из 93 наименований;
изложена на 145 страницах, включая рисунка, 5 таблиц.
КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении дается общая характеристика работы, обосновывается актуальность исследований, определяется тематика и формулируется цель работы, кратко излагаются основные задачи и результаты, выносимые на защиту.
Первая глава диссертации содержит необходимые определения, по становку задачи оптимизации на основе решения автоматных уравнений и обзор литературы по теме диссертации.
Одной из широко используемых моделей при синтезе и анализе дис кретных систем является конечный автомат, который описывает поведение системы, переходящей под действием входных воздействий из состояния в состояние и производящей при этом выходные сигналы.
Конечным автоматом, или просто автоматом, называется пятерка A = (A, I, O, TA, a0), где A – конечное непустое множество состояний с вы деленным начальным состоянием a0;
I – входной алфавит;
O – выходной алфавит;
TA I A A O – отношение переходов. Если для каждой пары (i, a) I A существует хотя бы один переход (i, a, a, o) TA, то автомат называется полностью определенным. Автомат называется детерминиро ванным, если для любой пары (i, a) I A существует не более одной пары (a, o) A O такой, что (i, a, a, o) TA, в противном случае автомат назы вается недетерминированным. Заметим, что входной (и/или выходной) ал фавит автомата может быть декартовым произведением нескольких алфа витов;
в этом случае говорят о множестве входных (и/или выходных) алфа витов автомата и о входных (и/или выходных) переменных, соответствую щих этим алфавитам.
Языком LA автомата A называется множество последовательностей входо-выходных пар в алфавите I O, получаемых при последовательных переходах из начального состояния. Автомат B = (B, I, O, TB, b0) называется подавтоматом автомата A, если B A, b0 = a0 и TB TA. Автомат B = (B, I, O, TB, b0) есть редукция автомата A (B A), если LB LA. Если LB = LA, то автоматы A и B эквивалентны (A B). Полностью определенный автомат, который не имеет эквивалентных состояний, называется приве денным. Автомат наблюдаемый, если для любой тройки (i, a, o) I A O существует не более одного состояния a A такого, что (i, a, a, o) TA.
Полуавтоматом называется пятерка P = (P, J, TP, p0, FP), где P – ко нечное множество состояний с выделенным начальным состоянием p0;
J – алфавит;
TP J P P – отношение переходов;
FP – множество финальных состояний. Язык полуавтомата есть множество последовательностей, кото рые переводят полуавтомат из начального в одно из финальных состояний.
Для любого полуавтомата P = (P, J, TP, p0, FP) можно построить эквива лентный ему детерминированный полуавтомат DP = (D, J, TD, d0, FD), мно жество состояний которого есть непустые подмножества состояний полу автомата P ;
подмножество d FD, если оно содержит хотя бы одно фи нальное состояние полуавтомата P ;
отношение переходов TD = {(j, d, d):
d = {p: p d: (j, p, p) TP}}.
Для автомата A = (A, I, O, TA, a0) можно построить соответствующий полуавтомат PA = (A, I O, TPA, a0, A) с тем же множеством состояний и начальным состоянием, каждое состояние является финальным. Множество действий полуавтомата есть декартово произведение входного и выходного алфавитов автомата, тройка (io, a, a) TPA, если и только если (i, a, a, o) TA.
Пусть P = (P, X V, TP, p0, FP) – полуавтомат с множеством действий X V. X-проекция PX = (R, X, TP X, p0, FP) получается после детерминиза ции полуавтомата P, который строится посредством «стирания» символа из V на каждом переходе полуавтомата P. Состояниями полуавтомата PX являются непустые подмножества множества P. Соответственно, операция проекции имеет экспоненциальную сложность.
X V U-расширение PU = (P, X V U, TPU, p0, FP) полуавтомата P есть полуавтомат с тем же множеством состояний, начальным состоянием и множеством финальных состояний, множество действий которого есть X V U. Для каждого перехода (xv, p, p) TP в полуавтомат PU добав ляются переходы (xvu, p, p) для всех u U.
Дополнение P = (PF, X V, TP, p0, FP ) детерминированного полуав томата P есть полуавтомат, множество состояний которого есть множество состояний полуавтомата P в объединении со специальным состоянием F P, множество финальных состояний FP = P\FP{F}. Для состояний p, p P тройка (xv, p, p) TP, если и только если (xv, p, p) TP. Если для пары (xv, p) не существует состояния p такого, что (xv, p, p) TP, то в по луавтомате P добавляется переход (xv, p, F). Кроме того, в состоянии F добавляется петля для любого символа xv X V.
Если множество входных алфавитов автомата B содержится в мно жестве входных алфавитов автомата A и, соответственно, множество вы ходных алфавитов автомата B содержится в множестве выходных алфави тов автомата A, то автомат B, расширение которого на алфавиты автомата A есть редукция A, называется (, )-редукцией автомата A.
Сложные дискретные системы обычно представляются в виде сети из взаимодействующих компонент. Если поведение каждой компоненты опи сано конечным автоматом, то совместное поведение всех компонент авто матной сети описывается композицией конечных автоматов. В диссертаци онной работе для описания поведения автоматной сети используется син хронная композиция конечных автоматов.
Формально синхронная композиция автоматов A и B на рис. 1 есть при веденный наблюдаемый автомат с входным алфавитом I1 I2 и выходным алфавитом O1 O2, который соответствует I1 O полуавтомату ( PA I 2 O2 PB I 1O1 ) I 1I 2 O1O2.
A Известно, что существует множество ав U V томатов, которые могут заменить компоненту I2 O B B, не изменяя внешнее поведение автоматной сети. Задача описания множества таких авто матов сводится к решению автоматного Рисунок 1 – Автоматная сеть уравнения A • X S, в котором X есть автомат с входным алфавитом I2 U и выходным алфавитом O2 V.
Выражение A • X S называется автоматным неравенством. Авто мат B с входным алфавитом I2 U и выходным алфавитом O2 V называет ся решением неравенства A • X S, если A • B S. Автомат B называется решением уравнения A • X S, если A • B S. Решение B называется пол ностью определенным, если B есть полностью определенный автомат. Мы далее рассматриваем только полностью определенные решения. Разреши мое автоматное уравнение имеет наибольшее решение, которое содержит все решения уравнения. Таким образом, задача оптимизации компоненты автоматной сети сводится к выбору оптимальной редукции наибольшего решения. Алгоритмы нахождения наибольшего решения автоматного урав нения предложены в работах Кима, Ньюборна, Ватанабе, Брайтона, Евту шенко, Виллы, Петренко и др. Однако во всех работах рассматривается двухкомпонентная автоматная сеть определенной структуры.
Любое решение автоматного уравнения является редукцией наиболь шего решения. Однако не всякая полностью определенная редукция такого решения является решением уравнения. Кроме того, не каждое решение автоматного уравнения подходит для практического использования. При оптимизации автоматных сетей с обратными связями могут быть выбраны только прогрессивные решения, которые гарантируют отсутствие тупиков в сети. Таким образом, остается открытым вопрос о полном описании ре шений автоматного уравнения, которые можно использовать при оптими зации соответствующей компоненты. С практической точки зрения суще ствующие методы нахождения наибольшего решения автоматного уравне ния имеют экспоненциальную сложность, что затрудняет их применение для многокомпонентных сетей. Поэтому, с одной стороны, необходимо уменьшать размерность автоматов-коэффициентов уравнения, а с другой стороны, находить, возможно, часть наибольшего решения, которая являет ся достаточно представительной и может быть найдена за достаточно ко роткое время. Необходимо также отметить, что в качестве единственного критерия при использовании автоматных уравнений для оптимизации ком поненты рассматривается число состояний компоненты. Алгоритмы выбо ра редукции недетерминированного автомата с минимальным числом со стояний предложены в работах Грацелли, Лючио, Ватанабе, Брайтона, Вет ровой и др. Данный критерий представляет скорее теоретический интерес, так как уменьшение числа состояний не всегда приводит к упрощению реа лизации.
Вторая глава диссертации посвящена решению автоматных уравне ний для многокомпонентной композиции. Напомним, что все известные методы решения автоматных уравнений разработаны для двухкомпонент ной автоматной сети. В данной работе мы вводим понятие автоматного уравнения для автоматной сети с произвольной структурой и произволь ным числом компонент.
В разд. 2.1 определяется операция синхронной композиции для много компонентной сети, и исследуются свойства такой композиции. Рассмотрим сеть из n конечных автоматов A1, …, An (рис. 2). Пусть = {G1, …, Gm} есть множество всех входных и выходных алфавитов компонент сети. Внешние алфавиты сети задаются подмножеством. Распределение алфавитов по автоматам-компонентам опреде O1 ляет структуру системы, так как пред I1 A A полагается, что все полюсы, которым O соответствует один и тот же алфавит, I2 An A A2 … отождествлены между собой. Синхрон … O3 ная композиция S = •, (A1, …, An) ав A An-1 томатов A1, …, An есть приведенный S наблюдаемый автомат, соответствую Рисунок 2 – Сеть из n автоматов щий полуавтомату (PA1 …P An ).
Показано, что операция синхронной композиции является коммутативной и ассоциативной.
В разд. 2.2 вводится определение многокомпонентного автоматного уравнения. Пусть в системе взаимодействующих автоматов известны эле менты A1, …, An1, структура и поведение системы, и необходимо описать поведение неизвестного автомата An такого, что •, (A1, …, An) S. Задача описания поведения неизвестной компоненты сводится к нахождению ре шения автоматного уравнения •, (A1, …, An1, X) S. Разрешимое авто матное уравнение имеет наибольшее решение. Пусть Largest есть наи больший полностью определенный подавтомат приведенного автомата, который соответствует полуавтомату •, (P A1,..., P An 1, PS ) после удаления нефинальных состояний, где есть множество алфавитов решения.
Теорема 1. Если автомат •, (A1, …, An1, Largest) эквивалентен ав томату S, то Largest есть наибольшее решение уравнения •, (A1, …, An1, X) S. Если автоматы •, (A1, …, An1, Largest) и S не эквивалентны, то уравнение не имеет решения.
Разрешимость автоматного уравнения существенно зависит от выбора алфавитов решения. В разд. 2.3 показано, что существует в некотором смысле наибольший алфавит. Если уравнение не разрешимо в этом алфави те, то оно не разрешимо и в любом другом алфавите. Идея нахождения ре шения в наибольшем алфавите заключается в следующем. В качестве мно жества выходных алфавитов неизвестной компоненты выбираем множе ство алфавитов, которые являются только входными алфавитами для ком понент, но не являются входными алфавитами автомата S, и выходные ал фавиты автомата S, которые не являются выходными алфавитами компо нент A1, …, An1. Все остальные алфавиты множества суть входные алфа виты неизвестной компоненты, множество которых обозначим.
Алгоритм 1. Построение наибольшего решения автоматного нера венства в наибольшем алфавите.
Вход: автоматы A1, …, An1 и S, множество всех алфавитов, множе ство внешних алфавитов, алфавиты решения =.
Выход: наибольшее решение неравенства Largestmax •, (A1, …, An1, X) S (если существует) в наибольшем алфавите.
1. Строим P = PA1... PAn 1 – пересечение полуавтоматов, соот ветствующих автоматам A1, …, An1.
2. Множество состояний автомата L есть множество состояний полу автомата P в объединении со специальным состоянием DNC. Для элемента g1…gm декартового произведения алфавитов из найдем проекцию a1,…,ak этого элемента на множество и проекцию b1…bt этого элемента на мно жество. В автомате L существует переход (a1…ak, p1... p n 1 s, p'1... p' n 1 s', b1…bt), если в полуавтомате P есть переход (g1…gm, p1... pn 1 s, p'1... p' n 1 s' ).
В автомате L существует переход (a1…ak, p1... p n 1 s, DNC, b1…bt), если в состоянии pj полуавтомата PAj отсутствует переход для проекции g1…gm на множество алфавитов PAj. В автомате L существует переход (a1…ak, DNC, DNC, b1…bt) для всех пар a1…ak, b1…bt. Автомат Largestmax есть приведенная наблюдаемая форма наибольшего полностью определенного подавтомата автомата L.
Теорема 2. Если автомат •, (A1, …, An1, Largestmax) не эквивален тен автомату S, то уравнение •, (A1, …, An1, X) S не имеет решения для любых алфавитов неизвестной компоненты.
В случае детерминированного автомата S сложность решения уравне ния в наибольшем алфавите является полиномиальной, так как не требует ся операция детерминизации полуавтомата. Более того, из этого решения можно получить решение уравнения в любых алфавитах (если такое реше ние существует).
Теорема 3. Пусть Largestmax есть наибольшее решение неравенства •, (A1, …, An1, X) S в наибольшем алфавите. Полностью определенный автомат Largest, с множеством входных алфавитов и множест вом выходных алфавитов есть наибольшее решение неравенства в алфа витах (, ), если Largest, есть наибольшая (, )-редукция автомата Largestmax.
Теорема 4. Если автомат •, (A1, …, An1, Largest, ) не эквивален тен автомату S, то уравнение •, (A1, …, An1, X) S не имеет решения с множеством входных алфавитов и множеством выходных алфави тов. Если •, (A1, …, An1, Largest, ) S, то Largest, есть наи большее решение уравнения в этих алфавитах.
В общем случае сложность нахождения наибольшего решения авто матного уравнения является экспоненциальной, что затрудняет применение данного подхода для оптимизации многокомпонентных систем. В разд. 2. предлагаются упрощенные алгоритмы, доставляющие не наибольшее решение, а только часть наибольшего решения, которая может быть вычис лена за достаточно короткое время и из которой можно выбрать оптималь ное решение. В частности, предлагается метод полиномиальной сложности нахождения комбинационного решения автоматного уравнения, т.е. реше ния с одним состоянием, так как комбинационные схемы обычно работают быстрее. Известный метод решения автоматного уравнения для последова тельной автоматной сети на основе безразличных последовательностей расширен на автоматные сети с обратными связями, причем сложность на хождения таких последовательностей является полиномиальной. Решение уравнения, полученное на основе безразличных последовательностей, яв ляется частичным детерминированным автоматом, и можно использовать известные алгоритмы для нахождения оптимального квазиэквивалентного автомата (согласно заданному критерию оптимизации).
В третьей главе диссертации рассматриваются различные подходы к оптимизации компонент автоматной сети на основе решения уравнений.
В разд. 3.1 рассматривается известный глобальный подход, когда каж дая компонента оптимизируется относительно всей автоматной сети.
Компоненты оптимизируются по очереди. Для каждой компоненты Aj ре шается соответствующее автоматное уравнение Context • X S, где Context = A1• … • Aj-1 • Aj+1 • … • An, находится наибольшее решение, и среди множества его редукций выбирается оптимальное решение.
Такой глобальный подход требует построения автомата Context, описывающего совместное поведение всех известных компонент. Для уменьшения объема вычислений в разд. 3.2 предлагается использовать ло кальную оптимизацию, т.е. рассматривать не всю автоматную сеть, а толь ко фрагмент, содержащий оптимизируемую компоненту и непосредственно связанные с ней компоненты. Пусть {A1, …, At} есть множество компо нент, непосредственно связанных с компонентой Aj. Задача оптимизации компоненты Aj сводится к решению множества автоматных уравнений { A1 • X A1 • Aj, …, At • X At • Aj }, причем в качестве оптимального решения можно выбрать решение любого уравнения из этого множества.
Как показывают эксперименты, проведенные на цифровых схемах, при ло кальном подходе остается достаточно возможностей для оптимизации.
Однако если все входы и выходы компоненты являются внешними по люсами оптимизируемого фрагмента (доступны для наблюдения), то ком понента может быть замещена только эквивалентным автоматом. Для такой топологии более эффективным является решение не множества, а системы автоматных уравнений. Системой автоматных уравнений называется ко нечная совокупность уравнений:
A1 • X S1,...
At • X St.
Наибольшее решение системы уравнений есть наибольший полностью определенный подавтомат пересечения наибольших решений всех уравне ний системы.
Разд. 3.3 посвящен критериям оптимизации компоненты.
В п. 3.3.1 в качестве критерия оптимизации рассматривается число связей в автоматной сети. Пусть входной алфавит компоненты An (рис. 3, а) есть G1 … Gk, где G1, …, Gk. Соответственно, автомат An имеет k входных переменных g1, …, gk, где переменная gj принимает значения из алфавита Gj, Gj. Пусть поведение компоненты An существенно не зави сит от переменной, соответствующей входному алфавиту Gj, т.е. реак ции автомата на любые две последовательности, которые отличаются зна чениями переменной, соответствующей входному алфавиту Gj, совпадают.
В этом случае компоненту An можно заменить компонентой An' с меньшим числом входных переменных (рис. 3, б). При этом внешнее поведение ав томатной сети не изменится.
G1 G2 G1 G Gj Gy Gy An An' Gm Gm S S а б Рисунок 3 – Автоматные сети Множество всех допустимых замещений компоненты описывается наибольшим решением соответствующего автоматного уравнения. Чтобы минимизировать число связей в автоматной сети, необходимо для оптими зируемой компоненты найти редукцию наибольшего решения соответст вующего автоматного уравнения, поведение которой существенно зависит от меньшего числа входных переменных. Таким образом, необходимо най ти редукцию наибольшего решения, являющуюся решением уравнения, множество входных алфавитов которой есть подмножество множества входных алфавитов наибольшего решения.
Пусть Largest – наибольшее решение с множеством входных ал фавитов и множеством выходных алфавитов автоматного уравнения •, (A1, …, An1, X) S относительно компоненты An.
Алгоритм 2. Нахождение наибольшей полностью определенной редукции с заданным множеством входных алфавитов.
Вход: автомат Largest, описывающий поведение компоненты авто матной сети, с множеством входных алфавитов и множеством выходных алфавитов, подмножество алфавитов.
Выход: наибольшая (, )-редукция автомата Largest, являющаяся решением уравнения •, (A1, …, An1, X) S, с множеством входных алфа витов (если существует).
1. Для автомата Largest строим соответствующий полуавтомат PL.
2. В полуавтомате PL неопределенные переходы доопределяем пере ходами в специальное состояние f. В состоянии f добавляем петлю по всем входо-выходным символам.
3. Берем проекцию PL полученного полуавтомата на алфавиты.
4. Удаляем из полуавтомата PL все состояния, соответствующие подмножествам, содержащим f, и переходы в такие состояния.
5. Строим автомат R, соответствующий полуавтомату PL, с множест вом входных алфавитов и множеством выходных алфавитов. Наиболь ший полностью определенный подавтомат RL автомата R (если существует) есть наибольшая полностью определенная (, )-редукция автомата Largest, являющаяся решением неравенства (согласно теореме 3). Если такого подавтомата не существует или •, (A1, …, An1, RL) S, то автомат Largest не имеет полностью определенных (, )-редукций, являющихся решением уравнения.
При построении редукции с заданным множеством входных алфавитов может потребоваться операция детерминизации, имеющая в общем случае экспоненциальную сложность. Поэтому для упрощения алгоритма миними зации входных переменных компоненты предлагается сначала удалить из наибольшего решения так называемые недопустимые состояния (относи тельно данной переменной), т.е. состояния, в которых поведение компо ненты существенно зависит от всех входных переменных. Затем для каж дого входного алфавита полученного автомата пытаемся построить редук цию, в которой отсутствует данный входной алфавит.
Алгоритм 3. Минимизация числа переменных, от которых суще ственно зависит компонента автоматной сети.
Вход: автоматы A1, …, An1, оптимизируемая компонента An, множест во всех входных и выходных алфавитов автоматов-компонент, множест во внешних алфавитов системы, множество входных и множество выходных алфавитов компоненты An.
Выход: редукция наибольшего решения автоматного уравнения •, (A1, …, An1, X) S, которая является решением уравнения и сущест венно не зависит от переменных, соответствующих некоторым входным алфавитам (если существует).
1. Находим наибольшее решение Largest с множеством входных алфавитов и множеством выходных алфавитов автоматного уравнения •, (A1, …, An1, X) S.
2. Для входного алфавита Gi (Gi ) итеративно удаляем Gi-недо пустимые состояния и переходы в такие состояния, а также переходы с Gi недопустимыми выходами. Если удаляется начальное состояние, то пове дение автомата Largest существенно зависит от входной переменной, соответствующей алфавиту Gi;
повторяем шаг 2 для следующего входного алфавита. Иначе шаг 3.
3. Строим редукцию Largest \Gi, автомата Largest с входным алфавитом \ Gi и выходным алфавитом, являющуюся решением уравне ния •, (A1, …, An1, X) S. Если такая редукция существует, то поведение автомата Largest существенно не зависит от входной переменной, соот ветствующей алфавиту Gi. Принимаем в качестве Largest автомат Largest \Gi,, и в качестве рассматриваем \ Gi. В противном случае не существует ( \ Gi, )-редукции автомата Largest, являющейся решением уравнения.
Если перебрали не все входные алфавиты, то шаг 2. Иначе конец.
Если существует решение уравнения •, (A1, …, An1, X) S, которое существенно не зависит хотя бы от одной из входных переменных, то ком поненту можно заменить автоматом с меньшим числом входных перемен ных, т.е. соответствующая линия связи в многокомпонентной сети является избыточной и может быть удалена.
В п. 3.3.2 в качестве критерия оптимизации рассматривается отказо устойчивость компоненты относительно выходных неисправностей. Все автоматы, которые могут заменить компоненту An без изменения внешнего поведения сети, суть редукции наибольшего решения Largest соответст вующего автоматного уравнения. Любая редукция An автомата Largest, являющаяся решением уравнения, описывает не обнаружимую неисправ ность. Чем больше выходных неисправностей компоненты An описываются редукциями автомата Largest, тем устойчивее композиция S к выходным неисправностям компоненты An.
В п. 3.3.3 в качестве критерия рассматривается число вентилей в логи ческой реализации. Приведены результаты экспериментов по локальной оптимизации цифровых схем на основе безразличных последовательностей (п. 2.3.3). Даже при выделении небольших фрагментов в ряде случаев воз можна оптимизация выделенного фрагмента по числу вентилей.
Четвертая глава диссертации посвящена разработке методов нахожде ния прогрессивных решений автоматных уравнений и систем автоматных уравнений. Именно такие решения интересны с практической точки зрения, так как при оптимизации автоматных сетей с обратными связями гаранти руют отсутствие тупиков, т.е. на любую внешнюю входную последо вательность сеть вырабатывает внешний выходной сигнал. Известно, что лю бой автомат Мура, являющийся решением уравнения, есть прогрессивное решение. Однако все прогрессивные решения не исчерпываются автомата ми Мура.
Для автоматной сети на рис. 1 полностью определенное решение Prog уравнения A • X S называется прогрессивным, если полуавтомат PA I 2 O2 PProg I1O1 соответствует полностью определенному автомату с входным алфавитом I1 I2.
Известно, что если существует прогрессивное решение, то существует наибольшее прогрессивное решение, которое в общем случае является ре дукцией, а не подавтоматом наибольшего решения автоматного уравнения.
Для нахождения наибольшей прогрессивной редукции Prog в известных работах строится специальный автомат Perf, эквивалентный наибольшему решению, такой, что Prog есть подавтомат автомата Perf.
В разд. 4.1 показано, что наибольшее прогрессивное решение является подавтоматом наибольшего решения, соответствующего полуавтомату (P A • PS ).
Теорема 5. Наибольшее прогрессивное решение автоматного уравне ния A • X S (если существует) есть подавтомат автомата, соответствую щего полуавтомату (P A • PS ) после удаления нефинальных состояний.
Как известно, не всякая полностью определенная редукция наиболь шего прогрессивного решения является решением уравнения. Более того, в работе показывается, что языковых свойств автомата недостаточно для описания всех прогрессивных решений. В разд. 4.2 устанавливаются необ ходимые и достаточные условия того, что полностью определенная редук ция наибольшего прогрессивного решения является прогрессивным реше нием.
Рассмотрим полуавтомат PA I 2 O2 PProg I1 O1 и алфавит (I2 U V O2).
Для каждого состояния ap полуавтомата и входного символа i1i2 I1 I через SubA (ap, i1i2) обозначим множество, содержащее (I2 U V O2) проекции всех символов, которые помечают переходы из состояния ap с внешним входным символом i1i2. Так как Prog – прогрессивное решение, то множество SubA (ap, i1i2) не пусто. Состоянию p автомата сопоставляем систему f(p) подмножеств SubA (ap, i1i2), где ap – состояние полуавтома та PA I 2 O2 PProg I1 O1, i1i2 I1 I2. Если для некоторого состояния p в полуавтомате отсутствуют состояния ap, то, по определению, полагаем множество f(p) пустым. Соответствие f назовем A-прогрессивным отобра жением множества состояний автомата Prog в совокупность подмножеств входо-выходных символов автомата.
Теорема 6. Пусть Prog – наибольшее прогрессивное решение уравне ния A • X S, полученное как подавтомат автомата, соответствующего полуавтомату (P A • PS ), и R – полностью определенная редукция автомата Prog. Автомат R является прогрессивным решением уравнения, если и только если для любого состояния rp пересечения R Prog множество f(p) не является пустым, множество входо-выходных пар в состоянии r пересе кает каждое подмножество из системы f(p), сопоставленной состоянию p автомата Prog.
При оптимизации многокомпонентных автоматных сетей в некоторых случаях возникает необходимость решения системы автоматных уравне ний, поэтому в разд. 4.3 предложенный метод нахождения наибольшего прогрессивного решения одного уравнения распространен на систему ав томатных уравнений.
Алгоритм 4. Построение наибольшего прогрессивного решения сис темы автоматных уравнений.
Вход: система автоматных уравнений Aj • X Sj, j = 1,.., n.
Выход: наибольшее прогрессивное решение системы уравнений (если существует).
1. Для каждого уравнения системы находим наибольшее решение Perfj = (Pj, I2 U, O2 V, TPj, p j0 ), соответствующее полуавтомату (PAj • PS j ).
2. Строим автомат Perf = Perf1... Perfn. Если пересечение не содержит полностью определенных подавтоматов, то система уравнений не имеет прогрессивного решения. Конец. Иначе шаг 3.
3. Для каждого уравнения системы находим наибольший полностью определенный подавтомат Perfj автомата Perf, который является про грессивным решением неравенства Aj • X Sj. Если композиция Aj • Perfj эквивалентна автомату Sj, то Perfj является прогрессивным решением уравнения Aj • X Sj. Если такого подавтомата для некоторого уравнения не существует, то система уравнений не имеет прогрессивного решения. Конец. Иначе шаг 2.
Повторяем шаги 2 и 3 до тех пор, пока не получим автомат, который после перебора всех уравнений системы больше не меняется, или ответ, что система уравнений не имеет прогрессивного решения.
Теорема 7. Если система уравнений Aj • X Sj, j = 1,.., n, имеет про грессивное решение, то алгоритм 4 доставляет наибольшее прогрессивное решение.
В разд. 4.4 приведены экспериментальные результаты по существова нию наибольшего прогрессивного решения автоматного уравнения для слу чайно сгенерированных автоматов, которые показали, что прогрессивное решение существует почти во всех случаях. Однако число состояний наи большего прогрессивного решения может превосходить число состояний наибольшего приведенного решения, т.е. наибольшее прогрессивное реше ние в общем случае является редукцией, а не подавтоматом наибольшего решения.
В заключении формулируются основные результаты работы.
1. Предложен новый подход к решению автоматного уравнения для оптимизации многокомпонентных автоматных сетей. Показано, что суще ствует наибольший алфавит решения. Если уравнение не разрешимо в наи большем алфавите, то оно не разрешимо ни в каком другом алфавите. Оп тимальное решение в заданных алфавитах есть специальная редукция наи большего решения в наибольшем алфавите.
2. Предложены алгоритмы полиномиальной сложности для построения части наибольшего решения автоматного уравнения. В частности, предло жены достаточные условия существования комбинационного решения ав томатного уравнения, а также алгоритм оптимизации компоненты на осно ве безразличных входных последовательностей распространен на сети с обратными связями.
3. Для снижения сложности оптимизации многокомпонентных авто матных сетей предложено от глобальной оптимизации перейти к локаль ной, т.е. рассматривать не всю сеть, а только фрагмент, содержащий опти мизируемую компоненту и непосредственно связанные с ней компоненты.
При локальном подходе задача оптимизации сводится к решению множест ва и/или системы автоматных уравнений.
4. Предложен алгоритм минимизации числа связей в автоматной сети на основе нахождения редукции наибольшего решения, которая сущест венно зависит от меньшего числа входных переменных.
5. Сформулированы необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения также является прогрессивным решением. Прогрессивные решения наибо лее интересны с практической точки зрения, так как гарантируют отсутст вие тупиков в оптимизируемой сети.
6. Предложены алгоритмы нахождения наибольшего и наибольшего прогрессивного решения системы автоматных уравнений.
Локальный подход к оптимизации с использованием безразличных по следовательностей опробован на цифровых схемах. Как показывают экспе рименты, при локальном подходе остается достаточно возможностей для оптимизации, что в ряде случаев приводит к более эффективной реализа ции компоненты по числу используемых вентилей.
Основные публикации по теме диссертации 1. Жарикова (Тихомирова) С. Оптимизация элементов цифровых схем посредством решения систем автоматных уравнений // Вестник ТГУ. Приложение. – 2002.
– № 1 (II). – С. 255–259.
2. Yevtushenko N. Multi component digital circuit optimization by solving FSM equations / N. Yevtushenko, S. Zharikova (Tikhomirova), M. Vetrova // Proceedings of the Euromicro symposium on digital system design. – Turkey, 2003. – P. 62–68.
3. Жарикова (Тихомирова) С. К синтезу отказоустойчивых элементов цифровых схем // Вестник ТГУ. Приложение. – 2003. – № 6. – С. 114–118.
4. Вилла Т. Характеризация живых решений синхронного автоматного уравнения / Т. Вилла, Н. Евтушенко, С. Жарикова (Тихомирова) // Вестник ТГУ. – Сентябрь 2003. – № 278. – С. 129–133.
5. Жарикова (Тихомирова) С. Решение автоматных уравнений в различных прило жениях / С. Жарикова, Н. Евтушенко // Вестник КрасГУ. Физико-математиче ские науки. – 2004. –№ 3. – С. 35–39.
6. Жарикова (Тихомирова) С. Автоматные уравнения и минимизация связей в ав томатных сетях // Вестник ТГУ. Приложение. – 2004. – № 9 (I). – С. 209–213.
7. Евтушенко Н.В. Достаточные условия существования комбинационного реше ния автоматного уравнения / Н.В. Евтушенко, С.В. Жарикова (Тихомирова) // Труды VI Международной конференции «Дискретные модели в теории управ ляющих систем». – М., 2004. – С. 100–103.
8. Жарикова (Тихомирова) С.В. Оптимизация бинарной композиции автоматов // Вестник ТГУ. Приложение. – 2005. – № 14. – С. 222–225.
9. Ветрова М.В. Исследование отношений совместимости между недетерминиро ванными автоматами / М.В. Ветрова, Н.В. Евтушенко, С.В. Жарикова (Тихоми рова), Н.В. Спицына // Вестник КрасГУ. Физико-математические науки. – 2006.
– № 4. – С. 20–27.
10. Жарикова (Тихомирова) С.В. Метод нахождения прогрессивного решения сис темы автоматных уравнений // Вестник ТГУ. Приложение. – 2006. – № 17.
– С. 20–24.
11. Zharikova (Tikhomirova) S.V. Minimization of communication wires in FSM composition / S.V. Zharikova, N.V. Yevtushenko // Proceedings of IEEE east-west design & test workshop. – Sochi, 2006. – P. 397–402.
12. Жарикова (Тихомирова) С.В. Решение автоматного уравнения для многомо дульной композиции / С.В. Жарикова, Н.В. Евтушенко // Вестник ТГУ. Прило жение. – 2007. – № 23. – С. 62–65.