本文へスキップ

「コンピュータ入門」の授業では,数値計算プログラミングの基礎を習得します。

〒910-8507 福井市文京3-9-1

福井大学 工学部 応用物理学科

プログラム高速化のためのノウハウHOW TO SPEED UP

実行速度の測定

time コマンドを使うと,プログラムの実行時間が測定できます。 以下のように,実行ファイル名の前に time をつけて実行すると,最後に実行時間が表示されます。
$ time ./kadai6-3.exe
球の体積:  4.1982121358
real    0m4.056s
user    0m3.993s
sys     0m0.015s

real はプログラム開始から終了までの実時間(キーボードの入力待ちなども含む), user はプログラムの実行のために使われた正味の CPU 時間, sys はプログラム実行のために OS が使用した CPU 時間です。 m は分を s は秒を表わしており,この場合 3.993 秒かかっています。この user 時間を短縮するのが目標です。

最適化コンパイル

コンパイル時に最適化オプション "-O" (Optimize の略)をつけると, コンパイラが自動的に高速化してくれます。
$ gcc -O -o kadai6-3 kadai6-3.c
$ time ./kadai6-3
球の体積:  4.1982120880
real    0m1.216s
user    0m1.153s
sys     0m0.015s

3.993 秒かかっていたのが 1.153 秒に短縮されました。 ただし,最適化によって加算の順序などが変更され,計算誤差の蓄積のされ方が変わって, 数値が変わる場合があるので,注意しましょう。

アルゴリズムの改良

問3の例では,球の全体積を計算しなくても, x ≥ 0, y ≥ 0, z ≥ 0 の領域のみを計算して 8 倍しても計算値は同じです。 これで,計算時間は 1/8 に短縮できます。 また,この他にも,距離の判定を省略できる格子点があります。

プログラムコードの改良

高速化のために,プログラムの記述上,気をつけることがあります。
  1. 除算(/)を使わない。極力 +, -, * のみを使う。
    CPU の構造上,除算には時間がかかります。除算の代わりに逆数を掛けると良い。
  2. sqrt( ), pow( ), exp( ) 等の数学関数をむやみに使わない。
    問3のプログラムでは,「距離」ではなく「距離の2乗」で判定すると良い。
  3. 同じ計算を何度も繰り返さない。
    ループ内で何度も同じ計算をしていると無駄になります。外で計算できることはループ外に移します。
  4. 多重ループの場合,ループ変数の依存性をよく考える。
    外側のループ変数のみに依存する計算を,内側のループで実行すると無駄になります。

分割数 1000 でテスト計算をしながら,プログラムをチューニングして下さい。 この計算時間を 1000 倍することにより,10000 分割の場合の所要時間が見積もれます。

(補足1)
まず,最適化オプション(-O)なしでコンパイルしながらプログラムコードの改良を進め, 十分にチューニングしてから -O 付きでコンパイルすると良いです。

(補足2)
最新の CPU は浮動小数点演算を高速に実行できるようになっており,整数演算との速度差は大きくはありません。 一方,整数演算と浮動小数点演算は CPU チップ内の別の部分で実行されるので,うまく並列実行されると速くなります。 試行錯誤でベストミックスを見つけて下さい。


バナースペース

コンピュータ入門担当

分子科学分野 玉井良則
総合研究棟5階東