すごく久しぶりだけども

だいぶ遅くなりましたが、あけましておめでとうございます。
長年ほったらかしにしていた当ブログも、せめて備忘録として活躍させるべく、またちまちま書いていきたいと思います。

並行計算について下調べ中

CSPやらアクターモデルやらペトリネットやらを下調べ中……のはずだったのに、気がついたらErlangを触っていた。
Erlangは、基本的にはシンプルな関数型言語っぽい。ただし（Prologの影響を受けているからなのか）ドット・セミコロン・カンマの使い分けが独特で、若干混乱ポイントになっている。流れるように->で処理を記述していけるのは気持ちいい。プロセスっていう概念も楽しい。

リングベンチマークも簡単に書けて、一発で動いた。（N個のプロセスでメッセージをM周させる課題）

やっぱりプログラムのバグを減らすのに最も有効なのは、状態の変化をできるだけ排除することのような気がする。Erlangの実績が示すように、静的な型システムは本質的な所では無いんじゃなかろうか。*1

ソースコード

まだ慣れてないのもあって、あんまりきれいに書けている感じはしない。

-module(ringbench).
-export([start/3, ringloop/1]).
%-compile(export_all).

make_process(P0, 1) -> spawn(?MODULE, ringloop, [P0]);
make_process(P0, N) when N > 1 ->
    NextPid = make_process(P0, N - 1),
	spawn(?MODULE, ringloop, [NextPid]).

ringloop(NextPid) ->
    receive
        stop -> NextPid ! stop;
        {msg, Num, Text} -> NextPid ! {msg, Num, Text},
                            ringloop(NextPid);
        _ -> io:format("illegal message received~n")
    end.

start(M, N, Msg) ->
    NextPid = make_process(self(), N),
        NextPid ! {msg, 1, Msg},
        loop(NextPid, M).

loop(Next, M) ->
    receive
        stop -> stop;
        {msg, Num, Text} when Num == M ->
            io:format("Msg ~p received.~nloop finished.~n", [Text]),
            Next ! stop,
            loop(Next, M);
        {msg, Num, Text} ->
            Next ! {msg, Num + 1, Text},
            loop(Next, M);
        _ -> io:format("illegal message received~n")
    end.

参考書籍

プログラミングErlang

Erlangプログラミング

下調べ中

協調型計算システム―分散型ソフトウェアの技法と道具立て

ホーアCSPモデルの理論

*1:Erlangは動的型付け言語

Intel Threading Building Blocksを使ってみる

Linuxのお勉強をVMWare上のUbuntsu 10.04でやっている。最近、C++でマルチスレッドもできるようになりたいなーということもあって、Intel TBB(Threading Building Blocks)をインストールした。

そんなに難しい作業ではないはずなのだが、Linuxのディレクトリ構成とか環境変数とかに無知なのでちょっと苦戦した。結局はぐぐって出たページを参考にしてそれをそのまま使わせてもらった。偉大な先人たちに感謝。

どれぐらい有効か

高速化のためのマルチスレッドプログラミングの経験はほとんどないので、TBBは具体的にどれぐらい有効なのか、全然想像もつかない。そこで何か簡単なコードを書いてみて検証しようとした。お題としては、そこそこコードが小さく済み、並列化が有効だと考えられるものということで、台形公式の実装を試みた。

でもよく考えたら、それ以前にC++をほとんど使ったことがなかった！！ ので、参考書を引っ張り出して見よう見まねで書いた。C++のコードとしては微妙な出来になったかも。

#include <tbb/task_scheduler_init.h>
#include <tbb/parallel_reduce.h>
#include <tbb/blocked_range.h>
#include <tbb/tick_count.h>

#include <cmath>
#include <iostream>

using namespace tbb;
using namespace std;

struct SumTranpezoid {
  double x, y;
  double h;
  double sum;

  inline double f(double x) { return 0.01 * x * fabs(sin(x)); }

  void operator()(const blocked_range<size_t>& range) {
    for (size_t i = range.begin(); i != range.end(); ++i) {
      sum += h * (f(x + h*(i - 1)) + f(x + h*i)) / 2;
    }
  }

  void join(const SumTranpezoid& t) { sum += t.sum; }

  SumTranpezoid(SumTranpezoid& t, split) : x(t.x), y(t.y), sum(0), h(t.h) {}

  SumTranpezoid(double x0, double y0, size_t n) : sum(0) {
    x = x0; y = y0;
    h = (y - x) / n;
  }
};

double parallel_tr(int x, int y, size_t n) {
  task_scheduler_init init;
  SumTranpezoid tr = SumTranpezoid(x, y, n);
  parallel_reduce(blocked_range<size_t>(1, n), tr);
  return tr.sum;
}

inline double f(double x) { return 0.01 * x * fabs(sin(x)); }

double serial_tr(double x, double y, int n) {
  double h = (y - x) / n;
  double sum = 0.0;

  for (int i = 1; i < n; i++) {
    sum += h * (f(x + h*(i - 1)) + f(x + h*i)) / 2;
  }
  return sum;
}

