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

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

Балака Екатерина Станиславовна

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

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва-2014

4 АсК 2014

005556154

Работа выполнена в ФГБУН Институте проблем проектирования в микроэлектронике Российской академии наук (ИПГТМ РАН).

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

академик HAH PK Амербаев Внльжан Мавлютинович

Официальные оппоненты: Оцоков Шамиль Алиевич, доктор технических наук,

доцент кафедры вычислительных машин, систем и сетей НИУ «МЭИ»;

Лупин Сергей Андреевич, кандидат технических наук, профессор кафедры вычислительной техники НИУ «МИЭТ»

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «МАТИ -Российский государственный технологический университет имени К.Э. Циолковского»

Защита состоится 25 декабря 2014 года в 11.00 на заседании диссертационного совета Д 002.078.01 по присуждению ученых степеней при ФГБУН Институте проблем проектирования в микроэлектронике Российской академии наук по адресу: 124365, г. Москва, Зеленоград, ул. Советская, д.З.

С диссертацией можно ознакомиться па сайте ИППМ РАН \v\vw. ippm.ru и в библиотеке ИППМ РАН.

Автореферат разослан ■/ " ноября 2014 г.

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

диссертационного совета Д 002.078.01, / /7/

к.т.н., доцент / „' ( М.М. Жаров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность исследования

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

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

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

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

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

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

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

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

2. Анализ и разработка методов и средств повышения сбоеустойчивости ВЭ бимодульной арифметики.

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

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

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

2. Разработана структура ВЭ бимодульной арифметики, арифметический узел которого построен на базе однотипного кодового представления операндов. Это позволило использовать в схеме ВЭ сумматоры одного типа - по модулю (р-1). Получено положительное решение о выдаче патента на полезную модель по заявке № 2014110622/08 (016695).

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

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

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

На защиту выносятся следующие результаты:

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

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

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

Реализация и висдреиие результатов работы

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

Результаты диссертационной работы внедрены и использовались на предприятиях ОАО «НИИЭТ», ОАО «Российские космические системы».

Практическая значимость результатов работы

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

- системы вооружений;

- космическая техника;

- промышленное оборудование;

- телекоммуникационная техника;

- навигационное оборудование.

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

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

Апробация работы

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

• 16-я, 17-я, 19-я Всероссийские межвузовские научно-технические конференции студентов и аспирантов "Микроэлектроника и информатика-2009,2010,2012 гг.

• Всероссийская конференция «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», Ульяновск, Ульяновский государственный технический университет, 2009.

• Ярмарка научно-технических и инновационных идей и проектов молодежи «РИТМ Зеленограда», 2011.

• Международная конференция The 8th Congress of the ISAAC, 2011.

• IV, V, VI Всероссийских научно-технических конференциях «Проблемы разработки перспективных микро- и наноэлектронных систем - 2010, 2012, 2014».

• XX заочная научная конференция Research Journal of International Studies,

2013.

• I Всероссийская научная конференция с элементами научной школы для молодежи «Параллельная компьютерная алгебра» - 2010.

• I Международная конференция «Параллельная компьютерная алгебра и ее приложения в новых инфокоммутационных системах» - 2014.

• Международный конгресс по интеллектуальным системам и информационным технологиям AS-IT 2014.

• Международная конференция СЕЕТ International conference on Advances in Computing , Electronics and Electrical Technology, Malaysia, Kuala Lumpur,

2014.

Публикации

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

Структура и объем работы

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

В Отделе методологии вычислительных процедур И1П1М РАН в части структурирования модулярных вычислений, впервые введено понятие ВЭ модулярной арифметики. Оно позволяет рассматривать архитектуру модулярного процессора как распределенную вычислительную систему. При этом ВЭ представляет собой минимальную автономную вычислительную структуру, реализующую за номинальную единицу времени все операции кольца вычетов Zp , где р, (; = 1,2,..,«) - основание модулярной вычислительной системы (см. рис. 1).

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

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

_шинаданных

\ «| \ /-—|

Арифметический узел по ыодулю

_Пт

уу

озу

7

Выход

Рис. 1. Структура вычислительного элемента модулярной арифметики

