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

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

Греков Артем Владимирович

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

ПОВЫШЕНИЕ ОТКАЗОУСТОЙЧИВОСТИ КОНФИГУРИРУЕМЫХ БЛОКОВ ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМ НА ОСНОВЕ ФУНКЦИОНАЛЬНО ПОЛНЫХ ТОЛЕРАНТНЫХ

Специальность: 05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Работа выполнена в ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет» (ГЖИПУ)

доктор технических наук, профессор Тюрин Сергей Феофентович

доктор технических наук, доцент Середа Юрий Алексеевич

кандидат технических наук, Березняков Сергей Вадимович

Учреждение Российской академии наук Институт проблем управления им. В.А. Трапезникова РАН

Защита состоится «16» декабря 2011 г. в 15.00 часов на заседании Диссертационного совета Д 212.188.04 при ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет» по адресу:

614990, г.Пермь, Комсомольский проспект, 29, ауд. 345.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет».

Автореферат разослан « 7 » ноября 2011г.

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

Общая характеристика работы

Актуальность работы. Для информационно-телекоммуникационных систем, перспективных вооружений, военной техники, космических систем критическими технологиями являются технологии создания электронной компонентной базы. В настоящее время одним из динамично развивающихся направлений цифровой схемотехники являются программируемые логические интегральные схемы - ПЛИС. Одним из широко используемых сегодня типов ПЛИС являются ПЛИС FPGA (англ. field-programmable gate array) - программируемые пользователем вентильные матрицы (ППВМ), которые имеют много логических элементов - конфигурируемых пользователем логических блоков - конфигурируемых блоков (КБ) и гибкую архитектуру.

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

Объектом исследования являются конфигурируемые блоки ПЛИС FPGA.

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

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

Принципы отказоустойчивости рассматривались в работах Р. Хэмминга, Дж. фон Неймана, Д. Малера, А. Авижениса и др. Эти принципы были использованы и используются при создании систем управления военными, космическими комплексами. Разработкой новых подходов к повышению надёжности цифровых элементов и узлов, в том числе на основе ПЛИС, занимаются в ИПУ РАН (группа Каравая М.Ф.), ИПИ РАН (группа Степченко Ю.А., продолжающая исследования Варшавского В.И. в области самосинхронных схем), активно работают украинские учёные - группы Харченко B.C., Хаханова В.И. Вопросы повышения надёжности исследовались также Пархоменко П.П., Согомоняном Е.С., Ткаченко A.B., Харитоновым В.А., Твердохлебовым В.А., Тюриным С.Ф. и др. В последние годы всё чаще говорят о «живучести», когда речь идёт об отказах, вызванных внешними поражающими воздействиями.

Однако научно-методический аппарат восстановления логики ПЛИС после отказов в настоящее время в полной мере не разработан. Поэтому предметом исследования являются методы и модели создания отказоустойчивых конфигурируемых блоков - КБ ПЛИС на основе восстановления логики.

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

Цель работы - совершенствование научно-методического аппарата синтеза отказоустойчивых конфигурируемых блоков ПЛИС на основе элементов с избыточным базисом (функционально-полных толерантных элементов).

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

- модификация и решение уравнения сохранения функциональной полноты элемента с четырьмя входами с учетом модели замыканий;

- совершенствование алгоритма представления произвольной булевой функции в функционально полном толерантном (ФПТ) базисе и остаточных базисах;

- разработка методики синтеза конфигурируемых блоков на основе ФПТ элементов.

Методы исследования: теория булевых функций и автоматов, комбинаторика, теория надёжности.

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

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

- рекомендуется фиксирование остаточных базисов элементов после глубокого диагностирования имеющимися средствами ПЛИС для использования при переконфигурировании мелкозернистых ПЛИС;

- для крупнозернистых ПЛИС на основе ФПТ мультиплексоров целесообразно «деление» с выявлением и последующим использованием работоспособной доли либо самостоятельно, либо путём восстановления из отказавших мультиплексоров одного полного;

- предлагается усовершенствование пассивной отказоустойчивости на основе структурного резервирования (дублирование, мажоритирование,

глубокое мажоритирование) путём использования в каждом канале скользящего резервирования с восстановлением элементов из отказавших, но сохранивших базис.

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

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

- установлено, что ФПТ функция xixi VX3X4 сохраняет базис и при модели замыканий двух переменных;

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

