Through-silicon via (TSV) with flip-chip packaging is a technology that enables vertical integration of silicon dies, forming a single 3-D IC stack. A practical model for preplaced TSV assignment of 3-D nets is proposed for this technology. We prove that the general preplaced 3-D IC TSV assignment problem with more than two dies is NP-complete. An integrated algorithm that combines shortest path search, bipartite matching, min-cost max-flow calculation, and postprocessing is developed. Experimental results using actual testing silicon data demonstrate that our flow achieves good results with reasonable runtime when compared to other existing works.

Through-Silicon Via (TSV) is a technology that enables vertical integration of silicon dies forming a single 3D-IC stack. In this paper, a practical model is proposed for the TSV assignment problem of the stacked-die 3D nets. We present the first work in the literature to prove that the general 3D-IC TSV assignment problem with more than two dies is NP-complete. An efficient heuristic algorithm that combines Shortest Path, Bipartite Matching, Min-cost Max-flow and Integer Linear Programming is developed. Experimental results demonstrate that our flow achieves good quality of results (within 98% of the optimal solution) with reasonable run-time compared to related works.

This paper describes a solution for global routing and track assignment of flip-chip I/O nets. Voronoi Diagram (VD) is used to partition the open routing space and the geometrical properties of VD graph are exploited to create global routing channels with capacity and congestion considerations. A network flow algorithm is used to achieve optimal global routing. The regularity of the flip-chip bump placement is observed and allows us to reduce the size of global routing channel graph by over 50% to speed up computation. A track assignment algorithm avoids crossing wires before completing the final route with a detailed router. Experiment results using actual silicon chip data demonstrate that our solution achieves good quality of results compared to an implementation used in a commercial tool.