改良

前回のお話でマルチコアで並列計算、たらいまわし計算をした話をしました。並列にした方が高速化と思いきや、逆に遅いのでした。どうして？？？　スレッドープーリング、やってみた？というコメントをいただきました。それは何？とChatGPTに聞いてみるとなんとか実装できそうです。スレッドプーリングを実装しました。

スレッドプーリングとは

pthreadライブラリを利用してスレッドを立ち上げるには時間がかかります。スレッドが終了したときにメモリを解放するのにも時間がかかります。そこで予めスレッドを立ち上げておいて待機させておきます。並列計算が必要になったら計算を開始させます。計算が終わったらまた待機させます。

スレッドはキューで待機させます。

pthreadライブラリのpthread_cond_wait を使ってスレッドを待機させキューに保存しておきます。pcallなど並列計算を開始した場合にはその待機を解除しevalを開始します。evalが終わったらmainスレッドにsignalを使って計算が終わったことを通知します。

このようにスレッドは最初から立ち上がっていますから、並列計算を頻繁に繰り返す場合にもタイムロスが生じません。

ガベージコレクションがなかなかたいへん

ガベージコレクションはコンカレント・マーク＆スイープとしています。もっともスイープの部分はコンカレントにはできなかったので部分的にしかコンカレントにできていません。GC用にも起動時にスレッドを確保しておきます。空きセル数が一定数を下回るとこのスレッドが計算開始します。それまではメインスレッドから待機命令が送られて待機しています。

たらい回し計算の場合には3つのワーカースレッドが計算をします。計算途中で空きセルが不足してきたらGCスレッドにGCの待機解除を通知します。GCはConcurrentモードに入ったことを大域変数で知らせます。ストップフェーズに入った場合には大域変数でstopモードに入ったことを知らせます。

ワーカーはそれぞれセルを供給する関数を持っています。ストップ状態に入ったときにはセルの供給を一時的にストップします。これによりeval計算は一時的に停止します。その間を縫ってGCスレッドはガベージコレクションを行います。逐次処理の場合と異なりGCが起動するタイミングは予想できません。eval計算の途中でもGCが突如、計算開始することもあります。ここがなかなか悩ましいところでした。生成されたセルを保護してゴミ処理に回らないように工夫をしています。

計測

さて。これで並列でたらいまわし計算をすることができるようになりました。インタプリタ、コンパイラで計測してみましょう。

計測はWSL2でicore5の6コアの３０００MHｚマシンで行いました。

コード


(defun ptarai (x y z)
    ;(the <fixnum> x)(the <fixnum> y)(the <fixnum> z)
    (if (<= x y)
        y
        (pcall ptarai (ptarai (- x 1) y z)
                      (ptarai (- y 1) z x)
                      (ptarai (- z 1) x y))))

(defun tarai (x y z)
    ;(the <fixnum> x)(the <fixnum> y)(the <fixnum> z)
    (if (<= x y)
        y
        (tarai (tarai (- x 1) y z)
               (tarai (- y 1) z x)
               (tarai (- z 1) x y))))

インタプリタ

Easy-ISLisp Ver3.33
> (load "./tests/para.lsp")
T
> (time (ptarai 12 6 0))
Elapsed Time(second)=24.491938
<undef>
> (time (tarai 12 6 0))
Elapsed Time(second)=16.057213
<undef>
>

コンパイラ

> (load "./tests/para.o")
T
> (time (ptarai 12 6 0))
Elapsed Time(second)=0.824204
<undef>
> (time (tarai 12 6 0))
Elapsed Time(second)=0.526622
<undef>
>

最適化コンパイル

> (load "./tests/para.o")
T
> (time (ptarai 12 6 0))
Elapsed Time(second)=0.015585
<undef>
> (time (tarai 12 6 0))
Elapsed Time(second)=0.020543
<undef>
>

スレッドプーリングの工夫をしたものの、やはり並列のたらいまわし計算の方が遅いのでした。

なぜ？

楽しく計算実験を繰り返しております。

実装はここにあります。