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

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

ООЗ165914

Тихомирова Светлана Владимировна

ОПТИМИЗАЦИЯ МНОГОКОМПОНЕНТНЫХ ДИСКРЕТНЫХ СИСТЕМ НА ОСНОВЕ РЕШЕНИЯ АВТОМАТНЫХ УРАВНЕНИЙ

05 13 01 - Системный анализ, управление и обработка информации (по отраслям информатики, вычислительной техники и автоматизации)

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

2 7 МДР 2008

Томск - 2008

003165914

Работа выполнена на кафедре информационных технологий в исследовании дискретных структур ГОУ ВПО «Томский государственный университет»

Научный руководитель.

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

Евтушенко Нина Владимировна

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

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

Каравай Михаил Федорович

кандидат технических наук, доцент

Громаков Евгений Иванович

Ведущая организация:

Институт вычислительной математики и математической геофизики СО РАН, г Новосибирск

Защита состоится 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), Международном семинаре по проекту НАТО CBPNRCLG 982314 «Discrete event system optimization through automata/FSM equation solving» (Италия, 2007)

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

Структура и объем

Диссертация состоит из введения, четырех глав, заключения и списка литературы из 93 наименований, изложена на 145 страницах, включая 72 рисунка, 5 таблиц

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении дается общая характеристика работы, обосновывается актуальность исследований, определяется тематика и формулируется цель работы, кратко излагаются основные задачи и результаты, выносимые на защиту

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

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

Конечным автоматом, или просто автоматом, называется пятерка А = (А, I, О, ТА, а о), где А — конечное непустое множество состояний с выделенным начальным состоянием ай, I — входной алфавит, О — выходной алфавит, ТАс1х А хА х О — отношение переходов Если для каждой пары (г, а) е / х А существует хотя бы один переход (г, а, а', о) е ТА, то автомат

называется полностью определенным Автомат называется детерминированным, если для любой пары (;, а) е / х А существует не более одной пары (а', о) & А х О такой, что (;, а, а', о) е ТА, в противном случае автомат называется недетерминированным Заметим, что входной (и/или выходной) алфавит автомата может быть декартовым произведением нескольких алфавитов, в этом случае говорят о множестве входных (и/или выходных) алфавитов автомата и о входных (и/или выходных) переменных, соответствующих этим алфавитам

Языком ¿4 автомата А называется множество последовательностей входо-выходных пар в алфавите 1х О, получаемых при последовательных переходах из начального состояния Автомат В= (В, I, О, Тв, Ь0) называется подавтоматом автомата А, если В с: А, Ь0 = а0 и Тв с ТА Автомат В = (В, I, О, Тц, Ь0) есть редукция автомата А (В< А), если сг ЬА Если Ьв = ЬА, то автоматы А и В эквивалентны (А= В) Полностью определенный автомат, который не имеет эквивалентных состояний, называется приведенным Автомат наблюдаемый, если для любой тройки (г, а, о) е / х А х О существует не более одного состояния а'е. А такого, что (/, а, а', о) е ТА

Полуавтоматом называется пятерка Р = (Р, У, ТР,р0,РР), где Р — конечное множество состояний с выделенным начальным состоянием р0, J -алфавит, TpC.JxPxP — отношение переходов, - множество финальных состояний Язык полуавтомата есть множество последовательностей, которые переводят полуавтомат из начального в одно из финальных состояний Для любого полуавтомата Р=(Р,^ТР,р0,РР) можно построить эквивалентный ему детерминированный полуавтомат йр = (р, Тп, с!0, РГ)), множество состояний которого есть непустые подмножества состояний полуавтомата Р, подмножество с1 е если оно содержит хотя бы одно финальное состояние полуавтомата Р, отношение переходов Т0 = {(/, с1, </) <Г = {р' Эрв<1 0,р,р')Е ТР}}

