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

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

Ляшов Максим Васильевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ СИНТЕЗА КОНЕЧНЫХ АВТОМАТОВ ДЛЯ АВТОНОМНЫХ ЭВОЛЮЦИОННЫХ АППАРАТНЫХ СРЕДСТВ

Специальности: 05.13.12 - Системы автоматизации проектирования

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

1 5 мдр 2012

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Таганрог 2012

005014613

Работа выполнена в Южно-Российском государственном университете экономики и сервиса.

Научнйй руководитель: кандидат технических наук, доцент

Берёза Андрей Николаевич

Официальные оппоненты: Чернышев Юрий Олегович

доктор технических наук, профессор, Донской государственный технический университет, профессор кафедры «Автоматизация производственных процессов»

Безуглов Дмитрий Анатольевич доктор технических наук, профессор, Ростовский технологический институт сервиса и туризма, заведующий кафедрой «Информационные технологии в сервисе»

Ведущая организация: ОАО «Таганрогский научно-

исследовательский институт связи», г. Таганрог

Защита диссертации состоится «12» апреля 2012 г. в 14:20 на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «05» марта 2012 г.

Ученый секретарь

диссертационного совета Целых А.Н.

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

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

В САПР для проектирования цифровых и аналоговых устройств в настоящее время применяются эволюционные алгоритмы (ЭА). Это направление получило название «эволюционная электроника» (Evolutionary Electronics). Применение ЭА на аппаратных платформах, имеющих реконфи-гурируемые элементы, позволяющие перестраивать систему во время функционирования, получило название эволюционные аппаратные средства. Научные исследования в этом направлении ведутся как в России, так и за рубежом. Результаты этих исследований приведены в работах В.М. Курейчика, В .В. Гудилова, C.B. Черуна, Д.Р. Коза, Г. Гариссона, Т. Хигучи, Д.Е. Голдберга, Е. Такахаши и др.

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

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

синтезируются, учитывая специфику функционирования целевого устройства.

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

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

В работах В.М. Курейчика, C.B. Черуна, В.В. Гудилова, Т. Хигучи и других представлены эволюционные алгоритмы синтеза комбинационных логических схем для ЭАС. Применяемые в настоящее время методы синтеза конечных автоматов всегда используют специфику решаемой задачи, делая полученную технику генерации автоматов неприменимой к остальным задачам. Возникает вопрос создания универсальных методов синтеза конечных автоматов, применимых к широкому кругу задач. В работах A.A. Шалыто, П.Г. Лобанова, Г. Хорихана, К. Вольфа и др. показано применение эволюционных алгоритмов для синтеза конечных автоматов. Однако представленные алгоритмы применяются для автоматного программирования, в рамках которого программа описывается с помощью конечных детерминированных автоматов, что не позволяет использовать их в автономных аппаратных системах на реконфигурируемых платформах.

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

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

Достижение указанной цели предполагает решение следующих основных задач:

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

2. Разработать генетический алгоритм кодирования состояний конечного автомата, который бы не уступал по эффективности существующим алгоритмам, используемым в современных САПР.

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

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

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

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

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

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

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

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

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

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

1. Генетический алгоритм кодирования состояний конечного автомата (по специальности 05.13.12).

2. Аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов (по специальности 05.13.12).

3. Устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС (по специальности 05.13.05).

4. Программный комплекс автоматизированного эволюционного синтеза конечных автоматов (по специальности 05.13.12).

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

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

• «Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.). Автором в качестве исполнителя были разработаны модифицированные генетические операторы для задачи автоматизации проектирования устройств вычислительной техники на схемотехническом и логическом уровнях.

• «Разработка и исследование реконфигурируемых гибридных эволюционных аппаратных систем» № 2.1.2/6959 (ЮРГУЭС-9.09.Ф). Автором в качестве исполнителя были разработаны: аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов; генетический алгоритм кодирования состояний конечного автомата; устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС.

• «Разработка и исследование бионических алгоритмов вычислительной математики для подсистемы схемотехнического моделирования» № 2.1.2/4595 (ЮРГУЭС-6.09.Ф). Автором в качестве исполнителя были разработаны генетические операторы для подсистем схемотехнического моделирования.

