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

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

Громов Олег Александрович

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

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

2 О ИЮН 2013

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

005062044

Пермь-2013

005062044

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

Научный руководитель - доктор технических наук, профессор

Тюрин Сергей Феофентович

Официальные оппоненты - Первадчук Владимир Павлович,

доктор технических наук, профессор, заведующий кафедрой «Прикладная математика» Пермского национального исследовательского политехнического университета

Березняков Сергей Вадимович, кандидат технических наук, начальник бригады ТО-5 ОАО «СТАР»

Ведущее предприятие - Федеральное государственное

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

Защита состоится «3» июля 2013 г. в 13.00 часов на заседании диссертационного совета Д 212.188.04 при Пермском национальном исследовательском политехническом университете по адресу: 614990, г. Пермь, Комсомольский проспект, 29, ауд. 345.

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

Автореферат разослан «31» мая 2013 г.

Ученый секретарь

диссертационного совета Д 212.188.04, доктор технических наук, профессор

А.А. Южаков

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

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

В настоящее время большое количество работ посвящено вопросу повышения отказоустойчивости ПЛИС, которое, как правило, осуществляется за счет резерва. Так в работах В. Хаханова представлены методы восстановления работоспособности ПЛИС при отказах путем покрытия дефектных блоков резервными блоками, в работах С. Уварова предлагается восстановление ПЛИС с помощью резервирования на уровне ячеек, F. Meyer и D. Paradham предлагают ввести резервный столбец ячеек, N. Hastie и К Cliff резервный столбец и строку, J. Emmert предлагает ввести специальную шину с помощью, которой будет происходить замена отказавшей ячейки. Недостатком данных подходов является то, что ячейки с отказами при дальнейшей работе не используются.

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

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

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

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

Объектом исследования являются программируемые логические интегральные схемы.

Предметом исследования являются отказоустойчивые программируемые логические интегральные схемы на основе КМОП элементов с избыточным базисом.

Цель работы - повышение отказоустойчивости программируемых логических интегральных схем на основе КМОП элементов с избыточным базисом.

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

1. разработка метода синтеза КМОП логических элементов с избыточным базисом, сохраняющих функциональную полноту при ¿-кратных отказах;

2. разработка метода синтеза КМОП логических элементов с избыточным базисом, сохраняющих базисную булеву функцию при к -кратных отказах;

3. разработка алгоритма реконфшурации отказоустойчивых ПЛИС на основе КМОП элементов с избыточным базисом;

4. разработка алгоритма поиска остаточного базиса таблиц преобразования LUT (Look-up table) крупнозернистых ПЛИС.

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

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

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

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

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

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

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

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

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

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

- алгоритм поиска остаточного базиса таблиц преобразования крупнозернистых ПЛИС.

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

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

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

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

Апробация работы. Основные теоретические и прикладные результаты диссертационной работы докладывались на следующих научно-технических конференциях: Международной НТК «Dependable Systems, Services and Technologies (DeSSerT)» (Украина, Кировоград, 2010, 2012), Международной НТК «Вычислительный интеллект» (Украина, Черкассы, 2011), Всероссийской конференции с международным участием "Технические и программные средства систем управления, контроля и измерения (УКИ-12)" (Москва, 2012), Международной конференции молодых ученых Информационные технологии в науке, образовании, телекоммуникации и бизнесе (Украина, Крым, Ялта-Гурзуф, 2012) и других. Результаты работы докладывались и получили положительную оценку на технических семинарах в Институте проблем информатики РАН (2012) и Институте проблем управления РАН (2013). Работа была удостоена диплома I степени за победу во Всероссийском конкурсе научно-исследовательских работ аспирантов и молодых ученых в области стратегического партнерства вузов и предприятий радиоэлектронной промышленности (Санкт-Петербург, 2010).

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников, включающего 93 наименования и 3 приложений. Основная часть работы изложена на 161 странице машинописного текста, содержит 79 рисунков и 17 таблиц. Приложения включают программу выбора структурной схемы надежности и акты внедрения результатов работы.

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

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

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

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

вероятности безотказной работы /"(/). Метод основан на реализации следующей последовательности действий.

Определяется базис, в котором будет строиться требуемая функция ДНФ или КНФ (дальнейшие действия описаны для ДНФ базиса).

