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

□ОЗОВ4515

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

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

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

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

1 6 АВГ 2007

Таганрог 2007

003064515

Работа выполнена в Южном федеральном университете

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

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

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

заслуженный деятель науки РФ, доктор технических наук, профессор Курейчик Виктор Михайлович

доктор технических наук, профессор Витиска Николай Иванович (первый проректор Таганрогского Государственного Педагогического Института, г Таганрог),

доктор технических наук, профессор Ковалев Сергей Михайлович (Ростовский государственный университет путей и сообщений, г Ростов-на-Дону),

Федеральное государственное унитарное предприятие «Таганрогский научно-исследовательский институт связи», г Таганрог

Защита диссертации состоится 28 августа 2007 г в 14 20 на заседании диссертационного совета Д 212 208 22 при Южном федеральном университете по адресу 347928, Таганрог, пер Некрасовский, 44, ауд Д-406

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

Автореферат разослан « 27 » июля 2007 г

Ученый секретарь диссертационного совета Д 212 208 22, доктор технических наук, профессор

Целых А Н

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

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

Исследования в области проектирования эволюционных аппаратных средств получили набольшее развитие в связи с построением автономных интеллектуальных систем и выходом технологий проектирования микроэлектроники на качественно новый уровень В настоящий момент большинство работ и исследований в области эволюционного проектирования аппаратных средств проводятся в крупнейших исследовательских центрах, размещенных в Японии, Центральной Европе и России Основной вклад в развитие методов эволюционного проектирования внесли С Д Луис (S J Louis), Г Д Раулинс (G J Rawlins), Д С Галлахер (J С Gallagher), Д Р Коза (J R Koza), С А Коелло (С A Coello), К А ДеДжонг (К A DeJong), Д Е Голдберг (D Е Goldberd), С Д Скотт (S D Scott), Д X Холланд (J H Holland), В M Курейчик (V M Kureichik), Д И Батищев (D I Batishev), Т К Васильев (V К Vassilev), JI А Зинченко (L A Zinchenko), А Томпсон (А Thompson), Т Хигучи (Т Higuchi), И Такаши (I Takashi), И Тажитани (I Kajitani), Т Хошино (Т Hoshino), X Саканаши (H Sakanashi), С Прабхас (С Prabhas), Е Такахаши (Е Takahashi), Т Калганова (Т Kalganova), X Мюленбайн (H Muhlenbem) и многие другие

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

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

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

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

1 Разработка бинарного и десятичного алгоритмов эволюционного синтеза комбинационных схем для программируемых логических матриц (ПЛМ)

2 Разработка десятичного алгоритма эволюционного синтеза комбинационных схем для заданного базиса логических элементов (ЛЭ)

3 Разработка структуры параллельного взаимодействия генетического материала в (ГО)

4 Разработка структуры конвейерного взаимодействия генетических операторов ГО

5 Разработка устройства эволюционного синтеза комбинационных схем для ПЛМ

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

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

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

2 Разработаны методы бинарного и десятичного кодирования и декодирования схем в ПЛМ и на основе заданного базиса ЛЭ, позволяющие выполнять переход между схемотехническим и закодированным представлением синтезируемых схем, что позволяет существенно повысить скорость синтеза схемных решений

3 Выполнена аппаратная реализация генетического алгоритма автоматизированного синтеза комбинационных схем для ПЛМ,

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

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

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

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

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

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

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

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

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета (ТТИ ЮФУ) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании»

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования»

Получен патент на изобретение Российской Федерации №2294561 «Устройство аппаратной реализации вероятностных генетических алгоритмов», заявка № 2005108760 от 28 03 2005 г

Апробация основных теоретических и практических результатов работы Результаты работы докладывались и обсуждались на VI и VII Всероссийской научной конференции с международным участием "Новые информационные технологии Разработка и аспекты применения" (г Таганрог, 2003 и 2004 гг), VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г Таганрог, 2004 г), II Всероссийской научной конференции "Методы и средства обработки информации" (г Москва, МГУ им М В Ломоносова, 2005 г), Международная конференция «Интеллектуальные системы (IEEE AIS'06)», (с Дивноморское, 2006 г), X Национальной конференции по искусственному интеллекту с международным участием "КИИ - 2006" (г Обнинск 2006 г)

Публикации По теме диссертационной работы опубликовано 9 печатных работ, сделано 5 докладов на Всероссийских и Международных научно-технических конференциях

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложения Работа содержит 187 стр, а также 50 рисунков, 1 таблицу, список литературы из 120 наименований, 60 стр приложений и актов об использовании

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

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

В первой главе рассмотрено состояние проблемы, проведены анализ и классификация алгоритмов синтеза, показано, что перспективными исследованиями являются алгоритмы синтеза, использующие в своей основе эволюционные методы, что позволяет получать набор решений, оптимальных по заданным критериям Большое внимание уделено методам и специфике эволюционного проектирования аппаратных средств, показаны преимущества и недостатки применения методов эволюционного синтеза в сравнении с другими методами для решения задачи синтеза схем Отмечено, что основным средством повышения быстродействия времеемких алгоритмов эволюционного синтеза является применение методов аппаратной реализации с организацией многопоточных параллельных вычислений Выполнена постановка задачи синтеза комбинационных схем, представленных в виде множества Я = {Н, с!<] Р}, где элемент множества Н определяет генотип синтезируемого решения, элемент cF определяет оценку математической модели синтезируемой схемы как критерий отбора, элемент Р определяет вероятность передачи наследственной информации Решение задачи синтеза заключается в поиске схемы, для которой сР = 1

