Timing issues in high-level synthesis

High-level synthesis transforms a behavioral specification into a register-transfer level implementation of a digital system. Much research has been put into auto- mating this demanding and error-prone task. Much of the effort has been directed towards finding techniques which minimize the length of the operation schedule and/or the implementation cost. As the techniques have matured and found their way into commercial applications, new problems have emerged such as the need to be able to specify not only the functional but also the timing behavior, and the difficulty to generate implementations with this timing behavior.This thesis addresses the timing-related problems in high-level synthesis by modeling the timing of a design at three different levels. In the high-level model, timing is expressed by constraints on the execution time of sequences of operations. At the middle level the timing is given by the selected clock period and the operation schedule. Finally, the low-level model is used to estimate the delay of each individual operation, taking into account the effects given by functional and storage units, multiplexors, interconnections, and the controller. This elaborated low-level timing model provides the basis for deciding the middle-level timing in such a way that the possibility of reaching a final implementation with this timing behavior is maximized. The middle level timing, in turn, is used to verify the timing constraints given by the high-level model.A set of design transformations has been developed to enable an integrated high-level synthesis algorithm performing automatic clock period selection, multicycle scheduling, resource allocation, and resource binding. The task of finding a sequence of transformations which leads to a (near) optimal solution yields a combinatorial optimization problem. To solve this problem an optimization algorithm based on the tabu search heuristic is proposed.The resulting high-level synthesis system has been applied to standard bench- marks and an example from the operation and maintenance (OAM) functionality of an asynchronous transfer mode (ATM) switch. The results motivate the usage of the proposed low-level and high-level timing models and demonstrate the efficiency of the implemented high-level synthesis system.