並列化

能書き

CPUの処理速度は既に飽和が近づいています。 そこで近年注目されているのが、多数のCPUを同時に使う「並列化」という手法です。
しかしながら、単純に「２つ使えば２倍速くなる」というものではなく、CPU性能を活かすにはそれなりの知識が必要となります。
ここでは並列化の基本を紹介します。

いろいろな並列化

並列化は、どのレベルで並列化するかによって次の３種類に分けることができる。
それぞれ性質や注意点が異なるので、混同しないこと。

  1. データ並列化（ベクトル計算機、単一コア、「SIMD」）
    複数のデータ（配列）を１つの命令で扱う技術。
    広い意味では並列化の一種だが、「ベクトル化」と呼ばれて区別されることが多い。
    特徴：余剰リソースを有効に使える
    ただし倍精度複素数を扱う場合、恩恵はほとんど受けられない。
    使う場面：我々が意識して使うことは少ない
    CPUとコンパイラの問題。Intel Fortranなら自動でやってくれる。
  2. 命令並列化（マルチスレッド、単一ノード、メモリ共有型、「OpenMP」）
    最近流行の、マルチコアを利用して複数の命令を同時に実行する技術。
    このテキストで扱う。
    特徴：速くなる
    使う場面：時間のかかるプログラム向け
  3. プロセス並列化（マルチプロセス、単一クラスター、メモリ分散型、「MPI」）
    複数のノードを共同で働かせる技術。主にスパコンで使われる。
    ノード間の通信を明示する必要があり、 時にはアルゴリズムから再考を迫られる本気の並列化。
    特徴：メモリを大量に使える・速くなる
    使う場面：大規模計算向け

１は基本的にコンパイラ任せなので気にしなくて良い。
３はコストパフォーマンスが悪い（リソース要求量が多く、プログラミングの手間もかかる）ため、 使用する際は、２を組み合わせた方が効率が良くなることが多い。
OpenMPを使ってみよう

能書き

最近は１つのCPU内にいくつものコアがあるのが普通になりました。 ここでは、複数のコアを１つのプログラムで同時に使うための枠組み「OpenMP」を学びます。
OpenMPというのはFortranの拡張機能とでも理解しておけばよいでしょう。 並列化したい部分に「OpenMPの命令」を付け加えるだけで並列化でき、 非並列環境と同じプログラムを使えるなど、扱いやすいように工夫がされています。
OpenMPの命令は『!$』で始まるため、 OpenMPが使えない環境ではただのコメント扱いとなります。
「並列化に挑戦したい」と考えるレベルの人なら、すぐに使いこなせるようになるでしょう。

とりあえず並列化してみよう

 program parallelTest
 !$ use omp_lib

 !$OMP parallel
 print *, "Hello, world!"
 !$OMP end parallel
 
 end program
これが並列プログラムです。『!$』をただのコメントと扱えば、普通のHello worldですね。
これを 
 コンパイルオプション　-openmp
付きでコンパイルします。 
$ ifort -openmp test.f90
さらに、実行時に並列数を指定する環境変数(OMP_NUM_THREADS)をセットします。 
$ env OMP_NUM_THREADS=4 ./a.out
実行結果が下のようになれば成功です。（CPU数が4つの場合） 
 Hello, world!
 Hello, world!
 Hello, world!
 Hello, world!
これが、Hello worldを並列実行した結果です。 並列化がどういうものか感覚的につかめたでしょうか。 「１つの命令を４つのCPUで実行する」のではなく、「（コピーされた）４つの命令を４つのCPUが同時に実行する」というのがOpenMPの「命令並列化」です。

もう一つ、例を出します。 
 program parallelTest
 !$ use omp_lib
 integer :: n
 
 n = 0
 !$OMP parallel
 n = n+1
 !$OMP end parallel
 print *, "n = ",n
 
 end program
結果は、次のようになります。（CPU数が4つの場合） 
 n =       4
『n+1』という計算が４倍速で実行されるのではなく、４倍（４回）実行されるため、このような結果になります。

ここで学んで欲しいこと： 
 ただ並列化しただけでは速くならない（むしろ遅くなる）
 下手に並列化したら結果が変わってしまうこともある
この基本的な性質を心に刻み込んでから、次の基礎理論をよく読んで下さい。
命令並列化（OpenMP）基礎理論

命令並列化の基本概念

まず命令並列化を行う目的は、 
 １つのプログラムの実行時間を短くする
ことです。プロセス並列化(MPI)と違い、使えるメモリが増えて大規模計算が可能になったりはしません。
時間の掛かりすぎる計算を現実的な時間で終わらせることは可能です。
ところが上で見たように、ただ単に「並列化」をしただけでは速くもなりません。
具体的には、 
プログラムを適切に分割し、複数のCPUに割り当てる
ことで高速化を図ります。
例えば４つの命令(inst1,2,3,4)からなるプログラムを例にとると、

