| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-12-01 13:15 コードベース三次元直方体配置における隣接挿入操作とその効果 ○上杉 伸・金子峰雄（北陸先端大）  VLD2010-77 DC2010-44 |
|
| 抄録 | （和） | 三次元直方体配置問題に対して，個々の配置解をコードにて表現する手法(コード表現手法)と確率的探索手法(例えば焼き鈍し法(Simulated Annealing(SA)))を組み合わせて準最適解を求めるアプローチが試みられている．二次元矩形配置問題に対して成功を収めたSequence Pair や O-Tree の三次元への拡張として5つの直方体名順列を使うSequence Quintuple や O-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 / / / / | |
| 文献情報 | 信学技報, vol. 110, no. 316, VLD2010-77, pp. 149-154, 2010年11月. | |
| 資料番号 | VLD2010-77 | |
| 発行日 | 2010-11-22 (VLD, DC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2010-77 DC2010-44 |
|
| 研究会情報 | |
| 研究会 | VLD DC IPSJ-SLDM CPSY RECONF ICD CPM |
| 開催期間 | 2010-11-29 - 2010-12-01 |
| 開催地（和） | 九州大学医学部百年講堂 |
| 開催地（英） | Kyushu University |
| テーマ（和） | デザインガイア2010 ―VLSI設計の新しい大地― |
| テーマ（英） | Design Gaia 2010 ―New Field of VLSI Design― |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2010-11-VLD-DC-SLDM-CPSY-RECONF-ICD-CPM |
| 本文の言語 | 日本語 |
| タイトル（和） | コードベース三次元直方体配置における隣接挿入操作とその効果 |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 上杉 伸 / Shin Uesugi / ウエスギ シン |
| 第1著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 第2著者 氏名（和/英/ヨミ） | 金子 峰雄 / Mineo Kaneko / |
| 第2著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-12-01 13:15:00 |
| 発表時間 | 20分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2010-77, DC2010-44 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.316(VLD), no.317(DC) |
| ページ範囲 | pp.149-154 |
| ページ数 | 6 |
| 発行日 | 2010-11-22 (VLD, DC) |
[研究会発表申込システムのトップページに戻る]