Full Text Views
34
Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.
Shimpei SATO
Tokyo Institute of Technology
Kano AKAGI
Tokyo Institute of Technology
Atsushi TAKAHASHI
Tokyo Institute of Technology
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.
Copy
Shimpei SATO, Kano AKAGI, Atsushi TAKAHASHI, "A Fast Length Matching Routing Pattern Generation Method for Set-Pair Routing Problem Using Selective Pin-Pair Connections" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 9, pp. 1037-1044, September 2020, doi: 10.1587/transfun.2019KEP0015.
Abstract: Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019KEP0015/_p
Copy
@ARTICLE{e103-a_9_1037,
author={Shimpei SATO, Kano AKAGI, Atsushi TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast Length Matching Routing Pattern Generation Method for Set-Pair Routing Problem Using Selective Pin-Pair Connections},
year={2020},
volume={E103-A},
number={9},
pages={1037-1044},
abstract={Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.},
keywords={},
doi={10.1587/transfun.2019KEP0015},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - A Fast Length Matching Routing Pattern Generation Method for Set-Pair Routing Problem Using Selective Pin-Pair Connections
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1037
EP - 1044
AU - Shimpei SATO
AU - Kano AKAGI
AU - Atsushi TAKAHASHI
PY - 2020
DO - 10.1587/transfun.2019KEP0015
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2020
AB - Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.
ER -