A new feed-through assignment algorithm based on a flow model

Presents a novel feed-through assignment algorithm based on minimum-cost multi-commodity flow formulation. After finding single-commodity flow with flow conflicts on the formulation, the algorithm eliminates all the conflicts to obtain a feasible solution. Since all nets and cell rows are considered simultaneously, our algorithm globally minimizes the number of tracks, the wire length, and the number of vias. Experimental results on benchmarks show that our algorithm substantially reduces these numbers compared with conventional algorithms.