グラフィック演算処理チップ
【課題】 負荷が抑制された簡易なアルゴリズムによって記憶領域の断片化を抑制するができるグラフィック演算処理チップチップを提供することを目的とする。
【解決手段】 オンチップメモリ１０４は，互いに隣接し，それぞれが同じタイプのデータ種別を有するように区分された複数のサブ領域Ｓに分割されている。サブ領域Ｓ内における各データはそれぞれ連続する順列データとして記憶されるとともに，同順列データはそれぞれが他の順列データと隣接する態様にて記憶される。そして，各サブ領域Ｓに記録されるデータは，オンチップメモリ１０４に記録されている期間であるライフサイクル値がそれぞれ異なっており，ライフサイクル値が短いデータを含むサブ領域Ｓが，ライフサイクル値が長いデータを含むサブ領域Ｓと隣接して設けられている。
【解決手段】 オンチップメモリ１０４は，互いに隣接し，それぞれが同じタイプのデータ種別を有するように区分された複数のサブ領域Ｓに分割されている。サブ領域Ｓ内における各データはそれぞれ連続する順列データとして記憶されるとともに，同順列データはそれぞれが他の順列データと隣接する態様にて記憶される。そして，各サブ領域Ｓに記録されるデータは，オンチップメモリ１０４に記録されている期間であるライフサイクル値がそれぞれ異なっており，ライフサイクル値が短いデータを含むサブ領域Ｓが，ライフサイクル値が長いデータを含むサブ領域Ｓと隣接して設けられている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップに関する。
【背景技術】
【０００２】
従来３Ｄコンピュータ図形は，複雑な幾何学的な形に近似して，ポイント，線，および三角形のような簡単な幾何学的なプリミティブを使用して表現されている。既存のコンピュータグラフィックスハードウェアは，そのような簡単なプリミティブ，特に三角形のメッシュの処理を高速化するように最適化されており，様々な三角形，線，およびポイントを用いることで複雑な形に近似することができる。
【０００３】
このような３Ｄコンピュータ図形を処理する画像処理パイプラインは，複数の処理ステージを有する場合がある。それぞれが異なる処理ステージにおいては，サイズや更新頻度の異なるデータが処理されている。これらのデータを記録するために，それぞれ別のメモリを設けるのではプロセッサの大型化が避けられないことから，共通の統合されたメモリにて記憶がなされるのであるが，その場合メモリに記憶を転送するコストを最小限に抑えつつ記録を行うとメモリの断片化が発生しやすくなってしまう。
【０００４】
そこで，例えば特許文献１においては，この断片化を防ぐための記憶アルゴリズムが採用されている。このアルゴリズムはスウィッチングファブリック方式とよばれ，メモリ上の空きスペースを検索し，データの配列情報は仮想的にバッファ上に論理アドレスとして記録し，実際の物理アドレスには個々のデータを分割して配置する。このようなアルゴリズムを採用することによって，断片化した記憶領域であっても，データを記憶領域上に適切に配置できるため断片化による処理の低速化といった問題を抑制することはできる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許公開公報２００８−００７４４３０号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら，上述のような方式にあっては論理アドレスと物理アドレスとを関連付ける処理が複雑になりやすく，また物理アドレスの容量が大きいもの（例えば２５６以上のエレメントを有するもの）になった場合に空き領域を検索するアルゴリズムの負荷が過大になってしまうという問題があった。
【０００７】
そこで，本発明は，画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップにおいて，負荷が抑制された簡易なアルゴリズムによって記憶領域の断片化を抑制することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために本発明は，画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップであって，この記憶領域は，互いに隣接し，それぞれが同じタイプのデータ種別を有するように区分された複数のサブ領域に分割されている。そして，サブ領域内における各データはそれぞれ連続する順列データとして記憶されるとともに，同順列データはそれぞれが他の順列データと隣接する態様にて記憶され，
各サブ領域に記録されるデータは，同記憶領域に記録されている期間であるライフサイクル値がそれぞれ異なっており，ライフサイクル値が短い前記データを含むサブ領域は，ライフサイクル値が長いデータを含むサブ領域と隣接して設けられている。
また，このサブ領域は，隣接するサブ領域が境界部にデータが記録されていない場合に，当該隣接するサブ領域の境界部をサブ領域の記録領域として再割り当て可能に構成されている構成も可能である。
また，より一層の処理の高速化を図るために，サブ領域においては，前記データは循環バッファ形式にて記憶容量の割り当てが行われるようにすることもできる。
更に，サブ領域において，割当ビットマップにのっとってデータに対して記憶容量の割り当てを行うこともできる。
【発明の効果】
【０００９】
本発明によれば，負荷が抑制された簡易なアルゴリズムによって記憶領域の断片化を抑制することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は，本発明のＧＰＵを含むコプロセッサの概略構成を示すブロック図である。
【図２】図２は，データの統合された記録領域を示すブロック図である。
【図３】図３（ａ）〜（ｉ）は，メモリにデータを記録していく手順を示す概略図である。
【発明を実施するための形態】
【００１１】
以下，発明を実施するための形態について説明する。本発明は，以下に説明する実施態
様に限定されるものではない。本発明は，以下に説明する実施態様から当業者に自明な範
囲で適宜修正される範囲を含む。
【００１２】
本発明においける３Ｄ画像は，プリミティブを用いて表現されるものである。プリミティブはジオメトリの基本単位であり，３Ｄグラフィックスの場合，プリミティブはポリゴン（典型的には三角形），法線ベクトル，点などを含むことが通常である。プリミティブが三角形の場合は，各三角形は３つの頂点によって画定され，各線は２つの頂点によって画定される。各頂点が有するデータとしては，様々な属性，例えば，空間座標，明度，テクスチャ座標などと関連づけられている。
本明細書において，用語「シェーダ」は，一般にシェーディングを実行するＧＰＵのハードウェアサブユニットを参照するか又はシェーディングを実行するためのシェーダ（ハードウェア）によって使用されるメモリ例えばレジスタ記憶装置に次にロードされる，ＧＰＵにダウンロードされる命令セット又はトークンを参照するために使用され得る。用語「シェーダ」は，動作する双方を一緒に参照することもできる。用語「シェーダプログラム」は，一般にグラフィックスパイプラインに存在し実行するプログラム又はプロセスを参照し得て，画面上の最終的な画像の表面特性又は３次元画面環境におけるオブジェクトの決定／定義を支援するために使用される。「シェーダ」は，それらの特定のタスクを実行するために毎秒何十億の計算を実行可能である。
【００１３】
図１は，コプロセサ１００内のコンポーネントのブロック図である。コプロセサ１００は，単一の集積回路であってもよい。この例において，コプロセサ１００は，グラフィックスパイプライン１０１，プロセッサインタフェース１０２，メモリインタフェース１０３，オンチップメモリ１０４，メモリ調停回路１０５を含む。
【００１４】
３次元グラフィックスプロセサ１０１はグラフィックス処理タスクを行う。プロセサインタフェース１０２は，ＣＰＵとコプロセサ１００との間のデータおよび制御インタフェースを与える。メモリインタフェース１０３は，コプロセサ１００とオンチップメモリ１０４との間のデータおよび制御インタフェースを与える。この例においては，メモリがグラフィック画像処理チップであるコプロセッサ１００上に設けられた統合型のＧＰＵとして構成されている。
【００１５】
より詳細には，ＣＰＵは表示リストをメインメモリに保存し，バスインタフェースを介してポインタをコマンドプロセサ１０６に渡す。コマンドプロセサ１０６（これは以下で詳細に述べる頂点キャッシュ１０７を含む）は，ＣＰＵからコマンドストリームを取り込み，コマンドストリームおよび／またはメモリの中の頂点アレイから頂点属性を取り込み，属性タイプを浮動小数点フォーマットに変換し，得られた完全な頂点ポリゴンデータをレンダリング／ラスタ化のためにグラフィックスパイプライン１０１に渡す。以下でさらに詳細に説明するように，頂点データはコマンドストリームから，および／または各属性がそれ自身の線形アレイで保存されているメモリ中の頂点アレイから直接に来ることができる。メモリ調停回路１０５は，グラフィックスパイプライン１０１，コマンドプロセサ０６の間でのメモリアクセスを調停する。
【００１６】
グラフィックスパイプライン１０１は，頂点シェーダ１０８，ラスタライザ１０９，ジオメトリシェーダ１１０，ピクセルシェーダ１１１を含んで構成されている。
グラフィックスパイプライン１０１において，頂点シェーダ１０８は，頂点単位に様々な処理を行う。例えば，頂点の移動処理や，座標変換，ワールド座標変換，視野変換（カメラ座標変換），クリッピング処理，射影変換（透視変換，投影変換），ビューポート変換（スクリーン座標変換），光源計算等のジオメトリ処理が行われ，その処理結果に基づいて，オブジェクトを構成する頂点群について与えられた頂点データを変更（更新，調整）する。ジオメトリ処理後のオブジェクトデータ（オブジェクトの頂点の位置座標，テクスチャ座標，色データ（輝度データ），法線ベクトル，或いはα値等）は，オンチップメモリ１０４に保存される。
ラスタライザ１０９は，頂点シェーダ１０８から頂点データを受け取るか，オンチップメモリ１０４に保存されたデータを読み出してこれをエッジラスタ化，テクスチャ座標ラスタ化および色ラスタ化を実行するラスタライザへ３角形セットアップ情報を送信するセットアップユニットを含んでいる。
ジオメトリシェーダ１１０は，単一，または複数の頂点（複数）／ポイント（複数），ライン（複数）（２つの頂点セット），及び三角形（複数）（３つのラインセット）や多頂点形を含む異なるタイプのプリミティブの入力に対して処理を行い，入力されるプリミティブに基づいてパイプライン１０１内部に新しい幾何学的図形を生成することが可能である。ジオメトリシェーダ１１０の入力は，完全プリミティブ用頂点（ライン用の２つの頂点，三角形用の３つの頂点又はポイント用の単一頂点）及びエッジ隣接プリミティブ用頂点（ライン用の更なる２つの頂点，三角形用の更なる３つの頂点）データなどである。ジオメトリシェーダ１１０は，例えば１つのプリミティブを受信し得て，０，１又は複数のプリミティブのいずれかを出力できる。ジオメトリシェーダ１１０は，選択された単一のトポロジーを形成する複数頂点を出力できる。出力例の中には，三角形ストリップのようなトポロジー，ラインストリップ又はポイントリストを含む。エミットされたプリミティブの数は，任意のジオメトリシェーダ１１０の呼び出しの内部で変更できる。具体的な処理の一例としては，ポイントスプライト又はワイドラインテセレーション，ファー／フィン生成，シャドウボリューム生成，複数テクスチャ立方体表面に対する単一パスレンダリングなどが実行される。
ピクセルシェーダ１１１は光源や陰影の処理を行い，画像をピクセル単位で処理する。
【００１７】
続いて，図２からこのコプロセサ１００上に設けられたオンチップメモリ１０４の構造を説明する。このオンチップメモリ１０４には，プロセッサ上で取り扱われる入力データ，出力データ，及び処理途中のデータの全てが統合されて記憶されるものであり，外部メモリにデータが移され，内部でデータを保持する必要が無くなるまで使用されるものである。このオンチップメモリ１０４では，その記憶領域が複数のサブ領域Ｓへと分割されており，それぞれのサブ領域Ｓは対応するデータ種別を有するデータのみが記憶されるようになっている。そして，各サブ領域Ｓの前後には，隣接するサブ領域Ｓとの境界を示すスタート境界部２０１とエンド境界部２０２とが存在している。また，このオンチップメモリ１０４の記録単位は，一つにデータが記録可能なメモリエレメント２０３からなっている。
【００１８】
サブ領域Ｓ内では，一まとまりのデータアレイは各メモリエレメント２０３に間隔なく配置されており，各データアレイ同士は隣接して記憶されている。各データアレイはサブ領域Ｓのスタート境界部２０１に隣接するメモリエレメント２０３から順次空き領域を検索し，その容量を記憶可能なエリアがあり次第そこに記録されていく。同じサブ領域Ｓ内に含まれるデータであれば，その更新頻度やデータ長等は均質のものとなるため，データアレイは隙間なく配置可能となる。例えばあるサブ領域Ｓにおけるデータアレイの長さが３とした場合，既に配置されているデータアレイの割当が解除されて，そこに空き領域ができた場合も，同じデータ長のデータアレイがその後配置されることから，メモリエレメントの断片化が発生しにくく，データ割当も単純なアルゴリズムで実行可能である。
【００１９】
ここでは，サブ領域Ｓ０はインプット頂点の記憶領域に相当する。インプット頂点とは頂点シェーダ１０８に入力される頂点のデータであり，頂点の属性情報などを含んで記録されている。サブ領域Ｓ１は頂点シェーダコンテクスト，すなわち頂点シェーダ１０８において処理されている途中の頂点のデータが記録されている。頂点シェーダ１０８では，その処理の間に一時的に頂点の処理途中の状態を記録することがある。この頂点シェーダコンテクストは，頂点シェーダ１０８での処理が終わると割当は解放される。
サブ領域Ｓ２はアウトプット頂点の記録領域に相当する。アウトプット頂点とは頂点シェーダ１０８から出力される頂点のデータであり，このデータが再利用されて再び別シェーダで利用されることもあるため，記憶は比較的長期にわたって行われる。このアウトプット頂点がそのままジオメトリシェーダ１１０の入力値として活用することもできる。
サブ領域Ｓ３はジオメトリシェーダコンテクストの記録領域に相当する。ジオメトリシェーダ１１０において処理されている途中のプリミティブのデータが記録されている。ジオメトリシェーダ１１０では，その処理の間に一時的に頂点の処理途中の状態を記録することがある。このジオメトリシェーダコンテクストは，ジオメトリシェーダ１１０での処理が終わると割当は解放される。
サブ領域Ｓ４は，ジオメトリシェーダ１１０のアウトプットが記録される領域である。この領域は，ジオメトリシェーダ１１０での処理が終わるとデータが記録されることから，サブ領域Ｓ３が解放されると記憶がされるようになっている。
サブ領域Ｓ５は，ラスタライザ１０９での処理結果が記憶される領域である。また，サブ領域Ｓ６は，フラグメントシェーダコンテクスト，すなわちピクセルシェーダ１１１において処理されている途中の頂点のデータが記録されている。ピクセルシェーダ１１１では，その処理の間に一時的に頂点の処理途中の状態を記録することがある。このピクセルシェーダコンテクストは，ピクセルシェーダ１１１での処理が終わると割当は解放される。
【００２０】
ここで，これらのサブ領域Ｓ０〜Ｓ６の並びの順番には法則性を設けており，データの更新頻度が高い，あるいは記憶される期間の短いデータが記憶されるサブ記憶領域Ｓは，データの更新頻度が低い，あるいは記憶される期間の長いデータが記憶されるサブ記憶領域Ｓの間に挟まる形で設けられている。この更新頻度の違いをライフサイクル値と称する。更新頻度の高いデータはライフサイクル値が短く，更新頻度の低いデータはライフサイクル値が高い。例えば，頂点データコンテクストやジオメトリシェーダコンテクスト，フラグメントシェーダコンテクストが記憶されるサブ記憶領域Ｓ１，Ｓ３，Ｓ５は更新頻度が高い。これらのシェーダプログラムにおいては，その演算途中において一時期的処理結果が記憶・再利用されるため，メモリエレメント２０３への頻繁なアクセスと書き換えが発生している。
一方で，出力頂点データなどは，頂点シェーダ１０８の処理結果が記憶されるものであることから，そのデータは再度別のパイプラインのステージで再利用される場合を想定して，記憶される期間は長く設定されている場合が多い。本実施例ではこのように更新頻度の高いサブ領域Ｓと更新頻度の低い（換言すれば，長期間にわたってサブ領域Ｓに記憶されている）サブ領域Ｓとが交互に配置されている。
【００２１】
このように更新頻度の異なるサブ記憶領域Ｓが隣接することによる利点を次に説明する。
本実施例では，各サブ記憶領域Ｓのメモリエレメント２０３が必要に応じて増減されるアルゴリズムが採用されている。すなわち，サブ領域Ｓにおいて，記録に必要なメモリエレメント２０３が不足する場合，隣接するサブ領域Ｓの境界部分に位置するメモリエレメント２０３を自らの領域として取得する処理が行われる。具体的には，この処理はサブ領域Ｓ間のスタート境界部２０１やエンド境界部２０２が移動されることによって行われる。この際，隣接するサブ領域Ｓの各境界部２０１，２０２付近のメモリエレメント２０３にデータが記録されている場合，境界部２０１，２０２を移動してサブ領域Ｓのメモリエレメント２０３を増減することができない。そのため，前述したように更新頻度の高い，すなわちメモリエレメント２０３が解放されて空き領域ができやすいサブ領域Ｓと隣接することによって，サブ領域Ｓのサイズ変更がより柔軟に実施されやすくなる。
この際，サブ領域Ｓのサイズ変更を実施するか否かを判定するアルゴリズムとしては，例えば空いたメモリエレメント数が所定の値以下になった際において，隣接するサブ領域Ｓのメモリエレメント２０３に空きがある場合に境界部２０１，２０２の変更を行うという処理の手順や，割当されるデータアレイに必要なメモリエレメント数がサブ領域Ｓ内に存在するか否かを判定し，存在しないときに必要分を隣接するサブ領域Ｓのスタート境界部２０１付近から取得するといった手順を採用することができる。
【００２２】
また，本実施例においては，メモリエレメント２０３の構造としては循環バッファ構造が採用されてもよい。循環バッファ構造の場合，サブ領域Ｓ内のメモリエレメント２０３の最初と最後のものが連続して構成されている。この循環バッファの構成を図３を示して説明する。
図３（ａ）は，このサブ領域Ｓの初期状態を示している。このサブ領域Ｓは１０のメモリエレメント２０３から構成されており，この時サブ領域Ｓのスタート境界部２０１，及びエンド境界部２０２を示す境界部は一つ目のメモリエレメント２０３の位置に存在している。また，図示するような割当ビットマップ２０４を設け，実際にメモリエレメント２０３にデータアレイの割当，又は割当解除を行う前に，割当ビットマップ２０４上で記録するメモリエレメント２０３を決定して「０」か「１」かを記録し，この値を参照にしてメモリエレメント２０３への割当や割当解除を行うこともできる。このような処理を行うことによって，実際にメモリエレメント２０３に対して直接割当等を行う場合に比較して，単純なデータ構造で記録がなれている割当ビットマップ２０４の方が検索が容易であり，データが割当されたメモリエレメント２０３の間に割当解除がされたメモリエレメント２０３が存在して断片化が発生している場合などは，より効率的に処理を行うことができるようになる。
【００２３】
続いて図３（ｂ）に示されるように，次いでシーケンス状のデータアレイがメモリエレメント２０３の０〜４の５つのエリアに記録される。このとき割当ビットマップ２０４は，「１，１，１，１，１，０，０，０，０，０」となっている。この時，スタート境界部２０１はメモリエレメント２０３の「０」の左側，エンド境界部２０２はメモリエレメント○の「４」の右側に位置している。
続いて，図３（ｃ）に示されるように，最初に割り当てられた５つのデータアレイのうち最初の３つのデータアレイの割当が解除される。メモリエレメント２０３のうちアドレス「０」「１」「２」へのデータの割当が解除され，スタート境界部２０１は「３」の左側に移動される。このとき割当ビットマップ２０４は「０，０，０，１，１，０，０，０，０，０」となっている。
続いて，図３（ｄ）に示されるように，新たに６のデータ長からならデータアレイへの記憶領域の割り当てが行われる。この割当はエンド境界部２０２が移動され，６つ分のメモリエリア２０３がこの記憶領域としてあてはめられ，「５」「６」「７」「８」「９」「０」の順番で記憶される。割当後のスタート境界部２０１は「３」の左側，エンド境界部２０２は「０」の右側に移動されている。このとき割当ビットマップ２０４は「１，０，０，１，１，１，１，１，１」となっている。
【００２４】
続いて，図３（ｅ）に示されるように，アドレス「４」「６」「７」の割当解除がされる。この時，境界部２０１，２０２には移動は生じていない。割当ビットマップ２０４は「１，０，０，１，０，１，０，０，１，１」となっている。
続いて，図３（ｆ）に示されるように，新たに２のデータ長からならデータアレイへの記憶領域の割り当てが行われる。この割当はエンド境界部２０２が移動され，２つ分のメモリエリア２０３がこの記憶領域としてあてはめられ，「１」「２」の順番で記憶される。割当後のスタート境界部２０１は「３」の左側，エンド境界部２０２も「２」の右側に移動されている。このとき割当ビットマップ２０４は「１，１，１，１，０，１，０，０，１，１」となっている。
続いて，図３（ｇ）に示されるように，アドレス「３」に記憶されたデータの割当が解除される。この解除に伴い，スタート境界部２０１はアドレス「５」の左側に移動される。この際の割当ビットマップ２０４は「１，１，１，０，０，１，０，０，１，１」となっている。
【００２５】
続いて，図３（ｈ）に示されるように，アドレス「５」に記憶されたデータの割当が解除される。この解除に伴い，スタート境界部２０１はアドレス「８」の左側に移動される。この際の割当ビットマップ２０４は「１，１，１，０，０，１，０，０，１，１」となっている。
最後に，図３（ｉ）に示されるように，アドレス「８」「９」「０」「１」「２」に記憶されているデータの割当が解除される。この時は，スタート境界部２０１がエンド境界部２０２と隣接する部位まで移動され，アドレス「３」の右側に位置する。この際の割当ビットマップ２０４は「０，０，０，０，０，０，０，０，０，０」となっている。
このように，循環バッファが採用される場合は，空き領域が少ない場合であっても，メモリエレメント２０３を効率的に利用することができる。とくに，更新頻度の高いデータが記憶されるようなサブ領域Ｓにあってはより一層効果的である。
【産業上の利用可能性】
【００２６】
本発明は，３Ｄゲームなどに有効である。
【符号の説明】
【００２７】
１００ コプロセッサ
１０１ グラフィックスパイプライン
１０２ プロセッサインタフェース
１０３ メモリインタフェース
１０４ オンチップメモリ
１０５ メモリ調停回路
１０６ コマンドプロセサ
１０７ 頂点キャッシュ
１０８ 頂点シェーダ
１０９ ラスタライザ
１１０ ジオメトリシェーダ
１１１ ピクセルシェーダ
２０１ スタート境界部
２０２ エンド境界部
２０３ メモリエレメント
２０４ 割当ビットマップ
【技術分野】
【０００１】
本発明は，画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップに関する。
【背景技術】
【０００２】
従来３Ｄコンピュータ図形は，複雑な幾何学的な形に近似して，ポイント，線，および三角形のような簡単な幾何学的なプリミティブを使用して表現されている。既存のコンピュータグラフィックスハードウェアは，そのような簡単なプリミティブ，特に三角形のメッシュの処理を高速化するように最適化されており，様々な三角形，線，およびポイントを用いることで複雑な形に近似することができる。
【０００３】
このような３Ｄコンピュータ図形を処理する画像処理パイプラインは，複数の処理ステージを有する場合がある。それぞれが異なる処理ステージにおいては，サイズや更新頻度の異なるデータが処理されている。これらのデータを記録するために，それぞれ別のメモリを設けるのではプロセッサの大型化が避けられないことから，共通の統合されたメモリにて記憶がなされるのであるが，その場合メモリに記憶を転送するコストを最小限に抑えつつ記録を行うとメモリの断片化が発生しやすくなってしまう。
【０００４】
そこで，例えば特許文献１においては，この断片化を防ぐための記憶アルゴリズムが採用されている。このアルゴリズムはスウィッチングファブリック方式とよばれ，メモリ上の空きスペースを検索し，データの配列情報は仮想的にバッファ上に論理アドレスとして記録し，実際の物理アドレスには個々のデータを分割して配置する。このようなアルゴリズムを採用することによって，断片化した記憶領域であっても，データを記憶領域上に適切に配置できるため断片化による処理の低速化といった問題を抑制することはできる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許公開公報２００８−００７４４３０号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら，上述のような方式にあっては論理アドレスと物理アドレスとを関連付ける処理が複雑になりやすく，また物理アドレスの容量が大きいもの（例えば２５６以上のエレメントを有するもの）になった場合に空き領域を検索するアルゴリズムの負荷が過大になってしまうという問題があった。
【０００７】
そこで，本発明は，画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップにおいて，負荷が抑制された簡易なアルゴリズムによって記憶領域の断片化を抑制することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために本発明は，画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップであって，この記憶領域は，互いに隣接し，それぞれが同じタイプのデータ種別を有するように区分された複数のサブ領域に分割されている。そして，サブ領域内における各データはそれぞれ連続する順列データとして記憶されるとともに，同順列データはそれぞれが他の順列データと隣接する態様にて記憶され，
各サブ領域に記録されるデータは，同記憶領域に記録されている期間であるライフサイクル値がそれぞれ異なっており，ライフサイクル値が短い前記データを含むサブ領域は，ライフサイクル値が長いデータを含むサブ領域と隣接して設けられている。
また，このサブ領域は，隣接するサブ領域が境界部にデータが記録されていない場合に，当該隣接するサブ領域の境界部をサブ領域の記録領域として再割り当て可能に構成されている構成も可能である。
また，より一層の処理の高速化を図るために，サブ領域においては，前記データは循環バッファ形式にて記憶容量の割り当てが行われるようにすることもできる。
更に，サブ領域において，割当ビットマップにのっとってデータに対して記憶容量の割り当てを行うこともできる。
【発明の効果】
【０００９】
本発明によれば，負荷が抑制された簡易なアルゴリズムによって記憶領域の断片化を抑制することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は，本発明のＧＰＵを含むコプロセッサの概略構成を示すブロック図である。
【図２】図２は，データの統合された記録領域を示すブロック図である。
【図３】図３（ａ）〜（ｉ）は，メモリにデータを記録していく手順を示す概略図である。
【発明を実施するための形態】
【００１１】
以下，発明を実施するための形態について説明する。本発明は，以下に説明する実施態
様に限定されるものではない。本発明は，以下に説明する実施態様から当業者に自明な範
囲で適宜修正される範囲を含む。
【００１２】
本発明においける３Ｄ画像は，プリミティブを用いて表現されるものである。プリミティブはジオメトリの基本単位であり，３Ｄグラフィックスの場合，プリミティブはポリゴン（典型的には三角形），法線ベクトル，点などを含むことが通常である。プリミティブが三角形の場合は，各三角形は３つの頂点によって画定され，各線は２つの頂点によって画定される。各頂点が有するデータとしては，様々な属性，例えば，空間座標，明度，テクスチャ座標などと関連づけられている。
本明細書において，用語「シェーダ」は，一般にシェーディングを実行するＧＰＵのハードウェアサブユニットを参照するか又はシェーディングを実行するためのシェーダ（ハードウェア）によって使用されるメモリ例えばレジスタ記憶装置に次にロードされる，ＧＰＵにダウンロードされる命令セット又はトークンを参照するために使用され得る。用語「シェーダ」は，動作する双方を一緒に参照することもできる。用語「シェーダプログラム」は，一般にグラフィックスパイプラインに存在し実行するプログラム又はプロセスを参照し得て，画面上の最終的な画像の表面特性又は３次元画面環境におけるオブジェクトの決定／定義を支援するために使用される。「シェーダ」は，それらの特定のタスクを実行するために毎秒何十億の計算を実行可能である。
【００１３】
図１は，コプロセサ１００内のコンポーネントのブロック図である。コプロセサ１００は，単一の集積回路であってもよい。この例において，コプロセサ１００は，グラフィックスパイプライン１０１，プロセッサインタフェース１０２，メモリインタフェース１０３，オンチップメモリ１０４，メモリ調停回路１０５を含む。
【００１４】
３次元グラフィックスプロセサ１０１はグラフィックス処理タスクを行う。プロセサインタフェース１０２は，ＣＰＵとコプロセサ１００との間のデータおよび制御インタフェースを与える。メモリインタフェース１０３は，コプロセサ１００とオンチップメモリ１０４との間のデータおよび制御インタフェースを与える。この例においては，メモリがグラフィック画像処理チップであるコプロセッサ１００上に設けられた統合型のＧＰＵとして構成されている。
【００１５】
より詳細には，ＣＰＵは表示リストをメインメモリに保存し，バスインタフェースを介してポインタをコマンドプロセサ１０６に渡す。コマンドプロセサ１０６（これは以下で詳細に述べる頂点キャッシュ１０７を含む）は，ＣＰＵからコマンドストリームを取り込み，コマンドストリームおよび／またはメモリの中の頂点アレイから頂点属性を取り込み，属性タイプを浮動小数点フォーマットに変換し，得られた完全な頂点ポリゴンデータをレンダリング／ラスタ化のためにグラフィックスパイプライン１０１に渡す。以下でさらに詳細に説明するように，頂点データはコマンドストリームから，および／または各属性がそれ自身の線形アレイで保存されているメモリ中の頂点アレイから直接に来ることができる。メモリ調停回路１０５は，グラフィックスパイプライン１０１，コマンドプロセサ０６の間でのメモリアクセスを調停する。
【００１６】
グラフィックスパイプライン１０１は，頂点シェーダ１０８，ラスタライザ１０９，ジオメトリシェーダ１１０，ピクセルシェーダ１１１を含んで構成されている。
グラフィックスパイプライン１０１において，頂点シェーダ１０８は，頂点単位に様々な処理を行う。例えば，頂点の移動処理や，座標変換，ワールド座標変換，視野変換（カメラ座標変換），クリッピング処理，射影変換（透視変換，投影変換），ビューポート変換（スクリーン座標変換），光源計算等のジオメトリ処理が行われ，その処理結果に基づいて，オブジェクトを構成する頂点群について与えられた頂点データを変更（更新，調整）する。ジオメトリ処理後のオブジェクトデータ（オブジェクトの頂点の位置座標，テクスチャ座標，色データ（輝度データ），法線ベクトル，或いはα値等）は，オンチップメモリ１０４に保存される。
ラスタライザ１０９は，頂点シェーダ１０８から頂点データを受け取るか，オンチップメモリ１０４に保存されたデータを読み出してこれをエッジラスタ化，テクスチャ座標ラスタ化および色ラスタ化を実行するラスタライザへ３角形セットアップ情報を送信するセットアップユニットを含んでいる。
ジオメトリシェーダ１１０は，単一，または複数の頂点（複数）／ポイント（複数），ライン（複数）（２つの頂点セット），及び三角形（複数）（３つのラインセット）や多頂点形を含む異なるタイプのプリミティブの入力に対して処理を行い，入力されるプリミティブに基づいてパイプライン１０１内部に新しい幾何学的図形を生成することが可能である。ジオメトリシェーダ１１０の入力は，完全プリミティブ用頂点（ライン用の２つの頂点，三角形用の３つの頂点又はポイント用の単一頂点）及びエッジ隣接プリミティブ用頂点（ライン用の更なる２つの頂点，三角形用の更なる３つの頂点）データなどである。ジオメトリシェーダ１１０は，例えば１つのプリミティブを受信し得て，０，１又は複数のプリミティブのいずれかを出力できる。ジオメトリシェーダ１１０は，選択された単一のトポロジーを形成する複数頂点を出力できる。出力例の中には，三角形ストリップのようなトポロジー，ラインストリップ又はポイントリストを含む。エミットされたプリミティブの数は，任意のジオメトリシェーダ１１０の呼び出しの内部で変更できる。具体的な処理の一例としては，ポイントスプライト又はワイドラインテセレーション，ファー／フィン生成，シャドウボリューム生成，複数テクスチャ立方体表面に対する単一パスレンダリングなどが実行される。
ピクセルシェーダ１１１は光源や陰影の処理を行い，画像をピクセル単位で処理する。
【００１７】
続いて，図２からこのコプロセサ１００上に設けられたオンチップメモリ１０４の構造を説明する。このオンチップメモリ１０４には，プロセッサ上で取り扱われる入力データ，出力データ，及び処理途中のデータの全てが統合されて記憶されるものであり，外部メモリにデータが移され，内部でデータを保持する必要が無くなるまで使用されるものである。このオンチップメモリ１０４では，その記憶領域が複数のサブ領域Ｓへと分割されており，それぞれのサブ領域Ｓは対応するデータ種別を有するデータのみが記憶されるようになっている。そして，各サブ領域Ｓの前後には，隣接するサブ領域Ｓとの境界を示すスタート境界部２０１とエンド境界部２０２とが存在している。また，このオンチップメモリ１０４の記録単位は，一つにデータが記録可能なメモリエレメント２０３からなっている。
【００１８】
サブ領域Ｓ内では，一まとまりのデータアレイは各メモリエレメント２０３に間隔なく配置されており，各データアレイ同士は隣接して記憶されている。各データアレイはサブ領域Ｓのスタート境界部２０１に隣接するメモリエレメント２０３から順次空き領域を検索し，その容量を記憶可能なエリアがあり次第そこに記録されていく。同じサブ領域Ｓ内に含まれるデータであれば，その更新頻度やデータ長等は均質のものとなるため，データアレイは隙間なく配置可能となる。例えばあるサブ領域Ｓにおけるデータアレイの長さが３とした場合，既に配置されているデータアレイの割当が解除されて，そこに空き領域ができた場合も，同じデータ長のデータアレイがその後配置されることから，メモリエレメントの断片化が発生しにくく，データ割当も単純なアルゴリズムで実行可能である。
【００１９】
ここでは，サブ領域Ｓ０はインプット頂点の記憶領域に相当する。インプット頂点とは頂点シェーダ１０８に入力される頂点のデータであり，頂点の属性情報などを含んで記録されている。サブ領域Ｓ１は頂点シェーダコンテクスト，すなわち頂点シェーダ１０８において処理されている途中の頂点のデータが記録されている。頂点シェーダ１０８では，その処理の間に一時的に頂点の処理途中の状態を記録することがある。この頂点シェーダコンテクストは，頂点シェーダ１０８での処理が終わると割当は解放される。
サブ領域Ｓ２はアウトプット頂点の記録領域に相当する。アウトプット頂点とは頂点シェーダ１０８から出力される頂点のデータであり，このデータが再利用されて再び別シェーダで利用されることもあるため，記憶は比較的長期にわたって行われる。このアウトプット頂点がそのままジオメトリシェーダ１１０の入力値として活用することもできる。
サブ領域Ｓ３はジオメトリシェーダコンテクストの記録領域に相当する。ジオメトリシェーダ１１０において処理されている途中のプリミティブのデータが記録されている。ジオメトリシェーダ１１０では，その処理の間に一時的に頂点の処理途中の状態を記録することがある。このジオメトリシェーダコンテクストは，ジオメトリシェーダ１１０での処理が終わると割当は解放される。
サブ領域Ｓ４は，ジオメトリシェーダ１１０のアウトプットが記録される領域である。この領域は，ジオメトリシェーダ１１０での処理が終わるとデータが記録されることから，サブ領域Ｓ３が解放されると記憶がされるようになっている。
サブ領域Ｓ５は，ラスタライザ１０９での処理結果が記憶される領域である。また，サブ領域Ｓ６は，フラグメントシェーダコンテクスト，すなわちピクセルシェーダ１１１において処理されている途中の頂点のデータが記録されている。ピクセルシェーダ１１１では，その処理の間に一時的に頂点の処理途中の状態を記録することがある。このピクセルシェーダコンテクストは，ピクセルシェーダ１１１での処理が終わると割当は解放される。
【００２０】
ここで，これらのサブ領域Ｓ０〜Ｓ６の並びの順番には法則性を設けており，データの更新頻度が高い，あるいは記憶される期間の短いデータが記憶されるサブ記憶領域Ｓは，データの更新頻度が低い，あるいは記憶される期間の長いデータが記憶されるサブ記憶領域Ｓの間に挟まる形で設けられている。この更新頻度の違いをライフサイクル値と称する。更新頻度の高いデータはライフサイクル値が短く，更新頻度の低いデータはライフサイクル値が高い。例えば，頂点データコンテクストやジオメトリシェーダコンテクスト，フラグメントシェーダコンテクストが記憶されるサブ記憶領域Ｓ１，Ｓ３，Ｓ５は更新頻度が高い。これらのシェーダプログラムにおいては，その演算途中において一時期的処理結果が記憶・再利用されるため，メモリエレメント２０３への頻繁なアクセスと書き換えが発生している。
一方で，出力頂点データなどは，頂点シェーダ１０８の処理結果が記憶されるものであることから，そのデータは再度別のパイプラインのステージで再利用される場合を想定して，記憶される期間は長く設定されている場合が多い。本実施例ではこのように更新頻度の高いサブ領域Ｓと更新頻度の低い（換言すれば，長期間にわたってサブ領域Ｓに記憶されている）サブ領域Ｓとが交互に配置されている。
【００２１】
このように更新頻度の異なるサブ記憶領域Ｓが隣接することによる利点を次に説明する。
本実施例では，各サブ記憶領域Ｓのメモリエレメント２０３が必要に応じて増減されるアルゴリズムが採用されている。すなわち，サブ領域Ｓにおいて，記録に必要なメモリエレメント２０３が不足する場合，隣接するサブ領域Ｓの境界部分に位置するメモリエレメント２０３を自らの領域として取得する処理が行われる。具体的には，この処理はサブ領域Ｓ間のスタート境界部２０１やエンド境界部２０２が移動されることによって行われる。この際，隣接するサブ領域Ｓの各境界部２０１，２０２付近のメモリエレメント２０３にデータが記録されている場合，境界部２０１，２０２を移動してサブ領域Ｓのメモリエレメント２０３を増減することができない。そのため，前述したように更新頻度の高い，すなわちメモリエレメント２０３が解放されて空き領域ができやすいサブ領域Ｓと隣接することによって，サブ領域Ｓのサイズ変更がより柔軟に実施されやすくなる。
この際，サブ領域Ｓのサイズ変更を実施するか否かを判定するアルゴリズムとしては，例えば空いたメモリエレメント数が所定の値以下になった際において，隣接するサブ領域Ｓのメモリエレメント２０３に空きがある場合に境界部２０１，２０２の変更を行うという処理の手順や，割当されるデータアレイに必要なメモリエレメント数がサブ領域Ｓ内に存在するか否かを判定し，存在しないときに必要分を隣接するサブ領域Ｓのスタート境界部２０１付近から取得するといった手順を採用することができる。
【００２２】
また，本実施例においては，メモリエレメント２０３の構造としては循環バッファ構造が採用されてもよい。循環バッファ構造の場合，サブ領域Ｓ内のメモリエレメント２０３の最初と最後のものが連続して構成されている。この循環バッファの構成を図３を示して説明する。
図３（ａ）は，このサブ領域Ｓの初期状態を示している。このサブ領域Ｓは１０のメモリエレメント２０３から構成されており，この時サブ領域Ｓのスタート境界部２０１，及びエンド境界部２０２を示す境界部は一つ目のメモリエレメント２０３の位置に存在している。また，図示するような割当ビットマップ２０４を設け，実際にメモリエレメント２０３にデータアレイの割当，又は割当解除を行う前に，割当ビットマップ２０４上で記録するメモリエレメント２０３を決定して「０」か「１」かを記録し，この値を参照にしてメモリエレメント２０３への割当や割当解除を行うこともできる。このような処理を行うことによって，実際にメモリエレメント２０３に対して直接割当等を行う場合に比較して，単純なデータ構造で記録がなれている割当ビットマップ２０４の方が検索が容易であり，データが割当されたメモリエレメント２０３の間に割当解除がされたメモリエレメント２０３が存在して断片化が発生している場合などは，より効率的に処理を行うことができるようになる。
【００２３】
続いて図３（ｂ）に示されるように，次いでシーケンス状のデータアレイがメモリエレメント２０３の０〜４の５つのエリアに記録される。このとき割当ビットマップ２０４は，「１，１，１，１，１，０，０，０，０，０」となっている。この時，スタート境界部２０１はメモリエレメント２０３の「０」の左側，エンド境界部２０２はメモリエレメント○の「４」の右側に位置している。
続いて，図３（ｃ）に示されるように，最初に割り当てられた５つのデータアレイのうち最初の３つのデータアレイの割当が解除される。メモリエレメント２０３のうちアドレス「０」「１」「２」へのデータの割当が解除され，スタート境界部２０１は「３」の左側に移動される。このとき割当ビットマップ２０４は「０，０，０，１，１，０，０，０，０，０」となっている。
続いて，図３（ｄ）に示されるように，新たに６のデータ長からならデータアレイへの記憶領域の割り当てが行われる。この割当はエンド境界部２０２が移動され，６つ分のメモリエリア２０３がこの記憶領域としてあてはめられ，「５」「６」「７」「８」「９」「０」の順番で記憶される。割当後のスタート境界部２０１は「３」の左側，エンド境界部２０２は「０」の右側に移動されている。このとき割当ビットマップ２０４は「１，０，０，１，１，１，１，１，１」となっている。
【００２４】
続いて，図３（ｅ）に示されるように，アドレス「４」「６」「７」の割当解除がされる。この時，境界部２０１，２０２には移動は生じていない。割当ビットマップ２０４は「１，０，０，１，０，１，０，０，１，１」となっている。
続いて，図３（ｆ）に示されるように，新たに２のデータ長からならデータアレイへの記憶領域の割り当てが行われる。この割当はエンド境界部２０２が移動され，２つ分のメモリエリア２０３がこの記憶領域としてあてはめられ，「１」「２」の順番で記憶される。割当後のスタート境界部２０１は「３」の左側，エンド境界部２０２も「２」の右側に移動されている。このとき割当ビットマップ２０４は「１，１，１，１，０，１，０，０，１，１」となっている。
続いて，図３（ｇ）に示されるように，アドレス「３」に記憶されたデータの割当が解除される。この解除に伴い，スタート境界部２０１はアドレス「５」の左側に移動される。この際の割当ビットマップ２０４は「１，１，１，０，０，１，０，０，１，１」となっている。
【００２５】
続いて，図３（ｈ）に示されるように，アドレス「５」に記憶されたデータの割当が解除される。この解除に伴い，スタート境界部２０１はアドレス「８」の左側に移動される。この際の割当ビットマップ２０４は「１，１，１，０，０，１，０，０，１，１」となっている。
最後に，図３（ｉ）に示されるように，アドレス「８」「９」「０」「１」「２」に記憶されているデータの割当が解除される。この時は，スタート境界部２０１がエンド境界部２０２と隣接する部位まで移動され，アドレス「３」の右側に位置する。この際の割当ビットマップ２０４は「０，０，０，０，０，０，０，０，０，０」となっている。
このように，循環バッファが採用される場合は，空き領域が少ない場合であっても，メモリエレメント２０３を効率的に利用することができる。とくに，更新頻度の高いデータが記憶されるようなサブ領域Ｓにあってはより一層効果的である。
【産業上の利用可能性】
【００２６】
本発明は，３Ｄゲームなどに有効である。
【符号の説明】
【００２７】
１００ コプロセッサ
１０１ グラフィックスパイプライン
１０２ プロセッサインタフェース
１０３ メモリインタフェース
１０４ オンチップメモリ
１０５ メモリ調停回路
１０６ コマンドプロセサ
１０７ 頂点キャッシュ
１０８ 頂点シェーダ
１０９ ラスタライザ
１１０ ジオメトリシェーダ
１１１ ピクセルシェーダ
２０１ スタート境界部
２０２ エンド境界部
２０３ メモリエレメント
２０４ 割当ビットマップ
【特許請求の範囲】
【請求項１】
画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップであって，
前記記憶領域は，互いに隣接し，それぞれが同じタイプのデータ種別を有するように区分された複数のサブ領域に分割されており，
前記サブ領域内における各データはそれぞれ連続する順列データとして記憶されるとともに，同順列データはそれぞれが他の前記順列データと隣接する態様にて記憶され，
各サブ領域に記録される前記データは，同記憶領域に記録されている期間であるライフサイクル値がそれぞれ異なっており，
前記ライフサイクル値が短い前記データを含む前記サブ領域は，前記ライフサイクル値が長い前記データを含む前記サブ領域と隣接して設けられている
グラフィック演算処理チップ。
【請求項２】
請求項１に記載のグラフィック演算処理チップにおいて，
前記サブ領域は，隣接するサブ領域が境界部近隣のメモリエレメントに前記データが記録されていない場合に，当該隣接するサブ領域の前記メモリエレメントを前記サブ領域の記録領域として再割り当て可能に構成されている
グラフィック演算処理チップ。
【請求項３】
請求項１または２に記載のグラフィック演算処理チップにおいて，
前記サブ領域においては，前記データは循環バッファ形式にて記憶領域の割り当てが行われる
グラフィック演算処理チップ。
【請求項４】
請求項１〜３のいずれか一項に記載のグラフィック演算処理チップにおいて，
前記サブ領域におけるデータの割当，又は割当の解除に先行して割当ビットマップ上で割当エリアの決定を行い，当該割当ビットマップにのっとって記憶領域の割り当てが行われる
グラフィック演算処理チップ。
【請求項１】
画像処理パイプラインを有し，記録領域がチップ上に設けられたグラフィック演算処理チップであって，
前記記憶領域は，互いに隣接し，それぞれが同じタイプのデータ種別を有するように区分された複数のサブ領域に分割されており，
前記サブ領域内における各データはそれぞれ連続する順列データとして記憶されるとともに，同順列データはそれぞれが他の前記順列データと隣接する態様にて記憶され，
各サブ領域に記録される前記データは，同記憶領域に記録されている期間であるライフサイクル値がそれぞれ異なっており，
前記ライフサイクル値が短い前記データを含む前記サブ領域は，前記ライフサイクル値が長い前記データを含む前記サブ領域と隣接して設けられている
グラフィック演算処理チップ。
【請求項２】
請求項１に記載のグラフィック演算処理チップにおいて，
前記サブ領域は，隣接するサブ領域が境界部近隣のメモリエレメントに前記データが記録されていない場合に，当該隣接するサブ領域の前記メモリエレメントを前記サブ領域の記録領域として再割り当て可能に構成されている
グラフィック演算処理チップ。
【請求項３】
請求項１または２に記載のグラフィック演算処理チップにおいて，
前記サブ領域においては，前記データは循環バッファ形式にて記憶領域の割り当てが行われる
グラフィック演算処理チップ。
【請求項４】
請求項１〜３のいずれか一項に記載のグラフィック演算処理チップにおいて，
前記サブ領域におけるデータの割当，又は割当の解除に先行して割当ビットマップ上で割当エリアの決定を行い，当該割当ビットマップにのっとって記憶領域の割り当てが行われる
グラフィック演算処理チップ。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１２−１１８９４３（Ｐ２０１２−１１８９４３Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２７０７３１（Ｐ２０１０−２７０７３１）
【出願日】平成２２年１２月３日（２０１０．１２．３）
【出願人】（５０２４０１７０３）株式会社ディジタルメディアプロフェッショナル (26)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１２月３日（２０１０．１２．３）
【出願人】（５０２４０１７０３）株式会社ディジタルメディアプロフェッショナル (26)
【Ｆターム（参考）】
[ Back to top ]