並列プログラミング

並列プログラミングを始めよう

 

複数コアを持つCPUの計算処理能力をプログラムを通して体験してみる。

 

並列プログラミングは難しそうであるが比較的簡単に書けるプログラミング言語があります。

 

あまり聞かない名前の言語ですがErlangという言語なら簡単に並列プログラミングが書けます。

 

Erlangにおける並列処理

 

特徴1 Erlangのプロセスは他のプロセスからは完全に独立した存在で、メモリを共有することが一切ない。

 

特徴2 プロセス間での情報交換にはメッセージを使用する。

 

 

Erlangにおけるプログラムの実行単位であるプロセスは共有メモリを持ちません。

 

よって共有メモリにアクセスするためのメモリロックの仕組みを必要としません。

 

このため、Erlangでは並列処理を非常にシンプルな形で記述できるようになっています。

 

並列処理を行うために

 

Erlangの一番の特徴である並列プログラミングについて以下の機能を使用します。

 

 ・プロセスを生成するspawn関数

 

 ・メッセージを送信する!演算子

 

 ・メッセージを受信するreceive機能

 

単数プロセスでの演算

 

フィボナッチ数を求める関数を例にして演算にかかる時間を計測します。

 

-module(single).
-export([fib/1,fib/2,sfib/1]).

fib(0) -> 1;
fib(1) -> 1;
fib(X) -> fib(X - 1) + fib(X - 2).

fib(0,P) -> P ! 1;
fib(1,P) -> P ! 1;
fib(X,P) -> P ! fib(X-1) + fib(X-2).

sfib(0) -> 1;
sfib(1) -> 1;
sfib(X) ->
    S = self(),
    spawn(single, fib, [X, S]),
    wait_for_result([], 0).

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

 

Erlangシェルから上記プログラムを実行します。


Eshell V8.3  (abort with ^G)
1> timer:tc(single,sfib,[42]).
{14451454,433494437}
2>

 

出力結果の左側が演算にかかった時間、右側が演算結果になります。

約14.451秒かかっています。

 

複数プロセスでの演算

-module(double).
-export([fib/1,fib/2,dfib/1]).

fib(0) -> 1;
fib(1) -> 1;
fib(X) -> fib(X - 1) + fib(X - 2).

fib(0,P) -> P ! 1;
fib(1,P) -> P ! 1;
fib(X,P) -> P ! fib(X-1) + fib(X-2).

dfib(0) -> 1;
dfib(1) -> 1;
dfib(X) ->
    S = self(),
    spawn(double, fib, [X-1, S]),
    spawn(double, fib, [X-2, S]),
    wait_for_result([], 0).

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

Erlangシェルから上記プログラムを実行します。

 

2> timer:tc(double,dfib,[42]).
{9696254,433494437}
3>

 

約9.696秒かかっています。

 

まとめ

        単数プロセス      複数プロセス

1      14.451454          9.317644

2      14.850858        11.703343

3      14.751691          9.927579

4      14.657374          9.560634

5      14.71481            9.989135

6      14.892589          9.718486

7      14.697935        10.099374

8      14.742849          9.625001

9      15.246751          9.952574

10    14.818206          9.662659

平均 14.7824517        9.9556429

 

単数プロセスと複数プロセスで10回実行し平均を計算したのが上記一覧です。

平均の演算時間を比較すると約32%高速に演算できていることがわかります。

コア数を多く持っているCPUの場合、さらにプロセスを増やして演算を実行することによって

処理時間の短縮ができます。