Логические элементы с избыточным базисом

Размещено на http://www.allbest.ru/

УДК 519.1(075.8)+510.6(075:8)

Логические элементы с избыточным базисом

С.Ф. Тюрин

Пермский государственный национальный исследовательский университет

Россия, 614990, Пермь, ул. Букирева, 15

tyurinsergfeo@yandex.ru; 8-952-32-02-510



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

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

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



Redundancy logical elements

S. F. Tyurin

Perm State University, Russia, 614990, Perm, Bukirev st., 15

tyurinsergfeo@yandex.ru; 8-952-32-02-510

In the work are summed up the sums more than 30 years of the flight activity of the author in the region of the programmed logic, including with the use of redundancy logical elements - functional complete tolerant ([FCT]) elements.

Key words: logic element with the redundancy basis - functional complete tolerant ([FCT]) element; the programmed logic integral circuit (PLD); reliability; failure resistance.



В сентябре олимпийского 1980 г. автор этих строк впервые серьёзно взялся за паяльник в скромной должности начальника отделения (инженерная должность) кафедры наземного проверочно-пускового электрооборудования ПВКИУ - Пермского военного командно-инженерного училища - и начал долгий и трудный путь по дороге, мощённой реле, транзисторами, интегральными микросхемами и пр. В 1982 г. на кафедре появились первые микропроцессоры фирмы Intel -8080А. Программной реализации логических функций и автоматов в этом новом логическом базисе была посвящена кандидатская диссертация, на подготовку которой ушло целых 10 лет. За это время автор вырос до преподавателя, старшего преподавателя, доцента. В 1996 г. автор стал начальником этой кафедры, которая стала называться кафедрой систем диагностирования и управления пуском ракет, а в 1997 г. - Заслуженным изобретателем РФ.

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

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

С благословления лаборатории перспективных архитектур ИПИ РАН (Филин А.В., Степченков Ю.А.), которая, продолжая дело Варшавского В.И. в области апериодических, самосинхронных цифровых автоматов, продвигала идеи КВН - компьютера высокой надёжности, естественно надёжного компьютера ЕНК, в "лихие" 90-е годы автором была сформулирована концепция так называемого функционально-полного толерантного (ФПТ) элемента, элемента с избыточным базисом, сохраняющего функциональную полноту в смысле теоремы (критериев) Поста при заданной модели отказов, которая в начале ограничивалась авторами моделью константных отказов входов.

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

В [4] описан разработанный метод построения вектора ФПТ функции и получен такой вектор четырёх и пяти переменных с учётом заданной классической модели однократных константных отказов входов. Это отказы типа stuck-at-0 - константный "0"(0) stuck-at-1 - константная "1"(1) [5].

Получены уравнения сохранения функциональной полноты для функций четырёх и пяти переменных и показано, что использование соответствующих избыточных (ФПТ) базисов четырёх переменных 2ИЛИ-2И-НЕ, 2И-2ИЛИ-НЕ

(1)

(2)

как своего рода "комбинирование" и "укрупнение" базиса по сравнению с традиционными базисами И-НЕ, ИЛИ-НЕ позволяет для широкого класса логических функций получать более простые и более быстродействующие схемы цифровых комбинационных автоматов [4]. При этом как таковой избыточности нет, она может возникать, как правило, при реализации простых функций типа "Чистое" И, "Чистое" ИЛИ.

Остаточные базисы базисов (1), (2) при модели однократных константных отказов входов элементов имеют вид

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

В конце 90-х г. XX в. предполагалось, что использовать такую толерантность возможно в перестраиваемых, реконфигурируемых в процессе эксплуатации структурах типа программируемых логических схем (ПЛИС (PLD), тогда назывались ПЛУ - программируемые логические устройства), которые как бы априори содержат все необходимые средства для диагностирования и адаптации к фактическому техническому состоянию элементов, например в виде [6]. В процессе производства микросхем такой подход также мог бы быть полезным - для повышения процента "выхода годных" (yield rate).

В XXI в. в военной технике, в авионике, космонавтике, в системах управления ответственными объектами - и в других критических областях применения, несмотря на постоянно возрастающее качество производства интегральных микросхем, большое внимание продолжает уделяться надежности элементной базы, в том числе созданию отказоустойчивых ПЛИС [7, 8]. Но часто производители не видят коммерческой выгоды в проектировании отказоустойчивых кристаллов в силу небольших объёмов заказов. В областях ответственного применения, например в военной, продолжают превалировать отказоустойчивые специализированные дорогостоящие решения на основе базовых матричных кристаллов (БМК). Тем не менее выделяются однократно программируемые радиационно-стойкие ПЛИС фирмы Actel [9], содержащие сбоеустойчивые троированные триггеры с мажоритарной схемой, ПЛИС фирм Atmel, Altera и Xilinx [10, 11], в которых в рамках одной микросхемы уже создана возможность реализации многоканальных систем, систем со структурным резервированием.