Суть рассмотренного им приема сводится к следующему: вводится представление элементов поля СР(/;) посредством нар ^ ¡пс/ |х| ^. где |х| есть

вычет х по тос1(р), 1-\п£1 Ы - соответсвующий вычету Ы индекс,

"I IР 1 I р

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

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

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

«Модульный» блок арифметического устройства представляет собой набор независимых ВЭ-ов бимодульной арифметики по каждому основанию модулярной системы. В данной главе была разработана ВЭ бимодульной арифметики, отличительной чертой которой является аппаратная однотипность выполнения кольцевых операций поля СР(р). Однако, данная структура в классе задач повышения сбоеустойчивости обладает недостатком, а именно использованием модульных сумматоров двух типов по модулям р и (/;-/).

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

Я=■яА(р -о ■- ир)+К - о - н„)

где = ]'' 11 - функция Кронекера, ¿(г/) = 1 — ¿>(и) -кофункция Кронекера. [О, иначе,

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

х=р-1, то вычету |х| ставится в соответствие технически легко распознаваемый

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

Для представления второй компоненты пары операнда, вместо индекса, используется дискретно-логарифметическое представление. Отличие состоит в том, что индексная арифметика определена на множестве отличных от нуля точек поля СР(р). Исскуственно доопределяя значение дискретного логарифма в точке О, переходим к вычислениям в логарифметике поля СР(р).

Такой способ представления пораждается отображением: : СР(р) —> 12. р,

где 1с^н,|;с| =Ярдфс| ) + тс!к|дс| ¿>(|х| ). Тем самым, областью значений дискретного

логарифма в отличие от индекса вычета, является множество Ь7.р = {0, 1, 2,..., р — 2, Лр}- Характерными точками области определения

отображения при любом р и любом выборе и> являются точки 0, 1, ту, /;-/; они,

соответственно, отображаются в точки: Я , 0,1, Ли1. При этом символ

2

сингулярности удобно брать в двоичном формате: Я :=2' — 1.

На основе усовершенствованного представления вычетов бимодульной арифметики в данной главе были разработаны алгоритмы выполнения аддитивных и мультипликативных операций по модулю р. Переход к однотипному кодовому представлению позволил свести выполнение кольцевых операций к выполнению на одном оборудовании, а именно на сумматоре по модулю (р-1). В главе разработанна структура арифметического узла ВЭ бнмодульной арифметики с однотипным кодовым представлением операндов, представленная на рис.2. На соответствующее техническое решение ВЭ бимодульной арифметики подана заявка на полезную модель.

Рис. 2. Структура арифметического узла вычислительного элемента бимодульной

арифметики

Для оценки аппаратных и временных затрат на проектирование арифметического узла по модулю бимодульной арифметики, а также для сравнительного анализа с аналогами традиционной и логарифметики поля GF(/;), предложенные технические решения были описанны на языке Verilog и синтезированы средствами САПР Synopsys Design Compiler в базисе 45 нм библиотеки стандартных ячеек Nangate Open Cell Library. Полученные результаты подтверждают теоретические выводы и доказывают эффективность разработанных методов. Разработанный арифметический узел бимодульной арифметики является более экономичным с точки зрения апаратных затрат относительно аналогов, при этом не уступая им по производительности.

