pthread で最短路をクエリ並列 その２。

前回では簡易的に pthread によるクエリを並列化した。今回は特にスレッド数だけ作業領域を確保するといった部分を改善し、メモリ消費を減らすことができた。改善に思ったよりも時間がかかってしまったため、単純なことでもマルチスレッドではデバッグが難しいといえる。

次に示すのはグラフデータは USA-road-d.USA.gr で、前回と同じクエリ (point-to-point type を 10 個、逐次版では 21 秒ほどかかる) を解いた。１スレッドの際もスレッド起動等のオーバーヘッドがあるため pthread を用いない時と比べて遅くなってしまうが、スレッド数を２、４、８と増やすにつれて、14.07 秒、8.48 秒、6.76 秒 と改善された。４→８の際にはあまり改善されていないが、スレッド起動のオーバーヘッドが効いてきてしまうのか？逐次版でクエリ１つに対し２秒～３秒ほどかかるのなので各スレッドに１～２つ割り振られるとこれが限界なのか。画像は増加率を表にしたものである。

以下のデータは gettimeofday を用いて計測した。

○環境
CPU : Xeon 2.33 GHz (4 core x 2 CPU)、Memory : 16GByte
option : -O2 -march=nocona

memory　　　　　 time
1　 851.30[MB]　24.8744[s]
2　1044.35[MB]　14.0701[s]
4　1430.46[MB]　 8.4823[s]
8　2202.68[MB]　 6.7580[s]