| 講演名 | 2010-12-01 コードベース三次元直方体配置における隣接挿入操作とその効果(物理設計,デザインガイア2010-VLSI設計の新しい大地-) 上杉 伸, 金子 峰雄, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 三次元直方体配置問題に対して,個々の配置解をコードにて表現する手法(コード表現手法)と確率的探索手法(例えば焼き鈍し法(Simulated Annealing(SA)))を組み合わせて準最適解を求めるアプローチが試みられている.二次元矩形配置問題に対して成功を収めたSequence PairやO-Treeの三次元への拡張として5つの直方体名順列を使うSequence Quintupleや0-Treeと順列を組み合わせたDouble Tree and Sequenceが提案されている.しかしこれら手法はSAと組み合わせたとき,二次元矩形配置におけるSPほどの優れた収束性を実現できていない.一方で,制限された配置解のみの表現に留まる三次元スライス表現やSequence Triple (3つの直方体名順列を使う)が比較的良好な収束性を見せることから,一般には解空間の大きさが収束性に大きく影響を与えると考えられているが,両者の関係は必ずしも明確になっているわけではない.本研究では,SQが持つある種の冗長性と,これによって隣接解生成操作が良質な解への到達に必ずしも寄与しない解への遷移を多数発生させる可能性があることに着目し,こうした無駄な遷移を削減して収束性の改善を図ることを考える.具体的には,有用な配置においては,いずれの直方体も他の少なくとも一つの直方体と隣接するであろうとの予想の下に,「隣接挿入」と呼ぶSQに対する新しい隣接解生成操作を導入し,その効果を計算機実験により評価している. |
| 抄録(英) | Three Dimensional (3D) cuboid placement can be considered as a mathematical background of several practical problems such as task scheduling problem for dynamically reconfigurable VLSIs. One typical approach to this 3D placement is the combination of a coding method of placement and a stochastic search method such as Simulated Annealing (SA). Being inspired by the success of Sequence Pair (SP) or Ordered-Tree (O-Tree) in two-dimensional rectangular placement, Sequence Quintuple code, which uses five sequences of cuboid names, and Double-Tree and Seqence (DTS), which uses two trees and one sequence, have been proposed. However, when those methods are combined with SA search, their convergence to solutions of good quality is not so fine as SP and O-tree in 2D placement. In this report, we focus on a kind of redundancy that SQ coding has, which may generate worthless neighbor solutions with a high probability. So we try to improve the convergence to a good solution by suppressing those worthless neighbor solutions. To this end, we will introduce a novel move operation named "adjacent insertion" into SQ framework, which is based on the concept that, in any proper placement, every cuboid is expected to share its border with other cuboid. Finally, our proposed method is evaluated through computer experiments. |
| キーワード(和) | 三次元直方体配置 / 焼き鈍し法(SA) / 隣接挿入 / 計算機実験 |
| キーワード(英) | 3-D placement / simulated annealing (SA) algorithm / adjacent insertion / computer experiment |
| 資料番号 | VLD2010-77,DC2010-44 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2010/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | コードベース三次元直方体配置における隣接挿入操作とその効果(物理設計,デザインガイア2010-VLSI設計の新しい大地-) |
| サブタイトル（和） | |
| タイトル（英） | Adjacent Insertion and Its Effectiveness in Code-Based 3-D Placement |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 三次元直方体配置 / 3-D placement |
| キーワード(2)（和/英） | 焼き鈍し法(SA) / simulated annealing (SA) algorithm |
| キーワード(3)（和/英） | 隣接挿入 / adjacent insertion |
| キーワード(4)（和/英） | 計算機実験 / computer experiment |
| 第 1 著者 氏名（和/英） | 上杉 伸 / Shin UESUGI |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology (JAIST) |
| 第 2 著者 氏名（和/英） | 金子 峰雄 / Mineo KANEKO |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology (JAIST) |
| 発表年月日 | 2010-12-01 |
| 資料番号 | VLD2010-77,DC2010-44 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 317 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |