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

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

Калашников Вячеслав Сергеевич

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

о

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

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

Москва-2007

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

Научный руководитель кандидат технических наук А И Корнилов

Официальные оппоненты

доктор технических наук, профессор А И Коекин кандидат технических наук, с н с Ю М Герасимов

Защита состоится 23 октября 2007 года в 10 час 00 мин на заседании диссертационного совета Д002 078 01 в ИППМ РАН по адресу 124681, г Москва, Зеленоград, ул. Советская, д 3.

С диссертацией можно ознакомиться на сайте ИППМ РАН www IPPM ru и в библиотеке ИППМ РАН

Автореферат разослан 20 сентября 2007 г.

Ученый секретарь диссертационного совета Д002 07801,

Ведущая организация

ФГУП "Научно исследовательский институт микроэлектронной аппаратуры "Прогресс"

и

ктн.

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

Актуальность темы

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

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

- обеспечивает естественный параллелизм при выполнении вычислений,

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

Данный вывод подтверждает ряд высокоэффективных устройств, реализованных с применением модулярной арифметики, наиболее известными из которых являются как отечественные ЭВМ "Т-340А", "К-340А", "Алмаз", "5Э53", так и зарубежные разработки, например, такие как сигнальный процессор INMOS' IMS AI 10, вычислительная машина IBM Enterprise System/9000

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

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

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

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

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

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

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

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

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

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

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

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

Лично автором получены следующие результаты

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов

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

Результаты диссертации внедрены и использовались в Московском институте электронной техники (МИЭТ) и научно-исследовательских работах ИППМ РАН

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

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

- медицинская техника;

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

- коммуникационные системы.

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

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

Основные положения и результаты диссертационной работы были представлены на следующих конференциях*

- Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика" (МИЭТ, 20032006г, 4 доклада, один из докладов отмечен дипломом);

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

- Юбилейная Международная научно-техническая конференция "50 лет модулярной арифметике" (МИЭТ, 2006г, 1 доклад).

Публикации

По теме диссертации автором опубликовано 13 печатных работ, подготовлено 4 отчета по НИР

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

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

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

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

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

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

В настоящее время можно выделить три основных метода повышения надежности вычислительных устройств

1) резервирование;

2) применение специальных позиционных кодов,

3) применение корректирующих кодов в модулярной арифметике

Основным недостатком первого из них является высокая

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

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

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

А =

информационная часть контрольная часть

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

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

Рис, 1, Особенности применения К-кодов при реализации систем повышенной надежности на основе аппарата модулярной арифметики

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

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

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

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

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

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

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

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

Из литературы известны методы реализации быстродействующих сумматоров для модулей вида 2° и (2"-1) с применением схем ускоренного переноса на основе декомпозиции BDD (Binary Decision Diagram, Диаграмма Двоичных Решений). Для модулей вида (2"+1) сравнимые по эффективности методы построения модулярных сумматоров отсутствуют В то же время модули данного типа не менее важны при проектировании вычислительных устройств на основе модулярной арифметики, а в особенности отказоустойчивых систем, принимая во внимание специфику выбора модулей для их построения.

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

\a + b\i"+\ =\а+ъ+Агп +дош> (1)

где z=2"-1 - дополнение значения модуля до 2n+I, £оШ - старший бит суммы (a+b+z). Введение добавочного слагаемого z осуществляется на основе сумматора с сохранением переносов, имеющего фиксированную задержку. Вычисление переносов реализуется с применением схем ускоренного переноса на основе декомпозиции BDD, которые затем корректируются с учетом инверсии выходного переноса за одну стадию с помощью КМОП-элементов 2И-ИЛИ Таким образом, в отличие от двоичного сумматора,

построенного аналогичным методом, предлагаемая структура сумматора по модулю (2п+1) включает два дополнительных блока, быстродействие которых не зависит от разрядности операндов (рис 2) Данный факт позволяет сделать вывод, что задержка такого модулярного сумматора больше задержки двоичного на фиксированное значение, равное сумме задержек полусумматора и КМОП-элемента 2И-ИЛИ

| а+Ь 12„+1 _ а+ъ НА Л И-ИЛИ гзтах • зтах ~ 'зтах 1зтах

а Ь

Рис 2. Общая структура сумматора по модулю вида (2п+1), построенного на основе декомпозиции ЕШБ 11

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

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

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

- прямой метод на основе двухвходовых сумматоров,

- линейная структура на основе сумматоров с сохранением переносов;

- древовидная структура на основе сумматоров с сохранением переносов,

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

(а+ Ь — тг), если (а + Ь)> т, (« + Ъ), если (а + Ь) < т1

(2)

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