int main() {
  tick_count t0 = tick_count::now();
  cout << serial_tr(0.0, 1000, 30000000) << endl;
  tick_count t1 = tick_count::now();
  cout << parallel_tr(0.0, 1000, 30000000) << endl;
  tick_count t2 = tick_count::now();

  cout << "serial  :" << (t1 - t0).seconds() << endl;
  cout << "parallel:" << (t2 - t1).seconds() << endl;

  return 0;
}

実行結果

手元の2コアの環境で実行したところ、並列化によってだいたい数割ぐらい高速化された。ちなみに関数fが（x * xとか）単純すぎた場合は並列化の効果が出るどころか逆に遅くなった。なんでだろう？そういうものなのだろうか。並列化のオーバーヘッドの方が相対的に大きくなったのか。

思ったほど効いてくれないなあ。あとやっぱり、コアが沢山ないと楽しくない。8コアぐらいのマシンがないと劇的な高速化は望めなさそう。

参考書

Accelerated C++―効率的なプログラミングのための新しい定跡 (C++ In Depth Series)

インテル スレッディング・ビルディング・ブロック ―マルチコア時代のC++並列プログラミング

謎の快挙

先月の公共料金は、特に冷房をガンガンにしていたこともあって非常に高くついた。
あーあ節電しないとな、とか考えながらコンビニに行き、支払おうとした時。

2^13だ！！ ちょっと感動。

ThinkPad欲しいな

欲しいな欲しいなThinkPad。

メモリが6GBぐらいあって、64ビットOSで、SSDを積んであるようなモデルが欲しいな。

本格的なやつを買うのはSandy Bridge世代ということにして、今はあと1年をつなぐネットブック的なものが欲しいな。

というわけで、ThinkPad X100eに目を付けていたのだが、近々新モデルが出るらしいという噂を聞いた。デュアルコア*1で、いくつかの点で追加もあるらしい？

さてさて、新型を買うべきか型落ちを狙うか。それとも我慢できずに買っちゃうか。

*1:時期的に見てAthlon II Neoが？

a la russe法による乗算アルゴリズム

忙しすぎてネタを書く時間がない。しかし時間は作るものらしいので、日々の生活をちょっとずつ切り詰めて余暇を作る。

乗算アルゴリズムの話。もし加算とビットシフトしか無かった場合、いかにして効率良く乗算を行うか？

単純な方法

a * bは、「aをb回足したもの」といえる（話が面倒になるので、a、bは非負整数とする）。そこで、その考えをそのままコードに落としてみる。

int mul(int a, int b) {
    int sum = 0;

    if (0 == b) return 0;

    while (b != 0) {
        sum += a;
        b--;
    }
    return sum;
}

計算量をざっと見積もる。
ループ部分の条件分岐がb+1回、加算がb回、デクリメントがb回。bに比例した計算コストがかかるように思われる。

a la russe法

多くのアーキテクチャでビットシフトは高速に実行できるから、うまくすれば計算量を削減することができる。表題のa la russe法は、ビットシフトを巧妙に使う。

1. a * bを計算するとき、aが偶数であれば、aを半分、bを2倍しても計算結果は変わらない。例えば 4 * 10は(4 / 2) * (10 * 2)すなわち2 * 20と同じ。この半分と二倍という操作がポイントで、2進数を使う多くのコンピュータでは、ビットシフトで実現できる。
2. それではaが奇数の時はどうするか。ひとつ値を「どける」ことでまた偶数にすれば、上述の変形ができる。すなわちa * b = (a - 1) * b + bとする。a - 1は偶数だから、a - 1とbに対して1.のビットシフト操作ができる。

この二つの操作を繰り返すと、いずれaは1となる。その時のbの値と、「どけた」分の値を足すことで乗算結果が得られる。
具体例として、35 * 21をやってみる。

35 * 21 = 17 * 42  + 21
        =  8 * 84  + 42 + 21
        =  4 * 168 + 42 + 21
        =  2 * 336 + 42 + 21
        =  1 * 672 + 42 + 21
        =  672 + 42 + 21
        =  735

Cで実装するなら、こんな感じになるはず。

int mul(int a, int b) {
    int sum = 0;

    if (0 == a) return 0;

    while(a != 1) {
        if (a & 1) sum += b;
        a >>= 1;
        b <<= 1;
    }
    return sum + b;
}

さてさて、この場合の計算量はどれほどだろうか。

ループの終了条件であるは、反復一回ごとに右に1だけシフトされるから、反復回数はおおむねとなるだろう。にを加算する部分の実行回数は、にいくつビットが立った部分があるかによる。平均して1が半分だとすれば、回実行されると予想できる。その他、最初のがゼロ判定と最後の加算がある。

まとめると、条件分岐は回、加算が回、ビットシフトがぐらいだろうか。演算回数が値の対数倍程度に抑えられているから、なるほど効率は良さそうだ。

……合ってるのかな、この考え。実測するべきだろうが、もう眠いので寝る。

昔は政治に興味があったけど

今はもう、情熱が消え失せた。せいぜい時事問題の概要を把握する程度。頑張って図書館にこもり下調べして、自分の政治的意見を持ったとしても、あんまり日常生活では役に立たないことに気づいてしまったのもある。

全体的に無力感。セリグマンが用意したイヌも、こんな気分だったんだろうか？ ……ちょっと違うか。