Модель Ч" сводится к модели к -кратных константных отказов, модели замыканий или к их комбинации. (Если это невозможно — реализация схемы может быть выполнена традиционными методами резервирования и далее не рассматривается.)

Исходный базис ДНФ трансформируется путем введения к дополнительных конъюнкций; всего реализуется к +1 конъюнкция. В каждой из к + \ конъюнкций вводится к дополнительных переменных. Таким образом, получаем функцию подключения шины питания и двойственную функцию подключения нулевой шины:

7=1 *+1*+!_

У* * = V л хI у. (2)

.=1

Выражения (1,2) позволяют перейти к принципиальной электрической схеме элемента сохраняющего функциональную полноту, в соответствии со следующими правилами:

1) Количество транзисторов, требуемое на реализацию каждой функции, определяется количеством переменных в реализуемой функции;

2) Если переменная входит в выражение, в прямом виде, то в схеме ей соответствует n-канальный КМОП транзистор, если в инверсном виде, то р-канальный КМОП транзистор;

3) Для реализации операции конъюнкция используется последовательное соединение КМОП транзисторов;

4) Для реализации операции дизъюнкция используется параллельное соединение КМОП транзисторов.

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

Сложность реализации схемы КМОП элемента оценивается по следующему выражению

Sk =2(1 + £)2Д>0. (3)

В случае если сложность реализации в числе транзисторов меньше заданной, то оценивается интенсивность отказов связей по выражению (4) и вероятность безотказной работы полученной схемы по выражению (5)

A/=2.(A: + 1)24„ (4)

(1-е )■ (5)

Коэффициент р¥ учитывает увеличение интенсивности отказов для экспоненциальной модели отказов.

С использованием предложенного метода синтеза КМОП логических элементов с избыточным базисом, сохраняющих функциональную полноту получены две схемы элементов (для случая Лг = 1 ). Данные схемы промоделированы в САПР Multisim фирмы National Semiconductors, результаты моделирования подтверждают их корректное функционирование, показано, что КМОП элементы сохраняют функциональную полноту при однократных константных отказах входов и транзисторов.

В третьей главе разработан метод синтеза КМОП логических элементов с избыточным базисом, сохраняющих базисную булеву функцию при ¿-кратных отказах. КМОП элементы с избыточным базисом, сохраняющие базисную булеву функцию построены с использованием подхода учетверенной логики, который требует четырехкратной избыточности функции и входов элемента

/=/l /2V/3 /4, (6)

где /i = /2 = /з = /4 = /•

Метод синтеза имеет ту же область применения, что и метод синтеза КМОП элементов с избыточным базисом, сохраняющих функциональную полноту и позволяет сформировать структуру КМОП логического элемента (на уровне транзисторов) с учетом модели отказов (), кратности отказов (£), заданных интенсивностях отказов транзисторов ( Лт ), электрических связей и

вероятности безотказной работы Метод основан на реализации следующей последовательности действий.

В соответствие с заданной моделью отказов У определяются все ДНФ (КНФ или иные) модификации заданной булевой функции, например, для ДНФ:

г* п*г9

/■ *= V А х (7)

Модель Ч* сводится к модели к -кратных константных отказов или замыканий или к их комбинации (если это невозможно - реализация схемы может быть выполнена традиционными методами резервирования и далее не рассматривается.)

Вводится к дополнительных конъюнкций; всего реализуется к г конъюнкций (где г - число переменных в исходной функции). В каждой из к г конъюнкций вводится к дополнительных переменных. Таким образом, получаем функцию подключения шины питания и двойственную функцию подключения нулевой шины:

/^ЛД, (8)

1=1 J=1

Далее получаем двойственную функцию подключения нулевой шины:

/-Ч^- (9)

1=1 ./=1 -1

На основании выражений (8,9) синтезируется принципиальная электрическая схема элемента сохраняющего функциональную полноту. Правила получения схемы аналогичны методу синтеза КМОП элементов, сохраняющих функциональную полноту.

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

Сложность реализации схемы КМОП элемента оценивается по следующему выражению

