Методы и алгоритмы диагностирования и реконфигурации логики высоконадежных ПЛИС тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Городилов Алексей Юрьевич

• Городилов Алексей Юрьевич
• кандидат наук
• 2016

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

Введение

Глава 1. Анализ существующих методов повышения отказоустойчивости ПЛИС типа FPGA и постановка задачи исследования

1.1. Анализ объекта исследования - ПЛИС

1.2. Причины и виды отказов

1.3. Существующие алгоритмы, методы и средства диагностирования и реконфигурации логики ПЛИС типа БРОЛ

1.3.1. Методы диагностирования

1.3.2. Методы реконфигурации

1.4. Постановка задачи исследования

Выводы по главе

Глава 2. Генетический алгоритм диагностирования ПЛИС

2.1. Генетические алгоритмы как универсальный метод решения задач оптимизации и поиска

2.1.1. Базовые понятия генетических алгоритмов

2.1.2. Общие техники усовершенствования ГА

2.1.3. Применение ГА в решении различных задач

2.2. Построение модели частичных отказов логических элементов ПЛИС

2.2.1. Частичные отказы ФПТ элементов

2.2.2. Частичные отказы ШГ-элементов

2.3. Математическая модель генетических алгоритмов

2.3.1. Шаблоны и теорема шаблонов

2.3.2. Подходы на основе теории вероятности и математической статистики

2.3.3. Модель Воса и Липинса

2.4. Разработка генетического алгоритма диагностирования ПЛИС

2.5. Выводы по главе

Глава 3. Генетический алгоритм реконфигурации ПЛИС

3.1. Разработка генетического алгоритма поиска компактного множества работоспособных элементов

3.1.1. Формализация задачи

3.1.2. Базовый приближенный алгоритм

3.1.3. Генетический алгоритм

3.2. Обоснование сходимости генетического алгоритма к точному решению

3.3. Разработка программы поиска компактного множества работоспособных элементов

3.3.1. Используемые инструментальные средства и технологии

3.3.2. Структура программной системы

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

3.4.1. Реконфигурация схемы на LUT-элементах

3.4.2. Реконфигурация схемы на ФПТ элементах

3.4.3. Формирование возможных отказов схемы

3.4.4. Программная реализация

3.5. Выводы по главе

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

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

4.2. Тестовый контроль LUT путём использования второй половины дерева передающих транзисторов

4.3. Контроль дерева LUT путём использования второй половины дерева передающих транзисторов с дублированием настройки

4.4. Контроль дерева LUT путём использования второй половины дерева передающих транзисторов с дублированием настройки и инверторов переменных

4.5. «Обратное» диагностирование логического элемента LUT

4.6. Моделирование предложенных методов контроля логических элементов LUT

4.7. Выводы по главе

Глава 5. Оценка эффективности предложенных алгоритмов и методов

5.1. Параметры генетического алгоритма

5.2. Оценка эффективности двухуровневого кодирования

5.3. Оценка эффективности «обратного» диагностирования LUT

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

5.5. Выводы по главе

Заключение

Список использованных источников

Приложение А. Акты о внедрении

А.1. Акт об использовании результатов работы в учебном процессе ПГНИУ

А.2. Акт о внедрении результатов работы в ОАО «Морион»

А.3. Справка о личном вкладе в НИОКР

Приложение Б. Листинги программ

Б.1. Программа построения диагностической последовательности

Б.1.1 Реализация генетических операторов

Б.1.2 Параметры генетического алгоритма

Б.2. Модули генерации файлов конфигурации и тестирования

Б.3. Программа поиска компактного множества работоспособных элементов

Б.3.1 Реализация генетического алгоритма

Б.3.2 Основная программа

Приложение В. Сгенерированный файл тестирования для схемы из трех ФПТ-элементов

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы диагностирования и реконфигурации логики высоконадежных ПЛИС»

ВВЕДЕНИЕ

Актуальность темы исследования. Интенсивное развитие и совершенствование цифровых устройств приводит к их активному применению в различных областях науки и техники, в том числе в цифровой обработке сигналов, передаче данных, системах хранения, а также в системах специального назначения. Отдельно стоит отметить системы управления, применяемые в аэрокосмической отрасли, в авиации, в военной технике (например, в качестве цифровой наземной и бортовой аппаратуры), в управлении атомными электростанциями, в медицине и других отраслях. Нарушение функционирования таких критических систем управления может причинить значительный экономический или экологический ущерб, нести угрозу здоровью или жизни людей, а иногда даже привести к катастрофическим последствиям. Поэтому проектирование надёжных, безопасных систем является одной из ключевых проблем современной науки и инженерной практики. Важность названных проблем для нашей страны подтверждается тем, что технологии информационных, управляющих, навигационных систем, а также технологии создания электронной компонентной базы включены в перечень критических технологий Российской Федерации, утвержденный соответствующим указом Президента РФ [64].

Международная терминология в области высоконадежных систем включает следующие понятия и термины: устойчивые к отказам (fault-tolerant) и эластичные к отказам (fault-resilient) системы; естественно надёжные (naturally reliable), естественно гарантоспособные (naturally dependable); отказобезопасные (fault-safe), естественно безопасные (naturally safe) системы; системы высокой готовности (high availability) и высокой живучести (high survivability); самовосстанавливающиеся (self-recovery), самоизлечивающиеся (self-healing) и другие системы [139]. Для более сложных систем и инфраструктур, кроме того, получили развитие идеи, связанные с устойчивостью к катастрофам (disaster tolerance) и восстанавливаемостью при катастрофах (disaster recovery) [139].

Отказоустойчивые, надежные системы управления должны обладать высокой устойчивостью к отказам в различных условиях внешней окружающей среды: температуры, давления, влажности, вибрации, в условиях вакуума, невесомости, а также повышенной радиации, что особенно актуально для космической отрасли. Для обеспечения требуемых характеристик надежности при проектировании таких систем используется специальная элементная база, создание которой часто требует применения специальных материалов и технологий, например, кремний на сапфире (КНС) или использование арсенида галлия [7, 113, 71]. Для радиаци-онно-стойких приборов применяют antifuse-перемычки (например, фирма Microsemi), используют обратную связь для защиты ячеек памяти (фирма IBM), применяют другие технологии, например, увеличивают толщину диэлектрика [50]. Названные специальные технологии усложняют процесс производства и значительно увеличивают стоимость оборудования. Кроме того, использование, например, арсенида галлия существенно уменьшает степень интеграции микросхем.

В качестве элементной базы систем управления в настоящее время помимо универсальных процессоров, микроконтроллеров и заказных больших интегральных схем (БИС) широко применяется программируемая логика: базовые матричные кристаллы (БМК), программируемые логические матрицы (ПЛМ), программируемые матрицы логики (ПМЛ), программируемые логические интегральные схемы (ПЛИС) и, в частности, программируемые пользователем вентильные матрицы (ППВМ, англ. Field-Programmable Gate Array, FPGA), а также программируемые аналоговые интегральные схемы (ПАИС) и системы на кристалле (System on Chip, SoC) [113].

Федеральная целевая программа «Развитие электронной компонентной базы», соответствующие Указы Президента РФ и постановления правительства РФ подчеркивают необходимость создания отечественной электронной компонентной базы, что имеет важнейшее значение для развития отечественной промышленности и обороноспособности России. В настоящее время серьезные успехи достигнуты в области создания отечественных БМК для аппаратуры специального назначения [11], вопросам разработки самосинхронных схем на БМК посвящены

работы Ю.А. Степченкова, Ю.Г. Дьяченко и других [46]. БМК является универсальной заготовкой для полузаказных интегральных схем, и специализируется технологически путем формирования слоев металлизации. Основным преимуществом БМК является отсутствие избыточных элементов программирования схемы, что существенно снижает сложность микросхемы и, тем самым, повышает ее надежность. Однако, если в процессе функционирования отказ все же произошел, возможность оперативного удаленного восстановления работоспособности схемы, построенной на основе БМК, отсутствует, так как логика их работы не может быть динамически перепрограммирована.

В современной цифровой аппаратуре систем управления и вычислительной техники, в аппаратуре специального назначения, в том числе военной, широко используются ППВМ как одна из разновидностей ПЛИС [148]. Их особенностью является то, что логика работы задается путем программирования, то есть может быть оперативно изменена прямо во время использования устройства. Такая особенность приводит не только к возможности гибкой настройки схемы для конкретной решаемой задачи за короткий срок, но и к возможности восстановления работоспособности после отказа путем реконфигурации. В случае отказа логического элемента расположение логических блоков на схеме может быть изменено так, что вместо отказавшего элемента будет задействован резервный. На настоящий момент лидерами в производстве ПЛИС типа FPGA являются иностранные компании (Xilinx, Altera, Lattice Semiconductor, Microsemi, Atmel и другие). Таким образом, актуальной является практическая задача разработки отечественных ПЛИС для критических, высоконадежных применений.

Поэтому объектом исследования являются программируемые пользователем вентильные матрицы (ПЛИС типа FPGA). Данным классом микросхем наиболее насыщен рынок. Согласно оценкам аналитиков, в последние годы объем их продаж показывает среднегодовые темпы роста более 15%. FPGA имеют низкую стоимость, высокое быстродействие и удобны в применении.

Степень разработанности темы исследования. Одним из важнейших этапов обеспечения надежности является контроль и диагностика. Основные прин-

ципы контроля и диагностики цифровой аппаратуры были заложены Р. Хэммин-гом, А. Авиженисом, П.П. Пархоменко, Е.С. Согомоняном, Ф. Селлерсом и др. [79, 34, 40]. Особенности диагностирования современных цифровых схем, в том числе ПЛИС, рассматривались в работах Е. Зориана, В.С. Харченко, В.И. Хахано-ва, М.Ф. Каравая, А.Л. Переверзева, В.В. Слюсаря, Р.М. Романова, Г.П. Аксеновой, Е.Л. Кона, О.В. Гончаровского, В.И. Фреймана и других [3, 4, 25, 26, 140, 35, 42, 65, 14, 66, 29].

Одним из основных трендов фирм-производителей FPGA является введение блоков встроенной диагностики для доступа к любому элементу без затрат трассировочных ресурсов схемы [66]. Активно применяется метод DFT (Design For Test - тестопригодное проектирование). Стандарт IEEE 1149.1 (граничное сканирование JTAG) [109] дополнен стандартом IEEE 1500 (тестопригодное проектирование систем на кристалле) [110]. Многие исследователи подчёркивают особое место логики ПЛИС, которая занимает всё меньшую площадь кристалла ПЛИС по сравнению с конфигурационной памятью и средствами трассировки, но без неё невозможно обеспечение надёжности. К тому же, и диагностика и реконфигурация логики ПЛИС существенно более сложны.

В работах С.Ф. Тюрина, А.В. Грекова, О.А. Громова предложены методы и средства повышения отказоустойчивости логики FPGA на основе функционально-полных толерантных элементов (ФПТЭ), сохраняющих либо логический базис, либо саму исходную функцию при отказах [18, 19, 57, 60]. Предложены соответствующие отказоустойчивые транзисторные структуры. Показано, что использование ФПТЭ позволяет повысить вероятность безотказной работы и коэффициент готовности как мелкозернистых ПЛИС (в которых логические элементы представляют собой набор простых логических вентилей), так и крупнозернистых ПЛИС типа FPGA (в которых используются таблицы поиска (Look-Up Table, LUT)). Однако вопросы контроля и диагностики схем на основе ФПТЭ до сих пор рассмотрены не в полной мере, а эффективность алгоритмов диагностики и реконфигурации логики FPGA исследована недостаточно. Это сдерживает развитие научно-методического аппарата проектирования FPGA на основе ФПТЭ для спе-

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

Сложность схем и количество используемых в них элементов постоянно возрастают, в настоящее время количество транзисторов в FPGA превысило миллиард, а количество логических элементов (ЛЭ) преодолевает миллионные рубежи. В связи с этим в области проектирования ПЛИС актуальными являются научные подходы, в том числе на основе эвристик, для нахождения оптимальных и квазиоптимальных решений за приемлемое время. В последнее время активно развивается подход к решению задач диагностирования и реконфигурации ПЛИС на основе генетических алгоритмов (работы Д.Е. Иванова, Ю.А. Скобцова, Дж. Холма, Е. Рудник, Д. Сааб) [22, 41, 127].

Генетический алгоритм (ГА) представляет собой универсальный адаптивный поисковый метод, основанный на моделировании естественных эволюционных процессов для эффективного решения оптимизационных задач. Обзор литературы позволяет утверждать, что ГА успешно используются для решения различных комбинаторных задач науки и техники. На эффективность ГА существенное влияние оказывает правильный выбор способа кодирования особей и параметров алгоритма. Также нужно отметить, что теоретическое обоснование корректности работы ГА в виде строгих математических моделей получено только для стандартного классического ГА [117]. Поэтому при разработке ГА диагностирования и реконфигурации ПЛИС необходимо первоочередное внимание уделить выбору способа кодирования, который бы позволил применять стандартные генетические операторы.

Объектом исследования являются программируемые пользователем вентильные матрицы (ПЛИС типа FPGA).

Предметом исследования являются методы, алгоритмы и средства обеспечения надёжности, контроля и диагностики функционирования ПЛИС типа FPGA.

Цель работы - совершенствование научно-методического аппарата диагностирования и реконфигурации логики ПЛИС типа FPGA, в том числе построенной с использованием ФПТЭ.

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

1. Разработка ГА диагностирования логики ПЛИС типа FPGA, учитывающего использование ФПТЭ в составе логических ячеек и минимизирующего время обнаружения отказа.

2. Разработка ГА реконфигурации логики ПЛИС типа FPGA, учитывающего использование ФПТЭ в составе логических ячеек и максимизирующего вероятность успешного восстановления после отказа.

3. Разработка модифицированного метода рабочего контроля логического элемента LUT.

4. Разработка модифицированного метода тестового контроля логического элемента LUT.

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

Научная новизна результатов:

■ разработан модифицированный генетический алгоритм диагностирования ПЛИС типа FPGA на основе ФПТЭ, новизна которого заключается в использовании дополнительного внешнего цикла, позволяющего использовать стандартные генетические операторы и оптимизировать диагностическую последовательность по двум параметрам - длине последователь-

ности и количеству отказов, которые эта последовательность позволяет обнаружить;

■ разработан модифицированный генетический алгоритм реконфигурации ПЛИС типа FPGA на основе ФПТЭ, отличающийся оригинальным двухуровневым способом кодирования решений, позволяющим использовать стандартные генетические операторы, благодаря чему увеличивается вероятность получения приемлемого решения, а также учитывается возможность использования частично отказавших элементов;

■ доказана теорема о сходимости предложенного генетического алгоритма реконфигурации ПЛИС типа FPGA к точному оптимальному решению;

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

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

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

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

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

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

Основные положения, выносимые на защиту:

■ алгоритм диагностирования логики ПЛИС типа FPGA на основе ФПТЭ;

■ алгоритм реконфигурации логики ПЛИС типа FPGA на основе ФПТЭ;

■ модифицированный метод рабочего контроля LUT FPGA;

■ модифицированный метод тестового контроля LUT FPGA;

■ оценки сложности и эффективности новых алгоритмов и технических решений реализации LUT FPGA с контролем.

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

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

бораторных работ по дисциплине «Алгоритмы и анализ сложности» реализованный ГА диагностирования был применен к ПЛИС Cyclone IV E фирмы Altera. Акты об указанных внедрениях результатов работы приведены в приложении А.

