Algorithms for design space exploration and high-level synthesis for multi-FPGA reconfigurable computers

The Reconfigurable Computer (RC) consists of multiple Field Programmable Gate Array (FPGA) devices, memory banks and interconnection hardware between the FPGAs. The RC, offering a wide variety of hardware resources but limited in quantity, poses a challenge to design automation techniques. The state-of-the-art design automation for RCs direly requires efficient High-Level Synthesis (HLS) and behavioral partitioning techniques that can effectively utilize the rich set of resources. Thus, HLS plays a central role in the design automation of RCs.; HLS comprises of a collection of well-established sub-problems, each of which are known to be NP-complete. HLS techniques have gained popularity primarily due to their ability to quickly explore a wide variety of structural implementations, for a given behavioral specification of the design.; This thesis presents a high-level synthesis framework consisting of a variety of HLS techniques and models that collectively provide complete synthesis support for the design automation of RCs. Traditional interaction between HLS and spatial partitioning is primarily to obtain a quick estimate on a contemplated solution, using a naive exploration model. This kind of an interaction is inadequate because high-level exploration is performed without any knowledge about the partitioned configuration of the behavior. This thesis presents a novel exploration technique that incorporates a partitioning-based exploration model.; In order to provide close interaction between synthesis and partitioning, we provide an exploration framework that can be integrated with any partitioning algorithm. The exploration framework provides an collection of methods that a partitioner can use to control the trade-off between time spent in exploration and the amount of design space explored.; Traditional HLS developed for ASICs are not quite suitable for RCS that provide a limited set of resources. This thesis presents two new techniques that efficiently utilize the resources on the Re architecture. We have developed a application-specific macro-based synthesis process that dynamically generates macro components specific to an application and uses these during HLS.; This thesis presents a new time-constrained scheduling algorithm that has low-complexity, yet produces good quality schedules. This scheduling algorithm is an ideal candidate for high-level exploration with partitioning since millions of solutions will have to be evaluated.; The high-level synthesis system incorporates the widely used resource-constrained Force Directed List Scheduling (FDLS) Algorithm developed by Paulin and Knight. We have developed an improved FDLS technique that significantly reduces the computational intensity of the original FDLS algorithm without degrading the schedule quality. (Abstract shortened by UMI.)...