Late Breaking Results: Novel Discrete Dynamic Filled Function Algorithm for Acyclic Graph Partitioning
TimeWednesday, December 8th6:00pm - 7:00pm PST
LocationLevel 2 - Lobby
Event Type
Late Breaking Results Poster
Networking Reception
Virtual Programs
Presented In-Person
In-Person Presenter
DescriptionThese paper models a circuit as a directed graph and considers acyclic graph partitioning to minimize edge cuts. This problem differs from the traditional problem because of the acyclicity constraint. Unlike traditional heuristics that tend to be trapped in local minima, we present a novel discrete dynamic filled function algorithm for the acyclic graph problem. Our algorithm guarantees convergence and effectively moves from one local minimizer to another better one. Based on the multi-level framework, we further extend our algorithm to partition large-scale acyclic graphs efficiently. Experimental results show that our algorithm achieves 8% cutsize reduction over the state-of-the-art work.