[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP5925202B2 - Method for quantifying and analyzing parallel processing of algorithms - Google Patents

Method for quantifying and analyzing parallel processing of algorithms Download PDF

Info

Publication number
JP5925202B2
JP5925202B2 JP2013518789A JP2013518789A JP5925202B2 JP 5925202 B2 JP5925202 B2 JP 5925202B2 JP 2013518789 A JP2013518789 A JP 2013518789A JP 2013518789 A JP2013518789 A JP 2013518789A JP 5925202 B2 JP5925202 B2 JP 5925202B2
Authority
JP
Japan
Prior art keywords
parallel processing
algorithm
computer
information regarding
strict
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2013518789A
Other languages
Japanese (ja)
Other versions
JP2013530477A (en
Inventor
グウォ ジウン クリス リー
グウォ ジウン クリス リー
ヘ ユァン リン
ヘ ユァン リン
Original Assignee
ナショナル・チェン・クン・ユニヴァーシティ
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from TW099122162A external-priority patent/TWI501168B/en
Priority claimed from US12/832,557 external-priority patent/US20120011186A1/en
Application filed by ナショナル・チェン・クン・ユニヴァーシティ filed Critical ナショナル・チェン・クン・ユニヴァーシティ
Publication of JP2013530477A publication Critical patent/JP2013530477A/en
Application granted granted Critical
Publication of JP5925202B2 publication Critical patent/JP5925202B2/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/44—Arrangements for executing specific programs
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/147—Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/456—Parallelism detection
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Discrete Mathematics (AREA)
  • Complex Calculations (AREA)
  • Stored Programmes (AREA)

Description

本発明は、アルゴリズムの並行処理を定量化及び分析する方法に関し、より詳しくは、アルゴリズムの本質的な並行処理を定量化及び分析する方法に関する。   The present invention relates to a method for quantifying and analyzing parallel processing of an algorithm, and more particularly to a method for quantifying and analyzing intrinsic parallel processing of an algorithm.

Ｇ．Ｍ．アムダールは、アルゴリズムの逐次実行部分の比率に従ったアルゴリズムの並列処理化の方法を紹介した。("大規模演算性能を達成するシングル・プロセッサによるアプローチの有効性、" ＡＦＩＰＳ会議の会議録、４８３から４８５ページ、１９６７）。   G. M.M. Amdahl introduced a method for parallel processing of algorithms according to the ratio of the sequential execution part of the algorithm. ("Effectiveness of a single processor approach to achieve large-scale computing performance," AFIPS conference proceedings, pages 483 to 485, 1967).

アムダールの方法の欠点は、この方法によって得られたアルゴリズムの並行処理の程度は、この方法を実行するターゲットとなるプラットフォームに依存し、アルゴリズム自体には必ずしも依存しないことである。従って、アムダールの方法を使って得られた並行処理の程度は、アルゴリズムに対して非本質的なであり、ターゲットとなるプラットフォームによるバイアスを受ける。   The disadvantage of Amdahl's method is that the degree of parallel processing of the algorithm obtained by this method depends on the target platform on which the method is executed and not necessarily on the algorithm itself. Thus, the degree of parallelism obtained using Amdahl's method is not intrinsic to the algorithm and is biased by the target platform.

Ａ．プリホジーらは、アルゴリズムのクリティカル・パス長と複雑性の比に基づくアルゴリズムの並列処理化可能性を評価する方法を提案した（"効率的なマルチメディア実装のための並列処理化可能性の評価：アルゴリズム・クリティカル・パスの動的評価、" 動画技術のための回路及びシステムについてのＩＥＥＥ論文誌、５９３から６０８ページ、１５巻、Ｎｏ．５、２００５年５月）。複雑性とは、アルゴリズムの演算の合計回数であり、クリティカル・パスとは、演算データ依存性により逐次実行しなければならない演算の最大回数である。この方法は、アルゴリズムに埋め込まれた並行処理の平均の程度を決めることができるかもしれないが、アルゴリズムに埋め込まれた様々なマルチグレイン並行処理を網羅的に決めるには不十分である。   A. Prehozy et al. Proposed a method for evaluating parallelism of an algorithm based on the ratio of the critical path length to the complexity of the algorithm ("Evaluation of parallelism for efficient multimedia implementation: Dynamic evaluation of algorithm critical path, "IEEE paper on circuits and systems for video technology, pages 593 to 608, volume 15, No. 5, May 2005). Complexity is the total number of operations of the algorithm, and critical path is the maximum number of operations that must be executed sequentially due to dependency on operation data. This method may be able to determine the average degree of parallel processing embedded in the algorithm, but is not sufficient to exhaustively determine the various multigrain parallel processing embedded in the algorithm.

従って、本発明の目的は、ターゲットとなるハードウェア及び／又はソフトウェアのプラットフォームによってバイアスを受けない、アルゴリズムの本質的な並行処理を定量化及び分析する方法を提供することにある。   Accordingly, it is an object of the present invention to provide a method for quantifying and analyzing the intrinsic parallelism of an algorithm that is not biased by the target hardware and / or software platform.

従って、本発明によるアルゴリズムの本質的な並行処理を定量化及び分析する方法は、コンピューターによって実装されるように構成され、以下のステップを有する：
ａ） コンピューターを、複数の演算セットによるアルゴリズムを表現するよう構成させる、
ｂ） コンピューターを、複数の演算セットに従いラプラス行列を取得するよう構成させる、
ｃ） コンピューターを、ラプラス行列の固有値及び固有ベクトルを計算するよう構成させる、
ｄ） コンピューターを、ラプラス行列の固有値及び固有ベクトルに従って、アルゴリズムの本質的な並行処理に関する情報のセットを取得させるよう構成させる。 Thus, the method for quantifying and analyzing the intrinsic parallelism of the algorithm according to the invention is configured to be implemented by a computer and comprises the following steps:
a) configure the computer to represent algorithms with multiple sets of operations,
b) configuring the computer to obtain a Laplace matrix according to multiple sets of operations;
c) configuring the computer to compute eigenvalues and eigenvectors of the Laplace matrix;
d) Configure the computer to obtain a set of information about the intrinsic parallelism of the algorithm according to the eigenvalues and eigenvectors of the Laplace matrix.

