Lagrangian relaxation based inter-layer signal via assignment for 3-D ICs

Song Chen*, Liangwei Ge, Mei Fang Chiang, Takeshi Yoshimura

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


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 twolayer 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 mincost 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(nntn2 g), 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.

Original languageEnglish
Pages (from-to)1080-1087
Number of pages8
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number4
Publication statusPublished - 2009


  • Three dimensional integrated circuits
  • Through-the-silicon via
  • Via assignment

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics
  • Signal Processing


Dive into the research topics of 'Lagrangian relaxation based inter-layer signal via assignment for 3-D ICs'. Together they form a unique fingerprint.

Cite this