Вторая глава диссертационной работы посвящена разработке ГА бинарного и десятичного алгоритма эволюционного синтеза комбинационных схем для ПЛМ и десятичного алгоритма эволюционного синтеза комбинационных схем для заданного базиса ЛЭ Выполняется аппаратно-ориентированная разработка ГО и методов их взаимодействия Предложены методы бинарного кодирования схемы в виде хромосомы на основе структуры ПЛМ, где хромосома Я/т+? кодирует двумерный массив М определяющий состояние перемычек ПЛМ Двумерный массив М;т+9 определен как матрица конъюнкторов С|>т размерности / на т и матрица дизъюнкторов размерности I на д, где т = 2с столбцов определяют конъюнктивные термы, количество строк / = 2е, с - количество входных

переменных аналитических функций, представленных в виде ДНФ и q — количество функций

Для десятичного кодирования структура хромосомы определена как массив, элементы которого представлены матрицей конъюнкторов С,„„ размерности / на с и матрицей дизъюнкторов Diq, размерности / на д, где с — количество входных переменных, количество строк 0 < I <2с определяет количество дизъюнкций и q — количество входных функций, описывающих искомую схему

Для алгоритма эволюционного синтеза комбинационных схем для базиса ЛЭ кодирование хромосомы определяется на основе матричного представления схемы Мт„ (рисунок 1 а)), содержащей абстрактные логические элементы (АЛЭ), посредством перехода от двумерной индексации ЛЭ (столбец т , строка п) в синтезируемой схеме к одномерной Число с входов хс, поступающих на схему, образуют нулевой столбец входов элементов L0„, где п = с задает количество строк матрицы Мтп Количество выходов схемы yq, определяется согласно количеству q аналитических выражений, описывающих закон функционирования искомой схемы Номера элементов Lrt в схеме имеют сквозную нумерацию, совпадающую с нумерацией логических элементов внутри матрицы Мтп и используемую при синтезе схемы для обозначения выхода элемента Индексы элементов Lr,rut задаются согласно порядковому расположению элемента в матрице Мтт по возрастанию слева направо и сверху вниз, где 0 <t < п и 0 <г <т (нулевой столбец т = 0 содержит сигналы входов схемы, т е количество столбцов т дополнено столбцом входов) Выходы схемы у подключаются только к выходам элементов Lr, столбца т (г = т), при этом элемент нулевой строки Lm о соответствует нулевому выходу у0 схемы и т д

В качестве минимального базиса ЛЭ определено множество L = {L,\ i = 1, 2, , nl}, элементами которого являются стандартные двухвходовые элементы "И", "ИЛИ", "XOR" и одновходовые элементы "НЕ" и "WIRE", имеющие один выход, где nl - количество элементов множества Функциональные составляющие элементов "И", "ИЛИ", "XOR" и "НЕ" аналогичны соответствующим им логическим элементам Функциональный элемент "WIRE" (перемычка) выполняет передачу сигнала, поступающего на единственный вход элемента к выходу, без каких-либо изменений функциональной составляющей входного сигнала Кодирование элементов функционального базиса выполняется посредством назначения кода в порядке возрастания их порядкового номера

а)

Вх„ Вх„ ВХ2, Вх„ Кой Вх1, Вх„ Вх2г Вхп Код • • • Вх,г Вхп Вх„ Код

8/0 #// &тп!

= {ЕД,\ , = 1,2,3, & =ёг„г = 1,2, ,т, 1 = 0,1, ,п-1} б)

Рисунок 1 - а) - представление схемы, содержащей матрицу иная ЛЭ Ьг1, имеющую с входов и д выходов, б) - представление структуры хромосомы,

кодирующей схему

Расположение АЛЭ в узлах решетки схемы остается неизменным в процессе синтеза схемы, а изменяется лишь их функциональная составляющая (код) и соединения между входами и выходами элементов Логический элемент ¿м, кодируемый геном gr,, заносится в хромосому Я последовательно, по столбцам, от младшего элемента I столбца г к старшему, где 0 < г <т, 0 <1 < п (рисунок 1 б)) Каждый ген хромосомы Н определяется вектором = {^п, (, = 1,2,3}, который кодирует отдельно взятый ЛЭ Ьг1, где элементы вектора и задают информацию о входах г и / ЛЭ Ьг,, и gn3 задает код кодируемого ЛЭ Ьг, Локус гена в хромосоме соответствует заданной позиции кодируемого им элемента в схеме, т о значение, получаемое на выходе ЛЭ, ассоциируется с отождествляемым ему геном Переход к многовходовым схемам возможен посредством дополнения функционального базиса новыми элементами и модификации структуры гена хромосомы Приведенные методы кодирования схем могут быть легко

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

Для анализа синтезируемой схемы разработан метод построения математической модели схемы с ее последующим анализом на б = 2е входных наборах ТИ, где с - количество входных переменных аналитических функций Построение ММ схемы для ПЛМ выполняется с учетом принципа функционирования конъюнктивных и дизъюнктивных термов Для схем на основе ЛЭ метод построения ММ определен как переход от одномерного массива ЛЭ, кодирующего фенотип в виде хромосомы, к некоторому множеству двумерных массивов Zm „ (матриц размерности т на и), элементы которых отражают функциональную составляющую синтезируемого объекта Элементы 7.тп представлены в виде матриц 2етп, '¿ш1т „, 7лп2т „ и 7о1Птт где 7*ет „ задает матрицу кодов ЛЭ, У,т1тп и 2т2т„ определяют адреса ЛЭ, подключаемых к входам текущего ЛЭ, 2оштп содержит значения выходов ЛЭ Построение ММ схемы выполняется посредством анализа ген хромосомы и построения на их основе матрицы кодов ЛЭ 2ет „ и матриц адресов входов 2т1т„ и У-1п2т „ Матрицы выходов ЛЭ 7ои1т„ формируются для каждого набора я входных сигналов схемы на основе набора состояний входных сигналов в ТИ

Степень соответствия эволюционирующей и искомой схемы определена как критерий с/71, значение которого изменяется в интервале от нуля до единицы, т е при полном соответствии эволюционирующей и искомой схемы с/7 принимает единичное значение Искомая ТИ определяется на основе входных аналитических функций, эволюционирующая ТИ вычисляется посредством установки 5 входных значений из искомой ТИ на входы ММ схемы Результатом построения ММ является построение эволюционирующей ТИ 77'-, элементы которой сравниваются с элементами искомой ТИ ТТ/, где ТИ представлены в виде матриц

TTz=

TTf-

f\ I /12 fi\ fll

/11 ft 2

f\ q fsq

О)