本発明の他の特徴や利点は、添付図面を参照しながら、下記の好適な実施例の詳細な記載において明らかになる。添付図面は、下記の通りである。   Other features and advantages of the present invention will become apparent in the following detailed description of the preferred embodiments with reference to the accompanying drawings. The attached drawings are as follows.

本発明のアルゴリズムの本質的な並行処理を定量化及び分析する方法の好適な実施例を示すフローチャートである。Fig. 6 is a flow chart illustrating a preferred embodiment of a method for quantifying and analyzing the intrinsic parallelism of the algorithm of the present invention. アルゴリズムの例に関するデータフロー情報を示す概略図である。FIG. 6 is a schematic diagram illustrating data flow information regarding an example algorithm. データフロー・グラフのセットの例を示す概略図である。It is the schematic which shows the example of the set of a dataflow graph. ４×４ 離散コサイン変換アルゴリズムの演算セットを示す概略図である。It is the schematic which shows the calculation set of a 4x4 discrete cosine transform algorithm. ６に等しい依存性深さに対応する本質的並列処理の構成の例を示す概略図である。6 is a schematic diagram illustrating an example of a configuration of intrinsic parallel processing corresponding to a dependency depth equal to 6. FIG. ５に等しい依存性深さに対応する本質的並列処理の構成の例を示す概略図である。6 is a schematic diagram illustrating an example of a configuration of intrinsic parallel processing corresponding to a dependency depth equal to 5. FIG. ３に等しい依存性深さに対応する本質的並列処理の構成の例を示す概略図である。3 is a schematic diagram illustrating an example of a configuration of intrinsic parallel processing corresponding to a dependency depth equal to 3. FIG.

図１を参照し、本発明によるアルゴリズムの本質的な並行処理を評価する方法の好適な実施例は、コンピューターによって実装されるように構成され、以下のステップを有する。   Referring to FIG. 1, a preferred embodiment of a method for evaluating the intrinsic parallelism of an algorithm according to the present invention is configured to be implemented by a computer and has the following steps.

本質的な並列処理の程度は、ソフトウェア及びハードウェアの設計及び構成を考慮せず、アルゴリズム自身の並列処理の程度を示すものである。つまり、本発明の方法は、アルゴリズムを分析する時、ソフトウェア及びハードウェアによって制限されない。   The essential degree of parallel processing indicates the degree of parallel processing of the algorithm itself without considering the design and configuration of software and hardware. That is, the method of the present invention is not limited by software and hardware when analyzing the algorithm.

ステップ１１において、コンピューターは、複数の演算セットによるアルゴリズムを表現するよう構成される。それぞれの演算セットは、等式、プログラムコード、フローチャート、その他、アルゴリズムを表すどのような形態であってもよい。下記の例においては、アルゴリズムは、下記のようにあらわされる、３つの演算セットＯ１、Ｏ２、及びＯ３を含む。
Ｏ１＝Ａ1＋Ｂ1＋Ｃ1＋Ｄ1、
Ｏ２＝Ａ2＋Ｂ2＋Ｃ2、及び
Ｏ３＝Ａ3＋Ｂ3＋Ｃ3 In step 11, the computer is configured to represent an algorithm with a plurality of operation sets. Each set of operations may take any form that represents an equation, program code, flowchart, or other algorithm. In the example below, the algorithm includes three operation sets O1, O2, and O3, represented as follows:
O1 = A 1 + B 1 + C 1 + D 1 ,
O2 = A 2 + B 2 + C 2 , and
O3 = A 3 + B 3 + C 3

ステップ１２は、演算セットに従ったラプラス行列Ｌdを取得するようコンピューターを構成することであり、下記のサブステップを含む。 Step 12 is to configure the computer to obtain a Laplace matrix L d according to the operation set and includes the following sub-steps.

