0-1ナップザック問題を並列化する

アルゴリズム C

0-1ナップザック問題のDPのデータフローの図[1]を見ていたら、計算機実験[2]の時にやった並列化が適用出来そうだなあと思ったので実装してみました。


並列化の方法としては、DPの配列R[品物][容量]に対して大きく
(1)列を各スレッドで分割
(2)行を各スレッドで分割
(3)行列をブロックに分割
の3つに分けられます。


(1)は1つの列(容量)を複数のスレッドで分担して、1行ずつ同期をとって処理をしていきます。
同じ行内ではデータの依存関係がないので1行につき1回の同期を取るだけでいいので楽です。


(2)は行(品物)ごとにスレッドで分割するのですが、行同士は依存関係があります。
具体的には、R[i][j]がR[i-1][j]とR[i-1][j-W[i] ] (W[i]は品物iの重量)の結果を利用しますので、
R[i][j]を計算するには最低でもR[i-1][j]までの計算が完了していることが必要になります。
そのため、(1)に比べるとやや複雑な同期処理が必要になります。


(3)は(1)と(2)の併用です。
M×N行列を小さなブロックm×nに分割して計算します。
局所性を高めるために使うこともありますが、今回の例ではあまり使わなさそうです。




というわけで今回は普通のDP、(1)の並列化、(2)の並列化をそれぞれ実装してみました。
ソースはこの辺に置いてあります。直列がn2.c、(1)がn4.c、(2)がn3.cです。ただの再帰はn1.cですが、まあ遅くて使いものにならないです。
http://github.com/osa9/knapsack


ベンチは複数のパターンで検証するべきでしょうが、面倒なので品物=10000、容量=10000の巨大なケース×3で試してみました。
それでも計算量はO(品物*容量)なので数秒で終わってしまいますね。


微妙な差異もあるので、それぞれ5回ずつ実行し、その中で最も速かった実行時間を成績としました。
コンパイラはgcc4.0.1で、コンパイルオプションは -O2 です(並列はpthreadを使っているので-pthreadも)
実行環境はMacBookPro : Core2 Duo 2.26GHzです。


普通のDP : 3.256390s
(1) 1.890291s (2スレッド) 58%
(2) 1.980377s (2スレッド) 61%


今回は行と列のサイズが同じだったので、同期処理のやや少ない(1)が勝っていますね。
2コアなので限界はおよそ50%ですが、スレッドの生成コストなどを考慮するとまあまあじゃないでしょうか。




参考：
[1]ナップザック問題 Knapsack Problem
http://algorithms.blog55.fc2.com/blog-entry-85.html

[2]le4 parallel programming
http://www.yuasa.kuis.kyoto-u.ac.jp/~yasugi/4/top.html