
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Lagrangian Relaxation Based InterLayer Signal Via Assignment for 3D ICs
Song CHEN Liangwei GE MeiFang CHIANG Takeshi YOSHIMURA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E92A
No.4
pp.10801087 Publication Date: 2009/04/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E92.A.1080 Print ISSN: 09168508 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, throughthesilicon via, via assignment,
Full Text: PDF>>
Summary:
Threedimensional integrated circuits (3D 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 throughthesilicon via, is a key technology for 3D ICs. In this paper, given 3D circuit placement or floorplan results with white space reserved between blocks for interlayer interconnections, we proposed methods for assigning interlayer signal via locations. Introducing a grid structure on the chip, the interlayer via assignment of twolayer chips can be optimally solved by a convexcost maxflow formulation with signal via congestion optimized. As for 3D ICs with three or more layers, the interlayer signal via assignment is modeled as an integral mincost multicommodity flow problem, which is solved by a heuristic method based on the lagrangian relaxation. Relaxing the capacity constraints in the grids, we transfer the mincost multicommodity flow problem to a sequence of lagrangian subproblems, which are solved by finding a sequence of shortest paths. The complexity of solving a lagrangian subproblem is O(n_{nt}n_{g}^{2}), where n_{nt} is the number of nets and n_{g} is the number of grids on one chip layer. The experimental results demonstrated the effectiveness of the method.

