Information transfer and area-time tradeoffs for VLSI multiplication

ABSTRACT

The need to transfer information between processing elements can be a major factor in determining the performance of a VLSI circuit. We show that communication considerations alone dictate that any VLSI design for computing the 2n-bit product of two n-bit integers must satisfy the constraint AT2 ≥ n2/64 where A is the area of the chip and T is the time required to perform the computation. This same tradeoff applies to circuits which can shift n-bit words through n different positions.

REFERENCES

• 1: Abelson, H. Lower bounds on information transfer in distributed systems. Proc. 19th IEEE Seminar Foundations Comptr. Sci., Ann Arbor, Mich., 1978.
• 2: Brent, R.P., and Kung, H.T. The area-time complexity of binary multiplication. Tech. Rep., Dept. Comptr. Sci., Carnegie-Mellon U., Pittsburgh, Pa., July 1979.
• 3: Preparata, F.P., and Vuillemin, J. The cube-connected-cycles: A versatile network. Proc. 20th IEEE Seminar Foundations Comptr. Sci., 1979.
• 4: Savage, J.E., and Swamy, S. Space-time tradeoffs for oblivious sorting and integer multiplication. Tech. Rep. No. 37, Dept. of Comptr. Sci., Brown U., Providence, R.I., 1978.
• 5: 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]
• 6: VuiUemin, J.P. A note on the paper: Area-time complexity for VLSI. Institute pour Recherche d'Infomatique et d'Automatique, Rocqencourt, France, 1979 (unpublished note).
• 7: Wallace, C.S. A suggestion for a fast multiplier. IEEE Trans. Electronic Comptg. EC-13 (Feb. 1964), 14-17.

INDEX TERMS

Keywords:
analysis of algorithms, area-time tradeoffs, integer multiplication, very large-scale intergration (VLSI)