On the Three-Dimensional Channel Routing
Summary :
The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.10 pp.1813-1821
- Publication Date
- 2016/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.1813
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Satoshi TAYU
Tokyo Institute of Technology
Toshihiko TAKAHASHI
Niigata University
Eita KOBAYASHI
Tokyo Institute of Technology
Shuichi UENO
Tokyo Institute of Technology
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
Satoshi TAYU, Toshihiko TAKAHASHI, Eita KOBAYASHI, Shuichi UENO, "On the Three-Dimensional Channel Routing" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 10, pp. 1813-1821, October 2016, doi: 10.1587/transfun.E99.A.1813.
Abstract: The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1813/_p
Copy
@ARTICLE{e99-a_10_1813,
author={Satoshi TAYU, Toshihiko TAKAHASHI, Eita KOBAYASHI, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Three-Dimensional Channel Routing},
year={2016},
volume={E99-A},
number={10},
pages={1813-1821},
abstract={The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).},
keywords={},
doi={10.1587/transfun.E99.A.1813},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - On the Three-Dimensional Channel Routing
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1813
EP - 1821
AU - Satoshi TAYU
AU - Toshihiko TAKAHASHI
AU - Eita KOBAYASHI
AU - Shuichi UENO
PY - 2016
DO - 10.1587/transfun.E99.A.1813
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2016
AB - The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).
ER -
English