Кроме того, в данной главе проводится сравнительный анализ различных реализаций модулярных сумматоров, как двухоперандных так и мультиоперандных, а также их двоичных аналогов. Для этого исследуемые устройства были представлены в виде высокоуровневых Уеп1о§-описаний и синтезированы средствами САПР Бупорвув в базис О.бмкм библиотеки стандартных ячеек Полученные результаты подтверждают теоретические выводы и доказывают высокую эффективность разработанных методов

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

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

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

м«. =

а

/=о

*2 X

а} 2]

п-1

+ +

Г=¿/-2+1 т, 7=^-1+1 т,

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

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

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

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

- разрядность результата на выходах таблиц состояний не увеличивается в зависимости от значения произведения и результат находится в диапазоне от 0 до М(М=т¡*т2у-. хтр),

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

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

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

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

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

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

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

- 2р двоичных компараторов на равенство,

- р двоичных комбинационных блоков на основе приоритетно-дешифрированной логики,

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

- блок многовходовых логических элементов ИЛИ.

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

Преимуществами предлагаемого подхода являются

- возможность локализации ошибки,

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

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

- аппаратные затраты значительно ниже в сравнении с методом на основе единой таблицы состояний (в 2 раза для используемого в работе набора модулей)

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

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

к информационным модулям

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

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

к контрольным модулям.

- удовлетворение условию взаимной простоты между собой и по отношению к информационным модулям системы;

- обеспечение сравнимого или более высокого быстродействия соответствующих вычислительных каналов при условии т1 <т.2< < тр< тр+1 < тр+2 < < тр+г,

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

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

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

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

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

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

Устройство в традиционном

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

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

L

Y^A,B, (4)

i=i

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

- динамический диапазон — N=23Z,

- разрядность входных данных - w,„ = 12 бит;

- длина вычислителя - £=256

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

- набор информационных модулей {11,13,31, 41,127,255}, р= 6,

- набор контрольных модулей {511,512}, г=2,

р

- рабочий диапазон М = J| ml = 5.886,070 905 ,

j=l

p+r

