| Item type |
SIG Technical Reports(1) |
| 公開日 |
2017-10-30 |
| タイトル |
|
|
タイトル |
集合対間配線における目標端子対選択法に関する一検討 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A Study on Target Pin-Pairs Selection for Set-Pair Routing |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
配置・配線手法 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
東京工業大学工学院情報通信系 |
| 著者所属 |
|
|
|
東京工業大学工学院情報通信系 |
| 著者所属 |
|
|
|
東京工業大学工学院情報通信系 |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Information and Communications Engineering, Tokyo Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Information and Communications Engineering, Tokyo Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Information and Communications Engineering, Tokyo Institute of Technology |
| 著者名 |
赤木, 佳乃
佐藤, 真平
高橋, 篤司
|
| 著者名(英) |
Kano, Akagi
Shimpei, Sato
Atsushi, Takahashi
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
集合対間配線問題に対し，配線長と配線長差の小さい配線パターンを効率よく生成することを目指し，（1） 目標端子対を設定し，（2） それら目標端子対をできる限り接続する配線パターンを初期解とし生成，修正する手法を検討している．本稿では，（1） において，離れた端子の対をできる限り含まない目標端子対の集合を選択する方法を提案する．目標端子対集合の選択を，二部グラフにおける辺重みの最大値が最小な完全マッチングを求める問題として定式化し，提案アルゴリズムは，辺重みの最大値が最小な完全マッチングを出力する．考察では提案するアルゴリズムの有効性を検討する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
In set-pair routing problem, in order to obtain a routing pattern that achieves length matching efficiently, we consider a design flow in which (1) target pin-pairs are selected, (2) an initial routing pattern that connects the target pin-pairs as much as possible is obtained, and is modified. In this paper, we propose a method that selects the target pin-pairs that consist of pin-pairs which can be connected by short connections. Target pin-pair selection problem is formulated as a minimization problem of maximum edge weight of perfect matching in a bipartite graph, and an algorithm that gets such a matching is proposed. Also, we discuss on an effectiveness of our proposed algorithm. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11451459 |
| 書誌情報 |
研究報告システムとLSIの設計技術（SLDM）
巻 2017-SLDM-181,
号 45,
p. 1-6,
発行日 2017-10-30
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8639 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-SLDM17181045.pdf (537.6 kB)