=2-2 (* + 1)Ч (10>

7=1

В случае если сложность реализации в числе транзисторов меньше заданной, то оценивается интенсивность отказов связей по выражению (11) и вероятность безотказной работы полученной схемы по выражению (12)

Я/=2 ± (к + 1)2пгЛ„„ (И)

1=1

(1-е ))2. (12)

Выражение (12) учитывает тот факт, что одновременно к отказов могут быть в двух частях схемы, в // и /_*.

С использованием предложенного метода синтеза КМОП логических элементов с избыточным базисом, сохраняющих базисную булеву функцию получены две схемы элементов (для случая к = 1 ). Для подтверждения правильности функционирования схем также проведено их моделирование при наличии и отсутствии отказов, которое подтвердило правильность функционирования предлагаемых схем.

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

а) б)

Рисунок 1 - Сравнительный анализ вероятностей: а) сохранения базиса для ФПТ элемента (Р1) и элемента 4И-НЕ (Р2); б) сохранения функции при мажоритировании трех элементов ИЛИ-НЕ (Р2) и ФПТ+ элемента (Р1) при Л = 10"7.

В четвертой главе разработан алгоритм реконфигурации отказоустойчивых ПЛИС на основе КМОП элементов с избыточным базисом и алгоритм поиска остаточного базиса таблиц преобразования крупнозернистых ПЛИС. Алгоритм

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

( Начало

Конец

Рисунок 2 — Схема алгоритма реконфигурации.

Для целей диагностики в ПЛИС предлагается использовать известные интерфейсы или способы диагностирования - ЛЖ}, ЬББО, метод параллельно-последовательного самотестирования и т.д. Тогда процедура диагностирования

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

Диагностирование реализовано на основе разработанных контрольных тестов для элементов с избыточным базисом. Для модели однократных константных отказов достаточно теста длиной четыре. По результатам теста дается заключение о техническом состоянии элемента.

Предложен алгоритм поиска остаточного базиса таблиц преобразования крупнозернистых ПЛИС. Данный алгоритм получен на основе анализа внутренней структуры крупнозернистых ПЛИС и позволяет осуществлять поиск имеющихся функциональных возможностей в LUT с отказами, при условии идеальности выходного инвертора или замены инвертора на КМОП элемент с избыточным базисом. Так при любом однократном константном отказе в транзисторной матрице 4-х входовой LUT, возможна реализация функции 3-х переменных.

Пусть задана размерность таблицы преобразования в виде числа входов - п. Обозначим X- / -й вход таблицы преобразования, где i = \...n ; j - номер отказавшего транзистора (нумерация транзисторной матрицы осуществляется сверху вниз, слева направо), причем у' = 1...2"+1 -2 ; q - четность номера транзистора (нечетные номера транзисторов включены при Х, = 1, четные при Xt = 0); m- вид однократного константного отказа транзистора (т = 0 при отказе «0», m-1 при отказе «1») . Тогда алгоритм поиска можно описать следующей последовательностью действий:

1. Проконтролировать техническое состояние LUT с помощью известных методов диагностирования.

2. Если таблица исправна перейти к п. 9 , если не исправна перейти к следующему пункту.

3. Локализовать место и вид отказа (определить номер отказавшего транзистора - j и тип отказа - m ).

4. При успешной локализации места и вида отказа перейти к следующему пункту, в противном случае перейти к п. 8.

5. Определить номер входа, к которому подключен транзистор по формуле

i=hfj\ (13)

6. Рассчитать q по формуле (14)

7. На основании рассчитанного q и определенного m выбрать требуемый вариант реконфигурации по следующим правилам и перейти к п. 9:

7.1 Если q = m = 0, то Xt, =1;

7.2 Если q = 0, т = 1,то Х, =0;

