A Fast Branch-and-Bound Approach to High-Level Synthesis of Asynchronous Systems

In this paper, we address the problem of scheduling and allocation for asynchronous systems, and present methods for performing both area-constrained and time-constrained design space exploration. Much of the recent work in this area has been adapted from synchronous approaches, and thereby suffers from the drawback of assuming discrete time (or a discrete approximation). Further, most existing approaches are based on ILP methods, which can suffer from long solution search times for even modest-sized examples.We present instead an approach that does not assume or approximate timing as discrete, and is therefore able to find more optimal solutions for asynchronous systems. The scheduling approach uses a branch-and-bound search strategy with simple, effective heuristics to safely prune the search space, while guaranteeing an optimal solution. In particular, a high-quality initial solution is obtained heuristically, allowing the search space and overall search time to be significantly reduced, particularly when compared to ILP approaches. A 1.9x-180x improvement in run-time is achieved for small examples, and an improvement of multiple orders of magnitude for larger examples (including an example containing over a thousand operations).