役に立つかもしれない、Task Queueの作り方
はじめに
この記事は、レイトレ合宿7 アドベントカレンダーの記事です。
様々なタスクをマルチスレッドで処理するために Task Queue を使う場合があります。 OpenMP 等のように気軽に並列化できる処理もたくさんありますが、例えば BVH を構築する場合、 この記事 内に紹介されるような Task Queue が使われることも多いかなと思います。 BVH を何種類も作ったり、他の処理でも Task Queue は使いどころがある気がします（具体的にたくさん挙げられるとは言っていない）し、可読性向上の観点からも、モジュールとしては小さいですが、独立したモジュールを作りたい気持ちになります。
Task Queue を独立したモジュールとして作ろうと思って色々考えてみると、終了条件をどう表現するかが比較的難しいポイントと感じました。 例えば、今は Queue が空でも、処理中のスレッドが新しくタスクが放り込まれるかもしれないため、Queue が空だという条件は使えません。 また、処理が終了したら迅速にスレッドを終了する必要もあるため無限ループするわけにもいかず、終了条件を記述した関数を渡すのもあまりしっくり来ませんでした。
このような時、数値で表現される進捗を queue に登録する方法だと、比較的上手く表現できそうと感じたので、紹介してみることにします。 例えば、BVH の構築であれば、Leaf Node を作成したタイミングでその Leaf Node に含まれる primitive (Polygon とか) な object の個数を進捗として報告し、最終的に進捗が BVH 構築時に渡される object の個数に到達すれば終了して良い、といった感じになります。
実装
c++ での実装例はこちらになります。TaskQueue の実装と、BVH の構築とよく似た処理を行うサンプルコードを一緒に置いておきました。 この記事を書いた環境の都合上、std::optional の代わりに boost を使っています。
例えば std::queue との差分としては、
- empty() や size() 相当の処理等はなく、進捗登録とタスク登録／取得しかできない
- front() と pop() は同時にやる
- 要素が取れる保証がないので、要素取得は optional で包む
といった感じになります。
おわりに
今回はこれ以上深追いしませんでしたが、もっといい設計はできるかもしれないので、いい方法等ありましたら教えて頂けると幸いです。また、この Queue に名前がついていたり、こんな使い方が出来そうみたいな例などあったりしたら、教えてもらえると嬉しいです。