Апробация результатов работы. Основные теоретические и прикладные результаты диссертационной работы были представлены и одобрены на научно-технических конференциях: 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 научных статьях, из них одна в изданиях, индексируемых Scopus, и 6 в других рецензируемых научных изданиях, включенных в Перечень ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников, включающего 149 наименований, и 3-х приложений. Основная часть работы изложена на 201 странице машинописного текста, содержит 68 рисунков и 16 таблиц. Приложения включают в себя акты внедрения результатов работы, листинги разработанных программ диагностирования и реконфигурации, а также листинг автоматически сгенерированного файла тестирования.

В первой главе выполнен анализ объекта исследования - ПЛИС типа FPGA. Рассмотрены различные причины и виды отказов логических элементов. Выполнен обзор существующих методов повышения отказоустойчивости логики FPGA. Отмечается недостаточное использование широких возможностей FPGA для по-

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

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

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

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

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

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

Второй этап заключается в построении работоспособной конфигурации, использующей выбранные на первом этапе логические элементы. При этом если полностью работоспособных элементов осталось недостаточно для реализации логики, задействуются частично отказавшие элементы с учетом их оставшихся функциональных возможностей. Разработанный алгоритм формирует список возможных отказов на основе структуры логических элементов ПЛИС, а затем осуществляет поиск работоспособной конфигурации для выбранных отказов. Такой подход позволяет заранее сформировать множество схем, чтобы в дальнейшем сразу после определения отказа в результате диагностирования выполнить загрузку новой схемы, не расходуя время на поиск оптимальной конфигурации. За счет этого уменьшается общее время реконфигурации. Реализован демонстрационный прототип, позволяющий задавать исходное описание схемы на языке VHDL (Very high speed integrated circuits Hardware Description Language, язык описания аппаратуры высокоскоростных интегральных схем), анализировать и проверять пра-

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

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

Выполнена оценка избыточности для LUT на n переменных с учётом и без учёта конфигурационной памяти (SRAM). Получены выражения для достоверности предлагаемого усовершенствованного метода контроля. Сравнение достоверности функционирования LUT без контроля и достоверности предлагаемого метода показывает эффективность последнего. Предложенная модификация позволяет уменьшить время диагностирования логики, затрачивая его только на поиск работоспособной половины дерева транзисторов в проблемных LUT. Также в данной главе исследованы варианты, когда выполняется дублирование настройки и дублирование инверторов входных переменных.

В модифицированном методе тестового контроля введена быстрая обратная активация всех ветвей дерева передающих транзисторов LUT. Если отключить конфигурационную память SRAM, подать диагностический сигнал c(z) на выход LUT, и считывать сигналы d ' на «входах», будет выполнен реверс дерева передающих транзисторов. При определенном наборе значений входных переменных можно проверить равенство 4 '=c(z), протестировав тем самым соответствующую цепочку в дереве передающих транзисторов. Определены условия, при которых можно выполнить одновременную проверку всех транзисторов во всех группах передающих транзисторов. Выполнена оценка избыточности LUT для «быстрого» диагностирования для различных значений числа входных переменных n. Показано, что предлагаемый модифицированный метод тестового диагностирования

позволяет строить тесты линейной сложности. Так, при размерности LUT n=5 получается более чем двукратный выигрыш во времени.

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Абакумов, Р.С., Куприянов, М.С., Писаревский, А.С. МЕТОДЫ РЕКОНФИГУРАЦИИ FPGA-СТРУКТУР [Электронный ресурс]. - 2015. - Режим доступа: http://www.eltech.ru/assets/files/university/izdatelstvo/izvestiya-spbgetu-leti/2005-14.pdf.

2. Айнутдинов, В. А. Автоматизация процессов составления расписания и распределения ресурсов при оперативном управлении производством [Электронный ресурс]. - 2015. - Режим доступа: http://ecsocman.edu.ru/db/msg/61013.html.

3. Аксенова, Г.П. Метод параллельно-последовательного самотестирования в интегральных схемах типа БРОЛ / Г.П. Аксенова, В.Ф. Халчев // Автоматика и телемеханика. - 2007. - №1. - С.163-174.

4. Аксенова, Г.П. Самотестирование «системы-на-кристалле», реализованной в ПЛИС / Г.П. Аксенова // Технические и программные средства систем управления, контроля и измерения: матер. конференции. - М., 2010. - С.23-30.

5. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин - Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

6. Батищев, Д.И. Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин // Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006 г. Обнинск): труды конференции. В 3-т. Т.3. - 2006. - С.976-983.

7. Березин, А. Все грани сапфира. [Электронный ресурс]. - Режим доступа: http://m-mos.ru/2006/09_10/15.htm (дата обращения 21.02.2015)

8. Биоинспирированные методы в оптимизации / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик, П.В. Сороколетов. - М.: Физматлит, 2009. - 380 с.

9. Благодарный, Н.П. Самодиагностирование высокоинтегрированных цифровых систем реального времени. / Н.П. Благодарный, Д.С. Троненко // Рад^лектронш i комп'ютерш системи. - 2010. - № 7 (48). - С.166-169.

10. Гаврилов, С. В. Анализ деградации параметров транзисторов во времени на логическом уровне / С.В. Гаврилов, О.Н. Гудкова, А.Н. Щелоков // Известия ЮФУ. Технические науки. - 2011. - №7.

11. Гаврилов, С.В. Семейство серий базовых матричных кристаллов. / С.В. Гаврилов, А.Н. Денисов, В.В. Коняхин, Н.И. Малашевич, Р.А. Фёдоров // Известия вузов. Электроника. -2015. -Том 20, №6. - C. 497 - 504.

12. Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик; под ред. В.М. Курейчика. - М.:ФИЗМАТЛИТ, 2006.

13. Голубин, А.В. Определение параметров генетического алгоритма с помощью программного комплекса "GENSEARCH" / А.В. Голубин. // Перспективные информационные технологии и интеллектуальные системы. - 2004. - №3. -С.42-47.

14. Гончаровский, О.В. Проектирование диагностических и отладочных стендов при производстве аппаратуры связи. Тестовое диагностирование и контроле-пригодное проектирование цифровых устройств: Учеб. пособие / О.В. Гончаровский, Е.Л. Кон. - Пермь: Перм. гос. техн. ун-т. - Пермь. - 2005. -73 с.

15. Городилов, А.Ю. Генетический алгоритм диагностирования цифровых устройств [Электронный ресурс] / А.Ю. Городилов, С.Ф. Тюрин // Интернет-журнал «Науковедение». -2013. -№ 5 (18). - Режим доступа: http : //naukovedenie. ru/PDF/12tvn513.pdf.

16. Городилов, А.Ю. О сходимости генетического алгоритма реконфигурации ПЛИС типа FPGA / А.Ю. Городилов // В мире научных открытий. -2015. -№ 8 (68). -С. 43-51.

17. Городилов, А.Ю. Постановка задачи диагностирования программируемых логических интегральных схем и анализ возможности применения генетических алгоритмов для ее решения / А.Ю. Городилов // Фундаментальные исследования. -2013. -№10 (ч. 5). -С. 958-962.

18. Греков, А.В. Повышение отказоустойчивости конфигурируемых блоков программируемых логических интегральных схем на основе функционально пол-

ных толерантных элементов: диссертация на соискание учёной степени кандидата технических наук / А.В. Греков. - Пермь, 2011. - 167 с.

19. Громов, О.А. Методы и алгоритмы повышения отказоустойчивости программируемых логических интегральных схем на основе КМОП элементов с избыточным базисом [Электронный ресурс]. - 2015. - Режим доступа: http://www.dissercat.com/content/metody-i-algoritmy-povysheniya-otkazoustoichivosti-programmiruemykh-logicheskikh-integralnyk#ixzz3 SNj qsCH 1.

20. Еремеев, А.В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. / А.В. Еремеев, Л.А. Заозерская, А.А. Колоколов // Дискретный анализ и исследование операций. Сер.2. - 2000 - Т.7. №2. -С.22-46.