サブステップ１２１において、演算セットに従い、コンピューターは、アルゴリズムに関するデータフロー情報を取得するよう構成される。図２に示されるように、この例の演算セットに対応するデータフロー情報は、下記のように表現されてもよい。
データ１＝Ａ1＋Ｂ1
データ２＝Ａ2＋Ｂ2
データ３＝Ａ3＋Ｂ3
データ４＝データ１＋データ７
データ５＝データ２＋Ｃ2
データ６＝データ３＋Ｃ3
データ７＝Ｃ1＋Ｄ1 In sub-step 121, according to the operation set, the computer is configured to obtain data flow information regarding the algorithm. As shown in FIG. 2, the data flow information corresponding to the operation set of this example may be expressed as follows.
Data 1 = A 1 + B 1
Data 2 = A 2 + B 2
Data 3 = A 3 + B 3
Data 4 = Data 1 + Data 7
Data 5 = Data 2 + C 2
Data 6 = Data 3 + C 3
Data 7 = C 1 + D 1

サブステップ１２２において、コンピューターは、データフロー情報に従って、データフロー・グラフを取得するよう構成される。データフロー・グラフは、アルゴリズムにおいて演算を表す複数の頂点及び、頂点のうち対応する２つの頂点の相互接続を示しアルゴリズムにおけるデータのソースとデスティネーションを示す方向性のある複数の辺によって構成される。図２に示されるデータフロー情報については、演算記号Ｖ1からＶ7（つまり、頂点）が加算記号の代わりに使われ、矢印（つまり、方向性のある辺）が、データのソースとデスティネーションを示し、これにより、図３のデータフロー・グラフが取得される。特に、演算記号Ｖ1が加算演算Ａ1＋Ｂ1を示し、演算記号Ｖ2が加算演算Ａ2＋Ｂ2を示し、演算記号Ｖ3が加算演算Ａ3＋Ｂ3を示し、演算記号Ｖ4が加算演算データ１＋データ７を示し、演算記号Ｖ5が加算演算データ２＋Ｃ2を示し、演算記号Ｖ6が加算演算データ３＋Ｃ3を示し、そして演算記号Ｖ7が加算演算Ｄ1＋Ｃ1を示す。 In sub-step 122, the computer is configured to obtain a data flow graph according to the data flow information. The data flow graph is composed of a plurality of vertices representing operations in the algorithm and a plurality of directional edges indicating the interconnection of two corresponding vertices of the vertices and indicating the source and destination of the data in the algorithm . For the data flow information shown in FIG. 2, operational symbols V 1 through V 7 (ie, vertices) are used instead of addition symbols, and arrows (ie, directional edges) indicate the data source and destination. As a result, the data flow graph of FIG. 3 is obtained. In particular, the operation symbol V 1 indicates an addition operation A 1 + B 1 , the operation symbol V 2 indicates an addition operation A 2 + B 2 , the operation symbol V 3 indicates an addition operation A 3 + B 3 , and the operation symbol V 4 adds. Operation data 1 + data 7 is shown, operation symbol V 5 is addition operation data 2 + C 2 , operation symbol V 6 is addition operation data 3 + C 3 , and operation symbol V 7 is addition operation D 1 + C 1 .

図３に示されるデータフロー・グラフから、演算記号Ｖ4が演算記号Ｖ1及びＶ7に依存することが分かる。同様に、演算記号Ｖ5が演算記号Ｖ2に依存し、演算記号Ｖ6が演算記号Ｖ3に依存し、演算記Ｖ4、Ｖ5及びＶ6は、互いに依存しない。 From the data flow graph shown in FIG. 3, it can be seen that the operation symbol V 4 depends on the operation symbols V 1 and V 7 . Similarly, the operation symbol V 5 depends on the operation symbol V 2 , the operation symbol V 6 depends on the operation symbol V 3, and the operation symbols V 4 , V 5, and V 6 do not depend on each other.

サブステップ１２３において、コンピューターは、データフロー・グラフに従ったラプラス行列Ｌdを取得するように構成される。ラプラス行列Ｌdにおいて、ｉ番目の対角の要素は、演算記号Ｖiに接続される演算記号の数を示し、対角から外れた要素は、２つの演算記号が接続されているかどうかを示す。 従って、ラプラス行列Ｌdは、明確にデータフロー・グラフを、線形代数形式によって示すことができる。図３に示されるデータフロー・グラフのセットは、下記のように示されてもよい。

Figure 0005925202
In sub-step 123, the computer is configured to obtain a Laplace matrix L d according to the data flow graph. In the Laplace matrix L d , the i-th diagonal element indicates the number of arithmetic symbols connected to the arithmetic symbol V i, and the element outside the diagonal indicates whether two arithmetic symbols are connected. . Therefore, the Laplace matrix L d can clearly show a data flow graph in linear algebra form. The set of data flow graphs shown in FIG. 3 may be shown as follows:
Figure 0005925202

ラプラス行列Ｌdは、演算記号Ｖ1からＶ7の間の接続性を示し、第１列から第７列は、演算記号Ｖ1からＶ7をそれぞれ示す。例えば、最初の列において、演算記号Ｖ1は、演算記号Ｖ4に接続され、従って、行列要素(１，４)は−１である。 The Laplace matrix L d indicates connectivity between the operation symbols V 1 to V 7 , and the first to seventh columns indicate the operation symbols V 1 to V 7 , respectively. For example, in the first column, the operation symbol V 1 is connected to the operation symbol V 4 , and thus the matrix element (1, 4) is −1.