размерности s на q элементов Тогда значение соответствия hit, вычисляется как

ГО (2)

1 1, если г, v = / v

где 0 < i < U, 0 <j < s, 0 <v < q и hit, определяет результат выполнения операции сравнения ;-го элемента матриц TTz и TTf Таким образом, критерий оценки cF для хромосомы j вычисляется на основе соотношения

и

cF(j) = —--(3)

Данное значение критерия оценивает функциональную составляющую схемы и при значении cF(j)^\-, схема j, кодируемая хромосомой H(j), стремится к

искомому решению Таким образом, параметром эволюции выступает степень соответствия схемы искомому решению

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

Передача генетического материала выполняется на основе лучших решений, для выбора которых предназначен оператор отбора, выполняющий перемещение из популяции IJCS, размера Ps, заданного количества Es хромосом el(i) с максимальным значением критерия cF(j) в порядке убывания cF(j), где 0 < i < Es, 0 < j < Ps и г < j Р азработанный метод передачи наследственной информации определен вектором вероятности Р = {р,\ t = 1, 2, , hL} наследования генетического материала из множества элитных хромосом Hei текущей популяции ПСЕ в последующую популяцию //„-/, где hL — длина хромосомы Величина р, определяет степень отношения многообразия генетического материала для гена g„ представленного в локусе i хромосом элитной области, к величине Es элитной области В случае бинарного кодирования хромосомы, величина р, определяет вероятность наследования единичных ген

eS

р =äf: (4)

" Es

При десятичном кодировании схемы, когда ген хромосомы задает ЛЭ, элементы р, вектора Р определяют вероятность наследования всех возможных состояний гена g, и имеют длину, определяемую количеством состояний, которое может принимать ген g, Значение векторов вероятности р, может изменяться в интервале от нуля до единицы и при единичном значении

означает, что гены в локусе / хромосом //последующей популяции //„+; унаследуют доминирующее значение генетического материала данного гена

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

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

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

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

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

Рисунок 2 - Алгоритм эволюционного синтеза комбинационных схем

Во втором разделе третьей главы приведен подробный анализ разработанного алгоритма синтеза комбинационных схем для ЛЭ, выполнен анализ разработанных ГО и алгоритмов их функционирования, определена структура взаимодействия генетического материала, приведена теоретическая оценка временной сложности алгоритма, соответствующая О = п3, где п —

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

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

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

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

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

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

2 Разработаны методы бинарного и десятичного кодирования и декодирования схем в ПЛМ и на основе заданного базиса ЛЭ, позволяющие выполнять переход между схемотехническим и закодированным представлением синтезируемых схем, что позволяет существенно повысить скорость синтеза схемных решений

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

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

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

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

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

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

1 В В Гудилов, В М Курейчик Устройство аппаратной реализации вероятностных генетических алгоритмов// Методы и средства обработки информации Труды Второй Всероссийской научной конференции МГУ им М В Ломоносова Москва 2005 стр 596-601

2 В В Гудилов, Л А Зинченко Аппаратная реализация вероятностных алгоритмов эволюционного поиска//Известия ТРТУ, №2, Таганрог 2003, стр 209-215

3 В В Гудилов, Л А Зинченко Аппаратная реализация вероятностных генетических алгоритмов с параллельным формированием хромосомы//Перспективные информационные технологии и интеллектуальные системы, №4, 2003, стр 34-38

4 В В Гудилов, В М Курейчик Методы повышения эффективности вероятностных алгоритмов, адаптированные к возможности динамических изменений параметров функционирования на примере аппаратной реализации генетического алгоритма UMDA// Перспективные информационные технологии и интеллектуальные системы, №1, стр 43-55 Таганрог 2005

5 В В Гудилов Аппаратная реализация генетических алгоритмов// КИИ -2006 Десятая национальная конференция по искусственному интеллекту с международным участием Москва Физматлит 2006 Том 3 стр 10131021

6 В В Гудилов, В М Курейчик Об аппаратной реализации генетического алгоритма// AIS'05 CAD-2005 Интеллектуальные системы, Интеллектуальные САПР Труды конференций Том 1 Москва Физматлит 2005 стр 413-419

i 7 В В Гудилов О построении эволюционных аппаратных средств// AIS'06 i CAD-2006 Интеллектуальные системы, Интеллектуальные САПР Труды

¡ конференций Том 1 Москва Физматлит 2005 стр 7-15

8 В В Гудилов Применение вероятностных алгоритмов генетического поиска для задач логической оптимизации// VII Всероссийская научная конференция с международным участием Новые информационные

