| 講演名 | 2007-03-05 配線長を考慮した半順序制約付きシーケンスペアによるモジュール配置の評価と考察(通信のための信号処理,符号理論,一般) 矢野 勇生, 金子 峰雄, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | モジュール配置問題において,シーケンスペアと呼ばれる配置表現のコードに基づき,焼きなまし法(SA)にて解空間を探索する手法が提案されている.SAの性質上,十分に計算時間をかけることで良質な解を得ることができるが,回路規模が大きくなるにつれ,シーケンスペアの解空間サイズがモジュール数に対し指数的に増加し,実行時間が増大してしまうことが問題となっている.これに対して,与えられたインスタンスから二次配線長最小配置(これをモデル配置とする)を求めてそこでのモジュール間相対位置関係を利用し,シーケンスペア中のモジュール出現順に制約を課すことで,探索する解空間を縮小する効率化手法が提案された.本稿ではこの方式に基づいて種々の配置実験を行い, (1)モデル配置のモジュール間重なり除去の効果,(2)制約付与率と解の質,(3)通常のシーケンスペアとの比較等について評価検証を行った. |
| 抄録(英) | In the module placement problem, the code representation of a placement called sequence-pair, and simulated annealing search of the solution space defined by the sequence-pair have been proposed. Due to the properties of sequence-pair and SA search, the computation time increases rapidly as the circuit size becomes large. As an approach to this problem, a solution space reduction using a model placement has been proposed. The model placement is obtained, for example, by computing a placement which minimizes total quadratic wire length. The solution space reduction is then achieved by transforming relative positions between modules in the model placement into constraints on sequence-pairs. In this paper, we conduct experiments of placement optimization based on the method mentioned above. This paper reports experimental results and discussions in the following issues: (1) The effect of removing overlaps between modules in the model placement, (2) the effect of the minimum distance between modules for which we extract relative position and transform it to a constraint on sequence-pair, and (3) comparison with normal sequence-pair. |
| キーワード(和) | シーケンスペア / simulated annealing / 力学的手法 / 半順序 / 解空間縮小 / 重なり除去 |
| キーワード(英) | Sequence-pair / simulated annealing / force-directed method / partial order / solution space reduction / overlap removal |
| 資料番号 | CAS2006-88,SIP2006-189,CS2006-105 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2007/2/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 配線長を考慮した半順序制約付きシーケンスペアによるモジュール配置の評価と考察(通信のための信号処理,符号理論,一般) |
| サブタイトル（和） | |
| タイトル（英） | Evaluation and Discussion on Module Placement using Wire Length Aware Partially Ordered Sequence-Pair |
| サブタイトル（和） | |
| キーワード(1)（和/英） | シーケンスペア / Sequence-pair |
| キーワード(2)（和/英） | simulated annealing / simulated annealing |
| キーワード(3)（和/英） | 力学的手法 / force-directed method |
| キーワード(4)（和/英） | 半順序 / partial order |
| キーワード(5)（和/英） | 解空間縮小 / solution space reduction |
| キーワード(6)（和/英） | 重なり除去 / overlap removal |
| 第 1 著者 氏名（和/英） | 矢野 勇生 / Yuuki YANO |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 金子 峰雄 / Mineo KANEKO |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology |
| 発表年月日 | 2007-03-05 |
| 資料番号 | CAS2006-88,SIP2006-189,CS2006-105 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 567 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |