ВВЕДЕНИЕ
В современных условиях жесткой конкуренции и значительного ускорения темпов технического прогресса необходимо при минимальных сроках проектирования обеспечить высочайшее качество проектируемых изделий большой функциональной сложности. Решение сложных задач проектирования сегодня уже невозможно без применения помощи систем автоматизированного проектирования (САПР). Постоянное усложнение и увеличение задач, решаемых проектировщиком, обуславливает потребность в постоянном развитии САПР, совершенствовании и внедрении накопленных, а также разработке новых методов и средств, способных существенно повысить качество проектирования [1-5].
В области системного и логического проектирования еще очень большая доля работ выполняется не машинной, а проектировщиком, вследствие чего результаты в значительной степени зависят от индивидуальных способностей специалиста. Однако при проектировании больших интегральных схем (БИС) появилась необходимость выполнять за короткий срок точно и безошибочно большой объем работ по логическому проектированию сложного устройства, что в свою очередь вызвало усиление требования автоматизации этого процесса.
Сегодня накопление опыта и сложных форм знаний проектировщика становятся частью основы для подхода к созданию современных полнофункциональных САПР и отдельных модулей САПР, отвечающим всем жестким требованиям. В итоге в настоящее время компьютер в паре с пользователем должен лучше опытного эксперта, проектировщика выполнять всевозможные процедуры проектирования, традиционно относимые к области интеллектуальной деятельности человека. Акад. Г.С. Поспелов писал: «Способность компьютера выдавать творческие результаты — это не что иное, как овеществленные знания в машине и интеллект человека».
БИС обрабатывает данные, представленные в двоичном виде. Поскольку операции, используемые при обработке, описываются как логические функции, средства представления логических функций в БИС являются основой логического проектирования.
Обычно логическая функция реализуется комбинационной схемой. Основу комбинационных схем составляют вентили, реализующие логическую функцию. Конкретная реализация этих вентилей зависит от процесса изготовления и типа схемы.
Известно [6-13], построению комбинационных логических схем Гл> предшествует операция получения и упрощения структурной формулы,
полученной в свою очередь из функции представленной в виде таблицы состояний. В настоящее время для получения и упрощения структурной формулы используют несколько основных методов. Это диаграммы Карно и метод Квайна - Мак-Класски.
Оба метода механически по своей структуре. Диаграммы Карно
возможно использовать для минимизации функций содержащих до пяти-
'*' шести переменных. Метод Квайна - Мак-Класски возможно использовать
для функций с любым количеством элементов, и притом его легко
реализовать программно.
Оба метода, и карты Карно, и процедура Квайна - Мак-Класски, разрешают получить двухуровневые схемы. Заметим, что наилучшим решением является комбинационная схема с минимальной задержкой прохождения сигналов в ней. Тем не менее, довольно часто требуется получить минимизацию количества логических элементов в схеме, при * этом, не утратив скорости прохождения сигналов. Для минимизации
количества логических элементов часто необходимо получить многоуровневую комбинационную схему. Поэтому совместно с методами Карно и Квайна - Мак-Класски используют различные алгебраические манипуляции над логическими выражениями. Помимо этого метод Квайна — Мак-Класски не эффективен в смысле минимизации вычислительных
3" затрат. Верхняя граница количества основных операций равна —, где п -
п
количество входящих элементов в таблице истинности. Это означает, что вычислительные затраты для реализации этого метода растут экспоненциально с количеством входов таблицы истинности. Также этот метод накладывает ограничение на используемые логические элементы в схемах: доступны только основные -элементы, такие как: AND, OR, NOT. Для использования элементов XOR приходится генерировать решение опытному эксперту [6].
В связи с этим возникает необходимость построения таких методов поиска комбинационных схем, которые были бы способны отыскивать решения при практически полном отсутствии предположений о характере исследуемой функции. Этим требованиям в значительной степени удовлетворяют эволюционные вычисления, которые представляют собой алгоритмы поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного процесса развития живых организмов.
Использование эволюционных .вычислений для нахождения решений в различных задачах является одним из альтернативных путей повышения интеллектуальности систем проектирования. Способность эволюционных алгоритмов к нахождению нестандартных и неожиданных решений подтверждается результатами большого числа исследований [14-25].
В настоящее время эти алгоритмы находят всё более широкое применение в силу своей способности решать слабо формализованные задачи. Это область задач на сегодняшний день требует интуитивных знаний о предмете проектирования и решается с привлечением экспертов для каждой конкретной задачи отдельно, где нет сформулированных, чётких правил, что изменение какого-либо параметра приведёт к определенным последствиям, что фактически, и соответствует задаче получение комбинационной схемы из таблицы истинности.
Цель диссертационной работы заключается в разработке и исследовании методов и алгоритмов, обладающих малой трудоемкостью и
обеспечивающих гарантированное качество при решении задач синтеза
¦Л)
комбинационных логических схем на основе эволюционного подхода.
Для достижения поставленной цели были решены следующие основные задачи:
1. Разработаны и исследованы алгоритмы синтеза комбинационных логических схем на основе эволюционного подхода.
2. Разработан и исследован принцип кодирования, хранения и • модификации альтернативных решений на различных этапах синтеза
комбинационных логических схем.
3. Разработаны модифицированные генетические операторы, ориентированные на задачу синтеза комбинационных схем.
4. Найден метод оценки качества получаемых альтернативных решений.
5. Разработан комплекс программ эволюционного проектирования на основе предложенных алгоритмов.
Методы исследования. Методы исследования основаны на теории алгоритмов, алгоритмах эволюционных вычислений.
Научная новизна заключается в следующем:
1. Сформулированы принципы, стратегии и методы синтеза
комбинационных схем на основе эволюционного подхода.
'У
2. Разработан генетический алгоритм синтеза комбинационных
логических схем.
3. Разработана методика перехода от генотипа к фенотипу при синтезе комбинационных логических схем.
4*
4. Построены модифицированные операторы генетического поиска, ориентированные на задачу синтеза комбинационных логических схем.
Практическую ценность представляют:
Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов синтеза комбинационных схем, позволяющих использовать разработанные методы, отвечающие конкретным задачам САПР. Алгоритмы реализованы на языке С# под ОС Windows. Проведенные экспериментальные исследования, показали преимущество предложенных алгоритмов и методик для решения задачи синтеза комбинационных схем, по сравнению с известными методами. Разработанные алгоритмы позволяют получать набор оптимальных решений. Время получения лучших результатов работы алгоритмов, соответствует полиномиальному времени О(п2), которое требуют эффективные итерационные алгоритмы.
Реализация результатов работы.
Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации нейросетевых моделей и методов принятия решений», а также в научно-исследовательской работе №12388 по теме «Разработка теорем и принципов принятия решений при разбиении сложных математических объектов на части на основе моделирования эволюции и фрактальных множеств».
Материалы диссертации были использованы в лабораторных, практических работах и при чтении следующих курсов на кафедре САПР
8
ТРТУ: «Математическая логика и теория алгоритмов», «Эволюционное моделирование и генетические алгоритмы».
Внедрение в учебный процесс ряда теоретических и практических результатов диссертационной работы позволило повысить качество подготовки специалистов в области проектирования САПР и информационных технологий.
Публикации. По теме диссертации опубликовано 6 печатных работ.
4 Структура и объем диссертационной работы. Диссертационная
работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 129 стр., 57 рис., 24 табл., список литературы из 112 наименований, 30 стр. приложений и актов об использовании.
Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, приведены сведения о полученных научных и практических результатах, реализации и внедрении результатов работы, апробации, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ дано определение эволюционной электроники, приведена постановка задачи синтеза комбинационных логических схем. Произведен анализ существующих методов синтеза комбинационных логических схем.
Во ВТОРОЙ ГЛАВЕ рассматриваются методы эволюционного , 4> проектирования комбинационных логических схем. Предложена методика
кодирования решений, позволяющая учитывать специфику решаемой задачи. Рассмотрен модифицированный алгоритм формирования начальной популяции. Рассмотрены особенности использования генетических операторов при эволюционном проектировании комбинационных логических схем.
В ТРЕТЬЕЙ ГЛАВЕ рассмотрен алгоритм выбора кандидатов на очередной этап скрещивания, рассмотрен пример работы алгоритма.
Разработан алгоритм функции рекомбинации. Предложен алгоритм ¦ вычисления целевой функции, который включает в себя разработанный
алгоритм нахождения дерева внутри матрицы пространства поиска решения. Определены основные критерии останова поиска. Показана на примерах, информативность выходных данных после работы предложенных алгоритмов.
В ЧЕТВЁРТОЙ ГЛАВЕ приведены результаты экспериментальных
^1 исследований. Описаны функциональные особенности программных
средств, реализующих синтез комбинационных схем на основе
предложенных алгоритмов, методик и подходов. Поставлены цели
экспериментальных исследований. Проведены серии экспериментов для
определения оптимальных параметров алгоритма. Выполнено сравнение
предложенного подхода с известными наборами тестовых данных. По
результатам исследований определены оптимальные управляющие
¦^' параметры для алгоритмов.
В ЗАКЛЮЧЕНИИ приведены основные результаты, полученные в диссертационной работе.
В ПРИЛОЖЕНИИ приведены акты об использовании результатов диссертационной работы.
10
1. ЭВОЛЮЦИОННОЕ ПРОЕКТИРОВАНИЕ ЛОГИЧЕСКИХ СХЕМ
1.1. Эволюционная электроника
Эволюционная электроника — область исследований, которая охватывает все прикладные задачи, использующие эволюционные вычисления для разработки электронных систем. Эволюционные вычисления используют средства поиска, охватывая специфический класс алгоритмов, который использует некоторые аспекты естественной эволюции как метафоры. Эти алгоритмы, называются эволюционными алгоритмами (ЭА). Они широко применяются к сложным проблемам оптимизации. Выделяют два основных аспекта, связанных с эволюционными алгоритмами:
• эволюционные алгоритмы типично производят выборку всех возможных решений (до 108), чтобы найти то, которое удовлетворяет
41 техническим требованиям, хотя количество выбранных решений,
часто незначительно по сравнению с огромным размером области поиска (до 10500);
• осуществление выборки в эволюционном алгоритме не происходит случайным образом. Здесь используются естественные принципы эволюции.
В середине 80-х годов эволюционные алгоритмы были применены к оптимизации цифровых микросхем, в задачах типа монтажа и ¦•* формирования разводки [26]. В начале 90-х, области исследований на
основе эволюционных алгоритмов значительно расширились:
• идея использования эволюционных алгоритмов не только для того, чтобы оптимизировать топологию цифровых микросхем, но и для получения технологии проектирования электронных схем в целом, включая разработку топологии схемы с самого начала;
11
• разработка нового класса интегральных схем, названных
программируемыми логическими интегральными схемами (ПЛИС).
Эти устройства могут быть быстро реконфигурированы
перепрограммированием, тем самым, имея возможность реализовать
огромное разнообразие цифровых схем.
Работа Льюиса и Ролинса [27] была одной из первых, представляющих идею использования эволюционных алгоритмов, как инструментальных средств, чтобы осуществить структурную разработку. В частности, было представлено понятие структурного синтеза цифровых 'J) схем: эволюционный алгоритм использовался, чтобы синтезировать
размещение цифровых логических элементов, которые решали определенную проблему, типа функции четности. Эта идея была достаточно оригинальна, поскольку эволюционный алгоритм выполнял полное автоматическое проектирование интегральных микросхем, с «нуля», не требуя экспертных знаний. Это радикально отличалось от предыдущих технологий, где эволюционные алгоритмы использовались - только, для того чтобы оптимизировать VLSI-топологии, являющиеся
результатом от схем, разработанных экспертом. К тому же, идея использования вычислительного алгоритма, чтобы достигнуть проектирования интегральных микросхем с «нуля», противопоставлялась процедуре, сопровождаемой большинством инструментальных средств САПР для проектирования интегральных микросхем, которые основаны на знаниях эксперта и ограничениях.
Согласно разновидности электронной разработки, эволюционная электроника может классифицироваться на три категории: цифровую, аналоговую и смешанную.
Прикладные задачи эволюционной электроники в цифровой разработке наиболее перспективны по двум причинам: более большая сложность области поиска; [28] и существование эффективных инструментов разработки автоматизированного проектирования,
12
посвященных цифровым схемам. Первая причина происходит от внутренней природы цифровой разработки. Во вторых, трудно разрабатывать новые инструменты автоматизированного проектирования, которые обеспечат конкурентоспособную рабочую характеристику в сравнении с уже существующими.
В настоящее время синтез комбинационных логических схем на основе эволюционной электроники зачастую превосходит схемы, разработанные человеком. Требования к цифровым разработкам возрастают и существующие " инструменты автоматизированного _! проектирования не в состоянии производить удовлетворительные решения.
Другая важная причина для развития исследования в области эволюционного проектирования цифровых схем - это важность цифровой технологии в современной электронике.
Важной систематикой эволюционной электроники является поиск схем при помощи программного обеспечения, такую методологию называют внешней эволюцией, а на перестраиваемых чипах - внутренней *' эволюцией. Таблица 1.1 представляет сравнительный анализ между
внешней и внутренней эволюцией. Согласно Таблице 1.1, есть много аспектов для сравнения внешней и внутренней эволюции электронных схем. В зависимости от особенностей разрабатываемых комбинационных логических схем может применяться внешняя или внутренняя методология. Во временном отношении, не возможно определить, какой метод удовлетворит требованиям в большей степени.
Использование внутренней или внешней методологии позволяет синтезировать новые комбинационные логические схемы с уникальной топологией. В обоих случаях, нет необходимости ограничивать процесс поиска, чтобы произвести выборку только хорошо известных топологий.
Обычно сложнее выполнить внутренний эксперимент, чем внешний. В первом случае, аппаратный интерфейс между главным компьютером и перестраиваемым чипом осуществляется лицом принимающим решения.
13
.Ml
Во втором, должен быть осуществлен простой программный интерфейс между эволюционным алгоритмом и программой моделирования схемы.
Таблица 1.1.
Свойство Внешняя дв®1Щи * Внутренняя^^
Время в зависимости от применения в зависимости от применения
Новые схемы возможно генерировать возможно генерировать
Сложность эксперимента Меньше Выше
Область поиска Меньше Больше
Свойства кремния частично рассмотрены полностью рассмотрены
Надежность Ниже Выше
Ошибкоустойчивость Выше Ниже
Кроме того, в случае перестраиваемых чипов, некоторые запрещенные конфигурации схемы, сгенерированные эволюционным алгоритмом, могут повредить схему. Перестраиваемые чипы закодированы через большие двоичные ряды, приводящие к очень большим областям поиска. С другой стороны, при использовании внешней методологии размер области поиска может управляться лицом принимающем решения, через оптимизированные образы. Эволюционные алгоритмы работают с большой областью поиска; однако, когда область поиска становится чрезмерно большой, даже эволюционный алгоритм сможет произвести выборку только очень маленькой части этой области, нарушая эволюционный процесс.
Отметим основные общие особенности эволюции схем на основе использования как внутренней, так и внешней эволюции:
• Большой потенциал для нахождения новых схем;
• Возможность нахождения новых топологических проектных норм из синтезированных решений;
14
• Эволюционные методы позволяют рассмотреть большее количество технических норм на проектирование по сравнению с классическими методами.
• В настоящее время, при проектировании комбинационных
логических схем необходимо учитывать много критериев: площадь, низкая потребляемая мощность, скорость прохождения сигнала и, в некоторых случаях, требования к отказоустойчивости. Эволюционные алгоритмы содержат в себе методологии позволяющие обрабатывать множество целей проектирования.
1.2. Особенности эволюционных алгоритмов
Под эволюцией понимаются медленные, постепенные, количественные и качественные изменения объекта. При этом каждое новое состояние объекта, как правило, имеет по сравнению с предыдущим более высокий уровень развития и организации.
Моделирование эволюции может представить алгоритмические средства для решения оптимизационных задач. В общих чертах эволюция может быть описана как многоступенчатый итерационный процесс, состоящий из случайных изменений и последующей затем селекции.
Результаты анализа известных форм эволюционных алгоритмов показывают определенные методологические различия между ними [29]. Эти различия касаются формы представления целевой функции и альтернативных решений. Операторов рекомбинации, мутации и вероятностей их использования, стратегии селективного отбора и методов повышения эффективности эволюционных вычислений путем адаптации.
Методологические различия между разными формами эволюционных вычислений позволяют отметить базовые свойства, такие как универсальность и фундаментальность, присущие эволюции независимо от формы и уровня абстракции модели. Указанная общность
15
может быть выражена в виде схемы абстрактного эволюционного алгоритма [30]:
1. Установка параметров эволюции;
2. инициализация начальной популяции;
3. t:=0;
4. оценка решений входящих в популяцию;
5. t:=t+l;
6. селекция (отбор);
7. репликация (повторение, копирование, автосинтез);
8. вариация (видоизменение);
9. оценка решений-потомков;
10. образование новой популяции P(t);
11. выполнение алгоритма до тех пор, пока параметр t не достигнет значения tmax либо не будут выполнены другие условия останова;
12. вывод результатов и останов.
Решающим обстоятельством для оценки практической пригодности и результативности эволюционного алгоритма являются скорость (время, необходимое для выполнения заданного пользователем числа итераций) и устойчивость поиска (способность постоянно, от поколения к поколению, увеличивать качество популяции).
Эволюционные алгоритмы ориентированы на решение практических задач оптимизации. Поэтому они не гарантируют нахождение глобального оптимума в заданное время. Однако многочисленные примеры применения эволюционных алгоритмов показывают, что они позволяют получать наборы квазиоптимальных или оптимальных решении за полиномиальное время.
16
1.3. Постановка задачи синтеза комбинационных схем
Постановка задачи в общем виде состоит в получении комбинационной логической схемы основываясь на данных из таблицы истинности и наборе допустимых логических элементов.
Постановка задачи синтеза комбинационных схем описана кортежем: <Х, D, Q>, где X - является множеством всех решений, D -ограничения, накладываемые на множество X для получения допустимых решений и Q - целевая функция (ЦФ), с помощью которой можно определить наилучшее (оптимальное) решение [31-33]. Здесь X - множество всех возможных хромосом в популяции. Эти хромосомы могут быть нерелевантными, т.е. кодировать в себе недопустимые решения, или решения, не приводящие ни к какому результату. Обозначим популяцию на шаге ГА t как Ph а хромосому с номером / - ht. Тогда можно записать, что популяция на шаге t Pt ={hif ... ,hnj, где t=[l,T], n=[l,N], T- количество итераций ГА и N - количество хромосом в популяции. Параметр Т может варьироваться в заданных пределах. Тогда X можно записать в следующей форме:
Х= {Р„ t=l, ..., Т} = {hti, t=l, ..., Т; i=l, ..., N}.
Решение представляется в виде неоднородной хромосомы. Исходя из этого условия, каждый ген может приминать только ограниченное количество значений, чтобы удовлетворять условию hczX, т.е. принадлежать области допустимых решений. Для генов, кодирующих номера входов это значения от 1 до к, где к ~ количество строк матрицы в которой осуществляется поиск решения. Для гена, кодирующего логический элемент, это значения от 1 до 5 (номера возможных логических элементов).
Целевая функция является многопараметрической. Во-первых она зависит от количества логических элементов. Второй составляющей целевой функции является количество связей (WIRE). Целевая функция описывается в следующем виде:
17 |