ステップ１３において、コンピューターは、ラプラス行列Ｌdの固有値λ及び固有ベクトルＸdを計算するように構成される。上記例において取得されたラプラス行列Ｌdについて、固有値λ及び固有ベクトルＸdは、下記の通りである。

Figure 0005925202
In step 13, the computer is configured to calculate the eigenvalue λ and eigenvector X d of the Laplace matrix L d . For the Laplace matrix L d acquired in the above example, the eigenvalue λ and the eigenvector X d are as follows.
Figure 0005925202

ステップ１４において、コンピューターは、ラプラス行列Ｌdの固有値λ及び固有ベクトルＸdに従って、アルゴリズムの本質的な並列処理に関する情報のセットを取得するように構成される。上記本質的な並列処理に関する情報のセットは、演算セットのうち、互いに独立しており並列処理に実行可能な独立な演算セットを認識するように厳密に定義される。厳密な並列処理に関する情報のセットは、アルゴリズムの上記演算セットのうち、独立な演算セットの数を示す厳密な並列処理の程度、及び、演算セットに対応する厳密な並列処理の構成のセットをそれぞれ含む。Ｆ．Ｒ．Ｋ．チャン（数学のリジョナル・カンファレンス・シリーズ、Ｎｏ．９２、１９９７）によって紹介されたスペクトルグラフ理論に基づき、グラフの接続された構成の数は、０に等しいラプラス行列の固有値の数に等しい。アルゴリズムに埋め込まれた厳密な並列処理の程度は、従って、０に等しい固有値λの数に等しい。その上、スペクトルグラフ理論に基づき、厳密な並列処理の構成は、０に等しい固有値λに関連付けられる固有ベクトルＸdに従って、特定されてもよい。 In step 14, the computer, in accordance with eigenvalue λ and eigenvectors X d Laplace matrix L d, configured to obtain a set of information about the intrinsic parallelism of the algorithm. The set of information regarding the essential parallel processing is strictly defined so as to recognize the independent operation sets that are independent from each other and can be executed in parallel processing. The set of information related to strict parallel processing includes the degree of strict parallel processing that indicates the number of independent operation sets, and the set of strict parallel processing configurations corresponding to the operation sets. Including. F. R. K. Based on the spectral graph theory introduced by Zhang (Mathematical Regional Conference Series, No. 92, 1997), the number of connected components of the graph is equal to the number of eigenvalues of the Laplace matrix equal to zero. The degree of strict parallel processing embedded in the algorithm is therefore equal to the number of eigenvalues λ equal to zero. Moreover, based on spectral graph theory, the exact parallel processing configuration may be specified according to the eigenvector X d associated with the eigenvalue λ equal to zero.

上記例から、０に等しいラプラス固有値は３つ存在するので、データフロー・グラフのセットは、３つの独立な演算セットから構成されることが分かる。従って、例示されるアルゴリズムに埋め込まれる厳密な並列処理の程度は、３に等しい。次に、固有ベクトルＸdの第１、２、及び３の固有ベクトルは、０に等しい固有値λに関連付けられる。固有ベクトルＸdの第１の固有ベクトルを観察することにより、演算記号Ｖ1、Ｖ4及びＶ7に対応する値が０ではないということが明らかであり、つまり、演算記号Ｖ1、Ｖ4及びＶ7は依存し、データフロー・グラフの接続されたもの（Ｖ1−Ｖ4−Ｖ7）を形成する。同様に、０に等しい固有値λに関連付けられた固有ベクトルＸdの第２及び３の固有ベクトルを形成し、演算記号Ｖ2、Ｖ5及び演算記号Ｖ3、Ｖ6 は依存し、データフロー・グラフの残りの２つの接続されたもの（Ｖ2−Ｖ5及びＶ3−Ｖ6）をそれぞれ形成すると理解される。従って、コンピューターは、３に等しい厳密な並列処理の程度、及び、（図３に示されるような）グラフ、テーブル、等式、又はプログラムコードの形態で表現されうる厳密な並列処理の構成を取得するように構成される。 From the above example, it can be seen that since there are three Laplace eigenvalues equal to 0, the dataflow graph set is composed of three independent sets of operations. Therefore, the degree of strict parallel processing embedded in the illustrated algorithm is equal to 3. Next, the first, second, and third eigenvectors of eigenvector X d are associated with an eigenvalue λ equal to zero. By observing the first eigenvector of the eigenvector X d , it is clear that the values corresponding to the operation symbols V 1 , V 4 and V 7 are not 0, that is, the operation symbols V 1 , V 4 and V 7 depends and forms a connected (V 1 -V 4 -V 7 ) of the data flow graph. Similarly, the second and third eigenvectors of the eigenvector X d associated with the eigenvalue λ equal to 0 are formed, the operation symbols V 2 , V 5 and the operation symbols V 3 , V 6 are dependent, and the data flow graph the remaining two connected ones (V 2 -V 5 and V 3 -V 6) is understood to form respectively. Thus, the computer obtains a degree of strict parallel processing equal to 3 and a strict parallel processing configuration that can be expressed in the form of a graph, table, equation, or program code (as shown in FIG. 3). Configured to do.