I

I

технологии Разработка и аспекты применения, "ПБОЮЛ В А Кравцов" Таганрог 2004, стр 283-285 9 В В Гудилов, Л А Зинченко, В М Курейчик, В В Курейчик Устройство аппаратной реализации вероятностных генетических алгоритмов// Патент Российской Федерации на изобретение №2294561, заявка № 2005108760 от 28 03 2005 Федеральный институт промышленной собственности Москва 51 стр

В работах [1, 4, 6], опубликованных в соавторстве, лично автору принадлежат следующие результаты - разработка параллельных методов аппаратной реализации ГА, применение динамической модификации для изменения параметров вероятностного генетического алгоритма в процессе функционирования, в работе [3] автором предложены методы параллельной обработки генетического материала в генетических операторах, в работе [9] автором выполнена разработка устройства аппаратной реализации вероятностных генетических алгоритмов, а также ряд методов и структур, для организации многопоточных параллельных аппаратных систем

Соискатель

В В Гудилов

Отпечатано на лазерном принтере Тираж 100 экз

Введение.

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

2.1 Классификация алгоритмов синтеза.

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

2.3 Специфика проектирования эволюционных аппаратных средств.

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

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

2.1 Разработка бинарного генетического алгоритма для ПЛМ.

2.1.1 Разработка бинарных генетических операторов.

2.1.2 Разработка структуры генетического алгоритма для ПЛМ.

2.2 Разработка десятичного генетического алгоритма для ПЛМ.

2.3 Разработка десятичного генетического алгоритма синтеза комбинационных схем для логических элементов.

2.3.1 Разработка методов передачи наследственной информации.

2.3.2 Разработка алгоритма генерации популяции.

2.3.3 Разработка структуры генетического алгоритма для логических элементов.

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

3.1 Разработка устройства автоматизированного синтеза комбинационных схем для ПЛМ.

3.1.1 Разработка параллельных генетических операторов.

3.1.2 Разработка структурной схемы алгоритма автоматизированного синтеза комбинационных схем для ПЛМ.

3.1.3 Анализ разработанного устройства автоматизированного синтеза комбинационных схем для ПЛМ.

3.2 Особенности разработанного генетического алгоритма автоматизированного синтеза комбинационных схем.

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

3.2.2 Анализ генетических операторов.

3.2.3 Временная сложность функционирования алгоритма синтеза.

3.2.4 Схемотехническое представление синтезированных комбинационных схем.

На основании возрастающего количества исследований, результаты которых получают свое освещение на научных международных конференциях и становятся доступны в печати [1-9], а также изучив материалы выданных патентов Европейской Патентной Организацией [10] за последние 10 лет, можно сделать вывод, что наряду с другими направлениями [11-17] в данный момент активно развивается идея применения генетических алгоритмов (ГА) [18] в системах автоматизированного проектирования цифровых и аналоговых аппаратных средств [19-27]. Первые работы по применению генетических алгоритмов для проектирования микроэлектронных средств относятся к 80-м годам, когда эволюционные алгоритмы были применены в задачах оптимизации размещения элементов и трассировки [28-30]. В начале 90-х годов было анонсировано появление нового класса интегральных схем, получивших название ПЛИС [31-33] (программируемые логические интегральные схемы FPGA), что стало определенным толчком для нового витка исследований в области автоматизированного проектирования микроэлектронных средств. В этот же период выходят работы С. Луиса и Д. Раулинса [21, 34], ставшие по сути революционными. Смысл работ состоял в том, что авторы пересмотрели само понятие структурной разработки для цифровых схем. Эволюционный алгоритм использовался для размещения цифровых логических элементов, при этом задача размещения сводилась к реализации какой либо функции, например, функции четности. Оригинальность идей заключалась в полном автоматическом проектировании с помощью эволюционного алгоритма, при котором необходимость присутствия человека при проектировании полностью исключалось. Данная идея радикально отличалась от технологий, применяемых в то время, т.к. эти технологии использовали эволюционные алгоритмы только для оптимизации VLSI-топологии [35, 36] и были спроектированы человеком, основываясь на эвристике и наборе ограничений.

Использование эволюционных алгоритмов как механизма для автоматического проектирования схем на реконфигурируемых платформах [4, 38] получило название эволюционные аппаратные средства (Evolvable Hardware) [7, 15-17, 22-27], которое также используется синонимом для несколько общего направления, известного как эволюционная электроника (Evolutionary Electronics) [38]. Одной из задач, которые ставятся в данный момент перед реконфигурируемыми вычислительными системами, выступает задача построения на их основе самореконфигурируемых [39-41] (самоадаптирующихся) систем, работающих в режиме реального времени, способных модифицировать внутреннюю архитектуру (собственную или подчиненной системы) в соответствии с изменением внешних факторов.

