An efficient design space exploration for balance between computation and memory
Mary W. Hall, Byoungro So · 2003
This dissertation describes an automated system that maps an application written in a high level language to an FPGA. The current practice of FPGA mapping requires designers to manually and iteratively apply loop transformations to negotiate the inherent space-time trade-offs. This iterative process is called design space exploration. This manual approach is tedious, error-prone, and prohibitively expensive given the large search space and the current long synthesis times. The DEFACTO system automates design space exploration by combining hardware synthesis with parallelizing compiler technologies into a unified system. The compiler uses its high-level knowledge and several metrics to guide code transformations toward a good design. Further, to quantitatively evaluate alternate designs, we use synthesis estimation techniques that are much faster than fully synthesizing a design. Thus, this integration significantly raises larger than is feasible for human designers. The code transformations developed for design space exploration are motivated by the flexibility of FPGAs. We can devote on-chip resources for multiple functional units to exploit more parallelism, or for on-chip data storage to keep data and repeatedly reuse it. Further, the multiple memory banks offer opportunities for parallel memory accesses to/from FPGAs. Therefore, the compiler optimizes designs using the following transformations. Scalar replacement replaces repeated accesses to an array element with a scalar variable, so that the element is accessed from a register rather than memory. Our approach extends the previous work to eliminate both redundant read and write memory accesses across multiple loops in a nest. A novel transformation called custom data layout derives an application-specific data layout in multiple memories that facilitates parallel memory accesses. Unroll-and-jam replicates the loop body and jams the copies of the inner loop, and thus improves fine-grain parallelism. We have reduced design space exploration to a more tractable problem of optimal unroll factor selection. The DEFACTO system derives an implementation that closely matches the best performance among those considered, and selects the smallest design among implementations with comparable performance. We search on average only 0.3% of the entire design space over 5 multimedia kernels.