21. Ерошенко, И.Н. Применение библиотеки PPL в алгоритмах генетического поиска / И.Н. Ерошенко // Технологии Microsoft в теории и практике программирования: труды VII-ой Всероссийской конференции студентов, аспирантов и молодых ученых. - Таганрог: Изд-во ТТИ ЮФУ, 2010.

22. Иванов, Д.Е. Генетические алгоритмы построения входных идентифицирующих последовательностей цифровых устройств / Д.Е. Иванов - Донецк: ТОВ «Цифровая типограф1я», 2012. - 240 с.

23. Исследование методов повышения отказоустойчивости систем на плис / А.Б. Биньковская, В.М. Бутенко, М.А.Коваленко и др. // Iнформацiйно-керуючi системи на залiзничному транспорт^ - 2012. - №6. - С.70-73.

24. Казаков, П.В. Оптимизация многоэкстремальных функций на основе кластерной модификации генетического алгоритма / П.В. Казаков // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008 (29 сентября - 3 октября 2008 г., Дубна): труды конференции. - 2008.

25. Каравай, М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I / М.Ф. Каравай // Автоматика и телемеханика. - 2004. - №12. - С.174-189.

26. Каравай, М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II / М.Ф. Каравай // Автоматика и телемеханика. - 2005. - №2. - С. 175-189.

27. Каршенбойм, И. JTAG-тестирование / И. Каршенбойм // Современная электроника. - 2007. -№2. - С.58-66.

28. Каширина, И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида / И. Л. Каширина // Вестник ВГУ. - 2003. - №1.

29. Кон, Е.Л. Подходы к тестовому диагностированию цифровых устройств / Е.Л. Кон, В.И. Фрейман // Вестник пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. -2012. -№6. - С. 231 - 241.

30. Курейчик, В.М. Решение задачи покрытия на основе эволюционного моделирования / В.М. Курейчик, Б.К. Лебедев, О.Б. Лебедев // Теория и системы управления. - 2009. -№1. -С101-116.

31. Ложкин, С.А. Декомпозиция на основе универсальных систем функций и её применение при логическом и топологическом синтезе СБИС / С.А. Ложкин, А.Н. Готманов, Е.А. Попов, А.Е. Шиганов // Проблемы разработки перспективных микроэлектронных систем - 2005 (МЭС-2005). - М.: Изд-во ИППМ РАН М, 2005. - С.66-71.

32. Математические и компьютерные основы криптологии: Учеб. Пособие / Ю.С. Харин, В.И. Берник, Г.Е. Матвеев и др. - Минск: Новое знание, 2003.

33. Низамова, Г.Ф. Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов: автореф. / Г.Ф. Низамова. - УГАТУ, 2006.

34. Пархоменко, П.П. Основы технической диагностики / П.П. Пархоменко, Е.С. Согомонян - М.: Энергоиздат, 1981. - 321 с.

35. Переверзев, А.Л. Масштабируемый программный комплекс для тестирования, конфигурации и отладки устройств с помощью интерфейса JTAG / А.Л. Переверзев, Ю.В. Савченко, Д.В. Твердунов // Естественные и технические науки. - 2011. - № 3 (53). - С. 398-404.

36. ПЛИС Actel - основа при реализации "SoC" бортовой аппаратуры. [Электронный ресурс]. - 2013. - Режим доступа: http://www.iclothes.ru/State_3.html.

37. Попович, А. Перспективная платформа для построения бортовых вычислительно-управляющих систем / А. Попович // Компоненты и технологии. 2008. -№8. - С. 168-170.

38. Сапрунова, Е.А. Интеллектуальные агенты в конструктивной среде / Е.А.Сапрунова // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10». - М.: Физматлит, 2010. - Т.1. - С.109-111.

39. Седов, С.Ю. Реализация систем параллельной обработки данных на ПЛИС типа FPGA / С.Ю. Седов. - М.:2009.

40. Селлерс, Ф. Методы обнаружения ошибок в работе ЭЦВМ, пер. с англ., М., -1972.

41. Скобцов, Ю.А. Генетический алгоритм построения функциональных тестов арифметико-логических устройств / Ю.А. Скобцов, Д.Е. Иванов, В.Ю. Скобцов // Восточно-Европейский журнал передовых технологий. - 2014. - Т. 2. № 9 (68). - С. 9-13.

42. Слюсарь, В.В. Методика проектирования программно-реконфигурируемых устройств на базе ПЛИС / В.В. Слюсарь, Р.М. Романов // Оборонный комплекс - научно-техническому прогрессу России. - 2010. - № 1. - С. 48-52.

43. Соломка, Ю.И. Исследование применимости генетических алгоритмов для оптимизации нейросетевых систем [Электронный ресурс]. - 2015. - Режим доступа: http://www.masters.donntu.edu.Ua/2004/fvti/solomka/diss/index.htm#ga2.

44. Сорокин, С.Н. Применение операторов многородительского скрещивания к эволюционному проектированию вибраторных антенн / С.Н. Сорокин // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008 (29 сентября - 3 октября 2008 г., Дубна): труды конференции. - 2008.

45. Стариков, А. Генетические алгоритмы - математический аппарат [Электронный ресурс]. - 2015. - Режим доступа: http : //www.basegroup .ru/library/optimization/ga_math.

46. Степченков, Ю.А. Опыт разработки самосинхронного ядра микроконтроллера на базовом матричном кристалле. / Ю.А. Степченков, В.С. Петрухин, Ю.Г. Дьяченко // Нано- и микросистемная техника. -2006. - №5. - C. 29 - 36.

47. Стешенко, В.В. Алгоритмы цифровой обработки сигналов: реализация на ПЛИС [Электронный ресурс]. - 2014. - Режим доступа: http : //www.dsol .ru/uploads/pdf/algodsp. pdf.

48. Стикс, Г. Совершенно секретно [Электронный ресурс]. - 2015. - Режим доступа: http://www. sciam.ru/news/2005.

49. Тарасов, И. Системы на кристалле на базе ПЛИС FPGA Xilinx с встроенными процессорами PowerPC [Электронный ресурс]. - 2015. - Режим доступа: http://www.kit-e.ru/articles/plis/2005_7_62.php.

50. Телец, В. ПЛИС для космических применений / В. Телец, С. Цыбин, А. Быстрицкий, С. Подъяпольский // Электроника: Наука, Технология, Бизнес. -2005. - №6. - C. 44 - 48.

51. Тюрин, С.Ф. Диагностирование логического элемента DC LUT FPGA [Электронный ресурс] / С.Ф. Тюрин, А.Ю. Городилов, Е.Ю. Данилова // Инженерный вестник Дона. - 2014. - №2. - Режим доступа: http : //www.ivdon.ru/ru/magazine/archive/n2y2014/2313.

52. Тюрин, С.Ф. Диагностирование ПЛИС на базе элементов с избыточным базисом с помощью генетических алгоритмов / С.Ф. Тюрин, А.Ю. Городилов // Материалы XLI междунар. конф. «Информационные технологии в науке, социологии и бизнесе». Осенняя сессия. Ялта-Гурзуф. - 2013. - С. 74-76.

53. Тюрин, С.Ф. Моделирование логического элемента LUT FPGA с контролем / С.Ф. Тюрин, А.Ю. Городилов, А.А. Байдаров // Информационно-измерительные и управляющие системы. - 2014. - Т. 12. № 9. - С. 35-43.

54. Тюрин, С.Ф. Повышение отказоустойчивости FPGA путем реконфигурации работоспособных элементов / С.Ф. Тюрин, А.Ю. Городилов, И.С. Понуровский // Радюелектронш i комп'ютерш системи. - 2013. - N5 (64). - С. 172-176

55. Тюрин, С.Ф. Реконфигурация функционально-полных толерантных элементов / С.Ф. Тюрин, А.Ю. Городилов, А.А. Сулейманов // Вестник Пермского

