On problem transformability in VLSI |
| |
Authors: | Scot Hornick and Majid Sarrafzadeh |
| |
Affiliation: | (1) Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois, 61801 Urbana, IL, USA;(2) Present address: Department of Electrical Engineering and Computer Science, The Technological Institute, Northwestern University, 60201 Evanston, IL, USA |
| |
Abstract: | The two basic performance parameters that capture the complexity of any VLSI chip are the area of the chip,A, and the computation time,T. A systematic approach for establishing lower bounds onA is presented. This approach relatesA to the bisection flow, . A theory of problem transformation based on , which captures bothAT2 andA complexity, is developed. A fundamental problem, namely, element uniqueness, is chosen as a computational prototype. It is shown under general input/output protocol assumptions that any chip that decides ifn elements (each with (1+)lognbits) are unique must have =(nlogn), and thus, AT2=(n2log2n), andA= (nlogn). A theory of VLSI transformability reveals the inherentAT2 andA complexity of a large class of related problems.This work was supported in part by the Semiconductor Research Corporation under contract RSCH 84-06-049-6. |
| |
Keywords: | VLSI model of computation Area-time tradeoff Lower bound Problem transformation Computational prototype |
本文献已被 SpringerLink 等数据库收录! |
|