Содержание к диссертации
Введение
Глава 1. Анализ существующих методов повышения отказоустойчивости ПЛИС типа FPGA и постановка задачи исследования 19
1.1. Анализ объекта исследования – ПЛИС 19
1.2. Причины и виды отказов 29
1.3. Существующие алгоритмы, методы и средства диагностирования и реконфигурации логики ПЛИС типа FPGA
1.3.1. Методы диагностирования 32
1.3.2. Методы реконфигурации 37
1.4. Постановка задачи исследования 42
Выводы по главе 1 47
Глава 2. Генетический алгоритм диагностирования ПЛИС 50
2.1. Генетические алгоритмы как универсальный метод решения задач оптимизации и поиска 50
2.1.1. Базовые понятия генетических алгоритмов 51
2.1.2. Общие техники усовершенствования ГА 58
2.1.3. Применение ГА в решении различных задач 61
2.2. Построение модели частичных отказов логических элементов ПЛИС 63
2.2.1. Частичные отказы ФПТ элементов 63
2.2.2. Частичные отказы LUT-элементов 66
2.3. Математическая модель генетических алгоритмов 68
2.3.1. Шаблоны и теорема шаблонов 68
2.3.2. Подходы на основе теории вероятности и математической статистики 70
2.3.3. Модель Воса и Липинса
2.4. Разработка генетического алгоритма диагностирования ПЛИС 76
2.5. Выводы по главе 2 85
Глава 3. Генетический алгоритм реконфигурации ПЛИС 87
3.1. Разработка генетического алгоритма поиска компактного множества работоспособных элементов 87
3.1.1. Формализация задачи 87
3.1.2. Базовый приближенный алгоритм 89
3.1.3. Генетический алгоритм
3.2. Обоснование сходимости генетического алгоритма к точному решению 95
3.3. Разработка программы поиска компактного множества работоспособных элементов
3.3.1. Используемые инструментальные средства и технологии 105
3.3.2. Структура программной системы 107
3.4. Разработка программы автоматического синтеза множества комбинационных схем для целей реконфигурации 111
3.4.1. Реконфигурация схемы на LUT-элементах 112
3.4.2. Реконфигурация схемы на ФПТ элементах 116
3.4.3. Формирование возможных отказов схемы 117
3.4.4. Программная реализация 118
3.5. Выводы по главе 3 119
Глава 4. Разработка модифицированных методов рабочего и тестового контроля логических элементов LUT 122
4.1. Рабочий контроль LUT путём использования второй половины дерева передающих транзисторов 122
4.2. Тестовый контроль LUT путём использования второй половины дерева передающих транзисторов 131
4.3. Контроль дерева LUT путём использования второй половины дерева передающих транзисторов с дублированием настройки 132
4.4. Контроль дерева LUT путём использования второй половины дерева передающих транзисторов с дублированием настройки и инверторов переменных 134
4.5. «Обратное» диагностирование логического элемента LUT 138
4.6. Моделирование предложенных методов контроля логических элементов LUT 146
4.7. Выводы по главе 4 152
Глава 5. Оценка эффективности предложенных алгоритмов и методов 154
5.1. Параметры генетического алгоритма 154
5.2. Оценка эффективности двухуровневого кодирования 161
5.3. Оценка эффективности «обратного» диагностирования LUT 169
5.4. Комплексная оценка эффективности предложенных методов 176
5.5. Выводы по главе 5 182
Заключение 184
Список использованных источников
- Существующие алгоритмы, методы и средства диагностирования и реконфигурации логики ПЛИС типа FPGA
- Общие техники усовершенствования ГА
- Обоснование сходимости генетического алгоритма к точному решению
- Контроль дерева LUT путём использования второй половины дерева передающих транзисторов с дублированием настройки и инверторов переменных
Введение к работе
Актуальность работы. Интенсивное развитие и совершенствование цифровых устройств приводит к их активному применению в различных областях науки и техники, в том числе в системах специального назначения. Отдельно стоит отметить системы, применяемые в аэрокосмической отрасли, в авиации, в военной технике, в управлении атомными электростанциями, в м едицине и других отраслях . Нарушение функционирования таких критических систем управления может причинить значительный экономический или экологический ущерб, нести угрозу здоровью или жизни людей, а иногда даже привести к катастрофическим последствиям. Поэтому проектирование надёжных, безопасных систем является одной из ключевых проблем современной науки и инженерной практики. Важность названных проблем для нашей страны подтверждается тем, что технологии информационных, управляющих, навигационных систем, а также технологии создания электронной компонентной базы включены в перечень критических технологий Российской Федерации, утвержденный соответствующим указом Президента РФ.
Для обеспечения требуемых характеристик надежности при проектировании отказоустойчивых систем используется специальная элементная база , с о-здание которой часто требует применения специальных материалов и технологий, что усложняет процесс производства и значительно увеличивает стоимость оборудования. В качестве элементной базы систем управления в настоящее время помимо универсальных процессоров, микроконтроллеров и заказных больших интегральных схем широко применяется программируемая логика: базовые матричные кристаллы (БМК), программируемые логические интегральные схемы (ПЛИС) и, в частности, программируемые пользователем вентильные матрицы (ППВМ, англ. Field-Programmable Gate Array, FPGA), а также системы на кристалле (System on Chip, SoC). В настоящее время серьезные успехи достигнуты в области создания отечественных БМК для аппаратуры специального назначения, вопросам разработки самосинхронных схем на БМК посвящены работы Ю.А. Степченкова, Ю.Г. Дьяченко и других. Основным преимуществом БМК является отсутствие избыточных элементов программирования схемы, что существенно снижает сложность микросхемы и, тем самым, повышает ее надежность. Однако, если в процессе функционирования отказ все же произошел, возможность оперативного удаленного восстановления работоспособности схемы, построенной на основе БМК, отсутствует, так как логика их работы не может быть динамически перепрограммирована.
В современной цифровой аппаратуре систем управления и вычислительной техники, в аппаратуре специального назначения, в том числе военной, широко используются ППВМ как о дна из разновидностей ПЛИС. Их особенностью является то, что логика работы задается путем программирования, то есть может быть оперативно изменена прямо во время использования устройства. Такая особенность приводит не только к возможности гибкой настройки схемы для конкретной решаемой задачи за короткий срок, но и к возможности восстановления работоспособности после отказа путем реконфигурации. На настоя-3
щий момент лидерами в производстве ПЛИС типа FPGA являются иностранные компании (Xilinx, Altera, Lattice Semiconductor, Microsemi, Atmel и другие). Таким образом, актуальной является практическая задача разработки отечественных ПЛИС для критических, высоконадежных применений.
Одним из важнейших этапов обеспечения надежности является контроль и диагностика. Основные принципы контроля и диагностики цифровой аппаратуры были заложены Р. Хэммингом, А. Авиженисом, П.П. Пархоменко, Е.С. Согомоняном, Ф. Селлерсом и др. Особенности диагностирования современных цифровых схем, в том ч исле ПЛИС, рассматривались в ра ботах Е. Зориана, В.С. Харченко, В.И. Хаханова, М.Ф. Каравая, А.Л. Переверзева, В.В. Слюсаря, Р.М. Романова, Г.П. Аксеновой, Е.Л. Кона, О.В. Гончаровского, В.И. Фреймана и других. Многие исследователи подчёркивают особое место логики ПЛИС, которая занимает всё меньшую площадь кристалла ПЛИС по сравнению с конфигурационной памятью и средствами трассировки, но без неё невозможно обеспечение надёжности. К тому же, и диагностика и реконфигурация логики ПЛИС существенно более сложны.
В работах С.Ф. Тюрина, А.В. Грекова, О.А. Громова предложены методы и средства повышения отказоустойчивости логики FPGA на основе функционально-полных толерантных элементов (ФПТЭ), сохраняющих либо логич е-ский базис, либо саму исходную функцию при отказах. Предложены соответствующие отказоустойчивые транзисторные структуры. Показано, что использование ФПТЭ позволяет повысить вероятность безотказной работы и коэффициент готовности как мелкозернистых ПЛИС (в которых логические элементы представляют собой набор простых логических вентилей), так и крупнозернистых ПЛИС типа FPGA (в которых используются таблицы поиска (Look-Up Table, LUT)). Однако вопросы контроля и диагностики схем на основе ФПТЭ до сих пор рассмотрены не в полной мере, а эффективность алгоритмов диагностики и реконфигурации логики FPGA исследована не достаточно. Это сдерживает развитие научно-методического аппарата проектирования FPGA на основе ФПТЭ для специальных критических, высоконадёжных применений, что особенно актуально в связи с необходимостью оперативного импортозамещения элементной базы. Таким образом, актуальна научная задача совершенствования методов и средств диагностирования и реконфигурации логики FPGA, в том числе построенной на основе ФПТЭ с целью повышения коэффициента готовности устройств путем сокращения среднего времени восстановления.
Сложность схем и количество используемых в них элементов постоянно возрастают, в настоящее время количество транзисторов в FPGA превысило миллиард, а количество логических элементов (ЛЭ) преодолевает миллионные рубежи. В связи с этим в области проектирования ПЛИС актуальными являются научные подходы, в том числе на основе эвристик, для нахождения оптимальных и квазиоптимальных решений за приемлемое время. В последнее время получает распространение подход к решению задач диагностирования и реконфигурации ПЛИС на основе генетических алгоритмов (ГА) (работы Д.Е. Иванова, Ю.А. Скобцова, Дж. Холма, Е. Рудник, Д. Сааб).
Объектом исследования являются программируемые пользователем вентильные матрицы (ПЛИС типа FPGA).
Предметом исследования являются методы, алгоритмы и средства обеспечения надёжности, контроля и диагностики функционирования ПЛИС типа FPGA.
Цель работы – совершенствование научно-методического аппарата диагностирования и реконфигурации логи ки ПЛИС типа FPGA, в том числе построенной с использованием ФПТЭ.
Решение сформулированной научной задачи происходит по двум направлениям: чисто программные методы и их аппаратная поддержка. Таким образом, д остижение указанной цели обеспечивается постановкой и решением в диссертационной работе следующих задач:
-
Разработка ГА диагностирования логики ПЛИС типа FPGA, учитывающего использование ФПТЭ в составе логических ячеек и минимизирующего время обнаружения отказа.
-
Разработка ГА реконфигурации логики ПЛИС типа FPGA, учитывающего использование ФПТЭ в составе логических ячеек и максимизирующего вероятность успешного восстановления после отказа.
-
Разработка модифицированного метода рабочего контроля логического элемента LUT.
-
Разработка модифицированного метода тестового контроля логического элемента LUT.
Научная новизна результатов:
разработан модифицированный ГА диагностирования ПЛИС типа FPGA на основе ФПТЭ, новизна которого заключается в использовании дополнительного внешнего цикла, позволяющего использовать ст ан-дартные генетические операторы и оптимизировать диагностическую последовательность по двум параметрам – длине последовательности и количеству отказов , которые эта последовательность позволяет обн а-ружить;
разработан модифицированный ГА реконфигурации ПЛИС типа FPGA на основе ФПТЭ, отличающийся оригинальным двухуровневым способом кодирования решений, позволяющим использовать стандартные генетические операторы, благодаря чему увеличивается вероятность получения приемлемого решения, а также учитывается возможность использования частично отказавших элементов;
впервые сформулирована и доказана теорема о сходимости предложенного ГА реконфигурации ПЛИС типа FPGA к точному оптимальному решению;
модифицирован метод рабочего (функционального) контроля логич е-ского элемента LUT FPGA, отличающийся тем, что используется и н-формация с неактивной половины дерева передающих транзисторов, благодаря чему повышается достоверность функционирования ЛЭ;
модифицирован метод тестового контроля логического элемента LUT FPGA, отличающийся тем, что введена быстрая обратная активация всех ветвей дерева передающих транзисторов LUT, благодаря чему сокращается время диагностирования;
получены оценки сложности и эффективности новых алгоритмов и технических решений реализации LUT с контролем, а также получены выражения для оценки их влияния на коэффициент готовности устройства.
Теоретическая и практическая значимость диссертации. Теоретическая значимость диссертации состоит в том, что в результате проведения исследований разработаны алгоритмы и программы диагностирования и реконфигурации логики ПЛИС FPGA, а также патентоспособные технические решения, обеспечивающие повышение надёжности отечественных ПЛИС FPGA критического применения. Практическая значимость подтверждается тем, что получено свидетельство о регистрации электронного ресурса на программный модуль для создания генетического алгоритма с двухуровневым кодированием, а также патенты РФ на программируемое логическое устройство с модифицированным рабочим (функциональным) контролем и на прог раммируемое логическое устройство с модифицированным тестовым контролем. Полученные результаты были использованы в виде технических предложений по созданию новых образцов отказоустойчивого телекоммуникационного оборудования, а также р е-комендаций по расширению возможностей тестирования выпускаемых изделий для ОАО «Морион» (г. Пермь). Использование результатов работы позволило повысить коэффициент готовности перспективных устройств связи в вариантах с активной отказоустойчивостью за счет сокращения среднего времени восстановления логики. Результаты также используются в учебном процессе на к а-федре Математического обеспечения вычислительных систем Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Пермский государственный национальный исследовательский университет» при преподавании дисциплин «Комбинаторные алгоритмы», «Математическая логика и теория алгоритмов», «Алгоритмы и анализ сложности». В частности, при разработке лабораторных работ по дисциплине «Алгоритмы и анализ сложности» реализованный ГА диагностирования был применен к ПЛИС Cyclone IV E фирмы Altera.
Методы исследования: дискретная математика, математическая логика и теория алгоритмов, генетические алгоритмы и эволюционное моделирование, теория надежности, отказоустойчивости, методы и средства объектно-ориентированного программирования.
Основные положения, выносимые на защиту:
алгоритм диагностирования логики ПЛИС типа FPGA на основе ФПТЭ;
алгоритм реконфигурации логики ПЛИС типа FPGA на основе ФПТЭ;
модифицированный метод рабочего контроля LUT FPGA;
модифицированный метод тестового контроля LUT FPGA;
оценки сложности и эффективности новых алгоритмов и технических решений реализации LUT FPGA с контролем.
Достоверность исследования подтверждается соответствием аналитических результатов и выводов результатам моделирования, в том числе схемотехнического.
Апробация работы. Основные теоретические и прикладные результаты диссертационной работы были представлены и одобрены на научно-технических конференциях: ITA 2007, ITA 2014 – Joint International Scientific Conferences on Informatics (Международный конгресс научных конференций в области информатики), Варна, Болгария, 2007, 2014; XLI международная конференция «Информационные технологии в науке, социологии и бизнесе», Ялта-Гурзуф, 2013; Третий международный семинар "Надежность и безопасность критических инфраструктур" (CrISS-DESSERT’13), Севастополь, 2013; 11th IEEE East-West Design & Test Symposium (EWDTS 2013), Ростов-на-Дону, 2013; на семинарах по проекту Евросоюза TEMPUS GreenCo project «Технологии зеленых вычислений» 2013-2015 гг.; 2015 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference, Санкт-Петербург, 2015 и других региональных и всероссийских конференциях.
Публикации. Основные результаты диссертационной работы опубликованы в 19 научных статьях, из них 1 в изданиях, индексируемых Scopus и 6 в других рецензируемых научных изданиях, включенных в Перечень ВАК.
Структура и объем работы. Диссертационная р абота состоит из введения, пяти глав, заключения, списка использованных источников, включающего 149 наименований и 3-х приложений. Основная часть работы изложена на 201 странице машинописного текста, содержит 68 рисунков и 16 таблиц.
Существующие алгоритмы, методы и средства диагностирования и реконфигурации логики ПЛИС типа FPGA
Кроме того, при отказе одного любого транзистора в схеме на рисунке 1.10 гарантированно остаётся одна работоспособная половина. Однако, поиск такой работоспособной половины сопряжён со значительными временными затратами, что осложняет использование такого подхода в задачах реального времени.
Что касается классификации ПЛИС по способу реконфигурации, то она тесно связана с типом используемой памяти.
Однократно программируемые ПЛИС. В них используются элементы с необратимыми изменениями состояний, например, перемычки типа fuse. Такая ПЛИС в исходном состоянии имеет все возможные соединения и для получения требуемой конфигурации схемы часть перемычек разрушается. Основное преимущество таких схем – быстрый старт, то есть начало полезного функционирования сразу в момент включения. Главным недостатком таких схем является невозможность конфигурировать ее более одного раза. То есть в случае потребности в доработке изменить что-либо уже невозможно и необходимо программировать новое устройство.
Многократно программируемые ПЛИС со стиранием и записью конфигурации в специальных режимах. Информация в элементах памяти таких схем может стираться с помощью облучения кристалла ультрафиолетовыми лучами, после чего кристалл можно заново запрограммировать. Такие ПЛИС обладают очевидным преимуществом перед однократно программируемыми схемами, однако у них имеются и недостатки, например, относительно долгое время стирания памяти (порядка десятков минут). Еще одним недостатком таких схем, ввиду того, что ультрафиолетовое облучение со временем изменяет свойства кристалла, является ограничение числа циклов репрограммирования порядком десятков сотен. Другим способом стирания элемента памяти является стирание электрическими сигналами. При таком способе не требуется извлечения микросхем из устройства, а число циклов репрограммирования составляет 105-106.
Оперативно перепрограммируемые ПЛИС. Это устройства, базирующиеся на флэш-памяти и SRAM. Их легко перепрограммировать, при этом стирание старой конфигурации и запись новой может производиться практически неогра 28 ниченное число раз. При использовании энергозависимой памяти типа SRAM конфигурация ПЛИС хранится во внутреннем ОЗУ и загружается в виде файла конфигурации из внешней памяти с высокой скоростью последовательным потоком байт. Очевидным недостатком является энергозависимость, требующая повторной загрузки конфигурации после каждого отключения питания. При использовании перепрограммируемой энергонезависимой флэш-памяти достаточно загрузить однократно программу конфигурации, которая будет далее управлять устройством.
Динамически перепрограммируемые ПЛИС. Это ПЛИС, в которых скомбинированы технологии хранения файлов конфигурации: флэш-память и память типа SRAM. «Линии управления поддерживают загрузку программ во флэш-память в фоновом режиме через JTAG-порт или выделенный порт конфигурации, затем в выбранный момент времени фиксируются выходы, приостанавливается работа ПЛИС, обновляется содержимое SRAM из флэш-памяти, и управление возвращается к пользовательской логике» [1]. При этом несколько файлов конфигурации могут быть заранее загружены во флэш-память. Благодаря такому подходу становится возможной динамическая реконфигурация ПЛИС в «полевых» условиях. Недостатком таких ПЛИС является ограниченное количество файлов конфигурации, которое может хранить встроенная флэш или PROM память. Некоторые ПЛИС данной категории могут поддерживать частичное статическое и динамическое реконфигурирование. Частичное реконфигурирование – это изменение конфигурации части схемы. При частичном статическом реконфигурирова-нии приостанавливается работа всей схемы. При частичном динамическом ре-конфигурировании приостанавливается лишь та ее часть, которой требуется новая конфигурация, при этом остальные части схемы могут продолжать функционировать. Основные отличительные особенности ПЛИС различной архитектуры представлены в таблице 1.1.
Таким образом, главным преимуществом чипов FPGA является их «пере-программируемость»: в любой момент чип может быть перепрограммирован, например, чтобы эффективнее работать в текущих условиях [137] или для нейтра 29 лизации возникшей ошибки. Следовательно, именно динамически репрограмми-руемые ПЛИС типа FPGA предоставляют больше всего возможностей для повышения надежности и отказоустойчивости построенных на их основе устройств. Однако, для того, чтобы воспользоваться этими возможностями, требуется разработка эффективных соответствующих методов диагностирования и реконфигурации.
Количество логических вентилей в FPGA с течением времени становится все больше и больше, что приводит к сложностям в производстве нетривиальных интегральных схем без дефектов. С другой стороны, со временем происходит деградация элементов схемы, что также может привести к возникновению ошибок в работе.
Деградация элементов FPGA может происходить вследствие различных процессов [99]. Например, электромиграция [84] (процесс переноса вещества в проводнике за счёт постепенного дрейфа ионов, приводящий к формированию нового непреднамеренного соединения); эффект «горячего носителя» [133] и температурная нестабильность при отрицательном смещении [10] (ведут к снижению скорости переключения и увеличению задержек), неустановившийся пробой диэлектрика [119] (увеличение тока утечки и создание короткого замыкания). Размеры интегральных схем имеют тенденцию к уменьшению, поэтому плотность 0 размещения элементов схем увеличивается. Значит, процесс деградации всё чаще будет становиться причиной отказов ПЛИС.
Помимо деградации причиной неполадок в работе ПЛИС могут стать дефекты производства, приводящие к константным отказам, коротким замыканиям или обрывам. Модель константных неисправностей предполагает, что линия или узел в цепи устанавливается в фиксированное значение логической единицы («за-липание 1») или логического нуля («залипание 0»). Первая ситуация соответствует физическому дефекту, когда линия связана с узлом питания, вторая – с землей. Модель неисправностей типа замыканий (bridge fault) предполагает электрическое соединение между двумя сетями сигналов, которые не должны быть связаны по проекту. Эти неисправности делятся на две группы: внешние и внутренние замыкания. Замыкания между любыми входами и выходами логических вентилей считаются внешними, остальные – внутренними.
Наконец, ошибки в работе ПЛИС могут возникнуть вследствие действия радиации (в таких областях, как ядерные исследования или работа в космосе). Большая мгновенная доза радиации может вызвать импульс напряжения на шинах питания, что приведёт к случайному сбою переключения. Часто проблемы вызываются так называемыми случайными воздействиями, которые происходят, когда в интегральную схему попадают тяжёлые частицы. Случайное воздействие может привести к одиночным сбоям. Обычно такие события происходят в ячейках памяти или триггерах при попадании в них ионов. Возникший при этом импульс тока переводит ячейку или триггер в противоположное состояние.
Обычно предполагается, что в случае отказа какого-либо элемента схемы соответствующий логический блок становится полностью неработоспособным, и выполняется поиск новой конфигурации, не использующей отказавший элемент. Однако, в случае невозможности построения такой конфигурации (например, в силу недостаточного количества оставшихся резервных блоков) необходим запасной вариант работы. Таким вариантом будет работа в рамках модели частичных отказов логических элементов.
Общие техники усовершенствования ГА
Таким образом, зная/?(ґ) и F, можно легко найти s(t) и наоборот. Используя данные определения, Вос и Липинс пытаются определить единственный «оператор» G такой, что применение G к s(f) будет точно соответствовать эффекту от одной итерации ГА: +l)=Gs0 (2.5) Тогда итерационное применение оператора G, начиная с s(0), даст точное описание работы ГА. Предположим, что ГА использует только селекцию (без кроссовера и мутации). Пусть Е(х) обозначает ожидаемую долю строки х. Тогда, поскольку s,{t) равно вероятности выбора строки /-го типа на каждом шаге селекции, F$t+l))= dt) (2.6) Пусть запись x у обозначает пропорциональность. Тогда из уравнения (2.4) имеем ЗИМИН (2.7) что ведет к следующему соотношению
Получаем искомое отношение (аналогичное виду уравнения (2.5)), из которого следует, что G=F в случае использования только селекции. Для учета кроссовера и мутации определим G как композицию матрицы приспособленности F и «оператора рекомбинации» Г7, который соответствует эффекту от применения кроссовера и мутации. Один из способов определить Г -найти rtJ(k) - вероятность получить к-ю строку в результате рекомбинации строк / иу. Если rit(k) известно, то мы можем вычислить
Определить rtj(k) и Г довольно непросто. Вос и Липинс сначала определяют более простую матрицу М, элементы которой 7Ц/ равны вероятности Гу(0), то есть, что рекомбинация строк / и у даст строку 0 (строку, содержащую одни нули). После того, как элементы Гу(0) определены, они могут быть использованы для рассмотрения общего случая.
Выражение для гг,у(0) равно сумме двух произведений: вероятности, что кроссовер между строками / и у не случится, а выбранный потомок (строка / или у) мутирует до строки 0 и вероятности, что кроссовер случится и выбранный потомок мутирует до строки 0.
Пусть вероятность применения кроссовера равна рс, а вероятность мутации каждого бита выбранного потомка равнарт. Если / - количество единичных разрядов в строке / длины /, то вероятность, что строка / мутирует до нулевой, есть вероятность, что все / единиц в строке мутируют, а ни один из (/-/) нулевых разрядов не изменится: Множитель отражает равную вероятность выживания каждого из потомков. Для определения второго слагаемого, будем считать, что кик обозначают потомков, полученных в результате применения кроссовера с разрывом в точке с (считая с правого края строки). Заметим, что всего существует /–1 возможная точка разрыва, поэтому вероятность выбора точки с равна 1/(/–1).
еперь можно записать окончательное выражение для ггу(0). Для упрощения записи введем обозначение Т]=рт/{1-рт). Тогда после ряда выкладок получим: Данное выражение отражает суть того, каким образом проведен анализ. Рационально используя логические операторы и перестановки, Вос и Липинс смогли выразить общий оператор рекомбинации Г через М. Пусть $k)=Frfk) для векторов х. Тогда в пределе для бесконечно большой популяции G )J s(f+1) и для начальной популяции бесконечно большого размера оператор G может быть выражен через оператор Г.
Рассматривая G как оператор, задающий динамическую систему, Вос и Липинс сформировали геометрическую картину поведения ГА и затем использовали ее, чтобы доказать некоторые свойства этого поведения. Геометрия картины в том, что набор всех возможных векторов s(f) образует поверхность S, на которой оператор G определяет перемещение от точки к точке. Исходной точкой является s(0), а итерационное применение G, начиная с этой точки, задает траекторию на S. Анализируя динамику G, прежде всего, необходимо определить точки равновесия для G на S, т.е. такой набор s(f), для которого G ))= ). Другими словами, точки равновесия обладают тем свойством, что если ГА окажется в них, то он «не уйдет» оттуда.
Эта задача в ее общей постановке не была решена Восом и Липинсом. Они решили отдельные проблемы нахождения неподвижных точек для F и Г и проанализировали их свойства. Так, точки равновесия для F (для одной только селекции) соответствуют популяциям, в которых строки сошлись к строкам с равной приспособленностью. Вос и Липинс доказали, что стабильным является только один класс таких точек, включающий точки, соответствующие популяциям строк с максимальной приспособленностью. Другими словами, если в популяции не все строки имеют максимальную приспособленность, то небольшое изменение в распределении приспособленности может привести к «уходу» из текущей фиксированной точки. Но если приспособленность по всей популяции максимальна, то в случае любого достаточно малого изменения в распределении приспособленности ГА снова окажется в этой фиксированной точке.
Вос и Липинс также показали, что в случае применения только оператора Г над s(i), существует единственная равновесная точка - вектор s(i), компоненты которого соответствуют популяции, содержащей с равными вероятностями все строки из пространства поиска. Аналогично, применяя оператор Г над P, получается только одна точка равновесия, в которой все возможные строки присутствуют в популяции с равными долями. Это значит, что в пределе для популяции бесконечного размера использование без селекции только кроссовера и мутации приводит к максимально «перемешанной» популяции, содержащей одинаковое количество всех возможных строк.
Обоснование сходимости генетического алгоритма к точному решению
Определим, какие отказы могут быть применены к элементам схемы. Анализируя возможные частичные отказы (параграф 2.2), можно заметить, что на логическом уровне все отказы LUT элемента равнозначны: в любом случае элемент позволяет реализовать функцию 3-х переменных. Для ФПТ элементов возможно два принципиально различных случая: либо состояние S1-S4 (элемент реализует функцию вида За v3e3&), либо S5-Sz (реализует стрелку Пирса). Необходимо сформировать множество уникальных комбинаций отказов, после чего провести реконфигурацию для каждой из сгенерированных комбинаций. Оценим количество таких комбинаций.
Пусть в схеме имеется к частично отказавших элементов. Тогда для схемы на базе LUT элементов имеем одну комбинацию (все к отказавших элементов равноценны), а для схемы на базе ФПТ элементов - (к+\) комбинацию (количество элементов в состоянии Si-S4 изменяется от 0 до к, остальные находятся в состоянии Ss-Sg). Пусть в схеме допускается наличие не более Ктах частично отказавших элементов. Если схема построена в базисе LUT-элементов, то получаем Ктах возможных комбинаций - по одной на каждое значение. Если схема реализована в базисе ФПТ элементов, то получаем количество возможных комбинаций: 8
На вход программы поступает описание схемы на языке VHDL (рисунок 3.7). Во время обработки входного описания строится граф передачи сигналов от одной сущности другой. После того, как граф построен, происходит валидация всех полученных сущностей, в ходе которой для каждой сущности строятся таблица истинности и обобщенная таблица истинности, на основе которых определяются таблица истинности и обобщенная таблица истинности анализируемой схемы. Для построения обобщенной таблицы истинности производится минимизация функции по алгоритму Куйна - Мак-Класки.
Далее происходит формирование возможных отказов. Поскольку ФПТ элементы и LUT элементы поддерживают разные типы отказов, была разработана иерархия классов, описывающих ошибку логического элемента. Базовый класс JUSchemeError позволяет получить описание ошибки в текстовом виде (для отображения пользователю), а также хранит информацию о типе элемента, для которого предназначена ошибка.
От класса JUSchemeError наследуются классы, непосредственно описывающие ошибку для каждого базиса: JUSchemeErrorLUT и JUSchemeErrorUBS. Поскольку механизмы генерации множества возможных отказов для каждого из ба 11 9 зисов совпадают, класс JUReconfigurator имеет метод generateErrors, который возвращает множество отказов, описывающихся классом JUSchemeError. Список сгенерированных видов отказов отображается в нижней части главного окна (рисунок 3.7).
Когда пользователь выбрал интересующий его вид отказа, конфигуратор на основе того, в базисе каких элементов ведётся работа, запускает нужный процесс реконфигурации. Результатом будет либо сообщение о том, что схема не может быть реконфигурирована для данного отказа, либо окно, в котором будут выведены VHDL-описание новой конфигурации схемы, а также графическая интерпретация построенной конфигурации (рисунок 3.8). Крестом на изображении схемы отмечаются входные порты, вышедшие из строя.
1. Первой подзадачей, возникающей при реконфигурации ПЛИС, является поиск компактного множества работоспособных элементов. Подзадача может быть формализована следующим образом: для заданной матрицы состояний, полученной по результатам диагностирования, и необходимого количества элемен 12 0 тов N найти такой минимальный набор покрывающих прямоугольников, чтобы их суммарная площадь была не меньше N. Указанная задача является NP-трудной, точное решение за приемлемое время найти невозможно, поэтому необходимо применять приближенные алгоритмы.
2. Предложен базовый приближенный алгоритм решения первой подзадачи. Качество находимых им решений зависит от порядка просмотра элементов матрицы состояний. На основе базового приближенного алгоритма разработан генетический алгоритм. Его отличительной особенностью является оригинальное двухуровневое кодирование решений. Первый уровень кодирования является традиционным и представляет решение задачи в виде перестановки на множестве натуральных чисел. Перестановка определяет порядок просмотра элементов при запуске базового алгоритма. Дополнительный второй уровень кодирует перестановку в виде целочисленной матрицы, элементы которой, в отличие от элементов перестановки, являются независимыми. Благодаря независимости элементов становится возможным использование стандартных генетических операторов (скрещивания, мутации).
3. Строгое формальное доказательство сходимости генетического алгоритма к точному решению получить невозможно. Тем не менее, получено доказательство всех свойств используемой функции приспособленности, требуемых классической моделью ГА, что в совокупности с использованием стандартных генетических операторов позволяет опираться на существующие теоретические и экспериментальные подтверждения эффективности ГА.
4. Генетический алгоритм решения первой подзадачи реализован в виде программной системы на языке семейства C. Программа может взаимодейство вать с ПЛИС двумя способами. Первый заключается в том, что программа запус кается на внешнем контроллере (таком, как стационарный компьютер) и ее ре зультаты загружаются на ПЛИС через интерфейс JTAG. Второй способ применим для моделей FPGA, включающих в себя аппаратное процессорное ядро IBM Pow erPC, на котором и выполняется программа. При этом реконфигурация выполня ется с использованием встроенного микроконтроллера через внутренний конфи 12 1 гурационный порт ICAP. Второй способ является наиболее гибким и эффективным, встроенный в FPGA процессор позволяет отказаться от необходимости подключения внешнего контроллера.
Разработанная программа позволяет также исследовать влияние параметров ГА на качество и скорость нахождения решения и подбирать оптимальные значения этих параметров.
5. Для решения второй подзадачи разработаны алгоритмы реконфигурации схем на ФПТ элементах и элементах LUT, учитывающие наличие частично работоспособных элементов. Поскольку алгоритмы реконфигурации возвращают в случае успеха реконфигурированную схему, можно считать, что также были реализованы алгоритмы синтеза комбинационных схем.
Разработанные алгоритмы реализованы в виде программы, позволяющей загрузить текущую схему в виде описания на языке VHDL, сгенерировать множество возможных отказов и построить новую конфигурационную схему в виде VHDL-описания и графического изображения для выбранного вида отказа.
Контроль дерева LUT путём использования второй половины дерева передающих транзисторов с дублированием настройки и инверторов переменных
Параметры ГА играют, пожалуй, самую важную роль в эффективности работы разработанного алгоритма. Удачный подбор параметров может существенно ускорить нахождение правильного решения, либо, в случае, когда точное решение не может быть найдено, существенно повысить качество получаемого решения.
Параметры генетического алгоритма влияют друг на друга сложным образом. Для исследования их взаимодействия применяют различные подходы, в том числе экспериментальные исследования, цепи Маркова, функциональную декомпозицию взаимодействия параметров.
Следует заметить, что в общем виде, для произвольной задачи, указать наилучшие значения параметров проблематично. Например, относительно веро 15 5 ятности мутации (рассматриваемой как вероятность мутации каждого бита (гена) хромосомы при бинарном кодировании) в приводится значение рт=0.01, в [129] приводится диапазон ртє[0.005,0.01]. Последний результат был также сформулирован в виде эмпирического выражения: Рт Ж (51) где X - размер популяции, а / - длина хромосомы. Выражение (5.1) схоже с выражением, полученным в работе [107]: і t) р =ё ям, (5.2) где сс,Р,у - некоторые константы. В выражении (5.2), как видно, присутствует зависимость от времени. Вообще, возможность зависимости параметров разное время различные исследователи давали различные рекомендации. Так, в [106] от времени отмечалась еще Дж. Холландом в его первых работах, а также и другими исследователями. Во всех известных работах предлагается уменьшение вероятности мутации со временем.
В [80] рассматривается генетический алгоритм, в котором с ходом эволюции изменяется и адаптивно настраивается вероятность мутации. Следует заметить, что, несмотря на положительные, в целом, результаты, самоадаптация мутации может привести к преждевременной сходимости [128]. В работе [45] замечено, что для многоэкстремальных функций использование адаптивной мутации дает лучшие результаты.
Более универсальный подход представлен в работе [103], где в генотипе особи закодированы вероятности применения сразу для нескольких операторов. В каждом поколении каждая особь модифицируется только одним оператором, который выбирается исходя из содержащихся в особи вероятностей. Вероятности пересчитываются на основе некоторого закона, пропорционально разнице при-способленностей потомков и родителей. Еще одним универсальным подходом яв 15 6 ляется использование мета-генетического алгоритма для определения параметров [13].
Таким образом, общая теоретическая рекомендация может быть только такой: вероятность мутации должна быть малой величиной, а вероятность унаследования генов от одного из родителей, наоборот, должна быть величиной, близкой к 1/2. Количество поколений может быть выбрано исходя из имеющихся временных ресурсов, если они ограничены. Если единственным условием окончания работы алгоритма является количество поколений, то оно должно быть достаточно большим. Также важна численность начальной популяции, так как в большинстве генетических алгоритмов численность популяции остается неизменной и всегда равна к. Следует отметить, что численность популяции существенным образом влияет на объем вычислений, и, следовательно, на затрачиваемое время.
Скрещивание позволяет смешивать «строительные блоки», объединяя лучшие и худшие характеристики предков. Использование мутации способно разрушить имеющиеся перспективные блоки и их хорошие комбинации, поэтому рационально использовать ГА с высокой вероятностью скрещивания и низкой вероятностью мутации.
Слишком малые размеры популяции приводят к быстрой преждевременной сходимости. Увеличение размера популяции выше определенного предела не имеет положительного эффекта, поэтому слишком большие размеры популяции также использовать нецелесообразно. ГА с кроссовером и мутацией работают на простых функциях лучше, чем варианты ГА только с одним из операторов. 7
Для получения хороших результатов необходимо выбрать правильный размер популяции. Если в алгоритме не используется мутация, можно построить оценку оптимального числа особей; если мутация применяется, таких оценок построить нельзя. Однако результаты экспериментов показывают, что оптимальный размер популяции для ГА с мутацией существует. В любом случае, размер популяции зависит от конкретной решаемой задачи.
В целом можно сказать, что ГА с кроссовером с правильно выбранным размером популяции надежнее, чем ГА с мутацией.
Для оператора селекции имеет значение только приспособленность особей, поэтому будем рассматривать только значения фитнесс-функции, а не сами особи. Очевидно, на конечном наборе возможных решений, фитнесс-функция может принимать конечный набор различных значений fx f,…JnJ R. Функцию s:RZ", которая каждому значению f фитнесс-функции ставит в соответствие количество особей в популяции Р, которые имеют значение функции приспособленности, равное/ называют распределением приспособленности популяции Р. Таким образом, оператор селекции можно представить как функцию, преобразующую одно распределение приспособленности в другое распределение. Получаем еще одно определение: метод селекции Q - это функция, которая преобразует распределение приспособленности s в новое распределение приспособленности s : s =0s,par_list s (5 3) где par list - список параметров оператора выбора.