университета, серия «Математика. Механика. Информатика». - 2013. - вып. 4(23) - С. 91-96.

56. Тюрин, С.Ф. «Обратное» диагностирование логического элемента LUT FPGA / С.Ф. Тюрин, А.Ю. Городилов, Е.Ю. Данилова // Проектирование и технология электронных средств. - 2014. - № 2. - С. 50-54.

57. Тюрин, С.Ф. Автоматизированный синтез цифровых схем в функционально-полном толерантном базисе и в остаточных базисах / С.Ф. Тюрин, О.А. Громов, П.В. Гладышева. - Тюмень: Ист Консалтинг, 2010. - С.181-195.

58. Тюрин, С.Ф. Логические элементы с избыточным базисом / С.Ф. Тюрин // Вестник Пермского университета. Серия: Математика. Механика. Информатика. - 2013. - № 3. - С.91-105.

59. Тюрин, С.Ф. Надёжность систем автоматизации / С.Ф. Тюрин. - Пермь: Изд-во ПНИПУ, 2012. - 191 с.

60. Тюрин, С.Ф. Проблема сохранения функциональной полноты булевых функций при «отказах» аргументов // Автоматика и телемеханика. - 1999. - №9. -С.176-186.

61. Тюрин, С.Ф. Разработка контрольных и диагностических тестов для КМОП элементов с избыточным базисом / С.Ф. Тюрин, О.А. Громов // Приволжский научный вестник. - 2013. - № 1 (17). - С.13-21.

62. Уваров, С.С. Проектирование реконфигурируемых отказоустойчивых систем на ПЛИС с резервированием на уровне ячеек / С.С. Уваров // Автоматика и телемеханика. - 2007. - №9. - С.176-189.

63. Угрюмов, Е.П. Цифровая схемотехника: учебное пособие для вузов / Е.П. Угрюмов. - 2-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2007. - 800 с.

64. Указ Президента Российской Федерации «Об утверждении приоритетных направлений развития науки, технологий и техники в Российской Федерации и перечня критических технологий Российской Федера-ции».12.05.2011.[Электронный ресурс]. - Режим доступа: http://mon.gov.ru/dok/npa/prez/8479/ (дата обращения 12.01.2015).

65. Харченко, В.С. Научно-методические результаты в области развития гарантоспособных систем / В.С. Харченко // Радюелектронш та комп'ютерш систе-ми. - 2009. - №4. - С. 24-33.

66. Хаханов, В.И. Инфраструктура диагностического обслуживания SoC. // Вестник Томского университета. - 2008. - №4(5) [Электронный ресурс]. - Режим доступа: http://sun.tsu.ru/mminfo/000063105/inf/05/image/05-074.pdf. (дата обращения 01.02.2013).

67. Цой, Ю. Р. О математических моделях эволюционных алгоритмов / Ю.Р. Цой // Перспективные информационные технологии и интеллектуальные системы. - 2006. - №2.

68. Цыбин, С. Программируемая коммутация ПЛИС: взгляд изнутри [Электронный ресурс]. - 2014. - Режим доступа: http://www.kit-e.ru/articles/plis/2010_11_56.php.

69. Цыбин, С.А. Архитектура отказоустойчивой ПЛИС емкостью свыше 100 тыс. вентилей / С.А. Цыбин, А.В. Быстрицкий, С.Н. Скуратович // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС): сборник трудов всероссийской научно-технической конференции. - 2006.

70. Чуприна, С.И. Разработка и реализация интегрированной инструментальной среды составления учебных расписаний / С.И. Чуприна, Д.В. Басов // Математика программных систем: межвуз. сб. науч. тр. - Пермь: Перм.ун-т, 2003. -С.112-122.

71. Юдинцев, В. Радиационно-стойкие интегральные схемы. Надёжность в космосе и на земле / В. Юдинцев // Электроника: Наука, Технология, Бизнес: журнал. - 2007. - № 5. - С. 72-77.

72. Ярушкина, Н.Г., Стецко А.А. Генетическая оптимизация при автоматизированном проектировании вычислительных сетей / Н.Г. Ярушкина, А.А. Стецко // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008 (29 сентября - 3 октября 2008 г., Дубна): труды конференции. - 2008.

73. A fault-tolerant FPGA-based multi-stage interconnection network for space applications / M. Alderighi et al. // IEEE Int. Workshop on Electronic Design, Test and Applications. - 2002. - P.302-306.

74. A novel approach to defect tolerant design for SRAM based FPGAs / J. Kelly et al. // Int. Workshop on FPGAs. - 1994.

75. Aarts, E. Local Search in Combinatorial Optimization / E. Aarts, J.K. Lenstra. -Princeton University Press, 2003.

76. An automated BIST architecture for testing and diagnosing FPGA interconnect faults / J. Smith et al. // Journal of Electronic Testing: Theory and Applications. -2006. - Vol.22, №3. - P.239-253.

77. An optimum ORA BIST for multiple fault FPGA look-up table testing / A. Alaghi et al. // Asian Test Symposium. - 2006. - P. 293-298.

78. Autonomous FPGA Fault Handling through Competitive Runtime Reconfiguration / R.F. DeMara et al. // NASA/DoD Conference of Evolution Hardware. - 2005.

79. Avizienis, A. Dependable Computing: From Concepts to Application / A. Avizienis, J.-C. Laprie // IEEE Trans. on Computers. - 1986. - №74 (5). - P. 629-638.

80. Back, T. Self-adaptation in genetic algorithms. / T. Back // Towards a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life. - 1992 - P.263-271.

81. BIST based Interconnect Fault Location for FPGAs / N. Campregher et al. // FPL'04, LNCS 3203. - 2004. - P.322-332.

82. Carmichael, C. Triple Module Redundancy Design Techniques for Virtex FPGAs / C. Carmichael // Xilinx Application Note XAPP197. - 2006.

83. Clark, A. Metaheuristic Search as a Cryptological Tool / A. Clark. - University of York, Department of Computer Science, 2001.

84. Clarke, P.J. Electromigration - a tutorial introduction / P.J. Clarke. // International Journal of Electronics. - 1990. - P.333-338.

85. Das, S.R. Self-testing of cores-based embedded systems with built-in hardware / S.R. Das // IEE Proc.-Circuits Devices Syst. - 2005. - Vol.152, №5. - P.539-546.

86. Deb, K. A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization / K. Deb, A. Anand, D. Joshi // KanGAL Report No.2002003. - Indian Institute of Technology, Kanpur, 2002.

87. Delgado, M. Coevolutionary genetic fuzzy systems: a hierarchical collaborative approach / M. Delgado, V.F. Zuben, F. Gomide // Fuzzy Sets and Systems. - 2004. -№141(1) - P.89-106.

88. Delman, B. Genetic Algorithms in Cryptography / B. Delman // A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Engineering/ New York. - 2004.

89. Diagnosis of interconnect faults in cluster-based FPGA architectures / I. Harris et al. // Int. Conf. on Computer Aided Design. - 2000. - P.472-475.

90. Dutt, S. Built-in-self-test of FPGAs with provable diagnosabilities and high diagnostic coverage with application to onlinetesting / S. Dutt, V. Verma, V. Suthar //IEEE Trans. Comput. Aided design of integrated circuits and systems. - 2008. -Vol.27, №2. - P.309-326.

91. Eiben, A.E. Evolutionary Algorithms with on-the-fly Population Size Adjustment / A.E. Eiben, E. Marchiori, V.A. Valko // Parallel Problem Solving from Nature, PPSN VIII. - 2004. - P.41-50.

92. Emmerich, M. Design of evolutionary algorithms: a case study for chemical process networks / M. Emmerich, M. GrSotzner, M. SchSutz // Evol. Comput. - 2001. -№9(3). - P.329-354.

93. Emmert, J.M. A fault tolerant technique for FPGAs / J.M. Emmert // Journal of Electronic Testing. - 2000. - Vol.16, №6. - P.591-606.

