DBGAのMPIでの実装
片浦 哲平
2002年5月9日
今年度研究報告の前に
昨年行ったこと
・Gregor，Cambriaでの並列GAの性能評価
参照
並列ゼミ 第1回 GAの並列モデルについて
並列ゼミ 第1回 並列クラスタにおけるGAの処理時間について
並列ゼミ 第2回 並列クラスタにおけるGAの処理時間について2
並列ゼミ 第3回 負荷の違いによるGAの処理時間について
並列ゼミ 第4回 負荷の違いによるGAの処理時間について2
第41回 月例発表会 大規模クラスタにおける並列アプリケーションの性能評価
・Grid環境を想定したヘテロな環境におけるDGAの性能評価
参照
並列ゼミ 第5回 SGAプログラムの測定
並列ゼミ 第6回 GAの移住時間についての考察
並列ゼミ 第7回 SGAプログラムの並列化
並列ゼミ 第8回 SGAプログラムの修正
並列ゼミ 第9回 作業･･･
並列ゼミ 第10回 DGAへの改良
並列ゼミ 第11回 ランダムリングの作成(MPI_Bcastを用いた方法)
並列ゼミ 第12回 ランダムリングの修正(複数リングあり)および比較測定
並列ゼミ 第13回 ランダムリングの修正(複数リングなし)およびプログラムのデバッグ
並列ゼミ 第14回 GAJIROとの性能比較
並列ゼミ 第15回 佐野さんのGAとの性能比較
並列ゼミ 第16,17回 gregorにおけるPGIの性能比較
並列ゼミ 第18回 MPICHを用いたPGIの性能比較
並列ゼミ 第19回 ヘテロ環境におけるDGAの性能調査
並列ゼミ 第20回 時間軸のスケーリング
並列ゼミ 第21回 最適なヘテロモデルの検証
第45回 月例発表会 ヘテロ環境におけるDGAの性能評価
・個体データベースを利用したGAの研究
Grid環境に適応したヘテロな環境に対応できるGAの提案として，マスタースレーブモデルのGAの応用モデルとして個体の情報を格納するデータベースをマスターとスレーブの中間に用いたGAの提案を行った．
提案モデルの有効性を調べるためにスレッドを用いたモデルでシミュレーションを行い，その性能を示した．
参照
並列ゼミ 第22回 遺伝子検索システムの構築
並列ゼミ 第23回 ツリー構造の遺伝子検索システム
並列ゼミ 第24回 評価計算プログラムのスレッド化
並列ゼミ 第25回 卒業論文のための実験
卒業論文発表会 Grid環境における評価部にデータベースを用いた遺伝的アルゴリズムの提案
現在行っていること
提案モデルをスレッドで実装したシミュレーションでは，通信の性能が測定できないため，実際にGrid上で用いることを考えた場合に不十分な点が多くあった．そのため，提案するモデルに近づけるために，MPIによってクラスタ上で実装し，同期の取り方や通信時間などの問題を加えて調査することにした．現在は提案モデルをMPIで実装するためのプログラミングを行っている．実装後，性能を測定しSwoppで発表する予定である．
今後の予定
提案モデルを実際にGrid上で動作させる事が最終的な目標となる．そのために，データベースの形式を改良し永久的にデータを保存できる実際のデータベースを用いる，各サイトにアクセスする際のセキュリティ問題を解決する，適切にジョブのスケジューリングを行えるシステムを構築するなど，Grid環境に合った実装にするという様々な課題が残っている．
1．研究報告
今週行ったこと
卒業論文執筆のために個体データベースGA(以下DBGA)をスレッドで実装した．しかし，Grid環境で実装するにはスレッドによるモデルでは以下のような不十分な点があった．
・スレッドではマシン間の通信を考慮に入れることができない．
・スレッドは1台のマシン内に発生するため，データベースに大量のデータを蓄積できない．
通信を考慮できない環境では，通信の遅れの検証や同期のとり方など，Gridでの実装前に必要な情報を得ることができない．そこで，今回はMPIによってクラスタ内で実装を行うことで通信環境のあるモデルを考えた．
図1 提案モデル
MPIを用いてクラスタ内でDBGAを作成する場合には，以下のように実装する必要がある．
MPIを用いて並列プログラムを作成し，実行すると，複数のプロセスが立ち上がり，それらが通信を行いながら並列プログラムが実行される．今回の場合では，プロセスは，マスターのプロセス，データベースのプロセス，評価のプロセスとなる．プロセスにはIDが割り当てられるので，IDごとにマスター，データベース，評価と役割を分配することで，提案モデルのシミュレーションが可能となる．
本プログラムでは，ID＝0にマスター，ID＝1にデータベース，それ以上を評価に割り当てている．
2．通信における問題点
通信における問題点として，以下のような点が挙げられる．
・評価サーバは複数存在するので，データベースサーバは利用頻度の少ない評価サーバに評価を依頼するシステムが必要となる
・評価サーバからデータをデータベースサーバに送る際に，データベースサーバはどのサーバから送られてきたデータかを認識できなければならない
・マスターサーバの遺伝的操作が終了した場合，終了を各サーバにどのように伝えるのかを考えなければならない．
・マスターサーバの遺伝的操作が終了し，評価サーバが残った計算を終えた際に，データベースサーバに全サーバの終了を伝えなければならない
現在の実装では，一番下の問題が解決していない．全評価サーバが計算を終えたことをデータベースサーバに伝えることができてきないため，1試行の最終世代(最適解が求まった世代)でデータベースサーバがプロセスを終了しない．
3．今後の課題
今後の課題は，
・最終世代終了後にデータベースサーバが正しく終了できるようにして複数回試行を可能とする
・データ測定を行いプログラムの動作を調べる
・意図的に評価計算時間を遅らせることで実際の環境に近づけたモデルでの計測
である．