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

• Семенов, Михаил Юрьевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Семенов, Михаил Юрьевич

Введение.

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

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

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

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

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

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

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

2.2. Методы аппаратной реализации сумматоров по модулю (2"+1). Сравнение и анализ типовых и оптимизированных структур.

2.3. Методы аппаратной реализации сумматоров по модулю (2п-1). Сравнение и анализ типовых и оптимизированных структур.

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

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

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

3.1. Архитектура и принципы функционирования индексного модулярного умножителя.

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

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

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

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

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

4.1. Математический алгоритм восстановления целого числа по его модулярному представлению.

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

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

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

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

5.1. Методы аппаратной реализации КИХ-фильтров в прямой и транспонированной формах.

5.2. Анализ и реализация фильтров в двоичной системе счисления.

5.3. Анализ и реализация фильтров в модулярной арифметике.

Выводы по главе 5.

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

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

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

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

В 70-80-е годы были проведены значительные теоретические исследования в области модулярной арифметики (в том числе и в России) и реализован ряд высокоэффективных вычислительных систем на ее основе. Однако данное направление не получило дальнейшего широкого развития во многом из-за проблем в реализации этих устройств, связанных с элементной базой, принципиально ориентированной на двоичную булеву арифметику. В настоящее время с развитием интегральной схемотехники появляются возможности по использованию новых методов проектирования (технология проектирования систем на кристалле - SoC) как для отдельных узлов, реализующих вычислительные операции, так и устройств в целом. Интегральное исполнение устройств, под которым здесь, прежде всего, понимается возможность гибкого проектирования и выбора тобрй элементной базы, дает возможность реализовывать устройства с применением модулярной арифметики также эффективно, как и для обычной двоичной. Таким образом, проблема реализации систем с применением модулярной арифметики, в частности устройств ЦОС, в интегральном исполнении является с одной стороны новой и малоисследованной, а с другой - обещающей высокую эффективность,.что доказано предыдущими поколениями вычислительной техники.

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

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

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

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

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

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

5. Анализ и сравнение реальных устройств ЦОС, реализованных в двоичной системе счисления и в модулярной арифметике.

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

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

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

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

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

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

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

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

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

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

2. Методы логического синтеза сумматоров с ускоренным переносом по модулю вида (2"-7) на основе BDD-технологии. Основной принцип декомпозиции функций переноса для сумматоров по модулю (2"-7).

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

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

5. Принципы построения КИХ-фильтров в транспонированной форме с применением аппарата модулярной арифметики.

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

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

Разработан ряд вспомогательных программ, генерирующих синтезируемые Verilog-описания отдельных блоков, используемых при проектировании данных устройств, что позволяет в1 совокупности со стандартными средствами s'синтеза автоматизировать их структурное проектирование.

Результаты диссертации внедрены и использовались в следующих организациях: ГУ НПК "Технологический Центр", МИЭТ, а также использовались в научно-исследовательских работах ИППМ РАН.

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

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

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

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

- Десятая межвузовская НТК "Микроэлектроника и информатика-2003", Москва 2003;

- Одиннадцатая межвузовская НТК "Микроэлектроника и информатика-2004", Москва 2004.

Публикации

По вопросам диссертации автором опубликовано 6 печатных работ, 1 отчет по завершенному НИР и 2 выступления на Всероссийских конференциях.

Список печатных работ приведен в конце автореферата.

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

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

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Семенов, Михаил Юрьевич

Основные результаты диссертации:

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

2. Проведен анализ и сравнение типовых структур модулярных сумматоров, выполненных с применением блоков двоичной арифметики. Для сумматоров по модулям типа (2"+1) и (2"-7) разработаны методы аппаратной реализации в интегральном исполнении, обеспечивающие выигрыш по занимаемой площади до 25-30%.

3. Разработаны методы логического синтеза сумматоров по модулю (Т-1) на основе BDD-технологии, в том числе для функций переноса. Сформулирован основной принцип декомпозиции функций переноса для сумматоров данного типа. На основе полученных методов предложены методы схемотехнической реализации сумматоров по модулю {Т-1) в базисе из мультиплексоров и в базисе элементов 2И-ИЛИ.

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат технических наук Семенов, Михаил Юрьевич, 2005 год

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

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

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

4. Бокарев А.В. Оценка затрат при модулярной реализации согласованного фильтра // Микроэлектроника и информатика-2001: Восьмая всероссийская межвузовская конференция студентов и аспирантов: Тезисы докладов, М.: МИЭТ, 2001. 336 с. - С. 90.

5. Виноградов И.М. Основы теории чисел. М.: Наука, Главная редакция физико-математической литературы, 1981. - 176 с.

6. Гольденберг JI.M., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов.- М.: Радио и связь, 1990. 256 с.

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

8. Жуков О.Д. Обработка числовых данных с повышенной точностью в модулярной алгебре // Информационные технологии. 2004. - Вып. 2. - С. 1015.

9. Инютин С.А. Теория и методы моделирования вычислительных структур с параллелизмом машинных операций // Автореферат на соискание ученой степени доктора технических наук, Москва. 2001.

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

11. Исаева Т.Ю. Разработка и исследование методов логического синтеза быстродействующих КМОП БИС // Автореферат на соискание ученой степени кандидата технических наук, Москва. 2002.

12. Исследование методов проектирования и разработка программных средствсинтеза быстродействующих арифметических устройств // Заключительный отчет по НИР "Вега-0-К-2003" (проект № 1.5/03) (Инв. №02.2.00405859),-М.гИППМ РАН. -2003.

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

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

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

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

17. Корнилов А.И. Построение быстродействующих арифметических устройств в одном универсальном логическом базисе // Техника средств связи. Сер. Микроэлектронная аппаратура. 1990. - Вып.1-2(12-13). - С. 41-47.

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

19. Корнилов А.И., Семенов М.Ю. Преобразователь из модулярного представления в двоичную систему счисления на основе алгоритма с предварительной обработкой данных // Известия ВУЗов. Электроника. 2003. - Вып. 3. - С. 54-58.

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

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

22. Сергиенко А.Б. Цифровая обработка сигналов. СПб.: Питер, 2002. - 608 с.

23. Стемпковский A.JL, Корнилов А.И., Семенов М.Ю. Особенности реализации устройств цифровой обработки сигналов в интегральном исполнении с применением модулярной арифметики // Информационные технологии. 2004. -Вып. 2.-С. 2-9.

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

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

26. Финько О.А. Модулярная арифметика параллельных логических вычислений / Под ред. В.Д. Малюгина. М.: Институт проблем управления РАН; Краснодар: Краснодарский военный институт, 2003.-224 с.

27. Barraclough S.R., Sotheran М., Burgin К., Wise А.Р., 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.

28. Bryant R.E. Graph-Based Algorithms // IEEE Transactions on Computers- Aug. 1986. V. C-35, N 8. - P. 677-691.

29. Bryant R.E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams // ACM Computing. 1992. - V. 24, N 3.

30. Bayomi M.A., Jullien G.A. A VLSI Implementation of the Residue Adders // IEEE Trans, on Circuits and Systems. March 1987. - V. 34, N 3. - P. 284-288.

31. Becker В., Drechsler R. How Many Decomposition Types Do We Need? // Proc.of

32. IP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, 19-20 December, 1994.

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

34. 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.-Jun.l988.-V. 2.-P. 1775-1778.

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

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

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

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

39. David R.Smith. "Verilog Styles for Synthesis of Digital Systems", Prentice Hall, Inc. 2000.

40. Del Re A., 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, 4-7 Nov. 2001 V. 2. - P. 13091313.

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

42. Efstathiou C., Vergos H.T. Modified Booth l's Complement and Modulo 2n-l Multipliers // ICECS 2000, The 7th IEEE International Conference on Electronics, Circuits and Systems, 2000. V. 2. - P. 637-640.

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

44. Hiasat A. New Memoryless, mod (2n±l) Residue Multiplier // IEEE Electronic Letters, 30 Januaiy 1992. -V. 28, N3. P. 314-315.

45. Hiasat A. RNS Arithmetic Multiplier for Medium and Large Moduli // IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. -Sept. 2000. V. 47, N 9. - P: 937-940.

46. Jullien G.A. Number Theoretic Techniques in Digital Signal Processing // Academic Press Inc., Advances in Electronic and Electron Physics. 1991. - V. 80, Chapter 2. -P. 69-163.

47. Kebschull U., Schubert E., Rosenstiel W. Multilevel Logic Synthesis Based on Functional Decision Diagrams // Proc. of ICC AD. 1992. - P. 43-47.

48. 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.

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

50. 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. Jan. 1999. - V. 46, N 1. - P. 9296.

51. Massey James L. An Introduction to Contemporary Cryptology // Proc. of IEEE. May 1988. - V. 76, N 5. - P. 533-549.

52. 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. May 2001. - V. II. - P. 305-308.

53. Preethy A. P., Radhakrishnan D., Omondi A. Fault-tolerance Scheme for an RNS MAC: Performance and Cost Analysis // ISC AS 2001, The 2001 IEEE International Symposium on Circuits and Systems, 6-9 May 2001. -V. 2. P. 717-720.

54. Radhakrishnan D., Yuan Y. A Fast RNS Galois Field Multiplier // IEEE International Symposium on Circuits and Systems. May 1990. -V. 4. - P. 2909-2912.

55. Radhakrishnan D., Pyon T. Fault Tolerance in RNS: An Efficient Approach // ICCD'90, IEEE International Conference on Computer Design, 17-19 September 1990.-P. 41-44.

56. Radhakrishnan D., Yuan Y. Novel Approaches to the Design of VLSI RNS Multipliers // IEEE Trans, on Circuits and Systems II: Analog and Digital Signal Processing. - January 1992. - V. 39, N 1. - P. 52-57.

57. Slegel T.J., Veracca R.J. Design and performance of the IBM Enterprise System/9000 Type 9121 vector facility // IBM J. Res. Develop. May 1991. - V. 35. - P. 367-381.

58. Soderstrand M.A., Jenkins W.K., Jullien G.A., Taylor F.J. (EDS) Modern Application of Residue Number System Arithmetic to Digital Signal Processing. -New York: IEEE Press, 1986.

59. Taylor F.J. An RNS Discrete Fourier Transform Implementation // IEEE Transactions on Acoustics, Speech, and Signal Processing. Aug. 1990. - V. 38, N 8. - P. 13861394.

60. Wall Larry, Christiansen Tom and Schwartz Randal with Stephen Potter Programming Perl, Second Edition. O'Reilly & Associates, Inc. Copyright 1996.

61. Walter C.D. Systolic Modular Multiplier // IEEE Trans. Computers. Mar. 1993. -V. 42, N3.-P. 376-378.