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

• Гудилов, Виталий Витальевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Гудилов, Виталий Витальевич

Введение.

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], выполнено исследование (на уровне генетических операторов и их взаимодействия) бинарного генетического алгоритма для решения задачи автоматизированного синтеза комбинационных схем для ПЛМ.

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

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

Список литературы диссертационного исследования кандидат технических наук Гудилов, Виталий Витальевич, 2007 год

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. С величина схемы, определяющая количество используемых элементовс количество входных переменных аналитической функции