Сравнительное исследование и анализ методов аппаратной реализации сумматоров по модулю

Comparative study and analysis methods hardware implementation RNS-based Adders

Балака Е.С. Тельпухов Д.В. Осинин И.П. Городецкий Д.А.

24.01.2016 2232

№ 1 (23)

10. Информатика, вычислительная техника и управление

Цитировать:

Сравнительное исследование и анализ методов аппаратной реализации сумматоров по модулю // Universum: технические науки : электрон. научн. журн. Балака Е.С. [и др.]. 2016. № 1 (23). URL: https://7universum.com/ru/tech/archive/item/2887 (дата обращения: 18.11.2024).

Прочитать статью:

Keywords: Residue Number System, RNS-based Adders, bit arithmetic sections, Minimization of Boolean functions

АННОТАЦИЯ

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

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

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

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

ABSTRACT

Meeting the challenges of developing new architectures of computers with high performance and reliability of computation is a topical area of research. Continued growth in performance requirements results in development of Parallel Computing. One of the possible ways to build parallel systems is the application of RNS-based arithmetic, capable of performing arithmetic operations independently for each RNS-channel excluding the carry propagation. The performance of RNS-based devices depends on the approaches to the implementation of its computational units.

The results of a comparative analysis of different approaches to the design of RNS-based Adders are introduced in this article: implementation based on minimized Boolean functions in the class of polynomials, minimized DNF, the implementation of RNS-based adders on the arithmetic bit slices, as well as the implementation of parallel structures based on CSA-technology.

The structures based on CSA algorithms show the best performance for delay and hardware relative to other approaches in the range of 8-bit simple modulo. However, in special cases it is possible to get a speed increase about 40% relative to PPA due to the technique of analysis of truth tables of RNS-based Adders.

The prospects of using the simulation results for the implementation of efficient Pipelined RNS-based Multi-Operand Adders on the basis of the proposed methods in the base class of polynomial representations of Boolean functions, as well as on the basis of the arithmetic bit slices are discussed.

Список литературы:

1. Абдуллаев Д.А., Юнусов Д.Ю. Симметрия в булевых функциях и некоторых классах корректирующих кодов. – Ташкент: ФАН, 1987.
2. Амербаев В.М., Соловьев Р.А., Тельпухов Д.В. Реализация библиотеки модульных арифметических операций на основе алгоритмов минимизации логических функций // Известия Южного федерального университета. Технические науки. – 2013. – № 7 (144). – С. 221–225.
3. Бибило П.Н. О реализации модулярных сумматоров на FPGA / П.Н. Бибило, Д.А. Городецкий // Информатика. – 2011. – № 1. – С. 62–67.
4. Городецкий Д.А., Супрун В.П. Сумматоры унитарных кодов по модулю Р // Интеллектуальные системы и САПР (AIS’08 / CAD-2008). – М.: Физматлит, 2008. – Т.2. – С. 391–395.
5. Инютин С.А. Модулярные вычисления в сверхбольших компьютерных диапазонах // Электроника. – 2003. – № 6. – С. 54–61.
6. Ирхин В.П. Табличная реализация операций модулярной арифметики. Сб. науч. трудов Юбилейной Международной научно-технической конференции «50 лет модулярной арифметики». – 2005. – С. 268–273.
7. Кравченко В., Радченко Д. Современные технологии RTL-синтеза в продуктах компании Synopsys // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. – 2005. – № 2. – С. 66–69.
8. Леончик П.В. Программа минимизации системы булевых функций / [Электронный ресурс]. – Режим доступа: http://sarah.narod.ru/ (дата обращения: 12.01.2016).
9. Осинин И.П. Способ и устройство массового параллельно-конвейерного мультиоперандного суммирования на базе пирамидального выделения переносов / И.П. Осинин // Фундаментальные исследования. – 2013. – № 10, ч. 6. – С. 1228–1233.
10. Осинин И.П., Князьков В.С. Способ организации вычислений суммы N М-разрядных чисел // Патент РФ №2450327 от 10 мая 2012 г.
11. Сайт Отдела методологии проектирования интегральных схем ИППМ РАН / [Электронный ресурс]. – Режим доступа: http://icdm.ippm.ru/ (дата обращения: 12.01.2016).
12. Стемпковский А.Л., Амербаев В.М. Принцип факторизации в проблеме проектирования модулярных процессоров // VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем – 2014»: сб. трудов / под общ. Ред. Ак. РАН Стемпковского А.Л. – М.: ИППМ РАН, 2014. Часть IV. – С. 183–186.
13. Червяков Н.И., Бережной В.В., Оленев А.А. и др. Минимизация избыточности кода системы остаточных классов с одним контрольным основанием / Электронное моделирование. – 1994. – № 1. – Т. 16. – С. 56–61.
14. F.E.P. Dale Gallaher and P. Srinivasan The digit parallel method for fast RNS to weighted number system conversion for specific moduli, IEEE Transactions on Circuits and Systems – II: Analog and Digital Signal Processing, 1997.
15. Hariri A., Navi K., and Rastegar R. A new high dynamic ranga moduli set eith efficient reverse converter // Computers and Mathematics with Applications. – 2008. – Vol. 55, no. 4. – Р. 660–668,
16. Knowles S., A family of adders // Proceedings of the 15th IEEE Symposium on Computer Arithmetic, Los Alamitos, CA, USA. – 2001. – Р. 277–284.
17. Ladner R.E. and Fischer M. J., Parallel prefix computation // Journal of the Association for Computing Machinery. – 1980. – Vol 27, No 4. – Р. 831–838.
18. Omondi Amos, Premkumar Benjamin, Eds., Residue Number Systems: Theory and Implementation (Advances in Computer Science and Engineering Texts) London, UK: Imperial College Press, September 10, 2007).
19. Pedro Miguens Matutino, Hector Pettenghi, Ricardo Chaves, Leonel Sousa RNS Arithmetic Units for Modulo // 15th Euromicro Conference on Digital System Design. – 2012. – Р. 795–802.
20. The Donald O. Pederson Center for Electronic Systems Design. Espresso / [Электронный ресурс]. – Режим доступа: http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm (дата обращения: 12.01.2016).