ステップ１５において、コンピューターは、アルゴリズムの複数の依存性深さの少なくとも１つ及び厳密な並列処理に関する情報のセットに従ったアルゴリズムのマルチグレイン並列処理に関する情報の複数のセットを取得するように構成される。マルチグレイン並列処理に関する情報のセットは、独立な演算セットに埋め込まれた全ての可能性のある並列処理を特徴付けるアルゴリズムの広義の並列処理に関する情報のセット含む。   In step 15, the computer is configured to obtain a plurality of sets of information regarding multi-grain parallelism of the algorithm according to at least one of the plurality of dependency depths of the algorithm and a set of information regarding strict parallelism. The The set of information regarding multi-grain parallel processing includes a set of information regarding broad parallel processing of algorithms that characterize all possible parallel processing embedded in an independent set of operations.

尚、アルゴリズムの依存性深さは、アルゴリズムの処理において重要な、関連付けられた逐次ステップを表し、つまり、アルゴリズムの可能な並列処理に対して相互補完的である。従って、 アルゴリズムの異なる本質的な並列処理に関する情報は、異なる依存性深さに基づいて取得されてもよい。特に、厳密な並列処理に関する情報は、アルゴリズムの依存性深さのうち最大のものに対応するアルゴリズムの本質的な並列処理に関する情報であり、広義の並列処理に関する情報は、依存性深さのうち最小のものに対応するアルゴリズムの本質的な並列処理に関する情報である。   Note that the depth of dependency of an algorithm represents an associated sequential step that is important in the processing of the algorithm, that is, complementary to the possible parallel processing of the algorithm. Thus, information regarding the intrinsic parallel processing of different algorithms may be obtained based on different dependency depths. In particular, information on strict parallel processing is information on the intrinsic parallel processing of the algorithm corresponding to the largest of the algorithm dependency depths, and information on parallel processing in a broad sense is information on the dependency depths. Information on the essential parallel processing of the algorithm corresponding to the smallest one.

例えば、上記アルゴリズムは、厳密な並列処理の２つの異なる構成、つまり、Ｖ1−Ｖ4−Ｖ7及びＶ2−Ｖ5を含む（Ｖ3−Ｖ6は、Ｖ2−Ｖ5に似ており、同じ構成と考えられる）。厳密な並列処理Ｖ1−Ｖ4−Ｖ7の構成については、演算記号Ｖ1及びＶ7が互いに独立である、つまり、演算記号Ｖ1及びＶ7が並列に処理されることができることが分かる。従って、 アルゴリズムの広義の並列処理に関する情報のセットは、４に等しい広義の並列処理の程度を含み、広義の並列処理の構成は、厳密な並列処理の構成に類似する。 For example, the above algorithm includes two different configurations of strictly parallel processing: V 1 -V 4 -V 7 and V 2 -V 5 (V 3 -V 6 is similar to V 2 -V 5. And is considered the same configuration). The configuration of strict parallelism V 1 -V 4 -V 7, an independent operation symbol V 1 and V 7 are mutually, i.e., it can be seen that the operation symbol V 1 and V 7 can be processed in parallel . Therefore, the set of information regarding the parallel processing in the broad sense of the algorithm includes the degree of parallel processing in the broad sense equal to 4, and the configuration of the parallel processing in the broad sense is similar to the configuration of strict parallel processing.

この実施例の方法によれば、上記アルゴリズムの広義の並列処理の程度は、４に等しい。 アルゴリズムを実装するのに、処理要素は７回の処理サイクルを要する。なぜならば、アルゴリズムは７個の演算記号Ｖ1−Ｖ7を含むからである。３に等しい厳密な並列処理の程度によれば、３個の処理要素を使ってアルゴリズムを実装するには、３回の処理サイクルを使う。４に等しい広義の並列処理の程度によれば、４個の処理要素を使ってアルゴリズムを実装するには、２回の処理サイクルを使う。更に、より多くの処理要素が使われるものの、少なくとも２回の処理サイクルがアルゴリズムを実装するのに必要であることが分かる。従って、アルゴリズムを実装するのに使われる処理要素の最適な数は、この実施例の方法に従って取得されうる。 According to the method of this embodiment, the degree of parallel processing in the broad sense of the above algorithm is equal to 4. The processing element requires seven processing cycles to implement the algorithm. This is because the algorithm includes seven operational symbols V 1 -V 7 . According to the degree of strict parallel processing equal to 3, to implement an algorithm using three processing elements, three processing cycles are used. According to the degree of parallel processing in a broad sense equal to 4, two processing cycles are used to implement an algorithm using four processing elements. Furthermore, although more processing elements are used, it can be seen that at least two processing cycles are required to implement the algorithm. Thus, the optimal number of processing elements used to implement the algorithm can be obtained according to the method of this embodiment.