7.3 Если д = 1,т = 0, то Х{ = 0;

7.4 Если q = m -1, то Xi, = 1.

Примечание. При этом LUT способна реализовывать функции /г-1 переменной, рабочими являются входа Xl,X2...XI_x,Xi+v..Xn.

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

9. Установить указатель таблицы преобразования на следующую LUT и повторить действия п. 1-8 для каждой таблицы преобразования ПЛИС.

10. Конец алгоритма.

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

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

А = — -100%.

К

где Р - вероятность сохранения функциональной полноты при однократных константных отказов входов в долях, Ьу - сложность рассматриваемого варианта ПЛИС, при этом считается, что сложность коммутатора во всех случаях одинакова. Значения показателя удельной отказоустойчивости сведены в таблицу 1. Из нее следует, что применение КМОП элементов с избыточным базисом в качестве базисных ячеек ПЛИС более целесообразно, так как данные элементы при сопоставимых аппаратных затратах имеют более высокие вероятности сохранения функциональной полноты.

Таблица 1 - Значения показателя относительной вероятности сохранения функциональной полноты для различных базисных структур и вентилей_

№ Базисная структура Р Ь,тр А,тр 1

1 КМОП транзисторы (элемент 4И-НЕ) 0,4 472 8,47

2 КМОП транзисторы (элемент ФПТ) 0,8 472 16,94

3 Транзисторные пары (элемент 4И-НЕ) 0,4 344 11,62

4 Транзисторные пары (элемент ФПТ) 0,8 344 23,25

5 Ячейки БМК (элемент 4И-НЕ) 0,4 328 12,19

6 Ячейки БМК (элемент ФПТ) 0,8 328 24,39

7 Готовые элементы 4И-НЕ 0,4 88 45,45

8 Готовые ФПТ элементы 0,8 88 90,9

9 Готовые ФГГГ+ элементы 1 160 62,5

В диссертационной работе разработана Марковская модель активно отказоустойчивой логики ПЛИС на основе КМОП элементов с избыточным базисом, учитывающая поток восстановления, вызванный наличием остаточного базиса при отказах. На основании данной модели получены формулы для расчета вероятности безотказной работы. Из них следует, что остаточный базис, который используется для реконфигурации ПЛИС, может увеличивать значение вероятности безотказной работы устройства. Так при интенсивности потока восстановления ¿и21ост =10~5 значение вероятности безотказной работы выше ориентировочно на 15-20 % по сравнению с классическим вариантом ПЛИС с реконфигурацией за счет резервных элементов.

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

Полученные в диссертационной работе методы и алгоритмы внедрены в виде ОКР новых образцов отказоустойчивых электронных регуляторов на основе

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

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

В приложениях представлены: листинг программы для выбора оптимальной структурной схемы надежности отказоустойчивых устройств на ПЛИС на базе КМОП элементов с избыточным базисом; акт внедрения результатов диссертационной работы.

Основные результаты работы и выводы

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

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

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

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

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

1. Тюрин С.Ф., Громов O.A. Базисный элемент программируемых логических интегральных схем//Вестник Ижевского государственного технического университета. - 2010. - №3. - С.122-125.

2. Тюрин С.Ф., Громов O.A., Греков A.B. Функционально-полный толерантный элемент ФІПУ/Научно-технические ведомости СПбГПУ. Сер. Информатика. Телекоммуникации. Управление - 2011. - № 1(115). - С. 24-30.

3. Тюрин С.Ф., Громов O.A., Каменских А.Н. Программный комплекс исследования методов повышения надежности// Вестник Ижевского государственного технического университета. — 2012. - №2. - С. 153-156.

Другие статьи и материалы конференций

4. Тюрин С.Ф., Громов O.A. Моделирование отказов функционально-полного толерантного элемента на основе КМОП транзисторов// Радіоелектронні та комп'ютерні системи. - 2010. -№5. -С.247-250.

5. Громов O.A. Функционально-полный толерантный элемент// Сборник конкурсных научно-исследовательских работ аспирантов и молодых ученых в области стратегического партнерства вузов и предприятий радиоэлектронной промышленности. СПб: Издательство СПбГЭТУ «ЛЭТИ». - 2010. - С. 67-72.

6. Громов O.A. Отказоустойчивая программируемая логическая интегральная схема на основе функционально-полных толерантных элементов //Наука сегодня: теоретические аспекты и практика применения: сб. науч. тр. по материалам Междунар. заоч. науч. - практ. конф. - Тамбов: Изд-во ТРОО «Бизнес. Наука. Общество», 2011. -Ч. 5. - С. 45-52.

7. Громов O.A. Методика синтеза и оценки сложности элементов, сохраняющих реализуемую булеву функцию при отказах и сбоях// Научные исследования и инновации. - 2012. - Т.6, № 1-4. - С. 95-105.

8. Тюрин С.Ф., Громов О А. Синтез LUT ПЛИС в функционально полном толерантном базисе //Радіоелектронні та комп'ютерні системи. - 2012. - № 5.-С.11-16.

9. Тюрін С.Ф., Громов O.A., Греков A.B., Понуровскій І.С. Адаптация FPGA до відмови логіки// Радіоелектронні і комп'ютерні системы. - 2013. - № 1(60). - С. 150-156.

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

11. Тюрин С.Ф., Громов O.A. Функционально-полный толерантный элемент: пат. РФ № 2438234; опубл. 27.12.2011, Бюл. №36

12. Тюрин С.Ф., Громов O.A., Греков A.B. Функционально-полный толерантный элемент: пат. РФ№ 2449469; опубл. 27.04.2012, Бюл. № 12.

Подписано в печать 30.05.2013. Формат 60x90/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 979/2013.

Отпечатано с готового оригинал-макета в типографии издательства Пермского национального исследовательского политехнического университета. Адрес: 614990, г. Пермь, Комсомольский пр., 29, к. 113. Тел. (342) 219-80-33.

ПЕРМСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

042СИ 359уОУ

Громов Олег Александрович

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

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

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Тюрин С.Ф.

Пермь-2013

СОДЕРЖАНИЕ

Определения, обозначения и сокращения........................................................5

ВВЕДЕНИЕ..........................................................................................................7

1 АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ПОВЫШЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ ЦИФРОВЫХ СИСТЕМ И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ...........................................................................17

1.1 Анализ объекта исследования - программируемых логических интегральных схем и средств повышения их отказоустойчивости..........17

1.1.1 Классификация программируемых логических интегральных схем .......................................................................................................................17

1.1.2 Архитектурные особенности различных типов ПЛИС..................22

1.2 Анализ моделей отказов современных интегральных микросхем.....26

1.3 Методы и средства повышения отказоустойчивости программируемой логики..............................................................................33

1.3.1 Методы, предлагаемые производителями ПЛИС...........................33

1.3.2 Современные подходы к повышению отказоустойчивости..........35

1.3.3 Обзор методов повышения отказоустойчивости............................37

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

1.5 Выводы по главе 1....................................................................................41

2 РАЗРАБОТКА МЕТОДА СИНТЕЗА ЭЛЕМЕНТОВ С ИЗБЫТОЧНЫМ БАЗИСОМ, СОХРАНЯЮЩИХ ФУНКЦИОНАЛЬНУЮ ПОЛНОТУ ПРИ КРАТНЫХ ОТКАЗАХ......................................................................................44

2.1 Разработка КМОП схемы классического ФПТ элемента....................44

2.2 Разработка КМОП схемы двойственного ФПТ элемента....................47

2.3 Разработка метода синтеза элементов сохраняющих функциональную полноту при кратных отказах.......................................................................49

2.4 Моделирование предлагаемых схем ФПТ и двойственного ФПТ элементов........................................................................................................54

2.5 Сравнительный анализ элементов с избыточным базисом и классических базисов.....................................................................................60

2.6 Выводы по главе 2....................................................................................64

3 РАЗРАБОТКА МЕТОДА СИНТЕЗА ЭЛЕМЕНТОВ С ИЗБЫТОЧНЫМ БАЗИСОМ, СОХРАНЯЮЩИХ БАЗИСНУЮ БУЛЕВУ ФУНКЦИЮ ПРИ КРАТНЫХ ОТКАЗАХ......................................................................................65

3.1 Разработка КМОП схемы элемента сохраняющего функцию при кратных отказах..............................................................................................65

3.2 Разработка КМОП схемы двойственного элемента сохраняющего функцию при кратных отказах.....................................................................68

3.3 Разработка метода синтеза элементов сохраняющих функцию при кратных отказах..............................................................................................70

3.4 Моделирование схем КМОП элементов с избыточным базисом, сохраняющих вид функции...........................................................................78

3.5 Сравнительный анализ элементов с избыточным базисом и классических базисов.....................................................................................83

3.6 Выводы по главе 3....................................................................................87

4 РАЗРАБОТКА АЛГОРИТМА РЕКОНФИГУРАЦИИ ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМ........89

4.1 Разработка контрольных тестов для элементов с избыточным базисом ..........................................................................................................................89

4.2 Разработка алгоритма диагностирования программируемых логических интегральных схем, допускающих перерывы в работе.........93

4.3 Разработка алгоритма диагностирования программируемых логических интегральных схем, не допускающих перерывы в работе....97

4.4 Разработка алгоритма реконфигурации программируемых логических интегральных схем.......................................................................................100

4.5 Разработка алгоритма поиска остаточного базиса крупнозернистых программируемых логических интегральных схем..................................106

4.6 Методика оптимизации структурной схемы надежности..................110

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

5 ОЦЕНКА ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ КМОП ЭЛЕМЕНТОВ С ИЗБЫТОЧНЫМ БАЗИСОМ..........................................................................115

5.1 Оценка эффективности применения КМОП элементов с избыточным базисом в отказоустойчивых элементах памяти.......................................115

5.2 Элементы с избыточным базисом в структуре конфигурируемых логических блоков программируемых логических интегральных схем 119

5.3 Оценка отказоустойчивости КМОП логических элементов, реализованных на различных ПЛИС.........................................................123

5.4 Оценка отказоустойчивости логических элементов в крупнозернистых ПЛИС..............................................................................130

5.5 Разработка Марковской модели программируемой логической интегральной схемы на основе КМОП элементов с избыточным базисом ........................................................................................................................131

5.6 Выводы по главе 5..................................................................................138

ЗАКЛЮЧЕНИЕ................................................................................................140

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

Приложение А..................................................................................................1 52

Приложение Б..................................................................................................154

Приложение В..................................................................................................178

Определения, обозначения и сокращения

ALM - англ. Adaptive Logic Module - адаптивный логический модуль. ASIC - англ. Application-Specific Integrated Circuit - интегральная схема для специфического назначения (заказная интегральная схема). CPLD - англ. Complex Programmable Logic Device - сложное программируемое логическое устройство.

EEPROM - англ. Electrically Erasable Programmable Read-Only Memory -электрически стираемое перепрограммируемое постоянное запоминающее устройство.

FPGA - англ. Field-Programmable Gate Array - программируемые пользователем вентильные матрицы.

JTAG - англ. Joint Test Action Group - специализированный аппаратный интерфейс на базе стандарта IEEE 1149.1, предназначенный для подключения сложных цифровых микросхем или устройств уровня печатной платы к стандартной аппаратуре тестирования и отладки. LUT - англ. Look Up Table - оперативное запоминающее устройство. PAL - англ. Programmable Arrays Logic - программируемая матричная логика.

PIP - англ. Programmable Interconnection Point - программируемые точки связи (ПТС).

SOPC - англ. System On Programmable Chip - системы на программируемом кристалле.

SRAM - англ. Static Random Access Memory - статическое оперативное запоминающее устройство. AJIM - адаптивный логический модуль. БИС - большая интегральная схема. БМК - базовые матричные кристаллы. ВБР - вероятность безотказной работы. ДНФ - дизъюнктивная нормальная форма. ИМС - интегральная микросхема.

КЛБ - конфигурируемые логические блоки.

КМОП - комплементарный металл оксид полупроводник.

КНФ - конъюнктивная нормальная форма.

ЛИЗМОП - полевой металл оксид полупроводник транзистор с лавинной инжекцией заряда. ЛЭ - логический элемент. ОЗУ - оперативное запоминающее устройство. ПЗУ - постоянное запоминающее устройство. ПЛИС - программируемая логическая интегральная схема. САПР - система автоматизированного проектирования. СДНФ - совершенная дизъюнктивная нормальная форма. СБИС - сверхбольшая интегральная схема. СКИФ - совершенная конъюнктивная нормальная форма. СОЗУ - статическое оперативное запоминающее устройство. ФПТ - функционально-полный толерантный элемент, элемент с избыточным базисом, сохраняющий функциональную полноту. ФПТ+ - элемент с избыточным базисом, сохраняющий базисную булеву функцию.

ВВЕДЕНИЕ

Актуальность работы. В современных цифровых устройствах используется большое количество интегральных микросхем сверхбольшой степени интеграции. К ним можно отнести микроконтроллеры, микропроцессоры, цифровые процессоры обработки сигналов и программируемые логические интегральные схемы (ПЛИС) [1]. ПЛИС это универсальный базис для проектирования цифровых устройств любого уровня сложности, который в настоящее время содержит встроенную память, блоки умножения, умножители частоты и прочие встроенные блоки [2,3]. Спектр применения этих ИМС очень разнообразен. Они активно применяются и в аппаратуре специального назначения [4-7]. К устройствам специального назначения можно отнести изделия, применяемые в области авионики, космонавтики, управления ответственными промышленными объектами, например, атомными электростанциями. В таких устройствах очень большое внимание уделяется надежности элементной базы. В том числе остро стоит проблема повышения отказоустойчивости программируемых интегральных схем[8]. Важность данной проблемы подтверждается вниманием к ней со стороны правительства РФ. В частности была создана федеральные целевая программа "Развитие электронной компонентной базы и радиоэлектроники" на 2008 - 2015 годы [9], в которой подчеркивается необходимость создания новой элементной базы, и есть раздел посвященный созданию военной и специальной электронной компонентной базы. Кроме того в указе Президента РФ от 7 июля 2011 года № 899 говорится об исключительной важности разработки критических технологий для создания высоконадежной специальной техники, что имеет существенное значение для развития страны [10].

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

ПЛИС фирмы Actel [6], которые содержат троированные триггеры с мажоритарной схемой подавления сбоев и ПЛИС фирм Atmel, Altera и Xilinx, с возможностью проведения частичной динамической реконфигурации [1113], что позволяет в рамках одной микросхемы реализовывать многоканальные системы. Не смотря на рост интереса к рынку отказоустойчивых ПЛИС число их пользователей все еще не слишком велико и производители не видят коммерческой выгоды в проектировании отказоустойчивых кристаллов.

Поэтому объектом исследования являются программируемые логические интегральные схемы.

Большинство исследований, которые проводятся в настоящее время, в области повышения отказоустойчивости ПЛИС направлены на решение проблемы парирования отказов на уровне проектируемой платы и на системном уровнях [14,15,16]. Следовательно, данные работы строятся исходя из принципа, что ПЛИС не надежное средство проектирования. В таких работах, как правило, разрабатываются алгоритмы реконфигурации ПЛИС и парирование отказов происходит за счет резерва. Ряд работ посвящены изменению архитектуры программируемых логических интегральных схем.

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

Вопросы исследования надежности цифровой аппаратуры и ПЛИС освещены в работах ведущих отечественных и зарубежных ученых М.Ф. Каравая [17-19], Ю.А. Степченкова [20,21], B.C. Харченко [22,23], В.И. Хаханова [24,25], Z. Yervant [26], В.А. Твердохлебовым [27], A. Doumar [14], С.С. Уварова [15], F. Meyer [28], N. Hastie [29], J.Emmert [30], С.Ф. Тюрина [31-34] и т.д.

В 1996 г. С. Ф. Тюриным была предложена концепция функционально-полных толерантных элементов (ФПТ) [31]. Особенностью данных элементов является сохранение ограниченной функциональности при отка-

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

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

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

Поэтому предметом исследования являются отказоустойчивые программируемые логические интегральные схемы на основе КМОП элементов с избыточным базисом.

Цель работы - повышение отказоустойчивости программируемых логических интегральных схем на основе КМОП элементов с избыточным базисом.

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

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

2. разработка метода синтеза КМОП логических элементов с избыточным базисом, сохраняющих базисную булеву функцию при к-кратных отказах;

3. разработка алгоритма реконфигурации отказоустойчивых ПЛИС на основе КМОП элементов с избыточным базисом;

4. разработка алгоритма поиска остаточного базиса таблиц преобразования LUT крупнозернистых ПЛИС.

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

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

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

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

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

- предложен алгоритм поиска остаточного базиса таблиц преобразования крупнозернистых ПЛИС, новизна которого в том, что он позволяет

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

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

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

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

- алгоритм реконфигурации отказоустойчивых ПЛИС на основе КМОП элементов с избыточным базисом, с подбором остаточного базиса образованного однократными константными отказами входов и транзисторов;

- алгоритм поиска остаточного базиса таблиц преобразования крупнозернистых ПЛИС.

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

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

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

Реализация результатов работы. Полученные в диссертационной работе мет