Исследование и разработка сбоеустойчивых устройств бимодульной модулярной арифметики тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Балака, Екатерина Станиславовна

• Балака, Екатерина Станиславовна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Балака, Екатерина Станиславовна

СОДЕРЖАНИЕ

Обозначения и сокращения

Введение

Глава 1. Принципы проектирования модулярных устройств, устойчивых к сбоям в процессе вычислений

1.1. Методы обеспечения сбоеустойчивости к одиночным событиям в процессе вычислений

1.2. Корректирующие коды модулярной арифметики

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

1.4. Построение арифметического устройства на вычислительных

элементах по каждому основанию модулярной системы

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

Глава 2. Принципы построения арифметического устройства бимодульной модулярной вычислительной системы

2.1. Бимодульная арифметика поля СР(р)

2.2. Однотипное кодовое представление операндов бимодульной арифметики поля ОР(р)

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

2.4. Обобщенная структура арифметического устройства

бимодульной модулярной арифметики

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

Глава 3. Разработка сбоеустойчивого вычислительного элемента

бимодульной арифметики

3.1. Методы введения структурной избыточности

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

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

3.3.1. Локализация и исправление одиночного сбоя методом нулевизации

3.3.2. Локализация и исправление одиночного сбоя методом на основе вычисления невязок

3.4. Выбор оснований для построения сбоеустойчивого

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

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

Глава 4. Применение разработанных методов для построения сбоеустойчивых устройств вычисления скалярных произведений векторов

4.1. Обоснование выбора элементной базы

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

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

вычислительных элементах

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

Заключение

Библиографический список

Приложение

Обозначения и сокращения

АЛУ арифметико-логическое устройство

БМК базовый матричный кристалл

БПФ быстрое преобразование Фурье

ВЭ вычислительный элемент

ДО детектор ошибок

ИС интегральная схема

ИУС информационно-управляющая система

НОК наименьшее общее кратное

ОЗУ оперативное запоминающее устройство

ПЛИС программируемая логическая интегральная схема

ПЗУ постоянное запоминающее устройство

САПР система автоматизации проектирования

СБИС сверхбольшая интегральная схема

СГ схема голосования

СПВ скалярное произведение векторов

СФО схема формирования ошибки

CRT Chinese Remainder Theorem (Китайская теорема об остатках)

DSP цифровой сигнальный процессор

LNS

Logarithmic Number System (логарифмическая система счисления)

LUT Look-Up-Table (просмотровая таблица) TMR

SEU Single Event Upset (одиночный сбой) RTL

Triple Modular Redundancy (трехкратное модульное резервирование)

Register-transfer level (модель описания аппаратуры как совокупность регистров и логических связей между ними)

Введение диссертации (часть автореферата) на тему «Исследование и разработка сбоеустойчивых устройств бимодульной модулярной арифметики»

Введение

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

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

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

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

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

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

Цель диссертационной работы

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

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). Для преодоления данного недостатка предложено усовершенствовать кодовое представление операндов бимодульной арифметики путем перехода от представления вычетов по модулям р и (р-1) к однотипному представлению по модулю (р-1). Такое решение позволило за счет незначительного усложнения схемы ВЭ выполнять кольцевые операции на одном типе сумматоров - сумматоре по модулю (р-1).

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

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

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

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

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

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

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

В заключении изложены основные научные и практические результаты диссертации.

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

Глава 1. Принципы проектирования модулярных устройств, устойчивых к сбоям в процессе вычислений

1.1. Методы обеспечения сбоеуетойчивости к одиночным событиям в

процессе вычислений