«Немодульный» блок арифметического устройства направлен на реализацию всех последовательно-параллельных алгоритмов модулярной арифметики. Несмотря на обширный набор операций, практически все немодульные процедуры базируются на непосредственном переводе из модулярной системы счисления во взвешенную систему счисления (полиадический код). Пусть модулярная система счисления задается основаниями р{, р2,рп и А = (о,, а2,..., «„)- число, принадлежащее

п

диапазону ЪР, где р = р. . Полагая р2,..., рп основаниями полиадической

ы

системы счисления число А можно представить в виде

А=хпР\ Рг - Р„-1 Рх Рг - Рп-2 +- + *3 А Рг +хгР1 +

>

где 0 < хк < ^р., О</<п - коэффициенты (цифры) полиадической /=1

системы счисления.

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

а4 а3 а2 а,

--1- , 1

* ТаЬ \ ТаЬ \ ТаЬ XI

у

X'

Рис. 3. Структура устройства формирования цифр полиадического кода числа, представленного модулярным кодом

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

Третья глава посвящена анализу и разработке методов повышения сбоеустойчивости ВЭ бимодулыюй арифметики.

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

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

С другой стороны, структура числа (р-1) за счет разложения на набор попарно взаимно простых субмодулей ду (/<у <л') позволяет строить ярусные вычисления. Это позволяет ввести дополнительный параллелизм в арифметическом узле, заменив операцию сложения по модулю (р-1) на параллельное сложение по более мелким модулям (рис. 4.). При этом проектирование сумматора по модулю (р-1) сводится к проектированию комбинации сумматоров по модулям qj. В данной главе на основе перехода к ярусным вычислениям разработана параллельная структура арифметического узла ВЭ бимодульной арифметики.

7

ч У ^<7,-и

Рис. 4. Параллельная структура сумматора по модулю (р-1)

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

дополнительный субмодуль д5+/. В результате, процедура сложения по модулю р будем иметь следующие стадии:

1) независимое сложение первых компанент пар операндов по субмодулям ц1}

2) определение признака переполнения за диапазон (р-/) с помощью немодульной процедуры;

3) если переполнение произошло, выполнить коррекцию результата;

4) выбор из таблицы второй компаненты пары результата, соответствующей дискретному логарифму.

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

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

1) взаимно просто с основаниями модулярной системы;

2) больше по значению любого из оснований модулярной системы.

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

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

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

основаниям системы. Суть метода заключается в следующем. Рассмотрим набор

субмодулей арифметического узла с//, </_>, ..., дх, Q = - рабочий диапазон.

/=1

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

А' = И, '14, '-И. 'К+з )

А'

Для определения правильности числа л необходимо по известным остаткам \А'\ ,\А'\ ,определить значения его остатков по контрольным

основаниям ¡А"I ,\А"I . Затем необходимо сравнить значения \А'\ ,\А\ с

I 1?1+2 1 1<?1+3 1 1 '?1+3

' ■ Результат сравнения остатков по контрольным есть невязки:

Согласно Китайской теореме об остатках:

А' = £ахД + аД - г,, • 0, Л = ¿«Д, + «Д - г, • 0

Л" -U1

'9jt3 1 '?i+3

<7st3

к=1

где Г, •, Г, - ранги чисел Л. и А соответственно, Вк {к = 1,/г) - ортогональные базисы. Тогда

А'-А = (а, ~а1)В1 -гл._л-£) = АД-гА,_л-0

При этом,

дд=л,а/и1=(л,ш,)-а = / 1Л/»Ч,+ А,/и,. \ ■ч,

V h У

Отсюда, ранг искаженного числа равен: rang АД, = —

A m

4i

Ч,

Таким образом,

У,* 2=||д/'я/1-й| '

Т.е. ошибка обнаружена, если |/л+2 • О, 1 = |7,+3' £2, | = • Величина ошибки

'<7,4.3

определяется согласно выражению Д. = • .

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

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

Рис. 5. Структура блока коррекции в арифметическом узле ВЭ бимодульной

арифметики

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

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

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

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

В данном случае к значениям оснований модулярной системы предъявляются следующие

основные требования:

1) перекрытие динамического диапазона чисел, на который расчитано разрабатываемое устройство;

2) взаимная простота выбранных оснований;

3) выбирать основания из набора модулей вида р = Тцхц1...ц1 +1, где

ц1 - простые числа.

При выборе контрольных оснований для реализации схемы коррекции внутри каждого ВЭ, необходимо, чтобы контрольный модуль:

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

- был больше по значению, чем любой рабочий субмодуль;

обеспечивал сравнимое быстродействие по отношению к рабочим субмодулям.

Таким образом, в качестве контрольных субмодулей целесообразно использовать

модули специального вида (2"-1), (2"+1) . В противном случае использовать наименьший по битности простой модуль. На основании представленных требований в главе разработан соответствующий алгоритм выбора контрольных оснований, представленный на рис.6.

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

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

Рис. 6. Алгоритм выбора контрольных оснований для реализации схем кодовой защиты от сбоев

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

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

• разрядность входных данных - 16 бит;