・並列化していない場合（通常） 
 time ->  1       2       3       4
 CPU1: [inst1] [inst2] [inst3] [inst4]
 CPU2: (sleep) (sleep) (sleep) (sleep)
 CPU3: (sleep) (sleep) (sleep) (sleep)
 CPU4: (sleep) (sleep) (sleep) (sleep)
１つのCPUが４つの命令"[inst1]-[inst4]"を実行している間、他の３つのCPUは遊んでいる(sleep)状態になります。

・並列化した場合 
 time:    1
 CPU1: [inst1]
 CPU2: [inst2]
 CPU3: [inst3]
 CPU4: [inst4]
４つのCPUにそれぞれ別の命令を割り当てることで、実行時間を短縮することができます。

並列化の方法

実際にプログラムを分割するのは容易な事ではありません。
まず、並列化するためには 
 命令の順序が可換であること
が大前提となります。
例えばinst1の結果を使ってinst2を実行する、といった場合、 inst1が終わる前にinst2を実行することができないため、並列化不能です。
また、詳しい話は後回しにしますが、プログラム中で最も時間がかかる部分を並列化しないと意味がありません。

以上の条件を踏まえ、実用的側面から考えると 
 実行順序に依存しない大きなループの分割
が現実的な並列化の方法ということになります。
「ループ分割」のことを狭義の「並列化」と呼ぶ場合もあります。

並列化（ループ分割）できない場合

上でも行ったように、命令は可換、すなわち同時に実行した時、常に正しい結果を与える必要があります。
具体的には、一つ前の計算結果が必要な漸化式のようなものは並列化できません。 
 m(0) = 1
 do i=1,10
    m(i) = m(i-1)+i   ! ループ内で依存関係があるので並列化不可能
 end do

では、次の場合はどうでしょうか。 
 m(0:10) = 1
 do j=1,10
    do i=1,10
       m(i) = m(i) + j*m(i-1)
    end do
 end do
最初の例と同じく、これは並列化できません。ところが、ループの順番を入れ替えてやると、 
 m(0:10) = 1
 do i=1,10
    do j=1,10
       m(i) = m(i) + j*m(i-1)   ! jに関しては依存関係がない
    end do
 end do
内側の『j』のループのみが並列化できるようになります。
このように、
アルゴリズムを変更することで並列化できるようになる場合がある
ことを覚えておきましょう。

OpenMPの役割

例えば20回のループを２つのCPUに割り振って、同時に実行させれば半分の時間で済むことになるわけです。
CPU1への命令 
! ループの前半部分
 do i=1,10
    m(i) = func(i)
 end do
CPU2への命令 
! ループの後半部分
 do i=11,20
    m(i) = func(i)
 end do

「CPUごとに違う命令を出すなんてどうするの！？」という人のために、OpenMPがあります。
OpenMPの実用的な役割は、 
 ループを自動分割し、各CPUに割り振る
ことです。
基礎理論

スレッド

「スレッド」というのはプログラムの実行単位のことです。 一般的には、1つのスレッドが1つのCPUに割り当てられます。
つまり「スレッド」の数を増やすと、それだけ多くのCPUを使えるようになります。

上で議論したように、プログラムを複数のスレッドに分けるには厳しい条件があるため、１つのプログラム中で適切なスレッド数は変動します。
・並列化されたプログラムの実行イメージ例 
 time:    1          2          3          4
 TRD1: [inst1]─┬─[inst2.1]─┬─[inst3]─┬─[inst4.1]─┬─ . . .
 TRD2:         ├─[inst2.2]─┤         └─[inst4.2]─┘ 
 TRD3:         ├─[inst2.3]─┤                
 TRD4:         └─[inst2.4]─┘
赤く示した分岐点ではOpenMPによる特殊な命令が実行されており、時間のロス（オーバーヘッド）が生じます。

メモリの扱い

OpenMPは「メモリ共有型」です。
基本的には全てのスレッドは同一のメモリにアクセスし、データを共有します。そのため、データの分割や通信に特に気を配る必要はありません。
ただし、きちんと理解せずに使うのは危険なので理解はしておきましょう。
例えば、 
 do i=1,10
    tmp = i**2
    a(i) = tmp
 end do
ここで出てくる変数は、「i,a,tmp」です。
『a』は全てのスレッドが同じもの（ただしインデックスが違う）を使うので、特に気を配る必要はありません。
が、『i』と『tmp』を同じものにしてしまうと、複数のスレッドが同時に同じ変数を書き換えてしまい、結果がめちゃくちゃになります。
このように、スレッドごとに独立に扱って欲しい変数がある場合は、明示的に指定する必要があります。
ただし分割ループ変数は例外で、『OMP DO』が自動的にスレッドごとに別々の変数として扱ってくれます。
詳しい指定の方法は後ほど。