Основная идея самореконфигурируемых аппаратных систем может быть представлена так: вместо использования аппаратных систем общего назначения, выполняющих различные программные приложения, позволить аппаратной схеме самостоятельно адаптироваться под специфику выполняемого программного обеспечения. В действительности, для реализации подобной гибкости программируемая цифровая схема должна обеспечивать возможность синтеза схемы на низком уровне, при котором решаемая задача будет собираться из мельчайших деталей. Таким образом, будет иметься возможность сконфигурировать аппаратную часть, настроенную на реализацию индивидуального алгоритма так, как если бы она была специально реализована для выполнения этого алгоритма. Подобная настройка выполняется посредством программирования реконфигурируемой логики (логических элементов) в индивидуальном порядке для каждой функции в отдельности. Для реализации рассмотренных функций применяются различные эволюционные алгоритмы, в которых средствами искусственной эволюции выполняется поиск и построение схемы в точности соответствующей рассматриваемой инструкции. Другим свойством проектируемых систем на базе реконфигурируемых кристаллов является возможность построения динамически реконфигурируемых аппаратных средств [42, 43], в которых производится эволюционное изменение архитектуры системы в режиме реального времени в соответствии с изменением внешних факторов. Данное свойство предоставляет возможность исправления допущенных при проектировании ошибок и неточностей даже после выпуска реализованного процессора в серийное производство. Как показано в [42], реконфигурируемые вычислительные системы - это платформы, архитектура которых может изменяться программно, посредством программной реконфигурации внутренней архитектуры системы. Следствием изменения архитектуры является возможность достижения соответствия выполняемого приложения аппаратно реализуемому алгоритму в рамках ограничения ресурсов при проектировании. При этом вопрос перевода алгоритма в аппаратную область не ограничивается одним из методов получения максимальной производительности реализуемых алгоритмов [44-47] или достижением возможности автономной работы, а преследует своей целью построение самореконфигурируемых вычислительных систем [48], что относится к разработке принципиально новых методов и средств взаимодействия проектировщик-система, в которых роль проектировщика исключается из процесса разработки.

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

Этим можно объяснить возрастающий интерес к моделям генетических алгоритмов, адаптированных для аппаратной реализации [49] и к самой аппаратной реализации ГА. Как пример можно рассмотреть работы по аппаратной реализации компактного генетического алгоритма [50] и семейства компактных генетических алгоритмов для встраиваемых эволюционных аппаратных средств [51].

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

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

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

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

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

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

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

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

ЦЕЛЬ диссертационной работы заключается в разработке и исследовании новых аппаратно-ориентированных алгоритмов автоматизированного синтеза комбинационных схем, способных синтезировать комбинационные схемы для различных представлений целевого объекта: в виде программируемой логической матрицы (ПЛМ) и заданного базиса логических элементов. Для достижения поставленной цели были решены следующие задачи:

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

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

- Разработаны методы бинарного и десятичного представления, кодирования и декодирования схем в ПЛМ.

- Разработаны методы оценки схем для ПЛМ, позволяющие оценить степень соответствия синтезируемой и искомой схемы, представленной в виде таблицы истинности или булевой функции.

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

- Разработаны методы генерации и оценки сложности решений для комбинационных схем, представленных в ПЛМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Разработаны методы бинарного и десятичного кодирования и декодирования схем в ПЛМ и на основе заданного базиса ЛЭ, позволяющие выполнять переход между схемотехническим и закодированным представлением синтезируемых схем.

Разработаны методы построения математической модели и оценки схем для ПЛМ и на основе заданного базиса ЛЭ, позволяющие оценить степень соответствия синтезируемой и искомой схемы, представленной в виде таблицы истинности (ТИ), или булевой функции.

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

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

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

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

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

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

5. Разработан инструментальный комплекс для автоматизированного синтеза комбинационных схем на основе базиса ЛЭ, позволяющий выполнять синтез заданного множества комбинационных схем в различных базисах, а также исследовать поведение алгоритма в зависимости от изменений параметров функционирования. ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

Разработанный комплекс программ для решения задачи автоматизированного синтеза комбинационных схем для ПЛМ и задачи автоматизированного синтеза комбинационных схем для базиса ЛЭ.

Разработанный комплекс алгоритмов, программ и аппаратных схем, который включает в себя:

- Алгоритм и программу автоматизированного синтеза комбинационных схем для ПЛМ.

