Parallelizing the Naughty Dog Engine Using Fibers

構成

• 30Hzのシングルスレッド
  • ゲームロジックを処理してからコマンドバッファをセットアップしていた
• SPUはワーカースレッドとして使っていた
  • エンジンシステムのほとんどはSPU上で処理していた
• SPU上で動作するgameplayコードはごくわずか

問題点

• ジョブは返すものがなくても完了を待たなければならない
  • アトミックな単位が決まっている
• メモリ管理はユーザーがやらなければならない
  • ジョブを定義したり、メモリの寿命を気にしたりする手間が大きい
• ジョブリストの状態が煩わしい
  • ジョブリストが実行中か停止中かを気にしなければならない
• ジョブ配列を指すマーカーインデックスによるジョブ同期
  • インデックスは再利用されうるため、使っていないときにリセットしなければならない

詳細

• ワーカースレッドはコアに固定される
  • 無用なスイッチングを避けるため
• WaitForCounter
  • ジョブをファイバーごと待機させる
• “The Last of Us: Remastered”では、1フレームに最大800から1000のジョブを処理する

I/O処理はシステムスレッドで行われるので、そこだけ例外的にデータの読み出しとジョブの発行を行うハンドラで処理する。それ以外はすべてジョブ化されている。

利点

• 既存のgameplay更新処理を簡単にジョブ化できる
• ジョブを待機させるのが簡単
• ファイバー切り替えが超軽量

欠点

• ミューテクスやセマフォなどのシステムの同期プリミティブが利用できなくなる
• 同期はハードウェアレベルでやらなければならない
  • アトミックなスピンロックが至るところで使われている
  • ロックが長引く場合には特殊なジョブ用ミューテクスを使う

ファイバーのサポート

• 基本的にはスレッドと同様にスタックトレースできるしダンプも吐くことができる
• 寝ているファイバーを異なるスレッドで起こすと、キャッシュされた前のTLSアドレスにアクセスすることがある
  • コンパイラに”Fiber-Safe TLS”オプションがあれば使う
  • ないなら、TLSアクセスを毎度キャッシュせずに行うよう、翻訳単位を分ける
• ジョブシステムではadaptive mutexを使う
  • システムコールを行う前にスピンロックでどうにかしてみる方法
  • ｜優先順位の逆転《priority inversion》によるデッドロックを解決する
  • 初回のスピンで大抵のシステムコールを回避できる

PS3時代のメモリ割り当て

• 線形なアロケータ
  • 連続したメモリブロックとそのオフセットを用いる
  • アロケートは単純なオフセットの更新で行われる
  • 解放はオフセットを0にするだけでよい
• シングル/ダブル/トリプル フレーム
  • フレーム開始時に新しいブロックに取り替え、オフセットを0にする

メモリブロックはその寿命をフレーム単位で指定することができる。

これらは、フレームが1つであればうまく機能した。

マルチフレームの難しいところ

• “いつメモリを解放したらいいの？”
• “毎フレーム新しいバッファが欲しいんだけど”
  • “memory stomping¹を回避しつつ取り替えるにはいくつバッファがあればいいの？”
• “フレームの｜経過時間《delta time》はどれを使えばいいの？”

Frames

あちらこちらで言及されるフレームだけど、意外と人によって解釈が違ったりする。

ゲームロジックだったり、GPUだったり、ディスプレイだったり。

メモリの寿命を指すときにも使われる。ダブルバッファとかトリプルバッファとかはどうすればいい？

そこで、フレームを再定義することにした。

このときは、“｜処理されて最終的にスクリーンに表示されるデータの集まり《A piece of data that is processed and ultimately displayed on screen》”とした。

重要なのは、計測時間ではなくデータの集まりとしたこと。

FrameParams

FrameParamsは各フレームが表示されるまでに必要なデータを持ち、すべてのステージ間を渡り歩く。

FrameParamsはフレーム毎の状態（フレーム番号、delta time、スキニング行列など）を含む。

必要なデータにアクセスするための、各ステージの｜入り口《entry point》になる。

FrameParamsは、各ステージが個別のインスタンスの上で動作するため、｜競合しない資源《uncontended resource》である。

delta time、カメラ位置、スキニング行列、描画するメッシュのリストなどが毎フレーム分コピーされる。

各ステージの開始/終了タイムスタンプが保存される。

特定のステージが完了したかどうかをテストするのは、タイムスタンプをチェックするなどですむ。

メモリの寿命はそのメモリを使っているフレームの完了を待つだけでよくなる。

16のFrameParamsを切り替えて使うことで、直近の15フレーム分をトラックできる。

Tagged Heap

メモリは異なるアロケータ、異なる寿命を持つ。サイズは最悪の場合を想定して確保してあるので、100から200MiBの無駄が発生している。

Tagged heapを導入した。Tagged heapは、PS4のTLBサイズである2MiBを基本サイズとしたブロックベースのアロケータで、ブロックはuint64_t型のタグを持つ。ブロックをfreeする関数は持たず、特定のタグをまとめてリセットできる。

アロケータはブロックを1つ持っていて、ブロックが空になるまでその領域から要求に応じた割り当てを行う。

高速化のため、ワーカースレッドごとにブロックを1つ持つ。