94. Evolutionary Based Techniques for Fault Tolerant Field Programmable Gate Arrays / G.V. Larchev et al. // Int. Conference on Space Mission Challenges for Information Technology. - 2006.

95. Exploring FPGA structures for evolving fault tolerant hardware / A.P. Shanthi et al. // NASA/DoD Conference on Evolvable Hardware. - 2003. - P.174-181.

96. Fault tolerance of switch blocks and switch block arrays in FPGA / J. Huang et al. // Trans. on VLSI Systems. - 2005. - Vol.13, №7. - P.794-807.

97. Fernandes, C. Self-regulated population size in evolutionary algorithms /

C. Fernandes, A. Rosa // Proceedings of the 9-th International Conference Parallel Problem Solving from Nature PPSN IX. - 2006. - P. 920-929.

98. Fiszelew, A. Automatic Generation of Neural Networks based on Genetic Algorithms / A. Fiszelew, P. Britos, G. Perichisky, R. Garcнa-Martнnez //Information Systems Electronic Review. - 2003. - №1(2).

99. FLAW: FPGA lifetime awareness / S. Srinivasan et al. // Design Automation Conference. - 2006. - P.630-635.

100. FPGA/CPLD - ПЛИС (Программируемые Логические Интегральные Схемы) [Электронный ресурс]. - 2013. - Режим доступа: http://www.fpga-cpld.ru/.

101. Gause, J. Static and Dynamic Reconfigurable Designs for a 2D Shape-Adaptive DCT / J. Gause, P. Cheung, W. Luk // Field-Programmable Logic and Applications. - New York: Springer-Verlag, 2000. - P.96-105.

102. Goldberg D.E. Simple genetic algorithms and the minimal deceptive problem /

D.E. Goldberg // Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence. - Morgan Kaufmann, 2007.

103. Gomez, J. Self Adaptation of Operator Rates in Evolutionary Algorithms / J. Gomez // Proceedings of Genetic and Evolutionary Computation Conference 2004 (GECCO 2004). - LNCS 3102, 2004. - P.1162-1173.

104. Gorodilov, A. Automatic synthesis of combinational circuits set for the purposes of FPGA reconfiguration within the model of partial failures of logic elements / A. Gorodilov // Proceedings of the 2015 IEEE North West Russia Section Young Researchers in Electrical and Electronic Engineering Conference (2015 ElConRusNW). -2015. - P. 196-197.

105. Grasemann, U. Evolving wavelets using a coevolutionary genetic algorithm and lifting. Proceedings of the Genetic and Evolutionary Computation Conference, vol. II / U. Grasemann, R. Miikkulainen. - New York: Springer, 2004. - P.969-980.

106. Grefenstette, J.J. Optimization of control parameters for genetic algorithms. / J.J. Grefenstette // IEEE Transactions on Systems, Man, and Cybernetics. - 1986. -№16(1). - P.122-128.

107. Hesser, J. Towards an optimal mutation probability for genetic algorithms. / J. Hesser, R. Manner // Proceedings of the 1 st Conference on Parallel Problem Solving from Nature. - 1990. - P.23-32.

108. High Quality TPG for Delay Faults in Look-Up Tables of FPGAs / P. Girard et al. // Int. Workshop on Electronic Design, Test and Applications. - 2004.

109. IEEE Std 1149.1 - Standard Test Access Port and Boundary-Scan Architecture [Электронный ресурс]. - Режим доступа: http://grouper.ieee.org/groups/1149/!/ (дата обращения 22.02.2015).

110. IEEE std 1500 - Standard for Embedded Core Test [Электронный ресурс]. -2015. - Режим доступа: http://grouper.ieee.org/groups/1500/.

111. Lach, J. Enchanced FPGA Reliability Through Efficient Run-Time Fault Reconfiguration / J. Lach // Transactions on Reliability. - 2000. - Vol. 49, № 3.

112. Lakamraju, V. Tolerating operational faults in cluster-based FPGAs / V. Lakamraju // ACM International Workshop on FPGAs. - 2000.

113. Mayer, D.C. Designing Integrated Circuits to Withstand Space Radiation / D.C. Mayer, R.C. Lacoe. // Crosslink. -2003. -Vol.4, № 2. -P. 30-35.

114. McDonald, E.J. Runtime FPGA Partial Reconfiguration / E.J. McDonald // IEEE A&E SYSTEMS MAGAZINE. - 2008. - July. - P.10-15.

115. Mesquita, D. Remote and partial reconfiguration of FPGAs: tools and trends / D. Mesquita, F. Moraes, J. Palma et al. // Proc. of the International Parallel and Distributed Processing Symposium. - 2003.

116. Michalewicz, Z. How to Solve It: Modern Heuristics / Z. Michalewicz. - Springer, 2004

117. Mitchell, М. An Introduction to Genetic Algorithms / М. Mitchell. - Fifth printing. Cambridge, MA: The MIT Press, 1999.

118. Nezami, K.G. Handel-C Implementation of Early-Access Partial-Reconfiguration for Software Defined Radio / K.G. Nezami, P.W. Stephens, S.D. Walker // Wireless Communications and Networking Conference. - 2008. - P.1103-1108.

119. On Interface and Oxide Degradation in VLSI MOSFETs — Part I: Deuterium Effect in CHE Stress Regim / D. Esseni et al. // IEEE Transactions on Electron Devices. - 2002. - Vol.49, №2.

120. Online Fault Tolerance for FPGA Logic Blocks / J.M. Emmert et al. // IEEE Trans. on VLSI Systems. - 2007. - Vol.15, №2.

121. Partial reconfiguration of FPGA mapped designs with applications for fault tolerance and yield enhancement / J.M. Emmert et al. // Int. Workshop on Field Programmable Logic and Applications, LCNS 1304. - 1997. - P.141-150.

122. Pelikan, M. Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms / M. Pelikan. - Springer, 2005. - 166 p.

123. Rabaey, J.M. Silicon platforms for the next generation wireless systems - What role does reconfigurable hardware play? / J.M. Rabaey // Field-Programmable Logic and Applications. - New York: Springer-Verlag, 2000. - P.277-285.

124. Reconfiguration and Fine-Grained Redundancy for Fault Tolerance in FPGAs / N. Campregher et al. // Int. Conf. on Field Programmable Logic (FPL). - 2006. - P.455-460.

125. Redundancy Circuitry for Logic Circuits / C. McClintock et al. // US Patent 6,6166,559. - 2000.

126. Roving STARs: An Integrated Approach to On-Line Testing, Diagnosis, and Fault Tolerance for FPGAs / M. Abramovici et al. // NASA/DoD Workshop on Evolvable Hardware. - 2001. - P.73.

127. Rudnick, E.M. Application of Simple Genetic Algorithm to Sequential Circuit Test Generation / E.M. Rudnick, J.G. Holm, D.G. Saab, J.H. Patel // Proc. European Design & Test Conf. - 1994. - P.40-45.

128. Rudolph, G. Self-adaptive mutations may lead to premature convergence. / G.Rudolph // IEEE Trans. Evol. Comput. - 2001. - №5(4).

129. Schaffer, J. A study of control parame-ters affecting online performance of genetic algorithms for function op-timization. / J. Schaffer, R. Caruana, L. Eshelman, R. Das // Proceedings of Third International Conference on Genetic Al-gorithms. - 1989. -P.51-60.

130. Self-characterization of Combinatorial Circuit Delays in FPGAs / J. Wong et al. // Int. Conf. on Field Programmable Tech. - 2007. - P.17-23.

131. Sidhu, R. A self-reconfigurable gate array architecture / R. Sidhu, S. Wadhwa, A. Mei, V.K. Prasanna // Field-Programmable Logic and Applications. - New York: Springer-Verlag, 2000. - P.106-120.