Более дешёвые, чем заказные микросхемы (ASIC - application-specific integrated circuit), ПЛИС (1,2 млн вентилей) были применены даже на марсоходе "Куриосити", где было введено для повышения надёжности традиционное структурное резервирование, что позволило реализовать спящий режим основных компьютеров с целью экономии электроэнергии [12].

Как отмечалось ведущими специалистами в области ПЛИС, проблема восстановления логики [14] при отказах и сбоях стала всё более обостряться в силу её специфики в отличие, например, от восстановления памяти [15], которая относительно просто диагностируется, и можно достаточно простыми средствами (по адресным сигналам) отключать отказавшие блоки, хотя площадь кристалла, занимаемая логикой по сравнению с памятью весьма невелика. Автор прекрасно помнит микросхемы памяти 80-х гг., в которых к номеру приписывался индекс А, В, С…. Как оказалось, этот номер означал отключение одного из нескольких (их тогда было 11-12) адресных входов - подачу некоторой константы, тем самым отключалась половина матрицы памяти, в которой был найден производственный дефект.

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

Определения функционально-полных толерантных булевых функций четырёх аргументов для комбинированной модели отказов

Автора часто справедливо упрекали за то, что рассмотренная модель однократных константных отказов входов ФПТ элемента, который рассматривался как бы абстрактно -- на функциональном уровне, без раскрытия внутренней структуры, якобы не соответствует современным реалиям. Тем не менее оказалось, что такая модель всё-таки применяется и в XX в. в системах так называемого встроенного сервисного обслуживания (I-IP Infrastructure Intellectual Property), в том числе и в стандарте IEEE 1500 [15]. Автор соглашался, что модель константных отказов не покрывает относительно большую часть неисправностей больших интегральных схем (БИС), имеются и другие достаточно широкие модели, например модель замыканий (Bridging Faults) [17].

Поэтому в [18] была предпринята попытка исследования более реалистичной, как их убедили, комбинированной модели с учётом отказов типа "Замыкания с доминированием (Dominant)", "Монтажное И, ИЛИ" (Wired AND, OR) "Монтажное И, ИЛИ с доминированием (Dominant AND/ OR) " и учтена при формировании уравнения сохранения функциональной полноты для четырёх переменных.

Такая модель отказов имеет следующие основные особенности. Например, при замыкании переменных х1 и х2 с преобладанием х1 останутся только наборы, соответствующие значению х1 - вместо 01 для х1 и х2 будет набор 00, вместо 10 - 11 и так далее. В случае моделей "Монтажное И, ИЛИ" двух входов - соответствующие входы заменяются их конъюнкцией (дизъюнкцией). Если же имеется доминирование - то соответствующий вход остаётся неизменным.

Полученные решения нового уравнения функциональной полноты имеют вид

; ;;

В отличие от модели однократных константных отказов, где было 20 функций, получено всего 6 ФПТ функций, представленных в табл. 1.

Таблица 1 - ФПТ функции для комбинированной модели отказов

№	ФПТ функция
1
2
3
4
5
6

Таким образом, базисы (1), (2) остались в силе и для модели замыканий двух переменных. То есть толерантность сохранялась и при модели замыканий - без замыканий выходов с входами и, конечно, без учёта увеличения возможных задержек сигналов.

Но оставались не исследованными ключевые вопросы сохранения функциональной полноты на транзисторном уровне - для внутренних отказов логического элемента (вентиля) - КМДП транзисторов (stuck-closed transistor - постоянно закрытый, stuck-open transistor - постоянно открытый) [19, 20].

Толерантность базиса относительно отказов КМДП транзисторов

С начала "нулевых" и особенно в последние годы автор не без влияния работ по реализации самосинхронных схем "в транзисторах" - на базовых матричных кристаллах - БМК, проводимых в ИПИ РАН группой Степченкова Ю.А., сосредоточился на транзисторных реализациях избыточных базисов [21…23], в которых при модели отказов одного КМДП транзистора функциональная полнота сохраняется, например, для КМДП структур 2ИЛИ-2И-НЕ, 2И-2ИЛИ-НЕ (рис. 1).

Рис. 1. Схемы элементов с избыточным базисом - ФПТ элементов (1)-FCT1 (а) и (2) FCT2 (б) на основе КМДП транзисторов VT1-VT8