• длина входных векторов — 1024;

• динамический диапазон модулярной системы - М = 242= 4.398.046.511.104. На основе анализа представленных в литературе методик выбора оснований для

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

• набор информационных модулей: {41, 43, 61, 67, 71, 79,109};

• набор контрольных модулей: {127, 255};

п

Рабочий диапазон м = = 4.405.233.041.161 > 4.398.046.511.104 = 242•

<=1 п+2

Полный диапазон Мпо1 = ]~[ р1 = 142.663.472.037.998.985 • Степень избыточности

/=1

К = Мтл! 242 ~ 32438

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

Рис. 7 . Структура модульного блока арифметического устройства модулярной вычислительной системы, построенная на базе сбоеустойчивых ВЭ-ов

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

Таблица 1

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

Основания модулярной вычислительной системы Субмодульное разложение Контрольные основания

61 2\ 3, 5 7, И, 17

71 2,5,7 11, 13, 17

137 2\ 17 19,31,33

157 2\ 3, 13 17, 19,31

211 2,3,5,7 11, 13,17

241 24, 3, 5 17, 19,31

Рабочий диапазон М = Д р, = 4.737.049.262.629 > 4.398.046.511.104 = 242 ;=1

Для проведения сравнительного анализа были разработаны высокоуровневые Verilog-описания модульного арифметического устройства вычислителя скалярных произведений векторов, а также позиционный блок вычислителя. Поведенческое описание указанных устройств синтезировано средствами САПР Synopsys Synplify в базисе ПЛИС Altera Stratix II , для симуляции и отладки проектов выбрана среда ModelSim. Модель эксперимента построена для обнаружения и исправления одиночного сбоя в модульном блоке арифметического устройства для позиционного и традиционных модулярных решений. В случае реализации на сбоеустойчивых ВЭ-ах, единичная ошибка вносится в каждый вычислительный канал модульного арифметического устройства. Результаты моделирования сведены в таблицу 2.

Таблица 2

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

Длина векторов Рабочий диапазон Максимальная частота, MHz Занимаемая площадь, ALUT

Двоичный вариант без троирования 1024 242 193 2060

Двоичный вариант с троированием 1024 242 182 4275

Таблица 2 (продолжение)

Модулярный вариант без схемы коррекции 1024 242 375 1985

Модулярный вариант с схемой коррекции (метод нелевизации) 1024 242 268 4230

Модулярный вариант с схемой коррекции (метод невязок) 1024 242 270 3357

Модулярный вариант без коррекции на ВЭ-ах 1024 242 474 1092

Модулярный вариант на сбоеустойчивых ВЭ-ах 1024 242 305 1804

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

- по сравнению с модулярной логарифметикой сокращено время выполнения модульных операции на один такт модульного суммирования по модулю (р-1).

2)Разработана архитектура ВЭ бимодульной арифметики, арифметический узел которого построен на базе однотипного кодового представления операндов. Это позволило выполнять арифметические операции на сумматоре одного типа - по модулю (р-1). Получено положительное решение о выдаче патента на полезную модель по заявке № 2014110622/08 (016695).

3) Предложена новая архитектура арифметического узла ВЭ бимодульной арифметики, предназначенная для реализации кодовой защиты от сбоев, возникающих в процессе вычислений. Разработанная архитектура имеет существенно более экономичные аппаратные затраты в сравнении с архитектурами, использующими структурную избыточность. При этом, рост избыточности после введения механизма обнаружения и исправления последствий сбоя составил 40% относительно схемы без защиты.

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

5) На примере скалярного произведения векторов показано, что модульное арифметическое устройство, построенное на наборе сбоеустойчивых ВЭ-ов позволяет сократить аппаратные затраты в 2 раза по сравнению с устройством на традиционной архитектуре, увеличить быстродействие в 1,6 раз по сравнению с позиционным вариантом с тройным резервированием. При этом контролируется вычислительный процесс по каждому основанию модулярной вычислительной системы, а не по одному каналу, как это имеет место при традиционном подходе.

6) По теме диссертации опубликовано 23 печатные работы, в том числе 12 работ опубликовано в журналах, рекомендованных ВАК, сделано 14 докладов на всероссийских и международных конференциях и конгрессах, получено положительное решение о выдаче патента на полезную модель.

