IEICE TRANSACTIONS on Fundamentals
An Efficient Multi-Level Algorithm for 3D-IC TSV Assignment
Summary :
Through-silicon via (TSV) assignment problem is one of the key design challenges of 3-D IC which is crucial to the wire length and signal delay. In this work we formulate the 3-D IC TSV assignment as an Integer Minimum Cost Multi Commodity (IMCMC) problem on a IMCMC network, and propose a multi-level algorithm. It coarsens the IMCMC network level by level, applies a rough flow assignment on each level of coarsened graph, and generates only promising edges to reduce the IMCMC network size. Benefiting from the multi-level structure, we propose a mixed single and multi commodity flow method improve the TSV assignment solution quality. Moreover, given a TSV assignment, we propose an extended layer by layer algorithm to further optimize the TSV assignment. The experimental results demonstrate that our multi-level with mixed single and multi commodity flow algorithm achieves not only smaller wire length but also shorter runtime compared to other existing works.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.3 pp.776-784
- Publication Date
- 2017/03/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.776
- Type of Manuscript
- PAPER
- Category
- VLSI Design Technology and CAD
Authors
Cong HAO
Waseda University
Takeshi YOSHIMURA
Waseda University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Cong HAO, Takeshi YOSHIMURA, "An Efficient Multi-Level Algorithm for 3D-IC TSV Assignment" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 3, pp. 776-784, March 2017, doi: 10.1587/transfun.E100.A.776.
Abstract: Through-silicon via (TSV) assignment problem is one of the key design challenges of 3-D IC which is crucial to the wire length and signal delay. In this work we formulate the 3-D IC TSV assignment as an Integer Minimum Cost Multi Commodity (IMCMC) problem on a IMCMC network, and propose a multi-level algorithm. It coarsens the IMCMC network level by level, applies a rough flow assignment on each level of coarsened graph, and generates only promising edges to reduce the IMCMC network size. Benefiting from the multi-level structure, we propose a mixed single and multi commodity flow method improve the TSV assignment solution quality. Moreover, given a TSV assignment, we propose an extended layer by layer algorithm to further optimize the TSV assignment. The experimental results demonstrate that our multi-level with mixed single and multi commodity flow algorithm achieves not only smaller wire length but also shorter runtime compared to other existing works.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.776/_p
Copy
@ARTICLE{e100-a_3_776,
author={Cong HAO, Takeshi YOSHIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Multi-Level Algorithm for 3D-IC TSV Assignment},
year={2017},
volume={E100-A},
number={3},
pages={776-784},
abstract={Through-silicon via (TSV) assignment problem is one of the key design challenges of 3-D IC which is crucial to the wire length and signal delay. In this work we formulate the 3-D IC TSV assignment as an Integer Minimum Cost Multi Commodity (IMCMC) problem on a IMCMC network, and propose a multi-level algorithm. It coarsens the IMCMC network level by level, applies a rough flow assignment on each level of coarsened graph, and generates only promising edges to reduce the IMCMC network size. Benefiting from the multi-level structure, we propose a mixed single and multi commodity flow method improve the TSV assignment solution quality. Moreover, given a TSV assignment, we propose an extended layer by layer algorithm to further optimize the TSV assignment. The experimental results demonstrate that our multi-level with mixed single and multi commodity flow algorithm achieves not only smaller wire length but also shorter runtime compared to other existing works.},
keywords={},
doi={10.1587/transfun.E100.A.776},
ISSN={1745-1337},
month={March},}
Copy
TY - JOUR
TI - An Efficient Multi-Level Algorithm for 3D-IC TSV Assignment
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 776
EP - 784
AU - Cong HAO
AU - Takeshi YOSHIMURA
PY - 2017
DO - 10.1587/transfun.E100.A.776
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2017
AB - Through-silicon via (TSV) assignment problem is one of the key design challenges of 3-D IC which is crucial to the wire length and signal delay. In this work we formulate the 3-D IC TSV assignment as an Integer Minimum Cost Multi Commodity (IMCMC) problem on a IMCMC network, and propose a multi-level algorithm. It coarsens the IMCMC network level by level, applies a rough flow assignment on each level of coarsened graph, and generates only promising edges to reduce the IMCMC network size. Benefiting from the multi-level structure, we propose a mixed single and multi commodity flow method improve the TSV assignment solution quality. Moreover, given a TSV assignment, we propose an extended layer by layer algorithm to further optimize the TSV assignment. The experimental results demonstrate that our multi-level with mixed single and multi commodity flow algorithm achieves not only smaller wire length but also shorter runtime compared to other existing works.
ER -
English