Такие структуры характеризуются наличием двух подсхем - подключения источника питания (z+) и двойственной ей схемы подключения шины "ноль вольт" (z-), которые описываются выражениями (11), (12):

, (11)

, (12)

, (13)

. (14)

Несмотря на то, что при таких отказах нарушается ортогональность функций (z+), (z-) - т. е. на некоторых наборах одновременно могут быть подключены либо обе шины, либо ни одной, чего не должно быть при нормальном функционировании, всегда возможно путём подбора настроить элемент на реализацию остаточного базиса, в отличие от эквивалентного по числу транзисторов элемента 4И-НЕ.

Так, при отказе четвёртого транзистора - "постоянно закрыт" (Т 4.0) на рис. 1а остаточный базис - "половинный" и соответствует функции (z+):

. (15)

При этом функция (z-) не изменяется:

, (16)

но на наборах 1, 2, 3 не подключается ни одна из шин. Для обеспечения работы элемента необходимо "нейтрализовать" конъюнкцию

, (17)

что требует выполнения условия:

. (18)

Таким образом, вероятность сохранения базиса ФПТ (FCT) элемента при экспоненциальной модели отказов (рис. 1) равна

. (19)

Эквивалентный по числу транзисторов КМДП элемента 4И-НЕ описывается выражениями

, (20)

. (21)



Такой элемент (4NAND) не сохраняет функциональную полноту при отказах транзисторов, которые приводят к тождественным нулю и единице в выражениях (20), (21). Поэтому для экспоненциальной модели отказов вероятность сохранения базиса у 4 И-НЕ очевидно меньше:

. (22)

Сравнение вероятностей сохранения базиса при отказах транзисторов для элемента с избыточным базисом (Р1) и элемента 4И-НЕ (Р2) в зависимости от времени представлено на рис. 2:

Рис. 2. Сравнение вероятностей сохранения базиса при отказах транзисторов для элемента с избыточным базисом (Р1) и элемента 4И-НЕ (Р2) для интенсивности отказов одного транзистора 1/час

Таким образом, интенсивность отказов "базисности" элемента с избыточным базисом 1

(23)

значительно снижается по сравнению с интенсивностью отказов элемента 4И-НЕ, хотя и увеличивается со временем (рис. 3).

Рис. 3. Сравнение интенсивностей отказов "базисности" элемента с избыточным базисом (1) и элемента 4И-НЕ (2) для интенсивности отказов одного транзистора 1/час

Также было установлено, что сложность избыточного базиса для толерантности к -константным отказам можно описать выражением

. (24)

Так, для толерантности к двум отказам предложены базисы, реализуемые 18-ю транзисторами:

, (25)

. (26)

Очевидно, что при любом двукратном отказе останется по меньшей мере одна конъюнкция (дизъюнкция).

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

Так, для сохранения базисной функции 2ИЛИ-НЕ при модели однократных константных отказов необходимо выражение



. (27)

Легко видеть, что в случае четырёхкратной избыточности

(28)

функция ИЛИ-НЕ сохранится при любом однократном константном отказе.

Такой элемент [24, 25], содержащий 16 КМДП транзисторов так же, как и (25), может быть использован как сложный (восьми переменных):

(29)

- в условиях отсутствия отказов и отказоустойчивый (двух переменных) - в специальной ответственной аппаратуре.

Для сохранения базисной функции 2И-НЕ при модели однократных константных отказов может быть использован элемент

, (30)

т. е.. (31)

Дальнейшим развитием подхода может быть сохранение более сложного и более эффективного ФПТ базиса [6, 7] - для этого необходима функция

(32)



С учётом того что при отказе одного транзистора не изменяется ни сама функция (27), ни двойственная ей, получим вероятность безотказной (бессбойной) работы такого избыточного элемента ФПТ+:

. (33)

Сравним (33) с вероятностью безотказной работы элемента 2И-НЕ:

. (34)

Результаты представлены на рис. 4.

Рис. 4. Сравнение вероятностей сохранения базиса при отказах транзисторов для элемента с избыточным базисом (Р1) и элемента 2И-НЕ (Р2) 1/час

Получается существенный выигрыш на значительном временном интервале. Попробуем сравнить такой вариант с троированием (мажоритированием). При мажоритировании трех элементов 2И-НЕ мажоритарной схемой из таких же элементов (требуется 6 элементов - 24 транзистора, и это увеличивает задержку на 4 элемента) получаем:



(35)

Если мажоритаров три (мажоритируются еще и сами мажоритары):

(36)

