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

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

Тельпухов Дмитрий Владимирович

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

обработки сигналов

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

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

Москва - 2012

2 О ДЕК 2012

005047813

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

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

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

Официальные оппоненты: Инютин Сергей Арнольдович

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

Машевич Павел Романович кандидат технических наук, ОАО "АНГСТРЕМ", заместитель генерального директора, главный конструктор

Ведущая организация: ОАО НПЦ «ЭЛВИС»

Защита состоится 20 декабря 2012 г. в 15 часов 00 минут на заседании диссертационного совета Д 002.078.01 при Федеральном государственном бюджетном учреждении науки Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН) по адресу: 124365, Российская Федерация, г. Москва, Зеленоград, Советская ул., д.З.

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

Автореферат разослан 19 ноября 2012 года.

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

Жаров М.М.

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

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

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

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

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

Следует также отметить, что в области модулярных вычислений помимо традиционного направления возникли новые: модулярная логарифметика (в основе которой лежат труды Карла Фридриха Гаусса и Карла Густава Якоби), рекурсивная модулярная арифметика (предложенная академиком А. Л. Стемпковским), где открываются новые возможности реализации первичных преобразователей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Разработан алгоритм БПФ дискретного алгебраического преобразования Фурье над конечным полем Галуа по модулям простого числа Прота и его обобщений.

7. Результат п.6 распространён на модулярную арифметику по однотипным числам Прота в роли базисных оснований. Этот факт позволяет впервые использовать алгоритм БПФ для вычислений над кольцом вычетов по составному модулю. В литературе отсутствуют какие-либо прикладные применения чисел Прота.

Положения, вмносимыс на защиту.

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

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

- Новый подход в реализации модулярного сумматора большого числа слагаемых позволяет увеличить быстродействие сумматоров на 15% в сравнении с традиционной реализацией.

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

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

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

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

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

- системы видеонаблюдения;

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

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

- фото и видео техника;

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

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

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

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

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

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

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

- Обратных преобразователей на базе перевода в полиадический код;

- Операции циклической свертки на базе теоретико-числового

модулярного БПФ;

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

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

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

- III Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем - 2008" (МЭС-2008).

- 16-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика-2009

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

- IV Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем - 2010" (МЭС-2010).

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

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

- V Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем - 2012" (МЭС-2012).

- 1-я Всероссийская конференция «Проблемы математики и радиофизики в области информационной безопасности», Ставрополь, 2012.

Публикации

По теме диссертации автором опубликовано 12 печатных работ, 8 из которых опубликованы в журналах, рекомендованных ВАК. Подготовлен один отчет по НИР. Новое техническое решение защищено патентом на изобретение.

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

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

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

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

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

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

Большое количество работ посвящено реализации цифровых фильтров, быстрых преобразователей Фурье, алгоритмов цифровой обработки изображений в модулярной арифметике. Значительные усилия исследователей сосредоточены на модулях специального вида: 2м, 2', 2t+1. Однако, новым, перспективным вычислительным системам на базе модулярной арифметики уделено существенно меньшее внимание. В первой главе проводится анализ перспективных современных вычислительных систем на базе модулярной арифметики, одной из которых является модулярная логарифметика.

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

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

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

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

Рис. 1. Точки зрения на модульные вычисления

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

а) сверхскоростных вычислительных устройств, предназначенных для решения специальных задач;

б) отказоустойчивых, автономных вычислителей;

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

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

а) посредством иерархической редукции;

б) посредством рекурсивной (рекуррентной) редукции;

в) посредством многоярусной реализации модулярной логарифметики Рекурсивная модулярная арифметика (РМА), предложенная академиком

Стемпковским, позволяет свести все вычисления к вычислениям по технологичным основаниям. Жесткая ориентация на конкретную задачу обусловлена необходимостью выбора технологичных оснований qu q2, ..., qy и базисных оснований р\,рг ,-.-,рп таким образом, чтобы избежать внутренних переполнений во время вычисления заданной функции.

Формула (1) и рис.2 демонстрируют представление числа X в рекурсивной системе вычетов с к технологичными q\, q2, ..., <?k и двумя базисными модулями р\ и Pl-