４×４離散コサイン変換（ＤＣＴ）を例とすると、ＤＣＴアルゴリズムの演算セットは、図４に示されるデータフロー・グラフによって表現される。４×４ＤＣＴは当業者によってよく知られているので、その更に詳細については、簡潔さのためにここでは省略される。図４より、４×４ＤＣＴアルゴリズムの依存性深さの最大のものは、６に等しいことが分かる。依存性深さの最大のもの（つまり、６）については、このアルゴリズムの厳密な並列処理の構成は、図５に示されるように取得されてもよく、このアルゴリズムの厳密な並列処理の程度は、この実施例の方法によれば、４に等しい。５に等しい依存性深さのうち１つをもって４×４ＤＣＴアルゴリズムの本質的な並列処理を分析する時、このアルゴリズムの本質的な並列処理の構成は、図６に示されるように取得されてもよく、本質的な並列処理の程度は８に等しい。更に、３に等しい依存性深さのうち１つをもって４×４ＤＣＴアルゴリズムの本質的な並列処理を分析する時、このアルゴリズムの本質的な並列処理の構成は、図７に示されるように取得されてもよく、本質的な並列処理の程度は１６に等しい。   Taking a 4 × 4 discrete cosine transform (DCT) as an example, the operation set of the DCT algorithm is represented by the data flow graph shown in FIG. Since 4 × 4 DCT is well known by those skilled in the art, further details thereof are omitted here for the sake of brevity. FIG. 4 shows that the maximum dependency depth of the 4 × 4 DCT algorithm is equal to 6. For the maximum dependency depth (ie 6), the exact parallelism configuration of this algorithm may be obtained as shown in FIG. According to the method of this embodiment, it is equal to 4. When analyzing the intrinsic parallelism of the 4 × 4 DCT algorithm with one of the dependency depths equal to 5, the intrinsic parallelism configuration of this algorithm can be obtained as shown in FIG. Well, the degree of intrinsic parallelism is equal to 8. Furthermore, when analyzing the intrinsic parallelism of the 4 × 4 DCT algorithm with one of the dependency depths equal to 3, the intrinsic parallelism configuration of this algorithm is obtained as shown in FIG. The degree of intrinsic parallel processing is equal to 16.

つまり、この発明による方法は、アルゴリズムの本質的な並列処理を評価するのに使われてもよい。   That is, the method according to the invention may be used to evaluate the intrinsic parallelism of the algorithm.

本発明は、最も実用的で好適な実施例と考えられるものに関連付けられて記載されたものの、この発明は、記載された実施例に限定されることなく、最も広い解釈の精神及び範囲に含まれる様々な配設を網羅するように意図され、そのような全ての変更や均等な配設を含む、と考えられなければならない。   Although the present invention has been described in connection with what are considered to be the most practical and preferred embodiments, the invention is not limited to the described embodiments and is included in the spirit and scope of the broadest interpretation. It is intended to cover various arrangements that may be considered, and should be considered to include all such modifications and equivalent arrangements.

Claims (10)