Характерной чертой специализированных вычислительных систем является стремление использовать устройства с повышенным быстродействием, архитектура которых адекватна алгоритму решаемой задачи [1, 2]. Анализ известных подходов, применяемых при разработке специализированых вычислителей, показывает, что все они подчинены современной тенденции к распараллеливанию вычислений [3-6]. Любая вычислительная система достигает своей наивысшей производительности благодаря использованию высокоскоростных элементов и параллельному выполнению большого числа операций. Именно возможность параллельной работы различных устройств системы является основой ускорения основных операций. Однако, при этом в стороне остаются вопросы оптимизации затрат на обеспечение сбое- и отказоустойчивости. С ростом степени распараллеливания вычислительного процесса, растет и объем используемой контрольной аппаратуры, необходимой для требуемого уровня сбоеустойчивости; усложняется устройство управления вычислительной системой, требуются дополнительные аппаратные и временные затраты на обеспечение его бесперебойной работы; вычислительная система разрастается, при этом частота сбоев в схемах увеличивается; резко возрастает потребляемая мощность.

Исходя из вышесказанного, заказчиками вычислительных систем специального назначения формируется дополнительное требование к разработке спецустройств - быть максимально компактным, потреблять минимум мощности и отвечать требованиям сбоеустойчивости для той или иной области применения[7-10].

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

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

При проектировании сбоеустойчивых устройств систем специального назначения основное внимание специалистов уделяется возможным одиночным событиям (SEU)[11-15], проявляющихся как изменение состояния элемента на противоположное. Одиночные сбои относятся к классу soft сбоев в том понимании, что они не приводят к катастрофическим (необратимым) отказам электрических цепей. В настоящее время разрабатывается широкий класс заказных СБИС, а также ПЛИС, для разных областей применения. Как известно, схемы памяти являются наиболее чувствительными к SEU, поэтому все типы ячеек памяти и триггера соответствующими архитектурными решениями защищаются от сбоев [16-18].

При передачи информации для устранения последствий SEU и одновременного обнаружения двойных сбоев используются помехоустойчивые коды. К ним относятся, например, модифицированный код Хемминга [19], код Хсяо [20]. Если при чтении данных обнаруживается одиночная ошибка, то с помощью встроенных схем коррекции она

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

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

1. Структурная избыточность. Основным методом, который широко применяется, является резервирование [21-24]. Существует большое количество различных способов резервирования, но для любого из них характерна очень высокая избыточность. Наиболее распространен метод тройного резервирования (Triple Modular Redundancy, TMR), основанный на создании дубликатов критических узлов схемы. Общее значение выбирается схемой голосования на основании выходов этих элементов. Таким образом, одиночный сбой изменит состояние логического элемента, только если пострадает сразу несколько узлов. Чем больше избыточность, тем больше задействуется полезной площади кристалла и тем меньше вероятность возникновения SEU. Недостаток этого подхода - увеличение площади на кристалле и потребляемой мощности на выполнение одной и той же функции. Данный метод не локализует и не исправляет ошибки, а только предоставляет правильное значение.

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

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

получили название арифметических кодов [25-27]. Применение арифметических кодов позволяет исправлять ошибки независимо от места и характера неисправности, т.е. с их помощью успешно обнаруживают и исправляют ошибки не только в работе исполнительных устройств, но и в устройствах передачи и хранения информации. Такая универсальность позволяет создать единую аппаратную систему контроля и устранения последствий сбоя в работе устройства. Кроме того, методы информационной избыточности обладают меньшими аппаратными затратами по сравнению с методами введения структурной избыточности [28, 29].

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

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

практического применения данные корректирующие коды не нашли [21, 30]. Основное применение коды данного класса нашли в вычислительных устройствах последовательного типа, т.к. при этом декодирующая схема получается достаточно простой. Однако при переходе к устройствам параллельного типа декодирующая аппаратура сильно усложняется даже для кодов, исправляющих только одиночные ошибки.

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

1.2. Корректирующие коды модулярной арифметики

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

X = х0р°+х1р1+...+хп_1рп'1; 0<хг<р-1 (1.1)

В этом случае говорят, что целое число X выражается в (1.1.) упорядоченными цифрами лг/, принадлежащими множеству 0, 1, ..., р-1. Целое число р > 1 представляет собой основание позиционной формы представления чисел. Для того, чтобы записать число X в двоичной (р = 2), троичной (р = 3) или десятичной (р = 10) форме, используется запись х„-1Х„.2...Х1Хо, нызываемая позиционным кодом.

Основанием модулярного представления чисел является множество целых чисел р, >1, в котором элементы любой пары ра,рь являются взаимно простыми числами. Запись целого числа X в модулярном представлении задается последовательностью Х„.]Х:п.2...Х]Хо, где Х; = X (тос1 р), 0< хр1 < р,~1•

т

При этом произведение модулей Р = ГТ А - ^ определяет область чисел, над

/=1

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

У {Р\>Р2,-Рт} у Г У у „ \ УХ г1Л1)Л2г"?Лт/>

I I (1'2)

где а. = для / = 1, 2, т.

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

• интервал определения для неотрицательных целых чисел: 0<Х<Р-1;

• интервал определения чисел со знаком:

- для четных значений Р: -Р/2 <Х<+Р/2;

- для нечетных значений Р: -(Р-1)/2 <Х<+(Р-1)/2;

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

Р: Х = Р-Х, а затем полученное значение X преобразовывается в модулярное представление в соответствии с формулой (1.2).

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

Л *В ){|а, *Ь,\р1,\а2 *Ь2\р2,...,\ат *Ът\рт),

где * - операция сложения, вычитания или умножения.

В общем случае операция умножения по модулю р1 двух чисел х и у может быть представлена в виде обычного позиционного умножения этих

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

Список литературы диссертационного исследования кандидат наук Балака, Екатерина Станиславовна, 2014 год

Библиографический список

[1] Бурцев B.C. Из истории развития специализированных ЭВМ специального назначения (1950 - 1990 гг.). - Политехнические чтения, выпуск 6, Москва 2006 г. (по материалам VI Политехнических чтений 7 апреля 2004 г.)

[2] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[3] Бурцев B.C. Параллелизм вычислительных процессов и развитие архитектуры Супер ЭВМ. М.: Торус Пресс, 2006. 416 с.

[4] Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. - М.:МЦНМО, 2000. - 960с.

[5] И.А.Каляев, И.И.Левин, Е.А.Семерников, В.И.Шмойлов. Реконфигурируемые мультиконвейерные вычислительные структуры.-Ростов-на-Дону. Издательство: ЮНЦ РАН, 2008. - 320 с.

[6] Корнеев В. Параллельные вычислительные системы. - М.: Нолидж, 1999.-320 с.

[7] О компании ОАО «НИИВС «Спектр» http://isc-spectr. spb.ru/about/hi story

[8] Общие технические требования к микропроцессорным устройствам защиты и автоматики энергосистем. РД 34.35.310 - 97.

[9] Материалы по проекту «Высокопроизводительный отказоустойчивый вычислительный комплекс с управляемой структурно-функциональной избыточностью», принадлежащего ЗАО НТКЦ «ПЕТРОФАРМ». http://www.petrofarm.ru/proiect.shtml

[10] О компании НПО РИТ http://www.nno-rit.ru/Droiects-cloud.html

[11] Осипенко П. Одиночные сбои — вызов для современных микропроцессоров // Электронные компоненты, №7, 2009. - с. 12-15.

[12] Соколов А.Г. Программно-аппаратные методы повышения радиационной стойкости микросхем SRAM ПЛИС //

http://ptkgroup.ru/assets/files/catalog

[13] Ныммик Р., Кузнецов Н. Радиационные одиночные сбои

микроэлектроники космических аппаратов, обусловленные событиями солнечных космических лучей // Космические исследования. — 1997. — Т. 35, № 5. — С. 465-479.

Игнатущенко В.В. Оценка эффективности одного из вариантов многоверсионного резервирования взаимосвязанных параллельных задач для управляющих параллельных вычислительных систем. // Доклады Пятой международной конференции «Параллельные вычисления и задачи управления», Москва, 2010. С. 627- 642.