Сравнение вероятностей сохранения базиса при отказах транзисторов для элемента с избыточным базисом (Р1), троированного элемента 2И-НЕ с мажоритарной схемой (Р2), троированного элемента 2И-НЕ с троированной мажоритарной схемой (Р3) и элемента 2И-НЕ представлено на рис. 5.

Рис. 5. Сравнение вероятностей сохранения базиса при отказах транзисторов для элемента с избыточным базисом (Р1), троированного элемента 2И-НЕ с мажоритарной схемой (Р2), троированного элемента 2И-НЕ с троированной мажоритарной схемой (Р3) и элемента 2И-НЕ

Оказывается, простое мажоритирование элемента не дает выигрыша в вероятности безотказной работы - Р2 на рис. 5. Таким образом, в области достаточно больших значений времени работы за счет введенной избыточности имеется значительный выигрыш в вероятности безотказной работы ФПТ+ элемента по сравнению с элементом 2И-НЕ.

Применение элементов с избыточным базисом для повышения надёжности "мелкозернистых" ПЛИС

На автора оказало и оказывает огромное влияние участие в ежегодной международной научно-технической конференции DESSERT "Гарантоспособные (надежные и безопасные) системы, сервисы и технологии", душой и сердцем которой является профессор В.С.Харченко из ХАУ - Харьковского национального аэрокосмического университета (Украина), с которым С.Ф. Тюрин начал сотрудничество ещё в приснопамятном "перестроечном" 1985 г. На этой же конференции произошло знакомство с профессорами М.Ф.Караваем (ИПУ РАН), В.А. Твердохлебовым (Институт точной механики проблем управления РАН, Саратов), В.И. Хахановым (Украина, Харьков, Харьковский институт радиоэлектроники - ХИРЭ) и др.

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

Такой "саморемонт" логики возможен при условии сохранения базиса отказавшими элементами. Можно использовать эти элементы как новые базисы, а можно восстанавливать исходный базис. Но для восстановления необходима соответствующая диагностика, кроме того, для восстановления одного элемента надо несколько отказавших. Тем более не все отказавшие элементы сохраняют базис. Исследованию этого вопроса была посвящена работа [26].

Так, например, показано если остаются базисы ,, то для получения исходного базиса (1) необходимо выражение (37) т.е. требуется 4 элемента с таким базисом - 2 для реализации двух конъюнкций ,, 1 для двухместной операции ИЛИ-НЕ и 1 - инвертор.

Если имеется один элемент с одним из базисов , , , , необходима декомпозиция, например, вида , (38) а это 2 элемента с базисом , + 1 элемент - всего 3.

Легко видеть, что даже в случае наличия максимальных базисов , , , для восстановления необходимо минимум 3 элемента.

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

Восстановление логики для ПЛИС, допускающих перерывы в работе

Обычно ПЛИС используют не все имеющиеся ресурсы. Допустим, как рекомендуют производители, в исходном состоянии задействовано около 70% логики ПЛИС. В случае отказов оставшиеся 30% в принципе могут быть использованы для замены 30% отказавших путём загрузки нового файла конфигурации. Далее, если считать, что произошли отказы, позволяющие использовать отказавшие элементы, и для восстановления одного полного базиса необходимо три элемента - получаем ещё около 10% "самовосстановленного" резерва. Таким образом, избыточность базиса позволяет увеличить логические резервы ПЛИС.

Для восстановления ПЛИС с одноканальной логикой в некритических приложениях, которые допускают перерывы в работе, необходимы процедуры диагностики (например, с использованием интерфейса JTAG), формирования и загрузки файлов конфигурации - необходим конфигурационный контроллер, который осуществляет и обычную загрузку ПЛИС типа FPGA. При этом предполагается, что логика ПЛИС реализована на основе КМДП элементов с избыточным базисом. Такие ПЛИС классифицируются как "мелкозернистые" [27]. В этом случае оценивается коэффициент готовности, который может увеличиваться за счёт предлагаемого "самовосстановления".

Граф состояний невосстанавливаемой ПЛИС, точнее восстанавливаемой путём замены микросхемы, представлен на рис. 6.

Рис. 6. Граф Марковского процесса для ПЛИС, восстанавливаемой путём замены микросхемы

Найдем коэффициент готовности для системы, представленной на рис. 6:

(46)

В то же время граф состояний восстанавливаемой ПЛИС имеет дополнительное состояние, не приводящее к отказу системы (рис. 7):



Рис. 7. Граф Марковского процесса системы - ПЛИС на основе элементов с избыточным базисом и конфигурационного контроллера

Коэффициент готовности системы с дополнительным восстановлением в процессе эксплуатации на основе остаточных базисов логики:

