(cache) 負荷の違いによるGAの処理時間について

(cache) 負荷の違いによるGAの処理時間について負荷の違いによるGAの処理時間について
No. 03, 2001年 6月 22日
片浦哲平

1 先週からの課題

先週からの課題として

オプションの意味を理解する

負荷を変えることでGAの処理時間がどのように変化するのかを調べる

SGAのプログラムの作成

があったが，SGAプログラムは現在作成中であるため，それ以外の課題についての報告を行う．今回の実験もデータを収集するGAプログラムは佐野正樹さんが作成したソースを用いて， cambriaで実行した．

2 オプションの意味

今回の実験では，実行に-formit-frame-pointer，-O3，-funroll-all-loopsのパラメータを用いた．このオプションの役割，効果を述べる．

今回用いたオプションはすべて，最適化を制御するオプションである．

2.1 -O

-Oオプションは最適化を行うオプションで-O0～-O3までがある．-O0は最適化を行わないオプションで -O1～-O3は数字が大きくなるにつれて最適化の強度が増す．

2.1.1 -O1

-Oが指定されないとコンパイル処理にかかるコストを削減することとデバッグ処理が期待される結果をもたらすようにすることがコンパイラの目標となるが，-O が指定されるとコンパイラは，コードのサイズと実行時間を削減するよう試みる．このため，この最適化にはいくらか余分に時間がかかり，関数のサイズが大きい場合には，かなり多くのメモリが追加的に必要になる．

-O1に比べさらに最適化を行う．コンパイラは，サポートされている最適化のうちサイズとスピードとのトレードオフを伴わないほとんどすべてのものを実行する．-O2を指定した場合にはコンパイラはループ展開（loop unrolling）や関数のインライン展開を実行しなくなる．したがって，-O2により，ループ展開と関数インライン展開を除くすべての任意選択の最適化が有効になりる．また，-O1と比較すると，コンパイル時間はより長くなるが，生成されるコードの性能は向上する．

2.1.3 -O3

さらに最適化を行う．-O3は，-O2により指定されるすべての最適化を有効にした上に inline-functionsオプションも有効にする． inline-functionsオプションには-finline-functionsと-fkeep-inline-functionsがあり，どちらも，単純な関数はすべて呼び出し側に統合し，このような方法で統合する値打ちがあるほど単純である関数はどれかということをコンパイラが発見して決定する．

2.2 -formit-frame-pointer

フレーム・ポインタを必要としない関数においては，フレーム・ポインタをレジスタ内に保持しない．これにより，フレーム・ポインタの待避，セットアップ，復元を行う命令を使わずに済むようになる．また，多くの関数において，レジスタを余分に利用することができるようになる．

2.3 -funroll-loops

-O2によって実行されない最適化オプションの1つ．

ループ展開（loop unrolling）による最適化を実行する．コンパイル時，もしくは，実行時に反復回数が決定できるループに対してのみ，この最適化が実行される．

2.4 -funroll-all-loops

-O2によって実行されない最適化オプションの1つ．

ループ展開（loop unrolling）による最適化を実行する．これは，すべてのループに対して実行され通常は，プログラムの実行速度はより遅くなる．

3 GAプログラムの実行

プログラムの初期パラメータはTable:1 ,Table:1b ,,Table:1bb の通りである．

Table 1: 実験に用いたパラメータ1

試行回数	10	移住率	0.3
移住間隔	5	交叉率	0.8
遺伝子長	100	突然変異率	0.01
負荷	100	世代数	1000

Table 2: 実験に用いたパラメータ2

試行回数	10	移住率	0.3
移住間隔	5	交叉率	0.8
遺伝子長	100	突然変異率	0.01
負荷	50	世代数	1000

Table 3: 実験に用いたパラメータ3

試行回数	10	移住率	0.3
移住間隔	5	交叉率	0.8
遺伝子長	100	突然変異率	0.01
負荷	10	世代数	1000

4 実行結果

まず，実行した結果をTable:4 ,Table:5 ,Table:6 に示す．

Table 4: 実行結果(パラメータ1)

プロセス数	etc	Selection	Migration	Crossover	Mutation	合計
1	計測不可	計測不可	計測不可	計測不可	計測不可	計測不可
2	計測不可	21.742837	4.792302	3.157590	2.039514	計測不可
4	計測不可	5.608720	2.802851	1.461155	1.016916	計測不可
8	173.04160	1.663831	1.785722	0.747054	0.507647	177.74580
16	86.45640	0.550489	1.044114	0.394354	0.254805	88.70016
32	43.18193	0.205855	0.905255	0.216636	0.128005	44.63768
64	21.57092	0.086134	0.697310	0.128031	0.064585	22.54698
128	12.21032	0.081949	0.387567	0.502294	0.315666	13.49779

Table 5: 実行結果(パラメータ2)

プロセス数	etc	Selection	Migration	Crossover	Mutation	合計
1	計測不可	86.86325	0.004486	6.750445	4.089184	計測不可
2	計測不可	20.77312	4.346866	2.968899	2.035281	計測不可
4	174.97230	5.58273	2.017771	1.458047	1.015411	185.04630
8	87.34846	1.66112	1.102404	0.747915	0.509063	91.36897
16	43.62265	0.54852	0.694906	0.393090	0.254852	45.51401
32	21.78176	0.20549	0.567830	0.217106	0.128141	22.90032
64	10.89029	0.08619	0.458937	0.128353	0.064978	11.62874
128	5.45488	0.04040	0.359388	0.086545	0.033153	5.97437

Table 6: 実行結果(パラメータ3)

プロセス数	etc	Selection	Migration	Crossover	Mutation	合計
1	172.09960	88.07413	0.003704	6.831991	4.112855	271.12230
2	76.57698	21.29627	3.766389	3.074150	2.038578	106.75237
4	37.87402	5.64392	1.357294	1.466472	1.017295	47.35900
8	18.79906	1.65707	0.563328	0.745520	0.508383	22.27336
16	9.34423	0.54896	0.284067	0.393268	0.255286	10.82581
32	4.64118	0.20648	0.212748	0.217832	0.128869	5.40711
64	2.31904	0.08680	0.189621	0.128680	0.065420	2.78956
128	1.14869	0.04055	0.159327	0.086168	0.032932	1.46766