Кроме того, материалы диссертационной работы использованы в учебных процессах в ФГБОУ ВПО ЮРГУЭС (г. Шахты) на кафедре «Информационные системы и радиотехника» в дисциплинах «Интеллектуальные информационные системы», «Архитектура ЭВМ и систем», «Цифровые устройства и микропроцессоры», ВИС ФГБОУ ВПО ЮРГУЭС (г. Волгодонск) на кафедре «Информационные технологии» в дисциплинах «Архитектура ЭВМ и систем», «Интеллектуальные информационные системы» и в ШИ(Ф) ФГБОУ ВПО ЮРГТУ(НПИ) (г.Шахты) на кафедре «Электрификация и автоматизация производства» в

дисциплинах «Автоматизация установок и комплексов», «Основы микропроцессорной техники» и «Элементы систем автоматики».

Апробация Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 20082011 гг.); Конгрессе по интеллектуальным системам и информационным технологиям «А18-1Т'09»; Международной научно-практической конференции «Научный потенциал молодёжи - будущее России» (г. Волгодонск, 2010 г.), Всероссийской научной конференции молодых ученых и аспирантов (г. Волгодонск, 2009 г.).

Публикации. По материалам диссертационной работы опубликовано 16 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК, получено 6 свидетельств об официальной регистрации программы для ЭВМ, сделано 9 докладов на Всероссийских и Международных научно-технических конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 176 страниц, включающих 59 рисунков, 14 таблиц, список литературы из 139 наименований, 20 страниц приложений и актов об использовании.

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

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

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

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

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

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

Структурная схема разработанного аппаратно-ориентированного генетического алгоритма синтеза конечных автоматов, предназначенного для создания эволюционных аппаратных средств на реконфигурируемых платформах, приведена на рисунке 1.

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

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

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

Рисунок 1 - Структурная схема аппаратно-ориентированного генетического алгоритма синтеза конечных автоматов

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

Алгоритм модифицированного оператора мутации состоит из следующих шагов:

Шаг 1. Генерируется случайное число 5, равномерно распределённое в интервале [0; и], где п - число переходов конечного автомата.

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

ШагЗ. Если было определено, что изменяется значение выходной переменной, то оно случайным образом изменяется в переходе с индексом 5.

Шаг 4. Если было определено, что изменяется номер состояния, то он случайным образом изменяется в переходе с индексом 5.

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

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

Для исправления подобных ошибок был разработан алгоритм корректировки переходов, состоящий из следующих шагов:

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

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

Шаг 3. Если текущее состояние не входит в список доступных, то для него выполняются следующие операции.

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

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

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

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

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

Рисунок 2 - Структурная схема генетического алгоритма кодирования состояний конечного автомата

При решении задачи кодирования состояний конечного автомата используется целевая функция:

k=0

где \Xq„Xqj\ - расстояние по Хеммингу между кодами состояний ¿-ого

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

Задачей генетического алгоритма является минимизация целевой функции:

F -> min.

Предельным случаем задачи является кодирование, при котором F = р , т.е. одно переключение элемента памяти на каждом переходе.

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

Модифицированный оператор мутации в разработанном алгоритме работает следующим образом: в хромосоме случайно выбираются два гена и меняются местами.

Теоретически было установлено, что при фиксированных значениях размера популяции и числа генераций, разработанные генетические алгоритмы имеют полиномиальную временную сложность 0(N2), где N -количество состояний конечного автомата.

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

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

В диссертационной работе эта проблема решается двумя путями: • созданием реконфигурируемой структуры на ПЛИС, позволяющей

реализовывать комбинационные схемы любой сложности;

• применением встроенных блоков памяти ПЛИС для реализации комбинационных схем.

На рисунке 3 показана разработанная реконфигурируемая структура на ПЛИС для создания динамически реконфигурируемых комбинационных логических схем. В качестве универсального реконфигурируемого логического элемента был использован мультиплексор.

Рисунок 3 - Реконфигурируемая структура на ПЛИС

Реконфигурируемый модуль представляет собой матрицу из реконфигурируемых логических блоков (РЛБ). Основное отличие предлагаемой структуры, по сравнению с аналогами, - это возможность за один такт полностью перестраивать комбинационную схему, что позволяет создавать высокопроизводительные ЭАС.

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

