並列処理で爆速化！括弧の整合性チェックを最適化する方法

括弧のペアが正しく閉じられているかを検証する「Parentheses Matching」という古典的なアルゴリズム問題。これをマルチコアCPUのパワーを最大限に引き出して並列処理で解決する手法について解説します。逐次処理では時間がかかる大規模な文字列解析も、並列アプローチなら効率的に処理可能です。

面白い記事で読む価値はあるんだけど、残念ながらLaTeXが全くレンダリングされてなかった（たぶんされるはずだよね）。

「Fast GPU bounding boxes on tree-structured scenes1」（未発表論文）とブログ記事に向けたメモ2も見てみて。これは括弧のマッチングをGPUで極限までチューニングして実装したものだよ。実際、Velloで使われている（古いバージョンで、処理のほぼ全てをGPUにオフロードするタイプ。ブレンドスタックの追跡をCPUで行う新しいCPU-GPUハイブリッド版ではないほうね）。

この研究の初期バージョンはHNでも取り上げられた3けど、今回のはもっと洗練されてる。（あとコメントなしの投稿がいくつかあったはず）

基本的なアイデア（二環半群と二分探索）は今回の投稿と同じ。一番古い出典は1985年のBar-OnとVishkin5の論文だと思う。このアイデアの実装としては、GPU高速化コンパイラの実験プロジェクトであるpareas6もあるよ。

この成果は論文として発表できるレベルだと思うし、学生と一緒に再投稿できたら最高だな。もしシドニー近辺の学生や教授がいたら、ぜひ連絡してほしい。

Oleg Kiselyovの仕事に初めて出会えるなんて最高だね。彼のWebアーカイブは本当に素晴らしいよ！今日初めてこれを見つけている著者や他の人たちが羨ましい。

https://okmij.org/ftp/

いいね。自分もEd KmettのMonoidal Parsingの録画講義で、Dyck言語としてこのアイデアを知ったのを思い出したよ。

興味深い記事だ。

同じ問題はRange Min Query Tree（RMQツリー）でも解けるよ。括弧のバランスが取れているかどうかのクエリはO(log N)でいける。2〜3レベルのRMQTreeがあれば、すでに数十億個の括弧を表現できる（ブランチファクター65536の2レベルツリーで40億個の括弧）。クエリはO(65536 + 65536)で、実質的にO(1)だね。256のブランチファクターを持つ4レベルツリーなら、クエリはO(256 + 256 + 256 + 256)で、これもO(1)。結局、レベル数に対するメモリアクセスの問題になる。合計（total）が0で、最小値（min）が0より大きければ、括弧のバランスは取れていることになる。

括弧は複数のセグメントに分割して並列処理することも可能だ。複数のRMQTreeを使って、各セグメントを並列に処理する。最後に各RMQTreeから「合計」と「最小値」を足し合わせる最終パスが必要になる。並列処理による恩恵は、たぶんそれほど大きくはないだろうけど。

CYKアルゴリズムをじっくり眺めて、それが動的計画法の一種だと理解できれば、同じ並列化のトリックがあらゆる文脈自由文法に使えるってことに気づけるはずだよ！