132. Stott, E. Fault tolerant methods for reliability in FPGAs /E. Stott, P. Sedcole, P.Y.K Cheung // Field Programmable Logic and Applications - 2008. - P.415-420.

133. The Energy-Driven Hot-Carrier Degradation Modes of nMOSFETs / C. Guérin et al. // IEEE Transactions on Device and Materials Reliability. - 2007. - Vol.7, №2.

134. The Yield Enhancement of Field-Programmable Gate Arrays / N.J. Howard et al. // IEEE Trans. on VLSI Systems. - 1994. - Vol.2, №1.

135. Three-stage compression approach to reduce test data volume and testing time for IP cores in SoCs / L. Li, K. Chakrabarty, S. Kajihara, S. Swaminathan // IEE Proc.-Comput. Digit. Techn. - 2005. - Vol.152, №6. - P.704-712.

136. Torresen, J. Reconfigurable Logic Applied for Designing Adaptive Hardware Systems / J. Torresen // Proc. of the International Conference on Advances in Infrastructure for e-Business, e-Education, e-Science, and e-Medicine on the Internet (SSGRR'2002W). - 2002.

137. Torresen, J. Reconfigurable Logic Applied for Designing Adaptive Hardware Systems / J. Torresen // International Conference on Advances in Infrastructure for Electronic Business, Education, Science, and Medicine on the Internet (SSGRR 2002W). - 2002.

138. Trimberger, S. A Time-Multiplexed FPGA / S. Trimberger, D. Carberry, A. Johnson, J. Wong // The 5-th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. - 1997. - P.22-28.

139. Tyurin, S. Redundant Basises for Critical Systems and Infrastructures General Approach and Variants of Implementation / S. Tyurin, V. Kharchenko // Proceedings of the 1st International Workshop on Critical Infrastructures Safety and Security. -2011. - Vol. 2. - P. 300 - 307.

140. Tyurin, S. Redundant Basises for Critical Systems and Infrastructures: General Approach and Variants of Implementation. / S. Tyurin, V. Kharchenko // Proceedings of the 1st Intrenational Workshop on Critical Infrastructures Safety and Security. - 2011.

141. Tyurin, S.F. A residual basis search algorithm of fault-tolerant programmable logic integrated circuits / S.F. Tyurin, O.A. Gromov // Russian Electrical Engineering. -

2013. - №84 (11). - P.647-651.

142. Villasenor, J. Congurable computing / J. Villasenor, W.H. Mangione-Smith // Sci-entic American. - 1997. - №6.

143. Vose, M. D. Punctuated equilibria in genetic search / M.D. Vose, G.E. Liepins //Complex Systems. - 1991.

144. Wang, L. Wu Feng-yan Dynamic partial reconfiguration in FPGAs / L. Wang. -2009.

145. Whitley, D. A genetic algorithm tutorial / D. Whitley // Statistics and computing. -1994. - №4. - P.65-85.

146. Yamamichi, T. A GA-based fault-containment learning algorithm for binary neural networks / T. Yamamichi, T. Saito, H. Torikai // Proc. of NOLTA. - 2004. - P.697-700.

147. Yu, T.-L. Online Population Size Adjusting Using Noise and Substructural Measurements. IlliGAL Report No. 2005017 / T.-L. Yu, K. Sastry, D.E. Goldberg. - The University of Illinois, 2005.

148. Zebulum, R.S. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms / R.S. Zebulum, M.A.C. Pacheco, M.M.B.R. Vellasco // Boca Raton, FL: CRC Press, 2002.

149. Zeidman, B. Introduction to CPLD and FPGA Design [Электронный ресурс]. -

2014. - Режим доступа: http://worldtracker.org/media/library/Engineering/ Electrical Engineering/Introduction to CPLD and FPGA Design.PDF.

ПРИЛОЖЕНИЕ А. АКТЫ О ВНЕДРЕНИИ А.1. Акт об использовании результатов работы в учебном процессе ПГНИУ

Комиссия в составе:

председатель - декан механико-математического факультета, к.т.н. Кузнецов А.Г., члены комиссии: зав. каф. прикладной математики и информатики, д.ф.-м.н., профессор Русаков C.B., доцент каф. математического обеспечения вычислительных систем, к.ф.-м.н., доцент Алябьева В.Г.,

составили настоящий акт о том, что результаты диссертационной работы «Методы и алгоритмы диагностирования и реконфигурации логики высоконадёжных ПЛИС», представленной на соискание ученой степени кандидата технических наук, использованы в учебном процессе на кафедре Математического обеспечения вычислительных систем ПГНИУ при преподавании дисциплин «Комбинаторные алгоритмы», «Математическая логика и теория алгоритмов», «Алгоритмы и анализ сложности» в следующем виде.

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

2. Модифицированные методы рабочего (функционального) и тестового контроля логического элемента LUT FPGA - в лекционном материале дисциплины «Математическая логика и теория алгоритмов».

3. Полученные оценки сложности и эффективности модифицированных алгоритмов и технических решений - в комплексе лабораторных работ дисциплины «Алгоритмы и анализ сложности».

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

«УТВЕРЖДАЮ»

Ректор Пермского государственного

Городилова Алексея Юрьевича.

Модифицированный генетический алгоритм реконфигурации ПЛИС типа FPGA,

(Кузнецов А.Г.)

Члены комиссии:

(Русаков C.B.)

(Алябьева В.Г.)

А.2. Акт о внедрении результатов работы в ОАО «Морион»

«УТВЕРЖДАЮ» й директор ОАО «Морион» \/^/</J_Бускин В.В.

А7 » дс^аЪрА 2015 г.

АКТ

о внедрении результатов НИОКР

В соответствии с договором о сотрудничестве №79 от 10.10.2011 г. между ОАО «Морион» и ПНИПУ (Пермским национальным исследовательским политехническим университетом - ПГТУ - Пермским государственным техническим университетом) была проведена НИОКР «ФПТ-FPGA».

В рамках данной НИОКР были проведены следующие работы:

1. Предложен модифицированный алгоритм диагностирования ПЛИС.

2. Разработан технический проект отказоустойчивого цифрового телекоммуникационного оборудования на базе ПЛИС FPGA. Реализован модифицированный алгоритм восстановления функциональности после отказа путем реконфигурации ПЛИС.

3. Предложена концепция отказоустойчивой программируемой логической интегральной схемы на основе модифицированных методов рабочего (функционального) и тестового контроля логических элементов LUT FPGA. Проведены расчеты сложности и эффективности новых алгоритмов и технических решений.

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

Главный конструктор ОАО

Ведущий инженер

«Морион»

Масальцев В.А.

Курилов Д.В.

А.3. Справка о личном вкладе в НИОКР

.ТВЕРЖДАЮ»

кого национального тельского политехнического :итета^ф.-м.н., профессор

А.А. Ташкинов

« 2 А »

^ек&Ер.я 2015 г.

генетический алгоритм

СПРАВКА

о личном вкладе Городилова А.Ю. в НИОКР «ФПТ-FPGA»

при выполнении договора о сотрудничестве №79 от 10.10.2011 г.

В процессе выполнения НИОКР был проведен анализ применяемых алгоритмических и аппаратных технических решений, в результате чего были сформулированы рекомендации по внедрению новых отказоустойчивых логических элементов FPGA и реализации новых методов диагностирования и реконфигурации ПЛИС типа FPGA.

В ходе работы Городилов А.Ю.:

1) разработал модифицированный диагностирования ПЛИС типа FPGA;

2) принимал участие в разработке технического проекта отказоустойчивого цифрового телекоммуникационного оборудования на базе ПЛИС типа FPGA (реализация модифицированного генетического алгоритма реконфигурации ПЛИС, формирования списка возможных отказов на основе структуры логических элементов ПЛИС с последующим поиском работоспособной конфигурации и формированием файла VHDL);

3) участвовал в разработке модифицированного метода рабочего (функционального) и тестового контроля логических элементов LUT FPGA с целью сокращения времени контроля, выполнил расчет достоверности функционирования и коэффициента готовности получаемых схем;

