(57)【特許請求の範囲】
【請求項１】
アルゴリズムの本質的な並行処理を定量化及び分析する方法であって、前記方法はコンピューターによって実装されるように構成され、前記方法は、
ａ）  前記コンピューターを、複数の演算セットによる前記アルゴリズムを表現するよう構成させるステップ、
ｂ）  前記コンピューターを、前記複数の演算セットに従いラプラス行列を取得するよう構成させるステップ、
ｃ）  前記コンピューターを、前記ラプラス行列の固有値及び固有ベクトルを計算するよう構成させるステップ、及び
ｄ）  前記コンピューターを、前記ラプラス行列の前記固有値及び前記固有ベクトルに従って、アルゴリズムの本質的な並行処理に関する情報のセットを取得させるよう構成させるステップ、を含み、
ステップｄ）は、
ｄ１）前記コンピューターを、前記ラプラス行列の前記固有値及び前記固有ベクトルに従って、前記アルゴリズムの厳密な並列処理に関する情報のセットを取得するよう構成させるサブステップ、並びに
ｄ２）前記コンピューターを、前記アルゴリズムの複数の依存性深さの少なくとも１つ及び前記厳密な並列処理に関する情報のセットに従って、前記アルゴリズムのマルチグレイン並列処理に関する情報のセットを取得するよう構成させるサブステップ、
を含むことを特徴とする前記方法。
【請求項２】
ステップｂ）は、
ｂ１）  前記コンピューターを、演算セットに従い、前記アルゴリズムに関するデータフロー情報を取得するよう構成させるサブステップ、
ｂ２）  前記コンピューターを、前記データフロー情報に従い、前記アルゴリズムにおける演算を示す複数の頂点から成るデータフロー・グラフを取得するよう構成させ、前記頂点のうち対応する２つの頂点の相互接続を示し前記アルゴリズムにおけるデータのソースとデスティネーションを示す方向性のある複数の辺を取得するよう構成させるサブステップ、及び
ｂ３）  前記コンピューターを、前記データフロー・グラフに従って、前記ラプラス行列を取得するよう構成させるサブステップ、
を含む、請求項１に記載の方法。
【請求項３】
前記厳密な並列処理に関する情報のセットは、前記アルゴリズムの前記演算セットの独立なものの数を表す厳密な並列処理の程度と、前記演算セットに対応する厳密な並列処理の構成のセット、をそれぞれ含む、請求項１に記載の方法。
【請求項４】
サブステップｄ２）において、前記コンピューターは、前記依存性深さ及び前記厳密な並列処理に関する情報のセットに従って前記アルゴリズムのマルチグレイン並列処理に関する複数の情報のセットをそれぞれ取得するよう構成されることを特徴とする請求項１に記載の方法。
【請求項５】
前記アルゴリズムのマルチグレイン並列処理に関する複数の情報のセットのそれぞれは、マルチグレイン並列処理の程度、及び、マルチグレイン並列処理の構成のセットを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記マルチグレイン並列処理に関する情報のセットは、前記依存性深さの最小のもの及び前記厳密な並列処理に関する情報のセットに従って取得される前記アルゴリズムの広義の並列処理に関する情報のセットを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記広義の並列処理に関する情報のセットは、前記アルゴリズムの前記演算セットの独立なものに埋め込まれた全ての可能な並列処理を特徴付ける広義の並列処理の程度、及び、広義の並列処理の構成のセットを含むことを特徴とする請求項６に記載の方法。
【請求項８】
サブステップｄ１）において、前記厳密な並列処理の程度は、スペクトルグラフ理論に基づき、０に等しい前記固有値の数に等しいことを特徴とする請求項１に記載の方法。
【請求項９】
前記マルチグレイン並列処理に関する情報は、マルチグレイン並列処理の程度と、マルチグレイン並列処理の構成のセットを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
請求項１に記載のアルゴリズムの本質的な並行処理を定量化及び分析する方法を実行時にコンピューターに行わせるプログラム命令を記録した機械読み取り可能な記憶媒体を有するコンピューター。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アルゴリズムの並行処理を定量化及び分析する方法に関し、より詳しくは、アルゴリズムの本質的な並行処理を定量化及び分析する方法に関する。
【背景技術】
【０００２】
Ｇ．Ｍ．アムダールは、アルゴリズムの逐次実行部分の比率に従ったアルゴリズムの並列処理化の方法を紹介した。("大規模演算性能を達成するシングル・プロセッサによるアプローチの有効性、" ＡＦＩＰＳ会議の会議録、４８３から４８５ページ、１９６７）。
【０００３】
アムダールの方法の欠点は、この方法によって得られたアルゴリズムの並行処理の程度は、この方法を実行するターゲットとなるプラットフォームに依存し、アルゴリズム自体には必ずしも依存しないことである。従って、アムダールの方法を使って得られた並行処理の程度は、アルゴリズムに対して非本質的なであり、ターゲットとなるプラットフォームによるバイアスを受ける。
【０００４】
Ａ．プリホジーらは、アルゴリズムのクリティカル・パス長と複雑性の比に基づくアルゴリズムの並列処理化可能性を評価する方法を提案した（"効率的なマルチメディア実装のための並列処理化可能性の評価：アルゴリズム・クリティカル・パスの動的評価、" 動画技術のための回路及びシステムについてのＩＥＥＥ論文誌、５９３から６０８ページ、１５巻、Ｎｏ．５、２００５年５月）。複雑性とは、アルゴリズムの演算の合計回数であり、クリティカル・パスとは、演算データ依存性により逐次実行しなければならない演算の最大回数である。この方法は、アルゴリズムに埋め込まれた並行処理の平均の程度を決めることができるかもしれないが、アルゴリズムに埋め込まれた様々なマルチグレイン並行処理を網羅的に決めるには不十分である。
【発明の概要】
【課題を解決するための手段】
【０００５】
従って、本発明の目的は、ターゲットとなるハードウェア及び／又はソフトウェアのプラットフォームによってバイアスを受けない、アルゴリズムの本質的な並行処理を定量化及び分析する方法を提供することにある。
【０００６】
従って、本発明によるアルゴリズムの本質的な並行処理を定量化及び分析する方法は、コンピューターによって実装されるように構成され、以下のステップを有する：
ａ）  コンピューターを、複数の演算セットによるアルゴリズムを表現するよう構成させる、
ｂ）  コンピューターを、複数の演算セットに従いラプラス行列を取得するよう構成させる、
ｃ）  コンピューターを、ラプラス行列の固有値及び固有ベクトルを計算するよう構成させる、
ｄ）  コンピューターを、ラプラス行列の固有値及び固有ベクトルに従って、アルゴリズムの本質的な並行処理に関する情報のセットを取得させるよう構成させる。
【図面の簡単な説明】
【０００７】
本発明の他の特徴や利点は、添付図面を参照しながら、下記の好適な実施例の詳細な記載において明らかになる。添付図面は、下記の通りである。
【０００８】
【図１】本発明のアルゴリズムの本質的な並行処理を定量化及び分析する方法の好適な実施例を示すフローチャートである。
【図２】アルゴリズムの例に関するデータフロー情報を示す概略図である。
【図３】データフロー・グラフのセットの例を示す概略図である。
【図４】４×４  離散コサイン変換アルゴリズムの演算セットを示す概略図である。
【図５】６に等しい依存性深さに対応する本質的並列処理の構成の例を示す概略図である。
【図６】５に等しい依存性深さに対応する本質的並列処理の構成の例を示す概略図である。
【図７】３に等しい依存性深さに対応する本質的並列処理の構成の例を示す概略図である。
【発明を実施するための形態】
【０００９】
図１を参照し、本発明によるアルゴリズムの本質的な並行処理を評価する方法の好適な実施例は、コンピューターによって実装されるように構成され、以下のステップを有する。
【００１０】
本質的な並列処理の程度は、ソフトウェア及びハードウェアの設計及び構成を考慮せず、アルゴリズム自身の並列処理の程度を示すものである。つまり、本発明の方法は、アルゴリズムを分析する時、ソフトウェア及びハードウェアによって制限されない。
【００１１】
ステップ１１において、コンピューターは、複数の演算セットによるアルゴリズムを表現するよう構成される。それぞれの演算セットは、等式、プログラムコード、フローチャート、その他、アルゴリズムを表すどのような形態であってもよい。下記の例においては、アルゴリズムは、下記のようにあらわされる、３つの演算セットＯ１、Ｏ２、及びＯ３を含む。
Ｏ１＝Ａ1＋Ｂ1＋Ｃ1＋Ｄ1、
Ｏ２＝Ａ2＋Ｂ2＋Ｃ2、及び
Ｏ３＝Ａ3＋Ｂ3＋Ｃ3
【００１２】
ステップ１２は、演算セットに従ったラプラス行列Ｌdを取得するようコンピューターを構成することであり、下記のサブステップを含む。
【００１３】
サブステップ１２１において、演算セットに従い、コンピューターは、アルゴリズムに関するデータフロー情報を取得するよう構成される。図２に示されるように、この例の演算セットに対応するデータフロー情報は、下記のように表現されてもよい。
データ１＝Ａ1＋Ｂ1
データ２＝Ａ2＋Ｂ2
データ３＝Ａ3＋Ｂ3
データ４＝データ１＋データ７
データ５＝データ２＋Ｃ2
データ６＝データ３＋Ｃ3
データ７＝Ｃ1＋Ｄ1
【００１４】
サブステップ１２２において、コンピューターは、データフロー情報に従って、データフロー・グラフを取得するよう構成される。データフロー・グラフは、アルゴリズムにおいて演算を表す複数の頂点及び、頂点のうち対応する２つの頂点の相互接続を示しアルゴリズムにおけるデータのソースとデスティネーションを示す方向性のある複数の辺によって構成される。図２に示されるデータフロー情報については、演算記号Ｖ1からＶ7（つまり、頂点）が加算記号の代わりに使われ、矢印（つまり、方向性のある辺）が、データのソースとデスティネーションを示し、これにより、図３のデータフロー・グラフが取得される。特に、演算記号Ｖ1が加算演算Ａ1＋Ｂ1を示し、演算記号Ｖ2が加算演算Ａ2＋Ｂ2を示し、演算記号Ｖ3が加算演算Ａ3＋Ｂ3を示し、演算記号Ｖ4が加算演算データ１＋データ７を示し、演算記号Ｖ5が加算演算データ２＋Ｃ2を示し、演算記号Ｖ6が加算演算データ３＋Ｃ3を示し、そして演算記号Ｖ7が加算演算Ｄ1＋Ｃ1を示す。
【００１５】
図３に示されるデータフロー・グラフから、演算記号Ｖ4が演算記号Ｖ1及びＶ7に依存することが分かる。同様に、演算記号Ｖ5が演算記号Ｖ2に依存し、演算記号Ｖ6が演算記号Ｖ3に依存し、演算記Ｖ4、Ｖ5及びＶ6は、互いに依存しない。
【００１６】
サブステップ１２３において、コンピューターは、データフロー・グラフに従ったラプラス行列Ｌdを取得するように構成される。ラプラス行列Ｌdにおいて、ｉ番目の対角の要素は、演算記号Ｖiに接続される演算記号の数を示し、対角から外れた要素は、２つの演算記号が接続されているかどうかを示す。 従って、ラプラス行列Ｌdは、明確にデータフロー・グラフを、線形代数形式によって示すことができる。図３に示されるデータフロー・グラフのセットは、下記のように示されてもよい。
0005925202.tif 000002
【００１７】
ラプラス行列Ｌdは、演算記号Ｖ1からＶ7の間の接続性を示し、第１列から第７列は、演算記号Ｖ1からＶ7をそれぞれ示す。例えば、最初の列において、演算記号Ｖ1は、演算記号Ｖ4に接続され、従って、行列要素(１，４)は−１である。
【００１８】
ステップ１３において、コンピューターは、ラプラス行列Ｌdの固有値λ及び固有ベクトルＸdを計算するように構成される。上記例において取得されたラプラス行列Ｌdについて、固有値λ及び固有ベクトルＸdは、下記の通りである。
0005925202.tif 000003
【００１９】
ステップ１４において、コンピューターは、ラプラス行列Ｌdの固有値λ及び固有ベクトルＸdに従って、アルゴリズムの本質的な並列処理に関する情報のセットを取得するように構成される。上記本質的な並列処理に関する情報のセットは、演算セットのうち、互いに独立しており並列処理に実行可能な独立な演算セットを認識するように厳密に定義される。厳密な並列処理に関する情報のセットは、アルゴリズムの上記演算セットのうち、独立な演算セットの数を示す厳密な並列処理の程度、及び、演算セットに対応する厳密な並列処理の構成のセットをそれぞれ含む。Ｆ．Ｒ．Ｋ．チャン（数学のリジョナル・カンファレンス・シリーズ、Ｎｏ．９２、１９９７）によって紹介されたスペクトルグラフ理論に基づき、グラフの接続された構成の数は、０に等しいラプラス行列の固有値の数に等しい。アルゴリズムに埋め込まれた厳密な並列処理の程度は、従って、０に等しい固有値λの数に等しい。その上、スペクトルグラフ理論に基づき、厳密な並列処理の構成は、０に等しい固有値λに関連付けられる固有ベクトルＸdに従って、特定されてもよい。
【００２０】
上記例から、０に等しいラプラス固有値は３つ存在するので、データフロー・グラフのセットは、３つの独立な演算セットから構成されることが分かる。従って、例示されるアルゴリズムに埋め込まれる厳密な並列処理の程度は、３に等しい。次に、固有ベクトルＸdの第１、２、及び３の固有ベクトルは、０に等しい固有値λに関連付けられる。固有ベクトルＸdの第１の固有ベクトルを観察することにより、演算記号Ｖ1、Ｖ4及びＶ7に対応する値が０ではないということが明らかであり、つまり、演算記号Ｖ1、Ｖ4及びＶ7は依存し、データフロー・グラフの接続されたもの（Ｖ1−Ｖ4−Ｖ7）を形成する。同様に、０に等しい固有値λに関連付けられた固有ベクトルＸdの第２及び３の固有ベクトルを形成し、演算記号Ｖ2、Ｖ5及び演算記号Ｖ3、Ｖ6 は依存し、データフロー・グラフの残りの２つの接続されたもの（Ｖ2−Ｖ5及びＶ3−Ｖ6）をそれぞれ形成すると理解される。従って、コンピューターは、３に等しい厳密な並列処理の程度、及び、（図３に示されるような）グラフ、テーブル、等式、又はプログラムコードの形態で表現されうる厳密な並列処理の構成を取得するように構成される。
【００２１】
ステップ１５において、コンピューターは、アルゴリズムの複数の依存性深さの少なくとも１つ及び厳密な並列処理に関する情報のセットに従ったアルゴリズムのマルチグレイン並列処理に関する情報の複数のセットを取得するように構成される。マルチグレイン並列処理に関する情報のセットは、独立な演算セットに埋め込まれた全ての可能性のある並列処理を特徴付けるアルゴリズムの広義の並列処理に関する情報のセット含む。
【００２２】
尚、アルゴリズムの依存性深さは、アルゴリズムの処理において重要な、関連付けられた逐次ステップを表し、つまり、アルゴリズムの可能な並列処理に対して相互補完的である。従って、 アルゴリズムの異なる本質的な並列処理に関する情報は、異なる依存性深さに基づいて取得されてもよい。特に、厳密な並列処理に関する情報は、アルゴリズムの依存性深さのうち最大のものに対応するアルゴリズムの本質的な並列処理に関する情報であり、広義の並列処理に関する情報は、依存性深さのうち最小のものに対応するアルゴリズムの本質的な並列処理に関する情報である。
【００２３】
例えば、上記アルゴリズムは、厳密な並列処理の２つの異なる構成、つまり、Ｖ1−Ｖ4−Ｖ7及びＶ2−Ｖ5を含む（Ｖ3−Ｖ6は、Ｖ2−Ｖ5に似ており、同じ構成と考えられる）。厳密な並列処理Ｖ1−Ｖ4−Ｖ7の構成については、演算記号Ｖ1及びＶ7が互いに独立である、つまり、演算記号Ｖ1及びＶ7が並列に処理されることができることが分かる。従って、 アルゴリズムの広義の並列処理に関する情報のセットは、４に等しい広義の並列処理の程度を含み、広義の並列処理の構成は、厳密な並列処理の構成に類似する。
【００２４】
この実施例の方法によれば、上記アルゴリズムの広義の並列処理の程度は、４に等しい。 アルゴリズムを実装するのに、処理要素は７回の処理サイクルを要する。なぜならば、アルゴリズムは７個の演算記号Ｖ1−Ｖ7を含むからである。３に等しい厳密な並列処理の程度によれば、３個の処理要素を使ってアルゴリズムを実装するには、３回の処理サイクルを使う。４に等しい広義の並列処理の程度によれば、４個の処理要素を使ってアルゴリズムを実装するには、２回の処理サイクルを使う。更に、より多くの処理要素が使われるものの、少なくとも２回の処理サイクルがアルゴリズムを実装するのに必要であることが分かる。従って、アルゴリズムを実装するのに使われる処理要素の最適な数は、この実施例の方法に従って取得されうる。
【００２５】
４×４離散コサイン変換（ＤＣＴ）を例とすると、ＤＣＴアルゴリズムの演算セットは、図４に示されるデータフロー・グラフによって表現される。４×４ＤＣＴは当業者によってよく知られているので、その更に詳細については、簡潔さのためにここでは省略される。図４より、４×４ＤＣＴアルゴリズムの依存性深さの最大のものは、６に等しいことが分かる。依存性深さの最大のもの（つまり、６）については、このアルゴリズムの厳密な並列処理の構成は、図５に示されるように取得されてもよく、このアルゴリズムの厳密な並列処理の程度は、この実施例の方法によれば、４に等しい。５に等しい依存性深さのうち１つをもって４×４ＤＣＴアルゴリズムの本質的な並列処理を分析する時、このアルゴリズムの本質的な並列処理の構成は、図６に示されるように取得されてもよく、本質的な並列処理の程度は８に等しい。更に、３に等しい依存性深さのうち１つをもって４×４ＤＣＴアルゴリズムの本質的な並列処理を分析する時、このアルゴリズムの本質的な並列処理の構成は、図７に示されるように取得されてもよく、本質的な並列処理の程度は１６に等しい。
【００２６】
つまり、この発明による方法は、アルゴリズムの本質的な並列処理を評価するのに使われてもよい。
【００２７】
本発明は、最も実用的で好適な実施例と考えられるものに関連付けられて記載されたものの、この発明は、記載された実施例に限定されることなく、最も広い解釈の精神及び範囲に含まれる様々な配設を網羅するように意図され、そのような全ての変更や均等な配設を含む、と考えられなければならない。
【図１】
0005925202.tif 000004
【図２】
0005925202.tif 000005
【図３】
0005925202.tif 000006
【図４】
0005925202.tif 000007
【図５】
0005925202.tif 000008
【図６】
0005925202.tif 000009
【図７】
0005925202.tif 000010