(57)【要約】  システムが、二つ以上のストリーム処理プログラムを、当該ストリーム処理プログラムの間で交換されるデータに基づいて最適化する。システムは、不要なプログラムコードを識別して除去し、それによって実行性能が向上するように、各ストリーム処理プログラムを交互に処理する。不要なプログラムコードは、他のストリーム処理プログラムからの入力として受け取られる定数を伝播することによって、また、第１のストリーム処理プログラムを解析して、第１のストリーム処理プログラムによって使用されない第２のストリーム処理プログラムの出力を突き止めることによって識別される。システムは、ストリーム処理プログラムへの入力として使用される更に別の定数を前の反復が導入する場合に、この最適化を複数回反復して実行してもよい。【選択図】  図３
2008505422.tif 000002
【特許請求の範囲】
【請求項１】
ストリーム処理システムによって実行されるようになっているストリーム処理プログラムを最適化する方法であって、該ストリーム処理システムが第１及び第２のプログラム制御可能なストリーム処理ユニットを備え、前記第２のストリーム処理ユニットが前記第１のストリーム処理ユニットに接続されて、前記第１のストリーム処理ユニットの出力が前記第２のストリーム処理ユニットの入力になっており、該方法が、
第１のストリーム処理ユニットによって実行されるようになっている第１のストリーム処理プログラムを受け取るステップであって、該第１のストリーム処理プログラムが出力パラメータを有する、該ステップと、
第２のストリーム処理ユニットによって実行されるようになっている第２のストリーム処理プログラムを受け取るステップであって、該第２のストリーム処理プログラムが、前記第１のストリーム処理プログラムの前記出力パラメータに対応する入力パラメータを有する、該ステップと、
前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の対応関係に基づいて、前記第１及び第２のストリーム処理プログラムを最適化するステップと、
を含む方法。
【請求項２】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第１のストリーム処理プログラムから、前記第２のストリーム処理プログラムによって使用されない追加の出力パラメータを計算するようになっている不要なプログラムコードを除去するステップを含む、請求項１に記載の方法。
【請求項３】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、
前記第１のストリーム処理プログラムの前記出力パラメータが定数であるという判定に応答して、前記第２のストリーム処理プログラムの前記入力パラメータ用の定数値を伝播するステップと、
前記第２のストリーム処理プログラムから、定数値を伝播した結果として余分になった不要なプログラムコードを除去するステップと、
を含む、請求項１に記載の方法。
【請求項４】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、
前記第１のストリーム処理プログラムの前記出力パラメータが一定値であるという判定に応答して、前記第２のストリーム処理プログラムの前記入力パラメータ用の一定値を伝播するステップと、
前記第２のストリーム処理プログラムから、一定値を伝播した結果として余分になった不要なプログラムコードを除去するステップと
を含む、請求項１に記載の方法。
【請求項５】
前記ストリーム処理システムがグラフィック処理サブシステム内にある、請求項１に記載の方法。
【請求項６】
前記第１のプログラム制御可能なストリーム処理ユニットが、プログラム制御可能な頂点プロセッサである、請求項５に記載の方法。
【請求項７】
前記第２のプログラム制御可能なストリーム処理ユニットが、プログラム制御可能な頂点プロセッサである、請求項５に記載の方法。
【請求項８】
前記第１のプログラム制御可能なストリーム処理ユニットが、プログラム制御可能なテッセレーションプロセッサである、請求項５に記載の方法。
【請求項９】
前記第２のプログラム制御可能なストリーム処理ユニットが、プログラム制御可能なフラグメントプロセッサである、請求項５に記載の方法。
【請求項１０】
前記ストリーム処理プログラムの少なくとも一つが、ＯｐｅｎＧＬシェーディング言語で書かれている、請求項１に記載の方法。
【請求項１１】
前記ストリーム処理プログラムの少なくとも一つが、Ｃｇ言語で書かれている、請求項１に記載の方法。
【請求項１２】
前記ストリーム処理プログラムの少なくとも一つが、ＤｉｒｅｃｔＸ高レベルシェーディング言語で書かれている、請求項１に記載の方法。
【請求項１３】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の前記対応関係に基づいて、前記第１及び第２のストリーム処理プログラムが最適化されるまで、前記第２のストリーム処理プログラムと第１の前記ストリーム処理プログラムを交互に最適化する複数回の反復を含む、請求項１に記載の方法。
【請求項１４】
前記最適化された第１及び第２のストリーム処理プログラムを、前記ストリーム処理システムによって実行されるようになっているフォーマットにコンパイルするステップを更に備える、請求項１に記載の方法。
【請求項１５】
情報処理デバイスにステップのセットを実行するよう指令するようになっているプロセッサ命令のセットを含む情報記憶媒体であって、該情報処理デバイスが、第１及び第２のプログラム制御可能なストリーム処理ユニットを有するストリーム処理システムを備え、前記第２のストリーム処理ユニットが前記第１のストリーム処理ユニットに接続されて、前記第１のストリーム処理ユニットの出力が前記第２のストリーム処理ユニットの入力になっており、前記ステップのセットが、
第１のストリーム処理ユニットによって実行されるようになっている第１のストリーム処理プログラムを受け取るステップであって、該第１のストリーム処理プログラムが出力パラメータを有する、該ステップと、
第２のストリーム処理ユニットによって実行されるようになっている第２のストリーム処理プログラムを受け取るステップであって、該第２のストリーム処理プログラムが、前記第１のストリーム処理プログラムの前記出力パラメータに対応する入力パラメータを有する、該ステップと、
前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の対応関係に基づいて、前記第１及び第２のストリーム処理プログラムを最適化するステップと、
を含み、
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の前記対応関係に基づいて、前記第１及び第２のストリーム処理プログラムが最適化されるまで、前記第２のストリーム処理プログラムと前記第１のストリーム処理プログラムを交互に最適化する複数回の反復を含む、
情報記憶媒体。
【請求項１６】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第１のストリーム処理プログラムから、前記第２のストリーム処理プログラムによって使用されない追加の出力パラメータを計算するようになっている不要なプログラムコードを除去するステップを含む、請求項１５に記載の情報記憶媒体。
【請求項１７】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、
前記第１のストリーム処理プログラムの前記出力パラメータが定数であるという判定に応答して、前記第２のストリーム処理プログラムの前記入力パラメータの定数値を伝播するステップと、
前記第２のストリーム処理プログラムから、定数値を伝播した結果として余分になった不要なプログラムコードを除去するステップと、
を含む、請求項１５に記載の情報記憶媒体。
【請求項１８】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、
前記第１のストリーム処理プログラムの前記出力パラメータが一定値であるという判定に応答して、前記第２のストリーム処理プログラムの前記入力パラメータ用の一定値を伝播するステップと、
前記第２のストリーム処理プログラムから、一定値を伝播した結果として余分になった不要なプログラムコードを除去するステップと、
を含む、請求項１５に記載の情報記憶媒体。
【請求項１９】
前記プログラム制御可能なストリーム処理ユニットの一つが、プログラム制御可能な頂点プロセッサである、請求項１５に記載の情報記憶媒体。
【請求項２０】
前記ストリーム処理プログラムの少なくとも一つが、ＯｐｅｎＧＬシェーディング言語で書かれている、請求項１５に記載の情報記憶媒体。
【請求項２１】
画像をレンダリングするようになっているシステムであって、
第１及び第２のプログラム制御可能なストリーム処理ユニットを有するグラフィック処理サブシステムであって、前記第２のストリーム処理ユニットが前記第１のストリーム処理ユニットに接続されて、前記第１のストリーム処理ユニットの出力が前記第２のストリーム処理ユニットの入力になっている、該グラフィック処理サブシステムと、
レンダリングアプリケーションから第１のストリーム処理プログラム及び第２のストリーム処理プログラムを含むレンダリングコマンドとデータのセットを受け取り、前記第１及び第２のストリーム処理プログラムを、ストリーム処理言語コンパイラユニットにディスパッチするようになっているＡＰＩドライバと、
を備え、
前記ストリーム処理言語コンパイラユニットが、
前記第１のストリーム処理ユニットによって実行されるようになっている前記第１のストリーム処理プログラムであって、出力パラメータを有する該第１のストリーム処理プログラムを受け取り、
前記第２のストリーム処理ユニットによって実行されるようになっている前記第２のストリーム処理プログラムであって、前記第１のストリーム処理プログラムの出力パラメータに対応する入力パラメータを有する該第２のストリーム処理プログラムを受け取り、
前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の対応関係に基づいて、前記第１及び第２のストリーム処理プログラムを最適化する、
ようになっており、
前記第１及び第２のストリーム処理プログラムを最適化することが、前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の前記対応関係に基づいて、前記第１及び第２のストリーム処理プログラムが最適化されるまで、前記第２のストリーム処理プログラムと前記第１のストリーム処理プログラムを交互に最適化することを複数回反復することを含む、システム。
【請求項２２】
前記ＡＰＩドライバが、更に、
前記ストリーム処理言語コンパイラユニットから、前記最適化された第１及び第２のストリーム処理プログラムを受け取り、
前記レンダリングコマンドとデータのセット、並びに、前記最適化された第１及び第２のストリーム処理プログラムを、前記グラフィック処理サブシステムに伝送し、
前記最適化された第１及び第２のストリーム処理プログラムをそれぞれ、前記第１及び第２のストリーム処理ユニットを用いて実行することによって、前記レンダリングコマンドとデータのセットの少なくとも一部分を処理するよう、前記グラフィック処理サブシステムに命令する、
ようになっている、請求項２１に記載のシステム。
【請求項２３】
前記ストリーム処理言語コンパイラユニットが、更に、前記最適化された第１及び第２のストリーム処理プログラムを、前記ストリーム処理システムによって実行されるようになっているフォーマットにコンパイルするようになっている、請求項２１に記載のシステム。
【請求項２４】
前記グラフィック処理サブシステムが、グラフィック処理ユニットを有する、請求項２１に記載のシステム。
【請求項２５】
前記グラフィック処理サブシステムが、前記レンダリングコマンドとデータのセットの少なくとも一部分を格納するようになっているグラフィックメモリを有する、請求項２１に記載のシステム。
【発明の詳細な説明】
【発明の背景】
【０００１】
[0001]本発明は、コンピュータグラフィックの分野に関するものである。多くのコンピュータグラフィック画像は、所与の視点から見た３次元場面と光の相互作用を数学的にモデル化することによって作成される。このプロセスは、レンダリングと呼ばれており、所与の視点から見た場面の２次元画像を生成するものであり、現実の場面の写真を撮るのに似たものである。
【０００２】
[0002]コンピュータグラフィック、特に、リアルタイムコンピュータグラフィックの需要が高まるにつれて、レンダリングプロセスを加速するようになっているグラフィック処理サブシステムを備えるコンピュータシステムが普及してきている。これらのコンピュータシステムにおいては、レンダリングプロセスは、コンピュータの汎用中央演算処理装置（ＣＰＵ）とグラフィック処理サブシステムの間で分割される。通常、ＣＰＵは、所与の場面におけるオブジェクトの位置、動き、及び衝突を決定する等、高度なオペレーションを実行する。これらの高度なオペレーションから、ＣＰＵは、所望の（一つ又は複数の）レンダリング画像を定義するレンダリングコマンドとデータのセットを生成する。例えば、レンダリングコマンドとデータは、場面の幾何配置、照明、シェーディング、テクスチャ、動き、及び／又は場面に対するカメラパラメータを定義することができる。グラフィック処理サブシステムは、レンダリングコマンドとデータのセットから一つ又は複数のレンダリング画像を作成する。
【０００３】
[0003]多くのグラフィック処理サブシステムは、高度にプログラム制御可能であり、特に、複雑な照明及びシェーディングアルゴリズムの実装を可能にする。このプログラム制御性を活用するために、アプリケーションは、一つ又は複数のグラフィック処理サブシステムプログラムを有することができ、これらのプログラムは、ＣＰＵによって実行されるメインプログラムと並列に、グラフィック処理サブシステムによって実行される。単にシェーディング及び照明アルゴリズムを実施することだけに制限されるものではないが、これらのグラフィック処理サブシステムプログラムは、しばしば、シェーディングプロトコル又はシェーダと呼ばれる。
【０００４】
[0004]グラフィック処理サブシステムは、通常、ストリーム処理モデルを使用し、当該ストリーム処理モデルでは、入力エレメントが、ストリーム処理ユニットのチェイン（連鎖）によって連続して読み取られ、処理される。あるストリーム処理ユニットの出力は、チェインにおける次のストリーム処理ユニットへの入力となる。通常、データは、ストリーム処理ユニットのチェインを、一方向、すなわち「下流」方向にのみ流れる。ストリーム処理ユニットの例には、２又は３次元頂点を処理する頂点プロセッサ、２又は３次元頂点の集合によって定義される幾何プリミティブを、フラグメント（断片）と呼ばれる画素又はサブ画素の集合へと処理するラスタライザプロセッサ、及びフラグメントを処理するフラグメントプロセッサがある。チェインには、更に、別の種類のストリーム処理ユニットも含まれ得る。例えば、テッセレーションプロセッサは、高次曲面の記述を受け取り、頂点によって定義され、且つ、当該高次曲面を近似又は対応する幾何プリミティブの集合を生成することができる。
【０００５】
[0005]チェインにおけるストリーム処理ユニットの一部又は全部がプログラム制御可能であり、プログラム制御可能なストリーム処理ユニットの各々が、他のストリーム処理ユニット上で実行されるシェーディングプログラムと並列に動作する独自の別個のシェーディングプログラムを備えていてもよい。複雑なアルゴリズムの実装形態は、しばしば、所望の結果を達成するために協働する各ストリーム処理ユニットに合わせて調整された別々のシェーディングプログラムに依存する。これらの実現形態では、チェインにおける最初のストリーム処理ユニットのシェーディングプログラムの出力が、当該チェインにおける後続のストリーム処理ユニットのシェーディングプログラムの入力とリンクされていることがある。シェーディングプログラムは、低レベルのアセンブリ、Ｃｇ言語、ＯｐｅｎＧＬシェーディング言語、ＤｉｒｅｘｔＸ高レベルシェーディング言語を含む、様々な低レベル及び高レベルのプログラミング言語で書くことができる。
【０００６】
[0006]シェーディングプログラムを最適化して、レンダリング性能を向上させ、アプリケーションが、グラフィック処理サブシステムの諸機能を十分に活用することができるようにすることが望ましい。異なるストリーム処理ユニット用のシェーディングプログラムが相互に連鎖している場合には（グラフィックＡＰＩ用語によっては、これをリンクということもある）、二つ以上のシェーディングプログラムの組み合わせに基づく最適化の可能性が生じることがあり、これはシェーダ間最適化と呼ばれる。
【０００７】
[0007]例えば、第１のシェーディングプログラムが、グラフィック処理ストリームにおける第２の連鎖シェーディングプログラムによって入力として使用されない値を出力することがある。この例では、使用されない出力を計算するために使用される第１のシェーディングプログラムの部分が安全に除外され、それによって、第１のシェーディングプログラムの実行時間が短縮される。別の例では、第１のシェーディングプログラムの出力が一定である場合、この定数の値を、第１のシェーディングプログラムに連鎖している第２のシェーディングプログラムの入力に伝播することができ、第１のシェーディングプログラムの実行時間が短縮され、恐らくは、第２のシェーディングプログラム内での更なる最適化が可能になる。
【０００８】
[0008]加えて、アプリケーション開発者は、各ストリーム処理ユニット用に、大規模な多目的シェーディングプログラムを書こうとする。各多目的シェーディングプログラムは、アプリケーションが、セットの中から、ストリーム処理ユニットによって必要に応じて実行されるべき一つ又は複数のオペレーションを選択することを可能にする。アプリケーションは、各ストリーム処理ユニットのシェーディングプログラムから適切なオペレーションを選択することによって、幾つかのストリーム処理ユニットにまたがって特定のアルゴリズムを実施することができる。それぞれが単一のオペレーションを実施する幾つかの異なる小規模なシェーディングプログラムではなく、各ストリーム処理ユニット用の選択可能なオペレーションを有する大規模な多目的シェーディングプログラムを使用すれば、アプリケーション開発が大幅に簡略化される。しかし、大規模な多目的シェーディングプログラムの実行は、大規模なシェーディングプログラムをグラフィック処理サブシステムに転送するのに必要な時間と帯域幅を含む幾つかの要因により、シェーディングプログラムのわずかな部分だけが実行されることになるときでさえも、時間がかかる。シェーディングプログラムのチェイニングを最適化すれば、このような大規模なプログラムを、その元のプログラムであったならでは最適化されなければ満たすことができなかったはずのハードウェアリソース限界内に収まる程度にまで簡略化することもできる。
【０００９】
[0009]従来の自動最適化技法は、各シェーディングプログラムを分離して考察するだけである。既存のハードウェアシェーディングコンパイラの最適化技法は、異なるストリーム処理ユニットに割り当てられている連鎖シェーディングプログラムの間の関係を解析せずに、シェーダ間最適化を決定する。加えて、これら従来の最適化は、ストリーム処理ユニットのチェインにおける一方向のデータフローを考慮に入れず、したがって、他の多くの潜在的な最適化を見落としてしまう。
【００１０】
[0010]したがって、連鎖シェーディングプログラム間の関係に基づいて、相互に連鎖した二つ以上のシェーディングプログラムを最適化することが求められている。さらに、大規模な多目的シェーディングプログラムを最適化して、大量のデータを不必要にグラフィック処理サブシステムに転送せずに、効率よく実行することも求められている。さらに、実行時にシェーダ間最適化を実行することができ、アプリケーションが、性能を損なわずにシェーディングプログラムの組み合わせを動的に選択できるようにすることも求められている。
【発明の簡単な概要】
【００１１】
[0011]本発明の実施の形態は、二つ以上のストリーム処理プログラムを、それらのストリーム処理プログラム間で交換されるデータに基づいて最適化するシステムである。このシステムは、各ストリーム処理プログラムを交互に処理し、不要なプログラムコードを識別して除去して、それによって実行性能を向上させる。不要なプログラムコードは、他のストリーム処理プログラムから入力として受け取られる定数を伝播することによって、また、第１のストリーム処理プログラムを解析して、第１のストリーム処理プログラムによって使用されない第２のストリーム処理プログラムの出力を突き止めることによって識別される。このシステムは、前の反復がストリーム処理プログラムへの入力として使用される追加の定数を導入する際に、この最適化を複数回反復して実行してもよい。各ストリーム処理プログラムの最適化に続いて、最適化されたストリーム処理プログラムは、ストリーム処理システムによって実行されるフォーマットにコンパイルされる。
【００１２】
[0012]本発明の実施の形態は、ストリーム処理システムによって実行されるようになっているストリーム処理プログラムを最適化する方法である。ストリーム処理システムは、第１及び第２のプログラム制御可能なストリーム処理ユニットを含む。第２のストリーム処理ユニットは、第１のストリーム処理ユニットに接続され、第１のストリーム処理ユニットの出力が、第２のストリーム処理ユニットの入力になる。
【００１３】
[0013]本方法は、第１のストリーム処理ユニットによって実行されるようになっている第１のストリーム処理プログラムを受け取るステップを含む。第１のストリーム処理プログラムは、出力パラメータを含む。本方法ではまた、第２のストリーム処理ユニットによって実行されるようになっている第２のストリーム処理プログラムも受け取る。第２のストリーム処理プログラムは、第１のストリーム処理プログラムの出力パラメータに対応する入力パラメータを含む。第１及び第２のストリーム処理プログラムは、第２のストリーム処理プログラムの入力パラメータと第１のストリーム処理プログラムの出力パラメータの間の対応関係に基づいて最適化される。
【００１４】
[0014]ある実施の形態では、第１及び第２のストリーム処理プログラムを最適化するステップは、第１のストリーム処理プログラムから、第２のストリーム処理プログラムによって使用されない追加の出力パラメータを計算するようになっている不要なプログラムコードを除去するステップを含む。別の実施形態では、第１及び第２のストリーム処理プログラムを最適化するステップは、第１のストリーム処理プログラムの出力パラメータが定数であるという判定に応答して、第２のストリーム処理プログラムの入力パラメータ用の定数値を伝達するステップと、第１のストリーム処理プログラムから、定数値を伝播する結果として余分になった不要なプログラムコードを除去するステップとを含む。
【００１５】
[0015]別の実施の形態において、第１及び第２のストリーム処理プログラムを最適化するステップは、第１のストリーム処理プログラムの出力パラメータが一定値であるという判定に応答して、第２のストリーム処理プログラムの入力パラメータ用の一定値を伝播するステップと、第２のストリーム処理プログラムから、一定値を伝播した結果として余分になった不要なプログラムコードを除去するステップと、を含む。一定値とは、シェーディング言語における専門用語であり、処理の間は変更することを許可されていないが、グラフィックプリミティブのストリームが、このようなストリームデータのバッチ間で値を変更することがある定数を指す。多くの場合に、一定値は、定数の畳み込み（コンパイル時に定数項を有する式をより単純な定数式に変形すること）のような最適化目的のために、定数値として扱うことができる。しかしながら、コンパイラが一定値の値を既知であることに基づいて最適化決定を行う場合（分岐の結果を決定するなど）、新しい一定値が先の最適化決定を変更することになれば、再最適化が必要である。
【００１６】
[0016]ストリーム処理システムのある実施の形態は、グラフィック処理サブシステム内にある。当該実施の形態では、プログラム制御可能なストリーム処理ユニットは、プログラム制御可能な頂点プロセッサ、プログラム制御可能なテッセレーションプロセッサ、又はプログラム制御可能なフラグメントプロセッサであってもよい。
【００１７】
[0017]本発明を、図面を参照して説明する。図面においては、類似の参照番号を使用して、同一の構成要素を示すこととする。
【発明の詳細な説明】
【００１８】
[0018]図１は、パーソナルコンピュータ、ビデオゲームコンソール、携帯情報端末、又はその他のディジタル機器といったコンピュータシステム１００のブロック図であり、本発明の実施の形態の実施に適したコンピュータシステムの図である。コンピュータシステム１００は、ソフトウェアアプリケーション及び、任意にオペレーティングシステムを実行する中央演算処理装置（ＣＰＵ）１０５を備えている。ある実施の形態においては、ＣＰＵ１０５は、実際には、並列で動作する幾つかの別個の中央演算処理装置である。メモリ１１０は、ＣＰＵ１０５が使用するためのアプリケーション及びデータを格納する。記憶装置１１５は、アプリケーション及びデータ用の不揮発性記憶を提供するものであり、当該記憶装置１１５としては、固定式ディスクドライブ、着脱式ディスクドライブ、フラッシュメモリデバイス、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、又はその他の光記憶装置がある。ユーザ入力装置１２０は、１人又は複数のユーザからのユーザ入力をコンピュータシステム１００に伝えるものであり、当該ユーザ入力装置１２０としては、キーボード、マウス、ジョイスティック、タッチスクリーン、及び／又はマイクロホンがある。ネットワークインターフェース１２５は、コンピュータシステム１００が、電子通信ネットワークを介して他のコンピュータシステムと通信できるようにするものであり、当該ネットワークインターフェース１２５としては、ローカルエリアネットワーク及びインターネットなどの広域ネットワークを介した有線又は無線通信がある。ＣＰＵ１０５、メモリ１１０、データ記憶装置１１５、ユーザ入力装置１２０、及びネットワークインターフェース１２５を含むコンピュータシステム１００の各構成要素は、一つ又は複数のデータバス１６０を介して接続されている。データバスの例には、ＩＳＡ、ＰＣＩ、ＡＧＰ、ＰＣＩ、ＰＣＩ−Ｘ（３ＧＩＯともいう）、ＨｙｐｅｒＴｒａｎｓｐｏｒｔデータバスが含まれる。
【００１９】
[0019]グラフィックサブシステム１３０は、データバス１６０、及びコンピュータシステム１００の各構成要素と接続されている。グラフィックサブシステム１３０は、グラフィック処理ユニット（ＧＰＵ）１３５とグラフィックメモリを有している。グラフィックメモリは、出力画像の各画素の画素データを格納するために使用される表示メモリ１４０（フレームバッファなど）を有する。画素データは、ＣＰＵ１０５から直接、表示メモリ１４０に提供することが可能である。或いは、ＣＰＵ１０５は、ＧＰＵ１３５に、所望の出力画像を定義するデータ及び／又はコマンドを提供し、当該データ及び／又はコマンドから、ＧＰＵ１３５が、一つ又は複数の出力画像の画素データを生成する。所望の出力画像を定義するデータ及び／又はコマンドは、追加メモリ１４５に格納される。ある実施の形態においては、ＧＰＵ１３５は、場面の幾何配置、照明、シェーディング、テクスチャ、動き、及び／又はカメラパラメータを定義するレンダリングコマンド及びデータから、出力画像の画素データを生成する。
【００２０】
[0020]別の実施の形態では、表示メモリ１４０及び／又は追加メモリ１４５が、メモリ１１０の一部となっており、ＣＰＵ１０５によって共用される。或いは、表示メモリ１４０及び／又は追加メモリ１４５は、グラフィックサブシステム１３０専用に設けられた一つ又は複数の別個のメモリである。グラフィックサブシステム１３０は、表示装置１５０に表示される表示メモリ１４０からの画像の画素データを周期的に出力する。表示装置１５０は、コンピュータシステム１００からの信号に応答して視覚情報を表示することのできる任意の装置であり、当該表示装置１５０としては、ＣＲＴ、ＬＣＤ、プラズマ、及びＯＬＥＤディスプレイがある。コンピュータシステム１００は、表示装置１５０に、アナログ又はディジタル信号を提供することができる。
【００２１】
[0021]更なる実施の形態においては、グラフィック処理サブシステム１３０は、ＧＰＵ１３５と類似の、一つ又は複数の追加のＧＰＵ１５５を備えている。更に別の実施の形態においては、グラフィック処理サブシステム１３０は、グラフィックコプロセッサ１６５を備えている。グラフィック処理コプロセッサ１６５及び追加ＧＰＵ１５５は、ＧＰＵ１３５と並列に動作するようになっている。追加ＧＰＵ１５５は、ＧＰＵ１３５と同様に、レンダリングコマンドから出力画像用の画素データを生成する。追加ＧＰＵ１５５は、ＧＰＵ１３５と連動して、出力画像の異なる部分の画素データを同時に生成するか、又は、異なる出力画像の画素データを同時に生成するように動作することができる。ある実施の形態では、グラフィックコプロセッサ１６５は、ＧＰＵ１３５及び／又は追加ＧＰＵ１５５のために、幾何変換、シェーダ計算、背面カリング操作といったレンダリング関連のタスクを実行する。
【００２２】
[0022]追加ＧＰＵ１５５は、ＧＰＵ１３５と同じ回路基板上に位置し、ＧＰＵ１３５とデータバス１６０への接続を共用していてもよく、データバス１６０と別々に接続されている別の回路基板上に位置していてもよい。追加ＧＰＵ１５５はまた、ＧＰＵ１３５と同じモジュール又はチップパッケージに集積されていてもよい。追加ＧＰＵ１５５は、表示メモリ１４０及び追加メモリ１４５と類似の、独自の表示及び追加のメモリを備えていてもよく、ＧＰＵ１３５とメモリ１４０及び１４５を共用していてもよい。ある実施の形態では、グラフィックコプロセッサ１６５は、データバス１６０の制御に使用されるノースブリッジ又はサウスブリッジチップのようにコンピュータシステムチップセット（不図示）に集積されている。
【００２３】
[0023]図２に、本発明の実施の形態の実施に適したグラフィック処理サブシステムのストリーム処理ユニットのチェイン２００の例を示す。ストリーム処理ユニットのチェイン２００は、ストリーム処理モデルを使用しており、当該ストリーム処理モデルにおいては、入力要素が、ストリーム処理ユニットのチェイン２００によって連続して読み取られ、操作される。チェイン２００の各ストリーム処理ユニットは、当該チェイン内の前のストリーム処理ユニットの出力を操作することができる。以下で詳細に論じるように、ストリーム処理ユニットの一部又は全部をプログラム制御可能とすることができる。プログラム制御可能なストリーム処理ユニットは、入力要素を読み取り、その入力要素を使ってプログラムを実行し、チェイン内の次のストリーム処理ユニットに結果を出力する。各ストリーム処理ユニットは、独立に、又は別のストリーム処理ユニットプログラムと連動して動作する独自の別個のプログラムを有することが可能である。
【００２４】
[0024]入力ストリーム２０５は、所望の一つ又は複数のレンダリング画像を定義するために使用されるレンダリングコマンド及びデータを含んでおり、当該レンダリングコマンド及びデータは、場面の幾何配置、照明、シェーディング、テクスチャ、動き、及び／又はカメラパラメータを含んでいる。頂点プロセッサ２１０は、入力ストリーム２０５から、各レンダリングコマンド及び任意の関連データを読み取る。レンダリングデータは、一つ又は複数の未変換の頂点を含み得る。頂点プログラムは、頂点シェーダとも呼ばれるものであり、頂点プロセッサ２１０によって、各未変換の頂点に対して実行され、変換された頂点を生成する。頂点プロセッサ２１０はプログラム制御可能であり、レンダリングアプリケーションは、任意の所与の頂点集合に使用されるべき頂点プログラムを指定することができる。ある簡単な実施の形態では、頂点プログラムは、頂点を、３次元ワールド座標系から２次元画面座標系に変換する。より複雑な頂点プログラムを使用して、照明及びシェーディング、手続き的幾何配置、並びに、アニメーションオペレーションを含む、様々な視覚効果を実施することも可能である。
【００２５】
[0025]変換された頂点は、頂点プロセッサ２１０からラスタライズステージ２１５に渡される。ラスタライズステージ２１５は、一つ又は複数の頂点を、点、線、三角形、四辺形などの幾何プリミティブにする。次いで、ラスタライズステージ２１５は、各幾何プリミティブを、一つ又は複数の画素フラグメントに変換する。画素フラグメントは、状態を提供して、その画素フラグメントによって「カバー」されるレンダリング画像内に表示される可能性のある一つ又は複数の画素の集合を更新する。各画素フラグメントは、関連の入力パラメータ、例えば、画面位置、テクスチャ座標、色値、法線ベクトル等を有する。
【００２６】
[0026]次いで、画素フラグメントは、ラスタライズステージ２１５からフラグメントプロセッサ２２０に渡される。フラグメントプロセッサ２２０は、各画素フラグメントに関連付けられた情報を用いて、表示される可能性のある各画素の出力色値を決定する。頂点プロセッサ２１０と同様に、フラグメントプロセッサもプログラム制御可能である。画素フラグメントプログラムは、画素シェーダとも呼ばれるものであり、各画素フラグメントに対して実行されて、画素の出力色値を決定する。画素フラグメントは頂点プログラムとは独立に動作するが、画素フラグメントプログラムは、前のストリーム処理ユニットによって作成されるか、又は、前のストリーム処理ユニットを介して渡される情報に依存していてもよく、当該情報には、頂点プログラムによって作成される情報を含む情報が含まれる。レンダリングアプリケーションは、任意の所与の画素フラグメントの集合に使用されるべき画素フラグメントプログラムを指定することができる。画素フラグメントプログラムを使って、照明及びシェーディング効果、反映、テクスチャマッピング及び手続き的テクスチャ生成を含む様々な視覚効果を実施することができる。加えて、頂点プログラム及び画素フラグメントプログラムの両者を、汎用計算処理、画像処理、信号処理のような視覚以外の目的に用いることもできる。
【００２７】
[0027]画素集合は、次いで、ラスタオペレーション及び格納ステージ段２２５に出力される。ラスタオペレーションステージ２２５は、画素集合を、レンダリング画像に統合する。画素は、前にそのレンダリング画像に書き込まれた画素との混合画素、又はマスク画素とすることができる。また、デプスバッファ、アルファバッファ、及びステンシルバッファを使って、もしあれば、レンダリング画像への各入力画素の寄与を決定することも可能である。次いで、各入力画素値と任意の前に格納された画素値との組み合わせが、レンダリング画像の一部としてフレームバッファに出力される。
【００２８】
[0028]図２の例には示していないが、ストリーム処理ユニットのチェイン２００に、別の種類のストリーム処理ユニットも含めてもよい。例えば、テッセレーションプロセッサは、高次曲面の記述を受け取り、頂点によって定義され、且つ、その高次曲面を近似し又は当該高次曲面に対応する幾何プリミティブの集合を生成することができる。次いで、幾何プリミティブの集合及びそれらに関連付けられた頂点を、前述のように、頂点プロセッサ、ラスタライザ、フラグメントプロセッサといったストリーム処理ユニットによって下流方向へ処理することができる。
【００２９】
[0029]図３に、連鎖シェーディングプログラム対を最適化する本発明の実施の形態に係る方法３００を示す。ステップ３０３において、二つの連鎖シェーディングプログラムの最適化が始まる。ある実施の形態では、アプリケーションが、これら二つのシェーディングプログラムをランタイムモジュールに伝達し、当該ランタイムモジュールが、各シェーディングプログラムを、最適化するための中間データ形式にコンパイルする。別の実施の形態では、各シェーディングプログラムを異なるプログラミング言語で表現することができ、ランタイムモジュールが、各シェーディングプログラムの言語に適したコンパイラを用いて、要求された中間データ形式でそのシェーディングプログラムのコンパイル版を生成することができる。代替の実施の形態では、ランタイムモジュールの全部又は一部分が、デバイスドライバに統合されている。
【００３０】
[0030]方法３００では、アプリケーションが、二つのシェーディングプログラムが連鎖されていること、即ち「リンク」されていることを、例えば、ＡＰＩコールを介してランタイムモジュールに接続することによって、明示的に指定することができる。或いは、ランタイムモジュールは、二つのシェーディングプログラムがリンクされているか否かを暗黙的に決定することもできる。例えば、ランタイムモジュールは、グラフィック処理サブシステムの様々なストリーム処理ユニットによって実行されるべきシェーディングプログラムを解析して、第１のシェーディングプログラムの任意の出力が、第２シェーディングプログラムの入力として使用されるか否かを判定することができる。
【００３１】
[0031]方法３００は、下流フェーズ３０５と上流フェーズ３２０の二つのフェーズに分かれている。以下で詳細に論じるように、方法３００は、下流フェーズ３０５及び上流フェーズ３２０を、両シェーディングプログラムにおける全てのシェーダ間最適化が完全に検出されるまで反復する。下流フェーズ３０５は、別の連鎖シェーディングプログラムから見てストリーム処理ユニットのチェイン内の「下流」で実行されるシェーディングプログラムを最適化する。逆に、方法３００の上流フェーズ３２０は、別の「下流」シェーディングプログラムから見てストリーム処理ユニットのチェイン内の「上流」で実行されるシェーディングプログラムを最適化する。例えば、図２に示すストリーム処理ユニットのチェイン２００の例では、フラグメントプロセッサ２２０によって実行されるフラグメントシェーディングプログラムが、頂点プロセッサ２１０によって実行される頂点プログラムから見て「下流」とみなされるはずである。この例では、頂点及びフラグメントシェーディングプログラムが連鎖されている場合、方法３００の下流フェーズ３０５は、フラグメントシェーディングプログラムを最適化することになり、方法３００の上流フェーズ３２０は、頂点シェーディングプログラムを最適化することになる。
【００３２】
[0032]方法３００の下流フェーズ３０５は、下流シェーディングプログラムのエントリ関数であるステップ３０７から開始する。下流シェーディングプログラムのエントリ関数は、ストリーム処理ユニットが、下流シェーディングプログラムの実行を開始するところにある。また、エントリ関数の入力及び出力パラメータも識別される。
【００３３】
[0033]ステップ３０９で、方法３００は、下流シェーディングプログラム出力に基づいて、有用なコードを決定する。一実施形態では、ステップ３０９で、データフロー解析を使用して、プログラム実行を、下流シェーディングプログラムの出力から下流シェーディングプログラムのエントリ関数まで遡ってトレースする。下流シェーディングプログラムの出力の決定に関与する下流シェーディングプログラムの部分が、有用なコードに指定される。最適化が下流シェーディングプログラムの出力に影響を及ぼさないようにするために、データフロー解析は、有用なコードを指定するに際して慎重でなければならない。二つ以上の代替の実行分岐を使用して下流シェーディングプログラムの出力を決定する場合、これらの実行分岐の全てが有用なコードに指定されなければならない。また、データフロー依存関係解析によって、ループ構築及びプロシージャコールを正確に考慮しなければならない。
【００３４】
[0034]ステップ３１１では、定数の伝播が実行される。定数の伝播は、可能な場合、追加のプログラムパラメータ値を事前に計算し、又は実行分岐を事前に選択するために、定数である任意のプログラムパラメータを特定し、これらのプログラムパラメータの値を、下流シェーディングプログラムを介して伝播する。例えば、下流シェーディングプログラム出力が一つ又は複数のプログラムパラメータから計算され、ステップ３１１で、これらのプログラムパラメータの一つ又は複数が定数値を有すると判定する場合、下流シェーディングプログラムの出力の中間又は最終の値が事前計算され得る（導出された定数又はユニフォームともいう）。別の例では、一つ又は複数のプログラムパラメータを使用して、下流シェーディングプログラムの実行分岐を選択し、ステップ３１１で、これらのプログラムパラメータの一つ又は複数が既知の定数値を有すると判定した場合、適切な実行分岐が実行用に事前選択される。
【００３５】
[0035]方法３００のステップ３１３は、不要なコードを識別して除去する。不要なコードは、下流シェーディングプログラム出力の決定に関与しない下流シェーディングプログラムの部分、すなわち、ステップ３０９で有用なコードに指定されなかった下流シェーディングプログラムの部分である。また、不要なコードは、ステップ３１１の定数の伝播によって余分となった下流シェーディングプログラムの部分も含む。これは、例えば、ステップ３１１において事前計算された定数で置き換えられるプログラムパラメータを計算するために使用される下流シェーディングプログラムの部分を含む。加えて、不要なコードは、例えば、ステップ３１１において実行用に事前選択されなかった下流シェーディングプログラムの代替の実行分岐を含むことがある。次いで、ステップ３１３で下流シェーディングプログラムから不要なコードを除去し、それによって、性能を向上させ、下流シェーディングプログラムのサイズを縮小する。
【００３６】
[0036]下流シェーディングプログラムの残りの部分から、ステップ３１５で、下流シェーディングプログラムの出力に影響を及ぼす下流シェーディングプログラムの入力を決定する。この下流プログラム入力の集合は、以下で論じる、後のステップ３２５で利用される。
【００３７】
[0037]ステップ３３３、３３５、及び３３７は論理的に独立しており、任意の順序で実行することができ、又は並列に実行することができる。
【００３８】
[0038]ステップ３１５及び下流フェーズ３０５の反復の終わりに、上流フェーズ３２０の反復が、上流シェーディングプログラムを最適化するためにステップ３２３で開始する。ステップ３２３では、上流シェーディングプログラムのエントリ関数を求める。上流シェーディングプログラムのエントリ関数は、ストリーム処理ユニットが上流シェーディングプログラムの実行を開始するところにある。また、エントリ関数の入力及び出力パラメータも識別される。
【００３９】
[0039]方法３００のステップ３２５は、上流シェーディングプログラムの出力の部分集合に基づいて有用なコードを決定する。この上流シェーディングプログラムの出力の部分集合は、ステップ３１５で識別された下流プログラムの入力の集合に対応する上流シェーディングプログラムの出力の全部又は一部分である。ある実施の形態では、ステップ３２５はデータフロー解析を使用して、プログラム実行を、上流シェーディングプログラム出力の部分集合から上流シェーディングプログラムのエントリ関数まで遡ってトレースする。上流シェーディングプログラムの出力の部分集合の決定に関与する上流シェーディングプログラムの部分が、有用なコードに指定される。上流シェーディングプログラムの出力の部分集合を計算する際に使用されない上流シェーディングプログラムの部分は、上流シェーディングプログラムの出力の部分集合の一部ではない他の上流シェーディングプログラムの出力を算出する際に使用される上流シェーディングプログラムの部分を含め、有用なコードとしては指定されない。最適化が、上流シェーディングプログラムの出力に影響を及ぼさないようにするために、データフロー解析は、有用なコードの指定に際して慎重でなければならない。二つ以上の代替の実行分岐を使用して、上流シェーディングプログラムの出力の部分集合を決定する場合には、これらの実行分岐の全てが有用なコードに指定されなければならない。また、データフロー依存関係解析によって、ループ構築及びプロシージャコールを正確に考慮しなければならない。
【００４０】
[0040]ステップ３２７では、定数の伝播が行われる。定数の伝播は、可能な場合、別のプログラムパラメータを事前に計算し、又は実行分岐を事前に選択するために、定数である任意のプログラムパラメータを識別し、これらのプログラムパラメータの値を、上流シェーディングプログラムを介して伝播する。一例として、ステップ３２７の定数の伝播は、上流シェーディングプログラムの出力が、ステップ３２７で定数値を持つと判定された一つ又は複数のプログラムパラメータから計算される場合に、その上流シェーディングプログラムの出力の中間値又は最終値を事前に計算することができる。別の例として、ステップ３２７は、当該ステップ３２７が、適切な実行分岐を選択するために使用される一つ又は複数のプログラムパラメータが一定であると判定する場合に、実行用の幾つかの代替プログラム分岐のうちの一つを事前に選択することができる。
【００４１】
[0041]方法３００のステップ３２９では、上流プログラム中の不要なコードを識別して除去する。前述のものと同様に、不要なコードは、上流シェーディングプログラムの出力の部分集合の決定に関与しない上流シェーディングプログラムの部分である。これは、ステップ３２５で有用なコードに指定されなかった上流シェーディングプログラムの部分を含む。また、不要なコードは、事前計算された定数で置き換えらるプログラムパラメータを計算するために使用される上流シェーディングプログラムの部分や、実行のために事前選択されなかった上流シェーディングプログラムの代替の実行分岐など、ステップ３２７の定数の伝播によって余分になった上流シェーディングプログラムも含む。ステップ３２９では、上流シェーディングプログラムから不要なコードを除去し、それによって、実行性能を向上させ、上流シェーディングプログラムのサイズを縮小する。
【００４２】
[0042]ステップ３３１は、上流及び下流シェーディングプログラムを最適化するために、下流フェーズ３０５及び上流フェーズ３２０のさらなる反復が必要とされるか否かを判定する。ステップ３３１は、上流シェーディングプログラムの出力の部分集合のいずれかが、ステップ３１１によって下流シェーディングプログラムの定数値出力であると以前に解析されていない定数であるか否かを判定する。上流シェーディングプログラムの出力の部分集合のいずれかが、以前にステップ３１１によって解析されていない定数である場合には、方法３００は、ステップ３１７に進む。
【００４３】
[0043]ステップ３１７は、ステップ３３１で識別された上流プログラム出力の部分集合の定数値の出力を、対応する下流シェーディングプログラム入力とマッチングさせる。次いで、これらの下流シェーディングプログラム入力が、定数値の下流シェーディングプログラム入力に指定される。次いで、方法３００の下流フェーズ３０５が、ステップ３１１から繰り返される。ステップ３１１の第２の反復及びそれに続く反復時には、ステップ３１７で指定された定数値の下流シェーディングプログラム入力を用いて定数の伝播が行われる。恐らく、ステップ３１１は、定数値の下流プログラム出力又は中間値を計算するコードや、不使用の実行分岐のためのコードなど、下流シェーディングプログラムの追加の部分が余分になる結果をもたらす。次いで、これらの下流シェーディングプログラムの更なる余分な部分が、ステップ３１５で除去され、それによって、実行性能がさらに改善され、下流シェーディングプログラムのプログラムサイズが縮小される。
【００４４】
[0044]恐らく、下流シェーディングプログラムからの不要なコードの除去により、下流シェーディングプログラム出力の数が減少し、さらに、使用される下流シェーディングログラム入力の数も減少する。下流シェーディングプログラム入力数の減少は、対応する上流シェーディングプログラム出力の一部、したがって、上流シェーディングプログラム自体の別の部分を不要にすることができ、したがって、上流シェーディングプログラムの更なる最適化を可能にする。
【００４５】
[0045]このために、ステップ３１１及び３１３の更なる反復に続いて、ステップ３１５は、下流シェーディングプログラムの残りの部分から、下流シェーディングプログラムの出力に影響を及ぼす下流シェーディングプログラムの入力を決定する。ステップ３１５に続いて、方法３００の上流フェーズ３２０の更なる反復が、ステップ３１５で識別された下流プログラムの入力の集合をステップ３２５で上流プログラム出力の部分集合として利用しつつ、実行される。方法３００の上流フェーズ３２０の更なる反復は、上流シェーディングプログラムを更に最適化するために行われる。ステップ３２３、３２５、３２７及び３２８が、ステップ３１５の最新の反復時に識別された下流プログラムの入力の集合を用いて繰り返される。恐らく、これは、上流シェーディングプログラムの更なる余分なコードの識別及び除去をもたらす。その結果、上流シェーディングプログラムの実行性能が更に改善され、上流シェーディングプログラムのサイズが更に縮小される。
【００４６】
[0046]前述のように、ステップ３３１は、上流及び下流シェーディングプログラムを最適化するために、下流フェーズ３０５及び上流フェーズ３２０の更なる反復が必要とされるか否かを判定する。上流シェーディングプログラムの出力の部分集合のいずれかが、以前にステップ３１１によって解析されていない定数である場合には、方法３００は、ステップ３１７に進み、引き続き下流フェーズ３０５及び上流フェーズ３２０を更に反復する。そうでない場合、方法３００は、ステップ３３３に進む。
【００４７】
[0047]ステップ３３３は、最適化された下流シェーディングプログラムを、その中間データ形式から、ストリーム処理ユニットが実行することのできる実行可能形式に変換する。ある実施の形態では、実行可能形式は、ストリーム処理ユニットの特有のハードウェアアーキテクチャに合わせて調整されたアセンブリ又は機械語コードの形態をとる。ステップ３３３はまた、下流シェーディングプログラムへの追加の最適化、例えば、ループの展開などを行ってもよい。前述の最適化と異なり、これらの追加の最適化は、下流と上流のシェーディングプログラムの間の関係に基づくものではなく、ストリーム処理ユニットのハードウェアアーキテクチャに基づくものである。
【００４８】
[0048]同様に、ステップ３３では、最適化された上流シェーディングプログラムを、その中間データ形式から、ストリーム処理ユニットが実行することのできる実行可能形式に変換する。ある実施の形態では、実行可能形式は、ストリーム処理ユニットの特有のハードウェアアーキテクチャに合わせて調整されたアセンブリ又は機械語コードの形態をとる。ステップ３３５はまた、下流シェーディングプログラムへの追加の最適化、例えばループ展開などを行ってもよい。前述の最適化と異なり、これらの追加の最適化は、下流と上流のシェーディングプログラムの間の関係に基づくものではなく、ストリーム処理ユニットのハードウェアアーキテクチャに基づくものである。
【００４９】
[0049]ステップ３３７は、最適化された上流シェーディングプログラムの出力に影響を及ぼす上流シェーディングプログラム入力を決定する。最適化された上流シェーディングプログラムの出力を決定する際に使用されない上流シェーディングプログラムの入力がある場合には、ステップ３３７は、メモリからこれらの入力をフェッチするために使用されるコードを除去する。この更なる最適化は、使用されない入力値をフェッチするためにメモリ帯域幅を無駄にすることを防ぐ。次いで、ステップ３３９で、最適化された上流及び下流シェーディングプログラムを、実行のために、それぞれのストリーム処理ユニットに転送する。
【００５０】
[0050]別の実施の形態では、方法３００を拡張して、任意の数の連鎖シェーディングプログラムを順次最適化することが可能である。この実施の形態は、最適化されるべき連鎖シェーディングプログラムの集合から、二つの連鎖シェーディングプログラムからなる対を選択する。選択された連鎖シェーディングプログラム対について、この実施の形態は、前述のステップ３０３から３３１までを実行し、恐らく、簡略化されたプログラム対をもたらす。次いで、この実施の形態は、最適化されるべき連鎖シェーディングプログラムの集合から別の連鎖シェーディングプログラム対を選択し、新しく選択された連鎖シェーディングプログラム対について、再度、ステップ３０３から３３１までを繰り返す。それ以上の最適化が不可能になるまで、連鎖シェーディングプログラム対の全ての可能な組み合わせについて、ステップ３０３から３３１までがさらに繰り返される。それ以上の最適化が不可能になった時点で、ステップ３３３、３３５、及び３３７のハードウェアコード生成及び入力除去を、シーケンス中の全てのシェーディングプログラムについて実行することができる。この実施の形態における連鎖シェーディングプログラム対は、必ずしも、相互に排他的ではないことに留意すべきである。例えば、単一の上流シェーディングプログラムが、二つ以上の下流シェーディングプログラムと連鎖していてもよく、第１の連鎖シェーディングプログラム対の下流シェーディングプログラムが、第２の連鎖シェーディングプログラム対の上流シェーディングプログラムであってもよい。
【００５１】
[0051]別の実施の形態では、方法３００が、一定値について連鎖シェーディングプログラムを最適化することができる。一定値とは、シェーディング言語における専門用語であり、所与のデータストリームの処理の間には一定のままであるが、このようなストリームデータのバッチ間で値を変更し得る値を指す。一定値の最適化は、前述の定数値の場合と同様の手法で実行することができる。例えば、ステップ３１１、３１７、３２７、及び３３１を、定数値に加えて一定値を用いて、前述のように実行することが可能である。しかしながら、一定値の伝播の結果として不要なコードが識別されて除去された場合には、連鎖シェーディングプログラムは、一定値の変更が連鎖シェーディングプログラムの別の部分を不要なコードとするときに、再最適化されなければならない。
【００５２】
[0052]方法３００の処理を図４〜６に示す。図４〜６は、上流及び下流シェーディングプログラムの例に及ぼす方法３００の影響を示している。表１及び２に、それぞれ、ＯｐｅｎＧＬシェーディング言語で書かれた連鎖のフラグメント及び頂点シェーディングプログラムの最適化されていないソースコードを示す。しかしながら、別の言語で書かれていてもよい。表１のフラグメントシェーディングプログラムは、五つの一定の（Ｕｎｉｆｏｒｍ）スカラ変数、四つの可変（Ｖａｒｙｉｎｇ）スカラ変数、及び一つの可変ベクトル変数を含む、幾つかのプログラム変数を定義している。同様に、表２の頂点シェーディングプログラムは、三つの一定のスカラ変数及び三つの可変スカラ変数を定義している。この例では、フラグメントシェーディングプログラムと頂点シェーディングプログラムの両者が、可変変数「ｖａｒｙｉｎｇ１」、「ｖａｒｙｉｎｇ２」及び「ｖａｒｉｙｉｎｇ３」を含んでいる。これら二つのシェーディングプログラムを相互に連鎖させると、上流の頂点シェーディングプログラムで求められたこれらの共通変数の値は、下流のフラグメントシェーディングプログラムを実行するときに持ち越される。表１及び表２の一定の変数に続くコメントは、最適化時に想定されるこれらの一定値を示している。
【表１】
2008505422.tif 000003
【表２】
2008505422.tif 000004
【００５３】
[0053]図４Ａ、４Ｂ、５Ａ、５Ｂ、６Ａ及び６Ｂは、データフローフォーマットを用いて、連鎖シェーディングプログラム対の例の最適化を示す。このデータフローフォーマットは、シェーディングプログラム出力と、これらの出力を計算するために使用される入力変数及びオペレーションの間の関連を示すものである。図４Ａ及び４Ｂには、表１及び２の連鎖シェーディングプログラム対の例が、最適化されていない形で示されている。
【００５４】
[0054]図４Ａは、表１のフラグメントシェーディングプログラムの例の一部分のデータフロー図４００を示している。データフロー図４００には、一定の変数４０７、４０９、４１１、４１３、４３１、及び４３３と可変変数４１５、４１７、４１９、４２０、及び４２１の組み合わせから形成される出力変数４０５が示されている。また、データフロー図４００は、一定変数と可変変数の両方に基づく条件分岐ステートメント４２５及び４２７と、式４３０、４３２、４３４など、完全に一定変数から導出される式も含んでいる。
【００５５】
[0055]図４Ａと同様に、図４Ｂは、表２の頂点シェーディングプログラムの例のデータフロー図４５０を示している。データフロー図４５０は、例示の頂点シェーディングプログラムの出力変数４５５、４５７、４５９、４６１、及び４６５と、それらの入力変数との関係が示されている。前述のように、表１及び表２の例示のシェーディングプログラムが相互に連鎖されている場合に、出力変数「ｖａｒｙｉｎｇ１」４５５、「ｖａｒｙｉｎｇ２」４５７、「ｖａｒｙｉｎｇ３」４５９、及び「ｖａｒｙｉｎｇ４」４６１は、フラグメントシェーディングプログラムの入力変数「ｖａｒｙｉｎｇ１」４１５、「ｖａｒｙｉｎｇ２」４１７、「ｖａｒｙｉｎｇ３」４１９、及び、「ｖａｒｙｉｎｇ４」と一致するが、図４Ａでは明確にするために省略されている。この例では、頂点シェーディングプログラムの出力変数の一部、例えば、「ｖａｒｙｉｎｇ５」４６３などが、連鎖フラグメントシェーディングプログラムによって使用されないことに留意すべきである。しかしながら、これらの出力変数は、頂点シェーディングプログラムの例と連鎖されている他の下流シェーディングプログラムによって使用されることもある。加えて、データフロー図４５０は、入力属性４７０、４７２、及び４７４も示している。他の変数と異なり、属性は、シェーディングプログラムによって処理される、頂点などの各データ項目に関連付けられたパラメータである。
【００５６】
[0056]例示の連鎖シェーディングプログラムをステップ３０５からステップ３３１までの第１の反復によって処理した後には、この例示のシェーディングプログラムの複雑度が実質的に低減される。表３及び４は、ステップ３０７から３３１までの第１の反復後の例示の連鎖シェーディングプログラム対のソースコードを示している。図５Ａ及び５Ｂに、これらの例示の連鎖シェーディングプログラムをデータフローフォーマットで示している。
【表３】
2008505422.tif 000005
【表４】
2008505422.tif 000006
【００５７】
[0057]図５Ａに、表３の最適化されたフラグメントシェーディングプログラムに対応するデータフロー図５００を示す。データフロー図４００とデータフロー図５００を比較すると、ステップ３０７から３３１までの第１の反復後に、条件分岐４２５のステートメントが、あるバッチデータに対して一定である一定変数４０７の値に依存するものであるために、除去されていることがわかる。加えて、一定変数４１１及び４１３も、４３２に等価の導出された一定変数５０５で置き換えることができる。この例では、一定変数４０９を含む式４３４が、式４３４の値に等しい導出された一定値５０７で置き換えられている。一定値５０５及び５０７の使用によって、グラフィック処理サブシステムが式４３２及び４３４の値を繰り返し余分に計算する手間が省かれる。ユニフォーム変数４０７、４０９、４１１、又は４１３が別のバッチデータの値を変更する場合、このシェーディングプログラムの例は、再最適化されなければならない。
【００５８】
[0058]図５Ｂに、表４の最適化された頂点シェーディングプログラムに対応するデータフロー図５５０を示す。データフロー図４５０とデータフロー図５５０を比較すると、ステップ３０７から３３１までの第１の反復後、出力４６１が、例示の連鎖フラグメントシェーディングプログラムが、当該出力を使用しないために、除去されている。その結果、出力４６１を計算するために使用される全てのオペレーションを廃棄することができる。さらに、属性４７２が出力４６１を計算するためだけに使用されたために、属性４７２も廃棄される。よって、属性４７２は、プログラム実行中に、グラフィック処理サブシステムによってフェッチされることさえもなくなり、メモリ帯域幅が節約される。加えて、最適化されていないシェーディングプログラムにおける一定変数４８０及び４８２も、データフロー図４５０内の式４８５の値に等しい導出された一定変数５５５で置き換えられる。
【００５９】
[0059]図５Ａ及び５Ｂの最適化されたシェーディングプログラムを、図４Ａ及び４Ｂのそれらの最適化されていないバージョンと比較すると、ステップ３０７から３３１までの第１の反復が、連鎖シェーディングプログラムを大幅に簡略化することがわかる。上述したように、ステップ３３１は、上流シェーディングプログラムの出力のいずれかが、以前に考慮されていない定数又は一定値であるか否かを判定する。この例では、図５Ｂの頂点シェーディングプログラムの第１の最適化反復で、出力４５５及び４５７が、両者とも、所与のバッチデータについて一定である一定値であると判定する。可変出力変数「ｖａｒｙｉｎｇ１」４５５は、導出された一定値５５５に等しい。同様に、出力変数「ｖａｒｙｉｎｇ２」４５７は、一定値５６０に等しい。したがって、ステップ３０７から３３１までを反復し、頂点シェーディングプログラムの出力４５５及び４５７に対応するフラグメントシェーディングプログラムの入力４１５及び４１７を定数として使用して、連鎖シェーディングプログラム対を更に最適化することが可能である。
【００６０】
[0060]表５及び表６に、ステップ３０７から３３１までの第２の反復後の例示の連鎖シェーディングプログラム対のソースコードを示す。同様に、図６Ａ及び図６Ｂに、この第２の最適化反復後の例示の連鎖シェーディングプログラム対を、データフローフォーマットで示す。
【表５】
2008505422.tif 000007
【表６】
2008505422.tif 000008
【００６１】
[0061]図６Ａのデータフロー図６００は、図４Ａのデータフロー図４００に示すフラグメントシェーディングプログラムの最適化版である。これら二つの図を比較すると、条件分岐４２７が除去されていることがわかる。これは、定数として扱われる可変入力変数４１５及び４１６をもつ条件分岐４２７を評価した結果であり、これは、例示の頂点シェーディングプログラムの前の最適化反復で決定されたものである。加えて、フラグメントシェーディングプログラム中の全てのオリジナルの一定値も、導出された一定値で置き換えられており、それによって、余分な計算が除去される。
【００６２】
［0062］図６Ｂのデータフロー図６５０に、第２の最適化反復の結果を示す。この図を、対応する最適化されていない図４５０と比較すると、可変出力変数４５５及び４５７が除去されていることがわかる。これらの出力変数の両者が連鎖下流シェーディングプログラムに一定値を出力するので、これらの値を、上流頂点シェーディングプログラムにおいて除去して、連鎖下流シェーディングプログラムにおいて定数で置き換えることが可能である。
【００６３】
[0063]この例では、ステップ３０７から３３１までの第２の反復の後には、上流シェーディングプログラムに位置する新しい定数又はユニフォーム出力がない。したがって、ステップ３３１の後、方法３００は、更なる最適化及びコード生成のために、ステップ３３３に進む。更なる最適化には、複数の命令を単一の効率の良い命令で代用することがある。例えば、加算命令が後に続く乗算命令は、単一の乗算及び積算命令で置き換えることができる。グラフィック処理サブシステムのパイプライン化ハードウェアを利用するよう更なる最適化が行われてもよい。例えば、スケジューリングを改善するために、命令をインターリーブさせることも可能である。表７及び表８は、ステップ３３９に続く例示の連鎖シェーディングプログラム対を示す。
【表７】
2008505422.tif 000009
【表８】
2008505422.tif 000010
【００６４】
[0064]表７のフラグメントシェーディングプログラムは、表１の最適化されていない例示のフラグメントシェーディングプログラムと対応する。これら二つの表のプログラムコードを比較すると、方法３００が、フラグメントシェーディングプログラムを、十数行の高レベルシェーディング言語コードから、わずか二つのアセンブリ言語命令に縮小することがわかる。同様に、表２の頂点シェーディングプログラムの例は、その元の形態における約１０命令から、表８における６命令に最適化される。
【００６５】
[0065]図７は、本発明の実施の形態の実施に適したシェーディング言語アーキテクチャ７００を示す。シェーディング言語アーキテクチャは、アプリケーション７０５を含む。ある実施の形態では、アプリケーション７０５は、グラフィック処理サブシステム７４０に命令して、一つ又は複数の３次元オブジェクトをレンダリングするようになっている。アプリケーション７０５は、幾何配置、照明、及びテクスチャのデータを含む、レンダリングされるべきオブジェクトを定義するオブジェクトデータ７１０をロードする。また、アプリケーション７０５はまた、上流７１５と下流７２０のシェーディングプログラムからソースコードもロードする。ある実施の形態では、上流７１５と下流７２０のシェーディングプログラムを、それぞれ、頂点シェーディングプログラムとフラグメントシェーディングプログラムとすることができる。
【００６６】
[0066]上流７１５と下流７２０のシェーディングプログラムを使ってオブジェクトをレンダリングするために、アプリケーション７０５は、シェーディングプログラムを、ＡＰＩドライバ７２５に送る。加えて、アプリケーション７０５は、ＡＰＩドライバ７２５に当該ＡＰＩドライバに指令するコマンドを送り、上流７１５と下流７２０のシェーディングプログラムを相互に連鎖させて、連鎖させたシェーディングプログラムをコンパイルし、最適化する。ストリーム処理言語コンパイラ７３０は、ある実施の形態ではＡＰＩドライバ７２５の一部であり、シェーディングプログラムのコンパイルと最適化を行う。代替の実施の形態では、ストリーム処理言語コンパイラ７３０は、ＡＰＩドライバ７２５又はアプリケーション７０５と動的にリンクされる外部モジュール又はライブラリである。
【００６７】
[0067]アプリケーション７０５は、次いで、オブジェクトデータ７１０をＡＰＩドライバ７２５に、当該オブジェクトデータ７１０がレンダリングされるべきであることを指示するコマンドと共に送る。その結果、ＡＰＩドライバ７２５は、オブジェクトデータ７１０、並びに、連鎖シェーディングプログラム７１５及び７２０のコンパイル済みの最適化版を、グラフィック処理サブシステム７４０に送る。グラフィック処理サブシステム７４０は、連鎖シェーディングプログラムを実行して、オブジェクトデータ７１０を処理し、オブジェクトをレンダリングする。
【００６８】
[0068]本発明は、ストリーム処理プログラム間の関係に基づいてストリーム処理プログラムを最適化するシステムを提供するものである。本発明は、コンピュータグラフィックアプリケーションで使用されるストリーム処理システムを参照して論じられているが、本発明は、オーディオアプリケーション及び通信アプリケーションを含む、二つ以上のプログラム制御可能なストリーム処理ユニットを備える任意のストリーム処理システムに適用することができる。本発明を、本発明の特定の例及び実施形態に関して論じてきたが、これらは、本発明の単なる例にすぎず、本発明を限定するものではない。よって、本発明の範囲は、特許請求の範囲によってのみ決定されるべきである。
【図面の簡単な説明】
【００６９】
【図１】本発明の実施の形態の実施に適したコンピュータシステムを示すブロック図である。
【図２】本発明の実施の形態の実施に適したグラフィック処理サブシステムのストリーム処理ユニットのチェインの例を示す図である。
【図３】連鎖シェーディングプログラム対を最適化する本発明の実施の形態に係る方法を示す図である。
【図４Ａ】連鎖シェーディングプログラムの例示の対の最適化されていない形で示す図である。
【図４Ｂ】連鎖シェーディングプログラム対の例を最適化されていない形態で示す図である。
【図５Ａ】本発明の実施の形態による最適化方法の第１の反復後の連鎖シェーディングプログラム対の例を示す図である。
【図５Ｂ】本発明の実施の形態による最適化方法の第１の反復後の連鎖シェーディングプログラム対の例を示す図である。
【図６Ａ】本発明の実施の形態による最適化方法の第２の反復後の連鎖シェーディングプログラム対の例を示す図である。
【図６Ｂ】本発明の実施の形態による最適化方法の第２の反復後の連鎖シェーディングプログラム対の例を示す図である。
【図７】本発明の実施の形態の実施に適したシェーディング言語アーキテクチャを示す図である。
【図１】
2008505422.tif 000011
【図２】
2008505422.tif 000012
【図３】
2008505422.tif 000013
【図４Ａ】
2008505422.tif 000014
【図４Ｂ】
2008505422.tif 000015
【図５Ａ】
2008505422.tif 000016
【図５Ｂ】
2008505422.tif 000017
【図６Ａ】
2008505422.tif 000018
【図６Ｂ】
2008505422.tif 000019
【図７】
2008505422.tif 000020
【手続補正書】
【提出日】平成19年3月5日(2007.3.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ストリーム処理システムによって実行されるようになっているストリーム処理プログラムを最適化する方法であって、該ストリーム処理システムが第１及び第２のプログラム制御可能なストリーム処理ユニットを備え、前記第２のストリーム処理ユニットが前記第１のストリーム処理ユニットに接続されて、前記第１のストリーム処理ユニットの出力が前記第２のストリーム処理ユニットの入力になっており、該方法が、
第１のストリーム処理ユニットによって実行されるようになっている第１のストリーム処理プログラムを受け取るステップであって、該第１のストリーム処理プログラムが出力パラメータを有する、該ステップと、
第２のストリーム処理ユニットによって実行されるようになっている第２のストリーム処理プログラムを受け取るステップであって、該第２のストリーム処理プログラムが、前記第１のストリーム処理プログラムの前記出力パラメータに対応する入力パラメータを有する、該ステップと、
前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の対応関係に基づいて、前記第１及び第２のストリーム処理プログラムを最適化するステップと、
を含む方法。
【請求項２】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第１のストリーム処理プログラムから、前記第２のストリーム処理プログラムによって使用されない追加の出力パラメータを計算するようになっている不要なプログラムコードを除去するステップを含む、請求項１に記載の方法。
【請求項３】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、
前記第１のストリーム処理プログラムの前記出力パラメータが定数であるという判定に応答して、前記第２のストリーム処理プログラムの前記入力パラメータ用の定数値を伝播するステップと、
前記第２のストリーム処理プログラムから、定数値を伝播した結果として余分になった不要なプログラムコードを除去するステップと、
を含む、請求項１に記載の方法。
【請求項４】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、
前記第１のストリーム処理プログラムの前記出力パラメータが一定値であるという判定に応答して、前記第２のストリーム処理プログラムの前記入力パラメータ用の一定値を伝播するステップと、
前記第２のストリーム処理プログラムから、一定値を伝播した結果として余分になった不要なプログラムコードを除去するステップと、
を含む、請求項１に記載の方法。
【請求項５】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の前記対応関係に基づいて、前記第１及び第２のストリーム処理プログラムが最適化されるまで、前記第２のストリーム処理プログラムと前記第１のストリーム処理プログラムを交互に最適化する複数回の反復を含む、請求項１に記載の方法。
【請求項６】
情報処理デバイスにステップのセットを実行するよう指令するようになっているプロセッサ命令のセットを含む情報記憶媒体であって、該情報処理デバイスが、第１及び第２のプログラム制御可能なストリーム処理ユニットを有するストリーム処理システムを備え、前記第２のストリーム処理ユニットが前記第１のストリーム処理ユニットに接続されて、前記第１のストリーム処理ユニットの出力が前記第２のストリーム処理ユニットの入力になっており、前記ステップのセットが、
第１のストリーム処理ユニットによって実行されるようになっている第１のストリーム処理プログラムを受け取るステップであって、該第１のストリーム処理プログラムが出力パラメータを有する、該ステップと、
第２のストリーム処理ユニットによって実行されるようになっている第２のストリーム処理プログラムを受け取るステップであって、該第２のストリーム処理プログラムが、前記第１のストリーム処理プログラムの前記出力パラメータに対応する入力パラメータを有する、該ステップと、
前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の対応関係に基づいて、前記第１及び第２のストリーム処理プログラムを最適化するステップと、
を含み、
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第２のストリーム処理プログラムの前記入力パラメータと前記第１のストリーム処理プログラムの前記出力パラメータの間の前記対応関係に基づいて、前記第１及び第２のストリーム処理プログラムが最適化されるまで、前記第２のストリーム処理プログラムと前記第１のストリーム処理プログラムを交互に最適化する複数回の反復を含む、
情報記憶媒体。
【請求項７】
前記第１及び第２のストリーム処理プログラムを最適化するステップが、前記第１のストリーム処理プログラムから、前記第２のストリーム処理プログラムによって使用されない追加の出力パラメータを計算するようになっている不要なプログラムコードを除去するステップを含む、請求項６に記載の情報記憶媒体。
【請求項８】
前記プログラム制御可能なストリーム処理ユニットの一つがプログラム制御可能な頂点プロセッサである、請求項６に記載の情報記憶媒体。
【請求項９】
画像をレンダリングするようになっており、請求項６に記載の情報記憶媒体を備える、グラフィック処理サブシステム。
【請求項１０】
前記グラフィック処理サブシステムがグラフィック処理ユニットを含む、請求項９に記載のシステム。
【国際調査報告】
2008505422.tif 000021