(57)【要約】【課題】    並列処理プログラムを正規化する並列処理正規化プログラムに関し、より詳細には並列処理プログラムのデータと計算との相互の整列関係を一定の標準形に正規化することにより実行性能を向上させるプログラムを提供することを目的とする。【解決手段】  本発明の並列処理正規化プログラムは、ソースコード中のプロセッサ群の各次元の上下限値を所定の値に変換するプロセッサ形状変換手順と、テンプレートの各次元の上下限値を所定の値に変換するテンプレート形状変換手順と、プロセッサ群に直接分散している変数と実行ループのテンプレートを生成して整列させるテンプレート整列化手順と、間接的にテンプレートに整列する変数と実行ループを直接に整列するよう変換する直接整列化手順とで構成する。【選択図】    図１
2005084939.tif 000002
【特許請求の範囲】
【請求項１】
並列処理プログラムのコード中におけるプロセッサ群の次元の上下限値を所定の値に変換するプロセッサ形状変換手順と、
前記コード中における第１のテンプレートの次元の上下限値を所定の値に変換するテンプレート形状変換手順と、
前記プロセッサ群に直接分散されている変数と実行ループのそれぞれに対して前記所定の変換による形状を持つ第２のテンプレートを生成し、該変数または該実行ループを該第２のテンプレートに整列させるテンプレート整列化手順と、
前記第１または第２のテンプレートに整列した変数に対して整列した他の変数と実行ループとを、該第１のまたは第２のテンプレートに直接に整列させる直接整列化手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。
【請求項２】
並列処理プログラムのコード中のテンプレートに整列している変数に対して、該変数の宣言された次元の上下限値を該テンプレートの次元の上下限値と等しい値に変換する変数形状変換手順と、
前記変数の前記テンプレートへの整列を、恒等的な形式に変換する第１の整列変換手順と、
前記変数のアクセスに対する添字式を所定の変換規則に基づいて変換する第１の添字式変換手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。
【請求項３】
並列処理プログラムのコード中のテンプレートに整列している実行ループに対して、該実行ループの整列の係数と定数とに基づいて該実行ループの初期値、終値、増分を変換するループパラメタ変換手順と、
前記実行ループの前記テンプレートへの整列を、恒等的な形式に変換する第２の整列変換手順と、
前記実行ループのアクセスに対する添字式を所定の変換規則に基づいて変換する第２の添字式変換手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。
【請求項４】
並列処理言語要素が正規化されている並列処理プログラムのコード中の、テンプレートに整列している実行ループの中での変数に対するアクセスが、ローカルアクセスであるか否かを判定するローカルアクセス判定手順と、
前記ローカルアクセスと判定された実行ループと変数とのアクセス要素に対して識別情報を付与する識別情報付与手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。
【請求項５】
並列処理プログラムのコード中におけるプロセッサ群の次元の上下限値を所定の値に変換するプロセッサ形状変換手順と、
前記コード中における第１のテンプレートの次元の上下限値を所定の値に変換するテンプレート形状変換手順と、
前記プロセッサ群に直接分散されている変数と実行ループのそれぞれに対して前記所定の変換による形状を持つ第２のテンプレートを生成し、該変数または該実行ループを該第２のテンプレートに整列させるテンプレート整列化手順と、
前記第１または第２のテンプレートに整列した変数に対して整列した他の変数と実行ループとを、該第１のまたは第２のテンプレートに直接に整列させる直接整列化手順と
を有することを特徴とする並列処理プログラムの正規化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
並列処理プログラムにおける正規化に関し、より詳細には並列処理プログラムのデータと計算との相互の整列関係を一定の標準形に正規化する並列処理正規化プログラムおよびその正規化方法に関する。
【背景技術】
【０００２】
並列計算機で数値計算を行う場合、以下のような方法がある。
【０００３】
１．ＭＰＩ (Message Passing Library)などのメッセージパッシングライブラリや、マ      シンに固有な低レベルの通信ライブラリを使って、プロセッサ間の通信を含む計算      機の挙動を直接記述する方法（非特許文献１）。
【０００４】
２．ＯｐｅｎＭＰ、ＶＰＰ  Ｆｏｒｔｒａｎなどの並列プログラミング言語を利用して      、プログラムの並列化方法をプログラマが指示する方法。この場合、通信や同期な      どの並列実行のために必要な細部の挙動はコンパイラが自動的に生成するので、プ      ログラマは原則として記述する必要はない（ＯｐｅｎＭＰについては、非特許文献      ２及び３、ＶＰＰ  Ｆｏｒｔｒａｎについては非特許文献４）。
【０００５】
３．ＦｏｒｔｒａｎやＣなどの並列性を意識しないプログラムを元に、自動並列化コン      パイラやインタラクティブなツール類によって並列化を行う方法。
【０００６】
４．上記２と３の中間。プログラマからの指示（あるいは情報）とコンパイラの自動並      列化の両方によってプログラムの並列化を行う方法。ＨＰＦ (High Performance F      ortran) では、プログラマは並列化の指示と並列化を促すための情報をコンパイラ      に与えることができる（非特許文献５〜７）。
【０００７】
プログラマはプログラムの容易さから２〜４の方法を望むが、性能面で劣るため、やむなく１の方法が使われることが多い。
【０００８】
ＨＰＦのような抽象度と自由度の高い言語仕様で分散並列を記述すると、配列データや実行ループの相互の整列関係は非常に複雑なものとなる場合がある。図５にＨＰＦプログラムの例を示す。その整列関係を図示したものが図６である。例えば配列Ａは図５の３行目のＤＩＳＴＲＩＢＵＴＥ指示文によってプロセッサ群Ｐへの分割割付けが指定されていて、配列Ｄは５行目のＡＬＩＧＮ指示文によって配列Ａとの整列が指定されているが、この組合せの効果により、配列Ｄの各配列要素がプロセッサ群Ｐのどこへ割り付けられるかが決定される。また、ループＬ１は１１行目のＯＮ指示文によって配列Ａとの間の整列関係が指定されていて、Ａの分散との組合せの効果により、Ｌ１の反復実行のうちどの部分範囲がどのプロセッサで実行されるべきかが指定されている。より一般的には、ＨＰＦ言語のサポートには、多次元ループの整列と分散、ｂｌｏｃｋ以外の分散種別（ｃｙｃｌｉｃ、ｉｎｄｉｒｅｃｔなど）、重複マッピング、縮退マッピング、袖（シャドウ）付き分散などや、プロセッサ台数や分散方法が不定の場合や可変の場合も考慮に入れる必要がある。
【０００９】
ＶＰＰ  ＦｏｒｔｒａｎでもＨＰＦの整列と分散に似た概念でデータとループのマッピングを記述することができる。ＯｐｅｎＭＰはループの分割にＨＰＦの分散と同じような考え方がある。自動並列化コンパイラによって配列とループの相関関係を解析した結果は、一般に図６と同じようなツリー状またはグラフ状の整列関係で表現できると考えられる。
【００１０】
こういった表現のバリエーションの豊富さは、記述言語ではプログラマの表現の自由度となるが、コンパイラにとっては解析を難しくしている。変数のローカル性や通信の削減に関する研究は古くからあり、論理的には多くの問題が解決しているが、それにも関わらず実際に商用化されているコンパイラで実プログラムに対して十分な性能が出ない場合があるのは、そのバリエーションに対して十分に対応し切れていないためと言える。
【００１１】
例えば、整列のパターンを線形な変換ｉ→ａｉ＋ｂ（ａ、ｂは定数）に限定すれば、多段の整列を結合するには線形変換の合成でよい、ということは論理的に知られていても、図５の１３行目のＣ（Ｉ−１）の参照について他プロセッサからの通信が必要か、ということをコンパイラが自動的に判定するのはそう簡単ではない。より難しいケースが多くあることを考えると、実プログラムで起り得るバリエーションのすべてに対応することは事実上できないことが分かる。コンパイラは重点的にサポート強化したパターン以外については、効率は良くないが動作保証する汎用的な処理に落すことが多い。通信が必要でないと判断できない場合には、通信があるかもしれないと考えたコードを生成することになる。その場合には、実行時に通信の必要性を判断することになるので、たとえ結果的に通信が不要であっても、通信がないと最初から分かっていた場合のアクセス（Ｌｏａｄ命令１回）に対して数倍〜数百倍のコストが掛かることがある。このようなアクセスを多発すれば、致命的な性能低下を招くことになる。
【００１２】
このようなコンパイラの未熟さを補う手段として、ＨＰＦの拡張仕様であるＨＰＦ／ＪＡでは、ローカルアクセス可能であることをコンパイラに知らせるためのＬＯＣＡＬ指示文を持つ。しかしそのような低水準の記述を必須とすることは、プログラマにとっては大きな負担であり、上述の方法２〜４のような場合にはプログラマの負担を軽減するという趣旨から考えて望ましくない。
【００１３】
ここまで、並列処理に係わる技術的背景を説明した。次にこれらに関連して並列処理の分野で使用される技術用語について説明する。
【００１４】
・配列データの分散
配列データの実体を要素毎に分割し、複数のプロセッサに割り当てることを言う。      
【００１５】
配列要素とプロセッサとの対応は分散の種類による。配列データのことを変数とも      言う。
【００１６】
・実行ループの分散
実行ループの反復実行を複数のプロセッサに分けて割り当てることを言う。ループ      インデックスとプロセッサとの対応は分散の種類による。ここでは実行ループを単      にループとも言う場合もある。
【００１７】
・分散の種類（ｂｌｏｃｋ、ｃｙｃｌｉｃ、不均等ｂｌｏｃｋ、ｂｌｏｃｋ−ｃｙｃｌ    ｉｃ、不規則）
ＨＰＦ言語仕様、ＯｐｅｎＭＰ言語仕様のそれぞれ以下の書式で定義される機能に    対応する。図７に３０要素を４プロセッサに分割する例を示している。
【００１８】
【表１】
2005084939.tif 000003
[*1]Ｗはプロセッサ数と同じ長さの整数型の一次元配列であり、各プロセッサに割り        当てるインデックスの大きさを表す。
【００１９】
[*2]Ｍはインデックス数と同じ長さの整数型の一次元配列であり、各インデックスに        対応するプロセッサ番号を表す。
【００２０】
・テンプレート
配列要素やループの反復をプロセッサに分散するとき、仲介となる仮想的な配列。      
【００２１】
ＨＰＦの言語仕様（非特許文献５、６）で定義されていて、ＶＰＰ  Ｆｏｒｔｒａｎ    のインデックス（非特許文献４）の概念にも近い。テンプレートは、図７に示した分    散方法のいずれかでプロセッサと対応づけられる。変数やループはテンプレートに対    して整列することができる。多次元テンプレートは、変数の多次元分割や、多重ルー    プの分割に対応する。
【００２２】
・整列
Ａの第ｄ次元がＢの第ｅ次元に整列するとは、Ａの第ｄ次元のインデックスｉと、    Ｂの第ｅ次元のインデックスｊの間に線形の関係
ｊ＝ｍｉ＋ｎ（ｍ，ｎは整数、ｍ≠０）
で対応付けがあり、対応するインデックスを持つＡとＢの要素が同じプロセッサに割    り当てられるように分散されることを言う。単に、ＡがＢに整列するとも言う。ＨＰ    Ｆでは配列データから配列データ、配列データからテンプレート、ループから配列デ    ータへの整列が表現できる。ＶＰＰ  Ｆｏｒｔｒａｎでは、配列データからテンプレ    ート、ループからテンプレートへの整列が表現できる。ＯｐｅｎＭＰでは整列の表現    はないが、並列ループからテンプレートへ常にｍ＝１，ｎ＝０の整列があると思えば    よい。
【００２３】
・整列の係数、定数項
それぞれ、上記の式のｍ，ｎのこと。ｍの値が１以外であるとき、整列にストライ    ドがあると言う。
【００２４】
・恒等的な整列
係数が１、定数項が０の整列。
【００２５】
・プロセッサ
単一のＣＰＵを含む並列計算機の構成要素。分散メモリ型計算機では、プロセッサ    は各プロセッサに固有のメモリを含む。共有メモリ型計算機（ＳＭＰ）では、メモリ    はプロセッサ間で共有される。本明細書で言うプロセッサは、実際のハードウェアの    プロセッサとの対応関係を、サポートする言語仕様で定義されていてもよいし、任意    に決めてもよい。例えば、配列の昇順に並べて同じ位置のプロセッサは同じ仮想プロ    セッサと見なすこともできるし、別々の仮想プロセッサ群を表現するとみなすことも    できる。複数のプロセッサを物理的に一つのプロセッサに対応付けることもできる。      
【００２６】
・ローカルアクセス
プロセッサ間の通信を伴わないデータのアクセス。参照の場合にはアクセスするプ    ロセッサがそのデータを所有していることが条件であり、定義の場合には、それに加    えて、複製を持つすべてのプロセッサが同じ値を定義することが条件となる。分散さ    れていない変数（プロセッサに分割配置されず全要素のコピーが配置されている変数    ）は、分散されたＤＯループの中では、参照はローカルアクセスだが、定義はローカ    ルアクセスでない。
【非特許文献１】Message Passing Interface Forum 、[online ］、MPI Forum 、［平成1 5 年８月１日検索］、インターネット<http://www.mpi-forum.org/index.html>
【非特許文献２】OpenMP Fortran Application Program Interface Version 2.0, November 2000 、[online ］、OpenMP Architecture Review Board、［平成1 5 年８月１日検索］、インターネット<http://www.openmp.org/specs/mp-documents/fspec20.pdf>
【非特許文献３】OpenMP C/C++ Application Program Interface Version 1.0, October 1998、[online ］、OpenMP Architecture Review Board、［平成1 5 年８月１日検索］、インターネット<http://www.openmp.org/specs/mp-documents/cspec10.pdf>
【非特許文献４】岩下英俊、進藤達也、岡田信、「VPP Fortran:分散メモリ型並列計算機向けプログラミング言語」、情報処理学会論文誌、Vol.36、No.7．1995年
【非特許文献５】High Performance Fortran Forum. High Performance Language Specification   Version 2.0. 1997.
【非特許文献６】富士通，日立，日本電気訳、「High Performance Fortran 2.0公式マニュアル」、シュプリンガー・フェアラーク東京、ISBN4-431-70822-7 .1999 年、
【非特許文献７】HPF/JA Language Specification.Version 1.0, November 1999、[online ］、Japan Association for High Performance Fortran (JAHPF)、［平成1 5 年８月１日検索］、インターネット<http://www.hpfpc.org/jahpf/spec/hpfja-v10-eng.pdf>
【発明の開示】
【発明が解決しようとする課題】
【００２７】
データと計算についての、相互の整列関係の様々な表現の組合わせによって、扱うべき対象のバリエーションが膨大になっている。そのため、コンパイラの開発コストが大きくなり、また、最適化し切れず効率の悪い汎用的な処理方法を残してしまう。加えて、本来コンパイル時に行うことのできる判断を実行時に持ち越しがちになるため、パラメタを伝えるインタフェースも大きくなり、生成コードは大きく重いものとなる。そして、実行時の判断をライブラリで行うことも多くなるため、実行時ライブラリで扱うパターンが多くなり、そこでも開発コストの制約から性能低下を招くことが多い。全体として、対応バリエーションの多さから大きなシステムとなりがちであり、開発コストが大きく、メンテナンスや改善が困難になる。
【００２８】
本発明は、データと計算との相互の整列関係のバリエーションをなくすこと、即ち、ある一定の標準形に正規化することにより、コンパイル時の判断を容易にしてコンパイル時に判断できるものを多くし、実行時のオーバヘッドを下げ、必要なライブラリを小さくし、全体として開発コストを下げると同時に実行時性能を向上させるものである。また、正規化の効果として、コンパイル時の判断が容易になったために、ローカルアクセスの検出を実現している。
【課題を解決するための手段】
【００２９】
本発明は、データと計算との相互の整列関係のバリエーションをなくすこと、すなわち、ある一定の標準形に正規化することにより、コンパイル時の判断を容易にしてコンパイル時に判断できるものを多くし、実行時のオーバヘッドを下げ、必要なライブラリを小さくし、全体として開発コストを下げると同時に実行時性能を向上させるものである。また、正規化の効果として、コンパイル時の判断が容易になったために、ローカルアクセスの検出を実現している。
【００３０】
個々の発明は以下のように構成される。
（１）第１の発明
第１の発明は、並列処理プログラムのコード（ソースコード）に対して、直接または間接的に互いに整列関係のある変数と実行ループとを、全てテンプレートに整列するよう、即ち一段の整列になるよう正規化を行うプログラムである。
【００３１】
その原理を図１を用いて説明する。第１の発明は、図１に示すように対象の並列処理プロセッサのソースコードに対して、プロセッサ形状変換手順１１、テンプレート形状変換手順１２、テンプレート整列化手順１３および直接整列化手順１４に基づいて正規化を施すものである。各手順は次のようにして正規化する。
【００３２】
プロセッサ形状変換手順１１は、ソースコード中に書かれているプロセッサ群の次元の上下限値に対して所定の正規化を行うものである。例えば、プロセッサ指示文で宣言される次元の下限値を「０」とするように正規化する。
【００３３】
テンプレート形状変換手順１２は、プロセッサ群と同様にソースコード中に書かれている第１のテンプレートの次元の上下限値に対して所定の正規化を行うものである。
【００３４】
テンプレート整列化手順１３は、プロセッサに直接分散されている変数（配列データ）と実行ループに対して第２のテンプレートを生成し、そのテンプレートに変数と実行ループを整列させることを行う。生成した第２のテンプレートの次元は、テンプレート形状変換手順１２で行った所定の方法による正規化がなされたものである。
【００３５】
直接整列化手順１４は、第１または第２のテンプレートに整列した変数に整列する他の変数または実行ループを直接に整列させるようにすることを行う。即ち、対象となる変数および実行ループは、間接的に第１または第２のテンプレートに整列している状態から直接に整列するようにするものである。
【００３６】
上記の構成により、対象のソースコードはプロセッサ形状変換手順１１とテンプレート形状変換手順１２により宣言されたプロセッサ群と第１のテンプレートの次元が変換され、続いてそのソースコードはテンプレート整列化手順１３により生成した第２のテンプレート宣言文が追加され、変数と実行ループの整列文が追加される。更に、ソースコードは直接整列化手順１４により間接整列している変数と実行ループが直接整列するように変換されたものとなる。
【００３７】
これにより、宣言されたプロセッサおよびテンプレート（第１のテンプレート）の次元の上下限値は正規化されると共に、変数および実行ループはテンプレート（第１または第２のテンプレート）に直接整列されるように正規化される。  
【００３８】
対象の並列処理プロセッサのソースコードは、ＨＰＦなどの並列言語で表現されたものであってもよく、自動並列化コンパイラや開発支援ツールを用いて並列化されたコードの内部表現であってもよい。
（２）第２の発明
第２の発明は、並列処理プログラムのコードに対して、テンプレートに整列している変数の形状と整列およびアクセスの正規化を図るプログラムである。図２はその原理を示すもので、変数形状変換手順２１、第１の整列変換手順２２および第１の添字式変換手順２３からなる。
【００３９】
変数形状変換手順２１は、テンプレートに整列している変数の次元の上下限値を、そのテンプレートの次元の上下限値と等しい値に変換することを行う。即ち、テンプレートの次元に合わせる。
【００４０】
第１の整列変換手順２２は、前記変数のテンプレートへの整列を恒等的な形式に変換する。即ち、テンプレートへの整列が係数１、定数項０の形に変換する。
【００４１】
第１の添字式変換手順２３は、前記変数のアクセスにおいて引用する添字式を所定の変換規則で変換する。例えば、第１の整列変換手順２２における変換前の整列の係数および定数項がそれぞれｍ、ｎであったとき、添字式ｓを（ｍｓ＋ｎ）に変換する。
【００４２】
上記の構成により、対象のソースコードは変数形状変換手順２１によりテンプレートに整列している変数の宣言された次元の上下限値はテンプレートの次元の上下限値と等しくなるよう変換され、続いてそのソースコードは第１の整列変換手順２２により変数の整列が恒等式になるよう変換される。更に、ソースコードは第１の添字式変換手順２３により変数のアクセスに対する添字式が変換されたものとなる。これにより、テンプレートに整列している変数は正規化される。
（３）第３の発明
第３の発明は、並列処理プログラムのコードに対して、テンプレートに整列している実行ループのループ変数と整列およびアクセスの正規化を図るプログラムである。図３はその原理を示すもので、ループパラメタ変換手順３１、第２の整列変換手順３２および第２の添字式変換手順３３からなる。
【００４３】
ループパラメタ変換手順３１は、テンプレートに整列している実行ループのループ変数である初期値、終値および増分を整列の係数と定数項の値に基づいて変換する。例えば、前述のように整列の係数ｍと定数項ｎを基に、初期値Ｉ１、終値Ｉ２、増分Ｉ３をそれぞれ（ｍＩ１＋ｎ）、（ｍＩ２＋ｎ）、ｍＩ３のように変換する。このループ変数は、Ｆｏｒｔｒａｎ言語のＤＯ文のループパラメタ相当のものである。
【００４４】
第２の整列変換手順３２は、前記実行ループのテンプレートへの整列を恒等的な形式に変換する。即ち、テンプレートへの整列が係数１、定数項０の形に変換する。
【００４５】
第２の添字式変換手順３３は、前記実行ループのアクセスにおいて引用する添字式を所定の変換規則で変換する。例えば、変換規則は第２の発明の第１の添字式変換手順２３で示すものである。
【００４６】
上記の構成により、対象のソースコードはループパラメタ変換手順３１によりテンプレートに整列している実行ループのループ変数が変換され、続いてそのソースコードは第２の整列変換手順３２により実行ループの整列が恒等式になるよう変換される。更に、ソースコードは第２の添字式変換手順３３により実行ループのアクセスに対する添字式が変換されたものとなる。
（４）第４の発明
第４の発明は、並列処理プログラムのコードに対して、実行ループ中の変数に対するアクセスがローカルアクセスであることを判定して、そのアクセス要素に識別情報の付与を行うプログラムである。図４はその原理を示すもので、ローカルアクセス判定手順４１および識別情報付与手順４２からなる。
【００４７】
ローカルアクセス判定手順４１は、並列処理言語要素が正規化されているソースコード中の同一のテンプレートに整列している実行ループと変数の組を対象としてその実行ループの中の変数に対するアクセスがローカルアクセスであるかどうかを判定する。ここで、並列処理言語要素とは並列処理プログラムで宣言されるプロセッサやテンプレート、変数および実行ループである。そしてそれらは前述の第１〜第３の発明に示される正規化が行われているものである。ローカルアクセスと判定されるのは、例えば値を参照するが定義しないアクセスで、アクセスとループとがある整合条件を満たす場合などである。
【００４８】
識別情報付与手順４２は、ローカルアクセスと判定した実行ループと変数のアクセスのアクセス要素に対して識別情報を付与する。アクセス要素とは、アクセスの対象となるもので、例えばアクセス変数ｉを伴う配列データであったり、ｉそのものであったりする。また、識別情報の付与は、例えばコードを構成するテキストに下線を施すとか、該当のテキストに対応して内部に何らかの情報を持つようにしてもよい。要は、コンパイル時にローカルアクセスであることが認識できればよい。
（５）第５の発明
第５の発明は、並列処理プログラムのコードに対して、直接または間接的に互いに整列関係のある変数と実行ループとを、全てテンプレートに整列するよう正規化を行う方法である。
【発明の効果】
【００４９】
本発明は、分散の方法（ｂｌｏｃｋ，ｃｙｃｌｉｃなど）や分散先のプロセッサ数がコンパイル時に不明である場合にも実行時に可変である場合にも適用できるという特徴がある。個々の発明の効果は下記に示すとおりで、第１〜第４の発明はプログラムの提供、第５の発明は方法の提供が可能になる。
【００５０】
第１の発明では、テンプレートの共通化と、整列の一段化により、様々な表現が可能な等価な整列関係が一通りの分かりやすい表現に正規化される。そのため、コンパイラによるデータ間、ループ間、およびデータとループの間の整列関係の解析処理が単純化かつ一本化され、最適化やコード生成が容易になる。
【００５１】
第２の発明では、同じテンプレートに対して整列する配列データの整合性の確認が容易になるため、最適化や自動並列化が促進される。
【００５２】
第３の発明では、同じテンプレートに対して整列するループの整合性の確認が容易になるため、最適化や自動並列化が促進される。第２の発明との組合せにより、データとループの整合性の検出がより容易になるため、様々な最適化が促進される。
【００５３】
第４の発明では、ローカルアクセスを取りこぼし少なく検出することができる。
【００５４】
第５の発明では、第１の発明の方法の提供ができる。
【発明を実施するための最良の形態】
【００５５】
並列処理プログラムのソースコードを解析して自動的に正規化が行えるように実現した。
【実施例１】
【００５６】
具体的な実施例の説明の前に、ここでの数学記号を以下のように定義する。なお、この定義は以降の実施例２〜４においても共通である。
【００５７】
【数１】
2005084939.tif 000004
文字を以下のように定義する。ここでＴはテンプレートとする。Ｔの各次元はそれぞれプロセッサ群の１つの次元に沿って分散される。なお、この定義は以降の実施例２〜４においても共通である。
【００５８】
Ｎ    Ｔのある次元の寸法。例えば、ＨＰＦプログラムで、
!HPF$ PROCESSORS Q(4,6) 
!HPF$ TEMPLATE U(100,0:29)
!HPF$ DISTRIBUTE U(block,cyclic) ONTO Q 
とある場合、本明細書で言うテンプレートの形状は［１：１００，０：２９            ］であり、Ｎの値は１次元目に着目するとき１００、２次元目に着目すると            き３０となる。
【００５９】
Ｐ    Ｔの分散先プロセッサ群の、Ｔのある次元に対応する次元の寸法。分散先プ            ロセッサ群が一次元配列の場合には、プロセッサ群を構成するプロセッサの            数となる。例えば、上の例で、Ｐの値はＴの１次元目に着目するとき４、Ｔ            の２次元目に着目するとき６となる。
【００６０】
ｐ    Ｔの分散先プロセッサ群の、Ｔのある次元に対応する次元方向に沿った、プ            ログラムを実行するプロセッサの要素番号（０≦ｐ＜Ｐ）。例えば上の例で            、プロセッサＱ（１，３）にとってのｐの値は、Ｔの１次元に着目するとき            １、Ｔの２次元目に着目するとき３となる。ｐの値は実行時にライブラリ呼            出しなどによって得られる。
【００６１】
ｗ    ｂｌｏｃｋ分散またはｂｌｏｃｋ−ｃｙｃｌｉｃ分散におけるｂｌｏｃｋ幅            。ｂｌｏｃｋ分散でプログラマの指定のない場合には、ＨＰＦとＯｐｅｎＭ            Ｐでは
【００６２】
【数２】
2005084939.tif 000005
と定義される。
【００６３】
Ｗ    不均等ｂｌｏｃｋ分散におけるブロック幅配列。
【００６４】
Ｗ（ｐ）（０≦ｐ＜Ｐ）はプロセッサｐに割り当てられるインデックスの幅            となる。Ｗ（０）＝Ｗ（１）＝．．．＝Ｗ（Ｐ−１）＝ｗであるとき幅ｗの            ｂｌｏｃｋ分散を意味する。
【００６５】
Ｍ    不規則分散における正規化されたマッピング配列。
【００６６】
Ｍ（ｋ）（０≦ｋ＜Ｎ）はＴの各要素に対応するプロセッサの要素番号であ            り、0 ≦Ｍ（ｋ）＜Ｐとなる。
【００６７】
実施例１の説明に入る。実施例１は、共通化したテンプレートに変数と実行ループを一段に整列することにより、整列関係を一通りに正規化するものである。この正規化は分散の正規化、整列の正規化、テンプレート共通化の３つのフェーズについて行うもので、そのフローを図８を用いて説明する。
（１）分散の正規化
（１−１）まず、最初の分散の正規化についてはすべての分散について、分散の種類に応じて分散のパラメタを正規化する。
【００６８】
・ｂｌｏｃｋ分散で、ブロック幅が指定されていない場合、ブロック幅ｗを計算する式    またはその結果の値を求めて保持する。計算式は以下の通りである。
【００６９】
【数３】
2005084939.tif 000006
・不均等ｂｌｏｃｋ分散の場合、ブロック幅配列Ｗ（０：Ｐ−１）の領域を確保し値を    設定する。
【００７０】
・不規則分散の場合、マッピング配列Ｍ（０：Ｎ−１）の領域を確保し値を設定する。      
【００７１】
以上の処理は必須ではない（Ｓ１０１）。
【００７２】
（１−２）すべてのプロセッサ群について、各次元の上下限を正規化する。すなわち、プロセッサ群のある次元の下限がＰ１、上限がＰ２のとき、それぞれ０と（Ｐ２−Ｐ１）に変換する。同時に、その次元に分散する不規則分散がある場合、Ｍの各要素Ｍ（ｋ）（０≦ｋ＜Ｎ）の値を、（Ｍ（ｋ）−Ｐ１）に変換する（Ｓ１０２）。
（２）整列の正規化
（２−１）テンプレートに分散されていない次元があるとき、その次元でテンプレートを縮退する。すなわち、ｄ次元目が分散されていないとすると：
・テンプレートの形状のｄ次元目をなくして１次元縮退する。
【００７３】
・テンプレートとプロセッサのｄ次元目以降の対応付けを維持する。
【００７４】
・テンプレートに整列しているすべての変数について、テンプレートのｄ次元目への整    列を抹消する（Ｓ１０３）
（２−２）テンプレートの各次元の上下限を正規化する。すなわち、テンプレートのある次元の下限値、上限値がそれぞれＮ１，Ｎ２のとき：
・テンプレートの下限値と上限値を、それぞれ０，（Ｎ２−Ｎ１）に設定する。
【００７５】
・テンプレートに対して整列されている変数は、その定数項ｎを（ｎ−Ｎ１）に変換す    る（Ｓ１０４）
（２−３）プロセッサ群に直接分散されている変数は、分散されている各次元について、下限値を０とするテンプレートを生成し、そのテンプレートへの整列に変換する。すなわち、変数のある分散されている次元の下限値、上限値がそれぞれＮ１，Ｎ２のとき：
・下限値、上限値がそれぞれ０，（Ｎ２−Ｎ１）のテンプレートを生成する。プロセッ    サへの分散の方法は、変数のその次元の分散の方法から継承する。
【００７６】
・変数をテンプレートに対して係数1 、定数項（−Ｎ１）で整列させる（Ｓ１０５）。      
【００７７】
（２−４）プロセッサ群に直接分散されているループは、その分散を、下限値を0 とするテンプレートへの整列に変換する。すなわち、ループの初期値、終値、増分がそれぞれＩ１，Ｉ２，Ｉ３のとき：
・下限値、上限値がそれぞれ０，Ｉ２−Ｉ１のテンプレートを生成する。プロセッサへ    の分散の方法は、ループの分散の方法から継承する。
【００７８】
・ループをテンプレートに対して係数1 、定数項（−Ｉ１）で整列させる（Ｓ１０６）    。
【００７９】
（２−５）変数Ｘに対して整列している変数またはループＹは、整列の合成を繰り返し計算し、ＹからテンプレートＴへの直接の整列に変換する。整列は線形結合によって合成することができる。ＸがＴへ係数ａ、定数項ｂで整列し、ＹがＸへ係数ｃ、定数項ｄで整列しているとすると、ＹからＴへの整列は以下のようになる。
【００８０】
ａ（ｃｉ＋ｄ）＋ｂ＝ａｃｉ＋ａｄ＋ｂ
即ち、係数ａｃ、定数項ａｄ＋ｂとなる。以下のアルゴリズムで、テンプレートに対して間接的に整列するすべての変数とループを、テンプレートへの直接の整列に変換することができる。
【００８１】
１）テンプレートに直接整列している変数とループを検出し、その集合をＳ１とする。      
【００８２】
２）Ｓ１の要素に直接整列している変数とループを検出し、その集合をＳ２とする。
【００８３】
３）Ｓ２が空であれば終了する。
【００８４】
４）Ｓ２に属す全ての変数とループについて、テンプレートへの直接整列に変換する。      
【００８５】
５）Ｓ１にＳ２を設定し、２）へ飛ぶ（Ｓ１０７）。
（３）テンプレート共通化  
以下の条件を満たすテンプレートは出来るだけ共通化し、それらに整列している変数とループは共通化したテンプレートに対して整列するように変換する。
【００８６】
・分散先のプロセッサ群と次元が一致する。
【００８７】
・分散の種類と属性が一致する。属性とは、ブロック幅ｗ、ブロック幅配列Ｗ、および    マッピング配列Ｍである。
【００８８】
共通化するテンプレートの上限が一致していない場合、大きい方の値を取るか、それを超える任意の値に変換する。ただしｂｌｏｃｋ分散の場合には、（Ｐｗ−１）を超える値に変換してはならない。不均等ｂｌｏｃｋ分散と不規則分散の場合には、言語仕様から必ずテンプレートの上限は一致する。このテンプレート共通化は必須ではない（Ｓ１０８）。
【００８９】
以上、基本のフローについて説明した。具体的に並列処理プログラムのソースコードを基にこのフローに沿って説明する。ソースコードは前述の図５を用いる。ここではＨＰＦ言語で表現したが、同様な内容を表現する自動並列化コンパイラや開発支援ツールの出力であってもよい。入力プログラムは、図６に示す整列関係を表現している。すなわち、配列ＡとＢはプロセッサ群への分散が指定されていて、配列ＣとＤはＡへの整列、配列ＦはＢへの整列が指定されている。配列Ｅは別の２次元プロセッサ群への分散が指定されている。ループＬ１とＬ２は、ＯＮ  ＨＯＭＥ指示文によって、それぞれ配列ＡとＤへの整列が指定されている。
【００９０】
まず、変数Ａ，ＢとＥの１次元目と２次元目のｂｌｏｃｋ分散の幅を、それぞれ以下のように計算する。
【００９１】
【数４】
2005084939.tif 000007
続いて、プロセッサＰの形状（１：４）を（０：３）に正規化する。プロセッサＰＰの形状はすでに正規化されているので変換の必要はない。
【００９２】
以上で、分散の正規化としてのＳ１０１、Ｓ１０２の処理を行ったことになる。この結果として得られるコードをＨＰＦ言語で表現したものを図９に示す。即ち、プロセッサＰとプロセッサに分散している変数Ａ、Ｂ及びＥのブロックの次元が変換されている。図９の太字斜体で示した部分は、そのステップで生成または変更されたコードである。以降同様に該当するステップで変更された部分を太字斜体で示す。
【００９３】
次に、整列正規化の処理を行うが、Ｓ１０３及びＳ１０４は該当分がないのでスキップし、プロセッサ群に直接分散されている変数Ａ，Ｂ，Ｅについて次のことを行う。
【００９４】
・変数Ａに対してテンプレートＴ１を生成し、その分散と、変数ＡからＴ１への整列を    記録する。Ｔ１の下限は０、上限は（（Ａの上限値）−（Ａの下限値））で２９、分    散方法はｂｌｏｃｋ、分散幅は８、整列は係数１、定数項（−１）となる。
【００９５】
・変数Ｂに対して同様にテンプレートＴ２を生成する。Ｔ２のパラメタはＴ１と同じで    、下限は０、上限は２９、分散方法はｂｌｏｃｋ、分散幅は８、整列は係数１、定数    項（−１）となる。
【００９６】
・変数Ｅの１次元目と２次元目は、それぞれプロセッサＰＰの１次元目と２次元目に直    接分散しているので、テンプレートＴ３を生成し、各次元の分散と整列を記録する。      
【００９７】
Ｔ３の１次元目の下限は０、上限は（（Ｅの第１次元の上限値）−（Ｅの第１次元の    下限値））で２９、分散方法はｂｌｏｃｋ、分散幅は１５、整列は係数１、定数項（    −１）となる。Ｔ３の２次元目は、下限値０、上限値２９、分散方法はｂｌｏｃｋ、    分散幅は１５、整列は係数１、定数項（−１）となる。Ｔ３はＰＰに対して分散され    る。
【００９８】
以上でＳ１０５の処理を終了し、Ｓ１０６は該当する内容はないのでＳ１０７の処理を行う。変数Ｃ，Ｄ，ＦおよびループＬ１，Ｌ２は、テンプレートに直接整列せず、他の変数に対して整列している。これらは以下のように、テンプレートへの直接の整列に変換される。
【００９９】
１）テンプレートＴ１，Ｔ２，Ｔ３に整列している変数またはループの集合Ｓ１は、｛      Ａ，Ｂ，Ｅ｝
２）Ｓ１の要素に直接整列している変数またはループの集合Ｓ２は、｛Ｃ，Ｄ，Ｆ，Ｌ      １｝
３）Ｓ２は空でないので４）へ。
【０１００】
４）Ｃ，Ｄ，Ｆ，Ｌ１について、テンプレートへの整列をそれぞれ以下のように求めら      れる。
【０１０１】
【表２】
2005084939.tif 000008
５）Ｓ１に｛Ｃ，Ｄ，Ｆ，Ｌ１｝を設定し、２）へ。
【０１０２】
２）Ｓ１の要素に直接整列している変数またはループの集合Ｓ２は、｛Ｌ２｝
３）Ｓ２は空でないので４）へ。
【０１０３】
４）Ｌ２について、テンプレートへの整列は以下のように求められる。
【０１０４】
【表３】
2005084939.tif 000009
５）Ｓ１｛Ｌ２｝設定し、２）へ。
【０１０５】
２）Ｓ１に属す変数に直接整列している変数は、存在しない。Ｓ２は空となる。
【０１０６】
３）Ｓ２は空でなので終了する。
【０１０７】
図１０は整列の正規化のステップによって生成されたテンプレートＴ１，Ｔ２，Ｔ３と変数・ループの整列関係を図示したものである。また、その結果を図１１に示す。
【０１０８】
最後に、テンプレート共通化のステップとして４つのテンプレートのうち、Ｔ１とＴ２の組はプロセッサ群、プロセッサの次元、分散の種類、およびブロック幅が一致するので、共通化できる条件を満たす。Ｔ１とＴ２の大きさは一致しているので、単純にＴ２の参照をＴ１に置換え、Ｔ２を抹消する。
【０１０９】
テンプレート共通化の結果を図１２に示す。
【実施例２】
【０１１０】
実施例２は、第２の発明に示されるデータの正規化の実施例であり、その処理フローを図１３に示す。まず入力コードの変数がテンプレートに整列しているかどうかをチェックし、テンプレートに整列している変数であれば整列係数項（ｍ）と定数項（ｎ）を取得する。次に、Ｔに整列している次元の宣言上下限を、Ｔの宣言上下限に置き換え、Ｔへの整列を恒等的（ｉｄｅｎｔｉｃａｌ）な形に変換する。即ち、係数１、定数項０とする。そしてその変数の全てのアクセスについて、Ｔに整列している次元の添字式ｓを（ｍｓ＋ｎ）に変換する。以上を全ての変数に対して実施する（Ｓ２０１〜Ｓ２０５）。
【０１１１】
図１２に引き続いて実施例２の処理を行うものとして、ソースコードを基に具体的に説明する。
【０１１２】
Ｔ１に整列する変数Ａ，Ｂ，Ｃ，Ｄ，Ｆについて、以下の処理を行う。
【０１１３】
１）Ｔ１に整列している次元の上下限をテンプレートＴ１の上下限と一致させる。結果      として、図１４に示すように使用されない領域を含む連続領域を確保することにな      る。
【０１１４】
２）テンプレートＴ１への整列を恒等的な形に変換する。
【０１１５】
３）プログラム内でこれらの変数のすべての引用について、添字式を次の変換規則で変      換する。
【０１１６】
Ａ（ｓ）→Ａ（ｓ−１）
Ｂ（ｓ）→Ｂ（ｓ−１）
Ｃ（ｓ）→Ｃ（ｓ）
Ｄ（ｓ）→Ｄ（２＊ｓ−１）
Ｆ（ｓ１，ｓ２）→Ｆ（ｓ１，ｓ２−１）
これらの変換の結果を図１５の太字斜体で示す。
【０１１７】
同様に、Ｔ３に整列する変数Ｅについても、上下限、添字式、整列を変換する。これらの変換の結果を図１６の太字斜体に示す。添字式の変換は
Ｅ（ｓ１，ｓ２）→Ｅ（ｓ１−１，ｓ２−１）
である。
【０１１８】
なお、図１４に見られるように、変数Ｄのような場合はストライドを持つ割付けとなり、単純な実装を行うとメモリの無駄を生じることになるが、以下の理由により実質的には問題とならない。
【０１１９】
・変数がＦｏｒｔｒａｎ９０のポインタ変数である場合、その変数に対する割付けは    行われない。変数がサブプログラムの仮引数である場合も、割付けが行われないこと    が多い。
【０１２０】
・それら以外の変数では、ストライド付きの整列が必要となる例は少ない。
【０１２１】
本実施例２により、同一のテンプレートに整列する変数（配列データ）の自動並列化がよりやり易くなる。例えば、図１６の２３行目のＡとＤのアクセスは、変換前には整合性の判別が難しいが、変換後は添字式の一致を見るだけで整合していることが確認できる。この情報により、例えば仮にループＬ２の並列化がプログラマの記述によって指定されていない場合でも、内部で通信を生成させないようなＡとＤに整合するループの自動並列化が可能となる。
【実施例３】
【０１２２】
実施例３は、第３の発明に示されるループの正規化の実施例であり、その処理フローを図１７に示す。
【０１２３】
まず、実行ループがテンプレートに整列しているかどうかを判断し、整列している実行ループについて、以下の処理を行う。
【０１２４】
１）実行ループの整列が係数ｍ、定数項ｎであるとき、対象ループの初期値Ｉ１、終値      Ｉ２、増分Ｉ３を、それぞれ、（ｍＩ１＋ｎ）、（ｍＩ２＋ｎ）、ｍＩ３に変換す      る。
【０１２５】
２）Ｔへの整列を恒等的（ｉｄｅｎｔｉｃａｌ）な形（即ち、ｍ＝１，ｎ＝０）に変換      する。
【０１２６】
３）そのループ内のループ変数I の引用を（Ｉ−ｎ）／ｍに変換する。
【０１２７】
多重ループが１つの多次元テンプレートに対して整列している場合も同様である（Ｓ３０１〜Ｓ３０４）。
【０１２８】
このフローを実際のソースコードへの適用を示すために、図１６のソースコードを例に説明する。上記の１）〜３）に対応して下記の１）〜３）に示すように変換する。
【０１２９】
１）ループＬ１は、初期値２、終値２９、増分１で、整列の係数１、定数項（−１）な      ので、初期値を１＊２−１＝１、終値を１＊２９−１＝２８、増分を１＊１＝１に      変換する。ループＬ２は、初期値１、終値１０、増分１で、整列の係数２、定数項      （−１）なので、初期値を２＊１−１＝１、終値を２＊１０−１＝１９、増分を２      ＊１＝２に変換する。これらの変換は、図１８に示すように、整列関係を変えない      でインデックスをテンプレートのインデックスに一致させることに相当する。
【０１３０】
２）テンプレートＴ１への整列を恒等的な形に変換する。
【０１３１】
３）Ｌ１内のＤＯ変数ＩとＬ２内のＤＯ変数Ｋは、それそれ次に示す変換を行う。
【０１３２】
Ｉ→Ｉ＋１、    Ｋ→（Ｋ＋１）／２
上記により変換したソースコードは図１９の太字斜体に示す通りである。
【０１３３】
本実施例３により、同一のテンプレートに整列する実行ループの自動並列化が促進される。例えば、図１９のプログラムで、ループＬ１とＬ２についてフュージョン（ｌｏｏｐｆｕｓｉｏｎ）の最適化を行おうとする場合、図２０に示すように、単純にＫ→１と置換して結合すれば可能である。このような変形が可能だと判断するためには、２つのループの整列の整合性と、ループ間を跨ぐデータ依存関係（この例では変数Ａで生じている）が正確に読み取れる必要があるが、本実施例３による正規化を施した後ではそれらは容易である。本実施例３による変換を用いず、図５や図１６に示すプログラムから直接ループフュージョンを行うことは容易ではない。
【実施例４】
【０１３４】
実施例４は、第４の発明に示されるローカルアクセス検出の実施例であり、具体的にはｍ次元テンプレートＴに整列している変数のアクセスについて、以下のいずれかの場合、そのアクセスはローカルアクセス可能であると判断し、その旨を示す印を付けることを行う。図２１にその処理フローを示す。
【０１３５】
まず、変数のアクセスが、それを取り囲むループとの間で整合条件を満たしているかどうかを判定する。この変数が次元を持たない場合（スカラ変数）やテンプレートに整列していない場合には、常にこの条件を満たす。テンプレートに整列している場合には、その次元の添字式がループ変数であり、且つそのループ変数に対応するループが、変数のその次元と同じテンプレートの同じ次元に整列されている場合に限って、整合条件を満たすと判断する（Ｓ４０１〜Ｓ４０５）。
【０１３６】
アクセスが値の定義を含む場合には、前記アクセスとループの整合条件に加えて、そのアクセスを取り囲むループに変数の整合先と異なる整合先を持つループがないことを確認する必要がある（Ｓ４０６、Ｓ４０７）。
【０１３７】
これらの条件を全て満たしたアクセスは、ローカルアクセスであると判断し、その旨を示す印を付ける（Ｓ４０８）。
【０１３８】
これらの処理は全ての変数およびその変数の全てのアクセスに対して行う。
【０１３９】
図２２は、ローカルと判定されたアクセスの変数名を下線付きで示している。例えば１２行目では、ＩとＮとＡ（Ｉ）がローカルアクセスである。ループＬ１の中で、Ｂ（Ｎ−１）とＣ（Ｉ＋１）は分散次元がＤＯ変数でないためローカルアクセスにできない。Ｅ（Ｉ，２９−Ｉ）はＤＯループとテンプレートが異なるためローカルアクセスにできない。Ｌ１の中のＤＯ変数Ｊは、入力プログラム図５の９行目のｎｅｗ指定により、ローカルアクセスであることがプログラマによって宣言されている。
【０１４０】
本実施例４で説明したようにローカルアクセスを確実に検出できるので、コンパイル時に通信不要と判断でき、性能を低下させることはない。
【０１４１】
なお、本実施例１〜４の入力プログラムの媒体は、ディスクなどに保存されたテキストファイルやバイナリファイルでもよく、コンパイラの内部構造、例えばＣ言語の構造体が相互にリンクされたような表現形式であってもよい。出力もまたプログラムコードであり、媒体はテキストファイルやバイナリファイルでもよく、コンパイラの内部構造でもよい。
【０１４２】
また、本実施例における次元の上下限値に対する正規化処理は、下限値を０となるようにしたが、例えば１にするなど数学的に等価な異なる表現とすることも可能である。
（付記１）
並列処理プログラムのコード中におけるプロセッサ群の次元の上下限値を所定の値に変換するプロセッサ形状変換手順と、
前記コード中における第１のテンプレートの次元の上下限値を所定の値に変換するテンプレート形状変換手順と、
前記プロセッサ群に直接分散されている変数と実行ループのそれぞれに対して前記所定の変換による形状を持つ第２のテンプレートを生成し、該変数または該実行ループを該第２のテンプレートに整列させるテンプレート整列化手順と、
前記第１または第２のテンプレートに整列した変数に対して整列した他の変数と実行ループとを、該第１のまたは第２のテンプレートに直接に整列させる直接整列化手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。（１）
（付記２）
並列処理プログラムのコード中のテンプレートに整列している変数に対して、該変数の宣言された次元の上下限値を該テンプレートの次元の上下限値と等しい値に変換する変数形状変換手順と、
前記変数の前記テンプレートへの整列を、恒等的な形式に変換する第１の整列変換手順と、
前記変数のアクセスに対する添字式を所定の変換規則に基づいて変換する第１の添字式変換手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。（２）
（付記３）
並列処理プログラムのコード中のテンプレートに整列している実行ループに対して、該実行ループの整列の係数と定数とに基づいて該実行ループの初期値、終値、増分を変換するループパラメタ変換手順と、
前記実行ループの前記テンプレートへの整列を、恒等的な形式に変換する第２の整列変換手順と、
前記実行ループのアクセスに対する添字式を所定の変換規則に基づいて変換する第２の添字式変換手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。（３）
（付記４）
並列処理言語要素が正規化されている並列処理プログラムのコード中の、テンプレートに整列している実行ループの中での変数に対するアクセスが、ローカルアクセスであるか否かを判定するローカルアクセス判定手順と、
前記ローカルアクセスと判定された実行ループと変数とのアクセス要素に対して識別情報を付与する識別情報付与手順と
をコンピュータに実行させることを特徴とする並列処理正規化プログラム。（４）
（付記５）
並列処理プログラムのコード中におけるプロセッサ群の次元の上下限値を所定の値に変換するプロセッサ形状変換手順と、
前記コード中における第１のテンプレートの次元の上下限値を所定の値に変換するテンプレート形状変換手順と、
前記プロセッサ群に直接分散されている変数と実行ループのそれぞれに対して前記所定の変換による形状を持つ第２のテンプレートを生成し、該変数または該実行ループを該第２のテンプレートに整列させるテンプレート整列化手順と、
前記第１または第２のテンプレートに整列した変数に対して整列した他の変数と実行ループとを、該第１のまたは第２のテンプレートに直接に整列させる直接整列化手順と
を有することを特徴とする並列処理プログラムの正規化方法。（５）
（付記６）
並列処理プログラムのコード中におけるプロセッサ群の次元の上下限値を所定の値に変換するプロセッサ形状変換手順と、
前記コード中における第１のテンプレートの次元の上下限値を所定の値に変換するテンプレート形状変換手順と、
前記プロセッサ群に直接分散されている変数と実行ループのそれぞれに対して前記所定の変換による形状を持つ第２のテンプレートを生成し、該変数または該実行ループを該第２のテンプレートに整列させるテンプレート整列化手順と、
前記第１または第２のテンプレートに整列した変数に対して整列した他の変数と実行ループとを、該第１のまたは第２のテンプレートに直接に整列させる直接整列化手順と
をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
（付記７）
並列処理プログラムのコード中におけるプロセッサ群の次元の上下限値を所定の値に変換するプロセッサ形状変換手段と、
前記コード中における第１のテンプレートの次元の上下限値を所定の値に変換するテンプレート形状変換手段と、
前記プロセッサ群に直接分散されている変数と実行ループのそれぞれに対して前記所定の変換による形状を持つ第２のテンプレートを生成し、該変数または該実行ループを該第２のテンプレートに整列させるテンプレート整列化手段と、
前記第１または第２のテンプレートに整列した変数に対して整列した他の変数と実行ループとを、該第１のまたは第２のテンプレートに直接に整列させる直接整列化手段と
を有することを特徴とする並列処理プログラムの正規化装置。
【図面の簡単な説明】
【０１４３】
【図１】第１の発明の原理図である。
【図２】第２の発明の原理図である。
【図３】第３の発明の原理図である。
【図４】第４の発明の原理図である。
【図５】ＨＰＦプログラム（ソースコード）の例である。
【図６】配列データや実行ループの整列関係である。
【図７】分散の種類である。
【図８】実施例１のフローである。
【図９】実施例１のプロセッサと変数の次元の変換結果である。
【図１０】実施例１の生成したテンプレートと変数、実行ループの整列の様子である。
【図１１】実施例１の生成したテンプレートと変数、実行ループの整列結果である。
【図１２】実施例１のテンプレートを共通化した変換結果である。
【図１３】実施例２のフローである。
【図１４】実施例２の整列の様子（Ｔ１に対して）である。
【図１５】実施例２の変換結果（Ｔ１に対して）である。
【図１６】実施例２の変換結果（Ｔ３に対して）である。
【図１７】実施例３のフローである。
【図１８】実施例３の整列の様子である。
【図１９】実施例３の変換結果である。
【図２０】実施例３の結果を利用したｌｏｏｐ  ｆｕｓｉｏｎの例である。
【図２１】実施例４のフローである。
【図２２】実施例４の変換結果である。
【符号の説明】
【０１４４】
１１    プロセッサ形状変換手順
１２    テンプレート形状変換手順
１３    テンプレート整列化手順
１４    直接整列化手順
２１    変数形状変換手順
２２    第１の整列変換手順
２３    第１の添字式変換手順
３１    ループパラメタ変換手順
３２    第２の整列変換手順
３３    第２の添字式変換手順
４１    ローカルアクセス判定手順
４２    識別情報付与手順
【図１】
2005084939.tif 000010
【図２】
2005084939.tif 000011
【図３】
2005084939.tif 000012
【図４】
2005084939.tif 000013
【図５】
2005084939.tif 000014
【図６】
2005084939.tif 000015
【図７】
2005084939.tif 000016
【図８】
2005084939.tif 000017
【図９】
2005084939.tif 000018
【図１０】
2005084939.tif 000019
【図１１】
2005084939.tif 000020
【図１２】
2005084939.tif 000021
【図１３】
2005084939.tif 000022
【図１４】
2005084939.tif 000023
【図１５】
2005084939.tif 000024
【図１６】
2005084939.tif 000025
【図１７】
2005084939.tif 000026
【図１８】
2005084939.tif 000027
【図１９】
2005084939.tif 000028
【図２０】
2005084939.tif 000029
【図２１】
2005084939.tif 000030
【図２２】
2005084939.tif 000031