(47)

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

(48)

при заданных ограничениях или достижения требуемого показателя

(49)

при минимизации объёма дополнительной памяти или времени реконфигурации.

Восстановление логики для ПЛИС, не допускающих перерывы в работе

При пассивной отказоустойчивости [28] (а выше описана активная отказоустойчивость), которая применяется там, где недопустимы даже кратковременные перерывы в работе системы, отказы и сбои маскируются системой, которая продолжает функционирование и при возникновении определённого количества отказов. Это требует значительной избыточности - мажоритирования 2 из 3 - рис. 9 (парируется 1 отказ - в одном из 3 каналов, то есть отказ 1 канала), 3 из 5 (парируется отказ 2 каналов) и т.д. Термин "мажоритирование" используется разработчиками высоконадёжных систем, в том числе "военных" систем, например бортовых и наземных цифровых вычислительных комплексов (БЦВК, НЦВК) [28], и он представляется точней термина ГОСТ "резервирование один к двум" - кратность резерва [29], поскольку ГОСТ фиксирует отношение числа резервных элементов к числу резервируемых ими элементов, выраженное несокращенной дробью, а в структуре рис. 8 имеется в виду горячее, постоянное резервирование, когда все три канала решают одну и ту же задачу, т. е. эти каналы одновременно являются и основными и резервными.

Основные методы пассивной отказоустойчивости, ориентированные на восстановление логики ПЛИС, рассмотрены в [30].

Рис. 8. Мажоритирование

Для мажоритарной системы (рис. 8) вероятность безотказной работы мажоритарной схемы (мс) оценивается выражением, учитывающим интенсивность отказов каналов и мажоритарного элемента (мэ) (50):

. (50)

Для повышения вероятности безотказной работы троируют и сами мажоритарные элементы:

.(51)

Для ещё большего повышения вероятности безотказной работы используют "глубокое" мажоритирование. Мажоритируются отдельные "слои" каналов:

(52)

где - вероятность безотказной работы глубоко мажоритированной структуры из -троированных слоёв, - интенсивность отказов k-го троированного слоя, - интенсивность отказов мажоритарного элемента, - время работы.

Примем допущение, что - интенсивность отказов всей структуры - как бы "разбивается" на одинаковых частей, тогда

(53)

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

Применим для описания такого восстановления в каждом канале систему со скользящим резервированием [26, 31], в которое введём частичное "самовосстановление" (подраздел 3). Таким образом получим пассивно-активную отказоустойчивую систему - рис. 9.

Рис. 9. Пассивно-активная отказоустойчивость - "глубоко" мажоритарное скользящее резервирование с восстановлением на основе элементов с избыточным базисом

В первом приближении (для восстановления из m отказавших - выражение (39)) получаем выражение для вероятности безотказной работы системы со скользящим резервированием и восстановлением - СССРВ:



В случае дополнительных затрат на восстановление оказавших в получаем:

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

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

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

Затраты на реконфигурацию логики мелкозернистых ПЛИС

Рассмотрим основные варианты реконфигурации элементов, начав с коммутации транзисторов.

1. Коммутация КМОП транзисторов

Такой подход мог быть характерен для первых поколений базовых матричных кристаллов (БМК), программируемых однократно путем изготовления фотошаблона на предприятии-изготовителе [32].

2. Коммутация пар КМОП транзисторов

Такой подход реализован не только в БМК, но и в "мелкозернистых" FPGA, основой логических ячеек которых являются транзисторные пары - SLC (Simple Logic Cells) - различных типов [27].

3. Коммутация ячеек БМК из КМОП транзисторов

Топологические ячейки КМОП БМК содержат от 4 до 10 транзисторов t [32].

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

Коммутация логических элементов

Пример коммутации входных переменных ФПТ элемента с помощью аппаратных средств ПЛИС FPGA представлен на рис. 10.

Рис. 10. Коммутация входных переменных элемента с избыточным базисом - ФПТ элемента

Анализ показывает, что на один вход при мультиплексорах 16-1 и шести-транзисторных ячейках памяти конфигураций SRAM необходим 131 транзистор. Сравним с учётом этого реализации элементов ФПТ, сохраняющих только базис, и ФПТ+, сохраняющих саму функцию.

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

(60)

ФПТ+ элемент имеет 8 входов, отказ одного из них, как и отказ одного транзистора в схемах подключения шин питания, не приводит к изменению функции. Но для реализации ФПТ функции необходимо 4 ФПТ+ элемента, и входов будет 8:

(61)

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

(62)

Результаты сравнения Р1- (62) - 4 элементы ФПТ+ и (60) - один ФПТ - Р2 представлены на рис. 11.