アルゴリズムの本質的な並行処理を定量化及び分析する方法であって、前記方法はコンピューターによって実装されるように構成され、前記方法は、
ａ） 前記コンピューターを、複数の演算セットによる前記アルゴリズムを表現するよう構成させるステップ、
ｂ） 前記コンピューターを、前記複数の演算セットに従いラプラス行列を取得するよう構成させるステップ、
ｃ） 前記コンピューターを、前記ラプラス行列の固有値及び固有ベクトルを計算するよう構成させるステップ、及び
ｄ） 前記コンピューターを、前記ラプラス行列の前記固有値及び前記固有ベクトルに従って、アルゴリズムの本質的な並行処理に関する情報のセットを取得させるよう構成させるステップ、を含み、
ステップｄ）は、
ｄ１）前記コンピューターを、前記ラプラス行列の前記固有値及び前記固有ベクトルに従って、前記アルゴリズムの厳密な並列処理に関する情報のセットを取得するよう構成させるサブステップ、並びに
ｄ２）前記コンピューターを、前記アルゴリズムの複数の依存性深さの少なくとも１つ及び前記厳密な並列処理に関する情報のセットに従って、前記アルゴリズムのマルチグレイン並列処理に関する情報のセットを取得するよう構成させるサブステップ、
を含むことを特徴とする前記方法。 A method for quantifying and analyzing the intrinsic parallelism of an algorithm, said method being configured to be implemented by a computer, said method comprising:
a) configuring the computer to represent the algorithm with a plurality of sets of operations;
b) configuring the computer to obtain a Laplace matrix according to the plurality of operation sets;
c) configuring the computer to calculate eigenvalues and eigenvectors of the Laplace matrix; and d) setting the computer with information about intrinsic parallel processing of the algorithm according to the eigenvalues and eigenvectors of the Laplace matrix. viewing including the step, which is configured so as to get a,
Step d)
d1) causing the computer to be configured to obtain a set of information regarding exact parallel processing of the algorithm according to the eigenvalues and the eigenvectors of the Laplace matrix; and
d2) Substep of configuring the computer to obtain a set of information regarding multi-grain parallel processing of the algorithm according to at least one of the plurality of dependency depths of the algorithm and the set of information regarding the strict parallel processing. ,
Said method comprising including Mukoto a. ステップｂ）は、
ｂ１） 前記コンピューターを、演算セットに従い、前記アルゴリズムに関するデータフロー情報を取得するよう構成させるサブステップ、
ｂ２） 前記コンピューターを、前記データフロー情報に従い、前記アルゴリズムにおける演算を示す複数の頂点から成るデータフロー・グラフを取得するよう構成させ、前記頂点のうち対応する２つの頂点の相互接続を示し前記アルゴリズムにおけるデータのソースとデスティネーションを示す方向性のある複数の辺を取得するよう構成させるサブステップ、及び
ｂ３） 前記コンピューターを、前記データフロー・グラフに従って、前記ラプラス行列を取得するよう構成させるサブステップ、
を含む、請求項１に記載の方法。 Step b)
b1) Substep for configuring the computer to obtain data flow information regarding the algorithm according to a set of operations;
b2) The computer is configured to acquire a dataflow graph composed of a plurality of vertices indicating operations in the algorithm according to the dataflow information, and indicates an interconnection of two corresponding vertices among the vertices. A sub-step configured to obtain a plurality of directional edges indicating the source and destination of the data, and b3) a sub-step configured to obtain the Laplace matrix according to the data flow graph ,
The method of claim 1 comprising: 前記厳密な並列処理に関する情報のセットは、前記アルゴリズムの前記演算セットの独立なものの数を表す厳密な並列処理の程度と、前記演算セットに対応する厳密な並列処理の構成のセット、をそれぞれ含む、請求項１に記載の方法。 The strict parallel processing information set includes a strict parallel processing degree representing the number of independent operation sets of the algorithm, and a strict parallel processing configuration set corresponding to the operation set, respectively. The method of claim 1 . サブステップｄ２）において、前記コンピューターは、前記依存性深さ及び前記厳密な並列処理に関する情報のセットに従って前記アルゴリズムのマルチグレイン並列処理に関する複数の情報のセットをそれぞれ取得するよう構成されることを特徴とする請求項１に記載の方法。 In sub-step d2), the computer is configured to respectively obtain a plurality of sets of information regarding multi-grain parallel processing of the algorithm according to the dependency depth and the set of information regarding the strict parallel processing. The method according to claim 1 . 前記アルゴリズムのマルチグレイン並列処理に関する複数の情報のセットのそれぞれは、マルチグレイン並列処理の程度、及び、マルチグレイン並列処理の構成のセットを含むことを特徴とする請求項４に記載の方法。 Each set of the plurality of information regarding the multigrain parallel processing of the algorithm, the degree of multigrain parallel processing, and a method according to claim 4, characterized in that it comprises a set of configuration of a multi-grain parallel processing. 前記マルチグレイン並列処理に関する情報のセットは、前記依存性深さの最小のもの及び前記厳密な並列処理に関する情報のセットに従って取得される前記アルゴリズムの広義の並列処理に関する情報のセットを含むことを特徴とする請求項１に記載の方法。 The set of information regarding multi-grain parallel processing includes a set of information regarding parallel processing of the algorithm in a broad sense obtained according to the minimum of the dependency depth and the set of information regarding strict parallel processing. The method according to claim 1 . 前記広義の並列処理に関する情報のセットは、前記アルゴリズムの前記演算セットの独立なものに埋め込まれた全ての可能な並列処理を特徴付ける広義の並列処理の程度、及び、広義の並列処理の構成のセットを含むことを特徴とする請求項６に記載の方法。 The set of information regarding the parallel processing in the broad sense includes a degree of parallel processing in the broad sense characterizing all possible parallel processing embedded in the independent operation set of the algorithm, and a set of configurations of the broad sense of parallel processing. The method of claim 6 , comprising: サブステップｄ１）において、前記厳密な並列処理の程度は、スペクトルグラフ理論に基づき、０に等しい前記固有値の数に等しいことを特徴とする請求項１に記載の方法。 In sub-step d1), the extent of the strict parallelism The method of claim 1, based on the spectral graph theory, characterized in that equal to the number of the eigenvalues equal to zero. 前記マルチグレイン並列処理に関する情報は、マルチグレイン並列処理の程度と、マルチグレイン並列処理の構成のセットを含むことを特徴とする請求項１に記載の方法。 The method of claim 1 , wherein the information regarding multi-grain parallel processing includes a degree of multi-grain parallel processing and a set of multi-grain parallel processing configurations. 請求項１に記載のアルゴリズムの本質的な並行処理を定量化及び分析する方法を実行時にコンピューターに行わせるプログラム命令を記録した機械読み取り可能な記憶媒体を有するコンピューター。 Computer chromatography with machine-readable storage medium storing program instructions for causing the computer during performing a method for quantifying and analyzing the essential parallelism of the algorithm according to claim 1.
JP2013518789A 2010-07-06 2011-07-05 Method for quantifying and analyzing parallel processing of algorithms Active JP5925202B2 (en)

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
TW099122162 2010-07-06
TW099122162A TWI501168B (en) 2010-07-06 2010-07-06 An intrinsic parallelism of an algorithm quantification and analysis method
US12/832,557 2010-07-08
US12/832,557 US20120011186A1 (en) 2010-07-08 2010-07-08 Method for quantifying and analyzing intrinsic parallelism of an algorithm
PCT/US2011/042962 WO2012006285A1 (en) 2010-07-06 2011-07-05 Method for quantifying and analyzing intrinsic parallelism of an algorithm

