負荷の違いによるGAの処理時間について2
No. 03, 2001年 7月 6日
片浦 哲平
1 先週からの課題
先週からの課題として
- オプションの意味の解説
- SGAのプログラムの作成
- GAプログラムの時間測定の修正，測定
があった．期間内に取り組めたものについて解説をする．
2 オプションの意味
今回の実験では，実行に-fomit-frame-pointer，-O3，-funroll-all-loopsのパラメータを
用いた．このオプションの役割，効果を述べる．
今回用いたオプションはすべて，最適化を制御するオプションである．
-Oオプションは最適化を行うオプションで-O0〜-O3までがある．-O0は最適化を行わないオプションで
-O1〜-O3は数字が大きくなるにつれて最適化の強度が増す．
-Oを指定すると，すべてのマシン上においてコンパイラは，
-fthread-jumpsを有効にする．すなわち，多重の条件ジャンプの最適化を行うことである．
サポートされている最適化のうちサイズとスピードとのトレードオフを伴わないほとんどすべての
ものを実行する．したがって，ループ展開と関数インライン展開を除くすべての任意選択の最適化が
有効になる．最適化されるオプションを説明する．
2.3.1 -fstrength-reduce
ループ強度（loop strength）の削減と反復変数の除去による最適化を実行する．
2.3.2 -fthread-jumps
比較によるジャンプの分岐先において，最初の比較に包含されるような別の比較があるかどうかを
チェックすることにより，最適化を実行する．最初の比較が２番目の比較を包含するのであれば，
２番目の比較の条件式が真偽いずれであるかが分かっているような場合には，真であれば，
最初の分岐命令の分岐先を２番目の分岐命令の分岐先に，偽であれば，最初の分岐命令の分岐先を
２番目の分岐命令の直後に変更する．
2.3.3 -fcse-follow-jumps
共通部分式の除去において，ジャンプ命令のジャンプ先がそのジャンプ命令以外のパスからは
到達されない場合，そのジャンプ命令のジャンプ先を調べる．
2.3.4 -fcse-skip-blocks
条件に応じてブロックをスキップするジャンプを追跡させる．
-fcse-skip-blocks は，else 節を持たない単純な if 文を見つけた場合に，
if の本体（body）を飛び越すジャンプを追跡させる．
2.3.5 -frerun-cse-after-loop
ループ最適化の実行後に再度，共通部分式の除去を実行する．
2.3.6 -fexpensive-optimizations
相対的にコストのかかる，重要ではない最適化をいくつか実行する．
2.3.7 -fdelayed-branch
命令の実行順序を変更することがターゲット・マシンでサポートされていれば，
遅延分岐命令の後に利用可能な命令スロットを活用するために，命令の実行順序の変更を試みる．
2.3.8 -fschedule-insns
命令の実行順序を変更することがターゲット・マシンでサポートされていれば，
必要なデータが利用できるようになっていないために発生する実行の一時的停止を除去するために，
命令の実行順序の変更を試みる．速度の遅い浮動小数点命令やメモリ・ロード命令を持つマシンでは，
ロード命令や浮動小数点命令の結果が必要になるまでの間，他の命令を実行することができるように
することによって役に立つ．
2.3.9 -fschedule-insns2
レジスタの割り当てが行われた後に，追加的に命令スケジューリングのパスの実行を要求する．
レジスタの数が比較的少なく，メモリ・ロード命令が複数サイクルを要するマシン上において特に役立つ．
2.3.10 -ffunction-sections
任意のセクションを自由に選択することがターゲット・マシンによりサポートされていれば，
出力ファイルの中において個々の関数を別個のセクションに置く．
関数の名前が，出力ファイルの中におけるセクションの名前を決定する．
命令空間（instruction space）において参照の範囲を改善するための最適化をリンカが実行
することができるようなシステム上において有効である．
このオプションを指定すると，アセンブラとリンカはサイズのより大きいオブジェクト・ファイルと
実行ファイルを作成するようになる．また，アセンブラとリンカの実行速度も遅くなる．
2.3.11 -fcaller-saves
関数呼び出しによって内容の破壊されるレジスタの中に値を割り当てることができるようにする．
2.3.12 -fno-peephole
マシン固有のピープホール（peephole）の最適化をすべて無効にする．
2.3.13 -fbranch-probabilities
-fprofile-arcs（see section ユーザ・プログラムもしくは GNU CC をデバッグするためのオプション）
を指定してコンパイルしたプログラムを実行後，分岐命令が取るであろうパスの推測に基づいて最適化
を改善するために，そのプログラムを -fbranch-probabilities を指定して再度コンパイルすることが
できる．
さらに最適化を行う．-O3は，-O2により指定されるすべての最適化を有効にした上に
inline-functionsオプションも有効にする．
これは，単純な関数はすべて呼び出し側に統合するもので，このような方法で統合する
値打ちがあるほど単純である関数はどれかということをコンパイラが判断して決定する．
2.5 -fomit-frame-pointer
フレーム・ポインタを必要としない関数においては，フレーム・ポインタをレジスタ内に保持しない．
これにより，フレーム・ポインタの待避，セットアップ，復元を行う命令を使わずに済むようになる．
また，多くの関数において，レジスタを余分に利用することができるようになる．
2.6 -funroll-loops
-O2によって実行されない最適化オプションの1つ．
ループ展開（loop unrolling）による最適化を実行する．コンパイル時，もしくは，実行時に
反復回数が決定できるループに対してのみ，この最適化が実行される．
どういう事かというと，例えば，
#include <stdio.h>
int main()
{
int i;
for( i = 0; i < 4; i++ );
printf( "i = %d\n", i);
return 0;
}
というプログラムがあるとする．
#include <stdio.h>
int main()
{
printf("i = %d\n", 0);
printf("i = %d\n", 1);
printf("i = %d\n", 2);
printf("i = %d\n", 3);
return 0;
}
という風に展開する．
ループ処理と変数が無くなっている分だけ，高速な処理が可能となる．
ただし，注意しなければならないのは，この処理によって実行ファイルのサイズが
かなり増大することがある，ということである．ディスク容量が大規模になったため容量の
心配は必要ないと思われるが，実行時のサイズの増大は計算機の速度低下の一因となる恐れがある．
せっかくの最適化が速度低下の原因になっては意味がないため，ループの最適化は可能な限り別の
方法で行った方が良く，特にループ回数が多い場合は別の方法での最適化を考えるべきであると思われる．
2.7 -funroll-all-loops
-O2によって実行されない最適化オプションの1つ．
ループ展開（loop unrolling）による最適化を実行する．これは，すべてのループに対して実行される．
3 GAプログラムの時間測定の修正，測定
プログラムの修正が終わっていないため，進んでいない．
新たに分かったことは，負荷を増加させると計算ができなかった
理由は消費電力にあるということである．
****負荷120の場合****
プロセッサ数が16，32，64ならば実行が可能で，
プロセッサ数が128の時はブレーカーが落ちてストップした．
****負荷150の場合****
プロセッサ数が16，32なら実行可能で，
プロセッサ数が64，128の時はブレーカーが落ちてストップした．
4 今後の課題
GAプログラムによる並列処理の効果は計測時間のプログラムの修正とクラスタの電源の問題が
解決するまで保留とする．
今後は大学院入試のための勉強と，SGA，DGAのプログラムを作成しプログラムの技術を高める
ことの2つに要点を置く．
File translated from
TEX
by
TTH,
version 2.92.
On 05 Jul 2001, 23:08.