article

Free access

Associative table lookup processing for multioperand residue arithmetic

Author:

Christos A. PapachristouAuthors Info & Claims

Journal of the ACM (JACM), Volume 34, Issue 2

Pages 376 - 396

https://doi.org/10.1145/23005.23017

Published: 01 April 1987 Publication History

PDF eReader

Abstract

This paper investigates the complexity of multioperand residue addition and multiplication implemented by associative table lookup processing. The complexity measure used is the size of the associative memory, that is, the number of matching words in memory. This measure largely depends on the residue recurrencies, or multiplicities, in the addition and multiplication tables module M. The major effort in this work is to evaluate the recurrencies in simultaneous multioperand residue addition and multiplication. The evaluation is simple in case of addition mod M, and also in multiplication mod M if M is prime. To treat the more difficult case of M nonprime, a recursive procedure was developed for computing the 2-operand multiplication recurrencies mod M. The basis of this technique is the precedence relationships associated with a tree representation of the factors of M. It is then shown that the general D-operand multiplication mod M, D > 2 and M nonprime, can be reduced to the 2-operand case by isomorphic transformation. Computation results of 2-operand residue arithmetic operations are provided. Applications to RNS arithmetic implementation are discussed.

References

[1]

BANERJI, D.K. A novel implementation method for addition and subtraction in residue number systems. IEEE Trans. Comput. 23, l (Jan. 1974), 106-109.

Google Scholar

[2]

BUTLER, J.T. On the number of locations required in the content-addressable memory implementation of multiple-valued function. In Proceedings of the 13th international Symposium on Multiple-Valued Logic. IEEE, New York, May, 1983, pp. 94-102.

Google Scholar

[3]

COLLINS, S.A. Numerical optical data processor. In Proceedings of the Society for Photo-Optical Instrumentation Engineering, vol. 128. SPIE, Bellingham, Wash. 1977, pp. 313-317.

Google Scholar

[4]

DEMICHELI, G., AND SANGIOVANNI-VICENTELLI, A. L. Multiple constrained folding of PLAs: Theory and applications. IEEE Trans. CAD oflnteg. Circuits and Syst. 2, 3 (July 1983), 151-180.

Google Scholar

[5]

FOSTER, C.C. Content Addressable Parallel Processors. Van Nostrand Reinhold, New York, 1976.

Crossref

Google Scholar

[6]

GARDNER, P. L. Functional memory and its microprogramming implications. IEEE Trans. Comput. 20, 7 (July 1971), 767-775.

Google Scholar

[7]

GARNER, H.L. The residue number systems. IRE Trans. Electron. Comput. 8, 2 (June 1959), 140-147.

Google Scholar

[8]

GARNER, H. L. Number systems and arithmetic. In Advances in Computers, voi. 6. Academic Press, Orlando, Fla., 1965, pp. 13 I- 194.

Google Scholar

[9]

GUEST, C. C., AND GAYLORD, T.K. Truth-table look-up optical processing utilizing binary and residue arithmetic. Appl. Optics 19, 7 (Apr. 1980), 1201-1207.

Google Scholar

[10]

GUEST, C. C., MIRSALEHI, M. M., AND GAYLOR, T.K. Residue number system truth-table lookup processing: Moduli selection and logical minimization. IEEE Trans. Comput. 33, l0 (Oct. 1984), 927-93 I.

Google Scholar

[11]

HACHTEL, G. D., NEWTON, A. R., AND SANGIOVANNI-VINCENTELLI, A. L. An algorithm for optimal PLA folding. IEEE Trans. CAD oflnteg. Circuits and Syst. 1, 2 (Apr. 1982), 63-77.

Google Scholar

[12]

HUANG, A. The implementation of a residue arithmetic unit via optical and other phenomena. In Proceedings of the International Optical Computing Conference, IEEE Catalog No. 75, CHO 941-5C. IEEE, New York, 1975, pp. 14-18.

Google Scholar

[13]

HUANG, C.H. A fully parallel mixed-radix conversion algorithm for residue number applications. IEEE Trans. Comput. 32, 4 (Apr. 1983), 398--402.

Google Scholar

[14]

JENKINS, W.j. A highly efficient residue combinatorial architecture for digital filters. Proc. IEEE 66, 6 (June 1978), 700-702.

Google Scholar

[15]

JULLIEN, G.A. Residue number scaling and other operations using ROM arrays. IEEE Trans. Comput. 27, 4 (Apr. 1978), 325-336.

Google Scholar

[16]

KOHONEN, T. Content-Addressable Memories. Springer-Verlag, New York, 1980.

Crossref

Google Scholar

[17]

MEAD, C., ANO CONWAY, L. Introduction to I/'LSI Systems. Addison-Wesley, Reading, Mass., 1980.

Crossref

Google Scholar

[18]

MILLER, D. D., AND POLKY, J.N. A residue number system implementation of the LMS algorithm using optical waveguide circuits. IEEE Trans. Comput. 32, 11 (Nov. 1983), 1013-1028.

Google Scholar

[19]

MoNouxmc MEMORIES. PAL Programmable Array Logic Handbook. 3rd ed. Monolithic Memories, Sunnyvale, Calif., 1983.

Crossref

Google Scholar

[20]

PAPACHRISTOU, C.A. Direct implementation of discrete and residue-based functions via optimal encoding: a programmable array logic approach. IEEE Trans. Comput. 32, 10 (Oct. 1983), 961-968.

Google Scholar

[21]

PARHAMI, B. Associative memories and processors: an overview and selected bibliography. Proc. IEEE 61, 6 (June 1973), 722-730.

Google Scholar

[22]