References:

1. Abdullaev D.A., Junusov D.Ju. Symmetry in Boolean functions and certain classes of error-correcting codes. Tashkent, FAN Publ., 1987. 141 p. (In Russian).
2. Amerbaev V.M., Solovyev R.A., Telpuhov D.V. Library implementation of modular arithmetic operations, based on logic functions minimization algorithms. Izvestija Juzhnogo Federal'nogo Universiteta. Tehnicheskie nauki. [Izvestiya SFEDU. Engineering sciences]. 2013. no. 7 (144). pp. 221–225. (In Russian).
3. Bibilo P.N. On the implementation of modular adders on FPGA. Informatika. [Computer science]. 2011. no. 1. pp. 62–67. (In Russian).
4. Gorodeckij D.A., Suprun V.P. Adders unitary codes modulo P. Intellektual'nye sistemy i SAPR (AIS’08 / CAD-2008) [Intelligent systems in CAD (AIS’08 / CAD-2008)]. Moscow, Fizmatlit Publ., 2008. Vol.2, pp. 391–395. (In Russian).
5. Injutin S.A. RNS-based computing extra-large computer range. Elektronika. [Electronics]. 2003. no. 6. pp. 54–61. (In Russian).
6. Irhin V.P Tabular implementation of Residue Number System arithmetic operations. Sbornik nauchnyh trudov Jubilejnoj Mezhdunarodnoj nauchno-tehnicheskoj konferencii «50 let moduljarnoj arifmetiki» [Collection of scientific works Anniversary International Scientific Conference "50 years of Residue Number System"]. 2005. pp. 268–273. (In Russian).
7. Kravchenko V., Radchenko D. Modern technology RTL-synthesis products from Synopsys. ELEKTRONIKA: Nauka, Tehnologija, Biznes. [Electronics: Science, Technology, Business]. 2005, no. 2, pp. 66–69. (In Russian).
8. Leonchik P.V. Software minimization of Boolean functions. Available at: http://sarah.narod.ru/ (accessed 12 January 2016)
9. Osinin I.P. The method and apparatus of mass parallel-pipelined multi operands summation based the pyramidal allocation carry. Fundamental'nye issledovanija. [Basic research]. 2013, no.10, part 6. pp. 1228–1233. (In Russian).
10. Osinin I.P., Knjaz'kov V.S. A method of computing the amount of N the organization M-bit numbers. Patent RF, no.2450327. 2012 (In Russian).
11. Website of the Department of methodology of designing integrated circuits IPPM RAS. Available at: http://icdm.ippm.ru/ (accessed 12 January 2016).
12. Stempkovskij A.L., Amerbaev V.M. The Principle of Factorization in a Problem of Design of RNS-based Processors. VI Vserossijskaja nauchno-tehnicheskaja konferencija «Problemy razrabotki perspektivnyh mikro- i nanojelektronnyh sistem – 2014» [VI All-Russia Science&Technology Conference Problems of Advanced Micro-Nanoelectronic Systems Development - 2014]. Moscow, IPPM RAN Publ., 2014. Part IV. pp. 183–186. (In Russian).
13. Chervjakov N.I., Berezhnoj V.V., Olenev A.A., Kalmykov I.A. Minimizing redundancy code system of residual classes with a control base. Elektronnoe modelirovanie [Electronic modeling]. 1994, no. 1, Vol.16. pp. 56–61. (In Russian).
14. F.E.P. Dale Gallaher and P. Srinivasan The digit parallel method for fast RNS to weighted number system conversion for specific moduli, IEEE Transactions on Circuits and Systems – II: Analog and Digital Signal Processing, 1997.
15. Hariri A., Navi K., and Rastegar R. A new high dynamic ranga moduli set eith efficient reverse converter. Computers and Mathematics with Applications, vol. 55, no. 4, pp. 660–668, 2008.
16. Knowles S., A family of adders, Proceedings of the 15th IEEE Symposium on Computer Arithmetic, Los Alamitos, CA, USA, pp. 277 – 284, 2001.
17. Ladner R.E. and Fischer M.J., Parallel prefix computation, Journal of the Association for Computing Machinery, Vol 27, No 4, October 1980, pp. 831–838.
18. Omondi Amos, Premkumar Benjamin, Eds., Residue Number Systems: Theory and Implementation (Advances in Computer Science and Engineering Texts) London, UK: Imperial College Press, September 10, 2007).
19. Pedro Miguens Matutino, Hector Pettenghi, Ricardo Chaves, Leonel Sousa RNS Arithmetic Units for Modulo 15th Euromicro Conference on Digital System Design, pp. 795–802, 2012.
20. The Donald O. Pederson Center for Electronic Systems Design. Espresso. Available at: http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm (accessed 12 January 2016).

