A Network-Flow-Based RDL Routing Algorithmz for Flip-Chip Design

The flip-chip package gives the highest chip density of any packaging method to support the pad-limited application-specific integrated circuit designs. In this paper, we propose the first router for the flip-chip package in the literature. The router can redistribute nets from wire-bonding pads to bump pads and then route each of them. The router adopts a two-stage technique of global routing followed by detailed routing. In global routing, we use the network flow algorithm to solve the assignment problem from the wire-bonding pads to the bump pads and then create the global path for each net. The detailed routing consists of three stages, namely: 1) cross-point assignment; 2) net ordering determination; and 3) track assignment, to complete the routing. Experimental results based on seven real designs from the industry demonstrate that the router can reduce the total wirelength by 10.2%, the critical wirelength by 13.4%, and the signal skews by 13.9%, as compared with a heuristic algorithm currently used in industry.