Разработанный генетический алгоритм кодирования состояний конечного автомата был протестирован на промышленных тестовых задачах MCNC. На рисунке 4 приведено сравнение эффективности разработанного генетического алгоритма кодирования состояний (ГАКС) с двумя вариантами алгоритма NOVA и аналогичного генетического алгоритма.

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

из приведенного графика, результаты в среднем на 20% лучше, чем у существующих алгоритмов.

Рисунок 4 - Сравнение эффективности разработанного генетического алгоритма кодирования состояний с аналогами

Разработанный аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов был протестирован на тестовых задачах об «Умном муравье» и построении автопилота для упрощенной модели вертолета. По количеству состояний синтезируемых конечных автоматов разработанный алгоритм не уступает аналогам, при этом время синтеза в 9 раз меньше, чем у существующих алгоритмов.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Определены основные этапы проектирования эволюционных аппаратных средств на ПЛИС и принципы оперативного изменения поведения системы. Предложен вариант отладки эволюционных аппаратных средств с использованием встроенных средств ПЯИС, позволяющий регистрировать состояния не только входов и выходов системы, но и состояния произвольных внутренних узлов.

3. Разработаны аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов и генетический алгоритм кодирования состояний конечного автомата, предназначенные для синтеза КА в автономных эволюционных аппаратных средствах. Найдены теоретические оценки временной сложности разработанных алгоритмов - 0(N2).

4. Выполнена аппаратная реализация генетического алгоритма для решения задач автоматизированного синтеза конечных автоматов на ПЛИС, которая позволила сократить время поиска решения более чем в 60 раз, что в свою очередь дает возможность использовать разработанные генетические алгоритмы в автономных эволюционных аппаратных средствах. Разработана реконфигурируемая структура на ПЛИС и предложено применение встроенных блоков памяти для создания перестраиваемых комбинационных логических схем. Это позволило создавать конечные автоматы для ЭАС с динамической перестройкой внутренней структуры.

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

6. Выполнено сравнение разработанных генетических алгоритмов. Генетический алгоритм кодирования состояний конечного автомата сравнивался с аналогом и классическими алгоритмами NOVA1, NOVA2 на промышленных тестовых задачах MCNC. Полученные результаты в среднем на 20% лучше, чем у существующих алгоритмов. Сравнение разработанного генетического алгоритма синтеза конечных автоматов проводилось на тестовых задачах об «Умном муравье» и построении автопилота для упрощенной модели вертолета. По количеству состояний синтезируемых конечных автоматов разработанный алгоритм не уступает аналогам, при этом время синтеза в 9 раз меньше, чем у существующих алгоритмов.

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

Публикации в ведущих рецензируемых изданиях, рекомендованных

ВАК РФ

1. Ляшов М.В., Берёза А.Н. «Аппаратная реализация нечетких контроллеров на ПЛИС». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2008, №4(81).-199-204 с. '

2. Ляшов М.В., Берёза А.Н. «Аппаратная реализация нелинейных математических функций для нейронных сетей». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». -Таганрог: Изд-во ТТИ ЮФУ, 2008, №9(86). -194-198 с.

3. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Аналитический обзор реконфигурируемых гибридных эволюционных аппаратных систем». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2009, №12(89). -185-189 с.

4. Ляшов М.В., Берёза А.Н. «Эволюционный синтез конечных автоматов». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2011. - №7. -201-217 с.

Свидетельства о государственной регистрации программ для ЭВМ

5. Ляшов М.В., Берёза А.Н. «Библиотека элементов генетических алгоритмов (LEGA)». Свидетельство № 2009611956,2009 г.

6. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Бионический алгоритм решения систем линейных алгебраических уравнений». Свидетельство № 2009616993, 2010 г.

7. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Алгоритм расчета оптимального шага аппроксимации активационной функции нейрона». Свидетельство № 2010611341,2010 г.

8. Ляшов М.В., Берёза А.Н., Бегляров В.В., Стороженко A.C. «Библиотека оптимизационных алгоритмов для подсистемы схемотехнического проектирования ЭВТ». Свидетельство № 2011613831, 2011 г.

9. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Библиотека алгоритмов вычислительной математики для подсистемы схемотехнического моделирования ЭВТ». Свидетельство № 2011614136,2011 г.

10. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Инструментальная среда проектирования и исследования генетических алгоритмов «ОАВшШег»». Свидетельство № 2011614981, 2011 г.

Публикации в других изданиях

11. Ляшов М.В, «Разработка ядра АУЯ-микроконтроллера для ПЛИС на АНБЬ (1РСоге)». Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, июнь-октябрь 2005 г., г.Шахты / ред. кол.: А.Э.Попов [и др.]. -Шахты: Изд-во ЮРГУЭС, 2005. - 82 е., стр. 72-73.

12. Ляшов М.В., Берёза А.Н. «Разработка сумматора с плавающей точкой на базе интегральных схем с перестраиваемой структурой». Проблемы экономики, науки и образования в сервисе: Сб. науч. трудов / Под ред. П.Д. Кравченко. - Шахты. Изд-во ЮРГУЭС, 2005. 285 е., стр. 151-153.

13. Ляшов М.В., Берёза А.Н., Семенищев Е.А. «Аппаратная реализация умножителя с плавающей запятой на ПЛИС». Проблемы экономики, науки и образования в сервисе: Сб. науч. трудов / Под ред. П.Д. Кравченко. - Шахты. Изд-во ЮРГУЭС, 2005.-285 е., стр. 153-155.

14. Ляшов М.В., Берёза А.Н. «Разработка и применение СФБ в системах на кристалле на базе ПЛИС (БоС)». Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, апрель-июнь 2006 г., г.Шахты / ред. кол.: А.ЭЛопов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2006. - 70 е., стр. 51-52.

15. Ляшов М.В., Берёза А.Н. «Сложный функциональный- блок АУЯ-микроконтроллера для проектирования систем на базе ПЛИС». Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, апрель-июнь 2006 г., г.Шахты / ред. кол.: А.Э.Попов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2006. - 70 е., стр. 52-56.

16. Ляшов М.В., Берёза А.Н. «Построение аппаратного ускорителя для систем автоматизированного проектирования». Информационные системы и технологии. Теория и практика: сб. науч. тр. / под ред. А.Н. Берёза. - Шахты: Изд-во ЮРГУЭС, 2008. - 189 е., стр. 55-63.

17. Ляшов М.В., Берёза А.Н. «Нечёткий контроллер с генетической подстройкой». Информационные технологии, системный анализ и управление: VI всероссийская научная конференция молодых ученых, аспирантов и студентов, сб. тр. - Таганрог: Изд-во ТТИ ЮФУ, 2008 - 206 е., стр. 154-156.

18. Ляшов М.В., Берёза А.Н. «Генетический нечеткий контроллер». Информационные системы и технологии. Теория и практика : сб. науч. тр. /

редкол.: А.Н. Береза [и др.]. - Шахты : ГОУ ВПО «ЮРГУЭС», 2009. - 209 е., стр. 45-53.

19. Ляшов М.В., Берёза А.Н. «Аппаратный модуль генетического алгоритма для встраиваемых систем». Информационные технологии в науке и образовании: материалы международной научно-практической интернет-конференции и IV Всероссийского семинара «Применение MOODLE в сетевом обучении», 6-9 апреля 2010 г. (Железноводск). - Шахты: ГОУ ВПО «ЮРГУЭС», 2010.-221 е., стр. 146-148.

20. Ляшов М.В., Берёза А.Н., Кузнецов П.С. «Анализ способов построения конечных автоматов - основы аппаратных биоинформационных систем». Информационные технологии в науке и образовании: материалы международной научно-практической интернет-конференции и IV Всероссийского семинара «Применение MOODLE в сетевом обучении», 6-9 апреля 2010 г. (Железноводск). - Шахты: ГОУ ВПО «ЮРГУЭС», 2010. - 221 е., стр. 159-166.

21. Ляшов М.В., Берёза А.Н. «Реконфигурируемый нейросетевой ускоритель на ПЛИС». Современные проблемы радиоэлектроники: Сборник научных трудов. Издательство РТИСТ ГОУ ВПО «ЮРГУЭС», 2010. - 420 е., стр. 367-375.