- усовершенствован алгоритм представления произвольной булевой функции в ФПТ базисе и новых остаточных базисах на основе предложенного правила инверсирования ортогональных конъюнкций и верификации результатов расчётов;

- разработана методика синтеза конфигурируемых блоков на основе ФПТ элементов и математических моделей активно и пассивно отказоустойчивой ПЛИС-ФПТ с переходом на остаточные базисы.

Достоверность исследования подтверждается проверкой результатов решения предложенного уравнения сохранения функциональной полноты с помощью разработанной программы, а также путём проверки соответствия полученных решений теореме Поста; верификацией представления булевых функций в заданных базисах путём вычисления соответствующих конъюнкций (решение обратной задачи); проверкой автоматически синтезированных ехем с помощью схемотехнического моделирования в системе «Quartus И» фирмы Altera; использованием апробированного математического аппарата булевой алгебры, теории автоматов и теории надёжности.

Практическая значимость диссертации: • - разработаны алгоритм и программа решения логического уравнения сохранения функциональной полноты;

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

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

- разработаны технические решения типовых комбинационных схем в новом ФПТ базисе, обеспечивающем снижение сложности типовых схем.

Таким образом, разработанные в диссертации теоретические положения и методики синтеза и анализа КБ ПЛИС позволяют повысить отказоустойчивость ПЛИС за счёт восстановления логики.

Реализация результатов работы. Полученные результаты внедрены в ОАО «СТАР» (г. Пермь) и ЗАО «ИБС» (г. Пермь).

Результаты работы используются па кафедре «Автоматика и телемеханика» Пермского национального исследовательского политехнического университета при преподавании дисциплин «Надёжность систем автоматизации» и «Основы схемотехники», а также на кафедре «Вычислительные машины, комплексы, системы и сети» Пермского военного института внутренних войск МВД России при преподавании дисциплин «Теория автоматов», «Схемотехника ЭВМ».

Апробация работы. Основные теоретические и прикладные результаты диссертационной работы докладывались на Всероссийской научно-технической конференции «Информация, инновации, инвестиции» (Пермь, 2006), Всероссийской научно-практической конференции молодых ученых и специалистов (Пермь, 2007, 2008), Международной научно-технической конференции «Dependable Systems, Services and Technologies

(БеБЗегТ)» (Украина, Кировоград, 2007, 2009), Международной интернет-конференции «Инновационные технологии: теория, инструменты, практика» (Пермь, 2010), Международной научно-технической конференции «Вычислительный интеллект» (Украина, Черкассы, 2011).

Публикации. Основные результаты диссертационной работы опубликованы в 17 научных работах, в том числе в двух статьях в рецензируемых научных изданиях, входящих в Перечень ВАК.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 81 наименования и шести приложений. Работа представлена на 267 е., в том числе 167 с. основного текста, содержит 97 рисунков и 76 таблиц.

Основное содержание работы

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

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

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 1 1 я3 1 аь «6 0 1 а9 а\о 0 а\г 0 0 0

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

(а6 V ап V а12Ха5 а, V аи\аг V я, V а^г V а, V а6)(а, V а5 V а9)(а3 V а6 V а10) (а, Vа, V а12Ха9 V а10 V ап\агаи Vа,а12Ха6а, V адХед„ V а5а10)= 1

Получены 6 решений. Решению а3а5а6а,аша12 соответствует ФПТ

функция Xlл:2Vд:зЛ4 (3), которая была получена ранее только для модели однократных константных отказов, что доказывает её толерантность и к модели замыканий двух входных переменных. Под толерантностью функции понимается невосприимчивость её свойства функциональной полноты к отказам заданной модели - вид функции изменяется, но функциональная полнота в смысле теоремы Поста сохраняется. Описывается усовершенствованная методика построения ФПТ функции.

На рисунке 1 представлено условное графическое обозначение предлагаемого ФПТ элемента:

Рисунок 1 - Условное графическое обозначение ФПТ элемента х\Хг vxзx4

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

таблице истинности Г(0,1,

) булева функция / представляется в ФПТ базисе и в А: остаточных базисах:

Алгоритм реализует представление произвольной ДНФ, заданной таблицей истинности, в виде отдельных таблиц для каждого ФПТ элемента в полном или остаточном базисах. Так, представление восьмиканального мультиплексора (генератора функций трёх переменных) в полном базисе имеет вид формулы:

г = хзх!(сх1\/ dx^)^/ x2(axlvbx\)v xзx2(gxl V кх