(57)【特許請求の範囲】
【請求項１】
各種データ粒度における固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されていない場合、n個頂点とm個エッジを含む細いデータ粒度のデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにエッジカットの総数の最大値を計算するように、n個要素を有するベクトルｘを用意し、xtLx=Σ(xi-xj)2及び(vi,vj)∈E(G)を成立させるステップであって、前記n個要素は、前記データフローグラフGのn個頂点に関連するn個変数であり、(vi,vj)∈E(G)は、すべての前記viがvjに隣接する時の操作対を表すステップと、
細いデータ粒度における固有データ転送速度の最大数量を推定するように、前記最大値を使用するステップと、
細いデータ粒度のデータフローグラフGをカプセル化して、粗い粒度のデータフローグラフG 'をビルドする後、粗い粒度のデータフローグラフG 'に対応するラプラス行列L’によって粗いデータ粒度における前記固有データ転送速度を定量するステップと、
各種データ粒度の定量結果から対応する平均及び瞬時のデータ転送速度を得るステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
【請求項２】
i=jが成立する時、L(i,j)=degree(vi)（viの自由度）が成立し、viがj番目の頂点vjに隣接する時、L(i,j)=-1が成立し、そうでないと、L(i,j)=0が成立することを特徴とする請求項１に記載の固有データ転送速度を定量する方法。
【請求項３】
degree(vi)は、i番目の頂点viに接続されたエッジの総数を示し、Lのi番目の対角要素は、i番目の操作に接続された操作又はデータの総数を示し、Lの非対角要素は、二つの操作が接続されているかどうかを示すことを特徴とする請求項２に記載の固有データ転送速度を定量する方法。
【請求項４】
ベクトルxの各要素は、１又は-１である値を有する時、前記データフローグラフGは、二つのサブグラフに分けられ、二つの隣接する頂点が同じ値が与えられる時、二つの隣接する頂点が同じ前記サブグラフに属し、二つの隣接する頂点が異なる値が与えられる時、二つの隣接する頂点が異なる前記サブグラフに属することを特徴とする請求項１に記載の固有データ転送速度を定量する方法。
【請求項５】
前記xtLx=4*エッジカットの総数であることを特徴とする請求項４に記載の固有データ転送速度を定量する方法。
【請求項６】
各種データ粒度における固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されている場合、n個頂点とm個エッジを含む細いデータ粒度のデータフローグラフG及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにインエッジカット、アウトエッジカット及び非エッジカットの各代表数字を取得するように、n個要素を有するベクトルxを用意してMxの値を計算するステップであって、前記n個要素は、前記データフローグラフGのn個頂点に関連するn個変数であるステップと、
余分のローカルストレージのサイズを推定するように、前記データムの再使用のために細いデータ粒度において必要な前記生起依存行列Mを使用するステップと、
細いデータ粒度のデータフローグラフGをカプセル化して、粗い粒度のデータフローグラフG 'をビルドする後、粗い粒度のデータフローグラフG 'に対応する生起依存行列M’によって粗いデータ粒度における前記固有データ転送速度を定量するステップと、
各種データ粒度の定量結果から対応する平均及び瞬時のデータ転送速度を得るステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
【請求項７】
viがj番目のエッジの尾部である時、M(i,j)=1が成立し、viがj番目のエッジの頭部である時、M(i,j)=-1が成立し、そうでないと、M(i,j)=0が成立することを特徴とする請求項６に記載の固有データ転送速度を定量する方法。
【請求項８】
前記Mx=y、yはベクトルであり、yの要素値が２を有する場合、yの要素は、対応するエッジがインエッジカットであることを示し、yの要素値が０を有する場合、yの要素は、対応するエッジ要素が非エッジカットであることを示し、yの要素が-２の値を有する場合、対応するエッジがアウトエッジカットであることを示すことを特徴とする請求項７に記載の固有データ転送速度を定量する方法。
【請求項９】
各種データ粒度における固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されていない場合、n個頂点とm個エッジを含む細いデータ粒度のデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
細いデータ粒度における固有データ転送速度の最大数量を推定するように、前記ラプラス行列Lを使用するステップと、
細いデータ粒度のデータフローグラフGをカプセル化して、粗い粒度のデータフローグラフG 'をビルドする後、粗い粒度のデータフローグラフG 'に対応するラプラス行列L’によって粗いデータ粒度における前記固有データ転送速度を定量するステップと、
各種データ粒度の定量結果から対応する平均及び瞬時のデータ転送速度を得るステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
【請求項１０】
各種データ粒度における固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されている場合、n個頂点とm個エッジを含む細いデータ粒度のデータフローグラフG及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
細いデータ粒度における最大データの再使用の状況下で固有データ転送速度の最小量を推定するように生起依存行列Mを使用するステップと、
前記データムの再使用のために細いデータ粒度において必要な余分のローカルストレージのサイズを推定するステップと、
細いデータ粒度のデータフローグラフGをカプセル化して、粗い粒度のデータフローグラフG 'をビルドする後、粗い粒度のデータフローグラフG 'に対応する生起依存行列M’によって粗いデータ粒度における前記固有データ転送速度を定量するステップと、
各種データ粒度の定量結果から対応する平均及び瞬時のデータ転送速度を得るステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願と優先権主張の相互参照
本出願は、台湾知的財産局での２０１１年１月１９日に出願された台湾特許出願第１００１０２１１号に基づく利益を主張し、当該国際特許出願の開示は、参照によって本明細書に組み込まれる。
【０００２】
本発明は、アルゴリズムの固有データ転送速度を定量する方法に関する。特に、固有データ転送速度の最大数量を推定するように、n個頂点とm個エッジを含むデータフローグラフ（dataflow graph）G及びixj要素L(i,j)を有するラプラス行列（Laplacian matrix）Lを用意する方法に関する。
【背景技術】
【０００３】
固有なアルゴリズムの複雑度の抽出と分析に基づいて、アルゴリズムとアーキテクチャの両方を探索できるアルゴリズム/アーキテクチャ同時探索（Architecture Co-exploration、ＡＡＣ）の設計方法論は、新興の電子システムレベル（ESL）設計時代の設計パラダイムになる。アルゴリズムの固有データ転送速度は、現代と将来の信号及び情報処理の応用で採用されるより複雑なアルゴリズムのための汎用プラットフォームの帯域幅の探索を容易にすることができる重要な複雑度メトリックの一つである。したがって、アルゴリズムによって必要とされる固有データ転送速度を定量化することは、同時にアルゴリズムやアーキテクチャの両方を最適化するために必要不可欠なことになる。
【０００４】
Ravasiらは、カスタマイズ可能な仮想メモリアーキテクチャに基づくデータ転送と保存必要条件のソフトウェア計測と推定によってアルゴリズムの計算量を抽出することを提案していた（M. Ravasi and M. Mattavelli, “High-abstraction level complexity analysis and memory architecture simulations of multimedia algorithms,” IEEE Trans. on Circuits and Systems for Video Technology, pp. 673-684, Vol. 15, No. 5,  May 2005）。この技術は、効果的に、プラットフォームに依存しない計算複雑度を抽出することができる。しかし、データ転送や保存必要条件は、むしろカスタマイズ可能な仮想メモリアーキテクチャに依存しており、したがって、アルゴリズム自体に固有ではない。
【０００５】
既存の技術は、様々なターゲットプラットフォームにアルゴズムの複雑度をプロファイリングすることによって測定する（例えばM. Horowitz, A. Joch, F. Kossentini and A. Hallapuro, “H.264/AVC baseline profile decoder complexity analysis,” IEEE Trans. on Circuits and Systems for Video Technology, pp. 704-716, Vol. 13,  No. 7, July 2003）。前記Horowitzらの文献によると、アルゴリズムのデータ転送量は、ロードと保存の操作という点で測定される。この従来技術の主な欠点（前記Horowitzらの文献）は、データ転送速度での測定されたアルゴリズムの複雑度は、ターゲットプロセッサ向けのプラットフォームに依存し、アルゴリズム自体に依存することではない。したがって、測定された複雑度は再びアルゴリズムに対し固有なものではなく、ターゲットプラットフォームによって偏らせる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
データ転送速度は、アルゴリズムを表すデータフローのデータ粒度（data granularity）によって著しく影響されるので、複数のデータ粒度でのデータ転送速度の測定は、アルゴリズムの複雑度の特性を明らかにするために不可欠かつ必要である。しかし、二つの前記技術は、マルチグレインデータ転送速度の分析をサポートしていない。これは、二つの前記技術の主な欠点である。
【０００７】
出願人は、従来技術の欠点を鑑み、実験や研究を持続的に利用し、ついにアルゴリズムの固有データ転送速度を定量する方法を想到する。
【課題を解決するための手段】
【０００８】
本発明の第一態様によれば、固有データ転送速度を定量する方法は、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されていない場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにエッジカットの総数の最大値を計算するように、n個要素を有するベクトルｘを用意し、xtLx=Σ(xi-xj)2及び(vi,vj)∈E(G)を成立させるステップであって、前記n個要素は、前記データフローグラフＧのn個頂点に関連するn個変数であり、(vi,vj)∈E(G)は、すべての前記viがvjに隣接する時の操作対を表すステップと、固有データ転送速度の最大数量を推定するように、前記最大値を使用するステップと、を含む。
【０００９】
本発明の第二態様によれば、固有データ転送速度を定量する方法は、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されている場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにインエッジカット、アウトエッジカット及び非エッジカットの各代表数字を取得するように、n個要素を有するベクトルxを用意してMxの値を計算するステップであって、前記n個要素は、前記データフローグラフGのn個頂点に関連するn個変数であるステップと、余分のローカルストレージのサイズを推定するように、前記データムの再使用のために必要な前記生起依存行列Mを使用するステップと、を含む。
【００１０】
本発明の第三態様によれば、固有データ転送速度を定量する方法は、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されていない場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、固有データ転送速度の最大数量を推定するように、前記ラプラス行列Lを使用するステップと、を含む。
【００１１】
本発明の第四態様によれば、固有データ転送速度を定量する方法は、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されている場合、n個頂点とm個エッジを含むデータフローグラフＧ及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、最大データの再使用の状況下で固有データ転送速度の最小量を推定するように生起依存行列Mを使用するステップと、前記データムの再使用のために必要な余分のローカルストレージのサイズを推定するステップと、を含む。
【発明の効果】
【００１２】
本発明は、アルゴリズムを新たなプラットフォーム上に容易に移植し、各種データ粒度におけるアルゴリズムに固有データ転送速度を定量化するために、代数理論に基づく系統化方法を提供することを目的とする。本発明の抽出されたデータ転送速度は、アルゴリズムに対して固有であり、ハードウェアやソフトウェアに利用することも偏向なく、従って、本発明は、プラットフォームに依存しなく、ＡＡＣを一般的な応用に補助することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の好適な実施形態に係るデータフローグラフである。
【図２】動き推定の検索ウィンドウの概略図である。
【図３】水平探索ウィンドウのデータ再使用仕組みの概略図である。
【図４】水平方向のみに二つの隣接するブロックの重複検索ウィンドウを利用するデータ再使用仕組みの概略図である。
【図５】単一の大きなブロック（block）の検索ウィンドウの概略図である。
【図６】水平方向および垂直方向の探索ウィンドウの再使用仕組みのためのストレージサイズに対するデータ転送速度の曲線を示す。
【発明を実施するための最良の形態】
【００１４】
本発明は、添付の図面を参照しながら以下の説明を通して理解することができる。
【００１５】
複雑度メトリックは、アルゴリズムのデータフローの特性のみに依存しており、ハードウェアやソフトウェアの実行詳細を意識する必要がない。本発明に提示された固有複雑度の測定は、プラットフォームに依存しない。それ故、一般的なアーキテクチャや新たなプラットフォーム上に複雑なアルゴリズムをマッピングすることにおいて重要な役割を果たしている。
【００１６】
アルゴリズムは、自然言語、数式、フローチャート、擬似コード、高級プログラミング言語で表すことができる。信号処理応用において、アルゴリズムを表すために、数式は最も抽象、明確、かつコンパクトな方法の一つである。対応する信号フローグラフとデータフローモデルは、数学的表現に基づいて得ることができる。データフローモデルは、コンピュータと通信との間の相互関係を示すことができる。結果、データフローモデルによって生成されたグラフは、操作を示す頂点、データの送信元と宛先（即ちデータの流れ）を示す有向辺によって、各操作間のデータ依存性を明らかにする。
【００１７】
伝統的な高級プログラミングモデルと比較して、数学的表現から継承するデータフローモデルは、固有の複雑度情報が含まれており、実行詳細に対して透明なアーキテクチャの特性を明らかにすることができる。従来の設計方法論では、アルゴリズムのアーキテクチャと開発のそれぞれは、二つの孤立段階で実行される。これに対し、データフローモデルは、ＡＡＣのためのアルゴリズムとアーキテクチャの両方の同時最適化を可能にするように、二つの孤立設計段階の間のギャップを縫わなくて架橋することができる。
【００１８】
データフローモデルのデータ粒度は、ＡＡＣにおける重要なパラメータである。粗い及び細いデータ粒度のそれぞれは、より高いとより低いレベルの抽象性に対応している。又、操作の粒度は、データ粒度と一致している。したがって、操作は、応用シナリオに応じて、論理演算、算術演算、フィルタ、タスクまたはパケット処理のレベルであってもよい。リアルタイム・ビジュアル・コンピューティングアプリケーションのスループットの必要条件を満たすために、アルゴリズムのワークロードは、区間で行われる必要があり、タイミング精度をデータ粒度に依存させる。データ粒度は、タイミング情報に関連する複雑度メトリックであるため、アルゴリズムのデータ転送速度に著しく影響を及ぼす。
【００１９】
データフローの実行順序もアルゴリズムのデータ転送速度に影響を及ぼす。様々なデータ再使用程度で異なる実行順序結果を有するデータフローは、アルゴリズムのデータ転送速度に影響を与える要因である。アルゴリズムのデータフローを指定すると、プラットフォームに依存しないデータ転送速度での複雑度分析を結果的に行うことができる。本発明は、データ転送量及びデータ転送速度を定量化し、従って、データ転送速度は、細いデータ粒度においてデータフローグラフのエッジカットの概念に基づいており、ビジュアル・コンピューティング・アプリケーションにおけるピクセルである。粗い粒度におけるデータ転送速度は、細い粒度を粗い粒度にカプセル化することにより、容易に得ることができる。この方法は、データフローモデルをリビルドすることなく、複数のデータ粒度でのデータフローを系統的に分析するために適用することができる。リアルタイム・アプリケーションのスループットの必要条件を考えた後、対応する平均データ速度は、細いと粗い粒度で計算することができる。瞬時データ速度においては、メモリレイテンシと通信オーバヘッドに関わり、バス幅とクロックレートをさらに決定するために、ピーク帯域幅を推定することができる。
【００２０】
一、データ再使用がない時の最大データ転送速度
アルゴリズムの機能を実行するために、入力データは、出力データを生成するように、オペレータによって読み出され、消費される。データ再使用を考慮しない場合、一部のデータが複数回に転送される。データ転送の最大量は、データ再使用することなく、データ転送の理論上界量を測定する固有の複雑度メトリックである。
【００２１】
アルゴリズムのデータフローグラフに基づいて、入力と出力データ転送の最大量は、エッジカット（edge cut）問題としてモデル化することができる。Gは、データフローグラフとし、操作またはデータのn個頂点とデータ転送を表すm個エッジからなる。データ粒度の定義に基づいて、入力データを表す頂点をサブグラフに分割し、出力データを表す頂点を別のサブグラフにリセットすることにより、入力データ転送の最大量を容易に計算する。このような分割によるエッジカットのサイズは、入力されたデータ転送の最大量を明らかにする。同様にして、出力データ転送の最大量は、出力データを表す頂点をサブグラフに分割することで定量することができる。
【００２２】
本発明において、エッジカットのサイズの定量化は、スペクトルグラフ理論（spectral graph theory）におけるラプラス行列Lを介して行われ、コンパクトな形式でGの接続性を示すことができる。次式（１）で表される。
【数１】
0005905491.tif 000002
【００２３】
即ち、i=jが成立する時、L(i,j)=degree(vi)（viの自由度）が成立し、viがj番目の頂点vjに隣接する時、L(i,j)=-1が成立し、そうでないと、L(i,j)=0が成立する。
【００２４】
そこで、degree(vi)は、i番目の頂点viに接続されたエッジ数を示す。ラプラス行列Lにおいて、i番目の対角要素は、i番目の操作に接続された操作又はデータ数を示し、Lの非対角要素は、二つの操作が接続されているかどうかを示す。
【００２５】
データ転送の理論上の最大量は、ラプラス行列Lに基づいて推定することができる。xは、nの操作またはGのデータに関連付けられたn個変数のベクトルとし、xtLxの値は隣接の頂点間の平方差の和に等しく、次式（２）で表される。
【数２】
0005905491.tif 000003
【００２６】
即ち、(vi, vj)∈E(G)は、viとvjの互いに隣接する全ての操作対（vi、vj）を表す。
【００２７】
xの要素を指定して1又は-1のいずれかとすることで、xは、指標ベクトル（indicator vector）として用いることができ、データフローグラフを切断して二つのサブグラフとなるさまざまな方法を表す。この場合には、xtLxの値がエッジカットの4倍のサイズに等しい。理由は以下のとおりである。二つの隣接する頂点は、同じサブグラフにグループ化されることを示すように同じ値を指定される場合、その平方差はゼロに等しい。そうでないと、二つの隣接する頂点は、異なるサブグラフにグループ化され、関連するエッジが切断されることを示すように反対の値を指定される場合、その平方差は4である。従って、xtLxの値は、切断されたエッジ数の4倍に等しい。
【００２８】
図１は、本発明の好適な実施の形態に係るデータフローグラフである。図１において、エッジカット方法を説明するために、簡単な例が示されている。図１は、３タップ・フィルタのデータフローが６ピクセルを生産することを表す。そこで、円と矩形の頂点のそれぞれは、操作及び入力/出力データを表す。関連付けられた操作及び二つの出力データ毎にサブグラフにカプセル化する場合、データ粒度は2×1になる。このデータ粒度におけるデータ転送量を分析した後、四つのデータが読み出されている場合でも、最大入力値と出力値のそれぞれは、６、２に示されている。これは、一部のデータが複数回読み取られるためである。同様に、3×1と6×1のデータ粒度に対応する、データが読み出された最大量は、それぞれ９と１８である。頂点を各種データ粒度におけるサブグラフに系統的にカプセル化することにより、データ転送のマルチグレインの量は、結果的に分析することができる。この方法は、一般的にビジュアル・コンピューティング・アプリケーションに使用される二次元データ粒度をサポートするように効率的に拡張することができる。
【００２９】
外部のデータ転送量を減らすために、一部のローカルストレージ（local storage）を割り当てることできる。しかし、データ再使用は、最小ストレージに加えて、余分のストレージを必要とする。データ転送量以外の余分なストレージのサイズもデータ粒度に著しく依存する。これにより、転送されたデータとストレージのサイズ量とのトレードオフ（trade-off）の可能性を生じさせる。
【００３０】
二、データ再使用時のデータ転送速度
データ再使用時のデータ転送量は、二つの連続処理粒度が必要とする非重複入力データに応じて定量することができる。以前及び現在の処理粒度における重複入力データが再使用される。現在の処理粒度に十分な入力データを得るために、非重複部分だけが読み取られるべきである。これにより、非初期の処理粒度が必要とするデータ転送量は、入力データの非重複部分に基づいて推定することができる。
【００３１】
アルゴリズムのデータフローによれば、各処理データ粒度における非重複入力データは、代数的グラフ理論に基づいて系統的に識別して定量することができる。本発明に係るデータフローグラフの生起依存行列（incidence dependency matrix）Mを介して簡単に行うことができる。次式（３）で表される。
【数３】
0005905491.tif 000004
【００３２】
即ち、viがj番目のエッジの尾部である時、M(i,j)=1が成立し、viがj番目のエッジの頭部である時、M(i,j)=-1が成立し、そうでないと、M(i,j)=0が成立する。
【００３３】
フロー方向及びデータ量を含むデータフロー情報のセットは、Mにおいて表される。Mの水平方向と垂直方向のインデックスのそれぞれは、頂点とエッジに相当する。分割のエッジカットセットは、yで表されるMxの結果に応じて得ることができる。xは、ラプラシアン法におけるインデックスベクトルと類似しているn組ベクトルである。結果ベクトルyの要素は、2、0又は-2であり、対応するエッジがインエッジカット、非エッジカット又はアウトエッジカットのそれぞれを表示する。インエッジカット及びアウトエッジカットに基づいて、処理粒度の入出力データを示す送信元及び宛先の頂点のそれぞれを識別することができる。
【００３４】
処理粒度に必要な入力データは、生起依存行列Mに基づいて簡単に識別することができる。この方法は、二つの連続処理粒度の非重複入力データを推定するために適用することができる。このような測定は、最大データ再使用を考慮し、現在の処理粒度が必要とするデータ転送の最小量を明らかにする。データ再使用のための余分なローカルストレージのサイズは、連続処理粒度における入力データの和集合に応じて推定することができる。
【００３５】
この応用形式は、平均外部データ転送速度とローカルストレージのサイズとの間のトレードオフのために、例えば動き推定を取る。同様の結果は動き補償に見出すことができる。図２は、動き推定の検索ウィンドウの概略図である。図２において、動き推定の検索範囲は、水平方向における[−SH, SH)であり、垂直方向における[−SV, SV)である。又、ブロックサイズは、B×Bである。検索ウィンドウ内におけるデータが再使用されていない場合には、動きベクトル（MV）を発見するためのデータ転送の最大量は、NS×B×BにB×Bを加える結果に等しい。NSは、検索戦略に応じて、検索位置の数である。完全な検索のために必要なデータ転送の最大量は、4×SH×SV×B×BにB×Bである。探索ウィンドウ内におけるデータが再使用される場合には、ブロックのMVを計算するために必要なデータ転送量は、(2SH+B-1)×(2SV+B-1)にB×Bを加える結果に等しく、検索ウィンドウに利用されるローカルストレージのサイズは、(2SH+B-1)×(2SV+B-1)に等しいである。平均データ転送速度は、リアルタイムアプリケーションに利用される毎秒のブロック数に応じて算出することができる。
【００３６】
図３は、水平探索ウィンドウのデータ再利用仕組みの概略図である。図３に示すように、水平探索ウィンドウのデータ再使用仕組みは、ローカルストレージのサイズにわずかなオーバーヘッドで外部データ転送速度を低減することができる。 この仕組みでは、水平方向のみに二つの連続したブロックの探索ウィンドウの非重複領域が読み取られる必要がある。これにより、第２ブロックのデータ転送量は、Bx(2SV+B-1)にB×Bを加えるだけの結果である。また、ローカルストレージのサイズは、(2SH+2B-1)x(2SV+B-1)になる。換言すれば、ローカルストレージのサイズのオーバーヘッドは、非重複入力データの量に等しい。この例では、データ転送速度及び異なるレベルに関連付けられたデータ再使用のローカルストレージのサイズを示している。
【００３７】
データ再利用のレベルを効率的に増加させることにより、外部のデータ転送速度を減少させる一つの聡明な方法は、ビデオのローカル空間関連性から利益を得るように粗い粒度データを使用して処理することである。図４は、水平方向のみに二つの隣接するブロックの重複検索ウィンドウを利用するデータ再利用仕組みの概略図である。図５は、単一の大きなブロックの検索ウィンドウの概略図である。図４において、データ再使用仕組みは、水平方向のみに二つの隣接するブロックの重複検索ウィンドウを利用する。対照的に、図５におけるデータ再利用仕組みは、水平重複を使用するだけでなく、粗いデータ粒度における垂直重複も使用する。そこで、GH水平方向に隣接するブロックが大きなものにカプセル化されている。明らかに、粗いデータ粒度での検索ウィンドウのサイズは、(2SH+ GH×B-1)×(2SV+B-1)である。また、図４において、水平方向に隣接する二つの大きなブロックに必要な検索ウィンドウの和集合を示し、ここで、実行順序は、まず垂直走査を行う。
【００３８】
図４に示す検索ウィンドウの重複に従って、大きいブロックによって必要とされる検索ウィンドウの更新のための入力データの量は、B×（2SH+ GH×B-1）であり、画素あたりの平均入力データレートは、（2SH+ GH×B-1）/（GH ×B）である。全体の検索ウィンドウに対応するローカルストレージのサイズは、（2SH+ GH×B-1）×（2SV+2 B-1）である。明らかに、粗い粒度のデータを処理に使用することで、ローカルストレージサイズにおけるオーバーヘッドで平均データ転送速度を効果的に減少させるように、データ再利用のレベルを上げることができる。
【００３９】
表１は、様々なデータ再利用のレベルで平均データ転送速度とのローカルストレージサイズとの比較を作表する。表１は、各種データ粒度で平均データ転送速度とローカルストレージサイズとの間の影響力を簡潔に明らかにする。
【表１】
0005905491.tif 000005
【００４０】
図６は、水平方向および垂直方向の探索ウィンドウの再利用仕組みのためのストレージサイズに対するデータ転送速度の曲線を示す。そこで、水平検索範囲がSH=64であり、垂直検索範囲がSV=32であり、ブロックサイズがB=16である。データ粒度が増加すると、平均データ転送速度は、ほぼ逆数の順序に低下する。結果として、ローカルストレージのサイズにおけるわずかなオーバーヘッドを支払うことによって、外部メモリ帯域幅を著しく低減することができる。例えば、GH値が2に設定されている場合、ローカルストレージサイズは１１％増加し、平均データ転送速度は55％低減される。この曲線が示すことは、平均データ転送速度及びストレージサイズが埋め込みメモリサイズと外部平均帯域幅の観点からアーキテクチャラルスペースを容易に検索することができる。設計上の制約を考えた後、ピーク帯域幅を推定することができる。
【００４１】
実施例
１、固有データ転送速度を定量する方法であって、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されていない場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにエッジカットの総数の最大値を計算するように、n個要素を有するベクトルｘを用意し、xtLx=Σ(xi-xj)2及びvi,vj)∈E(G)を成立させるステップであって、前記n個要素は、前記データフローグラフＧのn個頂点に関連するn個変数であり、(vi,vj)∈E(G)は、すべての前記viがvjに隣接する時の操作対を表すステップと、固有データ転送速度の最大数量を推定するように、前記最大値を使用するステップと、を含む。
【００４２】
２、実施例１に記載の固有データ転送速度を定量する方法は、i=jが成立する時、L(i,j)=degree(vi)（viの自由度）が成立し、viがj番目の頂点vjに隣接する時、L(i,j)=-1が成立し、そうでないと、L(i,j)=0が成立する。
【００４３】
３．実施例１に記載の固有データ転送速度を定量する方法は、egree(vi)は、i番目の頂点viに接続されたエッジの総数を示し、Lのi番目の対角要素は、i番目の操作に接続された操作又はデータの総数を示し、Lの非対角要素は、二つの操作が接続されているかどうかを示す。
【００４４】
４、実施例１に記載の固有データ転送速度を定量する方法は、ベクトルxの各要素は、１又は-１である値を有する時、前記データフローグラフGは、二つのサブグラフに分けられ、二つの隣接する頂点が同じ値が与えられる時、二つの隣接する頂点が同じ前記サブグラフに属し、二つの隣接する頂点が異なる値が与えられる時、二つの隣接する頂点が異なる前記サブグラフに属する。
【００４５】
５、実施例４に記載の固有データ転送速度を定量する方法は、前記xtLx=4*エッジカットの総数である。
【００４６】
６、固有データ転送速度を定量する方法であって、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されている場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにインエッジカット、アウトエッジカット及び非エッジカットの各代表数字を取得するように、n個要素を有するベクトルxを用意してMxの値を計算するステップであって、前記n個要素は、前記データフローグラフGのn個頂点に関連するn個変数であるステップと、余分のローカルストレージのサイズを推定するように、前記データムの再使用のために必要な前記生起依存行列Mを使用するステップと、を含む。
【００４７】
７、実施例６に記載の固有データ転送速度を定量する方法は、viがj番目のエッジの尾部である時、M(i,j)=1が成立し、viがj番目のエッジの頭部である時、M(i,j)=-1が成立し、そうでないと、M(i,j)=0が成立する。
【００４８】
８、実施例７に記載の固有データ転送速度を定量する方法は、前記Mx=y、yはベクトルであり、yの要素値が２を有する場合、yの要素は、対応するエッジがインエッジカットであることを示し、yの要素値が０を有する場合、yの要素は、対応するエッジ要素が非エッジカットであることを示し、yの要素が-２の値を有する場合、対応するエッジがアウトエッジカットであることを示す。
【００４９】
９、固有データ転送速度を定量する方法であって、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されていない場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、固有データ転送速度の最大数量を推定するように、前記ラプラス行列Lを使用するステップと、を含む。
【００５０】
１０、固有データ転送速度を定量する方法であって、データムが使用されるか否かを検出するステップと、検出したデータムが再使用されている場合、n個頂点とm個エッジを含むデータフローグラフＧ及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、最大データの再使用の状況下で固有データ転送速度の最小量を推定するように生起依存行列Mを使用するステップと、前記データムの再使用のために必要な余分のローカルストレージのサイズを推定するステップと、を含む。
【００５１】
上記の説明によれば、本発明は、アルゴリズムを新たなプラットフォーム上に容易に移植し、各種データ粒度におけるアルゴリズムに固有データ転送速度を定量化するために、代数理論に基づく系統化方法を提供することを目的とする。本発明の抽出されたデータ転送速度は、アルゴリズムに対して固有であり、ハードウェアやソフトウェアに利用することも偏向なく、従って、本発明は、新規性と進歩性を持つために、プラットフォームに依存しなく、ＡＡＣを一般的な応用に補助することができる。
【００５２】
以上の説明によると、当業者であれば本発明の技術思想を逸脱しない範囲で、多様な変更及び修正が可能であることが分かる。従って、本発明の技術的な範囲は、明細書の詳細な説明に記載された内容に限らず、特許請求の範囲によって定めなければならない。  
以下に、本願出願時の特許請求の範囲に記載された発明を付記する。
［１］固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されていない場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにエッジカットの総数の最大値を計算するように、n個要素を有するベクトルｘを用意し、xtLx=Σ(xi-xj)2及び(vi,vj)∈E(G)を成立させるステップであって、前記n個要素は、前記データフローグラフＧのn個頂点に関連するn個変数であり、(vi,vj)∈E(G)は、すべての前記viがvjに隣接する時の操作対を表すステップと、
固有データ転送速度の最大数量を推定するように、前記最大値を使用するステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
［２］i=jが成立する時、L(i,j)=degree(vi)（viの自由度）が成立し、viがj番目の頂点vjに隣接する時、L(i,j)=-1が成立し、そうでないと、L(i,j)=0が成立することを特徴とする前記［１］に記載の固有データ転送速度を定量する方法。
［３］degree(vi)は、i番目の頂点viに接続されたエッジの総数を示し、Lのi番目の対角要素は、i番目の操作に接続された操作又はデータの総数を示し、Lの非対角要素は、二つの操作が接続されているかどうかを示すことを特徴とする前記［２］に記載の固有データ転送速度を定量する方法。
［４］ベクトルxの各要素は、１又は-１である値を有する時、前記データフローグラフGは、二つのサブグラフに分けられ、二つの隣接する頂点が同じ値が与えられる時、二つの隣接する頂点が同じ前記サブグラフに属し、二つの隣接する頂点が異なる値が与えられる時、二つの隣接する頂点が異なる前記サブグラフに属することを特徴とする前記［１］に記載の固有データ転送速度を定量する方法。
［５］前記xtLx=4*エッジカットの総数であることを特徴とする前記［４］に記載の固有データ転送速度を定量する方法。
［６］固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されている場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
n個頂点を、少なくとも二つの隣接する頂点を含むサブグラフに分けると、m個エッジのうちにインエッジカット、アウトエッジカット及び非エッジカットの各代表数字を取得するように、n個要素を有するベクトルxを用意してMxの値を計算するステップであって、前記n個要素は、前記データフローグラフGのn個頂点に関連するn個変数であるステップと、
余分のローカルストレージのサイズを推定するように、前記データムの再使用のために必要な前記生起依存行列Mを使用するステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
［７］viがj番目のエッジの尾部である時、M(i,j)=1が成立し、viがj番目のエッジの頭部である時、M(i,j)=-1が成立し、そうでないと、M(i,j)=0が成立することを特徴とする前記［６］に記載の固有データ転送速度を定量する方法。
［８］前記Mx=y、yはベクトルであり、yの要素値が２を有する場合、yの要素は、対応するエッジがインエッジカットであることを示し、yの要素値が０を有する場合、yの要素は、対応するエッジ要素が非エッジカットであることを示し、yの要素が-２の値を有する場合、対応するエッジがアウトエッジカットであることを示すことを特徴とする前記［７］に記載の固有データ転送速度を定量する方法。
［９］固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されていない場合、n個頂点とm個エッジを含むデータフローグラフG及びixj要素L(i,j)を有するラプラス行列Lを用意するステップであって、それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
固有データ転送速度の最大数量を推定するように、前記ラプラス行列Lを使用するステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
［１０］固有データ転送速度を定量する方法であって、
データムが使用されるか否かを検出するステップと、
検出したデータムが再使用されている場合、n個頂点とm個エッジを含むデータフローグラフＧ及びixj要素M(i,j)を有する生起依存行列Mを用意するステップであって、iはi番目の頂点を表し、jはj番目のエッジを表し、前記それぞれの前記頂点は、操作又はデータムを表し、それぞれの前記エッジは、データ転送を表し、viがi番目の頂点であるステップと、
最大データの再使用の状況下で固有データ転送速度の最小量を推定するように生起依存行列Mを使用するステップと、
前記データムの再使用のために必要な余分のローカルストレージのサイズを推定するステップと、を含むことを特徴とする固有データ転送速度を定量する方法。
【図１】
0005905491.tif 000006
【図２】
0005905491.tif 000007
【図３】
0005905491.tif 000008
【図４】
0005905491.tif 000009
【図５】
0005905491.tif 000010
【図６】
0005905491.tif 000011