- Алгоритм и программу автоматизированного синтеза комбинационных схем для заданного базиса ЛЭ. Устройство автоматизированного синтеза комбинационных схем для ПЛМ, защищенное патентом Российской Федерации [56]. Разработанный комплекс алгоритмов, программ и аппаратных схем выполняет синтез комбинационных схем по их функциональному описанию в рамках принятой архитектуры целевого устройства, а также исследует разработанные алгоритмы при различных параметрах функционирования.

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ

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

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на VI и VII Всероссийской научной конференции с международным участием "Новые информационные технологии. Разработка и аспекты применения" (г. Таганрог, 2003 и 2004 гг.), VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г. Таганрог, 2004 г.), II Всероссийской научной конференции "Методы и средства обработки информации" (г. Москва, МГУ им. М. В. Ломоносова, 2005 г.), Международная конференция «Интеллектуальные системы (IEEE AIS'06)», (с. Дивноморское, 2006 г.), X Национальной конференции по искусственному интеллекту с международным участием "КИИ-2006" (г. Обнинск 2006 г.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 9-ти печатных работах. Получен патент Российской Федерации на изобретение №2294561 «Устройство аппаратной реализации вероятностных генетических алгоритмов» [56], заявка № 2005108760 от 28.03.2005 г.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложения. Работа содержит 187 стр., а также 50 рисунков, одну таблицу, списка литературы из 120 наименований, 60 стр. приложений и актов об использовании.

Выводы

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

- принципиальной схемы блока оценки решений;

- принципиальной схемы алгоритма вычисления вероятности;

- принципиальной схемы алгоритма генерации хромосомы;

- принципиальной схемы алгоритма оператора отбора.

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

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

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

- инициализации алгоритма;

- инициализации вектора вероятности;

- генерации популяции;

- вычисления критерия;

- отбора элитных хромосом;

- вычисления вероятности.

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

Заключение

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

Разработаны бинарный и десятичный генетический алгоритм для решения задачи автоматизированного синтеза комбинационных схем на основе программируемых логических матриц (ПЛМ):

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

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

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

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

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

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

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

Выполнен анализ и исследование разработанного алгоритма автоматизированного синтеза комбинационных схем.

Выполнена аппаратная реализация генетического алгоритма для решения задачи автоматизированного синтеза комбинационных схем для ПЛМ и получен патент Российской Федерации на изобретение [56], выполнено исследование (на уровне генетических операторов и их взаимодействия) бинарного генетического алгоритма для решения задачи автоматизированного синтеза комбинационных схем для ПЛМ.

Разработан комплекс программ для решения задачи автоматизированного синтеза комбинационных схем для ПЛМ и задачи автоматизированного синтеза комбинационных схем.

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

1. Cohoon, J.P. and Paris. W.D., Genetic Algorithms in Engineering Systems, The Institute of Electrical Engineers, London, 1997.

2. Grimbleby, J. B, Automatic analog network synthesis using genetic algorithms, in Proc. of the First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (GALESIAS 95), England, 1995, 53.

3. Brandon Blondet, Philip James-Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform //Field-Programmable Logic and Applications. 13th International Conference, FPL 2003 Proceedings, pp. 565-574.

4. Grimbleby, J. В., Automatic analog network synthesis using genetic algorithms, in Proc. of the First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (GALESIAS 95), England, 1995, 53.

5. Thompson A., Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al., Eds., MIT Press, Cambridge, 1996,444.

6. Европейская патентная классификация: http://ep.espacenet.com/

7. Vassilev V.K., Fogarty T.C., and Miller J.F., Information characteristics and the structure of landscapes, in Evolutionary Computation, 8, 1, MIT Press, Cambridge, 2000,31.

8. Kirkpatrick S., Gelatt C.D., Jr. and Vecchi M.P., Optimization by simulated annealing, Science, 220, 1983, 671.

9. Winston P. H., Artificial Intelligence, 3rd ed., Addison-Wesley, Reading, MA, 1992.

10. Thompson A., Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al., Eds., MIT Press, Cambridge, 1996,444.

11. Курейчик B.M. Генетические алгоритмы и их применение. Монография. Таганрог: изд-во ТРТУ, 2002, 242 с.

12. T. Higuchi, M. Murakawa, M. Iwata, I. Kajitani, W. Liu, and M. Salami. Evolvable Hardware at Function Level// Proc. of 1997 IEEE Int. Conf. on Evolutionary Computation (ICEC97), pp. 187-192,1997.

13. T. Higuchi et al. Evolvable hardware: A first step towards building a Darwin machine. In Proc. of the 2nd Int. Conference on Simulated Behaviour, pages 417424. MIT Press, 1993.

14. H. Iba, M. Iwata, and T. Higuchi. Machine Learning Approach to Gate-Level Evolvable Hardware// Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1259 (Proc. of ICES 1996), pp.327-343, Springer-Verlag, 1997.

15. X. Yao and Т. Higuchi. Promises and Challenges of Evolvable Hardware// Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1259 (Proc. of ICES 1996), pp.55-78, Springer-Verlag, 1997.

16. H. Sakanashi, M. Tanaka, M. Iwata, D. Keymeulen, M. Murakawa, I. Kajitani and T. Higuchi. Evolvable Hardware Chips and their Applications// Proc. of the 1999 IEEE Systems, Man, and Cybernetics Conference (SMC'99), pp. V559-V564, 1999.

17. H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangular-packing-based module placement," in Proc. IEEE Inl. Conf. on Computer-Aided Design, 1995, pp. 472-479.

18. J. Xu, P. N. Guo, and С. K. Cheng, "Rectilinear block placement using sequence-pair," in Proc. 1998 ACM/IEEE Int. Symp. on Physical Design, Monterey, CA, Apr. 6-8, 1998, pp. 173-178.

19. H. Shin, A. L. Sangiovarmi-Vincentelli, and С. H. Sequin, '"Zone-refining' techniques for 1С layout compaction," IEEE Trans. Computer-Aided Design, vol. 9, Feb. 1990.

20. Stephen D. Brown, Robert J. Francis, Jonathat Rose, Zvonko G. Vranesic. Field-Programmable Gate Arrays// Kluwer Academic Publishers, USA 1992. 206 s.

21. П. Хоровиц, У. Хилл "Искусство схемотехники". Москва Мир 2001г.

22. В.Б. Стешенко "Плис фирмы ALTERA: проектирование устройств обработки сигналов". Москва Додека 2000г.

23. S.J. Louis and G.J.E. Rawlins, "Syntactic Analysis of Convergence in Genetic Algorithms," Foundations of Genetic Algorithms 2 ed. by L.D. Whitley, San Mateo, CA: Morgan Kaufmann, pp. 141, 1993.

24. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

25. Hamilton, A., Papathanasiou, K., Tamplin, M.R., and Brandtner, Т., Palmo: field programmable analog and mixed-signal VLSI for evolvable hardware, in

26. Proc. of the Second International Conference on Evolvable Systems: From Biology to Hardware (ICES98), Lausanne, Switzerland, Sipper, M., Mange, D, and Perez-Uribe, A., Eds, vol. 1478, LNCS, Springer-Verlag, 1998, 335.

27. J.G. Eldredge and B.L. Hutchings "Run-Time Reconfiguration: A Method for Enhancing the Functional Density of SRAM-Based FPGAs", in Journal of VLSI Signal Processing, Volume 12, 1996. Pages 67-86.

28. R.S. Zebulum, M.A. Pacheco, M.M. Vellasco. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms// USA, CRC Press LLC, 2002

29. Brandon Blondet, Philip James-Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform //Field-Programmable Logic and Applications. 13lh International Conference, FPL 2003 Proceedings, pp. 565-574.

30. M.J. Wirthlin, B. L. Hutchings. "DISC: The dynamic instruction set computer", in Field Programmable Gate Arrays (FPGAs) for Fast Board Development and Reconfigurable Computing, John Schewel, Editor, Proc. SPIE 2607, pp. 92-103 (1995).

31. В.В. Гудилов, JI.A. Зинченко. Повышение эффективности генетических алгоритмов на основе инструментального комплекса//Техническая кибернетика, радиоэлектроника и системы управления, Таганрог, 2002, стр. 127.

32. В.В.Гудилов, В.М. Курейчик. Устройство аппаратной реализации вероятностных генетических алгоритмов// Методы и средства обработки информации. Труды Второй Всероссийской научной конференции. МГУ им. М. В. Ломоносова. Москва 2005. стр. 596-601.

33. В.В. Гудилов, Л. А. Зинченко. Аппаратная реализация вероятностных алгоритмов эволюционного поиска//Известия ТРТУ, №2 Интеллектуальные САПР Материалы международной научно-технической конференции, Таганрог 2003, стр 209-215.

34. В.В. Гудилов, Л. А. Зинченко. Аппаратная реализация вероятностных генетических алгоритмов с параллельным формированием хромосомы/ЯТерспективные информационные технологии и интеллектуальные системы, №4, 2003, стр 34-38

35. Virtual Computer Corporation. The Reconfigurable Computer Company. http://www.vcc.com

36. Stephen D. Scott, Ashok Samal, Sharad Seth. HGA: A Hardware-Based Genetic Algorithm // Dept. of Computer Science Washington University St. Louis, MO 63130-4899, 7 p. 2001.

37. A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27-30, 2001, pp.624-629.

38. John C. Gallagher, Saranyan Vigraham and Gregory Kramer. A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware // IEEE Transactions on Evolutionary Computation, vol. 8, No. 2, April, 2004

39. В. Стешенко, А. Самохин. Язык описания аппаратуры AHDL: www: http://ce.cctpu.edu.ru/msclub/pld/steshenko/ahdl.html53. www: http://altera.com54. www: http://xilinx.com

40. Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н.Э.Баумана, 2000.- 360с.

41. Гудилов В.В., Зинченко JI.A., Курейчик В.В., Курейчик В.М. Устройство аппаратной реализации вероятностных генетических алгоритмов. Патент Российской Федерации на изобретение №2294561, заявка № 2005108760 от 28.03.2005.

42. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР.-М.: Энергоатомиздат, 1987.

43. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. -М.: Радио и связь, 1990.

44. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983.

45. Brayton R.K. Factoring logic functions // IBM Journal of Research and Development. Vol. 31. № 2. March 1987. P. 187-198.

46. Miihlenbein Н., Kureichik V.M., Mahnig Т., Zinchenko L.A., A Comparison of Different Fitness Functions for Evolutionary Analog Circuit Design, Evolutionary Methods for Design, Optimization and Control, CIMNE, Barcelona, Spain, 2003, pp.49-50.

47. Зинченко JI.A. Интеллектуальные системы схемотехнического проектирования. Десятая национальная конференция по искусственному интеллекту с международным участием. Труды конференции, Москва, Физматлит 2006. стр. 984-992.

48. J. R. Koza. Genetic Programming II Automatic Discovery of Reusable Programs// A Bradford Book The MIT Press Cambridge, Massachusetts London, England 746 s

49. J. R. Koza et al. Genetic Programming III//. San Francisco, CA: Morgan Kaufmann Publishers, 1999. P. 130.

50. Holland J.H. "Genetic Algorithm, Scientific American, July 1992.

51. B.B. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

52. Курейчик В.М. Генетические алгоритмы. Обзор и состояние// Новости искусственного интеллекта, М, №3,1998, с.14-64.

53. Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы// Известия АН. Теория и системы управления, №1,1999, с. 144160.

54. Курейчик В.В. Генетические алгоритмы в проектировании СБИС: Учебное пособие. Таганрог: Изд-во ТРТУ, 1997.

55. В.М. Курейчик. Генетические алгоритмы// Таганрог, 1998.

56. Sripramong Т., Toumazou С. The Invention of CMOS Amplifiers Using Genetic Programming and Current-Flow Analisis //IEEE Trans. CAD, 2002.

57. Vieira P.F., Sa L.B. Botelho J.P.B., Mesquita A. Evolutionary synthesis of analog circuits using only MOS Transistors //Proc. EH'04. 2004

58. H. Muhlenbein. The Equation for Response to Selection and its Use for Prediction// Evolutionary Computation, May 1998, pp.303-346.

59. Гладков JI.A. Курейчик, В.М. Курейчик Генетические алгоритмы// Ростов-на-Дону, Ростиздат. 2004 год.

60. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: Изд-во ТРТУ, 2000. 192 с.

61. Лебедев Б.К. Методы поисковой адаптации на основе механизмов генетики, самообучения и самоорганизации. // Программные продукты и системы, 2002, №1, с.16-20.

62. J.D. Hadley, В. L. Hutchings. "Designing a partially reconfigured system," in Field Programmable Gate Arrays (FPGAs) for Fast Board Development and Reconfigurable Computing, John Schewel, Editor, Proc. SPIE 2607, pp. 210-220 (1995).

63. Joseph Hawkins, Scott Hemmert, Brent Nelson, and Mike Rytting "A CAD Suite for High-Performance FPGA Design", in Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines, April 1999.

64. Higuchi, Т. Niwa, Т., Tanaka, Т., Iba, H., de Garis, H., Furuya, Т.: Evolvable Hardware with Genetic Learning// Proc. Sinmlation of Adaptive Behavior, MIT Press (1993) 417-424.

65. I. Kajitani and other. An evolvable hardware chip and its application as a multi function prosthetic hand controller// In Proc. of 16th National Conference on Artificial Intelligence (AAAI-99), 1999.

66. A. Mark H. Kikuo. Genetic design method and apparatus//Patent number: US2004049472. Application number:US20030649936 20030828

67. I. Takashi, S. J. Barry, 0. Etsuko, Y. Mitsuhiro. Fitness function circuit//Patent number: US6185547. Application number: US 19970909830 19970812

68. I. Takashi, S. J. Barry, 0. Etsuko, Y. Mitsuhiro. Genetic algorithm machine and its production method, and method for executing a genetic algorithm//Patent number: US5970487. Application Number: US 19970910103 19970813

69. G. Harik, F. Lobo and D. Goldberg. The Compact genetic Algorithm // IEEE Transactions on Evolutionary Computation, vol. 3, Nov, 1999, pp. 287-309

70. K.A. DeJong. An analysis of the behavior of a class of genetic adaptive systems // Ph.D. dissertation, Univ. Michigan, Ann Arbor, MI, 1775

71. D. E. Goldberd. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 412 p.

72. C. A. Coello. An Empirical Study of Evolutionary Techniques for Mul-tiobjective Optimization in Engineering Design. PhD thesis, Department of Computer Science, Tulane University, New Orleans, LA, apr 1996.

73. T. Kalganova, J. F. Miller, and N.Lipnitskaya. "MultipleValued Combinational Circuits Synthesised using Evolvable Hardware," in Proceedings of the 7th Workshop on Post-Binary Ultra Large Scale Integration Systems, 1998.

74. Hollingworth, G. S., Smith, S. L. and Tyrrell, A. M., "The Intrinsic Evolution of Virtex Devices Through Internet Reconfigurable Logic," in Proceedings of the Third International Conference on Evolvable Systems. Vol. 1801,2000, pp. 72-79.

75. Черун C.B. Синтез комбинационных логических схем на основе эволюционного подхода. Диссертация, Таганров 2005, 157 стр.

76. David Е. Goldberg. Genetic Algorithms in search, optimization, and machine learning. Addison Wesley, 1989.

77. M. Murakawa et al. The grd chip: Genetic reconfiguration of dsps for neural network processing//IEEE Transactions on Computers, 48(6):628-638, June 1999.

78. J.D. Lohn and S.P. Colombano. A circuit representation technique for automated circuit design// IEEE Trans, on Evolutionary Computation, 3(3):205-219, September 1999.

79. Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования // Новости искусственного интеллекта. 2000. -№3. - С. 159-170.

80. M. Iwata et al. A pattern recognition system using evolvable hardware// In Proc. of Parallel Problem Solving from Nature IV (PPSN IV). Springer Verlag, LNCS 1141, September 1996.

81. Mining, and Complex Systems, Proc. of ANNIE'99. ASME Press, November 1999.

82. E. Takahashi et al. An evolvable-hardware-based clock timing architecture towards gigahz digital systems// In Proc. of the Genetic and Evolutionary Computation Conference, 1999.

83. J. F. Miller. Digital filter design at gate-level using evolutionary algorithms// In Proc. of the Genetic and Evolutionary Computation Conference, 1999.

84. Sakanashi et al. Evolvable hardware chip for high precision printer image compression// In Proc. of 15th National Conference on Artificial Intelligence (AAAI-98), 1998.

85. J. Torresen. Scalable evolvable hardware applied to road image recognition// In Proc. of the 2nd NASA/DoD Workshop on Evolvable Hardware. Silicon Valley, USA, July 2000.

86. D. Keymeulen et al. On-line model-based learning using evolvable hardware for a robotics tracking systems//In Genetic Programming 1998: Proc. of the Third Annual Conference, pages 816-823. Morgan Kaufmann, 1998.

87. E. Угрюмов. Цифровая схемотехника. Санкт-Перербург, "БХВ-Петербург" 2000 г. 528 стр.

88. Ю.В. Капитонова и др. Лекции по дискретной математике. Санкт-Перербург, "БХВ-Петербург" 2004 г. 624 стр.

89. Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001.

90. Кузнецов О.П. Дискретная математика для инженера. СПб.: Лань, 2004.

91. I. Kajitani, T. Hoshino, D. Nishikawa, H. Yokoi, S. Nakaya, T. Yamauchi, T. Inuo, N. Kajihara, M. Iwata, D. Keymeulen, T. Higuchi. A gate-level EHW chip: Implementing GA operations and reconfigurable hardware on a single LSI//

92. Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1478 (Proc. ofICES1998), pp. 1-12, Springer Verlag, 1998.

93. Д. Кнут. Искусство программирования для ЭВМ. Том 3. "Сортировка и поиск"// Москва Мир 1978г.

94. Баталов Б.В, Щемелинин В.М. Проектирование топологии интегральных схем на ЭВМ. М.: Машиностроение, 1979.

95. Основные обозначения и сокращения1. ГА генетические алгоритмы

96. ГП генетическое программирование1. ЛЭ логический элемент1. ММ математическая модель

97. ПЛМ программируемая логическая матрица

98. ПЛИС программируемые логические интегральные схемы FPGA1. П„ текущая популяция

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