| Configurable computing devices, such as field programmable gate arrays (FPGA), provide the opportunity to tailor computing and storage resources to the specific needs of an application. FPGAs have parallel compute fabric, interconnect and memory subsystems allowing for concurrent execution that translates into improved program performance. Mapping a program onto an FPGA is a difficult problem. The designer must manage the data movement among program and system components, and partition system resources among program components to maximize performance. The current approach requires that a designer perform a time-consuming translation into a low-level, hardware-oriented specification, searching many alternative solutions by hand. The designer needs assistance from automated design tools to navigate the design space efficiently, a process we call design space exploration.; This dissertation describes a system-level compiler that combines parallelizing compiler analyses with behavioral hardware synthesis estimates to automatically map five unannotated multiple loop nest sequential signal and image processing kernels onto an FPGA with multiple off-chip memories. We represent the program in a pipelined execution model; by detecting intermediate variables and assigning them to on-chip storage, our analysis reduces the number of off-chip memory accesses from 3 to 71 percent compared to the original code. We incorporate knowledge about the properties of our design space into our exploration algorithms and are able to prune 16 to 25 percent of the original size. We develop metrics, beyond the traditional area and performance measures, that are used to evaluate a design's performance against other designs. We select from a set of heuristics, based on a combination of compiler and synthesis knowledge, to guide our DSE. We find that a heuristic based on design quality identifies better candidates, in some cases 100 percent of the time, as opposed to heuristics based on area or performance alone.; As configurable devices continue to grow in capacity, the number of design choices will increase tremendously. Without tools, programmers will be unable to tap into the potential of these devices. The techniques in this dissertation aid in achieving this goal. |
