Wire reconnections based on implication flow graph

Global Flow Optimization (GFO) can perform the fanout/fanin wire re-connections by modeling the problem of the wire reconnections by a flow graph and then solving the problem using the maxflow-mincut algorithm on the flow graph. However, the flow graph cannot fully characterize the wire re-connections which causes GFO to lose optimality on several obvious cases. In addition, we find that the fanin re-connection can have more optimization power than the fanout re-connection but requires more sophisticated modeling. In this paper we re-formulate the problem of the fanout/fanin re-connections by a new graph called the implication flow graph. We show that the problem of wire re-connections on the implication flow graph is NP complete and also propose an efficient heuristic on the new graph. Our experimental results are very exciting.