22. Ляшов М.В. «Генетический алгоритм кодирования состояний конечного автомата». Информационные системы и технологии. Теория и практика: сб. науч. тр. / редкол.: А.Н. Береза [и др.]. - Шахты : ФГБОУ ВПО «ЮРГУЭС», 2011. - 209 е., стр. 68-75.

Личный вклад автора в работах, опубликованных в соавторстве: [1- 4] - обзор и анализ существующих методов и архитектур, а также разработка алгоритмов, [5, 10] - разработка эволюционных алгоритмов и генетических операторов, [12-21] - разработка архитектур, программная и аппаратная реализация предлагаемых алгоритмов.

Соискатель ¿¿¿fa М.В. Ляшов

Подписано в печать 02.03.2012г. Формат 60x84/16 Бумага офсетная. Рккнрафия. Усл.п.л. 1,0. Тираж 100 экз. Зак.45. Отпечатано в типографии: ИП Бурыхина Б.М Адрес типографии: 346500, Ростовская обл., г.Шахты, ул. Шевченко, 143.

61 12-5/3202

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования Южно-Российский государственный университет экономики и сервиса

(ФГБОУ ВПО «ЮРГУЭС»)

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

Л

Ляшов Максим Васильевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ СИНТЕЗА КОНЕЧНЫХ АВТОМАТОВ ДЛЯ АВТОНОМНЫХ ЭВОЛЮЦИОННЫХ

АППАРАТНЫХ СРЕДСТВ

Специальности: 05.13.12 - Системы автоматизации проектирования

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

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: к.т.н., доцент Берёза А.Н.

Таганрог - 2012 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1 Исследование способов создания автономных систем на основе эволюционных аппаратных средств

1.1 Эволюционные аппаратные средства 12

1.2 Классификация эволюционных аппаратных средств 15

1.3 Анализ алгоритмов синтеза конечных автоматов 17

1.3.1 Минимизация и кодирование внутренних состояний ^ конечных автоматов

1.3.2 Двухуровневый и многоуровневый синтез 21

1.4 Постановка задачи диссертационной работы 25

1.5 Выводы 29

2 Особенности проектирования эволюционных аппаратных средств с ^ использованием современных САПР

2.1 Этапы проектирования эволюционных аппаратных средств на ^ ПЛИС

2.2 Использование встроенных средств ПЛИС для отладки ^ эволюционных аппаратных средств

2.3 Принципы оперативного изменения поведения системы 48

2.4 Маршрут проектирования эволюционных аппаратных средств на ^ ПЛИС

2.5 Выводы

3 Разработка эволюционных алгоритмов синтеза конечных автоматов 58

3.1 Построение реконфигурируемых конечных автоматов на ПЛИС 58

3.1.1 Разработка реконфигурируемой структуры на ПЛИС 59

3.1.2 Применение блоков памяти ПЛИС для реализации комбинационных схем

3.2 Генетический алгоритм кодирования состояний конечного ^ автомата и его теоретическая оценка

3.3 Аппаратно-ориентированный генетический алгоритм синтеза ^ конечных автоматов и его теоретическая оценка

108

3.4 Разработка устройства аппаратной реализации генетического алгоритма

3.4.1 Технические характеристики устройства аппаратной реализации генетического алгоритма

3.5. Выводы 109

4 Экспериментальные исследования разработанных алгоритмов 111

4.1 Разработка инструментальной среды 111

4.2 Определение управляющих параметров разработанных генетических алгоритмов

4.3 Определение временной сложности разработанных генетических алгоритмов

114 121

4.4 Сравнение результатов генетического алгоритма кодирования состояний конечного автомата

4.5 Сравнение результатов генетического алгоритма синтеза конечных автоматов

4.5.1 Задача об «Умном муравье» 128

4.5.2 Задача построения автопилота для упрощенной модели ^ ^ вертолета

4.6 Выводы 139 Заключение 141

Библиографический список 143

Приложение А - Акты об использовании результатов диссертационной работы

Приложение Б - Охранные документы на объекты интеллектуальной собственности

Приложение В - Принципиальные схемы узлов ядра микроконтроллера

157

165

з

СПИСОК СОКРАЩЕНИЙ