Информация об авторах

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

канд. техн. наук, н., с. н. с., ФГБУН «Институт проблем проектирования в микроэлектронике Российской академии наук», 124365, Российская Федерация, г. Москва, Зеленоград, Советская ул., 3

Balaka Ekaterina

Candidate of Engineering Sciences, senior research scientist, Institute for design problems in microelectronics of Russian Academy of Sciences, 124365, Russian Federation, Moscow, Zelenograd, Sovetskaya Street, 3

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

канд. техн. наук, нач. отд., ФГБУН «Институт проблем проектирования в микроэлектронике Российской академии наук», 124365, Российская Федерация, г. Москва, Зеленоград, Советская ул., 3

Telpukhov Dmitry

Candidate of Engineering Sciences, Head of Department, Institute for design problems in microelectronics of Russian Academy of Sciences, 124365, Russian Federation, Moscow, Zelenograd, Sovetskaya Street, 3

Осинин Илья Петрович

канд. техн. наук, ФГУП «Российский федеральный ядерный центр – Всероссийский научно-исследовательский институт экспериментальной физики», 607188, Российская Федерация, Нижегородская обл., г. Саров, пр. Мира, 37

Osinin Ilya

Candidate of Engineering Sciences, The Russian Federal Nuclear Center – All-Russian Scientific Research Institute of Experimental Physics (RFNC-VNIIEF), 607188, Russian Federation, Nizhny Novgorod region, Sarov, Mira ave., 37

Городецкий Данила Андреевич

канд. техн. наук, Объединенный институт проблем информатики НАНБ, 220012, Беларусь, г. Минск, ул. Сурганова, 6

Gorodecky Danila

Candidate of Engineering Sciences, The State Scientific Institution "The United Institute of Informatics Problems of the National Academy of Sciences of Belarus" (UIIP NASB), 220012, Belarus, Minsk, Surganov Street, 6