3. プログラムの高速化

高速化技術

高速化技術としては現在のハードウェアの進歩に従い、 多数のコアのCPUまたはGPUを用いて並列計算を行うことが主流となっています。
ここでは以下の技術を実装します。

  1. OpenMP
    これは共有メモリー型並列計算に分類されるもので、 ソースコードに並列計算のための指示文を代入し、 コンパイラがその指示文を元に並列計算する実行プログラムを生成します。
    計算時間のかかる繰り返し処理(for文)の前に指示文を挿入するだけで計算時間を短縮することができます。
    計算時間の主要部を占める部分が単純なアルゴリズムであれば、 簡単なプログラミングで高い実行性能を得ることができます。
    THFD法はOpenMPによる並列化に適したアルゴリズムになっています。

  2. MPI (Message Passing Interface)
    これは分散メモリー型並列計算に分類されるもので、 複数のプロセスを起動し処理を分配することにより計算時間を短縮するものです。 プロセス間のデータのやりとりは通信用の関数を呼び出すことによって行います。
    計算ノードを増やすことにより高速化に上限はありません。
    THFD法はMPIによる並列化に適したアルゴリズムになっています。

  3. CUDA
    これはNVIDIAのグラフィックスボード(GPU)の高い演算能力を科学技術演算に利用するものです。 (GPGPU:General-Purpose computation on Graphics Processing Units)
    CPUは計算の制御を行い、計算時間のかかる部分はGPUで行います。
    GPUでは計算時間のかかるループを多数のスレッドに分解し並列計算します。
    THFD法はCUDAによる並列化に適したアルゴリズムになっています。

  4. CUDA + MPI
    1台のコンピュータに複数のグラフィックスボードを実装したとき(マルチGPU)と、 複数台のコンピュータに1個または複数のグラフィックスボードを実装したとき、 すべてのグラフィックスボードを使用して並列計算することができます。
    CUDAとMPIの両方を実装します。

3.1 二つのモード

3.1.1 二つのモード

本プログラムの使用メモリーの主要部は2.9で述べた連立一次方程式で必要になります。
必要な配列は図2-9-2のx,b,r,p,q,t,uの7個です。
これ以外に行列Aで必要になりますが、行列は1行に13個の非ゼロ要素を持つために、 行列をメモリーに入れると必要メモリーが20/7倍にもなります。 従って計算時間は増えますが行列要素を毎回必要になる毎に計算する方法が考えられます。
本プログラムでは実行時に引数"-matrix"を指定すると初めに行列要素をメモリーに格納し、 引数"-nomatrix"を指定すると行列要素を毎回計算するようにしています。 前者をmatrixモード、後者をnomatrixモードと呼びます。

3.1.2 CPUプロファイル

計算時間の大部分は図2-9-2の行列・ベクトル積とベクトル同士の演算(BLAS Level-1)が占めます。
表3-1-1と表3-1-2にGCCの付属ツールであるgprofで測定したプロファイル結果を示します。
表3-1-1のmatrixモードでは行列・ベクトル積が71%(30.1秒)、ベクトル演算が27%(11.2秒)を占め、 表3-1-2のnomatrixモードでは行列・ベクトル積が85%(68.5秒)、ベクトル演算が14%(11.6秒)を占めます。
matrixモードはnomatrixモードに比べて行列・ベクトル積の計算時間が半分以下になるために、 行列・ベクトル積の比率が下がります。


表3-1-1 gprofの出力(matrixモード, 1スレッド)
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 24.76     10.44    10.44     1003     0.01     0.01  prodmvEx
 24.28     20.68    10.24     1003     0.01     0.01  prodmvEz
 22.39     30.12     9.44     1003     0.01     0.01  prodmvEy
  7.49     33.28     3.16     1001     0.00     0.00  Zaxbycz
  4.79     35.30     2.02     1002     0.00     0.00  Zdotc
  4.60     37.24     1.94     1002     0.00     0.00  Zdotu
  3.98     38.92     1.68     1003     0.00     0.00  Zaxpy
  3.94     40.58     1.66     1005     0.00     0.00  Zcopy
  1.85     41.36     0.78      508     0.00     0.00  Dznrm2


表3-1-2 gprofの出力(nomatrixモード, 1スレッド)
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 28.44     22.98    22.98     1004     0.02     0.02  matrixEx
 28.30     45.85    22.87     1004     0.02     0.02  matrixEz
 28.05     68.52    22.67     1004     0.02     0.02  matrixEy
  3.79     71.58     3.06     1001     0.00     0.00  Zaxbycz
  2.55     73.64     2.06     1005     0.00     0.00  Zcopy
  2.55     75.70     2.06     1003     0.00     0.00  Zaxpy
  2.45     77.68     1.98     1002     0.00     0.00  Zdotu
  2.08     79.36     1.68     1002     0.00     0.00  Zdotc
  0.94     80.12     0.76      508     0.00     0.00  Dznrm2