Lagrangian relaxation based pin assignment and Through-Silicon Via planning for 3-D SoCs

As technology advances, 3-D stacking of silicon layers that promises a solution to significantly alleviate the interconnect problem faced by current System-on-Chips (SoCs). In 3-D SoCs, judicious assignment of the pin locations and related vertical Through-Silicon Vias (TSVs) can improve the routing area and interconnection delay by reducing wire length and wire congestion. In this paper, we propose a significant algorithm to locate pin and TSV positions simultaneously for the two-pin net list in 3-D SoCs. Given a floorplan result, we formulate the pin assignment and TSV planning problem as a min-cost multi-commodity flow model and solve it based on lagrangian relaxation. By relaxing the capacity constraints in pin and TSV locations, we transform the min-cost multi-commodity flow problem to several min-cost max-flow problems that can be solved independently. A heuristic algorithm is also proposed to improve the result of lagrangian relaxation to guarantee the feasible solution. Experimental results show the effectiveness of the proposed algorithm.