Fang, J.-W.J.-W.FangHsu, C.-H.C.-H.HsuYAO-WEN CHANG2018-09-102018-09-10200902780070http://www.scopus.com/inward/record.url?eid=2-s2.0-76349085643&partnerID=MN8TOARShttp://scholars.lib.ntu.edu.tw/handle/123456789/350368The flip-chip package provides a high chip-density solution to the demand for more input-output pads of very large scale integration designs. In this paper, we present the first routing algorithm in the literature for the preassignment flip-chip routing problem with a predefined netlist among pads and wire-width and signal-skew considerations. Our algorithm is based on integer linear programming (ILP) and guarantees to find an optimal solution for the addressed problem. It adopts a two-stage technique of global routing followed by detailed routing. In global routing, it first uses three reduction techniques to prune redundant solutions and create a global-routing path for each net. Without loss of the solution optimality, our reduction techniques can further prune the ILP variables (constraints) by 85.5% (98.0%) on average over a recent reduction technique. The detailed routing applies passingpoint assignment, net-ordering determination, and X-based gridless routing to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength, and satisfy all signal-skew constraints, under reasonable central-processing- unit times, whereas recent related work has resulted in much inferior solution quality. © 2009 IEEE.Detailed routing; Global routing; Layout; Physical design[SDGs]SDG9Detailed routing; Flip chip; Flip-chip packages; Global routing; Gridless; Input-output; Integer Linear Programming; Netlist; Optimal solutions; Optimality; Physical design; Reduction techniques; Routability; Routing path; Routing problems; Solution quality; Two stage; Very large scale integration designs; Wire length; Flip chip devices; Integer programming; Linearization; Optimization; Routing algorithms; Routing protocols; Designjournal article10.1109/TCAD.2008.20091512-s2.0-76349085643WOS:000262164100009