Аряшев С.И., Петров К.А., Корниленко А.В., Бобков С.Г. Способ регенерации и защиты от сбоев динамической памяти и устройство для его осуществления. Патент РФ № 2477880

Ачкасов В. Н., Смерек В. А., Уткин Д. М. Обобщенный критерий надежности ингтегральных схем и методы защиты от одиночных сбоев в цифровых устройствах на стадии проектирования. - Научный журнал КубГАУ, №76(02), 2012 . - 1-12 сс.

Гобчанский О., Кузнецов Н. Устойчивость IBM PC совместимых контроллеров к радиационным сбоям на орбитах космических аппаратов. // СТА («Современные технологии автоматизации»). 2005. №3. С. 46-51.

Амосов В.В. Схемотехника и средства проектирования цифровых устройств - СПб.: БХВ-Петербург, 2007. - 560 с.

Угрюмов Е.П. Цифровая схемотехника: учеб. Пособие для вузов. - 3-е изд., перераб. И доп. - СПб.: БХВ-Петербург, 2010. - 816 с.

Чекмарев С.А. Создание и отладка отказоустойчивой архитектуры космического процессора.

http://www.lib.tpii.rU/fulltext/c/2013/C22/040.pdf

Иыуду К.А. Надежность, контроль и диагностика вычислительных машин и систем. - М.: Высш. Шк., 1989. - 216 с.

Краснобаев В.А. и др. Методы повышения надежности специализированных ЭВМ систем и средств связи. - Харьков: ХВВКИУ РВ, 1990. - 172 с.

[23] Согомонян Е.С., Слабаков E.B. Самопроверяемые устройства и отказоустойчивые системы. - М.: Радио и связь, 1989. - 208 с.

[24] Кузьмин И.В., Бурназян Р.Г., Ковергин A.A. Аппаратный контроль электронных цифровых вычислительных машин. - М.: «Энергия», 1974.-72 с.

[25] Дадаев Ю. Г., Арифметические коды с определением места ошибок, Пробл. Передачи информ., 1966, том 2, выпуск 2, 39^2

[26] Дадаев Ю.Г. Арифметические коды, исправляющие ошибки. — М.: Сов.радио, 1969.-168 с.

[27] Дадаев Ю.Г. Теория арифметических кодов. — М.: Радио и связь, 1981.

- 272 с.

[28] Зуев Ю.А. Т. 1 : Основные структуры. Методы перечисления. Булевы функции. УРСС, 2012. - 273 с.

[29] R. Micheloni, A. Marelli and R. Ravasio Error Correction Codes for NonVolatile Memories, 2008. Qimonda Italy srl, Design Center Vimercate, Italy. ISBN: 978-1-4020-8390-7.

[30] Торгашев B.A. Система остаточных классов и надежность ЦВМ. - М.: Сов. Радио, 1973.-118 с.

[31] Акушский И .Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Советское радио, 1968. - 440 с.

[32] Акушский И.Я., Пак И.Т. Вопросы помехоустойчивого кодирования в непозиционном коде // Вопросы кибернетики. 1977. Т. 28, С. 36-56.

[33] Коляда А.П., Пак И.Т. Модулярные структуры конвейерной обработки цифровой информации. - Минск: Университетское, 1992. - 256 с.

[34] Краснобаев В.А. и др. Методы повышения надежности специализированных ЭВМ систем и средств связи. - Харьков: ХВВКИУ PB, 1990. -172 с.

[35] Червяков Н.И., Бережной В.В., Оленев A.A., Калмыков И.А. Минимизация избыточности кода системы остаточных классов с одним контрольным основанием / Электронное моделирование. 1994.

№1. Т.16. С.56-61.

[36] Barzi F. Error correcting properties of redundant residue number system / IEEE Trans. Comput. 1973. Vol. C-22, №3. P. 174-182.

