Lagrangian Relaxation Based Inter-Layer Signal Via Assignment for 3-D ICs

Song CHEN  Liangwei GE  Mei-Fang CHIANG  Takeshi YOSHIMURA 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E92-A  No.4  pp.1080-1087
Publication Date: 2009/04/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Advanced Technologies Emerging Mainly from the 21st Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
three dimensional integrated circuits,  through-the-silicon via,  via assignment, 

Full Text: PDF(255.2KB)

Summary: 
Three-dimensional integrated circuits (3-D ICs), i.e., stacked dies, can alleviate the interconnect problem coming with the decreasing feature size and increasing integration density, and promise a solution to heterogenous integration. The vertical connection, which is generally implemented by the through-the-silicon via, is a key technology for 3-D ICs. In this paper, given 3-D circuit placement or floorplan results with white space reserved between blocks for inter-layer interconnections, we proposed methods for assigning inter-layer signal via locations. Introducing a grid structure on the chip, the inter-layer via assignment of two-layer chips can be optimally solved by a convex-cost max-flow formulation with signal via congestion optimized. As for 3-D ICs with three or more layers, the inter-layer signal via assignment is modeled as an integral min-cost multi-commodity flow problem, which is solved by a heuristic method based on the lagrangian relaxation. Relaxing the capacity constraints in the grids, we transfer the min-cost multi-commodity flow problem to a sequence of lagrangian sub-problems, which are solved by finding a sequence of shortest paths. The complexity of solving a lagrangian sub-problem is O(nntng2), where nnt is the number of nets and ng is the number of grids on one chip layer. The experimental results demonstrated the effectiveness of the method.