能書き

並列化すれば速くなる、という簡単なものではありません。
実際に速くなるかどうかはやってみないと分からない部分もありますが、 理屈の上で理解しておくべきことをまとめておきましょう。

並列化の限界

並列化による高速化の限界は理論上、コア数をnとするとn分の1です。当たり前ですね。
ただ、１つのプログラムの中には、並列化できる部分と出来ない部分があります。今、並列化できる部分の（実行時間の）割合をp%、出来ない部分をs%だとしましょう。
これを並列化し、nコアで実行すると、1コアで計算した場合に比べ実行時間は(s+p/n)%になるはずです。
つまり、なるべく「重い」部分を並列化しなければ、あまり御利益はない、ということです。 また、忘れてはいけないのが「n並列はnコアを占有する」ことです。単発の計算ならともかく、パラメータを振ったりする場合は「プログラムをn個同時に走らせるよりも効率的かどうか」で評価しなければなりません。 リソースの無駄遣いにならないように心がけましょう。

並列化の細かいところ

単純な分担以外に、実行速度に関わる要因を挙げておきます。
低速化要因１：スレッド立ち上げ、ループ分割等のオーバーヘッド
　OpenMPが頑張る時間がかかります。１回あたりの時間は微々たるものですが、多重ループの内側を並列化する場合は注意が必要です。
　なるべく外側のループで、大きく並列化すると良いでしょう。

低速化要因２：スレッド待ち時間
　ループを分割した際、早く終わるスレッドと遅れるスレッドが出てきます。この場合、一番遅いスレッドによって実行時間が決まります。
　普段はあまり気にしなくても良いのですが、「最初の行の計算だけが大変」な場合などは気を付けましょう。
　なるべく細かく並列化すると避けることが出来ます。

高速化要因１：メモリ節約
　プログラムをn個同時に走らせると、当然n倍のメモリを消費します。
　OpenMP並列化であればメモリの消費量はほとんど増えないので、メモリ不足による速度低下が軽減できます。
　特に物理メモリを使い切ってしまうような場合には、大きな意味があります。

高速化要因２：キャッシュ利用効率UP
　コア1：行列Aを計算　＋　コア2：行列Bを計算
　とするより、
　コア1：行列Aの半分を計算　と同時に　コア2：行列Aのもう半分を計算
　のち
　コア1：行列Bの半分を計算　と同時に　コア2：行列Bのもう半分を計算
　とした方が速くなります（一般論としては）。
　仕組みは詳しく述べませんが、「同じ（少量の）データをみんなで使う」と効率が上がります。 これも大規模な計算になるほど効いてきます。

高速化要因（番外）：人間の手間節約
　ジョブをn個投げるかわりに、n個分のプログラムを並列化したものを用意（パラメータ並列化）すれば、ジョブは１つ投げるだけで済みます。
　コンピュータにとっては全く無意味であっても、人間的には少しお得です。ただし、並列化に手間がかかるようなら逆効果ですが。
　外部のスパコンを利用する際に使われる裏技でもあります。

並列化できる条件

並列化するためには、計算が「独立な部分に分けられる」ことが大前提となります。 「計算順序の入れ替え」によって結果が変わらなければ、並列化できると覚えておきましょう。 具体的には、漸化式のように「一つ前の計算結果が必要」な場合は並列化できません。
例１）並列化できない場合

 m(1) = 1
 !$OMP parallel
 !$OMP do
 do i=2,10
    m(i) = m(i-1) + 1
 end do
 !$OMP end do
 !$OMP end parallel
 print *, "m = ", m(:)

例２）並列化できる場合。並列化されるのは!$OMP doの直後のループのみ。

 !$OMP parallel
 !$OMP do
 do j=1,10
    m(1,j) = 1
    do i=2,10
       m(i,j) = m(i-1,j) + 1
    end do
 end do
 !$OMP end do
 !$OMP end parallel

ループの順序を入れ替えるなど、アルゴリズムの工夫によって並列化不可能に見えるものも並列化できるようになる場合がある。ただし、当然プログラマの負担は増える。

並列化が適さない場合

例え並列化できても、ほとんど意味をなさない場合もあります。

 time:    1       2       3       4         5       6       7       8       9
 TRD1: [unparallelizable instruction1] [inst2-1] [unparallelizable instruction3]
 TRD2: (sleep) (sleep) (sleep) (sleep) [inst2-2] (sleep) (sleep) (sleep) (sleep)
 TRD3: (sleep) (sleep) (sleep) (sleep) [inst2-3] (sleep) (sleep) (sleep) (sleep)
 TRD4: (sleep) (sleep) (sleep) (sleep) [inst2-4] (sleep) (sleep) (sleep) (sleep)

このように並列部分が少ないと、あまり速くなりません。

最大効率を得られるよう努力する

一般に、並列化すると
　利点：1ジョブ当たりの実行時間が短くなる
　欠点：1CPUあたりの効率が悪くなる
ことが言えます。
（実際には、並列化によって1ジョブ当たりが逆に遅くなる場合もある。実行してみないとわからない。）

・ジョブをたくさん実行したい（もしくは、分割できる）時
　ー＞並列実行「しない」
　（CPUが４つあるなら、ジョブを4つ投げた方が明らかに高効率）
・1つのジョブが重く、1つしか実行できない時
　ー＞最大並列数で実行する
　（遊んでいるCPUを活用できる）
と考えれば良いでしょう。

基準はメモリ使用量です。具体例で言うと、
「1つあたり12GBのメモリを食うプログラム」を「CPU4つ、メモリ32GBのクラスタ」で実行するなら、
「2並列×2ジョブ」が効率を最大化すると期待できます。

結果は正しいか？本当に速くなっているか？

複雑なプログラムを並列化すると、大抵どこかでミスが出ます。（よく見ると依存関係があった・共有すべきでない変数があった、など）
並列化前のプログラムと結果を比較して、必ず確かめましょう。 ただし、計算順序が変わることにより、機械誤差の範囲内で値が変わることは有り得ます。
結果が正しいことが確かめられたら、実行時間を比較してみましょう。「並列化しない方が速かった・・・」ということもしばしばあります。
また、並列数がどれくらいが一番効率良く実行できるかも考えましょう。