Late Breaking Results: Novel Discrete Dynamic Filled Function Algorithm for Acyclic Graph Partitioning

A parallel simulation that partitions a large circuit into sub-circuits is widely used to reduce simulation runtime. To achieve higher simulation throughput, we shall consider signal directions, and thus the final partitioning solution must be acyclic. In this paper, we model a circuit as a directed graph and consider acyclic graph partitioning to minimize edge cuts. This problem differs from the traditional partitioning problem because of the additional acyclicity constraint. Unlike traditional heuristics that tend to be trapped in local minima, especially for large graphs, we present a novel discrete dynamic filled function algorithm for the acyclic graph partitioning problem. Our algorithm can guarantee convergence and effectively move from one discrete local minimizer to another better one. Experimental results show that our algorithm achieves 8% average cutsize reduction over the state-of-the-art works in a comparable runtime.