[37] Червяков Н.И. Применение системы остаточных классов в цифровых системах обработки и передачи информации. - Ставрополь: СВВИУС, 1985.-68 с.

[38] Ирхин В.П. Табличная реализация операций модулярной арифметики. Сб.науч.трудов Юбилейной Международной научно-технической конференции «50 лет модулярной арифметики», 2005, стр.268-273.

[39] В. П. Ирхин, JI. А.Овчаренко Табличная реализация цифровых фильтров в модулярной арифметике // Информационные технологии -2005,-№10,-с. 13-20

[40] Коляда А.П., Пак И.Т. Модулярные структуры конвейерной обработки цифровой информации. - Минск: Университетское изд-во, 1992. - 256 с.

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

[42] Инютин С.А. Модулярные вычисления в сверхбольших компьютерных диапазонах. // Электроника. 2003. № 6. С. 54-61.

[43] Инютин С.А. Методы организации многоразрядных вычислений.

http://www.ipdn.ru/rics/vk/ private/vkl 2/89-93.pdf

[44] Исупов, К. С. Эффективное выполнение высокоточных численных расчетов на основе системы остаточных классов [Текст] / К. С. Исупов, В. С. Князьков, А. В. Логинов // Международный саммит проекта «Open Cirrus». Сессия: Аспекты развития программы Университетский кластер» : Сб. тез. Докл. (31 мая — 3 июня 2011 г., г. Москва, РАН). —М.: [б. и.], 2011. — С. 65.

[45] Синьков М.В. Конечномерные гиперкомплексные числовые системы.

Основы теории. Применения / М.В. Синьков, Ю.Е. Бояринова, Я.А. Калиновский. - К.: Инфодрук, 2010. - 388 с.

[46] Клипков С.И. О новом подходе к построению гиперкомплексных числовых систем ранга два над полем комплексных чисел // Укр. Мат. Журн.-2011.-63, №1.-С. 130-139.

[47] Акушский И.Я., Бурцев В.Н. Принципы построения высокопроизводительных и надежных процессоров в непозиционных системах счисления // В сборнике «Теория кодирования и сложность вычислений». - Алма-Ата: Наука, 1980.

[48] Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.-536 с.

[49] Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing, Second Edition, 1999, California Technical Publishing, P.O. Box 502407, San Diego, CA 92150. Also available for free download at: http://www.dspguide.com or http://www.analog.com

[50] Yang L.-L., Hanzo L. Redundant Residue Number System Based Error Correction Codes // IEEE Vehicular Technology Conference, 2001. IEEE VNC 54th, vol. 3, 7-11 October 2001. - p. 1472-1476.

[51] Червяков H. И., Степанян С. В., —Математическая модель коррекции пакетов ошибок в двухступенчатой системе остаточных классов!, Сборник трудов, Всероссийская научная конференция с элементами научной школы для молодежи «Параллельная компьютерная алгебра» -2010. С.-121-127.

[52] Д.А.Орлов, Ш.А. Оцоков О возможности применения «безошибочных» вычислений для решения задачи Коши. // Труды международной конференции «Информационные средства и технологии», МФИ - 2006, Т.2., Москва, 2006.

[53] Лавриненко C.B. Разработка отказоустойчивого мультинейропроцессора цифровой обработки сигналов // Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.01, 2008.

[54] Финько O.A. Реализация систем булевых функций большой размерности методами модулярной арифметики // Автоматика и

телемеханика. — 2004. № 6. — P. 37-60.

Финько O.A. Алгоритм генерации блочной ПСП, основанный на применении логико-числовых форм // Известия ЮФУ. Технические науки. — 2012. — том: 137, № 12 . — С. 158-167.

Тербер К. Архитектура высокопроизводительных вычислительных систем. М.: Наука, 1985.

Червяков Н.И., Сахнюк П.А. Применение нейроматематики для реализации модулярной арифметики при вычислениях в конечных кольцах // Нейрокомпьютер, 1999, №14. - С. 12 - 25.

