The systematic design of area efficient VLSI architectures /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1991.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Abstract: | A systematic technique for the mapping of algorithms to, and design of area-efficient, application-specific very large scale integration (VLSI) arrays is demonstrated. In this paper we use the Discrete Fourier Transform (DFT) as an example to illustrate this technique. Using linear projections and schedules of specific dependence graph (DG) algorithm representations, six architecture classes with asymptotically maximum throughput per unit area in a VLSI computing model are derived. These architectures use variants of two-stage (row-column) fast algorithms and can be applied to either prime factor maps of common factor maps (PFMs or CFMs). Both internal and edge I/O systolic rectangular mesh arrays are derived. Parallel multi-projections are used to generate efficient twin-PE versions of the meshes. Piecewise linear projections and schedules are used to generate flow-through arrays connected by pipelined square-root matrix transposers. When used with a square-root Fast Fourier Transform (FFT), asymptotic VLSI optimality is preserved while only Ar(1 + log2N ) multiplies per DFT are required. Results that are even better than the FFT are obtained when the Winograd Algorithm is used. The Winograd algorithm requires between two and three times the number of adders, but only one-half to one-third the number of multipliers as does the FFT. The savings in multipliers much more than compensates for the extra cost in adders. Expressions for 3- and 4-stage DFTs, and the associated PFMs and CFM s are derived. Investigations are made into the results of different projections and schedules for these structures using different DFT kernels. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Electrical Engineering." |
| Physical Description: | xiii, 141 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |