動機

ISLispの生みの親の一人である伊藤貴康先生の論文を読みました。並列マシンの製作、その上で走るPaiLispに興味を持ちました。その論文を参考にしてISLisp規格のEasy-ISLisp（以下「EISL」)に並列構文、pletとpcallを追加、並列Lispで何ができるのだろうか？と試行錯誤しています。

スレッドセーフ

インタプリタをスレッドセーフにするとともに、コンパイラが生成するLispオブジェクトもスレッドセーフにしました。EISLはLispコードをC言語にトランスパイルする方式です。スレッド番号を表す引数thを追加するようにしました。

int f_tarai(int x, int y, int z, int th){
    tarai(x,y,z,th)
}


int tarai(int x, int y, int z, int th){
    コード本体
}

C言語の引数はスレッドセーフですが、動的変数、シンボルや文字列を表すセルはスレッド間で共有していますので、これをスレッド番号ごとに管理するコードを生成するように変更しました。マーク＆スイープのGCスレッドごとに保護すべきセルなどのデータを保持し、スレッドセーフを実現しました。

C言語のPthreadライブラリを利用してスレッドに分割します。これによりマルチコアCPUであればそのスレッドが各コアで実行されるようになります。

並列構文

PaiLispの論文を参考にして次のように記述することとしました。

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

(defun pcount (n)
    (plet ((a (count 1 (div n 2)))
           (b (count (+ (div n 2) 1) n)))
     t))

(defun count (m n)
    (if (= m n)
        t
        (count (+ m 1) n)))

pcallは (pcall fn arg1 arg2 ...argn) という形式です。arg1,...argnをスレッドで起動、マルチコアで実行します。

pletはlet構文のマルチスレッド版です。式の部分をスレッドに分解して実行し、これをjoinで待機したのちにbody部を実行します。

余談ですが、EISLは型推論器をもっており、the構文により必要な情報を与えると最適化するようにしてあります。たらい回しのような単純な再帰コードの場合、C言語波の実行速度を出すことができます。

計測

インテルicore5で計測しました。Windows WSLで実行しています。

予想に反して並列のpfibの方が逐次のfibより若干遅いのでした。pthreadの設定の問題だろうか？などChatGPTに相手になってもらいかなり試行錯誤したのですが、残念ながら並列の方が遅くなっています。ARMラズパイ４００では並列の方が高速になっています。たらい回し、竹内関数の場合にはその再帰パターンは複雑なのでなかなか並列での性能が上げられないでいます。スレッドに分割するコストを考えても2倍くらいは高速になると予想していたのですが。ちょっとがっかり。

CPUによる違い

英語版Reddit/Lispには凄腕Lisperがた出入りしているように思いました。記事を投稿し、いくつか助言をいただきまいした。改良の余地はあるかもしれません。また、コンカレントGCと並列動作とかまだ共存できずにセグフォを起こしています。並列動作を理解しつつじっくりデバグしています。

インテル、AMD、ARM　それぞれ設計方針が異なるようで並列動作したときのパフォーマンスが異なります。ARMの方が並列で効果を出せています。インテルicoreは単一スレッドの高速性を重視しているのかもしれません。

EISLはGithubにおいてります。よかったらお試しください。
https://github.com/sasagawa888/eisl