電子系DAに於いて部品配置を同時に行う概略配線問題の定式化について

• Item type: SIG Technical Reports(1)
• 公開日: 1996-01-22
• タイトル: 電子系DAに於いて部品配置を同時に行う概略配線問題の定式化について
• タイトル / 言語: en
• タイトル: A Mathematical Formulation of a Global Routing Problem Concurrently Placing Components 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
• 著者名: 白石, 洋一; 平澤, 知久
• 著者名(英): Yoichi, Shiraishi; Tomohisa, Hirasawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 電子系レイアウトDA (esign Automatio)の1処理であるフロアプラン問題を対象とした超大規模組合せ最適化問題を取り扱う。フロアプラン処理では部品間の概略配線径路と部品の配置を同時に決定する必要がある。ここで概略配線径路とは、レイアウト領域全体を小領域に分割し、部品の端子間を結合する配線径路を概略径路、即ち小領域の系列、として求める問題である。目的関数は、配線径路長の合計最小化、レイアウ卜領域面積最小化、電気的特性最適化、等である。本稿では特に部品の相対配置を入力として、それをもとに概略配線径路を決定し、同時に部品の絶対配置をも決定する問題を目標計画問題として定式化する。目的関数は配線径路長の合計最小化、レイアウ卜領域面積最小化、とした。まず概略配線問題を平面多種フロー問題として定式化する。次にレイアウト領域サイズの推定式を求め、それらを平面多種フロー問題に追加して目標計画問題とする。実際のフロアプラン問題を対象としてこの目標計画問題の規模のオーダを推定した。その結果、変数の個数10^6個、制約行列サイズ(0^5、10^)であった。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This report deals with the very large combinatorial optimization problem formulated from a "floor planning" problem encountered in the Electronic Design Automation. In the floor planning design, the locations of components and the global routes of wires must be determined simultaneously. Here, a global route connecting the source and sink pair is defined as a sequence of channels, the fragments obtained by dividing the whole layout area. The objective functions are the minimization of the total wire length, the minimization of the layout area or the optimization of the electric performances. In this report, the mathematical formulation of floor planning problem with the input of relative placement of components is discussed. Objective functions are temporarily restricted to the minimization of the total wire length and the minimization of the layout area. A global routing problem is first formulated as a multi-commodity network flow problem. Then, the linear expressions estimating the layout area are added to this problem and finally, a goal programming problem is obtained. The orders of the size of this goal programming problem are estimated against comparatively large actual floor planning problems. Then, the order of the number of variables is 10^6 and that of the size of constraint matrix is (10^5, 10^6).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 1996, 号 10(1995-MPS-005), p. 19-24, 発行日 1996-01-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会