はじめに
私は2016年からISLisp準拠のLisp処理系の開発に取り組んでいました。2023年度には仕様への準拠もほぼ完全なものになりました。OSSとして公開しバグ報告に対応しつつ準拠度を向上させています。ところで、ISLispは当時東北大学、教授でいらっしゃった伊藤貴康先生の案が元となっています。伊藤先生はISLispのコアな部分に功績があるとともに、並列Lispについても研究されていました。伊藤先生のネットで公表されている並列Lispに関する文献に興味がわきました。自作のISLisp処理系に並列機能を取り入れようと思い立ち、2024年は並列機能に取り組みました。そのことに関して記録にとどめたいと思います。
マルチスレッド方式
手始めにマルチスレッド方式による並列に取り組みました。スタックポインタなど各種のポインタをスレッドセーフにしました。組込み関数にもスレッド番号を付与してスレッドセーフとしました。セルの供給はLispの性質上、切り分けることができず、lock/unlock機能によりスレッド間での競合を避けました。スレッドごとに関数を実行するときに素早く起動できるようにスレッドプーリングを実装しました。現在のパソコンは廉価版でも6コア程度はもっています。初期化の時点でスレッドを起動させプーリングするようにしました。
スレッドセーフにするのに手こずりましたが、なんとかスレッドセーフを達成して並列で動作するようになりました。しかし、これでフィボナッチ数列を並列実行するとかえって逐次よりも遅くなってしまうのです。不思議なことに安価なラズパイでは並列の方が速くなります。ところでインテルやAMDのCPUをを乗せたデスクトップでは並列の方が遅いのです。競合の問題なのか？とあれこれと試行錯誤しました。結論としてはCPUのキャッシュの問題とヒープからのセル切り出しの競合の問題でした。
まずはキャッシュの問題についてです。インテルやAMDのCPUにはL1,L2,L3のキャッシュが搭載されています。特にL3キャッシュのメモリ容量は大きいのですが、これから外れてしまうとメモリへのアクセスとなってしまい、速度が出せなくなります。ラズパイに搭載されているCPUはL1,L2キャッシュまでしかありません。逐次においても並列においてもL3キャッシュの恩恵がないので並列が高速化しました。ところがインテルなどのCPUではコンパイラの生成するコードが離れた場所にあるためにL3キャッシュでヒットしなかったのでした。コンパイルコードを改善して並列性能を出せるようになりました。
さらにヒープ領域からセルを切り出すときに競合が起きていることがわかりました。当初はヒープ領域を分けずにLOCK/UNLOCKで切り出していました。これが並列において速度の妨げになっていました。図のようにヒープ領域をスレッドごとにわけておくことにより競合を避け、並列性能を出せるようになりました。
この試行錯誤ではハードの勉強になりました。AMDのRyzenが並列性能に優れているというのでRyzenで自作マシンも作りました。
マルチプロセス方式
次にマルチプロセス方式に取り組みました。Unix系のOSはマルチプロセスの取り扱いが楽です。別プロセスでLispを起動させ入出力は標準入出力をパイプで切り替えることにより実装しました。なぜかこのパイプでのやりとりはOS仕様なのか8バイト単位なのです。試行錯誤しつつパイプで各Lispとのやりとりとできるようにしました。マルチプロセスの場合にはメモリがそれぞれ独立していますので競合の問題はありません。昨今のCPUは廉価版でも６コアくらいは積んでいます。5プロセスでLispを並列動作させて計算実験をしました。
プロセス間で同期をとるのにシグナルなどを勉強しました。最近ではChatGPTで相手をしてくれます。いろいろと教わりつつ独自に工夫をこらしました。
分散並列方式
最後は分散並列方式です。親機を頂点にして星型に子機をTCP/IP通信で接続する方法をとりました。TCP/IPのよい勉強になりました。
分散方式ですと子機はそれぞれ独立したマシンです。競合もなくメモリもたっぷり使える利点があります。一方で通信時間によるオーバーヘッドがあります。粒度が大きい問題でその威力を発揮するようです。
子機との同期をとるのにシグナルは使えませんので、プロコトルを決めておいてTCP/IPでスレッドを利用して通信する方法をとりました。
終わりに
20世紀の頃に活躍した伊藤先生他のLisper諸兄がどのように考えて、工夫をし突破したのかを私も体験したような気持ちでおります。もっとも当時は今のようなマルチコアCPUは市販されていません。ご自分でマルチコアマシンを設計、製作されていました。当時のLisperはスーパーハッカーでした。不可能と思われることに果敢に挑戦していたようです。
一時的にLispがブームになった時期がありました。ポール・グレアム氏の影響のようです。騒がしかったLisp世界も元の落ち着きを取り戻したようです。ひたすらマクロを連呼するLisp使いもいましたっけ。また落ち着きを取り戻したLisp世界でISLispを知的なおもちゃにして日々楽しんでいます。
私の製作した実装にご興味がありましたら、下記をご参照ください。たいへんに名誉なことにGNUのGuixにもパッケージとして採用していただきました。Lisper冥利に尽きます。感謝！