Рис. 11. Сравнение вероятности безотказной работы Р1 - 4 элементы ФПТ+ и Р2 одного ФПТ элемента с учётом затрат на коммутацию при

Рассчитанные значения приведённой сложности k коммутаций на один "логический" транзистор для рассмотренных вариантов указаны в табл. 3. Наибольшим значением k обладает ФПТ+ элемент, однако он реализует в отказоустойчивом варианте только функцию 2-х переменных, но может использоваться и как неотказоустойчивый для реализации функции 8-ми переменных.

Таблица 2 - Приведённая сложность k коммутаций на один "логический" транзистор

№	Вариант реконфигурируемой структуры
1	КМОП транзисторы (элемент 4И-НЕ, элемент ФПТ-8 транзисторов)	472	58
2	Транзисторные пары (элемент 4И-НЕ, элемент ФПТ - 8 транзисторов)	344	42
3	Ячейки БМК (элемент 4И-НЕ, элемент ФПТ - 8 транзисторов)	328	40
4	Коммутируемые элементы 4И-НЕ, ФПТ - 8 транзисторов	88	10
9	Коммутируемые ФПТ+ элементы - 16 транзисторов	160	9

Особенности применения избыточных базисов в крупнозернистых ПЛИС

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

В табл. 2 показано, что "укрупнение" базиса приводит к уменьшению приведённой сложности коммутаций, что бывает в так называемых крупнозернистых ПЛИС.

В крупнозернистых ПЛИС типа FPGA (field-programmable gate array) базис ещё более укрупнён - они содержат конфигурируемые логические блоки [33], состоящие из логических элементов ЛЭ, программируемых локальных и глобальных матриц соединений.

Логический элемент крупнозернистой ПЛИС - это супер избыточный базис, и он строится как постоянное запоминающее устройство ПЗУ (LUT - Look Up Table), представляющее собой для четырех переменных мультиплексор 16-1 (дерево мультиплексоров), входы данных которого настраиваются так называемыми конфигурируемыми ячейками памяти на реализацию одной из 65536 функций [33] - рис. 12.

Рис. 12. Логический элемент крупнозернистой ПЛИС - LUT (Look Up Table, ПЗУ) на 4 адресных переменных A,B,C,D

Для такого логического элемента (рис. 12) сложность с учётом коммутаций ещё больше, чем у вариантов, указанных в табл. 2, и равна 1392 транзистора, а приведённая сложность k коммутаций на один "логический" транзистор ниже, чем у ФПТ+ и составляет 7,28.

Адаптация к отказам транзисторов и адресных входов LUT-4 путём перехода на остаточный базис

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

Рассмотрим возможные случаи отказов транзисторов (рис. 12). Все возможные случаи отказов транзисторов приведены в табл. 3.



Таблица 3 - Адаптация LUT к некоторым однократным константным отказам

Вид отказа	Требуемая перекоммутация	Используемые переменные
VT10	A=0	B, C, D
VT11	A=1	B, C, D
VT170	B=0	A, C, D
VT171	B=1	A, C, D
VT250	С=0	A, B, D
VT251	С=1	A, B, D
VT290	D=0	A, B, C
VT291	D=1	A, B, C
A=0	-	B, C, D
A=1	-	B, C, D
B=0	-	A, C, D
B=1	-	A, C, D
C=0	-	A, B, D
C=1	-	A, B, D
D=0	-	A, B, C
D=1	-	A, B, C

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

Всё хорошо, но последний инвертор в дереве передающих транзисторов, портит всю картину - любой отказ одного из двух транзисторов приводит к невозможности восстановления, то есть приводит к отказу всего LUT. Это "узкое место", "бутылочное горлышко", "игольное ушко", через которое не может в критической ситуации пройти вся огромная функциональность LUT-4 (это 65536 возможных реализуемых функций).

Предлагается "расширить" это узкое место путём ввода элемента ФПТ вместо инвертора, тогда при отказе любого одного транзистора как в верхней, так и в нижней частях КМДП-схемы не приведёт к полному отказу (рис. 13).

Рис. 13. Модифицированная LUT, с ФПТ элементом на выходе

Сравним вероятность безотказной работы элемента 2И-НЕ

(69)

с вероятностью безотказной работы ФПТ элемента в режиме инвертора:

(70)

С учётом того что остальная схема остаётся неизменной (выражения (71), (72)), получаем при увеличении числа транзисторов в LUT на 6 (на 0,004%) даже выигрыш на очень большом временном интервале (рис. 14, рис. 15).



