The Area-Time Complexity of Binary Multiplication

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Area-Time Complexity of Binary Multiplication

Full text

Pdf (710 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 3 (July 1981) table of contents

Pages: 521 - 534

Year of Publication: 1981

ISSN:0004-5411

Authors

R. P. Brent	The Australian National University, Canberra, ACT 2600, Australia
H. T. Kung	Department of Computer Science, Schenley Park, Carnegie-Mellon University, Pittsburgh, Pennsylvania, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 44, Citation Count: 24

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322261.322269 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Harold Abelson , Peter Andreae, Information transfer and area-time tradeoffs for VLSI multiplication, Communications of the ACM, v.23 n.1, p.20-23, Jan. 1980 [doi>10.1145/358808.358814]
	2	R. J. Bonneau, A CLASS OF FINITE COMPUTATION STRUCTURES SUPPORTING THE FAST FOURIER TRANSFORM, Massachusetts Institute of Technology, Cambridge, MA, 1973
	3	BRENT, R P, AND KUNG, H T A regular layout for parallel adders. Tech. Rep CMU-CS-79-131, Dep of Computer Science, Carnegie-Mellon Umv, Pittsburgh, Pa, June, 1979 (to appear in IEEE Trans. Comput.).
	4	BRENT, R P On the addition of binary numbers IEEE Trans. Comput (7-19 (1970), 758-759.
	5	BRENT, R P The complexity of multlple-preosion anthmeuc In The Complexity of Computatwnal Problem Solving, R.S Anderssen and R P Brent, Eds, University of Queensland Press, Brisbane, Australia, 1976, pp. 126-165.
	6	BRENT, R.P., AND KUNG, H T On the area of binary tree layouts. Inf Proc Letters 11, (1980), 46- 48
	7	R. P. Brent , H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.190-200, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804666]
	8	GARNER, H.L A survey of some recent contnbutions to computer anthmeUc IEEE Trans Comput. C-25 (1976), 1277-1282.
	9	JACKSON, L.B., KAISER, S F, AND MCDONALD, H S An approach to the implementation of digital filters. IEEE Trans Audw Electroacoust. A U-16 (Sept 1968), 413-421.
	10	David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
	11	KUNG, H.T., AND LEISERSON, C E Systolic arrays (for VLSI). Sparse Matrix Proceedings 1978, Knoxwlle, Tenn., Society for Industrial and Apphed Mathematics, 1979, pp 256-282 (a slightly DIfferent version appears m {15, Sec 8 3})
	12	LEISERSON, C E. Area-effioent graph layouts (for VLSI) Carnegie-Mellon Univ., Pittsburgh, Pa., Feb. 1980
	13	LINNIK, UV On the least prime m an arithmetic progression. I The basic theorem. Rec. Math 15 (1944), 139-178
	14	LYON, R.F Two's complement ptpehne multiphers" IEEE Trans Commun. COM-24, 4 (April 1976), 418-425.
	15	Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
	16	MEAD, CA, AND REM, M. Cost and performance of VLSI computing structures IEEE J Sohd State Circuits SC-14, 2 (April 1979), 455-462.
	17	OFMAN, Y On the algorithm complexRy of &screte functions. Dokl. Akad. Nauk SSSR 145 (1962), 48-51 (m Russmn)
	18	ROSSER, J B, AND SCHOENFELD, L.Approximate formulas for some funcUons of prime numbers. ILLInois J Math. 6 (1962), 64--94
	19	John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
	20	SAVAGE, J E.Area-time tradeoffs for matrix mulUphcatmn and related problems in VLSI models Tech. Rep. CS-50, Brown Umv, Prowdence, R I, Aug 1979
	21	SAVAGE, J E, AND SWAMY, Space-time tradeoffs for obhvtous sorting and integer multiplication Tech Rep CS-37, Brown Umv, Prowdence, R I, 1978
	22	SCHONHAGE A., AND STRASSEN, V.Schnelle Multlphkatmn grosser Zahlen Comput. 7 (1971), 281- 292
	23	C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
	24	WAGSTAFF, S S. JR Greatest of the least primes m arithmetic progressions having a given modulus Math Comp. 33 (1979), 1073-1083.
	25	WALLACE, C,S.A suggestion for a fast multiplier. IEEE Trans. Elec. Comput. EC-13 (1964), 14-17.
	26	S. Winograd, On the Time Required to Perform Addition, Journal of the ACM (JACM), v.12 n.2, p.277-285, April 1965 [doi>10.1145/321264.321279]
	27	S. Winograd, On the Time Required to Perform Multiplication, Journal of the ACM (JACM), v.14 n.4, p.793-802, Oct. 1967 [doi>10.1145/321420.321438]
	28	YAOLOM, I.M., AND BOLTYANSKII, V.G.Convex Figures. Holt, Rinehart and Winston, New York, 1961 (translated by P.J, Kelly and L F Walton).

CITED BY 24

	Gloria Kissin, Upper and lower bounds on switching energy in VLSI, Journal of the ACM (JACM), v.38 n.1, p.222-254, Jan. 1991
	Peter R. Cappello , Kenneth Steiglitz, A VLSI layout for a pipelined Dadda multiplier, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.157-174, May 1983
	R. P. Brent , H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.190-200, April 28-30, 1980, Los Angeles, California, United States
	Helmut Alt, Comparing the combinational complexities of arithmetic functions, Journal of the ACM (JACM), v.35 n.2, p.447-460, April 1988
	Micah Adler , John Byers, AT2 bounds for a class of VLSI problems and string matching, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.140-146, June 27-29, 1994, Cape May, New Jersey, United States
	Gloria Kissin, Measuring energy consumption in VLSI circuits: A foundation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.99-104, May 05-07, 1982, San Francisco, California, United States
	C. Scheiman , P. Cappello, A Period-Processor-Time-Minimal Schedule for Cubical Mesh Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.274-280, March 1994
	Colin D. Walter, Space/Time Trade-Offs for Higher Radix Modular Multiplication Using Repeated Addition, IEEE Transactions on Computers, v.46 n.2, p.139-141, February 1997
	Randal E. Bryant, On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication, IEEE Transactions on Computers, v.40 n.2, p.205-213, February 1991
	Takafum Aoki , Naofumi Homma , Tatsuo Higuchi, Evolutionary Synthesis of Arithmetic Circuit Structures, Artificial Intelligence Review, v.20 n.3-4, p.199-232, December 2003
	Martin Fürber , Kurt Mehlhorn, AT/sup 2/-Optimal Galois Field Multiplier for VLSI, IEEE Transactions on Computers, v.38 n.9, p.1333-1336, September 1989
	Chang nian Zhang , David Y. Y. Yun, Multi-dimensional systolic networks, for discrete fourier transform, ACM SIGARCH Computer Architecture News, v.12 n.3, p.215-222, June 1984
	H. M. Alnuweiri, Optimal VLSI Networks for Multidimensional Transforms, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.763-769, July 1994
	Valentina Ciriani , Fabrizio Luccio , Linda Pagli, Synthesis of integer multipliers in sum of pseudoproducts form, Integration, the VLSI Journal, v.36 n.3, p.103-119, October 2003
	Ju-wook Jang , Heonchul Park , Viktor K. Prasanna, An Optimal Multiplication Algorithm on Reconfigurable Mesh, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.521-532, May 1997
	Giuseppe Alia , Enrico Martinelli, A VLSI Modulo m Multiplier, IEEE Transactions on Computers, v.40 n.7, p.873-878, July 1991
	P. Lee , Z. M. Kedem, Synthesizing Linear Array Algorithms from Nested FOR Loop Algorithms, IEEE Transactions on Computers, v.37 n.12, p.1578-1598, December 1988
	Takafumi Aoki , Naofumi Homma , Tatsuo Higuchi, Evolutionary synthesis of arithmetic circuit structures, Artificial intelligence in logic design, Kluwer Academic Publishers, Norwell, MA, 2004
	Peter R. Cappello , Willard L. Miranker, Systolic Super Summation, IEEE Transactions on Computers, v.37 n.6, p.657-677, June 1988
	Ginfranco Bilardi , Scot W. Hornick , Majid Sarrafzadeh, Optimal VLSI architectures for multidimensional DFT (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.45-52, March 1991
	S. C. Goldstein, The impact of the nanoscale on computing systems, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.655-661, November 06-10, 2005, San Jose, CA
	A. R. Hurson , B. Shirazi, A systolic multiplier unit and its VLSI design, ACM SIGARCH Computer Architecture News, v.13 n.3, p.302-309, June 1985
	J. Chu , G. Schnitger, The communication complexity of several problems in matrix computation, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.22-31, June 18-21, 1989, Santa Fe, New Mexico, United States
	G. Bilardi , S. W. Hornick , M. Sarrafzadeh, Optimal VLSI architectures for multidimensional DFT, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.265-272, June 18-21, 1989, Santa Fe, New Mexico, United States