Publications (2)

Publication Number Publication Date
JP2013530477A JP2013530477A (en) 2013-07-25
JP5925202B2 true JP5925202B2 (en) 2016-05-25

Family

ID=45441539

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2013518789A Active JP5925202B2 (en) 2010-07-06 2011-07-05 Method for quantifying and analyzing parallel processing of algorithms

Country Status (4)

Country Link
EP (1) EP2591414A4 (en)
JP (1) JP5925202B2 (en)
KR (1) KR20130038903A (en)
WO (1) WO2012006285A1 (en)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10593080B2 (en) 2017-04-27 2020-03-17 Daegu Gyeongbuk Institute Of Science And Technology Graph generating method and apparatus
KR101998020B1 (en) * 2017-04-27 2019-07-08 재단법인대구경북과학기술원 Method and apparatus for graph generation
CN111061150B (en) * 2019-10-23 2020-11-27 南京大学 Hardware implementation method of Laplace frequency response

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5587922A (en) * 1993-06-16 1996-12-24 Sandia Corporation Multidimensional spectral load balancing
US7418470B2 (en) * 2000-06-26 2008-08-26 Massively Parallel Technologies, Inc. Parallel processing systems and method
US6615211B2 (en) * 2001-03-19 2003-09-02 International Business Machines Corporation System and methods for using continuous optimization for ordering categorical data sets
US7171397B1 (en) * 2002-08-21 2007-01-30 Ncr Corp. Method and system for measuring parallelism of a database system execution step
US7724256B2 (en) * 2005-03-21 2010-05-25 Siemens Medical Solutions Usa, Inc. Fast graph cuts: a weak shape assumption provides a fast exact method for graph cuts segmentation
US8548238B2 (en) * 2007-05-03 2013-10-01 Carnegie Mellon University Method for partitioning combinatorial graphs
US8201171B2 (en) * 2007-06-27 2012-06-12 Microsoft Corporation Adjacent data parallel and streaming operator fusion
US7406200B1 (en) * 2008-01-08 2008-07-29 International Business Machines Corporation Method and system for finding structures in multi-dimensional spaces using image-guided clustering
US8522224B2 (en) 2010-06-22 2013-08-27 National Cheng Kung University Method of analyzing intrinsic parallelism of algorithm

Also Published As

Publication number Publication date
WO2012006285A1 (en) 2012-01-12
EP2591414A1 (en) 2013-05-15
EP2591414A4 (en) 2014-08-06
JP2013530477A (en) 2013-07-25
KR20130038903A (en) 2013-04-18

Similar Documents

Publication Publication Date Title
CN109190758B (en) Method and apparatus for unwrapping tensor data for convolutional neural networks
KR101517308B1 (en) Method of analyzing intrinsic parallelism of algorithm
CN106855952B (en) Neural network-based computing method and device
JP5925202B2 (en) Method for quantifying and analyzing parallel processing of algorithms
US11899741B2 (en) Memory device and method
TW201030607A (en) Instruction and logic for performing range detection
EP3295300B1 (en) System and method for determining concurrency factors for dispatch size of parallel processor kernels
US11880463B2 (en) Systems and methods for thermal side-channel analysis and malware detection
Hwang et al. A parallel adaptive nonlinear elimination preconditioned inexact Newton method for transonic full potential equation
TWI622014B (en) Apparatus and method for image processing
WO2019023910A1 (en) Data processing method and device
CN110750249A (en) Method and device for generating fast Fourier transform code
Kaiser et al. Package ‘biclust’
GB2567038B (en) Accessing prologue and epilogue data
US20230334062A1 (en) Computer-readable recording medium storing correlation coefficient computation program, information processing device, and correlation coefficient computation method
Shahbahrami et al. Avoiding conversion and rearrangement overhead in SIMD architectures
JPWO2017026051A1 (en) Image processing apparatus, image processing method, and image processing program
Imamura et al. Numerical reproducibility based on minimal-precision validation
Cong et al. Block Krylov subspace methods for approximating the linear combination of φ-functions arising in exponential integrators
JP7452247B2 (en) Conversion program, conversion method, and information processing device
Amano et al. Performance and cost analysis of time-multiplexed execution on the dynamically reconfigurable processor
Lin et al. Quantifying intrinsic parallelism via eigen-decomposition of dataflow graphs for algorithm/architecture co-exploration
Curreri et al. Communication visualization for bottleneck detection of high-level synthesis applications
KR101614215B1 (en) Low-power approximate multiplier and opertation mehotd of thereof
Zhang et al. Hlanc: heterogeneous parallel implementation of the implicitly restarted Lanczos method

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20140619

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20150624

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20150728

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20151027

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20160405

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20160419

R150 Certificate of patent or registration of utility model

Ref document number: 5925202

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313113

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250