7) Разработанные программные средства внедрены на предприятиях ОАО «НИИЭТ», ОАО «Российские космические системы».

СПИСОК СТАТЕЙ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ В ИЗДАНИЯХ, РЕКОМЕНДОВАННЫХ ВАК

1. Амербаев В.М., Балака Е.С. Анализ и синтез алгоритмов вычисления гауссовых логарифмов большого числа слагаемых над полем Галуа GF(p) // Изв. ВУЗов. Электроника. 2010. № 4. С. 64-69.

2. Балака Е.С., Тельпухов Д.В. Принципы построения специализированного вычислителя для задач матричной алгебры с применением параллельной арифметики // Нейрокомпьютеры: разработка и применение. 2010. №9. С. 46-49.

3. Амербаев В.М., Балака Е.С., Константинов A.B., Тельпухов Д.В. Методы построения прямых преобразователей модулярной логарифметики, 1 ориентированных на ЦОС // IV Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2010»: сб. трудов / под общ. ред. ак. РАН А.Л. Стемпковского. М.: ИППМ РАН, 2010. С. 374-377.

4. Амербаев В.М., Балака Е.С., Константинов A.B., Тельпухов Д.В. Методы ускорения вычислений скалярных произведений векторов в базисе модулярной логарифметики. // IV Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2010»: сб. трудов / под общ. ред. ак. РАН А.Л. Стемпковского. М.: ИППМ РАН, 2010. С. 378-381.

5. Амербаев В.М., Балака Е.С., Константинов A.B., Тельпухов Д.В. Применение аппарата модулярной логарифметики для решения специальных задач матричной алгебры // V Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2012»: сб. трудов / под общ. ред. ак. РАН А.Л. Стемпковского. М.: ИППМ РАН, 2012. С. 539-542.

6. Амербаев В.М., Балака Е.С., Константинов A.B., Тельпухов Д.В. Реализация обратного преобразователя модулярной арифметики совмещенного с операцией округления для задач ЦОС // V Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2012»: сб. трудов / под общ. ред. ак. РАН А.Л. Стемпковского. М.: ИППМ РАН, 2012. С. 535-538.

7. Амербаев В.М., Балака Е.С. Бимодульные вычисления над полем Галуа GF(p) // Вестник Московской государственной академии делового администрирования. Серия: Экономика. 2013. № 1 (20). С. 36-42.

8. Амербаев В.М., Балака Е.С., Щелоков А.Н. Применение структурной избыточности для повышения надежности арифметического узла вычислительного элемента бимодулыюй арифметики // Журнал «Известия ЮФУ. Технические науки». Таганрог, 2014. №7. С. 248-254. ISSN 19999429.

9. Амербаев В.М., Балака Е.С., Соловьев P.A., Тельпухов Д.В. Построение обратных преобразователей модулярной арифметики с коррекцией ошибок на базе полиадического кода // Нейрокомпьютеры: разработка и применение. 2014. №9. С. 30-36.

10. Амербаев В.М., Балака Е.С., Соловьев P.A., Тельпухов Д.В. Разработка аппаратного модулярного фильтра с конечной импульсной характеристикой на базе теоретико-числового быстрого преобразования Фурье // VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2014»: сб. трудов / под общ. ред. ак. РАН Стемпковского A.JI. М.: ИППМ РАН, 2014. Часть IV. С. 169-172.

11. Амербаев В.М., Балака Е.С., Соловьев P.A., Тельпухов Д.В. Устройство для вычисления скалярного произведения векторов с коррекцией ошибок на базе системы остаточных классов // VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2014»: сб. трудов / под общ. ред. ак. РАН Стемпковского А.Л. М.: ИППМ РАН, 2014. Часть IV. С. 173-178.

12. Амербаев В.М., Балака Е.С., Соловьев P.A., Тельпухов Д.В. Анализ и синтез арифметического узла проф. Поспелова Д.А. поля Галуа // VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2014»: сб. трудов / под общ. ред. ак. РАН Стемпковского А.Л. М.: ИППМ РАН, 2014. Часть IV. С. 179-182.