4) получил оценки сложности и эффективности новых алгоритмических и технических решений.

Личный вклад Городилова А.Ю. в выполнение указанных работ составил 60%.

Научный руководитель НИОКР «ФПТ-FPGA»

А.А. Южаков

ПРИЛОЖЕНИЕ Б. ЛИСТИНГИ ПРОГРАММ

Б.1. Программа построения диагностической последовательности

Б.1.1 Реализация генетических операторов

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.IO;

using System.Collections;

namespace FPGA_diagnosis {

public class csFunction {

public bool[] func = new bool[csParams.func_length]; //сама функция public bool[][] error_func = new bool[csParams.x_length * 2][]; //все возможные функции с отказами

public int[] func_classes = new int[csParams.x_length * 2]; //к каким классам принадлежит каждая из этих функций

//исходная функция всегда является 0-вым элементом

public bool[][] classes = new bool[csParams.x_length * 2 + 1][]; //выделенные классы (различные строки между func и error_func)

public int max_class = -1; //максимальное число классов (а заодно и предел, до которого считается ГА)

public int class_count = 0; //число классов = max_class + 1;

public csFunction()

{

for (int i = 0; i < csParams.func_length; i++) { func[i] = csParams.randomBool(); } generateFuncArray();

public csFunction(string function)

{

int length = Math.Min(csParams.func_length, function.Length);

csParams.func_length = length;

for (int i = 0; i < length; i++)

{ func[i] = function[i] == '1' ? true : false; }

generateFuncArray();

}

//получить из исходной функции набор ошибочных функций с единичными константными отказами

private void generateErrorFuncs() {

int x_count = csParams.x_length; int func_lenght = csParams.func_length;

for (int i = 0; i < x_count; i++) //i - длина копируемой строки; {

int j_i = (x_count - i - 1) * 2; //константный 0, копируем первые во вторые

int j_i_1 = j_i + 1; //константная 1, копируем вторые в первые

bool first = true;

int substring_length = Convert.ToInt32(Math.Pow(2, i)); int cur_length_substring = 0; //текущая длина в подстроке error_func[j_i] = new bool[csParams.func_length]; error_func[j_i_1] = new bool[csParams.func_length];

for (int k = 0; k < func_lenght; k++) {

error_func[j_i][k] = first ? func[k] : func[k - substring_length]; error_func[j_i_1][k] = first ? func[k + substring_length] : func[k]; cur_length_substring++;

if (cur_length_substring == substring_length)

{

cur_length_substring = 0; first = ! first;

}

//генерация классов

private void copyFuncToClass(bool[] p_func)

{

max_class++;

classes[max_class] = new bool[csParams.func_length]; for (int i = 0; i < csParams.func_length; i++) { classes[max_class][i] = p_func[i]; }

}

public bool cmpFuncs(bool[] f1, bool[] f2)

{

int lenght = Math.Min(f1.Length, f2.Length); if ((fl.Length > lenght) || (f2.Length > lenght)) return false;

else

{

int i = 0;

while (i < lenght && f1[i] == f2[i])

i++;

return i == lenght;

}

}

private void generateClasses()

{

copyFuncToClass(func);

for (int i = 0; i < csParams.x_length * 2; i++) {

int find = -1;

for (int j = 0; j <= max_class; j++) {

if (cmpFuncs(classes[j], error_func[i]))

{

find = j;

break;

}

if (find == -1)

{

copyFuncToClass(error_func[i]); find = max_class;

}

func_classes[i] = find;

}

}

//получить все функции-ошибки и выделить классы

public void generateFuncArray()

{

generateErrorFuncs(); generateClasses(); class_count = max_class + 1;

}

//преобразование числа из двоичного кода в десятичный - получение индекса в массиве

public int getIndexByBin(bool[] bin)

{

int res = 0; int pow = 1;

for (int i = bin.Length - 1; i >= 0; i--)

{

if (bin[i])

res += pow; pow *= 2;

}

return res;

}

public string printBoolArray(bool[] array)

string result = "";

for (int i = 0; i < array.Length; i++)

result += array[i] ? "1" : "0"; return result;

}

public string print()

{

return " класс №0 " + printBoolArray(func);

}

public string printErrorFuncs()

{

string result = "";

for (int i = 0; i < error_func.Length; i++) {

result += "x" + (i / 2).ToString() + " = " + (i % 2).ToString() + " класс №" +

func_classes[i].ToString() + " " + printBoolArray(error_func[i]) + Environment.NewLine;

}

return result;

}

public string printClasses()

{

string result = "";

for (int i = 0; i < class_count; i++) {

result += "Класс №" + i.ToString() + " " + printBoolArray(classes[i]) +

Environment.NewLine;

}

return result;

}

public string printTotal()

return "Функция:" + Environment.NewLine + print() + Environment.NewLine + "Единичные

отказы:" + Environment.NewLine + printErrorFuncs();

}

private string calcAnswerInner(int level, int unit_length, int prev_last, List<int> list) //при

первом запуске: level = 1, unit_length = unit_length, prev_last = -1, list => empty

{

for (int current_key = prev_last + 1; current_key < csParams.func_length - unit_length + level;

current_key++) {

list.Add(current_key); if (level != unit_length) { //спуститься на уровень вниз

string res = calcAnswerInner(level + 1, unit_length, current_key, list); if (res != null) return res;

}

else

{ //база - посчитать, сколько классов получается bool[][] test_res = new bool[class_count][]; int result = 1;

//сгенерировать результат прогона по функциям

for (int i = 0; i < class_count; i++) {

test_res[i] = new bool[unit_length]; for (int j = 0; j < unit_length; j++) test_res[i][j] = classes[i][list[j]];

}

//сравнить их между собой и посчитать количество уникальных

for (int i = 1; i < class_count; i++) {

bool find = false;

for (int j = 0; j < i - 1; j++) {

find = find || cmpFuncs(test_res[i], test_res[j]); if (find) break;

if (!find) result++;

}

if (result == class_count)

{

//нашли точное решение

string res = "Точное решение: " + result + " Длина тестовой последовательности: " + list.Count + " Тестовая последовательность: ";

for (int i = 0; i < list.Count; i++) res += " " + list[i].ToString(); return res;

}

}

li st.Remove(current_key);

}

return null;

}

public string calcAnswer()

{

int unit_length = Convert.ToInt32(Math.Ceiling(Math.Log(class_count, 2))); string result = null;

while (result == null)

{

result = calcAnswerInner(1, unit_length, -1, new List<int>()); unit_length++;

}

return result;

}

}

class csUnit

public bool[][] test_set = new bool[csParams.unit_length][]; //Тестирующая последовательность (строки длиной x_length (кол-во переменных)) public int fitness;

public List<int> i_find_classes = new List<int>();

public csUnit(bool empty) //создание особи со случайными значениями {

for (int i = 0; i < csParams.unit_length; i++) {

test_set[i] = new bool[csParams.x_length]; if (!empty)

for (int j = 0; j < csParams.x_length; j++) test_set[i][j] = csParams.randomBool();

}

if (!empty) calcFiness();

}

public csUnit(csUnit copy)

{

test_set = copy.test_set; fitness = copy.fitness;

}

public int calcFiness() //расчёт фитнесс-функции

//сколько различных классов может выделить данный элемент

{

int result = 1;

i_find_classes.Add(0);

int[] points = new int[csParams.unit_length];

for (int i = 0; i < csParams.unit_length; i++)

points[i] = csParams.func.getIndexByBin(test_set[i]); bool[][] test_res = new bool[csParams.func.class_count][]; //сгенерировать результат прогона по функциям

for (int i = 0; i < csParams.func.class_count; i++) {

test_res[i] = new bool[csParams.unit_length]; for (int j = 0; j < csParams.unit_length; j++)

test_res[i][j] = csParams.func.classes[i][points[j]];