Isomorphic Subgraph-based Problem Reduction for Resource Minimal Modulo Scheduling

摘要

Modulo scheduling is a powerful method to increase throughput in high-level synthesis for digital hardware design. When facing large designs, optimal approaches are likely to time out and heuristics fail to provide satisfying throughput and latency. We propose an isomorphic subgraph-based reduction of the input data-flow graph (DFG) that is applied before scheduling, in order to solve the modulo scheduling problem faster without changing the optimal initiation interval (II) and allocated hardware. Our results show a solving time speedup of 5× on average and up to 102× for large designs. Using the proposed pre-processing step, the II achieved could be reduced by 33% on average for SDC-based modulo schedulers. And in ILP-based scheduling, we could classify 15% more solutions as optimal within the same time compared to solutions provided without applying our transformation.