回顧
昨年、私はマルチスレッド方式による並列Lisp実装を試みていました。動作はするようになったものの、期待した並列性能が出ませんでした。スレッドプーリングの手法など効率化を試みたのですがうまくいきません。とうとう私は断念していました。CPUのL３キャッシュの問題ではないのか？という仮説を立てました。L3キャッシュは各コアCPUで共用されています。これのキャッシュミスではないかという仮説です。
再考
今年になりマルチプロセス方式で並列Lisp実装に挑戦しました。これはうまくいきました。２つのコアCPUに計算を分割することによりおおむね処理時間が2分の１に短縮されたのです。この結果をうけて私は以前の仮説が間違いであること思うようになりました。なぜならL3キャッシュの問題であればマルチプロセス方式でも同様に並列の効果がでないはずです。
ラズパイ400
不思議なことにラズパイ400ではマルチスレッド方式でも並列の効果が表れていたのです。ところがデスクトップパソコンで利用されているインテルやAMD製のCPUでは並列の方が遅いのです。ラズパイ400はインテルなどのCPUの10分の１程度の速度しかありません。ひょっとしたら遅いために競合が起きにくくなっているからではないのか？と考えなおしました。インテル、AMDのCPUは高速です競合が頻繁に起きているように思えました。
実証
この疑問を晴らすために自作のEasy-ISLispのマルチスレッドの実装を見直しました。多くの部分はスレッドセーフにしたのですが、ヒープ領域からセルを切り出してくる部分がスレッドセーフにはなっていませんでした。競合を回避するためにロック・アンロックをかけていました。ヒープ領域を分割し空リストを保持する自由リストをスレッドごとに独立させる方式を考えました。
部分的な計算実験
セルを取り出している関数はfreshcell()という関数なのですが、リスト処理、計算など多くの関数がこの処理に依存しています。全部を書き換えるのはたいへんです。次の並列によりフィボナッチ数を計算するコードに絞って調べてみました。
;;----------- multi-thread-----------------
(defun fib1 (n)
(mt-let ((a (fib (- n 1)))
(b (fib (- n 2))))
(+ a b)))
(defun fib (n)
(the <fixnum> n)
(cond ((= n 0) 0)
((= n 1) 1)
(t (+ (fib (- n 1)) (fib (- n 2))))))
Easy-ISLispでは小整数は即値になっておりセルを消費しません。フィボナッチの計算においてセルを消費しているのはapply関数で使用されるevlis関数であることが判明しました。ここでセルを消費しています。
int evlis(int addr, int th)
{
arg_push(addr, th);
top_flag = false;
if (IS_NIL(addr)) {
arg_pop(th);
return (addr);
} else {
int car_addr, cdr_addr;
car_addr = eval(car(addr), th);
arg_push(car_addr, th);
cdr_addr = evlis(cdr(addr), th);
car_addr = arg_pop(th);
(void) arg_pop(th);
return (tcons(car_addr, cdr_addr, th));
}
}
そこでこの部分をスレッドセーフなtcons関数に置き換えてみました。
インタプリタでの実行
LinuxMINTのマシンで計算させました。AMDのRyzenが搭載されています。6コアです。これを２つのワーカースレッドで起動させてフィボナッチ数を計算させました。結果は下記のようです。
どうやらこんどの仮説は正しいようです。並列の方が高速になっています。
改良
ようやく原因が判明しました。原因がわかってしまえば改良は時間の問題です。コンパイラも含めてマルチスレッドでの実装を書き直しています。東北大学の伊藤教授の論文を読んで並列Lispに取り組みました。1年ほど試行錯誤してようやく深い理解に達したようです。