Рис. 14. Сравнение вероятности безотказной работы элемента 2И-НЕ (Р1) и ФПТ элемента в режиме инвертора (Р2)

(71)

(72)

Рис. 15. Сравнение вероятности сохранения базиса LUT (1390 транзистора) с элементом 2И-НЕ (Р1, 2 транзистора) и LUT (1390 транзистора) с ФПТ элементом в режиме инвертора (Р2, 8 транзисторов)

Для исключения возможности обрыва связи от VT 29, 30 к ФПТ элементу на рис. 13 возможно топологическое резервирование, так чтобы единственный обрыв не приводил к отказу всего LUT.

Применение элемента с избыточным базисом в ячейке памяти статической памяти SRAM

С целью обеспечения сбоеустойчивости конфигурационной памяти предложим модифицированную ячейку статической памяти SRAM (рис. 16), заменив инверторы (DD1, DD2) элементами с избыточными базисами - ФПТ элементами, также работающими в режиме инвертора.

Рис. 16. Ячейка памяти SRAM

Сравним предлагаемую модифицированную SRAM схему с троированной ячейкой и мажоритарной схемой на выходе радиационно-стойкой ПЛИС фирмы Actel [34]. Мажоритирование требует 43+2 =14 транзисторов (2 - это "боковые" транзисторы записи-считывания). Схема мажоритирования, то есть реализации функции

, (73)

где a,b,c - выходы трёх ячеек, требует в лучшем случае 12 транзисторов инверсного мажоритара (подобные имеются в библиотеках базовых матричных кристаллов - БМК) и 2 транзисторов для выходного инвертора. Сравним два варианта реализации триггеров по вероятности безотказной работы без учёта «боковых» транзисторов, вероятность безотказной работы которых предполагается одинаковой для двух вариантов. Зададим - интенсивность сбоев транзисторов. Тогда для троированной схемы с одним мажоритаром



, (74)

где - вероятность безотказной работы мажоритара.

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

(75)

Сравнительный анализ вероятности безотказной работы троированного триггера на мажоритарных элементах (Ptt) и триггера на ФПТ элементах (Pfct) показан на рис. 17.

Рис. 17. Сравнительный анализ вероятности безотказной работы троированного триггера на мажоритарных элементах (Ptt) и триггера на ФПТ элементах (Pfct)

Гистограмма сравнения двух реализаций отказоустойчивых ячеек памяти SRAM (1 - аппаратные затраты в транзисторах, 2 - задержка в транзисторах) показана на рис. 18.



Рис. 18. Гистограмма сравнения двух реализаций отказоустойчивых ячеек памяти SRAM (1 - аппаратные затраты в транзисторах, 2 - задержка в транзисторах)

На рис. 18 показана предпочтительность SRAM-ФПТ как по затратам транзисторов, так и по задержке в количестве транзисторов в наиболее "длинном" пути сигнала со входа на выход.



Заключение

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

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

Автор считает, что его скромный труд может внести свою небольшую лепту в дело создания долгожданной новой отечественной элементной базы, на что ориентирована федеральная целевая программа "Развитие электронной компонентной базы и радиоэлектроники" на 2008-2015 гг.

Тематика работы также одобрена и включена в международный образовательный проект ЕС "Fostering Innovations on Green Computing and Communications TEMPUS GreenCo" project number 530270-TEMPUS-1-2012-1-UK-TEMPUS-JPCR.

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

Наконец, в русле исследований проекта TEMPUS - Green Computing and Communications возникает новая задача обеспечения отказоустойчивости ПЛИС FPGA на фоне требований по снижению энергозатрат, повышения энергоэффективности (Green FPGA). В этой связи предложен подход, условно называемый "Green logic", который, может быть, будет представлен в отдельной статье.



Список литературы

1. Тюрин С.Ф. Функционально-полные толерантные булевы функции // Наука и технология в России.1998. № 4. С. 7 -10.

2. Тюрин С.Ф. Синтез адаптируемой к отказам цифровой аппаратуры с резервированием базисных функций // Приборостроение. 1999. № 1. С. 36-39.

3. Тюрин С.Ф. Адаптация к отказам одновыходных схем на генераторах функций с функционально-полными толерантными элементами // Приборостроение. 1999. № 7. С. 32-34.

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

5. Stuck-at fault. [Электронный ресурс]. URL: http://en.wikipedia.org/wiki/Stuck-at_fault (дата обращения: 28.12.2012).

6. Тюрин С.Ф., Несмелов В.А., Харитонов В.А. и др. Программируемое логическое устройство. Патент Р.Ф. № 2146840, опубл. 20.03.2000, Бюл. № 8.

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

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

