PCクラスタ環境における並列分枝限定法大阪市立大学学術情報総合センター大西克実はじめに分散処理環境  クラスタ構築例  クラスタの利用  巡回セールスマン問題  並列分枝限定法  計算機実験結果  グリッドコンピューティング     “ネットワークを介して複数のコンピュータを結ぶことで仮想的に高性能コンピュータをつくり、利用者はそこから必要なだけ処理能力や記憶容量を取り出して使うというシステム” 複数コンピュータで並列処理し高速・大量の処理を実行スーパーコンピュータの高速ネットワークによる接続余剰パソコンの活用パソコンによる分散処理環境    パソコンの性能向上インターネット技術ツールの提供    PVM,MPI 環境構成，起動，通信などのライブラリ UNIX-WS,PC-WS,Super Computer プロジェクト例  SETI@HOME   distributed.net    暗号など解読 GIMPS(Great Internet Meresenne Prime Search)   地球外生命探索メルセンヌ素数 Googleツールバー Score 星状型マルチプロセッサシステム    PVMライブラリを利用親プロセッサ(PP) 1台と複数の子プロセッサ(CP)で構成プロセッサ間通信のみ，共有メモリなし PP CP1 CP2 CPm クラスタ構築例   性能比較のためにスペックを揃える．購入時期が半年かわるだけでも大変．   同じ製品を入手できない． HD それほど性能に影響がない？  マザーボードチップセットが同じならOK?  CPUはあらかじめ24個購入買っておいて良かった  配線はまじめに業者(F)納品物と比較ネットワーク構成 160.193.XX.0/24 IP VLAN over ATM ATMハブＡＴＭハブ 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) FreeBSD 3.3-RELEASE OS クラスタの利用  組合せ最適化問題を解く人員配置，スケジューリング，配送  特に巡回セールスマン問題   並列分枝限定法を利用部分問題を並列に解く  粒度が大きくクラスタ向き  巡回セールスマン問題  対称と非対称枝コストの扱いの違い  対称巡回セールスマン問題の定義 n 1 n 目的関数 :   cij xij  最小化 i 1 j i 1 i 1 制約条件 :  xij  j 1 n x j i 1 ij  2; i  1,2  n xij  0 or1; i  1,2, n  1; j  2,3, n; i  j xij  1となる枝の集合は長さnの巡回路を作る巡回セールスマン問題(2)  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 FreeBSD3.3 メモリ 128MB 256MB CPU Celeron 433MHz 最大19台 AMD K6 200MHz 1台台数子プロセッサでの探索  次に分解する問題候補の探索最良下界優先探索  再割り当てように親プロセッサに送る問題候補の探索幅優先探索 500 20.000 450 18.000 400 16.000 350 14.000 300 12.000 250 10.000 200 8.000 150 6.000 100 4.000 50 2.000 0 0.000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 GR48[台数/時間(秒)，加速度] 200 20.000 180 18.000 160 16.000 140 14.000 120 12.000 100 10.000 80 8.000 60 6.000 40 4.000 20 2.000 0 0.000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 EIL51[台数/時間(秒)，加速度] 6000 20.000 18.000 5000 16.000 14.000 4000 12.000 3000 10.000 8.000 2000 6.000 4.000 1000 2.000 0 0.000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ST70[台数/時間(秒)，加速度] 800 20.000 18.000 700 16.000 600 14.000 500 12.000 400 10.000 8.000 300 6.000 200 4.000 100 2.000 0 0.000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 RAT99[台数/時間(秒)，加速度] むすび  クラスタの構築例の紹介  クラスタ上での並列分枝限定法  TSPに対する適用結果