Abstract
This paper describes a new scheme for matrix multiplication in the residue number system (RNS) by a VLSI systolic structure. The basic goal is to accelerate matrix multiplication by exploiting the "double parallelism" involved in the systolic structure and in the RNS. The scheme consists of a N × N rhombus-like array of residue-based processors for RNS N × N matrix multiplication. Each processor operates in parallel, pipeline or hybrid modes using an arrangement of q moduli adders and multipliers, q>1. The operations of residue addition and multiplication are performed by associative table lookup processing, which has been shown to be particularly efficient for fast residue arithmetic implementations in VLSI technology.
The time performance of this method was shown experimentally to be very good for large matrix multiplications. Thus, the proposed scheme could be very attractive in special purpose signal processing computers that require a lot of fast linear operations.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Richard P. Brent, and H.T. Kung: A Regular Layout for Parallel Adders. IEEE Transactions on Computers, Vol. C-31, No. 3, 260–264, Mar. (1982)
Richard P. Brent, and H.T. Kung: The Area-Time Complexity of Binary Multiplication. Journal of The Association for Computing Machinery, Vol. 28, No. 3, 521–534, July (1981)
K. Bromley, J.J.Symanski, J.M.Speiser, and H.J.Whitehouse: ”Systolic Array Processor Developments” in VLSI Systems and Computations. H.T.Kung, R.F.Sproull, and G.L.Steele(eds.): Carnegie-Mellon University, Computer Science Press, 273–284, Oct. (1981)
H.L. Garner: ”Number Systems and Arithmetic” in Advances in Computers, 6, 131–194, (1965)
H.L. Garner et al.: Residue Number Systems for Computers. ASD TR 61-483, Information Systems Laboratory, Univ. of Michigan, Ann Arbor, Mich., Oct. (1961)
C.C. Guest, M.M. Mirsalehi, and T.K. Gaylord: Residue Number System Truth-Table Look-Up Processing — Moduli Selection and Logical Minimization. IEEE Trans. on Computers, Vol. C-33, No. 10, 927–931, Oct. (1984)
C.C. Guest, and T.K. Gaylord: Truth-Table Look-Up Optical Processing Utilizing Binary and Residue Arithmetic. Applied Optics, Vol. 19, No. 7, 1201–1207, Apr. (1980)
John P. Hayes: Computer Architecture and Organization. McGraw-Hill, (1978)
Leonard S. Haynes, Richard L. Lau, Daniel P. Siewiorek, and David W. Mizell: A Survey of Highly Parallel Computing. Computer, Vol. 15, No. 1, 9–24, Jan. (1982)
C.H. Huang: A Fully Parallel Mixed-Radix Conversion Algorithm for Residue Number Applications. IEEE Trans. on Computers, Vol. C-32, No. 4, 398–402, April (1983)
Kai Hwang, and Faye A. Briggs: Computer Architecture and Parallel Processing. McGraw-Hill, (1984)
W. Kenneth Jenkins, and Benjamin J. Leon: The Use of Residue Number Systems in The Design of Finite Impulse Response Digital Filters. IEEE Trans. on Circuits and Systems, Vol. CAS-24, No. 4, 191–201, April (1977)
G.A. Jullien: Residue Number Scaling and Other Operations Using ROM Arrays. IEEE Trans. on Computers, Vol. C-27, No. 4, 325–336, April (1978)
Donald E. Knuth: The Art of Computer Programming — Seminumerical Algorithms. Addison-Wesley, Vol. 2, 268–276, (1981)
T. Kohonen: Content — Addressable Memories. Springer-Verlag, (1980)
H.T. Kung: Why Systolic Architectures?. Computer, Vol. 15, No. 1, 37–46, Jan. (1982)
H.T.Kung, L,M,Ruane, and D.W.L.Yen: ”A Two-Level Pipelined Systolic Array for Convolutions” in VLSI Systems and Computations. H.T.Kung, R.F.Sproull, and G.L.Steele(eds.): Carnegie-Mellon Univ., Computer Science Press, 255–264, Oct, (1981)
H.T.Kung and C.E.Leiseron: ”Algorithms for VLSI processor arrays”, Chapter 8 in Introduction to VLSI Systems. C.Mead and L.Conway: McGraw-Hill, (1980)
Carver Mead, and Lynn Conway: Introduction to VLSI Systems. Addison-Wesley, (1980)
Roy D. Merrill, Jr: Improving Digital Computer Performance Using Residue Number Theory. IEEE Trans. on Electronic Computers, Vol. EC-13, 93–101, Apr. (1964)
C.A.Papachristou: Table Lookup Processing for Multi-Operand Residue Arithmetic. Journal of The Association for Computing Machinery, Vol. 34, No. 2, April (1987)
C.A. Papachristou: Direct Implementation of Discrete and Residue-Based Functions via Optimal Encoding: A Programmable Array Logic Approach. IEEE Trans. on Computers, Vol. C-32, 961–968, Oct. (1983)
RCA, Aerospace Systems Division: Modular Arithmetic Computer Research. AL TDR 64–86, Burlington, Mass., April (1964)
Nicholas S. Szabo, and Richard I. Tanaka: Residue Arithmetic and Its Applications to Computer Technology. McGraw-Hill, (1967)
Fred J. Taylor: A VLSI Residue Arithmetic Multiplier. IEEE Trans. on Computers, Vol. C-31, No. 6, 540–546, June (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Papachristou, C.A., Hwang, S. (1988). A systolic array structure for matrix multiplication in the residue number system. In: Houstis, E.N., Papatheodorou, T.S., Polychronopoulos, C.D. (eds) Supercomputing. ICS 1987. Lecture Notes in Computer Science, vol 297. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18991-2_40
Download citation
DOI: https://doi.org/10.1007/3-540-18991-2_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18991-6
Online ISBN: 978-3-540-38888-3
eBook Packages: Springer Book Archive