電気系レイアウトDAに於ける概略配線問題を対象とした 超大規模整数計画問題について

• Item type: SIG Technical Reports(1)
• 公開日: 1995-07-19
• タイトル: 電気系レイアウトDAに於ける概略配線問題を対象とした 超大規模整数計画問題について
• タイトル / 言語: en
• タイトル: On the Very Large Integer Linear Programming Problem generated from a Global Routing Problem in an Electronic Design Automation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者名: 平澤, 知久; 白石, 洋一
• 著者名(英): Tomohisa, Hirasawa; Yoichi, Shiraishi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 電気系レイアウトDA (esign Automatio)の種々の問題は組合せ最適化問題として定式化できる。本稿では、特に概略配線問題を平面多種フロー問題として定式する際の超大規模整数計画問題について論じる。レイアウトDA問題は部品を配置する配置問題と部品間を配線する配線問題とからなる。配線問題は概略配線と詳細配線問題の各々からなる。概略配線問題は、配線領域を分割した小領域単位に各配線がどの領域を通過するかを決定する問題である。目的関数は、配線長合計最小化、混雑度平準化、特定の配線経路長の最小化、である。この問題を解くために本稿では問題を平面多種フロー問題として定式化するが、それは制約式の数は数万程度の超大規模整数計画問題となり、処理時間は百数十時間を要すると推定される。従来は処理時間を実用レベルに抑えるために問題の規模を削減する手法を組み込んでいたが、本稿では、階層化並列処理を目的として、改めて超大規模整数計画問題の処理時間と解の整数性を実験したので報告する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The problems encountered in the Electronic Design Automation are formulated as the combinatorial optimization problems. The very large integer linear programming problem, that is, the multicommodity network flow problem, is formulated from a global routing problem and it is discussed in this report. The problems in the layout design automation consists of the placement and the routing problems. Moreover, the routing problem is divided into the global and the detailed routing problems. The global routing problem is regarded as the problem to find a sequence of channels obtained by dividing the entire routing region. Here, the objective function is the combination of the total wire length minimization, the minimization of the deviation of wire-congestions and the wire-length minimization of the specified wire. The multicommodity network flow problem formulated from the actual global routing problem has more than several tens of thousands of constraint expressions and therefore, the processing time to solve this problem would be more than a hundred of hours. Though conventionally, some approximation techniques are devised to reduce the processing time to the practical range, the processing time and the integer solution without any approximation are reevaluated and discussed in order to parallelize the global routing process.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 1995, 号 66(1995-MPS-002), p. 33-38, 発行日 1995-07-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会