Введение к работе
Актуальность темы. Актуальность работы связана с возрастающим интересом применения генетических алгоритмов (ГА) в автономных системах, вопросами повышения быстродействия времеемких ГА и развитием нового направления эволюционного проектирования аппаратных средств Как следствие расширения области применения ГА, встает вопрос повышения их эффективности по множеству критериев и разработке аппаратно-ориентированных алгоритмов эволюционного проектирования для систем реального времени
Исследования в области проектирования эволюционных аппаратных средств получили набольшее развитие в связи с построением автономных интеллектуальных систем и выходом технологий проектирования микроэлектроники на качественно новый уровень В настоящий момент большинство работ и исследований в области эволюционного проектирования аппаратных средств проводятся в крупнейших исследовательских центрах, размещенных в Японии, Центральной Европе и России Основной вклад в развитие методов эволюционного проектирования внесли С Д Луис (S J Louis), Г Д Раулинс (G J Rawlins), Д С Галлахер (J С Gallagher), Д Р Коза (J R Koza), С А Коелло (С A Coello), К А ДеДжонг (К A DeJong), Д Е Голдберг (D Е Goldberd), С Д Скотт (S D Scott), Д X Холланд (J Н Holland), В М Курейчик (V М Kureichik), Д И Батищев (D I Batishev), Т К Васильев (V К Vassilev), Л А Зинченко (L A Zinchenko), А Томпсон (A Thompson), Т Хигучи (Т Higuchi), И Такаши (I Takashi), И Тажитани (I Kajitani), Т Хошино (Т Hoshino), X Саканаши (Н Sakanashi), С Прабхас (С Prabhas), Е Такахаши (Е Takahashi), Т Калганова (Т Kalganova), X Мюленбайн (Н Muhlenbem) и многие другие
Построение автономных систем, использующих в своей структуре эволюционные методы для решения различных задач, таких как распознавание образов, определение кратчайшего пути, обучения, анализа, поиска, оптимизации, проектирование динамически реконфигурируемых систем и др , требуют наличия аппаратно реализованных алгоритмов
С другой стороны, увеличение сложности проектируемых систем является причиной увеличения сложности и повышения функциональности средств разработки, т к существующие алгоритмы и методы проектирования используют повторяющиеся шаблонные решения и не позволяют находить принципиально новые схемы, что негативно сказывается на дальнейшем развитии средств проектирования Решением является разработка новых методов и алгоритмов, способных находить новые топологии и схемотехнические решения для заданных параметров при различных конфигурациях целевых устройств (ЦУ)
Таким образом, диссертационная работа посвящена решению актуальной и важной научно-технической проблемы разработке и исследованию новых алгоритмов эволюционного синтеза комбинационных схем, адаптированных для аппаратной реализации, способных выполнять поиск решения в режиме реального времени
Цель диссертационной работы состоит в разработке и исследовании аппаратно-ориентированных алгоритмов эволюционного синтеза комбинационных схем для систем реального времени Достижение указанной цели предполагает решение следующих основных задач
Разработка бинарного и десятичного алгоритмов эволюционного синтеза комбинационных схем для программируемых логических матриц (ПЛМ)
Разработка десятичного алгоритма эволюционного синтеза комбинационных схем для заданного базиса логических элементов (ЛЭ)
Разработка структуры параллельного взаимодействия генетического материала в (ГО)
Разработка структуры конвейерного взаимодействия генетических операторов ГО
Разработка устройства эволюционного синтеза комбинационных схем для ПЛМ
Методы исследований в диссертационной работе основаны на использовании элементов теории множеств, теории алгоритмов, элементов теории статистических вычислений, теории проектирования микроэлектронных средств, теории синтеза, теории разработки систем автоматизированного проектирования, параллельного и объектно-ориентированного программирования
Научная новизна работы заключается в решении задачи автоматизированного синтеза комбинационных схем для аппаратно-ориентированных систем реального времени В работе
Разработаны бинарный и десятичный генетический алгоритм автоматизированного синтеза комбинационных схем для ПЛМ, десятичный генетический алгоритм автоматизированного синтеза комбинационных схем для заданного базиса ЛЭ, позволяющие получать множество комбинационных схем для заданного функционального описания
Разработаны методы бинарного и десятичного кодирования и декодирования схем в ПЛМ и на основе заданного базиса ЛЭ, позволяющие выполнять переход между схемотехническим и закодированным представлением синтезируемых схем, что позволяет существенно повысить скорость синтеза схемных решений
Выполнена аппаратная реализация генетического алгоритма автоматизированного синтеза комбинационных схем для ПЛМ,
разработаны методы организации многопоточных параллельных вычислений с поддержкой динамических изменений параметров алгоритма синтеза в процессе функционирования, что позволило выполнять параллельную обработку и синтез комбинационных схем в режиме реального времени
4 Разработан инструментальный комплекс для автоматизированного синтеза комбинационных схем на основе базиса ЛЭ, позволяющий выполнять синтез заданного множества комбинационных схем в различных базисах, а также исследовать поведение алгоритма в зависимости от изменений параметров функционирования
Решение поставленных задач позволяет автору защищать следующие новые научные результаты:
Многоуровневую параллельную архитектуру взаимодействия генетического материала в генетических операторах, позволяющую перевести реализуемые алгоритмы в область реального времени
Новые генетические алгоритмы автоматизированного синтеза комбинационных схем, основанные на методах эволюционного синтеза, позволяющие находить множество нешаблонных комбинационных схем
Устройство эволюционного синтеза комбинационных схем для ПЛМ, позволяющее выполнять синтез в автономной среде с возможностью динамически изменять параметры функционирования Практическая ценность работы заключается в аппаратной реализации
устройства эволюционного синтеза комбинационных схем для ПЛМ, использование которого позволило повысить скорость синтеза при решении тестовых задач, что позволяет использовать разработанный алгоритм в системах реального времени Разработан программный комплекс синтеза комбинационных схем, позволяющий автоматизировать процесс синтеза комбинационных схем по заданному функциональному описанию и производить отбор лучших решений из множества найденных, при различных критериях отбора
Устройство эволюционного синтеза комбинационных схем для ПЛМ используется в качестве однокристального микропроцессора, способного по заданной таблице истинности или функциональному описанию синтезировать комбинационную схему для реализации в целевом устройстве, где целевое устройство представлено реконфигурируемой платформой, способной перестраивать собственную архитектуру Алгоритм синтеза комбинационных схем для заданного базиса ЛЭ может быть использован в качестве инструментального средства проектирования программируемых логических интегральных схем (ПЛИС), где внутренняя конфигурация макроячейки ПЛИС формируется на основе фиксированного базиса функциональных элементов Рассматриваемые устройства автоматизированного синтеза
комбинационных схем наиболее востребованы при решении задач коммутации, навигации, управления и в других областях, где необходимо решать какую-либо задачу с помощью метода комбинационных схем в режиме реального времени Внесение изменений в оператор анализа синтезируемых схем (построения математической модели), а также модификация метода кодирования схем, позволяет расширить используемый базис ЛЭ и выполнить переход от синтеза комбинационных схем к использованию синхронных элементов с памятью, а также других функциональных элементов, что позволяет использовать предложенные в работе математические модели, стратегии, концепции, принципы, методы и структуры для синтеза различных цифровых схем
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета (ТТИ ЮФУ) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании»
Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования»
Получен патент на изобретение Российской Федерации №2294561 «Устройство аппаратной реализации вероятностных генетических алгоритмов», заявка № 2005108760 от 28 03 2005 г
Апробация основных теоретических и практических результатов работы Результаты работы докладывались и обсуждались на VI и VII Всероссийской научной конференции с международным участием "Новые информационные технологии Разработка и аспекты применения" (г Таганрог, 2003 и 2004 гг), VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г Таганрог, 2004 г), II Всероссийской научной конференции "Методы и средства обработки информации" (г Москва, МГУ им М В Ломоносова, 2005 г), Международная конференция «Интеллектуальные системы (ШЕЕ AIS'06)», (с Дивноморское, 2006 г), X Национальной конференции по искусственному интеллекту с международным участием "КИИ - 2006" (г Обнинск 2006 г)
Публикации По теме диссертационной работы опубликовано 9 печатных работ, сделано 5 докладов на Всероссийских и Международных научно-технических конференциях
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложения Работа содержит 187 стр, а также 50 рисунков, 1 таблицу, список литературы из 120 наименований, 60 стр приложений и актов об использовании