АЛУ - Арифметико-логическое устройство.

БИС - Большая интегральная схема.

БП - Блок памяти.

ГА - Генетический алгоритм.

КА - Конечный автомат.

ЛЭ - Логический элемент.

МК - Микроконтроллер.

МП - Микропроцессор.

ОЗУ - Оперативное запоминающее устройство. ПК - Персональный компьютер.

ПЛИС - Программируемые логические интегральные схемы.

ПЛМ - Программируемые логические матрицы.

РЛБ - Реконфигурируемый логический блок.

САПР - Системы автоматизированного проектирования.

УУ - Устройство управления.

ЭА - Эволюционные алгоритмы.

ЭАС - Эволюционные аппаратные средства.

ВВЕДЕНИЕ

В настоящее время в связи с ускорением темпов технического прогресса в условиях жесткой конкуренции необходимо обеспечить высокое качество проектируемых устройств при минимальных временных затратах. При решении сложных задач проектирования на сегодняшний день невозможно обойтись без использования систем автоматизированного проектирования (САПР). Современные САПР это многоаспектные и многоуровневые системы, которые включают в себя комплекс программных и аппаратных средств. Усложнение проектируемых устройств обуславливает потребность в развитии САПР путем внедрения новых программно-аппаратных систем и подсистем на различных уровнях проектирования, которые способны повысить качество выпускаемых изделий [1,2].

В САПР для проектирования цифровых и аналоговых устройств в настоящее время применяются эволюционные алгоритмы (ЭА) [10,11]. Это направление получило название «эволюционная электроника» (Evolutionary Electronics) [25]. Применение ЭА на аппаратных платформах, имеющих реконфигурируемые элементы, позволяющие перестраивать систему во время функционирования, получило название эволюционные аппаратные средства [5-9, 20-24]. Научные исследования в этом направлении ведутся как в России, так и за рубежом [5-15].

Эволюционные аппаратные средства (ЭАС) - это новый тип аппаратных средств, который основывается на реконфигурируемых аппаратных системах, эволюционных алгоритмах, отказоустойчивых и автономных системах. В последние годы этой теме уделяется большое внимание [5-25]. В ЭАС применяются биологические методы эволюции для синтеза новых архитектур аппаратных средств. В основе ЭАС лежат различные вероятностные алгоритмы поиска решений, такие как генетические алгоритмы и эволюционное программирование.

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

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

При создании цифровых ЭАС в качестве реконфигурируемой части выступают динамически перестраиваемые комбинационные или последовательностные логические схемы [5-7]. Для динамической перестройки цифровых логических схем необходимо, чтобы ГА мог синтезировать схему на вентильном уровне. Таким образом, для создания ЭАС возникает задача разработки эволюционных алгоритмов синтеза цифровых логических схем.

В работах [16-19] представлены эволюционные алгоритмы синтеза

комбинационных логических схем для ЭАС. Применяемые в настоящее

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

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

6

неприменимой к остальным задачам [51]. Возникает вопрос создания универсальных методов синтеза конечных автоматов, применимых к широкому кругу задач. В работах [52-60] показано применение эволюционных алгоритмов для синтеза конечных автоматов. Однако, представленные алгоритмы применяются для автоматного программирования, в рамках которого программа описывается с помощью конечных детерминированных автоматов, что не позволяет их использовать в автономных аппаратных системах на реконфигурируемых платформах.

Поиск приемлемого по выбранным критериям конечного автомата прямым перебором практически невозможен из-за огромного размера пространства, в котором осуществляется поиск. Например, в такой простой задаче, как задача об «Умном муравье» [54], число возможных автоматов с

1Я

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

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ состоит в разработке и исследовании генетических алгоритмов синтеза конечных автоматов для проектирования эволюционных аппаратных средств.

Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

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

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

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, теории алгоритмов, методов статистических вычислений и методов проектирования цифровых устройств.

НАУЧНАЯ НОВИЗНА РАБОТЫ заключается в решении задачи автоматизированного синтеза конечных автоматов для автономных эволюционных аппаратных средств. В работе:

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

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

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

4. Разработан программный комплекс автоматизированного

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

исследования поведения алгоритмов в зависимости от изменений