Для автомата А = (А, I, О, ТА, а») можно построить соответствующий полуавтомат РА = (А, I х О, Г;,(, а0, А) с тем же множеством состояний и

начальным состоянием, каждое состояние является финальным Множество действий полуавтомата есть декартово произведение входного и выходного алфавитов автомата, тройка (ю, а, а') е ТР, если и только если

О, а, а', о) & ТА

Пусть Р=(Р,Х* V, ТР, рп, />) - полуавтомат с множеством действий I* V Х-проекция Р1х - (7?,X, р0, />) получается после детерминиза-

ции полуавтомата Р', который строится посредством «стирания» символа из V на каждом переходе полуавтомата Р Состояниями полуавтомата /Заявляются непустые подмножества множества Р Соответственно, операция проекции имеет экспоненциальную сложность

Xх Ух и-расширение Р\и = (Р,Х * Ух и, Г7,?ц,рй, />) полуавтомата Р

есть полуавтомат с тем же множеством состояний, начальным состоянием и множеством финальных состояний, множество действий которого есть X* Ух и Для каждого перехода (ху,р,р') е ТР в полуавтомат Р\ц добавляются переходы (хми, р, р') для всех и е и

Дополнение Р = (/'и/-', X х У, Т-, р0, ) детерминированного полуавтомата Р есть полуавтомат, множество состояний которого есть множество состояний полуавтомата Р в объединении со специальным состоянием

Р <£ Р, множество финальных состояний /*",, = />\7г,.и{/г} Для состояний р,р' е Р тройка (XV, р, р') е , если и только если (XV, р, р') е ТР Если для пары (ху, р) не существует состояния р' такого, что (XV, р, р') е ТР, то в полуавтомате Р добавляется переход (xv, р, Г) Кроме того, в состоянии Г добавляется петля для любого символаXV еХ* У

Если множество т входных алфавитов автомата В содержится в множестве входных алфавитов автомата А и, соответственно, множество V выходных алфавитов автомата В содержится в множестве выходных алфавитов автомата А, то автомат В, расширение которого на алфавиты автомата А есть редукция А, называется (т, V)-редукцией автомата А

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

Формально синхронная композиция автоматов А и В на рис 1 есть приведенный наблюдаемый автомат с входным алфавитом Л х /2 и выходным ^0 алфавитом 0\ х 02, который соответствует -—полуавтомату (Рм,2УОг ^ТлюА/^^хО,

Известно, что существует множество ав-I0 томатов, которые могут заменить компоненту

-——н»- В, не изменяя внешнее поведение автоматной

сети Задача описания множества таких автоматов сводится к решению автоматного Рисунок 1 - Автоматная сеть „ „

уравнения А • X = 5, в котором X есть автомат

с входным алфавитом /2 х и и выходным алфавитом 02х У

Выражение А • X < 5 называется автоматным неравенством Автомат В с входным алфавитом /2 х и и выходным алфавитом 02 х V называется решением неравенства А • X < 5, если А • В< 5 Автомат В называется

решением уравнения А • X = 5, если А • В~ 5 Решение В называется полностью определенным, если Я есть полностью определенный автомат Мы далее рассматриваем только полностью определенные решения Разрешимое автоматное уравнение имеет наибольшее решение, которое содержит все решения уравнения Таким образом, задача оптимизации компоненты автоматной сети сводится к выбору оптимальной редукции наибольшего решения Алгоритмы нахождения наибольшего решения автоматного уравнения предложены в работах Кима, Ньюборна, Ватанабе, Брайтона, Евтушенко, Виллы, Петренко и др Однако во всех работах рассматривается двухкомпонентная автоматная сеть определенной структуры

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

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

В разд 2 1 определяется операция синхронной композиции для многокомпонентной сети, и исследуются свойства такой композиции Рассмотрим

Ai

1

Aiy

tr

As

I

—r>- Аб

4/7-1

Q^

О,

О,

Рисунок 2 — Сеть из и автоматов

сеть из п конечных автоматов Ai, , Ап (рис 2) Пусть Г = {G,, , Gm} есть множество всех входных и выходных алфавитов компонент сети Внешние алфавиты сети задаются подмножеством 8сГ Распределение алфавитов

по автоматам-компонентам определяет структуру системы, так как предполагается, что все полюсы, которым соответствует один и тот же алфавит, отождествлены между собой Синхронная композиция 5 = *г,е (<4i, , Ап) автоматов А\, ,АП есть приведенный наблюдаемый автомат, соответствующий полуавтомату (/^^n )ie

Показано, что операция синхронной композиции является коммутативной и ассоциативной

В разд 2 2 вводится определение многокомпонентного автоматного уравнения Пусть в системе взаимодействующих автоматов известны элементы Ai, , An-г, структура и поведение системы, и необходимо описать поведение неизвестного автомата Ап такого, что «r,e (А\, , Ап) = 5 Задача описания поведения неизвестной компоненты сводится к нахождению решения автоматного уравнения *г,е (Ai, , An-i, Л) = 5 Разрешимое автоматное уравнение имеет наибольшее решение Пусть Largest есть наибольший полностью определенный подавтомат приведенного автомата,

который соответствует полуавтомату *Гр (Я^, , РАпЛ, Ps) после удаления

нефинальных состояний, где р есть множество алфавитов решения

Теорема 1. Если автомат •r.eiA, , An-1, Largest) эквивалентен автомату 5, то Largest есть наибольшее решение уравнения •reO^i, , An-i, X) = S Если автоматы •г.еСА, , An-i, Largest) и 5 не эквивалентны, то уравнение не имеет решения

Разрешимость автоматного уравнения существенно зависит от выбора алфавитов решения В разд 2 3 показано, что существует в некотором смысле наибольший алфавит Если уравнение не разрешимо в этом алфавите, то оно не разрешимо и в любом другом алфавите Идея нахождения решения в наибольшем алфавите заключается в следующем В качестве множества v выходных алфавитов неизвестной компоненты выбираем множество алфавитов, которые являются только входными алфавитами для компонент, но не являются входными алфавитами автомата 5, и выходные алфавиты автомата 5, которые не являются выходными алфавитами компонент Ах, , An-i Все остальные алфавиты множества Г суть входные алфавиты неизвестной компоненты, множество которых обозначим т

Алгоритм 1. Построение наибольшего решения автоматного неравенства в наибольшем алфавите.

Вход: автоматы А\, , Ап-г и 5, множество всех алфавитов Г, множество внешних алфавитов 6сГ, алфавиты решения р = т и V

Выход. наибольшее решение ¿ал5ге5Гтах неравенства •г е {Ах, , Ап-г, А) < 5 (если существует) в наибольшем алфавите

1 Строим Р = Я4|Тг п п/> Гг - пересечение полуавтоматов, соответствующих автоматам А\, , Ап-г

2 Множество состояний автомата £ есть множество состояний полуавтомата Р в объединении со специальным состоянием ВИС Для элемента

Ет декартового произведения алфавитов из Г найдем проекцию аи ,ак этого элемента на множество т и проекцию Ъ\ Ь, этого элемента на множество V В автоматесуществует переход (Д1 ак, рх р„-\я,р\ р'п_\ .у', Ьх 6,), если в полуавтомате Я есть переход (^ gm, Р\ Рп-15'Р'\ Р'п-1 В автомате /. существует переход (а, ак, Р\ р„_\ я, ЭИС, Ь\ Ь,), если в состоянии Р) полуавтомата РА] отсутствует переход для проекции g1 gm на множество алфавитов РА В автомате I. существует переход (а| ак,

ОЛ^С, ОЫС, Ъ\ Ь,) для всех пар а, ак, Ъх Ь, Автомат (.агдвБ^ах есть приведенная наблюдаемая форма наибольшего полностью определенного подавтомата автомата I

Теорема 2. Если автомат •г.еСА, ,Ап-1, ¡.агдвБТтах) не эквивалентен автомату 5, то уравнение «г.е (А\, , А^. 1, Л) = 5 не имеет решения для любых алфавитов неизвестной компоненты

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

Теорема 3. Пусть ¿агдв5^г.х есть наибольшее решение неравенства •г,в (А\, , Ар-1, X) < 5 в наибольшем алфавите Полностью определенный автомат агдевс множеством т'ст входных алфавитов и множеством V выходных алфавитов есть наибольшее решение неравенства в алфавитах (т', у), если ¡.агдеБ^ ч есть наибольшая (т', у)-редукция автомата 1.агде5и ах

Теорема 4. Если автомат •геИъ ,Ап-1, I-агдвБГт ,у) не эквивалентен автомату 5, то уравнение *г 0 (/41, , Ап-1, Л) = 5 не имеет решения с множеством входных алфавитов т'схи множеством выходных алфавитов V Если «геО^ь , Ап-1, ¡.агдев^ч) = 5, то 1.агде5есть наибольшее решение уравнения в этих алфавитах

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

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

В разд 3 1 рассматривается известный глобальный подход, когда каждая компонента оптимизируется относительно всей автоматной сети Компоненты оптимизируются по очереди Для каждой компоненты Aj решается соответствующее автоматное уравнение Context • X = 5, где Context =Ai» • Aj-i • Aj+i • • An, находится наибольшее решение, и среди множества его редукций выбирается оптимальное решение

Такой глобальный подход требует построения автомата Context, описывающего совместное поведение всех известных компонент Для уменьшения объема вычислений в разд 3 2 предлагается использовать локальную оптимизацию, т е рассматривать не всю автоматную сеть, а только фрагмент, содержащий оптимизируемую компоненту и непосредственно связанные с ней компоненты Пусть {Ai, , At} есть множество компонент, непосредственно связанных с компонентой Aj Задача оптимизации компоненты А3 сводится к решению множества автоматных уравнений {А\* X =А\» Aj, , At* X в At» Aj }, причем в качестве оптимального решения можно выбрать решение любого уравнения из этого множества Как показывают эксперименты, проведенные на цифровых схемах, при локальном подходе остается достаточно возможностей для оптимизации

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

автоматных уравнений Системой автоматных уравнений называется конечная совокупность уравнений

Л • X = 5Г

Наибольшее решение системы уравнений есть наибольший полностью определенный подавтомат пересечения наибольших решений всех уравнений системы

Разд 3 3 посвящен критериям оптимизации компоненты

В п 3 3 1 в качестве критерия оптимизации рассматривается число связей в автоматной сети Пусть входной алфавит компоненты Ап (рис 3, я) есть С, х х й/с, где Сь , е т Соответственно,

автомат Ап имеет к

входных переменных £Ь , gk, где переменная принимает значения из алфавита Ор С, е т Пусть поведение компоненты Ап существенно не зависит от переменной, соответствующей входному алфавиту С, е т, т е реакции автомата на любые две последовательности, которые отличаются значениями переменной, соответствующей входному алфавиту совпадают В этом случае компоненту Ап можно заменить компонентой Ап ' с меньшим числом входных переменных (рис 3, б) При этом внешнее поведение автоматной сети не изменится

а б

Рисунок 3 — Автоматные сети

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

Пусть Largest - наибольшее решение с множеством т входных алфавитов и множеством v выходных алфавитов автоматного уравнения •г,9 (<4i, , An-i, X) = 5 относительно компоненты Ап

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

Вход: автомат Largest, описывающий поведение компоненты автоматной сети, с множеством входных алфавитов т и множеством выходных алфавитов v, подмножество алфавитов х' с т

Выход: наибольшая (т', у)-редукция автомата Largest, являющаяся решением уравнения «г о (А, , Ap-i, Л) S, с множеством входных алфавитов т' (если существует)

1 Для автомата ¿arrestстроим соответствующий полуавтомат PL

2 В полуавтомате PL неопределенные переходы доопределяем переходами в специальное состояние / В состоянии /добавляем петлю по всем входо-выходным символам

3 Берем проекцию PLlz. полученного полуавтомата на алфавиты т'

4 Удаляем из полуавтомата PLii. все состояния, соответствующие подмножествам, содержащим/ и переходы в такие состояния

5 Строим автомат R, соответствующий полуавтомату PL±X, с множеством входных алфавитов х' и множеством выходных алфавитов v Наибольший полностью определенный подавтомат RL автомата R (если существует) есть наибольшая полностью определенная (т', у)-редукция автомата Largest, являющаяся решением неравенства (согласно теореме 3) Если такого подавтомата не существует или *ro(Ai, , An-1, Rl) ? S, то автомат Largest не имеет полностью определенных (т', у)-редукций, являющихся решением уравнения

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

Алгоритм 3. Минимизация числа переменных, от которых существенно зависит компонента автоматной сети.

Вход: автоматы Ai, , An-i, оптимизируемая компонента Ап, множество Г всех входных и выходных алфавитов автоматов-компонент, множество 9 с Г внешних алфавитов системы, множество х входных и множество v выходных алфавитов компоненты Ап

Выход: редукция наибольшего решения автоматного уравнения •г,в (Ai, , An-1, X) = S, которая является решением уравнения и сущест-

венно не зависит от переменных, соответствующих некоторым входным алфавитам (если существует)

1 Находим наибольшее решение Largest с множеством входных алфавитов х и множеством выходных алфавитов v автоматного уравнения •reO^i, ,An-i,X)~S

2 Для входного алфавита G, (G, е т) итеративно удаляем G,-недопустимые состояния и переходы в такие состояния, а также переходы с G,-недопустимыми выходами Если удаляется начальное состояние, то поведение автомата Largest существенно зависит от входной переменной, соответствующей алфавиту G„ повторяем шаг 2 для следующего входного алфавита Иначе шаг 3

3 Строим редукцию LargestTtG v автомата Largest с входным

алфавитом т \ G, и выходным алфавитом v, являющуюся решением уравнения *re(A, , An-1, X) = 5 Если такая редукция существует, то поведение автомата Largest существенно не зависит от входной переменной, соответствующей алфавиту G, Принимаем в качестве Largest автомат LargesttlG v, и в качестве т рассматриваем т \ G, В противном случае не

существует (т \G„ у)-редукции автомата Largest, являющейся решением уравнения

Если перебрали не все входные алфавиты, то шаг 2 Иначе конец Если существует решение уравнения «г.е (Ai, , An-i, X) = S, которое существенно не зависит хотя бы от одной из входных переменных, то компоненту можно заменить автоматом с меньшим числом входных переменных, т е соответствующая линия связи в многокомпонентной сети является избыточной и может быть удалена

В и 3 3 2 в качестве критерия оптимизации рассматривается отказоустойчивость компоненты относительно выходных неисправностей Все автоматы, которые могут заменить компоненту Ап без изменения внешнего поведения сети, суть редукции наибольшего решения A arrest соответствующего автоматного уравнения Любая редукция Ап' автомата Largest, являющаяся решением уравнения, описывает не обнаружимую неисправность Чем больше выходных неисправностей компоненты Ап описываются редукциями автомата Largest, тем устойчивее композиция 5к выходным неисправностям компоненты Ап

В п 3 3 3 в качестве критерия рассматривается число вентилей в логической реализации Приведены результаты экспериментов по локальной оптимизации цифровых схем на основе безразличных последовательностей (п 2 3 3) Даже при выделении небольших фрагментов в ряде случаев возможна оптимизация выделенного фрагмента по числу вентилей

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

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

Для автоматной сети на рис 1 полностью определенное решение Prog уравнения А • X ~ 5 называется прогрессивным, если полуавтомат PAbiMi гл PProgtiix0l соответствует полностью определенному автомату

с входным алфавитом /, х 12

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

В разд 4 1 показано, что наибольшее прогрессивное решение является подавтоматом наибольшего решения, соответствующего полуавтомату

(Рл «~PS )

Теорема 5. Наибольшее прогрессивное решение автоматного уравнения А» X = 5 (если существует) есть подавтомат автомата, соответствующего полуавтомату (РА • Ps) после удаления нефинальных состояний

Как известно, не всякая полностью определенная редукция наибольшего прогрессивного решения является решением уравнения Более того, в работе показывается, что языковых свойств автомата недостаточно для описания всех прогрессивных решений В разд 4 2 устанавливаются необходимые и достаточные условия того, что полностью определенная редукция наибольшего прогрессивного решения является прогрессивным решением v

Рассмотрим полуавтомат PA\iiy0l о Ppr0g4h*0\ и алфавит (I2xUxVx С>2)

Для каждого состояния ар полуавтомата и входного символа txi2 eh х h через SubA(ap, hh) обозначим множество, содержащее (/2х Uх Vх Ог)-проекции всех символов, которые помечают переходы из состояния ар с внешним входным символом i\i2 Так как Prog— прогрессивное решение, то множество SubA (ар, не пусто Состоянию р автомата сопоставляем систему J(p) подмножеств Sub а (ар, i\i2), где ар — состояние полуавтомата РА1/г>;02 n Рргод\1у*.0\ ' '1*2 6 h X h Если для некоторого состояния р в полуавтомате отсутствуют состояния ар, то, по определению, полагаем

множество j[p) пустым Соответствие / назовем ^-прогрессивным отображением множества состояний автомата Ргод в совокупность подмножеств входо-выходных символов автомата

Теорема 6. Пусть Ргод - наибольшее прогрессивное решение уравнения А» X = 5, полученное как подавтомат автомата, соответствующего

полуавтомату (РА *PS), и R - полностью определенная редукция автомата Ргод Автомат R является прогрессивным решением уравнения, если и только если для любого состояния гр пересечения Rr\ Ргод множество ftp) не является пустым, множество входо-выходных пар в состоянии г пересекает каждое подмножество из системы J[p), сопоставленной состоянию р автомата Ргод

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

Алгоритм 4. Построение наибольшего прогрессивного решения системы автоматных уравнений

Вход: система автоматных уравнений Aj • X = Sj,j =1, , п Выход: наибольшее прогрессивное решение системы уравнений (если существует)

1 Для каждого уравнения системы находим наибольшее решение Perfj = (Pj, I2x U, 02х V, TPj, ph), соответствующее полуавтомату (PAj • PSj)

2 Строим автомат Perf= Perf\c\ гл Perfn Если пересечение не содержит полностью определенных подавтоматов, то система уравнений не имеет прогрессивного решения Конец Иначе шаг 3

3 Для каждого уравнения системы находим наибольший полностью определенный подавтомат Perfj автомата Perf, который является прогрессивным решением неравенства Aj • X < Sj Если композиция Aj • Perfj эквивалентна автомату Sj, то Perfj является прогрессивным решением уравнения Aj • X = Sj Если такого подавтомата для некоторого уравнения не существует, то система уравнений не имеет прогрессивного решения Конец Иначе шаг 2

Повторяем шаги 2 и 3 до тех пор, пока не получим автомат, который после перебора всех уравнений системы больше не меняется, или ответ, что система уравнений не имеет прогрессивного решения

Теорема 7. Если система уравнений А3 • X = Sj, j = 1, , п, имеет прогрессивное решение, то алгоритм 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 équations / 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 Вилла Т Характеризация живых решений синхронного автоматного уравнения / Т Вилла, H Евтушенко, С Жарикова (Тихомирова) // Вестник ТГУ - Сентябрь 2003 -№278 -С 129-133

5 Жарикова (Тихомирова) С Решение автоматных уравнений в различных приложениях / С Жарикова, H Евтушенко // Вестник КрасГУ Физико-математические науки -2004 -№ 3 -С 35-39

6 Жарикова (Тихомирова) С Автоматные уравнения и минимизация связей в автоматных сетях // Вестник ТГУ Приложение -2004 -№9(1) -С 209-213

7 Евтушенко H В Достаточные условия существования комбинационного решения автоматного уравнения / H В Евтушенко, С В Жарикова (Тихомирова) // Труды VI Международной конференции «Дискретные модели в теории управляющих систем» -М,2004 -С 100-103

8 Жарикова (Тихомирова) С В Оптимизация бинарной композиции автоматов // Вестник ТГУ Приложение - 2005 - № 14 - С 222-225

9 Ветрова M В Исследование отношений совместимости между недетерминированными автоматами / M В Ветрова, H В Евтушенко, С В Жарикова (Тихомирова), H В Спицына // Вестник КрасГУ Физико-математические науки - 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 Жарикова (Тихомирова) С В Решение автоматного уравнения для многомодульной композиции / С В Жарикова, H В Евтушенко // Вестник ТГУ Приложение - 2007 - № 23 - С 62-65

ГТеч л 1 Тираж 100 экз Заказ № 21

Тираж отпечатан в типографии ИОА СО РАН

Введение.

1. Основные определения. Постановка задачи оптимизации на основе автоматной модели.

1.1 Основные определения.

1.1.1 Конечные автоматы.

1.1.2 Операции над автоматами и полуавтоматами.

1.1.3 Синхронная композиция двух автоматов.

1.1.4 Многокомпонентная синхронная композиция.

1.2 Постановка задачи оптимизации на основе решения автоматных уравнений.

1.2.1 Задача оптимизации.

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

1.3 Методы решения бинарных автоматных уравнений.

1.3.1 Решение уравнения на основе безразличных последовательностей.

1.3.2 Решение уравнения на основе Е-автомата.

1.3.3 Языковый подход к решению автоматных уравнений.

1.4 Критерии оптимизации.

1.5 Выводы по главе.

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

2.1 Многокомпонентная синхронная композиция.

2.1.1 Методы построения многокомпонентной синхронной композиции.

2.1.2 Свойства многокомпонентной композиции.

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

2.2.1 Решение автоматных уравнений для многокомпонентной композиции.

2.2.2 Сведение автоматного уравнения для многокомпонентной композиции к бинарному автоматному уравнению.

2.2.3 Разрешимость автоматного уравнения относительно различных алфавитов.

2.3 Упрощенные методы решения автоматных уравнений для оптимизации автоматных сетей.

2.3.1 Комбинационное решение автоматного уравнения.

2.3.2 Экспериментальные результаты по нахождению комбинационного решения.

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

2.3.4 Экспериментальные результаты по нахождению безразличных последовательностей.

2.4 Основные результаты главы.

3. Покомпонентная оптимизация дискретных систем относительно различных критериев.

3.1 Глобальная оптимизация.

3.2 Локальная оптимизация.

3.2.1 Локальная оптимизация посредством решения множества автоматных уравнений.

3.2.2 Локальная оптимизация посредством решения системы уравнений

3.3 Критерии оптимизации.94*

3.3.1 Число связей в автоматной сети.

3.3.1.1 О минимизации числа связей на основе решения автоматного уравнения.

3.3.1.2 Нахождение наибольшего решения автоматного уравнения с заданным множеством входных алфавитов.

3.3.1.3 Минимизация числа входных переменных компоненты.98'

3.3.2 Отказоустойчивость компоненты.

3.3.3 Число вентилей в логической реализации компоненты.

3.4 Основные результаты главы.

4. Прогрессивные решения автоматных уравнений и систем автоматных уравнений.

4.1 Наибольшее прогрессивное решение автоматного уравнения.

1 4.2 Характеризация прогрессивных решений.

4.3 Прогрессивные решения системы уравнений.

4.4 Экспериментальные результаты по существованию прогрессивных решений.

4.5 Основные результаты главы.

Актуальность проблемы

Автоматизация синтеза дискретных систем [1—3], в частности, цифровых схем, таких как большие интегральные схемы (БИС) и сверхбольшие интегральные схемы (СБИС) [4-9], была и остается одной из актуальных задач систем автоматизированного проектирования (САПР). Как известно, большинство из существующих автоматизированных методов [1013] синтеза многокомпонентных дискретных систем не позволяют синтезировать оптимальную систему. Проблема осложняется тем, что понятие оптимальности зависит от целей решаемой задачи, и, соответственно, задача оптимизации является многокритериальной. В некоторых случаях система должна соответствовать сразу нескольким критериям, причем некоторые из них являются взаимоисключающими. Например, отказоустойчивость систем обеспечивается за счет введения избыточности, таким образом, отказоустойчивая система не может иметь минимальное число элементов. Достаточно часто в качестве критерия оптимальности выступают число внутренних состояний системы [14-17], число различных библиотечных модулей [11, 12], количество связей между модулями [18 - 20] и другие [21, 22]. Однако и для данных критериев задача построения оптимальной системы не является решенной. Одним из подходов к оптимизации является итеративный подход, когда компоненты оптимизируются последовательно, и на каждом шаге проверяется, что новая реализация компоненты сохраняет внешнее поведение системы и улучшает предыдущую реализацию. Как известно [23 - 26], при использовании автоматной модели все допустимые реализации компоненты содержатся в наибольшем решении соответствующего автоматного уравнения. Поэтому исследование возможностей оптимизации дискретных систем и разработка соответствующих алгоритмов на основе решения автоматных уравнений является актуальной задачей.

Цель работы

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

Основные задачи

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

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

3. Исследование различных критериев оптимизации и разработка алгоритмов оптимизации компонент автоматной сети согласно заданным критериям.

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

Методы исследования

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

Научная новизна

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

2. Предложен алгоритм нахождения наибольшего решения в наибольшем алфавите многокомпонентного автоматного уравнения. Такое наибольшее решение содержит все оптимальные решения как специальные редукции.

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

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

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

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

Основные положения, выносимые на защиту

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

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

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 таблиц.

4.5 Основные результаты главы

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

ЗАКЛЮЧЕНИЕ

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

1. Глушков В.М. Синтез цифровых автоматов / В.М. Глушков. -М.: Физматгиз, 1962.-476 с.

2. Скобцов Ю.А. Логическое моделирование и тестирование цифровых устройств / Ю.А. Скобцов, В.Ю. Скобцов. Донецк: ИПММ НАН Украины, ДонНТУ, 2005. - 436 с.

3. Закревский А. Д. Алгоритмы синтеза дискретных автоматов / А.Д. Закревский. М.: Гл. ред. физ.-мат. лит., 1971. - 416 с.

4. Колдуэлл С. Логический синтез релейных устройств / С. Колдуэлл. — М.: ИЛ, 1962.-740 с.

5. Лазарев В.Г. Синтез управляющих автоматов / В.Г. Лазарев, Е.И. Пийль. М.: Энергия, 1970. - 400 с.

6. Закревский А.Д. Логический синтез каскадных схем / А.Д. Закревский. -М.: Наука, 1981.-416 с.

7. Автоматизированное проектирование цифровых устройств / С.С. Бадулин и др.. М.: Радио и связь, 1981. - 240 с.

8. Киносита К. Логическое проектирование СБИС / К. Киносита, К. Асада, О. Карацу. М.: Мир, 1988. - 309 с.

9. Черемесинова Л.Д. Синтез и оптимизация комбинационных структур СБИС / Л.Д. Черемесинова. Минск: ОИПИ НАН Беларуси, 2005. -241 с.

10. Gao M. The optimization of multi-valued multi-level networks / M. Gao, J-H. Jiang, Y. Jiang, Y. Li, A. Mishchenko, S. Sinha, T. Villa, R. Brayton // Proceedings of the 32nd IEEE ISMVL. 2002. - P. 168-177.

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

12. Grasselli A. A method for minimizing the number of internal states in incompletly specified sequential networks / A. Grasselli, F. Luccio // IEEE Transactions on electronic computers. 1965. - Volume EC-14. - №3. -P. 350-359.

13. Devadas S. Approaches to multi-level sequential logic synthesis // Proceedings of the 26th design automaton conference. USA, 1989. -P. 270-276.

14. PaulinP.G. Algorithms for high-level synthesis / P.G. Paulin, J.P. Knight // IEEE design & test. 1989. - Volume 6. - Issue 6 - P. 18-31.

15. Jozwiak L. An efficient method for the decomposition of sequential machines / L. Jozwiak, J. Kolsteren // Microprocessing and microprogramming. 1991. -Vol. 32.-P. 657-664.

16. Yang W.-L. Multi-way FSM decomposition based on interconnect complexity / W.-L. Yang, R.M. Owens, M.J. Irwin // Proceedings of the design automation conference. 1993. - P. 390-395.

17. Baumgartner J. Min-area retiming on flexible circuit structures / J. Baumgartner, A. Kuehlmann // Proceedings of the ICCAD. 2001. -P. 176-182.

18. Jiang J.-H. Retiming and resynthesis: A complexity perspective / J.-H. Jiang, R. Brayton // IEEE TCAD. 2006. - Volume 25 (12). - P. 2674-2686.

19. Petrenko A. Nondeterministic state machines in protocol conformance testing / A. Petrenko, N. Yevtushenko, A. Lebedev, A. Das // Proceedings of the IFIP 6th IWPTS. France, 1993. - P. 363-378.

20. Watanabe Y. The maximum set of permissible behaviors for FSM networks / Y. Watanabe, R.K. Brayton // Proceedings of the 1993 IEEE/ACM international conference on computer-aided design. USA, 1993. - P. 316320.

21. Petrenko A. Testing strategies for communicating finite state machines / A. Petrenko, N. Yevtushenko, R. Dssouli // Proceedings of the International-workshop on protocol test systems. Tokyo, Japan, 1994. Chapman & Hall, 1995.-P. 193-208.

22. Решение уравнений в логическом синтезе / Н. Евтушенко и др.. -Томск: Изд-во "Спектр", 1999. 27 с.

23. Жарикова (Тихомирова) С. Оптимизация элементов цифровых схем посредством решения систем автоматных уравнений // Вестник ТГУ. Приложение. 2002. - № 1 (Ц). - С. 255-259.

24. Жарикова (Тихомирова) С. К синтезу отказоустойчивых элементов цифровых схем // Вестник ТГУ. Приложение. 2003. - № 6. - С. 114— 118.

25. Вилла Т. Характеризация живых решений синхронного- автоматного уравнения / Т. Вилла, Н. Евтушенко, С. Жарикова (Тихомирова) // Вестник ТГУ. Сентябрь 2003. - № 278. - С. 129-133.

26. Жарикова (Тихомирова) С. Решение автоматных уравнений в различных приложениях / С. Жарикова, Н. Евтушенко // Вестник КрасГУ. Физико-математические науки. 2004. -№3. - С. 35-39.

27. Жарикова (Тихомирова) С. Автоматные уравнения и минимизация связей в автоматных сетях // Вестник ТГУ. Приложение: — 2004. -№ 9 (I). С. 209-213.

28. Жарикова (Тихомирова) С.В. Оптимизация бинарной композиции автоматов // Вестник ТГУ. Приложение. 2005. - № 14. - С. 222-225.

29. Ветрова М.В. Исследование отношений совместимости между недетерминированными автоматами / М.В. Ветрова, Н.В. Евтушенко, С.В. Жарикова (Тихомирова), Н.В. Спицына // Вестник КрасГУ. Физико-математические науки. 2006. - № 4. - С. 20-27.

30. Жарикова-(Тихомирова) С.В. Метод нахождения прогрессивного решения системы автоматных уравнений // Вестник ТГУ. Приложение. -2006.-№17.-С. 20-24.

31. Жарикова (Тихомирова) С.В. Решение автоматного уравнения для многомодульной композиции / С.В. Жарикова, Н.В. Евтушенко // Вестник ТГУ. Приложение. 2007. - № 23. - С. 62^65.

32. Жарикова (Тихомирова) С. Решение автоматных уравнений в различных приложениях / С. Жарикова // Тезисы докладов региональной научной конференции студентов, аспирантов, молодых ученых «Наука. Техника. Инновации». Новосибирск, 2001. - С. 6-7.

33. 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.

34. Zharikova (Tikhomirova) S. Minimization of communication wires by FSM equations solving / S. Zharikova, N. Yevtushenko // Proceedings of the work in progress session, Euromicro symposium on digital system design. France,2004.

35. Евтушенко Н.В. Достаточные условия существования комбинационного решения автоматного уравнения / Н.В. Евтушенко, С.В. Жарикова (Тихомирова) // Труды VI Международной конференции «Дискретные модели в теории управляющих систем». М., 2004. — С. 100-103.

36. Жарикова (Тихомирова) С.В. К оптимальной реализации цифровых схем // Сборник тезисов 11-й Всероссийской научной конференции студентов-физиков и молодых ученых. Екатеринбург, 2005. - С. 461— 462.

37. Kolomeets A.V. Digital controller for multiphase inverters / A.V. Kolomeets, M.L. Gromov, S.V. Zharikova (Tikhomirova), D.D. Popov // Proceedings of IEEE east-west design & test workshop. Ukraine, 2005. - P. 165-168.

38. 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.

39. Дорофеева М.Ю. Декомпозиция цифровых схем для оптимизации на основе безразличных последовательностей / М.Ю. Дорофеева, С.В. Жарикова (Тихомирова) // Материалы V Всесибирского конгресса женщин-математиков. Красноярск: РИО СФУ, 2008. - С. 136-139.

40. Мур Э.Ф. Умозрительные эксперименты с последовательными машинами / Э.Ф. Мур . М.: Изд-во иностр. лит., 1956. - С. 179-210.

41. Гилл А. Введение в теорию конечных автоматов / А. Гилл. М.: Изд-во «Наука», 1966. - 272 с.

42. Трахтенброт Б.А. Конечные автоматы: поведение и синтез / Б.А. Трахтенброт, Я.М. Барздинь. М.: Наука, 1970. - 400 с.

43. Агибалов Г.П; Лекции по теории конечных автоматов: учеб. пособие / Г.П. Агибалов, A.M. Оранов. Томск: Изд-во Томского Университета, 1984.- 184 с.

44. Hartmanis J. The algebraic structure theory of sequential machines / J. Hartmanis and R.E. Stearns. N.Y.: Prentice-Hall Inc. Englewood Cliffs, 1966.-210 p.

45. Kim J. The simplification of sequential machines with input restrictions / J. Kim and M.M. Newborn // IRE transactions on electronic computers. -1972.-P. 1440-1443.

46. Hassoun S. Optimization of synchronous circuits / S. Hassoun, T. Villa // Logic synthesis and verification. 2001. - P. 225-253.

47. West C.H. An automated technique of communication protocols validation // IEEE transactions on communications. 1978. - Volume 26. - P. 1271-1275.

48. BochmannG.v. Formal methods in communication protocol design /• G.v. Bochmann, C.A. Sunshine // IEEE transactions on communications. -1980. Volume 28. - P. 624-631. >.

49. Merlin P. On the construction of submodule specification and Communication protocols / P. Merlin, G.v. Bochmann // ACM transactions on programming languages and systems. 1983. - Volume 5. - Issue 1. -P. 1-25.

50. Kumar R. A discrete event systems approach for protocol conversion / R. Kumar, S. Nelvagal, S.I.Marcus // Discrete event dynamic systems: Theory & applications. 1997. - Volume 7 (3). - P. 295-315.

51. MangF. Games in open systems: Verification and synthesis: Ph.D. thesis / F. Mang. England, 1995. - 129 p.

52. Yevtushenko N. Synthesis by language equation solving: extended abstract / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Proceedings of annual Intern, workshop on logic synthesis. -2000.-P. 11-14.

53. Brand D. On communicating finite state machines / D. Brand, P. Zafiropulo I I J. ACM. 1983. - Volume 30 (2). - P. 323-342.

54. Агибалов Г.П. Декомпозиция конечных автоматов / Г.П. Агибалов, Н.В. Евтушенко. Томск: Изд-во Томского Университета, 1985. — 128 с.

55. Synthesis of finite state machines: Functional optimization / Kam T. and et.al.. Kluwer academic publishers, 1997. - 296 p.

56. WonhamW.M. Supervision of DES Электронный ресурс. / W.M. Wonham. Электрон, дан. - Торонто, 1999 - Режим доступа: http://www.control.utoronto.ca/DES, свободный.

57. Евтушенко Н.В. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей / Н.В. Евтушенко, А.Ю. Матросова // АВТ. 1991. - №2. - С. 3-7.

58. Лялин И.В. О решении автоматных уравнений / И.В. Лялин // Дискретная математика. 2004 - Т. 16, вып. 2. - С. 1-21

59. Yevtushenko N. Solution of synchronous language equations for logic synthesis / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Вестник ТГУ. Приложение. 2002. -№ 1 (II).-С. 132-138.

60. Yevtushenko N. Compositionally progressive solutions of synchronous language equations / N. Yevtushenko, T. Villa., R.K. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Proceedings of the IWLS. 2003. - P. 148155.

61. Rho J. Don't care sequences and the optimization of interacting finite state machines / J. Rho, G. Hatchel, F. Somenzi // Proceedings of the International conference on computer-aided design. 1991. - P. 418-421.

62. Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов: дис. . канд. техн. наук / Н.В. Спицына; Томский государственный ун-т. Томск, 2004. -160 с.

63. Gill A. Introduction to the theory of finite state machines / A. Gill. New York: McGraw-Hill, 1962.

64. El-Fakih Kh. Progressive solutions to a parallel automata equation / Kh. El-Fakih, N. Yevtushenko, S. Buffalov, G.v. Bochmann // Theoretical computer science. 2006. - Volume 362. - Issues 1-3. - P. 17-32.

65. Евтушенко H.B. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции: учебное пособие / Н.В. Евтушенко, А.Ф. Петренко, М.В. Ветрова. Томск: Томский государственный университет, 2006. - 142 с.

66. Starke Р.Н. Abstract Automata / Р.Н. Starke. N.Y.: American Elsevier publishing company, 1972. - 419 p.

67. Hopcroft J.E. Introduction to automata theory, languages and computation / J.E. Hopcroft, J.D. Ulman. Addison-Wesley publishing company, 1979. -418 p.

68. Khatri S. Engineering change in a non-deterministic FSM setting / S. Khatri, A. Narayan, S.C. Krishnan, K.L. McMillan, R.K. Brayton, A. Sangiovanni-Vincentelli // Proceedings of the IEEE/ACM'design automation conference. -USA, 1996.-P. 451-456.

69. Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ. 1996. - № 6. - С. 34-50.

70. Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов: дис. . канд. техн. наук / М.В. Ветрова; Томский государственный ун-т. Томск, 2004. - 150 с.

71. Каравай М.Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // АиТ. 1996. - №6. - С. 159-173.

72. Cohen P.R. Trial by fire: understanding the design requirements for agents in complex environments / P.R. Cohen, M.L. Greenberg, D.M. Hart, A.E. Howe // AI Magazine. 1989. - Volume 10. - Issue 3. - P. 34-48.

73. Corno F. RT-level ITC99 benchmarking and first ATGP results / F. Corno, M. Sonza Reorda, G. Squillero // IEEE design & test. Special issue on benchmarking for design and test. 2000. - P. 44-53.

74. Закревский А.Д. Основы логического проектирования. Оптимизация в булевом пространстве. Кн. 2. / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. Минск: ОИПИ НАН Беларуси, 2004. - 240 с.

75. Benchmarks Электронный ресурс. Электрон, дан. - Режим доступа: http://wwwxbl.ncsu.edu/benchmarks/LGSynth93/testcases/fsm/, свободный.

76. Павлов В.Л. Синтез комбинационных схем в произвольном базисе // Алгоритмы решения задач дискретной математики. 1987. - Вып. 2. -С. 53-58.

77. Синтез асинхронных автоматов на ЭВМ / под общ. ред. А.Д. Закревского. Минск: Наука и техника, 1975. — 184 с.

78. BraytonR.K. The decomposition and factorization of Boolean expressions / R.K. Brayton, C. McMullen // Proceedings of the ISCAS. 1982. - P. 29-54.

79. MishchenkoA. SAT-based complete don't-care computation for network optimization / A. Mishchenko, R. Brayton // Design, automation and test in Europe. 2005. - Volume 1. - P. 412-417.

80. Yevtushenko N. Compositionally progressive solutions of synchronous FSM equations / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Journal of discrete event dynamic systems. -2007.