RAO, T. R. N., AND TREHAN, A.K. Binary logic for residue arithmetic using magnitude index. IEEE Trans. Comput. 19, 8 (Aug. 1970), 752-757.

Google Scholar

[23]

SASAKI, A. The basis for implementation of additive operations in the residue number system. IEEE Trans. Comput. 17, 11 (Nov. 1968), 1066-1073.

Google Scholar

[24]

S~GNET~CS CORPORATION. Integrated Fuse Logic. Signetics Corporation, Sunnyvale, Calif., Dec. 1980.

Google Scholar

[25]

SVOBODA, A., AND VALACH, M. Rational system of residue classes. In Stroje na Zpraccorani Informaci, Sbornik, Nakl. CSZV, Prague, 1957, pp. 9-37 (in English).

Google Scholar

[26]

SZAaO, N. S., AND TANAKA, R.I. Residue Arithmetic and Its Applications in Computer Technology. McGraw-Hill, New York, 1967.

Google Scholar

[27]

TAI, A. I., CINDRICH, I., FINEUP, J. R., AND ALEKSOFF, C.C. Optical residue arithmetic computer with programmable computation modules. Appl. Optics 18, 16 (Aug. 1979), 2812-2823.

Google Scholar

[28]

TAYLOR, F.J. A VLSI residue arithmetic multiplier. IEEE Trans. Comput. 31, 6 (June 1982), 540-546.

Google Scholar

Cited By

View all

Papachristou CHwang S(2005)A systolic array structure for matrix multiplication in the residue number systemSupercomputing10.1007/3-540-18991-2_40(716-731)Online publication date: 27-May-2005
https://doi.org/10.1007/3-540-18991-2_40
Ulman ZCzyzak M(1998)Highly parallel, fast scaling of numbers in nonredundant residue arithmeticIEEE Transactions on Signal Processing10.1109/78.65543246:2(487-496)Online publication date: 1-Feb-1998
https://dl.acm.org/doi/10.1109/78.655432
Chisvin LDuckworth R(1992)Content-Addressable and Associative MemoryAdvances in Computers Volume 3410.1016/S0065-2458(08)60326-5(159-235)Online publication date: 1992
https://doi.org/10.1016/S0065-2458(08)60326-5
Show More Cited By

Index Terms

Associative table lookup processing for multioperand residue arithmetic
1. Hardware
  1. Very large scale integration design

Recommendations

Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders

Residue generator is an essential building block of encoding/decoding circuitry for arithmetic error detecting codes and binary-to-residue number system (RNS) converter. In either case, a residue generator is an overhead for a system and as such it ...
A VLSI Residue Arithmetic Multiplier

Recently, residue arithmetic has received increased attention in the open literature. Using table lookup methods and high-speed memory, modular arithmetic has been demonstrated. However, the memory size limitation of ECL, bipolar, and high-speed MOS ...
High-Speed Multioperand Decimal Adders

There is increasing interest in hardware support for decimal arithmetic as a result of recent growth in commercial, financial, and Internet-based applications. Consequently, new specifications for decimal floating-point arithmetic have been added to the ...

Reviews

Reviewer: Giancarlo Bongiovanni

The residue number system (RNS) has been known in the mathematical literature for a long time and is computationally interesting in that it represents a viable system for high-speed computing. The reason for this is that addition and multiplication in RNS can be performed without the carry propagation since each digit of the result depends only on the corresponding digits of the operands. In this paper the author investigates the complexity of arithmetic operations on two or more operands in RNS by means of associative lookup tables, i.e., tables in which, essentially, the results corresponding to the possible inputs are appropriately stored and quickly retrieved. The author uses the size of the needed associative memory as the measure of complexity. A theory is developed under which such complexity is evaluated, and the following interesting results are obtained: In the proposed approach it is possible to avoid exhaustive enumerations carried on the tables; it is possible to reduce substantially the storage requirements and to improve the storage efficiency over the conventional memory lookup techniques. The author concludes the paper with the thought that “our approach demonstrates the viability of table lookup processing for residue arithmetic using the read-only associative memories of high technology, such as VLSI and electrooptics,” which is without a doubt interesting.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 34, Issue 2

April 1987

286 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/23005

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1987

Published in JACM Volume 34, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
471
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Papachristou CHwang S(2005)A systolic array structure for matrix multiplication in the residue number systemSupercomputing10.1007/3-540-18991-2_40(716-731)Online publication date: 27-May-2005
https://doi.org/10.1007/3-540-18991-2_40
Ulman ZCzyzak M(1998)Highly parallel, fast scaling of numbers in nonredundant residue arithmeticIEEE Transactions on Signal Processing10.1109/78.65543246:2(487-496)Online publication date: 1-Feb-1998
https://dl.acm.org/doi/10.1109/78.655432
Chisvin LDuckworth R(1992)Content-Addressable and Associative MemoryAdvances in Computers Volume 3410.1016/S0065-2458(08)60326-5(159-235)Online publication date: 1992
https://doi.org/10.1016/S0065-2458(08)60326-5
Dunham APatterson W(1991)Multiple-radix arithmetic on parallel machines and applications to cryptologyIEEE Proceedings of the SOUTHEASTCON '9110.1109/SECON.1991.147701(48-52)Online publication date: 1991
https://doi.org/10.1109/SECON.1991.147701
Piestrak S(1991)Design of residue generators and multioperand modular adders using carry-save adders[1991] Proceedings 10th IEEE Symposium on Computer Arithmetic10.1109/ARITH.1991.145540(100-107)Online publication date: 1991
https://doi.org/10.1109/ARITH.1991.145540

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders

A VLSI Residue Arithmetic Multiplier

High-Speed Multioperand Decimal Adders

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations