Boost Game Performance With Threads

原文こちら

今あるコードを少しだけ変更して機能を分割し、マルチコアプロセッサーのすべてのコアを使ってより高いパフォーマンスを得る方法を紹介する

Andrew Binstock

 グラフィックやマルチメディアに関する幅広い体験をユーザーに提供するゲームなどのソフトウェアは、パフォーマンスの問題にさらされます。そのため、ハードウェアのパフォーマンスを最大限に発揮するテクニックが、可能な範囲内で最高のユーザーエクスペリエンスをユーザーに提供するために、特に重要になってきます。ほとんどのゲーム開発者はそれがどんなに大事かを分かっていますが、最も優れたパフォーマンス向上テクニックである "並列処理" を避けがちです。タスクを並列に実行すれば、ソフトウェアはより高速に動作します。現在、インテルがリリースしているデュアルコアチップやクアッドコアチップといったマルチコアプロセッサー上で、もしソフトウェアがシングルスレッドで実行されているのであれば、プロセッサの多くの部分が未活用なまま眠っていることになります。しかし、複数のスレッドを渡ることの出来る細かい "塊" にソフトウェアが細分化されるのであれば、プロセッサーの 100% の部分をパフォーマンスアップのために働かせることができます。

 今の時点では、ユーザーはパフォーマンスを犠牲にするソフトウェアについてあまり不満を漏らしませんが、それはデスクトップPCにクァッドコアチップが使用され始めたのが、まだ最近の出来事だからです。インテルが4つ以上のコア(メニーコアプロセッサーと呼ばれるもの)を提供していくに従って、ひとつふたつのコアを使用する程度で他のコアを未使用なままにしているような重たいソフトウェアは見捨てられ、ユーザーはメニーコアに対応した製品を積極的に選ぶようになるでしょう。今日、並列処理はパフォーマンス向上のための賢い方法であり、そしてこれから数年間の基本的な必須要件になります。

並列処理の例

 シングルスレッドで動くソフトを書くことは、すべてのタスクがシーケンシャルに実行されるということです。例えば、ブラックジャックゲームを開発するとしましょう。ディーラのカードシューターが空っぽのとき、ソフトウェアは必要な数のデックをシャッフルしなければなりません。カードがシャッフルされている間は、ユーザーは待つしかありません。より良いユーザーエクスペリエンスは、前のカードシューターが使い切られたら、すぐにシャッフル済みのカードシューターをディーラーへ渡すことです。この方法であれば、一切待たされることなく、ゲームプレーを続けることができます。ゲームが進行中の間に、裏でカードシューターの準備を行うためには、スレッドを使ったプログラムを書くことになるでしょう。新しいシューターがサービスに配置されたとき、すぐに別のスレッドが新しいシューターをロードするためにロンチされます。このように、ゲームとカードシューターの準備は並列で行われます。

 この例は、どんなタスクがスレッドで扱われるように細分化されるべきかを判断するための2つの主要なテクニックのうちのひとつを示しています。このブラックジャック・ゲームで、私たちは2つのパートにタスクを分解しました。メインゲームスレッドとカードシューターの準備をするスレッドです。この分割は、機能分割*1として知られています。私たちは、タスクに基づいて、新しいスレッドの仕事を定義しました。

 "2つの主要なテクニック" のうちのもうひとつは、データ分割という方法です。これは、大量のデータに同じ操作を行う場合に、そのデータの部分部分にスレッドを割り当てていくパターンです。詳細は、また次の機会にでも紹介したいと思います。

