大阪市立大学 学術情報総合センター 大西克実 PCクラスタ環境における 並列分枝限定法 大阪市立大学 学術情報総合センター 大西克実
はじめに 分散処理環境 クラスタ構築例 クラスタの利用 巡回セールスマン問題 並列分枝限定法 計算機実験結果
グリッドコンピューティング “ネットワークを介して複数のコンピュータを結ぶことで仮想的に高性能コンピュータをつくり、利用者はそこから必要なだけ処理能力や記憶容量を取り出して使うというシステム” 複数コンピュータで並列処理し高速・大量の処理を実行 スーパーコンピュータの高速ネットワークによる接続 余剰パソコンの活用
パソコンによる分散処理環境 パソコンの性能向上 インターネット技術 ツールの提供 PVM,MPI 環境構成，起動，通信などのライブラリ UNIX-WS,PC-WS,Super Computer
プロジェクト例 SETI@HOME distributed.net 地球外生命探索 distributed.net 暗号など解読 GIMPS(Great Internet Meresenne Prime Search) メルセンヌ素数 Googleツールバー Score
星状型マルチプロセッサシステム PVMライブラリを利用 親プロセッサ(PP) 1台と複数の子プロセッサ(CP)で構成 プロセッサ間通信のみ，共有メモリなし PP CP1 CP2 CPm
クラスタ構築例 性能比較のためにスペックを揃える． 購入時期が半年かわるだけでも大変． 同じ製品を入手できない． HD マザーボード それほど性能に影響がない？ マザーボード チップセットが同じならOK? CPUはあらかじめ24個購入 買っておいて良かった 配線はまじめに 業者(F)納品物と比較
ネットワーク構成 IP VLAN over ATM 160.193.XX.0/24 160.193.XX.0/24 ＡＴＭハブ 160.193.XX.0/24 ＡＴＭハブ 160.193.YY.0/24
構成計算機の詳細 ＣＰＵ Intel Celron Processor 433MHz MEMORY 128MB SDRAM(66MHz) NIC Intel EtherExpress Pro 10/100B Mother 440BX MicroATX VGA ATI model 4742 graphics accelerator HD ST36421A(6GB),WDC WD64AA(6GB),Maxtor 2B20H(20GB) OS FreeBSD 3.3-RELEASE
クラスタの利用 組合せ最適化問題を解く 並列分枝限定法を利用 人員配置，スケジューリング，配送 特に巡回セールスマン問題 部分問題を並列に解く 粒度が大きくクラスタ向き
巡回セールスマン問題 対称と非対称 枝コストの扱いの違い 対称巡回セールスマン問題の定義
巡回セールスマン問題(2) 枝(i,j)を利用するかをxijで表す 問題例 Internet上で公開されているTSPLIB利用， n接点1,2…,nを持つグラフ 各枝(i,j)の重みcij，ただしcij=cji 枝(i,j)を利用するかをxijで表す xij=0:対応する枝を通らない xij=1:対応する枝を通る 問題例 Internet上で公開されているTSPLIB利用， GR48,EIL51,ST70,RAT99
分枝限定法 すべての組合せ最適化問題に 適用可能 分解操作 限定操作 探索 活性部分問題 分枝木
分枝変数の選択 ある枝を経路に利用するか，しないか 枝の選択方法 コスト順 次の巡回都市に対応する枝
下界値と上界値 限定操作を有効にするため 最適解に対する上界・下界値が必要 下界値 上界値 最小1-treeの利用 近似解法(“KL-method”)
並列分枝限定法 部分問題の管理と割り当て 親プロセッサ 部分問題の管理・割当， 問題例のデータ管理 子プロセッサ 他のプロセッサとは独立に動作 近似解プロセッサ
実験結果 A B 機種 PC(クラスタ) PC(研究室) OS FreeBSD3.3 メモリ 128MB 256MB CPU Celeron 433MHz AMD K6 200MHz 台数 最大19台 1台
子プロセッサでの探索 次に分解する問題候補の探索 最良下界優先探索 再割り当てように親プロセッサに送る 問題候補の探索 幅優先探索
GR48[台数/時間(秒)，加速度]
EIL51[台数/時間(秒)，加速度]
ST70[台数/時間(秒)，加速度]
RAT99[台数/時間(秒)，加速度]
むすび クラスタの構築例の紹介 クラスタ上での並列分枝限定法 TSPに対する適用結果