| Algorithm-architecture co-exploration is a new design paradigm for digital signal processing (DSP) applications, that can have a dramatic impact on area, power and speed of the resulting implementation. This thesis describes efficient design methodology and tools to support such a design paradigm.;To facilitate efficient design space exploration in FANTOM, accurate area, time and power estimation models have been developed for Virtex-II based FPGA implementations. Detailed area models for the number of slices, block RAMs and 18x18-bit multipliers have been developed, and these models have been utilized to develop accurate power models of logic power, signal power, clock power and I/O power. Timing models have been developed to predict the latency of designs. In all cases, the model coefficients have been derived by using curve fitting or regression analysis.;Next a systematic approach for evaluation of simple and composite functions on FP-GAs is described. It is based on LUT and considers user-specified accuracy, area and on-chip memory constraints. The optimization procedure searches through a three-dimensional design space spanning sampling density, degree of Taylor polynomial approximation and data precision. It utilizes both model-based estimates and gradient-based information gathered during the search.;Finally, an example of algorithm-architecture co-exploration in the context of inverse Discrete Fourier Transform (DFT) computation in image reconstruction is presented. A two-dimensional decomposition algorithm that enables partial DFT computation is proposed. The corresponding FPGA architecture has significantly lower number of computations and fewer memory accesses compared to the conventional row-column decomposition based implementation.;First, an automation tool called FANTOM (Framework for Automated Numerical Transforms on Microchips) is introduced. It transforms DSP algorithms into fixed point format and implements the computationally intensive parts on an Field Programmable Gate Array (FPGA) platform. Three major components are presented: the floating-to-fixed point conversion (FFC) unit which is based on a combination of interval arithmetic and affine arithmetic, the efficient implementation of DSP functions which uses a combination of lookup tables (LUT) and interpolation schemes, and geometric tiling which groups data with comparable numerical range and allows better control of accuracy as well as resource requirements. The capabilities of this tool have been successfully demonstrated for multi-body interaction problems. |
