A hierarchical framework to enhance scalability and performance of scheduling and mapping algorithms

Crucial to design productivity, architecture level synthesis algorithms trade off between design quality and algorithm complexity. The well-known list scheduling algorithm has a O(N) complexity but has well known deficiencies. Ant Colony, FDLS and Simulated Annealing have at least O(N³) time complexity. These considerations force a limitation on the scale of design instances that can be synthesized. A hierarchical analysis framework is proposed that improves both the run-time and ultimate performance of classical scheduling and mapping algorithms. Since the design hierarchy is not imposed, classical induced constraint issues from hierarchy are avoided. Compared to state-of-the-art heuristics, the framework runs an order of magnitude faster while achieving 12% performance improvement. The framework is able to efficiently address designs with more than 10⁴ operations which is beyond the capability of any high quality flat heuristics.