機能分割

 カードシューターの機能分割は、ユーザーに直接対応するソフトウェアの典型です。様々なワーカースレッドが、それぞれ明確に細分化できるタスクを担当して取り組むという形が普通ですが、メインプログラムループとグラフィックのレンダリングの制御はひとつのスレッドが行います。たとえば、多くのワープロソフトでは、スペルチェックの仕事にひとつのスレッドを割り当て、さらに別のスレッドに丁付けの仕事を割り当てます。こうして裏で丁付けなどが行われている間に、ユーザーは表側でドキュメントを書くことに取り組むことができるのです。

 ゲームは機能分割に向いてます。特に、スタートアップのロード待ちを補うのにマルチスレッドを活用できます。今のゲームは、ほとんどのタイトルでスタートアップ時に長い読み込み待ち時間があり、スプラッシュスクリーンやビデオエフェクトで包み隠して、ロード待ちのイライラをそらしたり誤魔化したりしています。しかし、個々のスタートアップタスクの多くはスタンドアロンでも動ける雑役に過ぎません。並列プログラミングモデルであれば、スタートアップの遅延を減少させるために、これらを並列化できます。簡単に並列化できるタスクとしては、たとえば、ディスクからのデータの読み込みや、ユーザーの環境設定の取得、ネットワークコネクションの作成などがあります。

 機能分割がゲーム開発に特に役立てることとして、カードシューターを準備する例のような、するべき仕事の予測/先読みが挙げられます。しかし、そこには単純なものもあれば、複雑なものもあります。多くの開発者が知っているように、動きの予測はユーザーにスムーズな視覚的体験をユーザーに提供する重要な部分です。たとえば、カーレースゲームのようなものであれば、 "するべき仕事の先読み" は簡単です。コースが決まっていれば、コース上にあることが分かっていて、ぼちぼち視界に入ろうとしているオブジェクトの描画の準備などを行うことができます。インタラクティブなゲームであっても、特定の交差点でユーザーが左右どちらかへ曲がる可能性を踏まえたうえで、動作と見た目を事前計算することは不可能ではありません。

多くの演算パワー

 先ほどの例の最後で、プレイヤーが左に曲がるか右に曲がるかをどうやって推測して事前演算の内容を決定するのか、怪訝に思われたかもしれません。しかし、たくさんのコアを自由に使える場合、推測をする必要はなく、両方の可能性を演算すればよいのです。それぞれの選択肢を別々のコアの上で走る別々のスレッドでハンドリングし、結果的にユーザーが左に曲がれば、左に曲がる部分を担当したスレッドの結果を利用して、右に曲がる部分を担当したスレッドを結果ごと破棄します。逆もまた然りです。*2

 シングルスレッドモデルに慣れ親しんだ開発者であれば、 "廃棄される可能性のある演算を行う" というコンセプトに少々抵抗を感じるかもしれません。純粋なシーケンシャルのアプローチでは、高いパフォーマンスを得るためには、ムダな演算を省くことが基本だからです。しかし、今の PC には多くの予備の処理パイプラインがあります。4つのパイプラインを持つ典型的なクアッドコアチップが来年のデファクトスタンダードなシリコン・プラットホームになると考えてください。さらに、2008年11月に、インテルは2本のハードウェアスレッドを持ったコアを4つ搭載した新型プロセッサ "i7" の出荷を始めています。このプロセッサでは、チップは合計8つの処理パイプラインを提供していることになります。インテルは、今後、さらに多くのパイプラインを持ったプロセッサを登場させる見込みであり、私たちは本格的なメニーコア時代に突入しようとしています。

 このように、非常に多くの数のパイプラインが利用可能な場合、投機的な命令の実行は決して "損失" ではありません。これはパフォーマンス上のベネフィットであり、活用しない手はありません。*3

