(57)【要約】【課題】ノイマン型プログラムの変換に関して、変換前のプログラムに制約が少なく、性能が高くしかもプログラムの改変が容易な、プログラム行列演算化装置を提供すること。【解決手段】一例のプログラム疎行列演算化装置は、ノイマン型プログラムを一群の疎行列プログラムに変換するノイマン型プログラムの疎行列演算化装置であって、変換前プログラムの並列ロジック化を行う並列ロジック化部と、この並列ロジック化部により得られた中間プログラムから疎行列を作成する疎行列作成部と、この疎行列作成部により得られた疎行列を保持する変換後プログラム保持部と、を備え、疎行列の演算を得意とするハードウェアにより高速に並列実行が可能な疎行列プログラムを作成することを特徴とする。【選択図】図１
2014197338.tif 000002
【特許請求の範囲】
【請求項１】
ノイマン型プログラムを一群の疎行列プログラムに変換するノイマン型プログラムの疎行列演算化装置であって、
変換前プログラムの並列ロジック化を行う並列ロジック化部と、
この並列ロジック化部により得られた中間プログラムから疎行列を作成する疎行列作成部と、
この疎行列作成部により得られた疎行列を保持する変換後プログラム保持部と、を備え、
疎行列の演算を得意とするハードウェアにより高速に並列実行が可能な疎行列プログラムを作成することを特徴とするプログラム疎行列演算化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、プログラム疎行列演算化装置に関する。
【背景技術】
【０００２】
ノイマン型プログラムは一般的には、直列的に演算処理を行うので、複雑な演算処理を行う場合には、時間がかかる。そこで行列式を用いて複数のプログラムに変換し、複数のＣＰＵを用いて並列的に処理することが考えられた。
【０００３】
例えば、画像処理用のＧＰＵを汎用プログラムに用いるためには特定の規則に従って、微少加工やヘッダの追加を行う。この発明の実施形態は、並列演算が容易に考えられる計算対象に関するものであり、対象を特定しないプログラムに対するものではない。
【０００４】
従来のこの種の並列演算化装置は、プログラム言語以外に記述ルールがありまたプログラム言語の一部の機能が含まれていてはならない等、変換前のプログラムに大きな制約があり、変換後のプログラムの性能があまり高くないなどの問題がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−１０８８３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の課題は、ノイマン型プログラムの変換に関して、変換前のプログラムに制約が少なく、性能が高くしかもプログラムの改変が容易な、プログラム疎行列演算化装置を提供することである。
【課題を解決するための手段】
【０００７】
一実施形態のプログラム疎行列演算化装置は、ノイマン型プログラムを一群の疎行列プログラムに変換するノイマン型プログラムの疎行列演算化装置であって、変換前プログラムの並列ロジック化を行う並列ロジック化部と、この並列ロジック化部により得られた中間プログラムから疎行列を作成する疎行列作成部と、この疎行列作成部により得られた疎行列を保持する変換後プログラム保持部と、を備え、疎行列の演算を得意とするハードウェアにより高速に並列実行が可能な疎行列プログラムを作成することを特徴とするプログラム疎行列演算化装置である。
【図面の簡単な説明】
【０００８】
【図１】一実施形態に係る構成例を示す図である。
【図２】一実施形態における並列実行の各要素の依存関係を示す図である。
【図３】一実施形態におけるスケジューリングの例を示す図である。
【図４】一実施形態における積和の疎行列の例を示す図である。
【図５】一実施形態における乗積の疎行列の例を示す図である。
【図６】一実施形態における正判の疎行列の例を示す図である。
【発明を実施するための形態】
【０００９】
実施形態について図面を用いて以下に説明する。図１に一実施形態の構成例を示す。
【００１０】
このプログラム疎行列演算化装置１１は、疎行列化演算処理を行う前の変換前プログラムを保持する変換前プログラム保持部１２と、どのように並列ロジックを行うかを決定する並列ロジック化部１３と、この並列ロジック化部１３のロジックにより上記変換前プログラム保持部に保持されていたプログラムから並列ロジック疎行列化プログラムを得る疎行列作成部１４と、このロジック化プログラム取得部１４において得た疎行列を保持する変換後プログラム保持部１６と、を有する。
【００１１】
並列ロジック化部１３では、変換前プログラム保持部１２から入力された変換前のプログラムがどのような構造になっているかを分析し並列に演算できるプログラムを検出する。この並列化されたプログラムは疎行列作成部１４に入力され、出力される疎行列を変換後プログラム保持部１６において保持される。
【００１２】
ここで、例を挙げて具体的に説明する。
【００１３】
（疎行列プログラムの作成例）
次に数の少ない簡易なSIMD（Single Instruction Multiple Data）型演算によりノイマン型プログラムを並列に実行する疎行列の作成手法について、一例を具体的に説明する。
【００１４】
まず第１ステップとしてノイマン型プログラムを、種類の少ない演算、かつ行列演算に適用したときに単位行列を有し、かつその単位行列が疎行列となるものに変換する。第２ステップとして変換されたものを疎行列に構成する。
【００１５】
今、演算の種類として、積和（演算子「・」）、乗積（演算子「×」）、正判（演算子「？」）の３種類があるとする。「＊」は上記３つの演算子のいずれかである。
【数１】
2014197338.tif 000003
【００１６】
ここで、＊は演算子である。
【００１７】
すると、積和（・）は次式のようになる。
【００１８】
ｏ１＝ｉ１×ｃ  １１＋・・・＋ｉｍ×ｃｍ１
・・・・・・・・・・・・・・
ｏｎ＝ｉ１×ｃ１ｎ＋・・・＋ｉｍ×ｃｍｎ      ・・・（２）
また、乗積（×）は次式のようになる。
【００１９】
ｏ１＝ｉ１ｃ１１×・・・×ｉｍｃｍ１ 
・・・・・・・・・・・・・・・
ｏｎ＝ｉ１ｃ１ｎ×・・・×ｉｍｃｍｍ          ・・・（３）
但し、ｏ０＝１とする。
【００２０】
更に、正判（？）は、次式のようになる。
【００２１】
［数２］
2014197338.tif 000004
【００２２】
但し、ｉ＝０のときｆ（ｉ，ｃ）＝０、ｉ０＝１とする。
【００２３】
今、変換前のプログラムが次のようであるとする。
【００２４】
void prog(a, b, c, d, &x, &y){
if (a>b && c>d){
x=d;
}
if (a+b>c*d){
y=a*b;
} else {
y=x;
}
return
}                                              ・・・・（５）
並列ロジック化部１３において、上記（５）式のプログラムがまずif-elseの変形がなされ、次に示す変換１の（６）式となる。
【００２５】
void prog(a, b, c, d, &x, &y){
x= (a-b>0 && c-d>0? d:0;
y=a+b -c*d>0)? a*b:x;
return
}                                           ・・・・・・（６）
次に、上記（６）式を行列演算で用いられる演算に変形して、次の変換２である（７）式が得られる。
【００２６】
void prog(a, b, c, d, &x, &y){
r1=a-b; r2=c-d;
r3= (r1>0 && r2>0)? 1:0;
r4= r3*(-1)+1;
r5= d*r3;
r6= 0*r4;
x=r5+r6;
r7= a+ b; r8=c*d;
r9=r7-r8
r10= (r9>0)?1:0;
r11= r10*(-1)+1;
r12= a*b;
r13= r12*r10
r14= x*r11;
y= r13+r14;
return;
}                                      ・・・・・・・（７）
更に、上記（７）式のプログラムの自明の削除を変換３として行うと、次の（８）式が得られる。
【００２７】
void prog(a, b, c, d, &x, &y){
r1=a-b; r2=c-d;
r3= (r1>0 && r2>0)? 1:0;
x= d*r3;
r7= a+ b; r8=c*d;
r9=r7-r8
r10= (r9>0)?1:0;
r11= r10*(-1)+1;
r12= a*b;
r13= r12*r10
r14= x*r11;
y= r13+r14
return;
}                                     ・・・・・・・（８）
次にこの（８）式のプログラムを疎行列に変換する。そのために各要素の依存関係を調べる。この過程を図２に基づいて説明する。（８）式の下の方から辿ると、ｙ（・）は、ｒ１３（ｘ）とｒ１４（ｘ）に依存しており、ｒ１４（ｘ）は、ｘ（ｘ）とｒ１１（・）に依存している。ｒ１３（ｘ）はｒ１２（ｘ）とｒ１０（？）に依存しており、ｒ１２（ｘ）はａとｂに依存している。
【００２８】
ｒ１１（・）はｒ１０（？）に依存し、ｒ１０（？）はｒ９（・）に依存する。ｒ９（・）はｒ７（・）とｒ８（ｘ）に依存し、ｒ７（・）はａとｂに依存し、ｒ８（ｘ）はｃとｄに依存する。
【００２９】
また、ｘ（ｘ）はｄとｒ３（？）に依存し、ｒ３（？）はｒ１（・）と、ｒ２（・）に依存する。ｒ１（・）はａとｂに依存し、ｒ２（・）はｃとｄに依存する。
【００３０】
次にスケジューリングを行う。今の場合、演算を積和（・）、乗積（×）、正判（？）の順序に行うとすると、上記依存関係なら、図３に示す４つのサイクルが導かれる。
【００３１】
そして、疎行列作成部１４において、これらの関係を積和（・）、乗積（×）、正判（？）の行列で表す。積和（・）の行列を図４に示し、乗積（×）の行列を図５に示し、正判（？）の行列を図６に示す。例えば、積和の行列において、ｒ７＝ａ＋ｂであり、ｒ９＝ｒ７−ｒ８である。
【００３２】
このようにして、積和の行列（プログラム）が得られる。図４から、０以外が遍在する３つの疎行列（０は空白で表示している）が得られたことがわかる。
【００３３】
これらの図４乃至図６から、各演算毎の疎行列が構成されたことが理解される。
【００３４】
以上述べたように、疎行列群を作成し、これらを並列に演算していくことにより演算処理の速度を向上させることができる。この疎行列の作成は、例えば図１では、並列ロジック化部１３、疎行列作成部１４で行われる。
【００３５】
本発明の実施形態によれば、プログラミング言語以外の記述ルールや、その言語に含まれる一部の機能は、ＶＨＤＬやVerilogHDLと同等にすることができる。
【００３６】
また、本発明の実施形態によれば、ＧＰＧＰＵメーカが提供する疎行列演算ライブラリを利用することができ、ハードウェア（ＦＰＧＡ）による並列実行と同様になり、相当の性能が出せる。変換後のプログラムを改変せず変換前のプログラムを改変することにより機能の改変を行うことができ、実質的に変換後のプログラムを改変できる。また上記実施形態によれば変換前のプログラムはＶＨＤＬやVerilogHDLと同様に改変が容易である。
【００３７】
本発明で、「疎行列の演算を得意とするハードウェア」とは例えばＧＰＧＰＵである。
【００３８】
（その他変形例）
本発明のいくつかの実施形態を説明したがこれらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００３９】
１１・・・・プログラム行列演算化装置
１２・・・・変換前プログラム保持部
１３・・・・並列ロジック化部
１４・・・・疎行列作成部
１６・・・・変換後プログラム保持部
【図１】
2014197338.tif 000005
【図２】
2014197338.tif 000006
【図３】
2014197338.tif 000007
【図４】
2014197338.tif 000008
【図５】
2014197338.tif 000009
【図６】
2014197338.tif 000010