ABSTRACT
In this paper we will explore the limitations imposed by entropic constraints, both in generality and for specific problems. We list below the main questions that we will address.
(1) In the binary number system, addition is easy while multiplication is hard for VLSI. Is there an “ideal” number representation, in which all arithmetic operations have efficient VLSI implementations?
(2) Can one build multipliers for binary numbers, which achieve both small area and fast average computation time?
(3) Thompson's technique applies only to multiple output functions. How can one prove area-time bounds for single output functions?
(4) What other ways are there for deriving entropic constraints from consideration of data movement?
Answers to these questions will be discussed in the ensuing sections.
- 1.H. Abelson and P. Andreae, "Information transfer and area-time tradeoffs for VLSI multiplications," Comm. ACM 23 (1980), 20-23. Google ScholarDigital Library
- 2.R. P. Brent and L. M. Goldschlager, "Some area-time tradeoffs for VLSI," August 1980, draft.Google Scholar
- 3.R. P. Brent and H. T. Kung, "The chip complexity of binary arithmetics," Proc. 12-th Ann. ACM Symp. on Theory of Computing, April 1980, Los Angeles, California, 190-200. Google ScholarDigital Library
- 4.R. P. Brent and H. T. Kung, "On the area of binary tree layouts," Information Processing Letters 11 (1980), 46-48.Google ScholarCross Ref
- 5.L.J. Guibas, H. T. Kung, and C. D. Thompson, "Direct VLSI implementation of combinatorial algorithms," Proc. Conf. on VLSI Architecture Design and Fabrication, 1979, CALTECH.Google Scholar
- 6.J. E. Hopcroft and R. M. Karp, "An n5/2 algorithm for maximum matchings in bipartite graphs," SIAM J. on Computing 2(1973), 225-231.Google ScholarDigital Library
- 7.H. T. Kung and C. E. Leiserson, "Systolic arrays for VLSI," in the book by Mead and Conway (reference {8}), Section 8.3.Google Scholar
- 8.R. J. Lipton, S. C. Eisenstat, and R. A. DeMillo, "Space and time hierarchies for classes of control structure and data structures," Journal ACM 23(1976), 720-732. Google ScholarDigital Library
- 9.C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980. Google ScholarDigital Library
- 10.A. L. Rosenberg, private communication, March 1980.Google Scholar
- 11.J. E. Savage, "Area-time tradeoffs for matrix multiplication and related problems in VLSI models," Proc. 17-th Ann. Allerton Conf. on Comm., Control and Computing, October 1979, Allerton, Illinois.Google Scholar
- 12.C. D. Thompson, "Area-time complexity for VLSI," Proc. 11-th Ann. ACM Symp. on Theory of Computing, April 1979, Atlanta, Gerogia, 81-88. Google ScholarDigital Library
- 13.C. D. Thompson, A Complexity Theory for VLSI, Ph.D. thesis, Carnegie-Mellon University, August 1980. Google ScholarDigital Library
- 14.J. Vuillemin, "A combinatorial limit to the computing power of VLSI circuits," Proc. 21-st Ann. IEEE Symp. on Foundations of Computer Science, October 1980, Syracuse, New York, 294-300.Google Scholar
- 15.S. Winograd, "On the time required to perform multiplication," Journal ACM 14(1967), 793-802. Google ScholarDigital Library
- 16.A. C. Yao, "Some complexity questions related to distributive computing," Proc. 11-th Ann. ACM Symp. on Theory of Computing, April 1979, Atlanta, Georgia, 209-213. Google ScholarDigital Library
Index Terms
The entropic limitations on VLSI computations(Extended Abstract)
Recommendations
A VLSI Modulo m Multiplier
A novel method to compute the exact digits of the modulo m product of integers is proposed, and a modulo m multiply structure is defined. Such a structure can be implemented by means of a few fast VLSI binary multipliers, and a response time of about ...
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 ...
Extended abstract: Unified digit-serial multiplier/inverter in finite field GF(2m)
HST '08: Proceedings of the 2008 IEEE International Workshop on Hardware-Oriented Security and TrustModular multiplication and inversion are the essential operations in both Elliptic Curve Cryptosystems (ECC) and HyperElliptic Curve Cryptosystems (HECC). In this paper, we describe a unified digit-serial multiplier/inverter in GF(2m). The inverter is ...
Comments