Стемпковский A.JI. Отказоустойчивые архитектуры микроэлектронных вычислительных систем // Информационные технологии и вычислительные системы, 2001, №2/3. - С. 40 - 50.

Басаев А., Гришин В. Космическое приборостроение: главное -правильная концепция. // ЭЛЕКТРОНИКА: НТБ. 2009. №8.

Бухтеев A.A. Методы и средства проектирования систем на кристалле. // Chip news, 2003, №4, с. 4-14.

Червяков Н.И., Сахнюк П.А., Шапошников A.B., Ряднов С.А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. / Под ред. Н.И. Червякова. - М.: ФИЗМАТЛИТ, 2003. - 288с.

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

Долгов A.M. Диагностика устройств, функционирующих в системе остаточных классов. - М.: Радио и связь, 1982. - 64 с.

Стемпковский А.Л., Амербаев В.М., Корнилов А.И. Модулярная логарифметика - новые возможности для проектирования модулярных вычислителей и преобразователей // IV Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2010»: сб. научн. Тр. / под общ.

Ред. А.Л. Стемпковского". - М.: ИППМ РАН, 2010.

[65] Стемпковский А.Л., Амербаев В.М., Соловьев P.A. Вычислительный элемент модулярной арифметики // Патент на полезную модель, заявка номер 2012127097, номер 123995 от 10 января 2013 года.

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

[67] Стемпковский А.Л., Амербаев В.М., Соловьев P.A. Принципы рекурсивных модулярных вычислений // Журнал «Информационные технологии», 2013, номер 2, стр. 22-27.

[68] Виноградов И.М. Основы теории чисел. М.: Наука, 1972.

[69] Preethy А.Р. and Radhakrishnan D. —An RNS Based Logarithmic Adderl. IEE Proceedings - Computers and Digital Techniques, vol. 147, issue 4, pp. 283-296, July 2000.

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

[71] Поспелов Д.А. Арифметические основы вычислитель-ных машин дискретного действия. М.: Высш. Шк., 1970.

[72] Опадчий Ю.Ф. и др. Аналоговая и цифровая электроника (Полный курс) // Учебник для вузов. М.: Горячая Линия - Телеком, 2000. - 768 с.

[73] Бухштаб А. А. Теория чисел. М.: «Просвещение», 1966. - 385 с.

[74] A. Omondi and В. Premkumar, —Residue Number System: Theory and Implementation // Imperial College Press 2007, ISBN 978-1-86094-866-4.

[75] Корнилов А.И., Семенов М.Ю., Ласточкин O.B., Калашников B.C. Применение современных методов проектирования при реализации модулярных вычислительных процедур // «50 лет модулярной арифметике»: Сб. научных трудов. М.: ОАО «Ангстрем», МИЭТ,

2006. С. 369-383.

[76] Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников B.C. —Методология проектирования специализированных вычислителей на основе автоматизированной генерации технологически независимых IP-блоков I// Проблемы разработки перспективных микроэлектронных систем - 2005. Сб. научных трудов, под общ. Ред. А.Л. Стемпковского. М.: ИППМ РАН. 2005. С. 487- 492.

[77] Soderstrand М.А., Jenkins W.K., Jullien G.A., and Taylor F.J. Residue Number System Arithmetic: Modern Applications in Digital Signal Processing // IEEE Press, 1986.

[78] Математический Энциклопедический словарь. M.: Сов. Энциклопедия, 1988. С. 141, 330.

[79] Лидл Р., Нидеррайтер Г. Конечные поля: в 2 т. / под общ. Ред. В.И. Нечаева. М.: Мир, 1988.

[80] Parhomi В., Computer arithmetic: algorithm and Hardware designs // Oxford University Press, 2000. № 4.

[81] Амербаев B.M. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. -324с.