(

Р2

Pl

Яi, Яг, ■■■, Як, (<?1 ,Яг,-,Як),\ Qi> Яг, -, Як, (<Ь Яг, -, Як)

\

р 1

(1)

X

qi

42

X

Як

Pl

Р2

п

qk

qi

qk

4i

q;

qk

Рис. 2. Представление чисел в рекурсивной системе вычетов

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

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

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

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

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

Ук

LUT

MUX

/

.z:

JL

elk Da Qa

REG

Db Qb

t

Ук+1

:X

k+1

Рис. 3. Ячейка систолического двоично-модулярного преобразователя

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

1 'т

Хк+1 = ror(Xk)

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

входных слов программа автоматически генерирует 7 файлов компонент в формате VHDL для дальнейшей загрузки в систему автоматизированного проектирования. Были проведены оценки быстродействия и аппаратных затрат для некоторых технологичных модулей 3-8 бит для входных данных разрядности 16 и 24 бита. Все оценки были получены в САПР Synopsys Synplify Pro для ПЛИС фирмы Altera семейства Stratix II, при одинаковых настройках синтезатора.

Таблица 1

Временные и аппаратные оценки_

16 битный вход 24 битный вход

модуль частота (MHz) ALUT/REG модуль частота (MHz) ALUT/REG

5 770.1 49/218 5 744.8 112/185

13 978.8 59/204 13 658.6 121/232

29 663.1 73/190 29 658.6 145/250

67 473.9 150/161 67 485.9 275/338

16 битный вход 24 битный вход

модуль частота (MHz) ALUT/REG модуль частота (MHz) ALUT/REG

107 434.6 194/163 107 458.9 321/338

139 274.9 164/139 139 282.9 307/365

191 290.4 138/139 191 274.4 243/365

223 260.7 164/136 223 272.6 293/365

251 263.9 75/117 251 245.2 139/391

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

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

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

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

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

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

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

В модулярной системе попарно взаимнопростых оснований (тп1,т2,...,тпп) восстановление числа (х1,х2, ...,хп) по китайской теореме об остатках происходит по формуле:

п

X = ^ а^ • Мг - <7 • М

¡=1

где щ £ Жт., а( = |лг£ • |М(-1| I - нормированный вычет по модулю т^

м

Ц 6 Ъ - нормированный ранг, М1 = —,М = П?=1т(-

Щ

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

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

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

к - \1од2п1

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

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

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

Модули в рекурсивной интрамодулярной системе подразделяются на два вида: технологичные модули </2» -»<7п> по которым, в конечном счете, ведутся вычисления, и базисные модули р1,р2, -,Рк> обеспечивающие покрытие динамического диапазона арифметической функции. Выбор оснований для рекурсивной модулярной системы должен начинаться с выбора технологичного набора модулей Идеология интрамодулярных вычислительных систем

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

На выходе данного алгоритма получаем набор минимальных базисных оснований с/2. —. Яп> и первое базисное основание р±.

НАЧАЛО

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

Подсчет фуь М(

(М(РУР) > Цр-1) ?

Да

и

Рис. 4. Алгоритм выбора технологичных модулей для рекурсивной интрамодулярной системы

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

1) Минимизация разрядности базисных модулей

2) Минимизация количества базисных модулей

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

Таблица 2

Результаты синтеза обратных преобразователей РМА

Длина/ разрядность Набор оснований рекурсивной интрамодулярной системы Аппаратные затраты (alut/reg) Временные затраты (Mhz)

Подход 1 Подход 2 Подход 1 Подход 2 Подход 1 Подход 2

8 6 Q = {3,5,7, 11} R= {13, 17} Q = {3,5,7, 11} R= {13, 17} 587/306 587/306 373,41 373,41

8 8 Q = {3,5,7,11} R= {13, 17, 19} Q= {3,5,7, 11} R= {13,37} 1478/638 771/319 336,47 325,31

8 10 Q= {3,5,7, 11} R= {13, 17, 19,23} Q= {3,5,7, 11} R= {13, 17,43} 3392/1302 1823/648 302,30 280,50

8 12 Q= {3,5,7, 11} R= {13, 17, 19,23,29} Q= {3,5,7, 11} R= {13,43,211} 7303/2593 4813/703 291,55 205,72

8 14 Q= {3,5,7, 11} R= {13, 17, 19, 23, 29,31} Q= {3,5, 7, 11} R= {13,17, 43,197} 7303/2593 7339/1366 291,55 199,52

Изучая полученные результаты можно сделать вывод о том, что первый подход обладает на 40% большим быстродействием, однако аппаратные затраты второго подхода существенно меньше (до 2х раз), так как требует меньшего количества немодульных узлов. Кроме того, количество тактов для осуществления обратного преобразования во втором подходе также меньше.

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

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

р. р= р. р. р. р> Х={Х1.Хг. Ха (X4.Xs.Xe)}

рекурсивной иитрамодулярной системы

Для проверки эффективности метода были построены и исследованы обратные преобразователи рекурсивной модулярной арифметики, реализованные прямым и ускоренным методом. Схемы были созданы для следующих наборов оснований: Q = {3,5,7} Р = {11} и Q = {3,5,7} Р = {11,13}. Синтез и верификация проводились с помощью САПР фирмы Altera:

Таблица 3

Результаты синтеза схем обратных преобразователей РМА_

Аппаратные затраты (ALUT/Registers) Тактовая частота (Mhz) Количество тактов преобразования

Набор 1 Прямой метод 88/95 462.53 7

Ускоренный метод 100/101 480.08 6

Набор 2 Прямой метод 258/224 446.23 12

Ускоренный метод 265/266 471.25 9

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

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

г ■ (г + 1)

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

1:2 = Я + 3 • г

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

увеличивается. Средняя величина — для большинства задач варьируется от 1,5 до 2,5.

¿2

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

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

Округление в двоичном коде достигается отбрасыванием двоичных разрядов, что в свою очередь эквивалентно делению на 2е, где 1 - число отбрасываемых разрядов.

а1 + а2 + а3 + ■■• + ап А =--¿7-

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

■ 2t + |аа|20 + - + (<?п • 2£ + |а„|20 А =--—-

, или

+

А = (Яг + Ч2 + Чз + - + Чп) + К12с + |а2|2с + |а3|2£ + - + \aJzt

2е

Необходимо учесть, что формирование слагаемых вида 2[ГП(_1т;_2 ...т^ (при переходе от полиадической к двоичной системе счисления) происходит методом обращения в таблицу. Соответственно, вместо запоминающих устройств, хранящих полноразрядные слагаемые, можно использовать таблицы со значениями qi и |а;[2с.

Формирование цифр полиадического кода

IF j , Tz3 Tz 1

X - 1 X ^ X Umfm> х jna_x -тп_г -...-т

т т т т

Пирамидальный сумматор

Округление

т —

2'

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

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

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

user interface

N

width — tw_width type

fft_gen.pl

Генератор Verilog описания БПФ

A À A i

muxer.v butlerfty.v complex mutt.v registr_cfiah.v manager.v stage.v J stage^exl.v

Synopsys DC

Генератор Testbench модуля БПФ

fft.vg

«i ib.«

testbench_generator.pt

-»- Cadence NC-Verilog

result

Рис. 7. Маршрут создания функционального описания модулярного БПФ при помощи генератора функциональных представлений

Генератор fft_gen.pl - создает схему БПФ Radix-2 Single-path Delay Feedback с округлением в процессе вычисления или с наращиванием разрядности. Генератор testbench_generator.pl - создает проверочный модуль fft tb.v для проверки (верификации) правильности работы схемы.

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

Были проведены эксперименты по оценке точности схем БПФ с округлением после каждой стадии алгоритма, и предлагаемой схемы в режиме точных вычислений. Оценка проводилась на БПФ устройствах с разрядностью входных данных - от 3 до 16 бит, и длиной преобразования от 8 до 256 точек. Оценка производилась средствами Cadence NC-verilog методом Монте-Карло. Следует отметить, что в оценке точности не были рассмотрены ошибки представления входных данных и поворачивающих множителей, а лишь ошибки округления при выполнении арифметических операций.

о; is

% I

s s

сС ф

CU Q. О. 1-

и О

> с

БПФ с округлением БПФ без округления 8точек

60 —В—16 точек

64 точки 128 точек

3 6 8 10 12 14 16 3 6 8 10 12 14 16 -•-256 точек Рис. 8. Результаты экспериментов по оценке точности БПФ

32 точки

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

1) В режиме фиксированной точки с округлением

2) В режиме накопления разрядности с фиксированной точкой

В обоих случаях использовалась архитектура Radix-2 Single-path Delay Feedback. . Оценка проводилась на БПФ устройствах с разрядностью входных данных - от 3 до 16 бит, и длиной преобразования от 8 до 256 точек. Экспериментальные оценки были получены с помощью САПР Design Compiler фирмы Synopsys (рис.9).

БПФ 64 точки

S о х и ш У S н S

а. х

го

X

а.

0) ч:

го т

s

6.

10 12 14 16

двоичныи БПФ с

округлением

—Я—двоичный БПФ без округления

-чАг-модулярный БПФ без округления

Рис. 9. Оценки быстродействия модулярных и двоичных схем БПФ

Кроме вычисления в целых числах модулярного дискретного преобразования Фурье тригонометрического базиса, было рассмотрено преобразование Фурье над конечным полем ОР(р). Базисом для данного преобразования являются простые числа Прота, (названные в честь математика Франсуа Прота), которые представляют собой числа вида р = <7 • 2е + 1, где q является нечётным положительным целым числом и /— положительное целое число, такое, что (? < 2'. Тогда, элемент у — \wi\p, где - примитивный элемент поля б'Д/?), порождает циклическую группу корней из единицы порядка 2е. Таким образом, можно определить преобразование последовательности чисел (Оп) (0 < п < 2е - 1), являющихся элементами Р в последовательность чисел (Ак) следующим образом:

2с-1

Лк =

(4.6)

Преобразование (4.6) является прямым аналогом дискретного преобразования

■ -25

Фурье тригонометрического базиса, в котором поворачивающие множители е1) N заменяются на у > а операции умножения и сложения комплексных чисел - на соответствующие операции в СР(р). Данное преобразование принято называть теоретико-числовым дискретным преобразованием Фурье в конечном поле.

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

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

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

а(к)

Ь(к)

шо(5(р„)

Рис. 10. Вычисление циклической свертки двух сигналов

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

128 точек

двоичная свертка

модулярная свертка

9 10 11 12 13 14 15 16 Разрядность операндов

Рис. 11. Вычисление циклической свертки двух сигналов

Рисунок 11 показывает, что использование предлагаемого метода теоретико-числового быстрого преобразования Фурье но однотипным числам Прота, вкупе с разработанными схемами прямых и обратных преобразователей, позволяет строить устройства вычисления циклической свертки демонстрирующие 10-50% увеличение производительности по сравнению с двоичными аналогами.

В заключении подведены итоги работы и сформулированы основные

выводы.

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

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

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

1. Проведён анализ и разработаны конвейерные схемы прямых и обратных преобразователей модулярной логарифметики, с точки зрения адаптации к структуре информационного потока, характерного для задач ЦОС.

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

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

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

необходимого числа тактов преобразования, увеличение тактовой частоты на 5 — 6 % при увеличении аппаратных затрат на 5 - 8%.

5. Достигнуто увеличение быстродействия на 10% для преобразователей из модулярного кода в позиционный за счет совмещения операции восстановления числа с операцией округления результата.

6. Увеличение быстродействия мультиоперандных модулярных сумматоров с большим числом входов на 15% было достигнуто благодаря методу подсчета однотипных слагаемых.

7. Разработан алгоритм дискретного алгебраического преобразования Фурье над конечным полем Галуа по модулю простого числа Прота и его обобщения. Разработано и спроектировано устройство, реализующее циклическую свертку на базе модулярного дискретно алгебраического преобразования Фурье по однотипным числам Прота. Показано, что использование предлагаемого метода теоретико-числового быстрого преобразования Фурье по однотипным числам Прота, вкупе с разработанными схемами прямых и обратных преобразователей, позволяет строить устройства вычисления циклической свертки, демонстрирующие 10-50% увеличение производительности по сравнению с двоичными аналогами.

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

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

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

1.Тельпухов Д.В., Амербаев В.М, Константинов A.B. Бивалентный дефект модулярных кодов и выбор технологичных модулей понижающий бивалентный дефект // III Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2008». Сб. научных тр. / под общ. ред. ак. РАН А.Л. Стемпковского. М.: ИППМ РАН, 2008. С. 462-465.

2. Амербаев В.М., Тельпухов Д.В., Шарамок A.B. Способ скрытого сложения и особенности его реализации // Известия ВУЗов. Электроника. 2009. № 3. С. 26-32.

3. Амербаев В.М., Романец Ю.В., Тельпухов Д.В., Шарамок A.B. Способ суммирования маскированного числа со снятием маски в процессе суммирования // Пат. РФ № 2372643; заявл. 05.12.2007; опубл. 10.11.2009.

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

5. Тельпухов Д.В., Балака Е.С., Константинов A.B. Разработка и сравнение различных вариантов быстродействующих MAC архитектур на базе непозиционных арифметик // Всероссийская конференция «Проведение научных исследований в области обработки, хранения, передачи и защиты информации». Ульяновск, Ульяновский государственный технический университет, 2009.

6. Тельпухов Д.В., Балака Е.С., Константинов A.B. Методы оптимизации синтезируемых IP-блоков при реализации "СнК" на основе ПЛИС // 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика - 2010». Сб. трудов. М.: МИЭТ, 2010.

7. Тельпухов Д.В., Балака Е.С. Быстрое преобразование Фурье в системе остаточных классов // Всероссийская научная конференция с элементами научной школы для молодежи «Параллельная компьютерная алгебра». Сб. трудов. Ставрополь, 2010. С. 135-139.

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

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

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

11. Тельпухов Д.В. Построение обратных преобразователей модулярной логарифметики для устройств цифровой обработки сигналов // Информационные технологии. 2011. № 4. С. 60-64.

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

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

и»

Отп. в типографии "Принт",

Москва, Зеленоград, ул. 1 Мая, д. 3, оф. 106, ИНН 5044024470 Заказ № 3110/12, тир. 100 экз. Уч. -Изд. л. 1,3. Формат 60x84 1/16

Введение.

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

1.1 Модулярная арифметика.

1.2 Модулярная логарифметика

1.3 Особенности скрытой реализации операций логарифметики конечного поля Галуа вР(р)

1.4 Интрамодулярные вычислительные структуры

1.5 Возможные области практического применения модулярной арифметики.

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

2.1 Выбор модулей для устройств модулярной логарифметики. Технологичные модули. Бивалентный дефект.

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

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

2.4 Обратные преобразователи МЛА на базе китайской теоремы об остатках.

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

3.1 Выбор оснований для устройств рекурсивной модулярной арифметики.

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

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

3.4 Построение модулярного сумматора большого числа слагаемых.

Глава 4. Применение разработанных методов реализации немодульных операций при проектировании БПФ преобразователя, работающего на базе нетрадиционных непозиционных арифметик.

4.1 Построение модулярных устройств ЦОС в режиме накопления разрядности.

4.1.1 Оценки точности.

4.1.2 Оценки быстродействия.

4.2 Теоретико-числовое дискретное преобразование Фурье в конечном поле. Построение быстрых свёрток.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Разработан алгоритм БПФ дискретного алгебраического преобразования Фурье над конечным полем Галуа по модулю простого числа Прота и его обобщением.

7. Результат п.6 распространён на модулярную арифметику по однотипным числам Прота в роли базисных оснований. Этот факт позволяет впервые разработать алгоритм БПФ над кольцом вычетов по составному модулю. В литературе отсутствуют какие-либо прикладные применения чисел Прота.

Положения, выносимые на защиту.

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

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

- Новый подход в реализации модулярного сумматора большого числа слагаемых позволяет увеличить быстродействие сумматоров на 15% в сравнении с традиционной реализацией.

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

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

- Метод построения ускоренного обратного преобразователя рекурсивной модулярной арифметики, реализованный на базе операции перевода в полиадический код, демонстрирует, в сравнении с традиционным, двукратное сокращение необходимого числа тактов преобразования, увеличение тактовой частоты на 5 — 6 % при увеличении аппаратных затрат на 5 - 8%.

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

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

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

- системы видеонаблюдения;

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

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

- фото и видео техника;

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

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

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

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

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

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

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

- Обратных преобразователей на базе перевода в полиадический код;

- Операции циклической свертки на базе теоретико-числового модулярного БПФ;

Спроектированная библиотека генераторов функциональных представлений позволяет в совокупности со стандартными средствами синтеза автоматизировать проектирование модулярных вычислительных систем. Разработанные методы и алгоритмы внедрены на предприятиях ООО «АНКАД» и ИППМ РАН.

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

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

- III Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем - 2008" (МЭС-2008).

- 16-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика-2009

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

- IV Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем - 2010" (МЭС-2010).

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

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

- V Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем - 2012" (МЭС-2012).

- 1-я Всероссийская конференция «Проблемы математики и радиофизики в области информационной безопасности», Ставрополь, 2012.

Публикации

По теме диссертации автором опубликовано 12 печатных работ, 8 из которых опубликованы в журналах, рекомендованных ВАК. Подготовлен один отчет по ПИР. Новое техническое решение защищено патентом на изобретение.

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

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

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

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

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

- Спроектирован генератор функциональных представлений для реализации RTL описания модулярного БПФ Radix-2 SPDF для различных длин и разрядностей входных данных и поворачивающих множителей. Представлен маршрут создания и оценок точности и производительности схем.

- Проведены эксперименты по оценке точности схем БПФ с округлением после каждой стадии алгоритма, и предлагаемой схемы в режиме точных вычислений. Предложенный подход вычислений в целых числах на базе модулярной системы вычетов, позволяет строить устройства ЦОС с улучшенными характеристиками точности. Выигрыш в точности вычислений при использовании режима вычислений в целых числах достигает 4-5 раз.

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

- Разработан алгоритм БПФ дискретного алгебраического преобразования Фурье над конечным полем Галуа по модулю простого числа Прота и его обобщением.

- Реализовано устройство вычисления циклической свертки на базе метода метода теоретико-числового быстрого преобразования Фурье по однотипным числам Прота. Продемонстрировано 10-50% увеличение производительности по сравнению с двоичными аналогами.

Заключение

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

1. Проведён анализ и разработаны конвейерные схемы прямых и обратных преобразователей модулярной логарифметики, с точки зрения адаптации к структуре информационного потока, характерного для задач ЦОС.

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

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

4. Разработан ускоренный обратный преобразователь рекурсивной модулярной арифметики, реализованный па базе операции перевода в полиадический код, демонстрирующий, в сравнении с традиционным, двукратное сокращение необходимого числа тактов преобразования, увеличение тактовой частоты на 5 - 6 % при увеличении аппаратных затрат на 5 - 8%.

5. Достигнуто увеличение быстродействия на 10% для преобразователей из модулярного кода в позиционный за счет совмещения операции восстановления числа с операцией округления результата.

6. Увеличение быстродействия мультиоперандных модулярных сумматоров с большим числом входов на 15% было достигнуто благодаря методу подсчета однотипных слагаемых.

7. Разработан алгоритм дискретного алгебраического преобразования Фурье над конечным полем Галуа по модулю простого числа Прота и его обобщением. Разработано и спроектировано устройство, реализующее циклическую свертку на базе модулярного дискретно алгебраического преобразования Фурье по однотипным числам Прота. Показано, что использование предлагаемого метода теоретико-числового быстрого преобразования Фурье по однотипным числам Прота, вкупе с разработанными схемами прямых и обратных преобразователей, позволяет строить устройства вычисления циклической свертки демонстрирующие 10-50% увеличение производительности по сравнению с двоичными аналогами.

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

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

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

2. Балака Е. С., Тельпухов Д. В. "Быстрое преобразование Фурье в системе остаточных классов", Сборник трудов, Всероссийская научная конференция с элементами научной школы для молодежи "Параллельная компьютерная алгебра" 2010. С. - 135 - 139.

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

4. G. L. Bernocchi, G.C. Cardarilli, A. D. Re, A. Nannarelli and М. Re/ Low-power adaptive Filter based on RNS components/ IEEE Int. Symp. on Circuits and Systems, pp. 3211-3214, May 2007.

5. Юбилейная Международная научно-техническая кон-ференция «50 лет модулярной арифметике»: Сб. науч-ных трудов. М.: ОАО «Ангстрем», МИЭТ, 2006. 775 с.

6. Современные проблемы вычислительной математики и математического моделирования; т. 1 Вычислительная математика, т. 2 Математическое моделирование, М.: Наука 2005.

7. Бухштаб А. А. Теория чисел. М.: "Просвещение", 1966. 385 с.

8. Корнилов А.И., Семенов М.Ю., Ласточкин О.В. // Принципы построения модулярных индексных умно-жителей. Известия ВУЗов. Электроника. 2004. №2.

9. Амербаев В.М., Стемпковский А.Л., Широ Г.Э. Моду-лярный быстродействующий согласованный фильтр // «50 лет модулярной арифметике»: Сб. научных трудов. М.: ОАО «Ангстрем», МИЭТ, 2006. С. 250 -267.

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

11. Koren J., Computer Arithmetic Algorithms Massachusetts, 2002.

12. Mehdi Hosseinzadeh, Amir Sabbagh Molahosseini, Keivan Navi, "A Fully Parallel Reverse Converter", International Journal of Electrical, Computer, and Systems Engineering, vol. 1 no. 3 2007 ISSN 1307-5179

13. Cardarilli, G.C. "RNS-to-binary conversion for efficient VLSI implementation", Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions, Vol. 45 no. 6, pp. 667 669, 1998.

14. Бивалентный дефект модулярных кодов и выбор технологичных модулей понижающий бивалентный дефект. В.М. Амербаев, Д.В. Тельпухов, А.В. Константинов-М:ИППМ РАН, МЕС-2008, Сб. Трудов.

15. Шауман A.M., Основы машинной арифметики. JIe-нинград: изд. ЛГУ, 1979.

16. Arnold M.G., Residue Logarithmic number System, Theory and Implementation // Computer Arithmetic, 27-29 June 2005. P. 196-205.

17. Preethy A.P. and Radhakrishnan D. "An RNS Based Logarithmic Adder". IEE Proceedings Computers and Digital Techniques, vol. 147, issue 4, pp. 283-296, July 2000.

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

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

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

21. Radhakrishnan D., Preethy А. А 32 bit multiplier architecture using Galois fields// The 2nd European Parallel and Distributed Syst. Conf., Vienna, Austria, Jul. 1998. Pages: 94-99.

22. Radhakrishnan D., Yuan Y. "Fast and highly compact RNS multipliers". INTERNATIONAL JOURNAL OF ELECTRONICS 1991, vol. 70, no. 2, pp. 281293.

23. Radhakrishnan D., Yuan Y. A fast RNS Galois field multiplier// Circuits and Systems, 1990. IEEE International Symposium on, 1-3 May 1990. Vol.4. Pages: 2909-2912.

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

25. Балака Е. С., Константинов А. В., Тельпухов Д. В. Применение аппарата модулярной логарифметики для решения специальных задач матричной алгебры, МЭС 2012, на рецензии.

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

27. Zelniker G., Taylor F.J., A Reduced Complexity Finite Field ALU // JEEE Truns. Sire. Syst. Dec. 1991. V. 38.

28. Williams T.A. Circuit for Adding and/or Substracting Re-presentation -U.S. Patent, № 4, 727, 508. Feb.23 1988.

29. Preethy A.P., Padhakrishnan D. An RNS based logarithmic adder // JEEE Proceeding, Computer and Digital Tech-niques. July, 2000. V. 147, Issue 4. P. 283296.

30. A.P. 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.

31. D. Radhakrishnan and A.P. Preethy, "A Novel 36-bit Single Fault Tolerant Multiplier using 5-bit Moduli", IEEE Intl. Conf. Global Connectivity in Energy, Computer, Communication and Control (TENCON 98), pp. 128-130, vol. I, New Delhi, India, Dec. 1998.

32. Виноград С., Коуэн Дж. Д. Надежные вычисления при наличии шумов. М.: Наука, 1968. 112 с.

33. Воеводин В.В. Вычислительная математика и структура алгоритмов. М.: Изд. МГУ, 2006.

34. Современные проблемы вычислительной математики и математического моделирования: в 2 т. / Т. 1: Вычис-лительная математика, Т. 2: Математическое модели-рование. М.: Наука, 2005.

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

36. А.Л.Глебов, Гурарий М.М., Егоров Ю.Б., Жаров М.М., Русаков С.Г., Ульянов СЛ., Стемпковский A.JI. Акту-альные проблемы моделирования в системах автоматизации схемотехнического проектирования // под. общ. ред. Стемпковского А Л. М.: Наука, 2003. 430 с.

37. Соболев А.Н., Кириллов В.М. Физические основы технических средств обеспечения информационной безопасности: Учеб. пособие. — М.: Гелиос АРВ, 2004. 224 с.

38. Амербаев В.М., Тельпухов Д.В., Шарамок А.В., "Способ скрытого сложения и особенности его реализации", Известия ВУЗов. Электроника. 2009. № 3(77). Стр. 26 32.

39. R. Conway and J. Nelson, "Improved RNS FIR Filter Architectures," IEEE Transactions On Circuits and Systems II, Vol. 51, No. 1, pp. 26-28, 2004. 107

40. R. N. Bracewell, Discrete Hartley transform, J. Opt. Soc. Am. 73(12), 1832-1835 (1983).

41. W. Wei et al., "RNS application for digital image processing," Proceedings of the 4th IEEE international workshop on system-on-chip for real time applications, Canada, pp. 77-80, 2004.

42. S. Yen, S. Kim, S. Lim and S. Moon, "RSA Speedup with Chinese Remainder Theorem Immune against Hardware Fault Cryptanalysis," IEEE Transactions on Computers, vol. 52, no. 4, pp. 461-472, 2003.

43. J. Ramirez, et al., "Fast RNS FPL-Based Communications Receiver Design and Implementation," Proceedings of the 12th Int'l Conf. Field Programmable Logic, pp. 472-481, 2002.

44. F. Barsi and P. Maestrini, "Error correcting properties of redundant residue number systems," IEEE Transactions on Computers, vol. 23, no.9, pp. 915923.

45. R. W. Watson and C. W. Hastings, "Self-checked computation using residue arithmetic," Proceedings of the IEEE, 1966, vol. 54, pp. 1920-1931.

46. A. Omondi and B. Premkumar, "Residue Number System: Theory and Implementation," Imperial College Press 2007, ISBN 978-1-86094-866-4.

47. G. C. Cardarilli, A. Nanareelli, and M. Re, "Reducing power dissipation in FIR filters using the residue number system," Proceedings of the 43rd IEEE Midwest Symposium on Circuits and Systems, Vol. 2, pp. 320-323, 2000.

48. A. Nanareelli, M. Re, and G. C. Cardarilli, "Tradeoffs between residue number system and traditional FIR filters," The 2001 IEEE International Symposium on Circuits and Systems, Vol. 2, pp. 305-308, 2001.

49. В. Cao, C. Chang, and T. Sirkanthan, "A residue-to-binary converter for a new five- moduli set," IEEE Transactions on Circuits and Systems, 35 (11), 1998

50. He S., Torkelson M. A New Approach to Pipeline FFT Processor// Proceedings 10th International Parallel Processing Symposium (IPPS '96). 1996. P. 766 770.

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

52. Radhakrishnan D. and Preethy А. P., "A Parallel Approach to Direct Analog-to-Residue Conversion", Information Process. Lett, (to be published).

53. Radhakrishnan D. and Preethy A. P., "A Direct Analog-to-Residue Converter", IEEE Intl. Conf. Global Connectivity in Energy, Computer, Communication and Control (TENCON 98), 336-339, New Delhi, India

54. Radhakrishnan D. and Preethy A. P., 1998, "A New Approach to Data Conversion: Direct Analog-to-Residue Converter", IEEE Intl. Conf. on Acoustics, Speech and Signal Processing, 3013-3016, Seattle, USA

55. Abdelfattah, O. , 2010, "Direct residue-to-analog conversion scheme based on Chinese Remainder Theorem", Electronics, Circuits, and Systems (ICECS), 2010 17th IEEE International Conference, Montreal, Canada, 687 690

56. B. Parhami and C.Y. Hung. 1994. "Optimal table look up schemes for VLSI implementation of input/output conversions and other residue number operations". In: VLSI Signal Processing VII ,IEEE Press, New York

57. G. Alia and E. Marlinelli.1990. VLSI binary-residue converters for pipelined processing // The Computer Journal, 33(5): 473 475

58. S. Piestralc. 1994. Design of residue generators and multioperand modular adders using carry save adders. IEEE Transactions oh Computers, 42(1): 68-77.

59. A. Mohan. 1999. Efficient design of binary to RNS converters. Journal of Circuits and Systems, 9 (3/4): 145-154.

60. Birreck, D.; Drolshagen, A.; Anheier, W.; Laur, R.: Implementation of a Binary-to-RNS-Converter. Proc.o.t.Eurochip Workshop o. VLSI Design Training. (1994) p. 284-289

61. M. Bhardwaj, T. Srikanthan, С. T. Clarke: VLSI costs of arithmetic parallelism: a residue reverse conversion perspective. Proceeding ARITH '99 Proceedings of the 14th IEEE Symposium on Computer Arithmetic

62. Д. В. Тельпухов "Построение обратных преобразователей модулярной логарифметики для устройств цифровой обработки сигналов", Информационные технологии. 2011. № 4. Стр. 60 - 64.

63. Джон Стиллвелл, "Математика и ее история", Москва-Ижевск: Институт компьютерных исследований, 2004. 531с.

64. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. -324с.

65. Балака Е. С., Константинов А. В., Тельпухов Д. В. Реализация обратного преобразователя модулярной арифметики совмещенного с операцией округления для задач ЦОС, МЭС 2012, на рецензии.

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

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

68. Richard J. Higgins, Digital Signal Processing in VLSI, Prentice-Hall,1990.

69. L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing, Prentice-Hall, 1975

70. Полард Дж., Быстрые преобразования Фурье в конечном поле. Применение теории чисел в цифровой обработке сигналов, М.: Радио и связь, 1983

71. Blahut R. Е., Fast algoriyhms for digital signal processing, MA: Addison-Wesley, 1987

72. Nussbaumer, Fast Fourier Transform and convolution algorithms, Berlin: Springer-Verlag, 1982

73. J. W. Cooley and J. W. Tukey, An Algorithm for the Machine Computation of Complex Fourier Series, Mathematics Computation, Vol. 19, pp. 297-301, April 1965.

74. E.H. Wold and A.M. Despain. "Pipeline and parallel-pipeline FFT processors for VLSI implementation", IEEE Trans. Comput., C-33(5):414-426, May 1984.

75. Ben-Dau Tseng, G. A. Jullien, William C. Miller "Implementation of FFT Structures Using the Residue Number System". IEEE Transactions On Computers, vol. C-28, no. 11, November 1979.

76. Taylor, Fred J, "A more efficient residue arithmetic implementation of the FFT". Computer Arithmetic (ARITH), 1985 IEEE 7th Symposium, 4-6 June 1985, pp. 243 249. ' ' <

77. Wei-Hsin Chang and Truong Q. Nguyen, "On the Fixed-Point Accuracy Analysis of FFT Algorithms", IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 56, NO. 10, OCTOBER 2008

78. C. J.Weinstein, "Quantization Effects in Digital Filters," MIT Lincoln LAB, Lexington, MA, Tech. Rep.AD0706862, Nov. 1969

79. Муттер B.M., "Основы помехо-устойчивой телепередачи информации", изд-во "ЭНЕРГОАТОМИЗДАТ" Ленинградское отд., Ленинград, 1990, стр.285.

80. Adamson I. Т., "Introduction to Field Theory", Oliver & Boyd, London, Interscience, New York, 1964. MR 33 # 7325: