Andrew Stone

DG2VHDL: Methods and Tools for the Synthesis of Scalable Parallel VLSI Architectures from Abstract Algorithmic Descriptions

Date: May 16, 2001

ABSTRACT

The problem of creating quality parallel processing VLSI array architectures from an abstract algorithmic description has been the research focus of the VLSI Signal Processing (VLSI-SP) research community. A vast number of signal processing (and other useful) algorithms have been analyzed using Dependence Graphs (DGs). Additionally, the mapping of DGs to Signal Flow Graph (SFG) distributed memory and control architectures has created a library of high performance parallel processing arrays for virtually every algorithm of interest. However, historically there has been lacking a convenient path to the silicon implementations for these architectures. At the same time, over the last ten years High Level Synthesis (HLS) research has led to the introduction of powerful industrial strength synthesis tools that allow the user to target a wide variety of ASIC and FPGA devices for rapid design prototyping. The required input to these tools, however, is carefully partitioned Hardware Description Language (HDL) code. Partitioning is necessary to deal with real-world, large size problems due to the high algorithmic complexity of the synthesis algorithms. The work presented in this PhD dissertation aims to utilize the strengths of both approaches while eliminating the weaknesses. We present a suite of algorithms which automatically use DG to SFG mappings as a pre-processing, partitioning step to HLS. After partitioning, optimal, synthesizable and scalable HDL models of the SFG processing arrays are automatically produced. The scalability of the generated HDL models is such that the resulting silicon area typically scales sub-linearly for increasing problem size, and synthesis time and memory requirements remain almost constant. In addition, algorithms have been implemented which find optimal SFG parallel structures prior to HDL generation and others which automatically generate an HDL framework for array simulation and error analysis. All algorithms have been integrated into a suite of interactive tools we call DG2VHDL. The suite has been used to synthesize hardware for a variety of signal and image processing problems, such as the Discrete Wavelet Transform, Block Matching Motion Estimation etc.

PhD Committee: Dr. Fridman, Analog Devices Inc. Prof. Leeser Prof. Manolakos (advisor) Prof. Meleis