集合対問配線問題のための配線の付け替えによる配線長差最小化手法

• Item type: SIG Technical Reports(1)
• 公開日: 2016-11-21
• タイトル: 集合対問配線問題のための配線の付け替えによる配線長差最小化手法
• タイトル / 言語: en
• タイトル: Length Difference Minimization with Exchanging Pin Pair for Set Pair Routing Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 配線・DFM
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京農工大学
• 著者所属: 東京農工大学
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者名: 原, 秀太郎; 藤吉, 邦洋
• 著者名(英): Shutaro, Hara; Kunihiro, Fujiyoshi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 集合対間配線問題はプリント基板の設計などで生じる配線問題で，最長の配線と最短の配線の長さの差 （配線長差） を最小化することを目標として，グリッドグラフ上に与えられる複数のソース端子とシンク端子を総配線長最短の点非共有のパスで 1 対 1 接続する問題である．この問題に対して，総配線長最短の解を初期解として，閉路に基づいて総配線長を変化させずに配線を付け替えていき，貧欲的に配線長差を削減していく手法が提案された．しかし，この手法は配線長差最小の解を求められない場合がある．本稿では，配線長差を最小にする配線の付け替えを単位閉路の集合にて求め，それを適用して配線長差を最小にする手法を提案する．これを整数線形計画問題の形で定式化し実験を行った結果，閉路を用いずに整数線形計画法を解くのと比べ，配線領域の面積に対するネット数が多いときに高速化された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Set pair routing is the problem to minimize the maximum difference of paths (length difference) that one to one connected with separated paths between several source terminals and sink terminals on a grid graph with shortest total wire length. For this problem, length difference reduction algorithm based on a cycle in greedy manner is proposed. In this paper, we propose a method for minimizing the length difference with changing the route of wires based on a set of unit cycles. We formulate this method into integer linear programming and perform computer experiment. As a result, our method is faster than the integer linear programming without using cycles when there is many nets in wiring area.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムとLSIの設計技術（SLDM）; 巻 2016-SLDM-177, 号 14, p. 1-6, 発行日 2016-11-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8639
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会