パラレルテンパリングを並列化する場合にオーバーヘッドが気になるのですが，それを極力なくす方向で考えたアイディアのメモです。

パラレルテンパリングは複数本の異なるパラメーターを持つマルコフ連鎖を同時に走らせ，適当なステップごとに隣り合う鎖と交換するという操作を行うことで，目的とする分布からのサンプリングを行う手法です。図で表すと次のようになります。

各行がそれぞれの連鎖を表し，網掛け部分が連鎖の交換を表します。

複数本の鎖があるのでこれらを並列に走らせたら良いのではないかということは当然のように思いつくのですが，交換ステップがあるため連鎖数がそこそこ大きいか，連鎖の 1 ステップあたりの計算時間 (図の矢印のコスト) が大きくないと，パフォーマンスの低下を招きかねません。

できるだけオーバーヘッドコストを減らす方向で考えてみると，交換ステップでは交換にかかわる 2 つの連鎖以外は次のステップに進んで問題ありません。言い換えると，ある連鎖に着目したとき，その連鎖が交換ステップに関係するまでは連鎖を進めて良いことになります。上の図でいうと，一番上の連鎖は，他の連鎖間の交換を待つ必要はなく， 5 ステップまでは MCMC を進めて良いということです。

ということで以下のような並列化の方法が思いつきます。

1. 交換ステップの場所を決めるワーカーを走らせる (上の図でいうと網を設置していく役)。
2. 各連鎖を，交換ステップワーカーを追い越さないように，並列して走らせる。
   1. 交換ステップに到達したら，交換相手の連鎖が到達するのを待つ。
   2. 交換するペアが揃ったら交換する。
   3. 交換したら再び次の交換ステップまで走る。

交換ステップの起こる頻度にもよりますが，そこそこうまくいくのではないかなと思います^[A]。実装も難しくないでしょう。注意すべき点は，交換ステップワーカーを先行させすぎると交換ステップキューが肥大してしまうということくらいでしょうか。

脚注

1. 実際にベンチマークをとったわけでもないし，そもそもまだ実装して試してすらいませんが。 [↩]