使用多執行緒提高並行性#
同步的代價#
我們研究對一列整數 $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())
}
我們在一個四核系統上，對一個大小為 $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)
}
我們在一個四核系統上，對一個大小為 $n=2^{31}$ 的序列進行測試，運算時間以秒為單位，結果如下：
| | | | | |
-- | -- | -- | -- | -- | -- | --
執行緒數 | 1 | 2 | 4 | 8 | 16 | 32
時間 | 22.413 | 11.430 | 6.087 | 7.414 | 7.428 | 7.411
結果基本符合預期，得到一組遞減的運行時間。
刻畫並行程序的性能#
如圖，我們看到，隨著執行緒數的增加，運行時間下降，直到增加到四個執行緒，此時，運行時間趨於平穩，甚至開始有點增加。在理想的情況中，我們會期望運行時間隨著核數的增加線性下降。也就是說，我們會期望執行緒數每增加一倍，運行時間就下降一半。確實是這樣，直到到達 $t > 4$ 的時候，此時四個核中的每一個都忙於運行至少一個執行緒。隨著執行緒數量的增加，運行時間實際上增加了一點兒，這是由於在一個核上多個執行緒上下文切換的開銷。由於這個原因，並行程序常常被寫為每個核上只運行一個執行緒。
雖然絕對運行時間是衡量程序性能的終極標準，但是還是有一些有用的相對衡量標準能夠說明並行程序有多好的利用了潛在的並行性。並行程序的加速比通常定義為： $p$ 是處理器核的數量， $T_k$ 是在 $k$ 個核上的運行時間。這個公式有時被稱為強擴展（strong scaling）。當 $T_1$ 是程序順序執行版本的執行時間時， $S_p$ 稱為絕對加速比（absolute speedup）。絕對加速比比相對加速比能更真實地衡量並行的好處。即使是當並行程序在一個處理器上運行時，也常常會受到同步開銷的影響，而這些開銷會人為地增加相對加速比的數值，因為它們增加了分子的大小。另一方面，絕對加速比比相對加速比更難以測量，因為測量絕對加速比需要程序的兩種不同的版本。對於複雜的並行代碼，創建一個獨立的順序版本可能不太實際，或者因為代碼太複雜，或者因為源代碼不可得。
一種相關的測量量稱為效率（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\%$