9. Actel FAQ [Электронный ресурс]. URL: http://www.actel.ru/publics/54-actelfaq.html (дата обращения: 29.12.2012).

10. Цыбин С.А., Быстрицкий А.В., Скуратович С.Н. Архитектура отказоустойчивой ПЛИС емкостью 100 тыс. вентилей // Проблемы разработки перспективных микроэлектронных систем - 2006: сб. науч. тр. / под общ. ред. А.Л. Стемпковского. М.: ИППМ РАН, 2006. С. 376-381.

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

12. Авионика марсохода Curiosity поможет найти следы жизни на красной планете. [Электронный ресурс]. URL: http://www.russianelectronics.ru/leaderr/pechat/60585/ (дата обращения: 20.12.2012).

13. Программируемая логическая интегральная схема [Электронный ресурс]. URL: http://www.russika.ru/ef.php?s=4495 (дата обращения: 28.12.2012).

14. Yervant Z. Gest editors' introduction: Design for Yield and reliability/ Z. Yervant, G. Dmytris // IEEE Design & Test of Computers. May-June 2004. P. 177-182.

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

16. Tyurin S., Kharchenko V. Redundant Basises for Critical Systems and Infrastructures: General Approach and Variants of ImplementationProceedings of the 1st Intrenational Workshop on Critical Infrastructures Safety and Security, Kirovograd, Ukraine 11-13, May, 2011 / Kharchenko V., Tagarev V. (edits), Vol. 2. P. 300-307.

17. Bridging fault. [Электронный ресурс]. URL: http://en.wikipedia.org/wiki/Bridging_fault (дата обращения: 28.12.2012).

18. Тюрин С.Ф., Греков А.В., Громов О.А. Определение функционально-полных толерантных булевых функций четырёх аргументов с учётом модели замыканий переменных // Доклады Академии военных наук. №5 (49), 2011. Саратов, 2011. С. 35-44.

19. Большой англо-русский словарь. [Электронный ресурс]. URL:http://dic.academic. ru/dic.nsf/eng_rus/775498/stuck (дата обращения: 29.12.2012).

20. Asbjoern Djupdal and Pauline C. Haddow. Defect Tolerance Inspired by Artificial Evolution. [Электронный ресурс]. URL: http://www.djupdal.org/asbjoern/publications/djupdal-haddow-isvlsi08_published.pdf (дата обращения: 29.12.2012).

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

22. Тюрин С.Ф., Громов О.А., Греков А.В. Функционально-полный толерантный элемент. Патент РФ № 2449469, опубл. 27.04.2012, Бюл. № 12.

23. Тюрин С.Ф., Громов О.А. Функционально-полный толерантный элемент. Патент РФ 2438234, опубл. 27.12.2011, Бюл. № 36.

24. Тюрин С.Ф., Громов О.А., Греков А.В. Функционально-полный толерантный элемент ФПТ+ // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2011. № 1(115). С. 24-31.

25. Тюрин С.Ф., Громов О.А., Греков А.В., Сулейманов А.А. Функционально-полный толерантный элемент. Решение о выдаче

26. патента на изобретение от 13.03.2013 по заявке № 2012125400/08 (038968) от 19.06.2012.

27. Тюрин С.Ф., Греков А.В., Коржев В.С. Скользящее резервирование с восстановлением на основе элементов с избыточным базисом // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2012. №5(157). С. 38-44.

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

29. Отказоустойчивые вычислительные системы / В.А.Бородин [и др.]. М., 1990. С. 55.

30. ГОСТ 27.002-89. Надежность в технике Основные понятия. Термины и определения. М.: Изд-во стандартов. 1990. 42 с.

31. Тюрин С.Ф., Греков А.В., Громов О.А., Греков А.В., Сулейманов А.А. Анализ методов обеспечения пассивной отказоустойчивости цифровых устройств и систем // Вестник ПГТУ. Электротехника, информационные технологии, системы управления. 2011. № 5. С. 143-153.

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

33. Проектирование ИС на БМК КМДП. [Электронный ресурс]. http:// miet.ru/ content/s/200 (дата обращения:13.02.13).

34. Цыбин С. Программируемая коммутация ПЛИС: взгляд изнутри. [Электронный ресурс]. URL: http://www.kit-e.ru/articles /plis/ 2010_11_56.php (дата обращения: 12.11.12).

35. ПЛИС Actel - основа при реализации "SoC" бортовой аппаратуры. [Электронный ресурс]. URL: http:// www.spigl.wordpress.com/2009/09/16/плис/ (дата обращения: 3.1.2013).

Размещено на Allbest.ru

...