параметров синтеза.

НА ЗАЩИТУ ВЫНОСЯТСЯ СЛЕДУЮЩИЕ ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ПОЛОЖЕНИЯ:

1. Генетический алгоритм кодирования состояний конечного автомата (по специальности 05.13.12).

2. Аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов (по специальности 05.13.12).

3. Устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС (по специальности 05.13.05).

4. Программный комплекс автоматизированного эволюционного синтеза конечных автоматов (по специальности 05.13.12).

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1. Устройство аппаратной реализации генетического алгоритма для решения задачи автоматизированного синтеза конечных автоматов на ПЛИС, позволяющее использовать разработанные генетические алгоритмы в автономных эволюционных аппаратных системах. На устройство получено положительное решение о выдаче патента на изобретение [129].

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в

госбюджетных научно-исследовательских работах Южно-Российского государственного университета экономики и сервиса:

• «Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.). Автором в качестве исполнителя были разработаны модифицированные генетические операторы для задачи автоматизации проектирования устройств вычислительной техники на схемотехническом и логическом уровнях.

• Гранты аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» 2009-2011 г:

о «Разработка и исследование реконфигурируемых гибридных

эволюционных аппаратных систем» № 2.1.2/6959 (ЮРГУЭС-

9.09.Ф). Автором в качестве исполнителя были разработаны:

аппаратно-ориентированный генетический алгоритм синтеза

конечных автоматов; генетический алгоритм кодирования

состояний конечного автомата; устройство автоматизированного

синтеза конечных автоматов, реализованное на ПЛИС;

о «Разработка и исследование бионических алгоритмов

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

моделирования» № 2.1.2/4595 (ЮРГУЭС-6.09.Ф). Автором в

качестве исполнителя были разработаны генетические

операторы для подсистем схемотехнического моделирования.

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

процессах в ФГБОУ ВПО ЮРГУЭС (г. Шахты) на кафедре

«Информационные системы и радиотехника» в дисциплинах

«Интеллектуальные информационные системы», «Архитектура ЭВМ и

систем», «Цифровые устройства и микропроцессоры», ВИС ФГБОУ ВПО

ЮРГУЭС (г. Волгодонск) на кафедре «Информационные технологии» в

дисциплинах «Архитектура ЭВМ и систем», «Схемотехника ЭВМ»,

ю

«Интеллектуальные информационные системы» и в ШИ(Ф) ФГБОУ ВПО ЮРГТУ(НПИ) (г. Шахты) на кафедре «Электрификация и автоматизация производства» в дисциплинах «Автоматизация установок и комплексов», «Основы микропроцессорной техники» и «Элементы систем автоматики». Используются следующие результаты кандидатской диссертации: алгоритмы эволюционного синтеза конечных автоматов; методы построения интеллектуальных систем управления на реконфигурируемых платформах; программный комплекс, выполняющий автоматизированный эволюционный синтез конечных автоматов для систем автоматизации производства. Акты об использовании результатов работы приведены в приложении к диссертации.

АПРОБАЦИЯ РАБОТЫ. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 2008-2011 гг.), международной научно-практической конференции «Научный потенциал молодёжи - будущее России», Всероссийской научной конференции молодых ученых и аспирантов (г. Волгодонск, 2009 г.), конгрессе по интеллектуальным системам и информационным технологиям «А18-1Т'09». По материалам диссертационной работы опубликовано 16 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК. СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 176 страниц, включающих 59 рисунков, 14 таблиц, список литературы из 139 наименований, 20 страниц приложений и актов об использовании.

1 ИССЛЕДОВАНИЕ СПОСОБОВ СОЗДАНИЯ АВТОНОМНЫХ СИСТЕМ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АППАРАТНЫХ СРЕДСТВ

1.1 Эволюционные аппаратные средства

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

автономно) [4].

Обобщенная блок-схема ЭАС приведена на рисунке 1.1.

Входы

J\ т/

Выходы

Реконфигурируемая часть

V

Рисунок 1.1- Обобщенная блок-схема ЭАС

Впервые понятие ЭАС было введено независимо друг от друга в

работах Mange и Higuchi в 1992 году [5-7]. Работа Mange описывает био-

инспирированные устройства, котор