Presentation
ネットワーク性能に合わせた
分散遺伝的アルゴリズムにおける
最適な移住についての検討
知的システムデザイン研究室
斉藤 宏樹
ISDL Monthly Lecture Meeting
遺伝的アルゴリズム
・遺伝的アルゴリズム(GA)は有効な最適化手法の
一つ.
GAの問題点
・個体の評価に時間を要する.
・解探索に膨大な反復計算を
行うため計算コストが高い.
並列化により,
計算コストを軽減させ,
実行速度を向上させる
ISDL Monthly Lecture Meeting
並列遺伝的アルゴリズム
・GAを並列化して実行
並列遺伝的アルゴリズム(PGA)の研究が行われて
いる.
・PGAの代表的なモデル
実行速度の向上だけでなく、有効な解探索を目的と
した,島モデルがある.
島モデルは分散遺伝的アルゴリズム(DGA)と
呼ばれる.
ISDL Monthly Lecture Meeting
分散遺伝的アルゴリズム
・DGAは母集団を複数の分割母集団(島)に分割し
各島内で遺伝的操作を行うGAの並列モデル.
・移住という操作により各島間で
個体の交換が行われる.
並列で行う場合,
移住には通信を要する.
ISDL Monthly Lecture Meeting
移住のパラメータ
・移住率
各島内における移住個体の
割合.
・移住間隔
何世代おきに移住するか.
最適な移住のパラメータは,問題に依存し,
何回か試行することで経験的に定めてきた.
ISDL Monthly Lecture Meeting
DGAを並列計算機上で実行
・島数を増加させることで,実行時間は短縮するか.
(並列化効率は良くなるか.)
・移住のパラメータは,実行時間にどう影響するか.
・CPUやネットワークの性能が異なる並列計算機上で
DGAを実行.
ISDL Monthly Lecture Meeting
数値実験に用いたマシン
・実験では本研究室にあるGregor,Maiaを使用.
Gregor
CPU
Maia
Pentium 1GHz×64×2 POWER3-Ⅱ375MHz×16
通信ライブラリ MPI,PVM
IBM MPI for AIX
通信プロトコル GM,TCP/IP
USプロトコル,TCP/IP
通信媒体
SPスイッチ,
Fast Ethernet
Myrinet 2000,
Fast Ethernet
・ GregorでMyrinet,Ethernetによる実行時間の比較.
・ MaiaでSPスイッチ,Ethernetによる実行時間の比較.
ISDL Monthly Lecture Meeting
実験方法
・移住間隔,島数を変えて計測.
移住間隔を経験的に利用している1と5に設定し,
島数は2から最大40で実行.
・テスト関数にはRidge関数を使用.
単峰性で依存関係あり.
・1島を1プロセッサとする.
ISDL Monthly Lecture Meeting
DGAのパラメータ
・DGAのパラメータを以下に示す.
総個体数
遺伝子長
設計変数
移住率
終了世代
試行回数
480
200
20
0.5
1000
20
・総個体数を島数で割ったものが,1島の個体数と
なる.
ISDL Monthly Lecture Meeting
島数と実行時間
Gregor:20回試行平均
MyrinetはEthernetよりも実行時間が短くなっている.
Ethernetは島数が増えると実行時間が長くなっている.
ISDL Monthly Lecture Meeting
島数と実行時間
Maia :20回試行平均
SPスイッチの方がEthernetより実行時間が短い.
ISDL Monthly Lecture Meeting
実行時間における移住時間の割合
Gregor :20回試行平均
Ethernetは島数が増加すると移住に多くの時間を
消費し,移住によるCPUの待ち時間が長い.
ISDL Monthly Lecture Meeting
実行時間における移住時間の割合
Maia :20回試行平均
SPスイッチはMyrinet同様移住時間の占める割合が
増加しない.
ISDL Monthly Lecture Meeting
ネットワーク性能
・EthernetはCSMA/CD方式.
ネットワーク媒体上に,データ転送が行われて
いないかどうかを検査し,行われてなければ
データ転送を行う.
検査してから転送するまでには遅延時間があり,
同時に送信するデータ数が増加すると,
データの衝突を起こす.
Myrinet,SPスイッチは通信路が一つでは無く,
衝突が起こらないようにしている.
ISDL Monthly Lecture Meeting
CPUとネットワーク性能
・Gregor,MaiaのEthernet
CPUの性能とネットワークのバランスが悪いので,
島数が増加すると実行時間が長くなる.
・GregorのMyrinet,MaiaのSPスイッチ
CPUの性能とネットワークの性能のバランスが
良いので,実行時間は短くなる.
CPUとネットワークの性能に応じて,
DGAを実行することが重要である.
ISDL Monthly Lecture Meeting
CPUとネットワーク性能に応じた移住
・DGAにおける移住間隔を,通信負荷に応じて,
変更する必要がある.
・移住間隔を以下のパラメータによって,動的に
変更する.
移住時間
=通信負荷率
実行時間
通信負荷率を用いたDGAを実行する.
ISDL Monthly Lecture Meeting
実験方法
・移住間隔,島数を変えて実行時間を計測.
移住間隔を始め1に設定し,通信負荷率が
0.2,0.3を超えると,移住間隔を2倍にしていく.
島数は2から最大40で実行.
・テスト関数にはRidge関数を使用.
・1島を1プロセッサとする.
・Gregorのみで実行.
・DGAのパラメータは前回と同様.
ISDL Monthly Lecture Meeting
島数と実行時間
20回試行平均
通信負荷に応じて動的に移住間隔を変更することで,
EthernetにMyrinet同様並列化効率が見られる.
ISDL Monthly Lecture Meeting
実行中の移住間隔の推移
Ethernet:通信負荷率0.2
島数の増加に伴ない,移住間隔を大きくしている.
ISDL Monthly Lecture Meeting
実行中の移住間隔の推移
Myrinet:通信負荷率0.2
Myrinetは通信負荷が低く,移住間隔を大きくしない.
ISDL Monthly Lecture Meeting
解の性能
・通信負荷に応じて移住間隔を大きくすることで,
実行時間は短くなった.
移住間隔を動的に変更することで,
解探索はどうなるのか.
・Ridge関数の最適解が求まるまでの実行時間,
世代数について,一定間隔の移住(1,5)を行う
ものと解の性能を比較する.
ISDL Monthly Lecture Meeting
DGAのパラメータ
総個体数
遺伝子長
設計変数
移住率
交叉
交叉率
突然変異率
選択
トーナメントサイズ
エリート保存
終了世代
試行回数
480
200
20
0.5
一点交叉
1.0
0.005
トーナメント選択
4
1
1000
20
ISDL Monthly Lecture Meeting
最適解を得るまでの時間
Ethernet :20回試行の平均値
移住間隔を固定した場合より,最適解を得るまでの
実行時間が短い.
ISDL Monthly Lecture Meeting
最適解を得るまでの時間
Myrinet :20回試行の平均値
ISDL Monthly Lecture Meeting
最適解を得るまでの世代数
Ethernet :20回試行の中央値
より多くの評価計算が行われている.
ISDL Monthly Lecture Meeting
最適解を得るまでの世代数
Myrinet :20回試行の中央値
ISDL Monthly Lecture Meeting
まとめ
・異なるCPUとネットワークで,DGAを実行.
CPUとネットワーク性能に応じて,DGAを
実行することが重要であることがわかった.
・CPUとネットワーク性能を考慮したDGAの検討
移住間隔を動的に変更することで,マシンの
性能をフルに利用し,並列化効率を向上できた.
解の性能は,従来のDGAより短い実行時間で
求めることができた.
ISDL Monthly Lecture Meeting
ISDL Monthly Lecture Meeting
ネットワーク性能の比較
Ethernet
Myrinet
理論バンド幅 12.5MB/sec 160MB/sec
トポロジ
SPスイッチ
150MB/sec
スイッチング 高速スイッチ SPスイッチ
ハブ
ング
ISDL Monthly Lecture Meeting
Ethernetで遅延が発生した理由
・CSMA/CD方式
パケットの増加による衝突.
・TCP/IP処理による遅延
今回の実行時間から考えると,無視できる.
これはMaiaによる実行結果からわかる.
・ヘッダ情報の増加
データ数が増加すると,ヘッダ情報が増加するが,
島数が2と40の場合で0.475KBしか異ならない.
これは,移住個体2個分である.
ISDL Monthly Lecture Meeting
TCP/IPのオーバヘッド解析
単位:マイクロ秒
処理内容
割合
1.6
システムコール
TCP
15.5
IP
プロトコル処理切り替え
デバイスドライバ
6.2
3.2
4.7
ハードウェア割り込み
NIC+メディア遅延
合計
5.9
7.7
44.8
TCP/IP処理 48.4%
参考資料:Linuxで並列処理をしよう
ISDL Monthly Lecture Meeting
低遅延ソフトウェアGM
独自の軽量プロトコルを用いて,低遅延を実現
ISDL Monthly Lecture Meeting
移住の実装
・移住における通信の方法
MPI_Sendrecv()により移住個体の遺伝子情報を,
各島間で通信する.
MPI_Bcast()により通信を行う島の情報を,
各島間に送信する.
・通信量
遺伝子の情報量=移住個体数×200B
通信する島の情報量=島数×2B
ISDL Monthly Lecture Meeting
島数が40の場合の通信量
・理論バンド幅の80%の性能がでているとする.
バンド幅=0.006(移住時間)×12.5MB×0.8=0.6MB
・通信量
遺伝子の情報量=6(移住個体数)×200B=1.2KB
通信する島の情報量=40(島数)×2B=0.08KB
ISDL Monthly Lecture Meeting
移住率
・移住率を変更しなかった理由
移住率を変化させても,送受信するデータ数は
島数が増加することで増えつづけ,その影響が
大きいと考えたからである.
ISDL Monthly Lecture Meeting
ダウンロード

ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な