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. The spatial and temporal (behavioral) partitioning techniques for RCs rely heavily on HLS to provide high-level estimates and a sound back-end support for synthesizing the partitioned designs. 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. However, there is an ever increasing need for HLS techniques that satisfy application specific requirements and utilize target-architecture-specific features to perform efficient high-level exploration and synthesis.
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. The exploration model, unlike traditional HLS exploration model, views a four-dimensional design space consisting of multiple spatially partitioned segments of the behavior. The exploration technique has the ability to simultaneously explore the design space of all partitioned behavior segments and generate multiple structural implementations, one for each FPGA device on the RC.
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. The framework can be used by a partitioner to either dynamically perform exploration or statically generate design points prior to partitioning. In addition, the framework incorporates behavioral exploration at two levels of abstraction: the block-level BBIF specification that represents a single thread of control, and the task-level USM specification that represents multiple threads of control.
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 RC 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 technique results in considerable improvement in the design performance for RCs. We also developed an improved register optimization and binding technique that results in considerable reduction in the design area on the RC.
The scheduling phase of HLS forms an integral part of the exploration and synthesis process since it directly impacts the area-speed tradeoffs of the design. This thesis presents three scheduling techniques that are used during high-level synthesis and exploration.
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. Moreover, since the algorithm is time-constrained, it enables the exploration framework to handle a latency constraint on the given behavior. The scheduling algorithm and a collection of HLS estimation algorithms have been integrated with exploration framework.
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. Even a small improvement in the schedule quality translates to a significant increase the design throughput. Finally, this thesis presents another resource-constrained cone-based list scheduling algorithm which generates better quality schedules than FDLS at the expense of little computational overhead, for a class of DSP applications.