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

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

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法と比較することによって,分散シミュレーテッドアニーリング法の有効性を実証した。

Journal Title
広島国際学院大学研究報告
Volume
40
Spage
31
Epage
37
Published Date
2007
Publisher
広島国際学院大学
ISSN
1345-3858
NCID
AA11419398
Language
jpn
NIIType
Departmental Bulletin Paper
Text Version
出版社版
Old URI
Set
hkg