Obstacle-Avoiding Free-Assignment Routing for Flip-Chip Designs

The flip-chip packaging is introduced for modern IC designs with higher integration density and larger I/O counts. It is necessary to consider routing obstacles for modern flip-chip designs, where the obstacles could be regions blocked for signal integrity protection (especially for analog/mixed-signal modules), prerouted or power/ground nets, and even for through-silicon vias for 3-D IC designs. However, no existing published works consider obstacles. To remedy this insufficiency, this paper presents the first work to solve the free-assignment flip-chip routing problem considering obstacles. For the free-assignment routing problem, most existing works apply the network-flow formulation. Nevertheless, we observe that no existing network-flow model can exactly capture the routability of a local routing region (tile) in presence of obstacles. This paper presents the first work that can precisely model the routability of a tile, even with obstacles. Based on this new model, a two-stage approach of global routing followed by detailed routing is proposed. The global routing computes a routing topology by the minimum-cost maximum-flow algorithm, and the detailed routing determines the precise wire positions. Dynamic programming is applied to further merge tiles to reduce the problem size. Compared to a state-of-the-art flow model with obstacle handling extensions, experimental results show that our algorithm can achieve 100% routability for all circuits while the extensions of the previous work cannot complete routing for any benchmark circuit with obstacles.