[82] Лавриненко И.Н. Разработка математических методов модклирования модулярного нейропроцессора цифровой обработки сигналов // дис. Канд. Физ.-мат. Наук: 05.13.18 - Ставрополь: РГБ, 2005.

[83] Юдинцев В. Радиационно стойкие интегральные схемы. Надежность в космосе и на земле. - ЭЛЕКТРОНИКА: Наука, Технология, Бизнес 5/2007

[84] Буев П.В. Повышение эффективности функционирования систем электроснабжения посредством структурной избыточности // дис. Канд. Тех. Наук: 05.09.03 - Липецк, 2012.

[85] В. Н. Тупкало Решение задачи функционального контроля на основе введения унифицированной структурной избыточности // Автомат. И телемех., 1993, выпуск 1,167-172.

[86] Амербаев В.М., Балака Е.С., Щелоков А.Н. Применение структурной избыточности для повышения надежности арифметического узла вычислительного элемента бимодульной арифметики // Журнал

«Известия ЮФУ. Технические науки». Таганрог, 2014. № 7. С. 248254. ISSN 1999-9429.

[87] Аверченков О. Е. Схемотехника: аппаратура и программы. - М.: ДМК Пресс, 2012.-588 с.

[88] Черкесов Г.Н. Надежность аппаратно-программных комплексов. Учебное пособие. - СПб.: Питер, 2005. - 479 с.

[89] А.Р. Preethy and D. Radhakrishnan, —A 36-bit Balanced Moduli MAC Architecture!, 42nd Midwest Symp. On Circuits and Systems (MWSCAS99), Las Cruces, NM, vol. 1, pp. 380-383, Aug. 1999.

[90] Амербаев B.M., Константинов A.B., Тельпухов Д.В. Бивалентный дефект модулярных кодов // Проблемы разработки перспективных микро- и наноэлектронных систем - 2008. Сб. научных трудов / под общ. Ред. А.Л. Стемпковского. М.: ИППМ РАН, 2008. С. 462- 466.

[91] Выбор технологичных модулей в задаче оптимизации модульных умножителей и сумматоров. Д.В. Тельпухов, А.В. Константинов -М:МИЭТ, 16-ю Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2009», Сб. тезисов

[92] S. Piestrak. 1994. Design of residue generators and multioperand modular adders using carry save adders. IEEE Transactions on Computers, 42(1): 68-77.

[93] Калашников B.C. Исследование и разработка методов проектирования быстродействующих вычислительных узлов для реализации отказоустойчивых систем на основе модулярной арифметики // дис. Канд. Тех. Наук: 05.13.05 - Москва, 2007.

[94] Yang L.-L., Hanzo L. Coding Theory and Performance Of Residue Number SystemCodes // submitted to IEEE Transactions on Information Theory, 1999.-40 p.

[95] Шпаковский Г.И. Параллельные микропроцессоры для цифровой обработки сигналов и медиа данных// Минск: БГУ, 2000. 196 с.

[96] Технологии проектирования специальной аппаратуры с применением БМК // Материалы с сайта НПК «Технологический центр» http://www.asic.ru/

[97] Федухин A.B., Муха A.A., Муха A.A. ПЛИС-системы как средство повышения отказоустойчивости // Математичш машини i системи. 2010, №1. С. 198-204.

[98] Попович A.B. Применение технологии разработки «систем на кристалле» на платформе ПЛИС // Компаненты и технологии. 2004. №4.

[99] Сравнительный анализ применения ПЛИС и микропроцессоров при разработке информационно-управляющих систем, важных для безопасности АЭС // Научно-технический отчет. НАУ им. Н.Е. Жуковского «ХАИ», НТСКБ «Полисвит», ИПМЭ им. Г.Е. Пухова HAH Украины, ИПММС HAH украины. - 2005. С.47.

[ 100] Официальный сайт фирмы ALTERA http://www.altera.ru/

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

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

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

[104] Патент US4752904. Efficient structure for computing mixed-radix projections from residue number systems. 26.06.1988