- полный диапазон Мт = Ди( =1 539.984 503 016 960,

г=1

- степень избыточности R = Мт IN- 358555 ;

- минимальное расстояние кода dmm = г +1 = 3

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

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

Для проведения сравнительного анализа разработанные высокоуровневые Уеп^-описания вычислителя с указанными выше параметрами в двоичном и модулярном исполнении были синтезированы в базис 0 бмкм библиотеки стандартных ячеек средствами САПР Зупорвув. Результаты синтеза представлены в таблице 1 Для обеспечения эквивалентной степени надежности в двоичном варианте при сравнении используется метод аппаратного резервирования, предполагающий в данном случае тройную избыточность

Таблица 1

Сравнительный анализ специализированного вычислителя с повышенной

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

Параметр Двоичный вычислитель Модулярный вычислитель Двоичный вычислитель с исправлением одиночных ошибок методом аппаратного резервирования (тройная избыточность) Модулярный вычислитель с исправлением одиночных ошибок на основе корректирую -щих К-кодов

Разрядность вх. данных 12 бит 12 бит 12 бит 12 бит

Длина основного блока 256 256 256 256

Рабочий диапазон 232 232 232 232

Максимальная задержка, не 28.53 14 5 >28 53 14 5

Занимаемая площадь, мкм2 1206864 25 2489803 0 >3620592 75 3484543 5

Аппаратная избыточность (в сравнении с исходным) - - 200 % 40%

Как показывают результаты синтеза, интегральное исполнение отказоустойчивых систем на основе аппарата модулярной арифметики и разработанных методов реализации ее вычислительных операций обеспечивает более высокое быстродействие по сравнению с двоичными способами реализации подобных устройств в 2 и более раз при сравнимых аппаратных затратах Стоит также отметить, что рост избыточности при введении механизма обнаружения и коррекции ошибок в модулярном варианте составляет всего 40%, тогда как в двоичном он равен 200%

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

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

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

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

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

- не требуют дополнительной коррекции операндов и результата операции (для сумматоров по модулям вида 2п+1)

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

3 Предложены методы построения прямых и обратных преобразователей, которые, в отличие от известных методов

- обладают универсальностью (для любых значений модулей),

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

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

- обеспечивают возможность гибкого проектирования в зависимости от разных критериев

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ

РАБОТЫ

[1] Семенов М Ю, Калашников В С , Ласточкин О В Структура оптимизированных сумматоров, функционирующих в системе остаточных классов// Десятая всероссийская межвузовская конференция студентов и аспирантов «Микроэлектроника и информатика-2003» тез докладов - М МИЭТ, 2003 -С. 91

[2] Калашников ВС Основные виды архитектур модулярных сумматоров для двух операндов // Одиннадцатая всероссийская межвузовская конференция студентов и аспирантов «Микроэлектроника и информатика-2004»-тез докладов.-М. МИЭТ, 2004 - С 217

[3] Корнилов А И, Семенов М Ю , Калашников В С Методы аппаратной оптимизации сумматоров для двух операндов в системе остаточных классов // Известия ВУЗов. Электроника - 2004 - № 1 - С 75-82

[4] Исследование методов проектирования и разработка программных средств синтеза быстродействующих арифметических устройств отчет о НИР (заюпоч.), шифр "Вега-0-К-2004" / ИППМ РАН, рук Стемпковский А Л - Москва, 2004 - № ГР 01200410528 - Инв № 02200406453

[5] Исследование и разработка методов аппаратной реализации базовых элементов и основных вычислительных процедур для специализированных устройств цифровой обработки сигналов с применением нетрадиционной арифметики: отчет о НИР (заключ.), шифр "Вега-К-2004" / ИППМ РАН, рук Стемпковский А Л - Москва, 2005. -№ ГР 01200410531 - Инв № 02200601688.

[6] Калашников В С Принципы построения двоичных и модулярных мультиоперандных сумматоров//Двенадцатая всероссийская межвузовская конференция студентов и аспирантов «Микроэлектроника и информатика-2005» тез докладов - М МИЭТ, 2005 - С 209

[7] Семенов М Ю, Калашников В С , Ласточкин О В Применение аппарата модулярной арифметики для построения фильтра с конечной импульсной характеристикой // Известия ВУЗов Электроника — 2005 — № 3. — С. 46-50

[8] Корнилов А И, Семенов М.Ю, Ласточкин О В, Калашников В.С Принципы построения специализированных вычислителей с применением модулярной арифметики //Проблемы разработки перспективных микроэлектронных систем — 2005 сб научных трудов/ под общ. ред А.Л Стемпковского. - М ИППМ РАН, 2005. - С 346-351

[9] Корнилов А.И, Семенов М Ю, Ласточкин О.В, Калашников В С. Методология проектирования специализированных вычислителей на основе

автоматизированной генерации технологически независимых IP-блоков // Проблемы разработки перспективных микроэлектронных систем - 2005 сб научных трудов / под общ ред А JI Стемпковского - М ИППМ РАН, 2005 - С 487-492

[10] Корнилов АИ, Семенов МЮ, Ласточкин OB, Калашников ВС Реализация специализированных быстродействующих вычислителей на основе нетрадиционных алгоритмов с применением IP-генераторов // V Международная научно-техническая конференция «Электроника и информатика - 2005» материалы конференции - М . МИЭТ, 2005 - 4 1 -С 192-193

[11] Исследование методов проектирования и разработка программных средств синтеза быстродействующих арифметических устройств отчет о НИР (заключ), шифр "Вега-0-Ст-2005" / ИППМ РАН, рук Стемпковский АЛ -Москва,2005 -№ ГР 01200606057 -Инв №02200603585

[12] Корнилов А И., Калашников ВС, Ласточкин OB, Семенов МЮ. Особенности построения умножителей по модулю (2п-1) // Известия ВУЗов Электроника -2006 -№1 -С 55-59

[13] Калашников В С Основные принципы построения отказоустойчивых систем с применением аппарата модулярной арифметики// Тринадцатая всероссийская межвузовская конференция студентов и аспирантов «Микроэлектроника и информатика-2006» тез докладов - М МИЭТ, 2006 -С 237

[14] Корнилов АИ, Семенов МЮ, Ласточкин OB, Калашников ВС Применение современных методов проектирования при реализации модулярных вычислительных процедур // Юбилейная Международная научно-техническая конференция (В рамках V Международной научно-технической конференции «Электроника и информатика - 2005») «50 лет модулярной арифметике» Сб научных трудов - М ОАО "Ангстрем", МИЭТ, 2006 - С 369-383 http //www computer-museum/histussr/sokconfö htm

[15] Стемпковский АЛ, Корнилов АИ, Семенов МЮ, Ласточкин OB, Калашников ВС Построение систем повышенной надежности на основе аппарата модулярной арифметики с применением современных методов и средств проектирования // Проблемы разработки перспективных микроэлектронных систем - 2006 сб научных трудов/ под общ ред АЛ Стемпковского - М • ИППМ РАН, 2006 - С 253-258

[16] Исследование методов проектирования и разработка программных средств синтеза быстродействующих арифметических устройств отчет о НИР (заключ), шифр "Вега-0-Ст-2006"/ИППМ РАН, рук Стемпковский АЛ -Москва, 2006 -№ ГР 01200606060. - Инв X» 02200701842.

Введение.

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

1.1. Основные свойства модулярной арифметики. Обобщенная структура вычислительной системы на основе аппарата модулярной арифметики.

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

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

1.4. Теоретические основы применения аппарата модулярной арифметики для обнаружения и коррекции ошибок. Аналитическое сравнение позиционных и модулярных методов повышения надежности.

Выводы по Главе 1.

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

2.1. Анализ типовых архитектур модулярных двухоперандных сумматоров.

2.2. Методы логического синтеза быстродействующих двухоперандных сумматоров по модулям (2п-1) и (2п+1) на основе BDD.

2.3. Сравнительный анализ различных реализаций модулярных двухоперандных сумматоров.

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

2.5. Метод аппаратной реализации модулярных двухоперандных сумматоров на основе структур с сохранением переносов.

2.6. Сравнительный анализ различных реализаций двоичных и модулярных мультиоперандных сумматоров.

Выводы по Главе 2.

Глава 3. Методы реализации основных немодульных операций для построения систем повышенной надежности.

3.1. Методы построения конвейерных прямых преобразователей.

3.2. Методы построения конвейерных обратных преобразователей на основе "Китайской теоремы об остатках".

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

Выводы по Главе 3.

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

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

4.2. Реализация основного блока вычислителя.

4.3. Реализация блока обнаружения и коррекции ошибок.

4.4. Сравнительный анализ специализированного вычислителя в модулярном и двоичном исполнении.

Выводы по Главе 4.

Актуальность темы

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

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

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

Данный вывод подтверждает ряд высокоэффективных устройств, реализованных с применением модулярной арифметики, наиболее известными из которых являются как отечественные ЭВМ "Т-340А", "К-340А", "Алмаз", "5Э53", так и зарубежные разработки, например, такие как сигнальный процессор INMOS' IMS А110, вычислительная машина IBM Enterprise System/9000.

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

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

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

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

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

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

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

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

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

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

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

Лично автором получены следующие результаты:

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

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

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

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

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

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

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

1. Метод аппаратной реализации модулярных двухоперандных сумматоров для модулей вида (2п+1), обеспечивающих быстродействие, сравнимое с быстродействием двоичных сумматоров одинаковой разрядности и построенных аналогичным образом.

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

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

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

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

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

Реализация результатов

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

Результаты диссертации внедрены и использовались в Московском институте электронной техники (МИЭТ) и научно-исследовательских работах ИППМ РАН.

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

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

- военная техника;

- медицинская техника;

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

- коммуникационные системы.

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

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

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

- Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика" (МИЭТ, 2003-2006г., 4 доклада, один из докладов отмечен дипломом);

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

- Юбилейная Международная научно-техническая конференция "50 лет модулярной арифметике" (МИЭТ, 2006г., 1 доклад).

Публикации

По теме диссертации автором опубликовано 13 печатных работ, подготовлено 4 отчета по НИР.

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

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

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

В данной главе:

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

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

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

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

Заключение

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

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

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

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

- не требуют дополнительной коррекции операндов и результата операции (для сумматоров по модулям вида 2п+1).

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

3. Предложены методы построения прямых и обратных преобразователей, которые, в отличие от известных методов:

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

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

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

- обеспечивают возможность гибкого проектирования в зависимости от разных критериев.

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

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

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

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

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

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

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

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

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

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

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

2. Амербаев В.М., Стемпковский A.JI., Широ Г.Э. Быстродействующий согласованный фильтр, построенный по модулярному принципу// Информационные технологии. 2004. - №9. - С. 5-12.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536с.

4. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986.-576с.

5. Виноградов И. М. Основы теории чисел. М.: Наука, 1981. 176с.

6. Евстигнеев В.Е. Недвоичная машинная арифметика и специализированные процессоры/ Под ред. Акушского И.Я. М.: МИФИ Сервис, 1992. - 267с.

7. Исаева Т.Ю., Корнилов А.И. Алгоритм декомпозиции логических функций, ориентированный на синтез быстродействующих цифровых устройств// Информационные технологии. №4,2001. - С. 26-31.

8. Калашников B.C. Основные виды архитектур модулярных сумматоров для двух операндов// Микроэлектроника и информатика-2004. Одиннадцатая всероссийская межвузовская конференция студентов и аспирантов: Тезисы докладов, М.:МИЭТ, 2004.-443с, С. 217.

9. Калашников B.C. Принципы построения двоичных и модулярных мультиоперандных сумматоров// Микроэлектроника и информатика-2005. Двенадцатая всероссийская межвузовская конференция студентов и аспирантов: Тезисы докладов, М.:МИЭТ, 2005. 444с, С. 209.

10. Калашников B.C., Ласточкин О.В., Семенов М.Ю. Лабораторный практикум по курсу "Основы логического синтеза средствами САПР Synopsys с использованием Verilog HDL"/ под ред. чл.-корр. РАН, д.т.н. А.Л. Стемпковского; М.: МИЭТ, 2004. - 88с.

11. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и связь, 1987. - 391с.

12. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы. М.: Издательский дом "Вильяме", 2001. - 832с.

13. Коёкин А.И. Структурные методы обеспечения надежности информационных систем// Диссертация на соискание ученой степени доктора технических наук. -Москва, 1974.-303с.

14. Конопелько В.К., Борискевич А.А. Контроль ошибок в цифровых устройствах// Учеб. пособие по курсам "Теория кодирования" и "Цифровые и микропроцессорные устройства". Мн.: БГУИР, 2003. 18с.

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

16. Корнилов А.И., Исаева Т.Ю., Семенов М.Ю. Методы логического синтеза сумматоров с ускоренным переносом по модулю (2п-1) на основе BDD-технологии// Известия ВУЗов. Электроника. 2004. - №3. - С. 54-60.

17. Корнилов А.И., Калашников B.C., Ласточкин О.В., Семенов М.Ю. Особенности построения умножителей по модулю (2п-1)// Известия ВУЗов. Электроника. 2006. -№1.-С. 55-59.

18. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976. -590с.

19. Стемпковский A.JI., Семенов М.Ю. Основы логического синтеза средствами САПР Synopsys с использованием Verilog HDL// Учебное пособие. М.: МИЭТ, 2005. -140с.

20. Титце У., Шенк К. Полупроводниковая схемотехника// Справочное руководство. М: Мир, 1982.-512с.

21. Торгашев В.А. Система остаточных классов и надежность ЦВМ. М.: Советское радио, 1973.-120с.

22. Угрюмов Е.П. Цифровая схемотехника. СПб.: БХВ-Петербург, 2002. - 528с.

23. Alia G., Martinelli Е. A VLSI Algorithm for Direct and Reverse Conversion from Weighted Binary Number System to Residue Number System// IEEE Transactions on Circuits and Systems, vol. CAS-31, no. 12, December 1984. P. 1033-1039.

24. Alia G., Martinelli E. Designing multioperand modular adders// IEEE Electronics Letters 4th, vol. 32, no. 1, January 1996. P. 22-23.

25. Barraclough S.R., Sotheran M., Burgin K., Wise A.P., Vadher A., Robbins W.P., Forsythe R.M. The Design and Implementation of the IMS A110 Image and Signal Processor// IEEE Custom Integrated Circuits Conf. 1989. - P. 24.5.1-24.5.4.

26. Barsi F., Maestrini P. Error Correcting Properties of Redundant Residue Number Systems// IEEE Transactions on Computers, vol. C-21, no. 3, March 1973. P. 307-315.

27. Barsi F., Maestrini P. Error Detection and Correction by Product Codes in Residue Number Systems// IEEE Transactions on Computers, vol. C-23, no. 9, September 1974. -P. 915-924.

28. Bayoumi M.A., Jullien G.A., Miller W.C. An Efficient VLSI Adder for DSP Architectures Based on RNS// IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP'85, vol. 10, April 1985.-P. 38.2.1-38.2.4

29. Bayoumi M.A., Jullien G.A., Miller W.C. A VLSI Implementation of Residue Adders// IEEE Transactions on Circuits and Systems, vol. CAS-34, no. 3, March 1987. P. 284288.

30. Becker В., Drechsler R. How Many Decomposition Types Do We Need?// Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institute National Polytechnique de Grenoble, France, December 19-20,1994. P. 1-5.

31. Beuchat J.L. Some Modular Adders and Multipliers for Field Programmable Gate Arrays// IEEE Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'03), 2003. 8p.

32. Bi G., Jones E. V. Fast Conversion between Binary and Residue Numbers// Electronics Letters, vol. 24, no. 19,15th September 1988. P. 1195-1197.

33. Bryant R.E. Graph-Based Algorithms// IEEE Transactions on Computers, vol. C-35, no. 8.-Aug. 1986.-P. 677-691.

34. Bryant R.E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams// ACM Computing, vol. 24, no. 3, 1992.

35. Burrascano P., Cardarilli G.C., Lojacono R., Martinelli G., Salerno M. RNS Fourier Transforms// ICASSP-88, International Conference on Acoustics, Speech and Signal Processing, Vol. 3,11-14 Aug. 1988, P. 1427-1430.

36. Burrascano P., Cardarilli G.C., Lojacono R., Martinelli G., Salerno M. Application of Number Theory to Structurally Passive Digital Filters// IEEE International Symposium on Circuits and Systems, vol. 2, Jun. 1988. P. 1775-1778.

37. Cao В., Srikanthan Т., Chang C.-H. Design of Residue-to-Binary Converter for a New 5-Moduli Superset Residue Number System// IEEE Circuits and Systems, 2004. ISCAS'04.

38. Proceedings of the 2004 International Symposium on, vol. 2, 23-26 May 2004. P. II-841-11-844.

39. Cardarilli G.C., Del Re A., Nannarelli A., Re M. Residue Number System Reconfigurable Datapath// ISCAS 2002, IEEE International Symposium on Circuits and Systems, vol. II, May 2002, P. II-756-11-759.

40. Cardarilli G.C., Lojacono R., Martinelli G., Salerno M. Structurally Passive Digital Filters in Residue Number Systems// IEEE Trans, on Circuits and Systems, vol. 35, no. 2, February 1988.-P. 149-158.

41. Cardarilli G.C., Nannarelli A., Re M. Reducing Power Dissipation in FIR Filters using the Residue Number System// Proc. of the 43rd IEEE Midwest Symposium on Circuits and Systems, Aug. 2000. P. 320-323.

42. Cardarilli G.C., Re M., Lojacono R. A new RNS FIR Filter Architecture// DSP-97, IEEE 13th International Conference on Digital Signal Processing, vol. 2, 2-4 Jul. 1997. P. 671674.

43. Cosentino R.J. Fault Tolerance in a Systolic Residue Arithmetic Processor Array// IEEE Transactions on Computers, vol. 37, no. 7, July 1988. P. 886-890.

44. Curiger A.V., Bonnenberg H., Kaeslin H. Regular VLSI Architectures for Multiplication Modulo (2n+l)// IEEE Journal of Solid-State Circuits, vol. 26, no. 7, July 1991. P. 990994.

45. Dimitrakopoulos G., Vergos H.T., Nikolos D., Efstathiou C. A Family of Parallel-Prefix Modulo 2n-l Adders// Proc. of the Application-Specific Systems, Architectures, and Processors (ASAP'03), 2003. P. 326-336.

46. Dugdale M. VLSI Implementation of Residue Adders Based on Binary Adders// Trans, on Circuits and Systems II: Analog and Digital Signal Processing, vol. 39, May 1992. P. 325-329.

47. Efstathiou C., Nikolos D., Kalamatianos J. Area-Time Efficient Modulo 2n-l Adder Design// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 41, no. 7, July 1994. P. 463-467.

48. Efstathiou С., Vergos H.T., Nikolos D. Modulo 2n±l Adder Design Using Select-Prefix Blocks// IEEE Transactions on Computers, vol. 52, no. 11, November 2003. P. 13991406.

49. Freking W.L., Parhi K.K. Low-Power FIR digital filters using residue arithmetic// 31st Asil. Conf Signals, Syst. Comput., Pacific Grove, CA, USA, vol. 1, November 1997. P. 739-743.

50. GroBschadl J. The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip// ACSAC'00, 16 Annual Conference, Computer Security Application, December 2000. P. 384-393.

51. Hiasat A.A. High-Speed and Reduced-Area Modular Adder Structures for RNS// IEEE Transactions on Computers, vol. 51, no. 1, January 2002. P. 84-89.

52. Hiasat A.A. Arithmetic binary to residue encoders for moduli (2n±2k+l)// Computers and Digital Techniques, IEE Proceedings, vol. 150, no. 6, November 2003. P. 369-374.

53. Hiasat A.A., Abdel-Aty-Zohdy H.S. Residue-to-Binary Arithmetic Converter for the Moduli Set (2k, 2k-l, 2ы-1)// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 45, no. 2, February 1998. P. 204-209.

54. Itoh N., Naemura Y., Makino H., Nakase Y., Yoshihara Т., Horiba Y. A 600-MHz 54x54-bit Multiplier with Rectangular-Styled Wallace Tree// IEEE Journal of Solid-State Circuits, vol. 36, no. 2, February 2001. P. 249-257.

55. Jenkins W.K., Altman E.J. Self-Checking Properties of Residue Number Error Checkers Based on Mixed Radix Conversion// IEEE Transactions on Circuits and Systems, vol. 35, no. 2, February 1988. P. 159-167.

56. Jenkins W.K., Jullien G.A., Dimitrov V.S. Residue Arithmetic With Applications in Digital Signal Processing, 1999. 67 p.

57. Jullien G.A. Number Theoretic Techniques in Digital Signal Processing// Advances in Electronics and Electron Physics, Academic Press Inc., vol. 80, Chapter 2, 1991. P. 69163.

58. Kalampoukas L., Nikolos D., Efstathiou C., Vergos H.T., Kalamatianos J. High-Speed Parallel-Prefix Modulo 2n-l Adders// IEEE Transactions on Computers, vol. 49, no. 7, July 2000.-P. 673-680.

59. Kebschull U., Rosenstiel W. Efficient Craph-Based Computation and Manipulation of Functional Decision Diagrams// Design Automation, 1993, with the European Event in ASIC Design. Proceedings 4th European Conference on, 22-25 February 1993. P. 278282.

60. KebschuII U., Schubert E., Rosenstiel W. Multilevel Logic Synthesis Based on Functional Decision Diagrams// Design Automation, 1992. Proc. 3rd European Conference on, 16-19 March 1992.-P. 43-47.

61. Kim Т., Jao W., Tjiang S. Arithmetic Optimization using Carry-Save-Adders// Proceedings on Design Automation Conference 1998, 15-19 June 1998. P. 433-438.

62. Kim Т., Jao W., Tjiang S. Circuit Optimization Using Carry-Save-Adder Cells// IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 10, October 1998.-P. 974-984.

63. Kim Т., Um J. A Practical Approach to the Synthesis of Arithmetic Circuits Using Carry-Save-Adders// IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, no. 5, May 2000. P.615-624.

64. Kornilov A., Isaeva T. Circuit Depth Optimization by BDD Based Function Decomposition// IFIP Workshop on Logic and Architecture Synthesis, Grenoble, France, 1994. -P.64-70.

65. Kornilov A., Isaeva Т., Syngaevsky V. Carry Circuit Depth Optimization by BDD Based Decomposition// Proc. of PATMOS'97 Workshop Louvain-la-Neuve, Belgium, Sep. 8-10,1997.-P. 89-98.

66. Krishna H., Sun J.-D. On Theory and Fast Algorithms for Error Correction in Residue Number System Product Codes// IEEE Transactions on Computers, vol. 42, no. 7, July 1993.-P. 840-853.

67. Larsson P., Nicol C.J. Transition Reduction in Carry-Save Adder Trees// Low Power Electronics and Design 1996, International Symposium on, 12-14 Aug. 1996.-P. 85-88.

68. Lim K.P., Premkumar A.B. A Modular Approach to the Computation of Convolution Sum Using Distributed Arithmetic Principles// IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 46, no. 1, Jan. 1999. P. 92-96.

69. Massey J.L. An Introduction to Contemporary Cryptology// Proceeding of the IEEE, vol. 76, no. 5, May 1988. P. 533-549.

70. Nannarelli A., Cardarilli G.C., Re M. Power-Delay Tradeoffs in Residue Number System. Circuits and Systems, 2003. ISCAS'03. Proceedings of the 2003 International Symposium on, vol. 5, May 2003. P. 413 -416.

71. Nannarelli A., Re M., Cardarilli G.C. Tradeoffs between Residue Number System and Traditional FIR Filters// ISCAS 2001, Proc. of IEEE International Symposium on Circuits and Systems, vol. II, May 2001. P. 305-308.

72. Orton G.A., Peppard L.E., Tavares S. E. New Fault Tolerant Techniques for Residue Number Systems// IEEE Transactions on Computers, vol. 41, no. 11, November 1992. -P.1453-1464.

73. Piestrak S.J. A High-Speed Realization of a Residue to Binary Number System Converter// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 42, no. 10, October 1995. P. 661-663.

74. Piestrak S.J. Design of Residue Generators and Multi-Operand Modular Adders Using Carry-Save Adders// Computer Arithmetic, 1991. Proc., 10th IEEE Symposium on, 26-28 June 1991.-P. 100-107.

75. Piestrak S.J. Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders// IEEE Transactions on Computers, vol. 423, no. 1, January 1994. P. 68-77.

76. Pourbigharaz F., Yassine H.M. Modulo-free Architecture for Binary to Residue Transformation with respect to {2m-l, 2m, 2m+l} Moduli Set// ISCAS'94., IEEE International Symposium on Circuits and Systems, vol. 2, 30 May 2 June 1994. - P. 317-320.

77. Pourbigharaz F., Yassine H.M. Simple Binary to Residue Transformation with Respect to 2m+l Moduli// IEE Proc.-Circuits Devices Syst., vol. 141, no. 6, December 1994. P. 522-526.

78. Radhakrishnan D., Preethy A.P. A novel 36-bit single fault tolerant multiplier using 5-bit moduli// IEEE TENCON 98, vol. 1, pp. 128-130, New Delhi, India, Dec. 1998.

79. Re A. Del., Nannarelli A., Re M. Implementation of Digital Filters in Carry-Save Residue Number System// IEEE Conference Record on the Thirty-Fifth Asilomar Conference on Signals, Systems and Computers, vol. 2,4-7 Nov. 2001. P. 1309-1313.

80. Taylor F.J. An RNS Discrete Fourier Transform Implementation// IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 38, no. 8, Aug. 1990. P. 1386—1394.

81. Um J., Kim T. An Optimal Allocation of Carry-Save-Adders in Arithmetic Circuits// IEEE Transactions on Computers, vol. 50, no. 3, March 2001. P. 215-233.

82. Um J., Kim T. Utilization of Carry-Save-Adders in Arithmetic Optimization// Proceedings Twelfth Annual IEEE International ASIC/SOC Conference, 15-18 September 1999.-P. 173-177.

83. Um J., Kim T. Wallace-Tree based Timing-Driven Synthesis of Arithmetic Circuits// ICVC'99. 6th International Conference on VLSI and CAD, 26-27 Oct 1999. P. 89-94.

84. Vergos H.T., Efstathiou C., Nikolos D. Diminished-One Modulo 2n+l Adder Design// IEEE Transactions on Computers, vol. 51, no. 12, December 2002. P. 1389-1399.

85. Wang W., Swamy M.N.S., Ahmad M.O. An Area-Time-Efficient Residue-to-Binary Converter// Circuits and Systems, 2000. Proceedings of the 43rd IEEE Midwest Symposium on, vol. 2, 8-11 August 2000. P. 904-907.

86. Wang W., Swamy M.N.S., Ahmad M.O. Moduli Selection in RNS for Efficient VLSI Implementation// Circuits and Systems, 2003. ISCAS'03. Proceedings of the 2003 International Symposium on, vol. 4, May 2003. P. IV-512-IV-515.

87. Wang W., Swamy M.N.S., Ahmad M.O., Wang Y. A Study of the Residue-to-Binary Converters for the Three-Moduli Sets// IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, vol. 50, no. 2, February 2003. P. 235-243.

88. Wang Y. Residue-to-Binary Converters Based on New Chinese Remainder Theorems// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 47, no. 3, March 2000. P. 197-205.

89. Wang Y., Song X., Aboulhamid M., Shen H. Adder Based Residue to Binary Number Converters for (2n-l, 2", 2n+l)// IEEE Transactions on Signal Processing, vol. 50, no. 7, July 2002.-P. 1772-1779.

90. Wang Z., Jullien G.A., Miller W.C. An Improved Residue-to-Binary Converter// IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, vol. 47, no. 9, September 2000. P. 1437-1440.

91. Watson R.W., Hastings C.W. Self-Checked Computation Using Residue Arithmetic// Proceedings of the IEEE, vol. 54, no. 12, December 1966.-P. 1920-1931.

92. Yang L.-L., Hanzo L. Coding Theory and Performance Of Redundant Residue Number System Codes// submitted to IEEE Transactions on Information Theory, 1999. 40 p.

93. Yang L.-L., Hanzo L. Redundant Residue Number System Based Error Correction Codes// IEEE Vehicular Technology Conference, 2001. IEEE VTC 54th, vol. 3, 7-11 October 2001.-P. 1472-1476.

94. Yassine H.M., Moore W.R. Improved mixed-radix conversion for residue number system architectures// Circuits, Devices and Systems, IEE Proceedings G, vol. 138, no. 1, February 1991.-P. 120-124.

95. Zimmermann R. Binary Adder Architectures for Cell-Based VLSI and their Synthesis// A dissertation submitted to the Swiss Federal Institute of Technology Zurich. Diss. ETH No. 12480, 1997.

96. Zimmermann R. Efficient VLSI Implementation of Modulo (2"±1) Addition and Multiplication// Proceedings 14lh IEEE Symposium on Computer Arithmetic, 14-16 April 1999.-P. 158-167.

97. Zimmermann R. Lecture notes on Computer Arithmetic: Principles, Architectures, and VLSI Design// Integrated Systems Laboratory, ETH Zurich, http://www.iis.ee.ethz.ch/zimmi/publications/comparithnotes.ps.gz, June 1998.

98. Zimmermann R., Curiger A., Bonnenberg H., Kaeslin H., Felber N., Fichtner W. A 177 Mbit/s VLSI Implementation of the International Data Encryption Algorithm// IEEE Journal of Solid-State Circuits, vol. 29, no. 3, March 1994.