並列性の向上によるマルチスレッドの使用#
同期のコスト#
私たちは整数の列 $0, ..., n - 1$ の合計を求めることを研究しています。この列を $t$ 個の互いに重ならない領域に分割し、$t$ 個のスレッドにそれぞれ領域を割り当てます。スレッドの合計を変数に格納し、この変数を保護するためにミューテックスロックを使用します。
use std::{
sync::{Arc, Mutex},
thread,
time::Instant,
};
fn main() {
let args = std::env::args().collect::<Vec<String>>();
if args.len() != 3 {
panic!("Usage: {} <nthreads> <log_nelems>", args[0]);
}
let nthreads: usize = args[1].parse().unwrap();
let log_nelems: usize = args[2].parse().unwrap();
let nelems = 1_usize << log_nelems;
let nelems_per_thread = nelems / nthreads;
let gsum = Arc::new(Mutex::new(0));
let now = Instant::now();
let mut handlers = vec![];
for i in 0..nthreads {
let gsum = Arc::clone(&gsum);
let handler = thread::spawn(move || {
let start = i * nelems_per_thread;
let end = start + nelems_per_thread;
for j in start..end {
let mut sum = gsum.lock().unwrap();
*sum += j;
}
});
handlers.push(handler);
}
for handle in handlers {
handle.join().unwrap();
}
assert_eq!(nelems * (nelems - 1) / 2, *gsum.lock().unwrap());
println!("Running took {} s.", now.elapsed().as_secs())
}
私たちは 4 つのコアを持つシステムで、サイズが $n=2^{20}$ のシーケンスに対してテストを行いました。実行時間はミリ秒単位で表され、結果は次のようになります：
| | | | | |
-- | -- | -- | -- | -- | -- | --
スレッド数 | 1 | 2 | 4 | 8 | 16 | 32
時間 | 14932 | 72823 | 76478 | 118155 | 108878 | 101532
結果は理解しづらく、使用するCPUのコア数が増えるほど性能が低下することがわかります。性能の低下の原因は、メモリ更新操作に対するオーバーヘッド、および同期操作のコストが大きすぎるためです（PとV）。これは並列プログラミングの重要な教訓を示しています：同期のコストは非常に高く、できるだけ避ける必要があります。避けられない場合は、このコストを補うためにできるだけ多くの有用な計算を行う必要があります。
ローカル変数の最適化による同期の除去#
したがって、不要なメモリ参照を除去するためにローカル変数を使用し、各対等スレッドがグローバル変数ではなくローカル変数に部分和を累積させるようにします。
use std::{thread, time::Instant};
fn main() {
let args = std::env::args().collect::<Vec<String>>();
if args.len() != 3 {
panic!("Usage: {} <nthreads> <log_nelems>", args[0]);
}
let nthreads: usize = args[1].parse().unwrap();
let log_nelems: usize = args[2].parse().unwrap();
let nelems = 1_usize << log_nelems;
let nelems_per_thread = nelems / nthreads;
let now = Instant::now();
let mut handlers = vec![];
for i in 0..nthreads {
let handler = thread::spawn(move || {
let mut sum = 0;
let start = i * nelems_per_thread;
let end = start + nelems_per_thread;
for j in start..end {
sum += j;
}
sum
});
handlers.push(handler);
}
let mut gsum = 0;
for handle in handlers {
gsum += handle.join().unwrap();
}
assert_eq!(nelems * (nelems - 1) / 2, gsum);
println!("Running took {} s.", now.elapsed().as_micros() as f64 / 1e6)
}
私たちは 4 つのコアを持つシステムで、サイズが $n=2^{31}$ のシーケンスに対してテストを行いました。実行時間は秒単位で表され、結果は次のようになります：
| | | | | |
-- | -- | -- | -- | -- | -- | --
スレッド数 | 1 | 2 | 4 | 8 | 16 | 32
時間 | 22.413 | 11.430 | 6.087 | 7.414 | 7.428 | 7.411
結果はほぼ予想通りであり、減少する実行時間のセットを得ることができました。
並列プログラムの性能の特徴#
上の図からわかるように、スレッド数の増加に伴い、実行時間が減少し、4 つのスレッドに増加すると、実行時間が安定し、少し増加する傾向が見られます。理想的な場合、私たちはコア数の増加に伴い、実行時間が線形に減少することを期待しています。つまり、スレッド数が 2 倍になるごとに、実行時間が半分になることを期待しています。実際には、これは当てはまりますが、 $t > 4$ になると、各コアが少なくとも 1 つのスレッドを実行するため、実行時間がわずかに増加します。これは、1 つのコア上で複数のスレッドのコンテキスト切り替えのオーバーヘッドによるものです。この理由から、並列プログラムは通常、各コアで 1 つのスレッドのみを実行するように書かれます。
絶対実行時間はプログラムの性能を測るための最終的な基準ですが、並列化による利点を示すいくつかの有用な相対的な基準もあります。並列プログラムの加速比は通常次のように定義されます： ここで、 $p$ はプロセッサのコア数、 $T_k$ は $k$ 個のコア上での実行時間です。この式は時には強いスケーリング（strong scaling）と呼ばれます。 $T_1$ が順序実行バージョンの実行時間である場合、 $S_p$ は絶対加速比（absolute speedup）と呼ばれます。絶対加速比は相対加速比よりも並列化の利点をより正確に測ることができます。並列プログラムが 1 つのプロセッサ上で実行されている場合でも、同期のオーバーヘッドの影響を受けることがあり、これらのオーバーヘッドによって相対加速比の値が人為的に増加するためです。一方、絶対加速比は相対加速比よりも測定が難しいです。なぜなら、絶対加速比を測定するにはプログラムの 2 つの異なるバージョンが必要だからです。複雑な並列コードの場合、独立した順序バージョンを作成することは実際的ではないかもしれません。コードが複雑すぎるか、またはソースコードが利用できないためです。
関連するもう 1 つの測定値は効率（efficiency）と呼ばれ、次のように定義されます： 通常、パーセントで表され、範囲は $(0, 100]$ です。効率は並列化によるオーバーヘッドの測定です。効率が高いプログラムは、効率が低いプログラムよりも有用な作業により多くの時間を費やし、同期と通信により少ない時間を費やします。
以下の表は、並列化された合計プログラムの各加速比と効率の測定値を示しています。 $90%$ を超える効率は非常に良いですが、騙されないでください。これほど高い効率を達成できるのは、問題が非常に簡単に並列化できるためです。実際の状況では、これはめったに起こりません。数十年にわたり、並列プログラミングは非常に活発な研究分野でした。商用のマルチコアマシンの登場に伴い、これらのマシンのコア数は数年ごとに倍増し、並列プログラミングは引き続き深く、困難で活発な研究分野となるでしょう。
| | | | | |
-- | -- | -- | -- | -- | -- | --
スレッド（$t$）| $1$ | $2$ | $4$ | $8$ | $16$ | $32$
コア（$p$）| $1$ | $2$ | $4$ | $8$ | $16$ | $32$
実行時間（ $T_p$ ）| $22.413$ | $11.430$ | $6.087$ | $7.414$ | $7.428$ | $7.411$
加速比（ $S_p$ ）| $1$ | $1.96$ | $3.68$ | $3.023$ | $3.017$ | $3.024$
効率（ $E_p$ ）| $100\%$ | $98\%$ | $92\%$ | $76\%$ | $75\%$ | $76\%$