機能分割を始める前に

 スレッドの良いところは、スレッドを使うためにコードを1から書き直す必要がないことです。スレッドを使うための付け足し分を書き加えて、すぐにそのパフォーマンス上の利点を堪能することができます。機能分解可能なタスクを今あるコードから見つけ出すもっとも簡単な方法は、以下のガイドラインを満たす動作を探すことです。

  1. メインプログラムループか、レンダリングの一部でないこと。
  2. 概念的に、1つのタスクであるか、タスクの1つのセットであること。
  3. 他のスレッドの機能に依存していないこと。
  4. メインスレッドやほかのスレッドと共有しているデータ項目がわずかであること。


 カードシューターの再充填の例は、このガイドラインを満たしています。それはメインスレッドの一部ではありませんでした。概念的に離散的なタスクということです。それは、ほかのスレッドに全くかかわりなく、実行できます。そして、それは他の実行中のスレッドとデータ項目を全く共有しません。(ただし、充填を終えたシューターはディーラーのいるスレッドへデータ項目として引き渡されます)

 すべての動作は、より大きなソフトウェア操作と何らかの部分で統合されなければならないため、他のスレッドとの接触部分が必ずどこかにあります。よく言われる "並列プログラミングの複雑さ" のすべては、こういった接触部分に由来しています。

 本質的には、問題は主に2つです。

  1. スレッドは他のスレッドを待つ
  2. 同時にデータ項目を変更するふたつのスレッド

 こういったものをどう扱うかです。どちらにも、とらえにくく、デバッグしにくい問題があるので、並列プログラミングに詳しくないうちは、他のスレッドを待たず、そしてほとんどデータポイントを他のスレッドと共有しないタスクを細分化することがベストでしょう。カードシューターは良い例です。それがどのようなものか、ラフな擬似コードで見てみましょう。

 開発者は既に、カードシューターを充填するルーティンを書き終わっているとします。これから、充填するカードシューターオブジェクトを受け取るスレッドを作ります。カードシューターがどのタイミングで必要になるかを示すフラグ(つまり boolean 変数)も使います。典型的サイクルはこのようになるでしょう:

  1. カードシューターを充填するスレッドを起動します(最初だけスレッドを作ってください)
  2. スレッドを呼んで、空のカードシューターを渡します。
  3. スレッドはシューターにカードを充填して、 boolean フラグに false (現在はシューターの充填が必要とされない)を設定します。
  4. フラグがメインスレッドによって true に設定されるまで、スレッドをサスペンドさせます。それから、1へ戻ってください。


 メインのディーラープログラムが新しいカードシューターを必要とするとき、そのプログラムは充填済みのカードシューターを取得して、フラグを true に設定します。これによって、新しいカードシューターを充填するためのワーカースレッドが起動するでしょう。また、メインのディーラープログラムがシューターを必要とする場合であっても、まだそのシューターが準備されていないのであれば、フラグが false にリセットされるまで(シューターが現在利用可能であると通達されるまで)待機します。

 この例では、2つのスレッドが同時に1つの変数(フラグ)を使用しています。そのため、この操作は、一度に1つのスレッドだけがその変数を変更できるように、ロッキング・メカニズムを使用する必要があります。すべてのスレッディング API は mutex と呼ばれるロックを提供します。それは、一度に1つ以上のスレッドがロックされた領域のコードを実行すること(ここではフラグをリセットする処理)を禁止します。どんなスレッディング API でも、基本的に、同様のロッキング・メカニズムを提供しています。

スケールアップ

 カジノゲームを作ることを考えた場合、複数のゲーム卓が同時にシューターを要求してくることが想定されますので、複数の準備済みシューターを予備として持っておく必要があります。準備済みのカードシューターのキューを作っておくとよいでしょう。生産者のスレッドがカードシューターにシャッフルしたカードを充填して、そのシューターをキューの末尾に追加するようにします。他方、カジノの各ゲーム卓は、キューの先頭からシューターを取り出して使うわけです。このように、ひとつのスレッドがデータアイテムを生産し、消費するスレッドのためにキューに追加するというやり方は「Producer-Consumer パターン」と呼ばれ、並列プログラミングの一般的なパターンのひとつになっています。

 Producer-Cunsumerパターンは、広く使われている方法であり、 Producer と Consumer にあたる処理を別々のスレッドへ簡単に分離することができます。たとえば、遅いメディアや遅いネットワーク通信からデータを読み込むようなシチュエーションがいい例です。ほとんどのゲームで、 CD や DVD からのデータ読み込みを行っています。光学式メディアの読み込みの遅さは悪名高く、開発者としては読み込み中は別のことに取り組みたいところです。 Producer-Consumerパターンはこういった状況を手助けしてくれます。ひとつのスレッドはデータのブロックをファイルから読み込み、キューへそれを追加する仕事を担当します。そして、別のスレッドが、そのブロックを検索して処理を始めます。こういう作り方をすれば、時間の浪費はほとんどなくなります。

 大型のポーカーゲームで機能分割を適用できる他の例としては、各プレイヤーにスレッドをひとつずつ割り当てるアプローチが挙げられます。これはスケーラビリティを高めます。プレイヤーやテーブルの数を増やすことはよく比例します。OSは、数多くのニーズ---たとえそれが何百というスレッドを同時に走らせることであっても---のバランスをとることが得意です。並列プログラミングを用いることで、あなたはメインスレッドからそれぞれの新しいプレーヤーを取り扱うオーバーヘッドを取り除くことができます。スレッドを使わなければ、設計はまったくスケールアップすることができず、追加されたそれぞれのプレイヤーが、そのぶんだけゲームのパフォーマンスを重くするでしょう。

 さきほども言いましたが、3Dゲームには似たような機能分割の機会がたくさんあります。スタートアップタスク、離散的なタスク、そしてプレイヤーまたはアニメーションスプライトがとりうるアクションとモーションの予測などです。

