PCクラスタ環境での並列シミュレーティッドアニーリング法による基板設計問題の計算

URI http://harp.lib.hiroshima-u.ac.jp/hkg/metadata/795
ファイル
タイトル
PCクラスタ環境での並列シミュレーティッドアニーリング法による基板設計問題の計算
別タイトル
A computation issue in circuit board design using distributed simulated annealing with PC cluster
著者
氏名 中川 歩
ヨミ ナカガワ アユミ
別名 Nakagawa Ayumi
氏名 趙 悦
ヨミ
別名 Zhao Yue
キーワード
シミュレーティッドアニーリング法
分散シミュレーティッドアニーリング法
基盤設計
PCクラスタ
分割問題
配線問題
simulated annealing
distributed simulated annealing
circuit boad design
wiring problem
PC cluster
抄録

In this paper, we discuss the application of the distributed simulated annealing(DSA) to the graph partition problem and the wiring problem which occurred in the process of circuit board design. DSA is a parallel algorithm that needs a shorter computation time than using the traditional simulated annealing algorithm. We carried out the experiment in the environment of PC cluster using DSA. Through comparing the solutions and the computation time with some of the results based on the traditional simulated annealing algorithm, it was confirmed that DSA is more effective.

基板設計の工程の中には次の3つのステップがある。一つは部品を複数の基板に分割して配置する分割問題があり,二つ目に基板のどの部分に部品を置くかを決める配置問題又はフロアプラン問題がある。そして三つ目に,部品間の配線を決定する配線問題がある。これら三つのステップは組み合わせ最適化問題となり,NP-完全問題に分類される。本論文では,シミュレーティッドアニーリング法(SA法)を並列計算に適応させた分散シミュレーティッドアニーリング法(DSA法)をPCクラスタ上で基板設計工程で生じる上述の一つ目の分割問題と三つ目の配線問題に適応させて実験をし,基板設計時における分散シミュレーティッドアニーリング法の活用を模索した。SA法と比較することによって,分散シミュレーテッドアニーリング法の有効性を実証した。

掲載雑誌名
広島国際学院大学研究報告
40
開始ページ
31
終了ページ
37
出版年月日
2007
出版者
広島国際学院大学
ISSN
1345-3858
NCID
AA11419398
本文言語
日本語
資料タイプ
紀要論文
著者版フラグ
出版社版
旧URI
区分
hkg