| 講演名 | 2004/6/11 木構造データを用いた直方体パッキング表現手法(信号処理,LSI,及び一般) 川井 英教, 藤吉 邦洋, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 複数の直方体を互いに重なり合うことなく最も体積の小さい直方体内に配置するという直方体パッキング問題は、3次元MCMや3次元VLSI設計、計算資源の動的再構成スケジューリング問題の基本であるために効率よく優れた解を得る手法が求められている。しかしこの問題はNP困難であり、良い近似解を求めるためにその表現方法が求められている。この要求に対し、2次元上での矩形パッキング表現方法を拡張した方法がいくつか提案されているが、表現できない解があったり、冗長な解を多く含んでいて探索効率が悪いなどの問題があった。そこで本稿は、左下詰めパッキングだけを順序付きの多分木によって効率よく表現する"O-Tree"の考え方を基にして、左下手前詰めの直方体パッキングを表現する方法を提案する。また、直方体数nに対し、既存手法ではO(n^2)時間を必要としたデコード手法を,計算幾何学の手法を用いてO(n log n+s)に改善する手法も提案する。但し、sはz方向で重なりのある直方体対の数である。そしてこれらの手法を計算機実装して既存方法と実験比較し、その有効性を確かめる。 |
| 抄録(英) | Three dimensional packing of rectangular boxes, which is to pack all the given rectangular boxes in the minimum bounding rectangular box without overlapping, is the fundamental problem of the design of 3D MCM and 3D VLSI, but it is NP-hard. Therefore, a good representation method of a 3D packing is strongly required to obtain a good packing by searching method such as Simulated Annealing. In this paper, we propose a method to represent 3D packing of rectangular boxes using a tree representation. Also, we propose an improved method of decoding in O(n log n+s) time compared with the conventional one of O(n^2) time using computational geometry, where n is the number of rectangular boxes and s is that of pairs of rectangular boxes overlapping in xy plane. We have confirmed the efficiency of the proposed methods by experimental comparisons. |
| キーワード(和) | 直方体パッキング, / Sequence-Quintuple / O-Tree / 計算幾何学 |
| キーワード(英) | 3D-packing / Sequence-Quintuple / O-Tree / computational geometry |
| 資料番号 | CAS2004-18,VLD2004-29,SIP2004-32 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2004/6/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木構造データを用いた直方体パッキング表現手法(信号処理,LSI,及び一般) |
| サブタイトル（和） | |
| タイトル（英） | 3D-Block Packing using a Tree Representation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 直方体パッキング, / 3D-packing |
| キーワード(2)（和/英） | Sequence-Quintuple / Sequence-Quintuple |
| キーワード(3)（和/英） | O-Tree / O-Tree |
| キーワード(4)（和/英） | 計算幾何学 / computational geometry |
| 第 1 著者 氏名（和/英） | 川井 英教 / Hidenori KAWAI |
| 第 1 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture and Technology |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 2 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture and Technology |
| 発表年月日 | 2004/6/11 |
| 資料番号 | CAS2004-18,VLD2004-29,SIP2004-32 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 117 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |