Введение к работе
Актуальность темы. В настоящее время в связи с ускорением темпов технического прогресса в условиях жесткой конкуренции необходимо обеспечить высокое качество проектируемых устройств при минимальных временных затратах. При решении сложных задач проектирования на сегодняшний день невозможно обойтись без использования систем автоматизированного проектирования (САПР). Современные САПР – это многоаспектные и многоуровневые системы, которые включают в себя комплекс программных и аппаратных средств. Усложнение проектируемых устройств обуславливает потребность в развитии САПР путем внедрения новых программно-аппаратных систем и подсистем на различных уровнях проектирования, которые способны повысить качество выпускаемых изделий.
В САПР для проектирования цифровых и аналоговых устройств в настоящее время применяются эволюционные алгоритмы (ЭА). Это направление получило название «эволюционная электроника» (Evolutionary Electronics). Применение ЭА на аппаратных платформах, имеющих реконфигурируемые элементы, позволяющие перестраивать систему во время функционирования, получило название эволюционные аппаратные средства. Научные исследования в этом направлении ведутся как в России, так и за рубежом. Результаты этих исследований приведены в работах В.М. Курейчика, В.В. Гудилова, С.В. Черуна, Д.Р. Коза, Г. Гариссона, Т. Хигучи, Д.Е. Голдберга, Е. Такахаши и др.
Эволюционные аппаратные средства (ЭАС) – это новый тип устройств, который основывается на эволюционных алгоритмах и автономных реконфигурируемых системах. В последние годы этой теме уделяется большое внимание. В ЭАС применяются биологические методы эволюции для синтеза новых архитектур аппаратных средств. В основе ЭАС лежат различные вероятностные алгоритмы поиска решений, такие как генетические алгоритмы и эволюционное программирование.
Основная цель применения ЭАС может быть сформулирована так: вместо использования аппаратных средств общего назначения, выполняющих различные программные приложения, можно применить аппаратную систему, которая будет самостоятельно адаптироваться под специфику решаемых задач. Для этого реконфигурируемое цифровое устройство должно обладать возможностью синтеза схемы на вентильном уровне, чтобы можно было его сконфигурировать на реализацию определенного алгоритма. При этом цифровые логические схемы, которые реализуются методами эволюционного синтеза на ЭАС, будут эффективнее по аппаратным затратам и быстродействию в сравнении со схемами, синтезируемыми другими методами. Это объясняется тем, что на ЭАС схемы синтезируются, учитывая специфику функционирования целевого устройства.
В качестве реконфигурируемой элементной базы для построения ЭАС применяются программируемые логические интегральные схемы (ПЛИС), универсальные и цифровые сигнальные процессоры. Основное преимущество ПЛИС по сравнению с универсальными и цифровыми сигнальными процессорами при построении ЭАС – это возможность реконфигурирования в системе, что позволяет создавать автономные реконфигурируемые эволюционные аппаратные средства.
При создании цифровых ЭАС в качестве реконфигурируемой части выступают динамически перестраиваемые комбинационные или последовательностные логические схемы. Для динамической перестройки цифровых логических схем необходимо, чтобы генетический алгоритм мог синтезировать схему на вентильном уровне. Таким образом, для создания ЭАС возникает задача разработки эволюционных алгоритмов синтеза цифровых логических схем.
В работах В.М. Курейчика, С.В. Черуна, В.В. Гудилова, Т. Хигучи и других представлены эволюционные алгоритмы синтеза комбинационных логических схем для ЭАС. Применяемые в настоящее время методы синтеза конечных автоматов всегда используют специфику решаемой задачи, делая полученную технику генерации автоматов неприменимой к остальным задачам. Возникает вопрос создания универсальных методов синтеза конечных автоматов, применимых к широкому кругу задач. В работах А.А. Шалыто, П.Г. Лобанова, Г. Хорихана, К. Вольфа и др. показано применение эволюционных алгоритмов для синтеза конечных автоматов. Однако представленные алгоритмы применяются для автоматного программирования, в рамках которого программа описывается с помощью конечных детерминированных автоматов, что не позволяет использовать их в автономных аппаратных системах на реконфигурируемых платформах.
Учитывая вышеизложенное, можно утверждать, что тема диссертационного исследования, связанная с разработкой генетических алгоритмов синтеза конечных автоматов для автономных эволюционных аппаратных средств, является АКТУАЛЬНОЙ.
Цель диссертационной работы состоит в разработке и исследовании генетических алгоритмов синтеза конечных автоматов для автономных эволюционных аппаратных средств.
Достижение указанной цели предполагает решение следующих основных задач:
-
Провести исследование методов синтеза конечных автоматов и особенностей использования современных систем автоматизированного проектирования для создания эволюционных аппаратных средств.
-
Разработать генетический алгоритм кодирования состояний конечного автомата, который бы не уступал по эффективности существующим алгоритмам, используемым в современных САПР.
-
Разработать аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов для автономных эволюционных аппаратных средств.
-
Выполнить аппаратную реализацию генетического алгоритма для решения задачи автоматизированного синтеза конечных автоматов на ПЛИС, позволяющую использовать разработанные генетические алгоритмы в автономных системах.
-
Разработать инструментальный комплекс автоматизированного эволюционного синтеза конечных автоматов, позволяющий проводить исследования поведения алгоритмов в зависимости от изменений параметров синтеза.
Методы исследования в диссертационной работе основаны на использовании элементов теории множеств, теории алгоритмов, методов статистических вычислений и методов проектирования цифровых устройств.
Научная новизна работы заключается в решении задачи автоматизированного синтеза конечных автоматов для автономных эволюционных аппаратных средств. В работе получены следующие результаты:
-
Разработан алгоритм кодирования состояний конечного автомата, отличающийся от известных алгоритмов модифицированными генетическими операторами, которые в своей работе учитывают значение целевой функции.
-
Разработан аппаратно-ориентированный алгоритм синтеза конечных автоматов, отличающийся от существующих алгоритмов возможностью использования в автономных системах на реконфигурируемых платформах.
-
Разработано устройство аппаратной реализации генетического алгоритма для решения задачи автоматизированного синтеза конечных автоматов на ПЛИС, позволяющее использовать разработанные генетические алгоритмы в автономных системах.
-
Разработан программный комплекс автоматизированного эволюционного синтеза конечных автоматов, позволяющий проводить исследования поведения алгоритмов в зависимости от изменений параметров синтеза.
На защиту выносятся следующие основные результаты и положения:
-
Генетический алгоритм кодирования состояний конечного автомата (по специальности 05.13.12).
-
Аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов (по специальности 05.13.12).
-
Устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС (по специальности 05.13.05).
-
Программный комплекс автоматизированного эволюционного синтеза конечных автоматов (по специальности 05.13.12).
Практическая ценность работы заключается в разработке программного комплекса автоматизированного эволюционного синтеза конечных автоматов и аппаратной реализации устройства эволюционного синтеза конечных автоматов на ПЛИС, использование которого позволило повысить скорость синтеза по сравнению с программной реализацией. Что, в свою очередь, позволяет использовать разработанные алгоритмы в автономных эволюционных аппаратных средствах.
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Южно-Российского государственного университета экономики и сервиса:
«Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.). Автором в качестве исполнителя были разработаны модифицированные генетические операторы для задачи автоматизации проектирования устройств вычислительной техники на схемотехническом и логическом уровнях.
«Разработка и исследование реконфигурируемых гибридных эволюционных аппаратных систем» № 2.1.2/6959 (ЮРГУЭС-9.09.Ф). Автором в качестве исполнителя были разработаны: аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов; генетический алгоритм кодирования состояний конечного автомата; устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС.
«Разработка и исследование бионических алгоритмов вычислительной математики для подсистемы схемотехнического моделирования» № 2.1.2/4595 (ЮРГУЭС-6.09.Ф). Автором в качестве исполнителя были разработаны генетические операторы для подсистем схемотехнического моделирования.
Кроме того, материалы диссертационной работы использованы в учебных процессах в ФГБОУ ВПО ЮРГУЭС (г. Шахты) на кафедре «Информационные системы и радиотехника» в дисциплинах «Интеллектуальные информационные системы», «Архитектура ЭВМ и систем», «Цифровые устройства и микропроцессоры», ВИС ФГБОУ ВПО ЮРГУЭС (г. Волгодонск) на кафедре «Информационные технологии» в дисциплинах «Архитектура ЭВМ и систем», «Интеллектуальные информационные системы» и в ШИ(Ф) ФГБОУ ВПО ЮРГТУ(НПИ) (г.Шахты) на кафедре «Электрификация и автоматизация производства» в дисциплинах «Автоматизация установок и комплексов», «Основы микропроцессорной техники» и «Элементы систем автоматики».
Апробация Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 2008-2011 гг.); Конгрессе по интеллектуальным системам и информационным технологиям «AIS-IT’09»; Международной научно-практической конференции «Научный потенциал молодёжи – будущее России» (г. Волгодонск, 2010 г.), Всероссийской научной конференции молодых ученых и аспирантов (г. Волгодонск, 2009 г.) .
Публикации. По материалам диссертационной работы опубликовано 16 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК, получено 6 свидетельств об официальной регистрации программы для ЭВМ, сделано 9 докладов на Всероссийских и Международных научно-технических конференциях.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 176 страниц, включающих 59 рисунков, 14 таблиц, список литературы из 139 наименований, 20 страниц приложений и актов об использовании.
