(57)【要約】【課題】マルチコア処理システム上の効果パイプラインを通じて複数の画像フレームを処理するためのシステム及び方法を提供する。【解決手段】本発明は、画像フレームを複数のブロックの画像データに細分化することによって効果のパイプラインを通じて画像フレームを処理することに関する。例示的な方法は、各フレームから複数のブロックを発生させる段階と、所定の連続した順序で効果のパイプラインを通じて各ブロックを処理する段階と、処理済みブロックを集約して、各処理済みブロックからの主ピクセルを結合することによって出力フレームを生成する段階とを含むことができる。効果のパイプラインは、複数の処理ノードにわたって分配することができ、各効果は、ノードに入力として供給されたブロックを処理することができる。各処理ノードは、効果を使用してブロックを独立に処理することができる。【選択図】図１
2010067276.tif 000002
【特許請求の範囲】
【請求項１】
効果のパイプラインを通じて画像フレームを処理する方法であって、
各ブロックが１群の主ピクセルと、効果のパイプラインからの効果が該主ピクセルのための出力を生成する入力として必要とするあらゆるピクセルを含む１群の全ピクセルとを収容する複数のブロックを発生させる段階と、
複数の処理ノードにわたって分配されている前記効果のパイプラインを通じて所定の連続した順序で各ブロックを処理する段階と、
前記処理されたブロックを集約し、該処理されたブロックからの前記主ピクセルを結合することによって出力フレームを生成する段階と、
を含み、
効果のパイプラインからの各効果が、前記ノードに入力として供給されたブロックを処理して、該ブロックの前記主ピクセルのための出力を生成する、
ことを特徴とする方法。
【請求項２】
前記全ブロックピクセルは、前記主ピクセルと、該主ピクセルのための出力を生成するのに少なくとも１つ効果が入力として必要とするあらゆる付加的なピクセルとを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記複数のブロックを発生させる段階は、効果を分析して前記主ピクセルのための前記出力を発生させるのに必要な該全ピクセルを判断する段階を更に含むことを特徴とする請求項１に記載の方法。
【請求項４】
複数のブロックを発生させる段階は、
第１の効果を分析して、前記主ピクセルのための出力を生成するのに必要な前記全ピクセルを判断する段階と、
第２の効果を分析して、前記第１の効果が前記主ピクセルのための出力を生成するのに必要とする前記全ピクセルのための出力を発生させるのに必要な該全ピクセルを判断する段階と、
を含む、
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記処理する段階は、前記第２の効果を通じて前記ブロックを処理した後で、かつ前記第１の効果を処理する前に、ブロックにおける全ピクセルの数を低減することを特徴とする請求項４に記載の方法。
【請求項６】
前記処理する段階は、第１の効果を処理した後で、かつ第２の効果を処理する前に、少なくとも１つの隣接ブロックからの主ピクセルを用いてブロックにおける前記全ピクセルを更新する段階を含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記全ピクセルは、前記効果のパイプラインからの複数の効果を通じてブロックを連続処理して前記主ピクセルのための出力を生成するのに入力として必要なあらゆるピクセルを含むことを特徴とする請求項１に記載の方法。
【請求項８】
複数のブロックを発生させる段階は、各効果を分析して、該効果がピクセル効果、面積効果、又は範囲効果であるかを判断する段階を含むことを特徴とする請求項１に記載の方法。
【請求項９】
複数のブロックを発生させる段階は、ノード及び効果に対して利用可能なリソースを分析して、該複数のブロックからの各ブロックのための主ピクセル及び全ピクセルの数を判断する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記全ピクセルは、時間的に隣接する画像フレームからの複数のピクセルを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記全ピクセルは、入力画像フレーム内の複数の空間的に隣接するピクセルを含むことを特徴とする請求項１に記載の方法。
【請求項１２】
効果のパイプラインを通じて各ブロックを処理する時に、各処理ノードは、効果を使用してブロックを独立に処理することを特徴とする請求項１に記載の方法。
【請求項１３】
前記処理する段階は、各フレームにおける第１のブロックの処理の開始と各フレームにおける最終ブロックの出力との間の待ち時間を短縮するように前記効果をスケジュールする段階を含むことを特徴とする請求項１に記載の方法。
【請求項１４】
効果パイプラインを通じて一連の画像フレームを処理するための装置であって、
ブロック発生器、効果分配器、及びブロック集約器を含む１次プロセッサと、
ブロックのコンテンツを格納する最小メモリキャッシュを各々含む複数の２次プロセッサと、
前記１次プロセッサ、前記複数の２次プロセッサ、及びメモリインタフェースを相互接続するバスと、
を含み、
前記ブロック発生器は、前記メモリインタフェースを通じて供給された入力画像フレームから複数のブロックを発生させ、各ブロックは、該入力画像フレームからの１群の主ピクセルと１群の全ピクセルを収容し、該全ピクセルは、効果のパイプラインからの効果が該主ピクセルのための出力を生成するのに入力として必要とするあらゆるピクセルを含み、
前記効果分配器は、前記複数の２次プロセッサの間での前記効果及び前記複数のブロックの分配及び処理順序を管理し、
前記ブロック集約器は、前記処理されたブロックを結合し、
前記複数の２次プロセッサは、連続した順序で前記効果のパイプラインを通じて各ブロックを処理し、該効果のパイプラインは、該複数の２次プロセッサにわたって分配されており、
各２次プロセッサは、各ブロックを独立に処理してそのブロックに対して前記主ピクセルのための出力を生成する効果を実行する、
ことを特徴とする装置。
【請求項１５】
前記全ピクセルは、各ブロックにおいて、前記主ピクセルと、少なくとも１つ効果が該主ピクセルを出力するのに入力として必要とするあらゆる付加的なピクセルとを含むことを特徴とする請求項１４に記載の装置。
【請求項１６】
前記１次プロセッサは、効果を分析して、前記主ピクセルを発生させるのに必要な前記全ピクセルを判断することを特徴とする請求項１４に記載の装置。
【請求項１７】
前記ブロック発生器は、第１の効果を分析して、前記主ピクセルを発生させるのに必要な前記全ピクセルを判断し、かつ第２の効果を分析して、該第１の効果が該主ピクセルを発生させるのに必要とする該全ピクセルを発生させるのに必要な該全ピクセルを判断することを特徴とする請求項１４に記載の装置。
【請求項１８】
２次プロセッサは、前記第２の効果を通じて前記ブロックを処理した後で、かつ前記第１の効果を処理する前に、ブロックにおける全ピクセルの数を低減することを特徴とする請求項１７に記載の装置。
【請求項１９】
前記２次プロセッサは、少なくとも１つの隣接ブロックからの主ピクセルを用いてブロックの前記全ピクセルを該ブロックに対して第１の効果を処理した後でかつ第２の効果を処理する前に更新することを特徴とする請求項１４に記載の装置。
【請求項２０】
前記全ピクセルは、前記効果のパイプラインからの少なくとも１つ効果を実行して前記主ピクセルのための出力を生成する少なくとも１つの２次プロセッサがブロックを連続処理するのに入力として必要とするあらゆるピクセルを含むことを特徴とする請求項１４に記載の装置。
【請求項２１】
前記ブロック発生器は、各効果を分析して、前記少なくとも１つの効果がピクセル効果、面積効果、又は範囲効果であるかを判断することを特徴とする請求項１４に記載の装置。
【請求項２２】
複数のブロックを発生させる段階は、２次プロセッサ及び対応する効果に対して利用可能なリソースを分析して、主ピクセル及び全ピクセルの数を判断する段階を含むことを特徴とする請求項１４に記載の装置。
【請求項２３】
前記全ピクセルは、時間的に隣接する画像フレームからの複数のピクセルを含むことを特徴とする請求項１４に記載の装置。
【請求項２４】
前記全ピクセルは、空間的に隣接するブロックからの複数の主ピクセルからのピクセルを含むことを特徴とする請求項１４に記載の装置。
【請求項２５】
効果のパイプラインを通じて各ブロックを処理する時に、各処理ノードが、効果を使用してブロックを独立に処理することを特徴とする請求項１４に記載の装置。
【請求項２６】
前記１次プロセッサは、各フレームにおける第１のブロックの処理の開始と各フレームにおける最終ブロックの出力との間の待ち時間を短縮するスケジューラーを含むことを特徴とする請求項１４に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本出願は、２００８年９月９日出願の米国特許仮出願出願番号第６１／１９１、５５７号に関し、この特許の内容全体は、本明細書において引用により組み込まれている。
【０００２】
本発明は、一般的に、「パイプライン画像処理エンジン」に関し、より具体的には、マルチコア処理システム上の効果パイプラインを通じて複数の画像フレームを処理するためのシステム及び方法に関する。
【背景技術】
【０００３】
製造技術が改善し続けると、半導体ベースのマイクロエレクトロニクスの物理限界は、マイクロプロセッサの機能増強の需要を満たすために拡大する。処理速度の制限は、マルチコア又は分散型アーキテクチャを使用して作業負担を分配し、それによって処理機能を増強して処理時間を短縮することにより、並列処理を通して既存のプロセッサ速度及び機能を利用する適応をもたらしている。
【０００４】
フィルム／ビデオ／撮像空間の用途では、パイプライン式に複数の画像処理効果を互いに連鎖させることが多い。これらの画像処理パイプラインは、マルチコア又は分散型アーキテクチャを通して得られる並列処理から恩典を受けることができる。このような画像処理を行う用途は、リアルタイムの速度で膨大なデータ量の処理及び移動の両方を行う必要性を含む共通の特性を共有する。
【０００５】
このようなシステムの従来の実施には、収量不良、長い待ち時間、複雑性増大に及ぶ複合的な問題があり、それによって伸展性及び拡張性が低減されている。これらの制限は、パイプラインシステムにおけるような連続的な実行に依存する複数の個別の効果を互いに連鎖させる時に悪化する。
【０００６】
映像を処理する時、「効果パイプライン」は、画像への定められた順序の視覚効果の適用を指す。同様に、「効果」は、効果パイプラインの各段を指す。
【０００７】
効果パイプラインにおける様々な効果の間のハードウエアリソースの分配に対する従来の手法は、一般的に、並列処理に対するいくつかの制限を受ける。
【０００８】
１つの手法は、データの各画像フレームを最小分量の作業と定め、各効果が独立して所定のフレームに又は他のフレームに操作することを可能にする。この手法により、複数の効果は、それらの間の緊密な統合を実行しなくても共有システムにおいて共存することができるが、この手法はまた、システム全体の長い待ち時間をもたらす。この待ち時間は、効果パイプラインにおける効果の数と相関している。
【０００９】
「パイプライン性能」は、待ち時間及び計算時間の組合せとして性能を測定する。「待ち時間」は、所定のデータユニットを放出するためにパイプラインシステムにより必要とされる時間を指す。効果パイプラインに関しては、「待ち時間」は、画像フレームがパイプラインにおける最初の効果に入った瞬間からパイプラインにおける最後の効果を出る時間まで各画像フレームがパイプラインにおいて費やす時間を説明するものである。
【００１０】
「計算時間」は、標準的なデータユニット、例えば画像フレームを処理するのに必要とされる時間を指す。更に、計算時間は、映像システムに対するフレームレートの関数又はフレームを処理する実時間の関数として表すことができる。
【００１１】
図１１は、マルチコアシステム上の６段フレームベースの効果パイプラインを示している。図１１では、各効果は、プロセッサ数がパイプラインにおける効果の個数に等しいか又はそれを超えるという最良の場合の仮定でプロセッサ（又はコア）に割り当てられている。各プロセッサは、一度に１つの完全な画像フレームに対する効果を処理する。画像フレームは、映像ストリーム又は他の画像フレーム源からのものとすることができる。各到着入フレームは、順番に順次処理される。簡潔さを期すために、各効果は、フレームを処理するために同じ時間量が掛かると仮定されており、これは、一貫したフレームレートを維持するために各フレームを出力するのに必要とされる最適時間を表している。
【００１２】
時間ｔ１で、フレーム１は、パイプラインに入り、第１の効果が、プロセッサ１によりフレーム１に適用される。時間ｔ２で、フレーム２が、プロセッサ１により取り込まれて処理され、フレーム１は、プロセッサ２により取り込まれて処理される。時間ｔ３で、フレーム３が、プロセッサ１により取り込まれて処理され、フレーム２は、プロセッサ２により取り込まれて処理され、フレーム１は、プロセッサ３により取り込まれて処理される。時間ｔ４からｔ６まで、フレーム４〜６が、パイプラインに導入され、フレーム１〜３は、パイプラインに沿って進行する。時間ｔ６の終了時に、フレーム１は、パイプラインから現れる。
【００１３】
パイプライン待ち時間は、パイプラインにおける全ての段を通してフレームを処理するのに必要とされる時間の関数として、又は「フレーム時間」、すなわち、フレームＮが効果パイプラインを出る前にパイプ内の第１の効果により処理されたフレームの個数で測定することができる。フレーム時間の関数として、パイプライン待ち時間は、以下として計算される。
ＰＬFT＝Ｍ−Ｎ          （式１）
ここで：
・ＰＬFTは、フレーム時間での「パイプライン待ち時間」である。
・Ｍは、瞬間Ｔでパイプラインに入るフレームである。
・Ｎは、瞬間Ｔでパイプラインを出るフレームであり、Ｍ＜Ｎである。
【００１４】
フレームベースのアーキテクチャに対しては、パイプライン待ち時間はまた、連鎖内の最も速度が遅い効果に対する処理時間とパイプラインにおける効果（又は段）の個数との積と定めることもできる。これは、以下のように計算される。
ＰＬCT＝Ｎ*ＴFM          （式２）
ここで：
・ＰＬCTは、計算時間としての「パイプライン待ち時間」である。
・Ｎは、パイプラインにおける段の個数である。
・ＴFMは、パイプラインにおける最も速度が遅い効果Ｍによりフレームを処理するのに必要とされる時間である。
【００１５】
新しいフレームが、１２０ｍｓ毎にパイプラインに供給され、パイプラインが、６つの段又は効果を収容し、かつパイプラインにおける最も速度が遅い効果も、１フレームのデータを処理するのに１２０ｍｓ掛かると仮定することにより、図１１のフレームベースのシステムに対する「パイプライン待ち時間（ＰＬ）」は、６*１２０＝９６０ｍｓである。
【００１６】
更に、パイプライン待ち時間は、第１のフレーム、すなわち、フレーム１がパイプラインに入って出る時からの時間の関数として測定されるので、各プロセッサに全ての効果を並列に連続して実行させることによって得られる恩典はない。すなわち、新しいフレームを１２０ｍｓ毎にパイプラインに連続して供給する代わりに、どのフレームも直ちに処理に向けて利用可能であったとしても、パイプラインは、第１のフレームがパイプラインに入って出た時からの時間に基づいて、依然として６フレーム待ち時間、及び９６０ｍｓ計算時間待ち時間を有するであろう。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】米国特許仮出願出願番号第６１／１９１、５５７号
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上述のシステムは、利用可能なハードウエアリソースにより制限され、すなわち、処理は、効果の個数が利用可能な独立した処理構成要素の数を超えた場合、又は各プロセッサにおいて利用可能なキャッシュメモリがフレーム全体を格納することができない場合に速度がかなり遅くなる。
【課題を解決するための手段】
【００１９】
本発明は、限られたハードウエアリソースを何とか調節する柔軟かつ拡張可能なパイプラインを実施する「パイプライン画像処理エンジン」を提供する。実施形態は、静的及び動的負荷均衡の両方を含むこともできる。例示的な実施形態は、上述の制限の多くを除去又は低減すると同時に、より効率的に効果を実行する一般フレームワークも提供する。
【００２０】
本発明の例示的な実施形態は、効果のパイプラインを通じて画像フレームを処理する方法を含むことができる。本方法は、各フレームから複数のブロックを発生させる段階と、所定の連続した順序で効果のパイプラインを通じて各ブロックを処理する段階と、処理済みブロックを集約して、各処理済みブロックからのピクセルを結合することによって出力フレームを生成する段階とを含むことができる。各ブロックは、１群の主ピクセルと１群の全ピクセルの群とを収容することができ、全ピクセルは、主ピクセルのための出力を生成するために効果のパイプラインからの効果により入力として必要とされるあらゆるピクセルを含む。各ブロック内の主ピクセルは、効果のパイプラインにより発生した最終フレームに対して使用されることになるピクセルである。
【００２１】
効果のパイプラインは、複数の処理ノードにわたって分配することができ、各効果は、ノードへの入力として供給されたブロックを処理して、ブロックの主ピクセルのための出力を生成することができる。各処理ノードは、効果を使用してブロックを独立に処理することができる。各フレーム内の第１のブロックの処理と各フレーム内の最終ブロックの出力との間の待ち時間を短縮するために、効果は、スケジュール目的に対して分析することができる。
【００２２】
効果は、空間的又は時間的効果のいずれかを含むことができる。空間的効果を処理する時、ブロック内の全ピクセルは、隣接ブロックからの複数のピクセルを含むことができる。時間的効果を処理する時、全ピクセルは、時間的に隣接する画像フレームからの複数のピクセルを含むことができる。
【００２３】
ブロック処理及び発生は、以下で説明する減少範囲又は固定範囲戦略のような異なる戦略を使用することができるが、これらに限定されず、異なる戦略の結合及び小結合を含むことができる。例えば、効果パイプラインの異なる部分は、異なる戦略を用いて作動させることができる。
【００２４】
一実施形態では、全ピクセルを発生させる段階は、効果のパイプラインからの複数の効果を通じてブロックを連続処理し、主ピクセルのための出力を生成するのに必要とされるあらゆるピクセルを識別する段階を含むことができる。これは、第１の効果を分析して、主ピクセルのための出力を生成するのに必要とされる全ピクセルを判断する段階と、第２の効果を分析して、主ピクセルのための出力を生成するのに第１の効果により必要とされる全ピクセルのための出力を発生させるのに必要とされる全ピクセルを判断する段階とを含むことができる。処理段階は、次に、第２の効果を通じてブロックを処理した後で、かつ第１の効果を処理する前にブロック内の全ピクセル数を低減することができる。
【００２５】
別の実施形態では、処理段階は、第１の効果を処理した後で、かつ第２の効果を処理する前に少なくとも１つの隣接ブロックからの主ピクセルでブロック内の全ピクセルを更新する段階を含むことができる。
【００２６】
更に別の例示的な実施形態は、効果パイプラインを通じて一連の画像フレームを処理するための装置とすることができる。装置は、１次プロセッサ、複数の２次プロセッサ、及びバスを含むことができる。バスは、１次プロセッサ、複数の２次プロセッサ、及びメモリインタフェースを相互接続することができる。
【００２７】
１次プロセッサは、ブロック発生器、効果分配器、及びブロック集約器を含むことができる。ブロック発生器は、メモリインタフェースを通じて供給された入力画像フレームから複数のブロックを発生させることができる。効果分配器は、複数の２次プロセッサの間の効果及び複数のブロックの分配及び処理順序を管理することができる。最後に、ブロック集約器は、処理済みブロックを結合することができる。
【００２８】
複数の２次プロセッサの各々は、ブロック発生器からのブロックのコンテンツを格納する最小メモリキャッシュを含むことができる。複数の２次プロセッサの各々は、連続した順序で効果のパイプラインを通じて一度に１つのブロックを処理することができる。効果のパイプラインは、複数の２次プロセッサにわたって分配することができる。各２次プロセッサは、効果を独立に実行し、所定のブロックに対して主ピクセルのための出力を生成することができる。
【００２９】
添付図面を参照して上記及び他のより詳細かつ特定の本発明の特徴を以下の明細書でより十分に開示する。
【図面の簡単な説明】
【００３０】
【図１】本発明によるマルチコアプロセッサの例示的な実施形態の図である。
【図２】本発明によるコンピュータクラスターの第２の例示的な実施形態の図である。
【図３】１６個の均一なブロックに分割した１２×１２ピクセルフレームを示す図である。
【図４】１２×１２ピクセルフレームで形成したブロックを示す図である。
【図５Ａ】本発明によるパイプラインシナリオにおける３つの面積効果を処理する減少範囲戦略の例示的な実施形態を示す図である。
【図５Ｂ】図５Ａの３個の効果を考慮して望ましい主データ領域に対する出力を発生させるのに必要な外側範囲のサイズを判断する処理を示す図である。
【図６Ａ】本発明による効果のパイプラインを処理する固定範囲戦略を示す図である。
【図６Ｂ】ブロック横断戦略の第１の例示的な実施形態の図である。
【図６Ｃ】ブロック横断戦略の第２の例示的な実施形態の図である。
【図７】本発明によりマルチコアプロセッサ上で効果パイプラインを実行するための処理の例示的な実施形態を示す図である。
【図８】本発明により最小分量の作業が半フレームのブロックサイズまで低減された第１の修正効果パイプラインを示す図である。
【図９】ブロックサイズが１／４フレームまで低減された図８のブロックベースのフレームワーク内で同じ効果パイプラインを使用する図である。
【図１０Ａ】分配された不均衡な効果パイプラインの例を示す図である。
【図１０Ｂ】分配された負荷均衡が取れた効果パイプラインの例を示す図である。
【図１１】マルチコアシステム上の従来の効果パイプラインを示す図である。
【００３１】
以下の説明では、説明上、本発明の１つ又はそれよりも多くの実施形態の理解をもたらすために、流れ図、システム構成、及び処理アーキテクチャのような多くの詳細を説明する。しかし、これらの特定の詳細は、本発明を実施するのに必要とされるものではないことは、当業者には明らかであり、かつ明らかであろう。
【００３２】
本発明は、限られたハードウエアリソースを調節する柔軟かつ拡張可能なパイプラインを実行する「パイプライン画像処理エンジン」を提供する。実施形態は、フレームから「ブロック」まで各「効果」により処理される最小作業分担を低減するものである。各ブロックは、フレーム全体の部分集合を表している。ブロックベースの処理は、各フレーム分のデータをＮ個のある程度重なり合っている又は重なり合っていないブロックに細分化するものであり、ブロックベースの処理により、パイプラインのあらゆる段での各効果は、他のブロックとは独立にブロックを処理することができる。それによって複数の効果は、フレーム又はフィールド全体が利用可能になるのを待つことなく同時に作業することができ、また、それによって複雑な同期化機構が不要になる。各ブロックは、完全独立式であり、各効果に向けて、各ブロックに独立して作業するのに十分なフレームデータを保持している。ブロックは、完全独立式であると共に様々なブロックに作業する様々な効果が緩く結合しているので、フレームワークは、パイプラインにおける効果の速度が遅いほど多くのプロセッサを容易に割り当て、一方、軽量の簡単な効果には、物理的プロセッサの数を低減して割り当てることができる。更に、プロセッサ割当ては、いかなるユーザ干渉もなしに１つのフレームから次のものへと変えることができる。
【００３３】
本発明は、ビジネス処理、コンピュータ実施式方法、コンピュータプログラム製品、コンピュータシステム及びネットワーク、ユーザインタフェース、及びアプリケーションプログラミングインタフェースなどを含む様々な形態で具現化することができる。
図１は、本発明によるマルチコアプロセッサ１００の例示的な実施形態を示している。
【００３４】
マルチコアプロセッサ１００は、超高速内部バス１１０により互いに接続した多くの個別の単一プロセッサユニット（ＳＰＵ）１０４を含むことができる。マルチコアプロセッサ１００は、並列処理ユニット（ＰＰＵ）１０２、メモリインタフェース１０６、及び入出力インタフェース１０８を含むことができる。ＰＰＵ１０２は、ＳＰＵ１０４間の処理タスクの分配を調節することができる。ＰＰＵ１０２は、実行中の処理又は効果に関連する情報及び命令を格納するローカルメモリキャッシュ１０３を収容することができる。各ＳＰＵ１０４は、そのＳＰＵ１０４に割り当てた実行中の処理又は効果に関連する情報を格納するのに使用するメモリキャッシュ１０５を含むことができる。
【００３５】
作動中、効果パイプライン及び複数の画像フレームを含む入力は、入出力インタフェース１０８を通じてマルチコアプロセッサ１００に供給することができる。ＰＰＵ１０２は、効果パイプラインを複数の個別の効果に構文解析することができる。各画像フレームは、複数の効果と共に分析してピクセルブロックに分離することができる。ＰＰＵ１０２は、次に、処理に向けて効果及びブロックをＳＰＵ１０４間に分配することができる。ＳＰＵ１０４が効果に基づいてブロックを処理した後、ＰＰＵ１０２は、処理済みブロックを完全な出力画像フレームに集約することができる。
【００３６】
図１は、異なるＰＰＵ１０２及びＳＰＵ１０４を有するアーキテクチャを示すが、当業者は、本発明がこれに限定されず、かつ均一なマルチコアプロセッサを含む汎用アーキテクチャ又は他の形式の専用アーキテクチャ上で実行することができることを認めるであろう。
【００３７】
図２は、効果パイプラインの処理に関連の作業負荷を分配することができるコンピュータクラスター２００の形態で本発明の第２の例示的な実施形態を示している。コンピュータクラスター２００は、ネットワーク２１０により互いに接続した多くの個別の処理ユニット（ＤＰＵ）２０４を含むことができる。コンピュータクラスター２００は、クラスター管理ユニット（ＣＭＵ）２０２及び制御端末２０８を含むことができる。ＣＭＵ２０２は、ＤＰＵ２０４間の処理タスクの割当てを調節することができる。ＣＭＵ２０２はまた、各ＤＰＵ２０４に分配された進行状況、負荷、及び効果を追跡するクラスターモニタを含むことができる。
【００３８】
作動中、効果パイプライン及び複数の画像フレームは、ネットワーク２１０にアクセス可能な端末２０８又は別のソースからＣＭＵ２０２に供給することができる。ＣＭＵ２０２は、効果パイプラインを個別の効果に構文解析することができる。各画像フレームは、個別の効果と共に分析してピクセルブロックに分離することができる。ＣＭＵ２０２は、次に、処理に向けて個別の効果及びピクセルブロックをＤＰＵ２０４間で分配することができる。
【００３９】
効果のタイプ
ピクセルデータのブロックに関しては、「効果」は、ピクセルのブロックを変化又は変形させる処理である。各ブロックは、複数のピクセル、例えばピクセルの矩形又は正方形グリッドから成る。ＭｘＮピクセルを有するＡブロックは、ＭｘＮ処理要素が同時に利用可能にされていたとしたら、全て一度に並列処理することができるであろう。これは、対応する出力ピクセルを所定の効果が生成するのに必要な全てのデータを各入力ピクセルが供給した場合に限り可能である。しかし、多くの効果は、入力ピクセルを出力ピクセルに適正に変化又は変形させるのに入力ピクセル及び隣接ピクセルに依存する。
【００４０】
効果は、３つのタイプ、すなわち、点効果、面積効果、及び範囲効果に分類することができる。「点効果」は、入力ピクセル１つだけに基づいて出力ピクセルを生成する効果である。色補正効果は、この部類に該当する。「面積効果」は、出力ピクセルを生成するために所定の入力とは別にある一定の量の隣接ピクセルを必要とする効果である。ぼかし効果のような畳み込みフィルタは、面積効果である。面積効果は、特にメモリ使用量及び性能に関連する並列処理に対するいくつかの傷害となっている。「範囲効果」は、単一出力ピクセルを生成する入力としてフレーム全体を必要とする効果である。ヒストグラム効果は、あらゆる出力ピクセルを発生させる前にフレーム全体の分析を必要とすることから、一般的に範囲効果である。範囲効果は、並列処理に対する最大の傷害となっている。
【００４１】
上述の効果を空間領域に関して説明するが（すなわち、これらの効果は、データの単一フレームを使用して作動する）、これらの効果は、時間領域で作動させることもできる。時間領域効果は、時間的に隣接するフレームからのデータを必要とする場合がある。例えば、時間的面積効果は、単一フレームで出力ピクセルデータを生成するために隣接フレーム入力ピクセルデータを必要とする場合があり、時間的範囲効果は、単一出力フレームに対してピクセルデータを生成するためにクリップ又はシーケンスのフレームの全てを必要とする場合がある。例示的に、「ボックスぼかし」は、空間面積効果であり、「モーションぼかし」は、時間的面積効果である。更に、効果は、両領域内で作業することができる。例えば、「飛越から漸進への変換」は、空間−時間的面積効果であり、その理由は、空間領域（単一フレーム）及び時間的領域（隣接フレーム）内の隣接データを必要とするからである。
【００４２】
ブロック分割
フレームに関連の作業の分量を低減するために、各フレームは、より小さいサブフレーム、つまりデータの「ブロック」に分割することができる。
図３は、１６個の均一なブロック（ブロック１〜１６として示す）に分割した１２×１２ピクセルフレームを示している。フレーム３０２は、１２×１２ピクセルを収容するが、ブロック３０４（３０４−１〜３０４−１６）の各々は、３×３ピクセルを収容することができ、１６個のブロックは、フレーム３０２をブロック３０４に完全にマッピングすべきである。１２×１２ピクセルフレーム３０２は、単に例示を目的として示しており、いかなる点においても本発明を特定のフレームサイズ、解像度、又は縦横比に制限するものではないことが理解されるであろう。
【００４３】
例示的な実施形態は、所定のフレーム内のブロックの全てに対して同じ次元を維持することができる。それによってＳＰＵ１０４の全ての間での作業の均一な分配をもたらすことができる。しかし、ブロックサイズの分配は、異なる方式に従う場合がある。例えば、効果においてある一定のピクセル間でより大きい依存度が存在する場合には、これらのピクセルは、単一ブロックに分類して並列処理を容易にすることができる。更に、色関係、物体識別などのような様々な基準に基づいて特定のフレームを分割することができる。最後に、ブロックサイズに関する基準により、異なるブロックに対する所定の効果の処理時間がほぼ均一なままであるように同様の作業分担を有するブロックを生成することができる。
【００４４】
ブロック分割（又は集約））自体は、本質的に並列のタスクではなく、従って、複数のＳＰＵ１０４の結果にアクセスすることができ、かつより大きい利用可能なメモリリソースを利用することができる単一のプロセッサ、例えば、ＰＰＵ１０２に任せることができる。ＰＰＵ１０２が直ちにフレーム全体にアクセスすることができ、一方、ＳＰＵ１０４は個別のブロックで好ましくは作動させることができるので、ブロック分割及び集約処理は、ＰＰＵ１０２に任せることができる。更に、ブロック３０４がＳＰＵ１０４に取り込まれた状態で、ＰＰＵ１０２とＳＰＵ１０４間の相互作業を最小にすることが好ましい。これは、高速ＳＰＵ１０４の複数を利用することによって最大計算収量を促進し、一方、交差処理又は通信に関連の遅延が回避される。
【００４５】
点効果を扱う時は、フレームを重複なしの固有のブロックに分解することが良好に機能する。しかし、面積効果に対しては、同じ重複なしのブロックは、依然として出力に寄与することができるが、エッジ回りで余分なピクセルデータが必要になる場合がある。例えば、３×３ピクセルブロック３０４を修正又は出力するためには、５×５ピクセルブロックが必要である場合がある。
【００４６】
ブロック３０４に対しては、効果により修正することができるブロック３０４の部分を「主データ」と呼ぶ。面積効果の処理を助けるために「エッジデータ」４０６と呼ぶ主データ４０２に接する付加的なデータが必要である場合がある。主データ４０２及びエッジデータ４０６の結合は、ブロック３０４の「全データ」と呼ぶ。同様に、主データ４０２により覆われた面積は、「内側範囲」４０４と称し、一方、主データ４０２及びエッジデータ４０６の結合により覆われた面積は、「外側範囲」４０８と呼ぶ。
【００４７】
必要なエッジデータ４０６の量は、面積効果に依存する。例えば、「畳み込み効果」は、各ブロック３０４に対するエッジデータ４０６に値する１ピクセル幅の周囲を必要とするであろう。図４は、１２ｘ１２ピクセルフレーム３０２のブロック分割を示している。図４では、ピクセルフレーム３０２は、１６個の３ｘ３ピクセルブロック３０４（３０４−１から３０４−１６）に分割される。例えば、ブロック３０４−６は、内側範囲４０４を有する３ｘ３ピクセル主データ４０２を有することができるが、全データは、主データ４０２と外側範囲４０８を有する境界ピクセル幅エッジデータ４０６との両方を含む５ｘ５ピクセル領域を包含する。
【００４８】
この例においては、各ブロックのエッジデータ４０６は、少なくとも１つの近接ブロック３０４の主データ４０２と重なり合う。最大性能を達成するために、このエッジデータ４０６は、ブロック３０４を効果処理に関してできるだけ自己充足的にするために冗長的に含めることができる。フレーム３０２のエッジにあるブロック３０４は、確実にブロックを均一に処理することができるようにするために、加工されたエッジデータ４０６を含むことができる。例えば、このエッジデータ４０６は、フレームの３０２境界ピクセルのコピーを含むか又は固定値に設定することができる。
【００４９】
図４の例示的な実施形態では、ブロック３０４−６のエッジデータ４１０の全ては、近接ブロック３０４の内側範囲４０４内にあり、従って、ブロック３０４−６は、「内部ブロック」であると考えられる。対照的に、ブロック３０４−１６の２つのエッジは、フレーム３０２のエッジと一致しており、従って、ブロック３０４−１６のエッジデータ４０６の一部は、上述のように加工することが必要になる。ブロック作成時にエッジブロック３０４のエッジデータ４０６を加工することによって、個々の効果が特別な境界条件検査を行うことを不要とすると共に、効果が内部ブロックとエッジブロック３０４を区別することを不要とすることができる。
【００５０】
また、あらゆるエッジデータ４０６を除くブロック３０４のサイズを「主ブロックサイズ」と呼び、その理由は、これが最終出力画像フレームに寄与するブロック３０４の唯一の部分であるからである。エッジデータを含むブロックのサイズは、「全ブロックサイズ」と呼ぶ。
【００５１】
図４では、各ブロック３０４の主ブロックサイズは、９ピクセルとすることができ、一方、全ブロックサイズは、２５ピクセルとすることができる。これらのブロックは正方形であるので、各辺は、エッジデータ４０６のピクセルを出力ブロックサイズに加えるだけで計算することができる。
【００５２】
開示したブロック分割を空間的効果に関して説明したが、ブロック分割は、時間的領域においても機能することができることは、当業者によって理解されるであろう。時間的領域で機能する時には、ブロック３０４は、主に時間的に隣接するフレームからのピクセルを含み、全ブロックサイズは、空間的領域におけるような２次元ではなく、２又は３次元のいずれかとすることができる。
【００５３】
図５は、９ピクセルの各ブロック３０４及び２５ピクセルの全ブロックサイズの主ブロックサイズを示すが、当業者は、この実施例は、各次元に対して独立して各効果のエッジ要件を考慮することによって正方形以外のブロックに拡張することができることを認めるであろう。更に、この実施例は、多次元領域（ブロックが２次元でなくて多次元、すなわち、ｎ次元である場合）に拡張することができる。
【００５４】
パイプラインシステムにおけるブロックエッジ
複数の効果を収容する効果パイプラインという関連では、複数の面積効果の各々は、全ブロックサイズのエッジ要件を連続して組み合わせることになる。以下の例示的な実施形態は、各々が１ピクセル幅のエッジを必要とする３つの面積効果を含む効果パイプラインに対して説明する。しかし、所定の効果は、様々なエッジピクセル幅を必要とすることができ、エッジピクセル幅は、内側範囲４０４回りに均一に分配される場合もあれば、均一に分配されない場合もあることが理解されるであろう。
【００５５】
この例の主データ４０２は、９ピクセルの内側ブロックサイズ及び２５ピクセルの全ブロックサイズを有するブロック３０４を含むことができる。エッジデータ４０６を追加すると、結果として、パイプラインにおける第１の効果が主データ４０２の出力を生成するのに十分な情報を担持するサイズ２５ピクセルのブロックが得られる。しかし、第１の効果がブロック３０４を処理した状態で、パイプラインにおける面積効果は、データの残りの３×３ピクセルを使用して主データ４０２のデータを生成するのに十分なデータを有することができず、又は次の効果は、修正された主データ４０２と一致しない未修正エッジデータ４０６にアクセスすべきである場合がある。これは、ブロック３０４のエッジデータ４０６が、第１の効果がそれを受信した時と依然して同じものであり、一方、主データ４０２は、第１の効果の出力を反映することになるからである。このパイプライン状況に対処するためには、各連続的面積効果が出力を生成することができるのは漸進的により小さい領域に関する場合のみであるから、より大きな全ブロックサイズを供給することが必要であると考えられる。
【００５６】
図５Ａは、本発明によるパイプラインシナリオにおける３つの面積効果を処理する減少範囲戦略の例示的な実施形態を示している。この例示的な実施形態は、パイプラインにおける各連続的面積効果に対して余分なエッジを追加して各先行面積効果がその後の効果のエッジデータ４０６を出力の一部として処理することを可能にすることにより、連続的面積効果からの低減を克服するものである。
【００５７】
図示の減少範囲戦略においては、ピクセルブロックは、３つの面積効果により連続的に処理される。この戦略で、ブロック３０４の外側範囲は、ブロック３０４が各効果により処理される時に連続的に収縮する。上述の例の状況の範囲では、第１の効果は、８１ピクセルを処理して４９ピクセルを出力又は修正し、第２の効果は、修正４９ピクセルを処理して２５ピクセルを出力又は修正し、第３の効果は、修正２５ピクセルを処理して内側範囲４０４内の９ピクセルを出力又は修正する。
【００５８】
第１の段階では、主ブロックサイズは、９ピクセルであり、一方、全ブロックサイズは、８１ピクセルである。第１の面積効果には、外側範囲４０８−３を有するブロック３０４が供給され、それによって外側範囲４０８−２を有する全データの出力が生成される。第２の面積効果には、外側範囲４０８−２を有する全データが供給され、それによって外側範囲４０８−１を有する全データの出力が生成される。第３の面積効果には、次に、外側範囲４０８−１を有するブロック３０４が供給され、第３の面積効果は、主データ４０２の出力を生成する。
【００５９】
図５Ｂは、低減範囲戦略を用いて図５Ａの３個の効果を考慮して望ましい主データ領域の出力を発生させるのに必要な外側範囲のサイズを判断する方法を示している。ブロックの外側範囲４０８を判断する方法として、望ましい内側範囲４０４（この例では３×３ピクセル）を取ってパイプラインにおける最終面積効果に対してエッジデータ４０６を追加し（５×５ピクセルの外側範囲４０８−１を得るために）、次に、中間面積効果に後戻り（７ｘ７ピクセルの外側範囲４０８−２を得るために）、次に、最終効果の外側範囲５０６に後戻る（９×９ピクセルの外側範囲４０８−３を得るために）。この処理により、９×９ピクセルの外側範囲４０８−３を有するブロックサイズが発生する。
【００６０】
これを計算する代替方法は、単にパイプラインにおける各効果により必要とされるエッジ次元を主データ４０２の次元に追加するというものである。主データ４０２のブロックの未加工次元が３×３ピクセルであり、各効果が１ピクセル境界（各次元で付加的な２ピクセル）を必要とする場合、全次元は、９ｘ９である。
【００６１】
低減範囲戦略は、パイプラインを横断中に各ブロック３０４に与えられた高い独立度から恩典を受ける。すなわち、ブロック３０４は、パイプラインに入った状態で、あらゆる他の隣接ブロック３０４と同期する必要がなく、また、データブロック３０４がパイプラインを出るまで、データの一体性を保証するに当たって制御機構が不要である。それによってパイプライン待ち時間において最大の自由度が得られる。
【００６２】
低減範囲戦略は、最終段階を除きパイプラインにおける全ての効果の全データの処理時間及び格納の形態で余分なコストを招くが、コスト及び待ち時間は、点効果と面積効果を区別してパイプラインの終わりに向けてあらゆる点効果を配置する（最終面積効果の後）ことによって低減することができる。
【００６３】
図６Ａは、効果のパイプラインを処理する固定範囲戦略を示す図である。一定の範囲戦略においては、各ブロック３０４が隣接ブロック３０４と同期化される前に、１つの効果のみがパイプラインの各段で処理される。所定のブロック３０４は、隣接ブロックと同期化された後、パイプラインにおける次の効果により処理することができる。この戦略は、何らかの余裕分パイプライン待ち時間を増大させることができるが、計算オーバーヘッドを低減する。
【００６４】
図６Ａは、全ての効果の内側範囲４０４及び外側範囲４０８が同じことである固定範囲戦略の例示的な実施形態を示している。図６Ａでは、各効果は、全データを入力として用いて主データ４０２を処理するだけである。各面積効果が処理された後の隣接ブロック３０４との同期により、次の効果が処理される前に、ブロック３０４内のデータの全てが隣接ブロック３０４の主データ４０２で更新されることを保証する。
【００６５】
固定範囲戦略の効率は、ブロック３０４が処理している命令により達成することができる。固定範囲戦略では隣接ブロック３０４間で効果後のデータの同期が必要であるので、所定の第２の（又は現在の）効果は、第１の（又は以前の）効果がブロック３０４に隣接する所定のブロックの全てを処理し、かつ所定のブロックのエッジデータ４０６が隣接ブロック３０４と同期化されるまで、所定のブロックの処理を開始することはできない。例示的に、第１の効果により処理された後、ブロック３０４−１は、第２の効果により処理される前に周囲ブロック、すなわち、ブロック３０４−２、３０４−５、及び３０４−６と同期化すべきである。同様に、ブロック３０４−６は、ブロック３０４−１、３０４−２、３０４−３、３０４−５、３０４−７、３０４−９、３０４−１０、及び３０４−１１と同期化すべきである。
【００６６】
図６Ｂは、連続した順序でブロックが処理されるブロック横断戦略の例示的な実施形態を示している。この戦略は、最も簡単な処理戦略であるが、最も効率的なものとすることはできない。マルチプロセッサ１００の並列処理を考慮して、ＰＰＵ１０４は、隣接ブロック３０４が処理された直後に所定のブロックのエッジデータ４０６の同期を開始することができる。例として、第１の効果により処理された後、ブロック３０４−１は、同期させることができる前に、５つのブロック、すなわち、ブロック３０４−２〜３０４−６が処理されるのを待たなければならない。同様に、第１の効果により処理された後、ブロック３０４−６は、同期させることができる前に、５つのブロック、すなわち、ブロック３０４−７〜３０４−１１が処理されるのを待たなければならない。従って、代替ブロック横断戦略は、固定範囲戦略の並列処理を改善することができる。
【００６７】
図６Ｃは、代替ブロック横断戦略の例示的な実施形態を示すが、ブロックは、所定のブロックを同期させることができる前に処理すべきであるブロック３０４の数を低減するように処理される。例示的に、第１の効果により処理された後、ブロック３０４−１は、同期させることができる前に、３つの他のブロック、すなわち、ブロック３０４−２、３０４−５、３０４−６が処理されるのを待たなければならない。ブロック３０４−１に対しては、両方の戦略では、３つの隣接ブロック３０４とのデータのやり取りが必要である。代替ブロック横断戦略の方が有利であり、その理由は、３つの隣接ブロック３０４が処理される間に実際に待つべきブロック３０４数は、固定（４ブロック）であり、かつフレーム内のブロック３０４総数とは独立しているからである。対照的に、図６Ｂの本来の横断戦略においては、たとえブロック３０４−１が同じ番号のブロック３０４の従属ブロックであったとしても、ブロック３０４−１は、同じ横列の他のブロック（３０４−２〜３０４−４）及びフレームの次の横列の２つの従属ブロック（３０４−５及び３０４−６）が処理されるのを待つ必要がある。これには、３つの従属ブロック（３０４−２、３０４−５、３０４−６）及び２つの独立ブロック（３０４−３、３０４−４）があり、後者が、横断戦略のため含まれる（上下の全ての横列に対しては、各横列において左又は右に横断する）。これは、大きなブロック分布を備えたフレームの場合の方が著しい（例えば、１００ｘ１００ブロックフレームに対しては、ブロック０は、図６Ｂの戦略を利用すると１０１個のブロック、すなわち、３つの従属ブロック及び９８個の独立ブロックを待つ必要があるが、図６Ｃの戦略を利用すると依然として僅か４つのブロック３０４、すなわち、３つの従属ブロック及び１つの独立ブロックである）。
【００６８】
図６Ｃは、処理ブロック３０４の１つの代替戦略を示すが、この戦略は、例示的なものであり、ブロック３０４を処理するための潜在的な横断順序を変える利点を示すことを目的とする。更に、代替横断戦略も、本発明の精神の範囲内で可能であろう。例えば、代替戦略は、異なるブロック分割戦略に向けてパイプラインにおける効果、メモリ容量、プロセッサ速度などを最適化することによって性能を改善することができる。
【００６９】
パイプライン処理
図７は、本発明によりマルチコアプロセッサ１００上で効果パイプラインを実行する方法の例示的な実施形態を示している。処理７００は、様々なシステム上で実行することができるが、明瞭さを期すためにマルチコアプロセッサ１００に対して説明する。
【００７０】
段階７０２で、マルチコアプロセッサ１００は、効果パイプラインを識別する入力を受け取ることができる。効果パイプラインは、ピクセルブロック３０４を処理するためにＳＰＵ１０４により実行することができる複数の効果を識別することができる。複数の効果をＰＰＵ１０２により分析して、各効果に対して空間的／時間的エッジ要件を識別することができる。
【００７１】
段階７０４で、段階７０２での分析に基づいて、効果は、複数のＳＰＵ１０４間で割り当てかつ分配することができる。ＰＰＵ１０２は、各ＳＰＵ１０４に１つの効果を割り当てることができる。代替的に、ＰＰＵ１０２は、単一ＳＰＵ１０４に複数の簡単で迅速に実行される効果を割り当て、複数のＳＰＵ１０４に複雑でゆっくりと実行される効果を割り当てることができる。更に別の代替的な実施形態では、システムは、動的負荷平衡に依存して様々なＳＰＵ１０４間で効果の割り当てを管理することができる。
【００７２】
段階７０６で、ＰＰＵ１０２は、効果パイプラインに従って処理対象の画像フレーム３０２を受け取ることができる。代替的に、ＰＰＵ１０２は、メモリインタフェース１０６又は他のあらゆるアクセス可能なデータソースを通じてメモリから画像フレーム３０２を読み取ることができる。
【００７３】
段階７０８で、ＰＰＵ１０２は、画像フレーム３０２からデータブロック３０４を発生させることができる。データブロック３０４の次元及び構造は、予め定めることができ、又は個々の効果、並びに使用する処理戦略の処理要件に依存するとすることができる。
【００７４】
段階７１０で、ＰＰＵ１０２は、各データブロック３０４を効果パイプラインにおける第１の効果に割り当てたＳＰＵ１０４に供給することができる。各データブロック３０４は、次に、効果パイプラインによって定められた順序で効果パイプラインから複数の効果を横断することができる。
【００７５】
段階７１２で、データブロック３０４が最終効果により処理された後、効果パイプラインの判断に従ってメモリキャッシュ１０３又は他のメモリ内でＰＰＵ１０２によりデータブロック３０４を集約することができる。ＰＰＵ１０２は、次に、画像フレーム３０２内に集約データブロック３０４を結合することができる。
【００７６】
段階７１４で、いずれかの更に別の画像フレーム３０２を効果パイプラインを通じて処する必要がある場合、処理は、段階７０６に戻り、そうでなければ処理は終了する。
【００７７】
図１１は、従来技術においては、６段効果パイプラインの予想待ち時間は、各フレームが、定義上、処理するのに１つのフレーム時間を消費するので、６フレームであることを示している。
【００７８】
図８は、ブロック３０４まで作業の最小分量が低減された修正効果パイプラインを示している。この実施形態では、各ブロック３０４は、１フレーム３０２の半分と同等であり、従って、１／２フレーム時間で各効果により処理される。図８に示すように、それによって待ち時間を６フレームから３と１／２フレームに低減することができる。
【００７９】
図８では、第１の半フレームＦ１Ｂ１は、３つのフレーム内で処理される（１／２フレームｘ６つの効果）。第２の半フレームＦ１Ｂ２も、３つのフレーム内で処理されるが、第１の半フレームＦ１Ｂ１の１／２フレーム後にのみパイプラインに入る。従って、第２の半フレームＦ１Ｂ２は、３つの１／２フレーム以内でパイプラインを出て（１／２フレームｘ６つの効果＋１／２フレーム遅延）、従って、全フレーム時間待ち時間は、第１のフレーム３０２全体に対しては３と１／２フレームになる。
【００８０】
図９に示す例示的な実施形態は、図８のブロックベースのフレーム内であるが、ブロックサイズが１／４フレームに低減された状態で同じ効果パイプラインを使用する。この実施形態により、従来技術と比較して、再びブロックサイズを低減することによって６つのフレームから２と１／４フレームへのパイプライン待ち時間改善が得られる。
【００８１】
図９では、第１の１／４フレームＦ１Ｂ１は、１と１／２フレーム内で処理される（１／４フレームｘ６つの効果）。第２の１／４フレームＦ１Ｂ２も、１と１／２フレーム内で処理されるが、第１の１／４フレームＦ１Ｂ１の１／４フレーム後にのみパイプラインに入る。従って、第２の１／４フレームＦ１Ｂ２は、１と３／４フレーム以内にパイプラインを出る（１／４フレーム×６つの効果＋１／４フレーム遅延）。第３及び第４の１／４フレームＦ１Ｂ３及びＦ１Ｂ４も、第１の１／４フレームＦ１Ｂ１の１／２フレームと１／４フレーム後にパイプラインを出る。従って、第１のフレームは、２と１／４フレーム以内で処理される。
【００８２】
上述の例は、「フレームベースの効果処理」に優る「ブロックベースの効果処理」の利点を明確に示すものである。ブロックサイズが減り続ける時に、パイプライン待ち時間に関して取得することが可能になる利得は高くなるが、利得は、漸進的に小さくなる。最終的には、データブロック３０４のデータ転送及び他の処理の計算上の面から導入される待ち時間は、更に別のブロック縮小からの利得を超える。
【００８３】
従来のフレームベースのアーキテクチャと同様に、ブロックベースのシステムのパイプライン待ち時間は、連鎖内の最も速度が遅い効果の処理時間とパイプラインにおける効果（又は段）の個数との積と定めることができる。しかし、ブロックベースのアーキテクチャに切り換えると、これは、データの１フレーム３０２を処理するのに最も速度が遅い効果が掛かる時間に、データの１ブロック３０４を処理するために最も遅い効果Ｍが斯かる時間と効果（又は段）の数から１を引いたものとの積を加えた合計に変形される。ブロックベースのパイプライン待ち時間は、計算時間として、以下のように計算することができる。
ＰＬCT＝（Ｓ*ＴBM）＋（（Ｎ−１）*ＴBM）          （式３）
ここで、
・ＰＬCTは、計算時間としての「パイプライン待ち時間」である。
・Ｎは、パイプラインにおける段／効果の個数である。
・Ｓは、各フレーム３０２から発生したブロック３０４の個数である。
・ＴBMは、パイプラインにおける最も速度が遅い効果Ｍによりフレームを処理するのに必要とされる時間である。
【００８４】
ブロック処理に関連のオーバーヘッド費用は無視することができると仮定すると、これは、以下の処理時間を計算する。
ＴFM＝（Ｓ*ＴBM）          （式４）
例えば、Ｓ＝２である図７に示すブロックベースのシステムのＰＬCTは、（２*６０）＋（５*６０）＝４２０ｍｓになる。ＴBMは、単にＴFM／Ｓとして計算するが、その理由は、ブロック処理への切換えに関連のあらゆるオーバーヘッド費用を無視しているからである。
【００８５】
フレーム時間でＰＬを計算すると、以下の式が得られる。
ＰＬFT＝ＰＬCT／ＦＲ          （式５）
ここで、
・ＰＬFTは、フレーム時間での「パイプライン待ち時間」である。
・ＰＬCTは、計算時間としての「パイプライン待ち時間」である。
・ＦＲは、有効フレームレートである。
【００８６】
上述の数を用いると、図８の例のＰＬFTは、４２０／１２０＝３．５個のフレームであり、これは、先に計算した数字と同一である。図９に示す例により、２７０ｍｓのＰＬCT及び２．２５個のフレームのＰＬFTが得られる。
【００８７】
上述のように、これらの例では、ブロックベースの処理のオーバーヘッドが無視することができるものであると仮定されている。現実のシナリオでは、パイプラインにおいて効果が先に位置するほど計算時間が長くなるか（減少範囲戦略）又は同期オーバーヘッドが増大し、従って、パイプライン待ち時間を低減することができる（固定範囲戦略）。
【００８８】
メモリ要件
ブロックベースのシステムには、パイプラインのメモリ使用量に関して有意な利点がある。従来のフレームベースのＮ段パイプラインでは、全ての段を作動させておく少なくともＮ個のフレームバッファが必要である。フレームＩ／Ｏが効果パイプラインの外側で処理されるので、このようなシステムは、その目的に必要な余分なフレームバッファ数が数個になる（必要最小限で２つ、Ｉ／Ｏ作動の二重バッファリングを使用した場合は４つ）。従って、パイプラインを処理するのに必要な最小フレームバッファ数は、実質的にＮ＋２である。
【００８９】
Ｐがパイプラインに向けてシステム内で利用可能なプロセッサ要素の数を表す場合、必要とされるバッファは、最低（Ｐ、Ｎ）個のバッファになると考えられ、その理由は、プロセッサ要素の数がパイプラインにおける段の数よりも小さい場合に、システムは、Ｐ個のフレーム３０２を同時に処理することができるのみであるからである。逆に、パイプライン段の数がプロセッサ要素の数よりも小さい場合、システムは、付加的なプロセッサ要素が空作動のままになることになるので、Ｎ個のバッファを同時に処理することができるのみである。
【００９０】
従来のフレームベースのパイプラインにより必要とされるフレームバッファの最小数を計算する公式は、以下のように導出することができる。
ＹF＝ｍｉｎ（Ｐ、Ｎ）＋２          （式６）
ここで、
・ＹFは、パイプラインを処理するのに必要な最小フレームバッファ数である。
・Ｐは、利用可能なプロセッサ要素の数である。
・Ｎは、パイプラインにおける段／効果の個数である。
【００９１】
バッファの実際のメモリ要件は、従って、以下のようになる。
ＭFBA＝ＹF*ＺF          （式７）
ここで、
・ＭFBAは、フレームベースの手法によるパイプラインに対してバッファに必要とされるバイトでの最小メモリである。
・ＹFは、パイプラインを処理するのに必要な最小フレームバッファ数である。
・ＺFは、バイトでの各フレームバッファのサイズである。
【００９２】
ブロックベースのシステムには、パイプラインのメモリ使用量に関して有意な利点がある。ブロックはフレームより小さいので、メモリ節約は、短いパイプの場合でさえ有意なものとすることができる。以前の論理により、ブロックベースのシステム内で必要なバッファの最小数は、ここでもまた、Ｉ／Ｏ作動に対してはｍｉｎ（Ｐ、Ｎ）ブロックバッファに少なくとも２つのフレームバッファを加えたものとすることができる。上述のように、以下のようになる。
ＹB＝ｍｉｎ（Ｐ、Ｎ）          （式８）
ここで、
・ＹBは、パイプラインを処理するのに必要なフレームバッファの最小数である。
・Ｐは、利用可能なプロセッサ要素（ＳＰＵ１０４）の数である。
・Ｎは、パイプラインの段の個数である。
【００９３】
しかし、バッファの全てに関する実際のメモリ要件は、以下のようになる。
ＭBBA＝ＹB*ＺB＋２*ＺF          （式９）
ここで、
・ＭBBAは、ブロックベースの手法によるパイプラインに対してバッファに必要とされるバイトでの最小メモリである。
・ＹBは、パイプラインを処理するのに必要なブロックバッファの最小数である。
・ＺＢは、バイトでの各ブロックのサイズである。
・ＺＦは、バイトでの各フレーム３０２バッファのサイズである。
【００９４】
例として、１つのフレームを保持するのに必要なメモリが８１９２ＫＢ（次元２０４８×１０２４のピクセルＨＤフレーム当たりに４バイトを保持するのに必要とされるサイズ）であり、各フレーム３０２が次元２５６×２５６のブロック３０４に分割されるＳＰＵシステム上の６段パイプラインにおいて、各ブロック３０４を保持するのに必要なサイズは、２５６ＫＢであり、フレーム３０２当たりに３２個のブロック３０４がある（簡潔さを期すためにエッジサイズ＝０）。
【００９５】
従来のフレームを基本する手法に関する公式を用いると、フレームベースのパイプラインシステム内のバッファに必要とされるメモリは、以下のようになる。
ＭFBA＝［ｍｉｎ（Ｐ、Ｎ）＋２］*ＺＦ＝［ｍｉｎ（４、６）＋２］*８１９２＝６*８１９２＝４９１５２ＫＢ
【００９６】
比較すると、ブロックベースの手法を用いて同じパイプラインを処理するのに必要な最小メモリは、以下のようになる。
ＭBBA＝［ｍｉｍ（Ｐ、Ｎ）］*ＺＢ＋２*ＺＦ＝［ｍｉｍ（４、６）］*２５６＋２*８１９２＝４*２５６＋２*８１９２＝１７４０８ＫＢ
【００９７】
更に、２つの必須のフレームバッファは、ブロックベースのシステムにおいて使用される１７ＭＢのうちの１６ＭＢを消費することに注目することができる。従って、これらの必須のバッファを除去することによって、類似のメモリ使用量の差は、フレームベースのシステムに対しては３２ＭＢ、それに対してブロックベースのシステムに対しては１．５ＭＢになる。たとえブロックベースの手法の方が連続的面積効果に対して大幅に多くのメモリを必要とするとしても、メモリ消費量は、フレームベースのシステムに近づく可能性はない。
【００９８】
ＩＩＩ．負荷平衡
これまでに示した例示的な実施形態では、形成する効果の全てが同量のデータを処理するのに同量の時間を消費すると仮定している（フレーム３０２又はブロック３０４である場合）。しかし、効果は、アルゴリズム上及び実行上の複雑性に基づいて掛かる時間量が異なる場合がある。効果が異なると処理時間も異なることにより、パイプライン待ち時間が短くなる恐れもあり、速度が最も遅い効果が障害になる。この障害により、次に、下流側ＳＰＵ１０４が作業を奪われる場合がある。バッファの数を制限した場合、それによってメモリが消費されると上流側ＳＰＵ１０４も作業を奪われる場合がある。
【００９９】
図１０Ａは、効果の個々の計算時間が大幅に変動するパイプラインの例を示している。図１０Ａでは、効果ＦＸ１、ＦＸ２、及びＦＸ４は、２０ｍｓの計算時間を必要とし、効果ＦＸ３は、１６０ｍｓの計算時間を必要とし、効果ＦＸ５及びＦＸ６は、１０ｍｓの計算時間を必要とする。この実施形態では、様々なブロックは、効果ＦＸ１でパイプラインに入ると効果ＦＸ２〜ＦＸ６の各々を連続的に通過するので、障害は、効果ＦＸ３で発生する。
【０１００】
図１０Ａの処理パイプラインは、各ＳＰＵ１０４が単一の効果を割り当てられる図８及び図９に対して説明した実施形態と類似のものである。しかし、図８及び図９では、ブロック待ち時間は６ブロックであったのに対して、図１０では、全パイプライン待ち時間は、効果３において発生した障害のために大幅に長くなる。それによって下流側効果（従って、他のＳＰＵ１０４）が休止状態で時間を浪費する。長時間では、この障害は、結局は、ただ上流側ＳＰＵ１０４を使用中に保つために、出力終了時にいかなる恩典もなく非常に多くのバッファを使用する場合がある。
【０１０１】
静的負荷平衡には、この問題に対する第１の解決法がある。静的負荷平衡は、関わっている様々な効果（ＦＸ１〜ＦＸ６）の計算時間を考慮することによって効果の静的解析を行う段階を含む。これは、効果の以前の分配を考慮するものであり、これは、速度が遅い効果にリソース（例えば、複数のＳＰＵを専従させる）の数を増大させながら短い計算効果を単一のリソース（すなわち、１つ又は数個のＳＰＵ）に結合する段階を含むことができる。
【０１０２】
図１０Ｂは、負荷均衡が取れた効果パイプラインの例を示している。図１０Ｂの効果処理時間は、図１０Ａと同一であるが、効果は、異なるＳＰＵ１０４（１０４−１〜１０４−６）間で負荷均衡が取れている。図１１Ｂでは、ＳＰＵ１０４−２〜１０４−５は、効果ＦＸ３専用である。ＳＰＵ１０４−６には、効果ＦＸ４、ＦＸ２が割り当てられ、一方、ＳＰＵ１０４−６には、効果ＦＸ４、ＦＸ５、及びＦＸ６が割り当てられる。この分配は、ＳＰＵ１０４の全てを利用すると同時に、バッファ使用量を制限して全体的な性能を加速の速度を上げるものである。効果ＦＸ３により消費される過大な処理時間は、複数のＳＰＵ１０４（１０４−２〜１０４−５）にわたって分配されることが特に明らかである。それによって各ブロック３０４が効果ＦＸ２を出ると、効果ＦＸ３を処理する利用可能なＳＰＵ１０４があることが保証される。更に、各ブロック３０４が効果ＦＸ３を出ると、効果ＦＸ４〜ＦＸ６を割り当てられたＳＰＵ１０４が、直ちに利用可能である。
【０１０３】
「静的負荷平衡」は、固定機能パイプラインに対して十分に働くことができるが、一般効果パイプライン、又は効果処理時間が入力データの複雑性又は外部パラメータに基づいて変動する固定機能パイプラインであってもその必要性に対して十分に拡張することができない。
【０１０４】
「動的負荷平衡」は、外部入力（処理時間がユーザにより供給されたパラメータで変わる効果など）に基づいて又は作業負荷自体（符号化データ内の圧縮変動に基づく復号器など）に基づいて、処理負荷がフレーム単位又はブロック単位で変動する場合に静的負荷平衡の代替を提供する。
【０１０５】
フレームベースの処理からブロックベースの処理への切換えは、均衡を取るためにスケジューラーが利用可能な同期点の増加があり、局在化する作業の差異を考慮に入れることができるので、スケジューリングシステム内の動的負荷均衡の効果増大を可能にするものである（例えば、コントラストの低いデータを収容する同じフレーム内のブロック及びコントラストの高いデータを収容するブロックは、効果が異なれば性能特性も異なり、ブロック基本とする動的負荷均衡への切換えにより、システムは、より細かいレベルでこれに適応することができる）。
【０１０６】
本明細書で説明する処理、システム、方法、発見的手法などに関して、このような処理の段階などは、ある一定の順序付けされたシーケンスに従って行われると説明したが、このような処理は、本明細書で説明する順序以外の順序で実行される上述の段階で実施することができることを理解すべきである。ある一定の段階を同時に実行することができ、他の段階を追加することができ、又は本明細書で説明するある一定の段階を省略することができることを更に理解すべきである。処理はまた、クライアント、サーバ、及び／又はデータベース上のコンピュータ実行可能命令（例えば、１つ又はそれよりも多くのスクリプトとして）、格納済み手順、実行可能プログラムなどとして実施することもできる。換言すれば、処理の説明は、ある一定の実施形態を示す目的で行うものであり、いかなる点においても特許請求する発明を制限すると解釈すべきではない。
【０１０７】
従って、以上の説明は、例示的なものであり、かつ制限的なものではないように意図していることは理解されるものとする。示した例以外の多くの実施形態及び用途は、以上の説明を読むと即座に当業者に明らかであるであろう。本発明の範囲は、以上の説明を参照するのではなく、代わりに特許請求の範囲及びそのような特許請求の範囲が権利を与える均等物の完全な範囲を参照して判断すべきである。将来の開発が本明細書で説明する技術分野で行われ、かつ言及したシステム及び方法は、このような将来の実施形態に組み込まれることが予想かつ意図されている。要するに、本発明は、修正及び変形が可能であり、かつ特許請求の範囲だけにより制限されることを理解すべきである。
【０１０８】
開示した並行処理方法は、オーディオ効果パイプライン、３Ｄ効果パイプライン、又はデータを別々のブロックに細分化して効果のパイプラインを通じて処理することができるあらゆる状況に適用することができる。
【０１０９】
本明細書で説明するような計算デバイス（例えば、プロセッサ、クライアント、サーバ、端末など）は、一般的に、実行可能命令を含むことができる。更に、プロセッサは、ＳＰＵ、ＰＰＵ、ＧＰＵのようなあらゆる数の処理構成要素をそれ自体が収容するあらゆるデバイスを含むことができる。コンピュータ実行可能命令は、Ｊａｖａ（登録商標）、Ｃ、Ｃ＋＋、アセンブリなどを含むがこれらに限定されず、かつ単独で又は組合せで、当業者に公知の様々なプログラム言語及び／又は技術を用いて作成されたコンピュータプログラムからコンパイル又は解釈することができる。一般的に、プロセッサ（例えば、マイクロプロセッサ）は、命令（例えば、メモリ、コンピュータ可読媒体など）を受け取ってこれらの命令を実行し、従って、本明細書で説明する処理の１つ又はそれよりも多くを含む１つ又はそれよりも多くの処理が実行される。このような命令及び他のデータは、様々な公知のコンピュータ可読媒体を使用して格納及び送信することができる。
【０１１０】
コンピュータ可読媒体は、コンピュータによって読み取ることができるデータ（例えば命令）を供給することに関わるあらゆる媒体を含む。このような媒体は、不揮発性媒体、揮発性媒体、及び伝送媒体を含むがこれらに限定されない多くの形を取ることができる。不揮発性媒体は、例えば、光ディスク又は磁気ディスク及び他の永続メモリを含む。揮発性媒体は、典型的に主メモリを構成する動的ランダムアクセスメモリ（ＤＲＡＭ）を含む。
【０１１１】
計算デバイス間及び計算デバイス内の通信には、プロセッサに結合されたシステムバスを含むワイヤを含む、同軸ケーブル、銅ワイヤ、光ファイバケーブルを含む伝送媒体を使用することができる。伝送媒体は、音波、光波、及び高周波（ＲＦ）及び赤外線（ＩＲ）データ通信中に発生するような電磁放射を含むか又は伝達することができる。一般的な形のコンピュータ可読媒体は、例えば、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、あらゆる他の磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤ、あらゆる他の光媒体、パンチカード、紙テープ、穴のパターンを有するあらゆる他の物理媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＥＰＲＯＭ、あらゆる他のメモリチップ又はカートリッジ、以下に説明する搬送波、又はコンピュータが読み取ることができるあらゆる他の媒体を含む。
【０１１２】
従って、本発明の実施形態は、パイプライン画像処理エンジンを生成かつ提供する。本発明をそのある一定の実施形態を参照してかなり詳細に説明したが、本発明は、本発明の精神又は範囲から逸脱することなく様々に実施することができる。従って、以下の特許請求の範囲は、いかなる点においても本明細書に含まれる実施形態の説明に限定されてはならない。
【符号の説明】
【０１１３】
１００  マルチコアプロセッサ
１０３  ローカルメモリキャッシュ
１０４  単一プロセッサユニット（ＳＰＵ）
１１０  超高速内部バス
【図１】
2010067276.tif 000003
【図２】
2010067276.tif 000004
【図３】
2010067276.tif 000005
【図４】
2010067276.tif 000006
【図５Ａ】
2010067276.tif 000007
【図５Ｂ】
2010067276.tif 000008
【図６Ａ】
2010067276.tif 000009
【図６Ｂ】
2010067276.tif 000010
【図６Ｃ】
2010067276.tif 000011
【図７】
2010067276.tif 000012
【図８】
2010067276.tif 000013
【図９】
2010067276.tif 000014
【図１０Ａ】
2010067276.tif 000015
【図１０Ｂ】
2010067276.tif 000016
【図１１】
2010067276.tif 000017
【外国語明細書】
2010067276.tif 000018
2010067276.tif 000019
2010067276.tif 000020
2010067276.tif 000021
2010067276.tif 000022
2010067276.tif 000023
2010067276.tif 000024
2010067276.tif 000025
2010067276.tif 000026
2010067276.tif 000027
2010067276.tif 000028
2010067276.tif 000029
2010067276.tif 000030
2010067276.tif 000031
2010067276.tif 000032
2010067276.tif 000033
2010067276.tif 000034
2010067276.tif 000035
2010067276.tif 000036
2010067276.tif 000037
2010067276.tif 000038
2010067276.tif 000039
2010067276.tif 000040
2010067276.tif 000041
2010067276.tif 000042
2010067276.tif 000043
2010067276.tif 000044
2010067276.tif 000045
2010067276.tif 000046
2010067276.tif 000047
2010067276.tif 000048
2010067276.tif 000049
2010067276.tif 000050
2010067276.tif 000051
2010067276.tif 000052
2010067276.tif 000053
2010067276.tif 000054
2010067276.tif 000055
2010067276.tif 000056
2010067276.tif 000057
2010067276.tif 000058
2010067276.tif 000059
2010067276.tif 000060
2010067276.tif 000061
2010067276.tif 000062
2010067276.tif 000063
2010067276.tif 000064
2010067276.tif 000065
2010067276.tif 000066
2010067276.tif 000067
2010067276.tif 000068
2010067276.tif 000069
2010067276.tif 000070