スレッディングの実践

 x86プロセッサには、利用可能なスレッディングAPIがたくさんあります。これらのAPIはすべてスレッドの基本であるスレッドの作成や実行、スリープ、削除、条件変数とスレッドの待機、そしてさまざまなロッキング・メカニズムを提供します。公開されているスレッディング API のほとんどは、こういった基本性能のスーパーセットを提供します。

 C/C++ で開発されるゲームのために、たくさんのインターフェイスがあります。ネイティブの Windows スレッド API は、最も広範囲に利用できるインターフェイスです。これを使うなら、スタート地点として MSDN をオススメします。しかしながら、 Windows API は移植性がないため、開発者によっては、 Windows 上で動作して、かつ、 Linux 系と UNIX ベースのほとんどの OS でネイティブスレッド API となる "Pthreads" を使うことを好むかもしれません。 Pthreads の Windows 向けネイティブ実装は http://sourceware.org/pthreads-win32/ で利用可能で、うまく動作します。そのほか、 .NET フレームワーク上のすべての言語には Java がやるような Windows API があります。他方、スレッドが使えないゲーム言語のひとつは Lua です。開発者が Lua でプログラムを書いている場合、上述のタスクを実行するために Lua のスレッド実装を使うことはできません。 Lua スレッドはコルーチン(スレッドの類似コンセプトながら、中身は決定的に異なっており、並列の実行はできません)です。

次回予告

 次のコラムでは、ビジュアルソフトウェアに対する機能分割をより深いレベルで調べていくつもりです。私たちは若干のソースコードを見て、きめ細かいマルチスレッディングを使って最大のベネフィットをユーザーに届ける課題を解く方法を調べます。

 Andrew Binstock は Pacific Data Works LLC で技術白書を書いています。彼は InfoWorld のシニアコントリビュータであり、 SD Times のコラムニストであり、また Intel Press の "Programming With Hyper-Threading Technology" を含むいくつかの本の著者または共著者でもあります。彼はフリータイムの間に、オープンソースの植字&ページレイアウトプロジェクト "Platyus" にコントリビュートしています。ブログは http://binstock.blogspot.com

*1:訳者注:タスク並列とも

*2:訳者注:メモリ貧民のコンソール機でどうやってこんなのを活用するのかは知りませぬ

*3:実際に、インテルのプロセッサーは10年以上にわたり、命令の投機的実行を行ってきています。 Pentium、Core、i7 プロセッサーの内部には、実行が予定されている命令のシーケンスを調べるロジックが備えられています。このロジックは、分岐命令を調べて、これからの実行が実際に分岐を行うかどうか判断します。分岐すると予測されると、プロセッサの実行ユニットはその分岐に沿って命令を事前に実行し始めます。プロセッサの予測が当たって分岐が始まれば、事前実行されたぶん、時間が短縮されます。しかし、もし分岐が起きなければ、あらかじめ実行された命令は破棄されます。