Erlangで並列フィボナッチ数計算 - シリコンの谷のゾンビ

プログラミング言語のベンチマークと言えばフィボナッチ数計算．
Erlangといえば，並列フィボナッチ計算．
というわけでプログラミング言語Erlang入門に書いてあった並列フィボナッチ数計算を参考にして，プロセスを2つ以上に増やしたフィボナッチ数計算を書いてみた．

コードはこんな感じ．

-module(cfib).
-compile(export_alL).

%% fib
fib (1) -> 1;
fib (2) -> 1;
fib (X) when X > 2 -> fib(X - 1) + fib(X - 2).


%% cfib
fib (1, P) -> P ! 1;
fib (2, P) -> P ! 2;
fib (X, P) when X > 2 -> P ! fib(X - 1) + fib(X - 2).


cfib (X, N) ->
    cfib(X, self(), N),
    receive
       Res -> Res
    end.

cfib (X, P, N) ->
    if
       X > N ->
               S = self(),
               spawn(cfib, cfib, [X - 1, S, N]),
               spawn(cfib, cfib, [X - 2, S, N]),
               P ! wait_for_reply([], 0);
       true ->
               P ! fib(X - 1) + fib(X - 2)
    end.

wait_for_reply (L, 2) -> lists:sum(L);
wait_for_reply (L, N) ->
    receive
       Res -> L2 = lists:append(L, [Res]),
                    wait_for_reply(L2, N + 1)
    end.

fib/1は普通にフィボナッチ数を計算する．
fib/2はcfib用ロジック．親プロセスに計算結果を返す．
cfib(X,N)は，Nより大きいフィボナッチ数は2プロセスに分割し，N以下のフィボナッチ数は1プロセスで計算するというロジック．

cfib(X,P,N)のPは値を集めるための親プロセス番号なので，以下Pを省略して解説をする．

cfib(6,3)が呼ばれると，6は3よりも大きいので，cfib(5,3)とcfib(4,3)をspawnする．
1. cfib(5,3)が呼ばれ，cfib(4,3)とcfib(3,3)をspawnする
2. cfib(4,3)が呼ばれ，cfib(3,3)とcfib(2,3)をspawnする
．．．

という感じにプロセスを増やしていく．
呼び出しの様子をまとめると下記のようになる．

cfib(6,3)
=  #1( cfib(5,3) ) + #2( cfib(4, 3) )

=  #3( cfib(4,3) ) + #4( cfib(3, 3) )
 + #5( cfib(3,3) ) + #6( cfib(2, 3) )

=  #3( fib(3) + fib(2) ) + #4( fib(2) + fib(1) )
 + #5( fib(2) + fib(1) ) + #6( fib(1) + fib(0) )

括弧の前の#は，子プロセス番号を意味している．

このようにNの値を変更することによって合計Σ_{i = 1}^{X - N} 2^(i - 1)数のプロセスが生成される．

ベンチマーク

プロセス数をどれだけ増やせばいいのかというのはアーキテクチャによって異なるし，ベストの解はわからないのでベンチマークを取るべきだ，みたいなことをArmstrong先生がおっしゃっていたような気がするので，ベンチマークを取ることにする．

テストに用いたコードはこんな感じ．
X=35固定で，Nの値を変化させた計算を10回試行して平均を取った．
10回試行して平均を取る，という計算をもう少しスマートに書けないのかなぁ．

Pythoのrangeを使ったforループのような書き方がしたかったので，Linuxのseqコマンドと同じような働きをするseq/1関数を用意．(seqとPythonのrangeは微妙に挙動が違う)

test2() ->
    FibNum   = 35,
    TrialNum = 10,
    L = lists:reverse( seq(FibNum - 26, 27) ),
    TimeLis = lists:map(fun (N) ->
                                TmpLis = lists:map(fun (_) ->
                                                           {T, _} = timer:tc(cfib, cfib, [FibNum, N]),
                                                           T
                                                   end, seq(1, TrialNum)),
                                lists:sum(TmpLis) / TrialNum
                        end,
                        L),

    lists:map(fun ({N, T}) ->
                      io:format("~p: ~p usec~n", [N, T])
              end,
              lists:zip(L, TimeLis)).

%% seq function
seq (_From, 0) -> [];
seq (From, Num) when is_integer(From), is_integer(Num) ->
    [From | seq(From + 1, Num - 1)].

よくわかっていないけれど，スケジューラ数によっても数字が変わるのかもチェックすることにする．

マシンスペック

Debian 5.0
Intel Core2Duo E8500 (3.16GHz)
4GBメモリ (3GBちょっとしか認識されていない模様)

結果

スケジューラ数: 2 (コア数)

% erl -smp +P 500000
1> c(cfib).
2> cfib:test2()
35: 790622.6 usec
34: 521177.9 usec
33: 436207.4 usec
32: 448118.4 usec
31: 432095.7 usec
30: 422019.2 usec
29: 442529.7 usec
28: 444034.1 usec
27: 441167.8 usec
26: 409905.8 usec
25: 403646.0 usec
24: 432257.2 usec
23: 424571.4 usec
22: 459982.9 usec
21: 464582.3 usec
20: 463015.7 usec
19: 461612.3 usec
18: 461607.8 usec
17: 458722.1 usec
16: 487093.8 usec
15: 538136.3 usec
14: 591087.3 usec
13: 704761.5 usec
12: 883533.8 usec
11: 1170538.1 usec
10: 1692506.1 usec
9: 2553182.9 usec

スケジューラ数: 4

% erl -smp +S 4 +P 500000
1> c(cfib).
2> cfib:test2()
35: 795083.8 usec
34: 494873.1 usec
33: 436717.6 usec
32: 419877.5 usec
31: 407839.5 usec
30: 401915.3 usec
29: 400281.9 usec
28: 400581.6 usec
27: 399481.6 usec
26: 402835.7 usec
25: 402030.7 usec
24: 404313.6 usec
23: 408603.2 usec
22: 407382.0 usec
21: 411396.0 usec
20: 418257.5 usec
19: 428285.6 usec
18: 452891.1 usec
17: 470644.4 usec
16: 521761.4 usec
15: 619131.3 usec
14: 807613.9 usec
13: 1091652.0 usec
12: 1471593.5 usec
11: 2109116.3 usec
10: 2803975.1 usec
9: 4207485.4 usec

スケジューラ数: 8

% erl -smp +S 8 +P 500000
1> c(cfib).
2> cfib:test2()
35: 790895.7 usec
34: 497966.7 usec
33: 457857.4 usec
32: 434896.5 usec
31: 413279.9 usec
30: 406419.1 usec
29: 404339.6 usec
28: 400024.3 usec
27: 399958.0 usec
26: 399955.2 usec
25: 399838.2 usec
24: 400167.0 usec
23: 402148.0 usec
22: 402234.2 usec
21: 403597.6 usec
20: 416372.9 usec
19: 426337.0 usec
18: 427474.6 usec
17: 441139.6 usec
16: 476898.7 usec
15: 577075.4 usec
14: 654459.0 usec
13: 904409.9 usec
12: 1124672.3 usec
11: 1614105.2 usec
10: 2430266.0 usec
9: 3678832.3 usec

プロセス数

各Nにおけるプロセス数は以下のとおり．

35: 1
34: 3
33: 7
32: 15
31: 31
30: 63
29: 127
28: 255
27: 511
26: 1023
25: 2047
24: 4095
23: 8191
22: 16383
21: 32767
20: 65535
19: 131071
18: 262143
17: 524287
16: 1048575
15: 2097151
14: 4194303
13: 8388607
12: 16777215
11: 33554431
10: 67108863
9: 134217727