JP5175524B2 - コンパイラ - Google Patents

Description

本発明は、ソースプログラムを入力してオブジェクトプログラムを出力するコンパイラおよびコンパイラを含むツールチェインに関し、特に、アドレッシング可能なメモリからなる階層メモリを持つシステムで稼動するオブジェクトプログラムを生成する技術に関するものである。

従来、非特許文献１のp.33に記載されているように、動的再構成可能プロセッサ（ＤＲＰ：Dynamically Reconfigurable Processor）では、各プロセッサエレメントのコンフィギュレーション格納用に２階層のメモリ（主メモリと、各プロセッサエレメント内にある４個のレジスタ）を用い、動的再構成する機能ごとに主メモリから各レジスタへ全プロセッサエレメント分のコンフィギュレーション、すなわち固定サイズのコンフィギュレーションデータを転送していた。

また、従来、非特許文献２に記載されているように、多階層のキャッシュを用いるプロセッサがあった。また、非特許文献３のp.403に記載されているように、動的再構成可能プロセッサ内の各プロセッサエレメントに対するコンフィギュレーションを格納するメモリであるConfiguration Data Bufferと、そのメモリ中の複数のコンフィギュレーションを指すTransfer Control Tableを格納するメモリを持ち、これら２つを使ってコンフィギュレーションを各プロセッサエレメント内のConfiguration Data Registerに転送するシステムがあった。
榊原泰徳、佐藤友美 「DAPDNA（登録商標）のデバイス・アーキテクチャ」 Design Wave Magazine 2004 August, pp.30-38 Hennesy and Patterson, "Computer architecture a quantitative approach", Margin Kaufmann, 1996 Tomoyuki Kodama, Takanobu Tsunoda, Masashi Takada, Hiroshi Tanaka, Yohei Akita, Makoto Sato, and Masaki Ito, "Flexible Engine: A Dynamic Reconfigurable Accelerator with High Performance and Low Power Consumption", in Proceedings of IEEE Symposium on Low-Power and High-Speed Chips (COOL Chips IX), Yokohama, Japan, April 19-21, 2006, pp.393-408

非特許文献１に記載されている従来技術では、機能ごとのコンフィギュレーションの転送に際し、常に全プロセッサエレメント分のコンフィギュレーションを主メモリから転送するので、転送量が多くなり、転送時間も長くなる。また、非特許文献２に記載されている従来技術では、プリフェッチのような技術で必要となるデータをあらかじめキャッシュ上に置いたとしても、必要な時にデータがキャッシュ上にあるとは限らないので処理性能低下のおそれがある。また、非特許文献３に記載されている従来技術では、ハードウェアとしてデータ共用をサポートする階層メモリが提供されているが、これをソフトウエアとして効率的に使う手段については開示されていない。

そこで本発明の目的は、アドレッシング可能なメモリからなる階層メモリを持つシステムにおいて、命令やコンフィギュレーションの転送を高速かつ効率的に行うようなソフトウェアプログラムを作成する技術を提供することにある。

本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。

本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。

本発明の代表的な実施の形態によるコンパイラは、ソースプログラムを入力し、アドレッシング可能なメモリからなる少なくとも３階層の階層メモリを有する情報処理装置において稼動するオブジェクトプログラムを出力するコンパイラであって、情報処理装置のプロセッサに対する命令列またはコンフィギュレーションを、階層メモリにおいて下層のメモリから上層のメモリへ段階的に転送するコードを出力することを特徴とするものである。

本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。

本発明の代表的な実施の形態によれば、オブジェクトプログラムの実行時に、ソフトウエア的にキャッシュ制御を行うことなく階層メモリを有効に使うことができるので、アドレッシング可能な階層メモリを持つＤＲＰ等のアクセラレータにおいて、命令列やコンフィギュレーションのロードにかかるオーバーヘッドを極力少なくし、アクセラレータの高速処理能力を最大限に生かすことができる。

以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一の符号を付し、その繰り返しの説明は省略する。

図１は、本発明の一実施の形態であるＤＲＰ（動的再構成可能プロセッサ）向けコンパイラの構成を示した図である。ＤＲＰ向けコンパイラ１００は、コード生成部１０１と階層メモリ向けコード生成部１０２とから構成され、ソースプログラム１１０を入力として、プロセッサにより実行可能な形式のオブジェクトプログラムであるシーケンサコード１２０と、最終ＣＰＵコード１３０とを生成して出力する。

コード生成部１０１は、ソースプログラム１１０を入力して、後述する階層メモリを意識せずに、メインメモリから直接命令を読み込む形式で、中間ＣＰＵコード１０３、スレッドコード１０４、および階層スレッドグラフ１０５を生成して出力する。コード生成部１０１での処理は、一般的なコンパイラでの処理と同様であるため、処理内容についての説明は省略する。

階層メモリ向けコード生成部１０２は、コード生成部１０１が出力した中間ＣＰＵコード１０３、スレッドコード１０４、階層スレッドグラフ１０５を入力して、スレッド区間グラフ１０６を使いながら処理を行い、階層メモリを意識した形式で、シーケンサコード１２０と最終ＣＰＵコード１３０とを生成して出力する。階層メモリ向けコード生成部１０２での処理内容については後述する。

図２は、図１のＤＲＰ向けコンパイラ１００が稼動するコンピュータシステムのハードウェア構成例を示した図である。コンピュータシステムは、メモリ２００、ＣＰＵ２０１、ディスプレイ２０２、ＨＤＤ（ハードディスクドライブ）２０３、キーボード２０４を有し、これらがバス２０５に接続する構成となっている。ＨＤＤ２０３に格納されたソースプログラム１１０は、メモリ２００に格納されてＣＰＵ２０１上で稼動するＤＲＰ向けコンパイラ１００に入力され、ＤＲＰ向けコンパイラ１００から出力されたシーケンサコード１２０と最終ＣＰＵコード１３０はＨＤＤ２０３に格納される。

図３は、図１のＤＲＰ向けコンパイラ１００から出力されたシーケンサコード１２０および最終ＣＰＵコード１３０が稼動する情報処理装置のハードウェア構成例を示した図である。この情報処理装置は、例えばＬＳＩとして実装され、ＤＲＰ（動的再構成可能プロセッサ）３００、ＣＰＵ３１０、メインメモリ３２０、シーケンサメモリ３３０、ＣＭ３４０、ＴＭ３５０、シーケンサ（ＳＥＱ）３６０、データ転送用バス３７０、コンフィギュレーション転送用バス３８０を有する構成となっている。

ＤＲＰ３００は、さらに、プロセッサアレイ３０１、クロスパスネットワーク３０２、ローカルデータメモリ（ＬＭ）３０３を有する構成となっている。プロセッサアレイ３０１は、複数のプロセッサエレメント３０１１によって構成され、各プロセッサエレメント３０１１の間は、図示するように縦方向と横方向に配線で接続されている。ローカルデータメモリ３０３は、本実施の形態では左右それぞれ３バンクずつの合計６バンクの構成となっており、左右のローカルデータメモリ３０３は、それぞれプロセッサアレイ３０１の左端と右端にあるプロセッサエレメント３０１１と、クロスパスネットワーク３０２により接続されている。

シーケンサ３６０は、ＤＲＰ３００の動作を制御するシーケンサであり、シーケンサメモリ３３０は、シーケンサ３６０用のメモリであってシーケンサコード１２０を格納する。また、ＣＭ３４０は、プロセッサエレメント３０１１（セル）ごとのコンフィギュレーションである、セルコンフィギュレーションを格納するアドレッシング可能な命令プール用メモリであり、本実施の形態では７バンクを有する構成としている。また、ＴＭ３５０は、プロセッサアレイ３０１上で動作する１つのスレッドのプログラム（命令）であるスレッドテーブルを格納するアドレッシング可能な命令ブロックテーブル用メモリである。詳細は後述するが、ＣＭ３４０、ＴＭ３５０は、階層メモリを構成する要素となる。

ここで、メインメモリ３２０に格納された最終ＣＰＵコード１３０は、まず、ＴＭ３５０にスレッドテーブルを転送し、ＣＭ３４０にセルコンフィギュレーションを転送する。次に、シーケンサメモリ３３０に格納されたシーケンサコード１２０は、スレッドテーブルおよびセルコンフィギュレーションを用いて、セルコンフィギュレーションをプロセッサエレメント３０１１にロードし、ＤＲＰ３００の動作を制御する。このように、メインメモリ３２０からプロセッサエレメント３０１１まで段階的にデータの転送が行われる。

図４は、図３のプロセッサエレメント３０１１の構成例を示した図である。プロセッサエレメント３０１１は、ＤＬＹ４０１、ＡＬＵ４０２、ＭＵＬ４０３、スイッチ４０５、４０７、ＲＦ（レジスタファイル）４０８、スイッチ４０９、４１２を有する構成となっている。ＤＬＹ４０１は、１サイクルのディレイを発生させるディレイ用バッファであり、ＡＬＵ４０２は、算術演算を行う算術演算器であり、ＭＵＬ４０３は、乗算を行う乗算器である。

スイッチ４０５は、セルコンフィギュレーションによって、どのデータ入力用配線４０４からデータが入力したか、すなわち、詳細は後述するが、プロセッサエレメント３０１１のどの転送方向からデータが入力したかを選択する。さらに、入力するデータを演算させる演算器をＤＬＹ４０１、ＡＬＵ４０２、ＭＵＬ４０３の中から選択する。スイッチ４０７は、セルコンフィギュレーションによって、プロセッサエレメント３０１１が出力するデータを選択し、さらに、どのデータ出力用配線４０６にデータを出力するか、すなわち、プロセッサエレメント３０１１のどの転送方向にデータを出力するかを選択する。

ＲＦ４０８は、セルコンフィギュレーションを格納するレジスタファイルであり、詳細は後述するが、階層メモリを構成する要素となる。本実施の形態では、２バンクから構成されるものとしている。スイッチ４０９は、信号線４１０を介したシーケンサ３６０からの入力により、ＲＦ４０８の内の一方の内容を選択する。スイッチ４１２は、信号線４１１を介してＣＭ３４０から転送されるセルコンフィギュレーションをどちらのＲＦ４０８に入力するかを選択する。この構成により、ＲＦ４０８には２つのセルコンフィギュレーションが格納でき、プロセッサエレメント３０１１は、これらを使って２種類の演算を選択することができるので、高速に２種類の動的再構成を行うことが可能となる。

図５は、ＣＭ３４０とＴＭ３５０との関係の例を示した図である。図５において、ＣＭ３４０には、各プロセッサエレメント３０１１のセルコンフィギュレーションとして、７個のセルコンフィギュレーション３４０１が格納されている。また、ＴＭ３５０には、命令ブロックテーブル３５０１、３５０２が格納されており、命令ブロックテーブル３５０１、３５０２は、それぞれ６個の要素を有する。この各要素は、それぞれ６個のプロセッサエレメント３０１１に対応するフィールドとなっている。

命令ブロックテーブル３５０１、３５０２の各フィールドには、７個のセルコンフィギュレーション３４０１のいずれかを指すポインタが格納されている。従って、命令ブロックテーブル３５０１または３５０２と、図４の信号線４１１およびスイッチ４１２とを使えば、各セルコンフィギュレーション３４０１を該当する各プロセッサエレメント３０１１に転送することができる。

図６は、図３のＬＳＩの構成における階層メモリを示した図である。図中のＭＭは、メインメモリ３２０を表している。メモリ間を結ぶ破線は、対象のメモリ間（例えばＴＭ３５０とＲＦ４０８との間）では直接データを転送しないが、データ転送の制御を行うことを表す。また、メモリ間を結ぶ実線は、対象のメモリ間（例えばＣＭ３４０とＲＦ４０８との間）で直接データの転送を行うことを表す。

階層メモリは、プロセッサ（本実施の形態の動的再構成可能プロセッサの場合はプロセッサエレメント３０１１）から近いメモリを上層とする。従って、図３のＬＳＩの場合は、ＲＦ４０８を最上層に有し、その１つ下層にＣＭ３４０およびＴＭ３５０を有し、さらに１つ下層にメインメモリ３２０を有する３階層の階層メモリを有する構成となる。なお、本実施の形態では階層メモリは３階層となっているがこれに限られるものではなく、３階層以上の階層を有する階層メモリであっても構わない。

以下に、図１の階層メモリ向けコード生成部１０２での処理の内容について説明する。図７は、階層メモリ向けコード生成部１０２の処理の流れを示すフローチャートである。まず、ステップＳ７０１で、中間ＣＰＵコード１０３の内、未処理のプログラム片Ｐの有無を判定する。未処理のプログラム片ＰがあればステップＳ７０２へ進み、なければ処理を終了する。

ステップＳ７０２では、プロセッサに最も近い、最上層の階層メモリのうちから一つを選択する。次に、ステップＳ７０３で、ステップＳ７０２で選択したメモリをxとし、xより一つ下層のメモリのうち、xとの間でデータ転送が可能なメモリ、またはxと他のメモリとの間のデータ転送を制御するメモリのうちの一つを選択する。

ここで、後者のメモリは、例えば、xに転送するデータを保持するメモリ（zとする）とは別の、そのデータを転送するx上のアドレスを保持するメモリ（wとする）等を指す。実際のデータ転送は、wとzを両方同時に用いて行われるので、本実施の形態では、wのようなメモリも、xとの間でデータ転送が可能なメモリと同様に扱う。ＴＭ３５０はこのようなメモリの一例である。

次に、ステップＳ７０４で、ステップＳ７０３で選択したメモリをyとし、プログラム片Ｐ内の命令に対してxとyとの間の命令転送スケジューリングを行う。ステップＳ７０４の命令転送スケジューリング処理の詳細については、図８を用いて説明する。

図８は、命令転送スケジューリング処理の流れを示すフローチャートである。まず、ステップＳ８０１では、プログラム片Ｐに対する階層スレッドグラフ１０５に未処理のスレッドがあるか否かを判定する。階層スレッドグラフ１０５については後述する。未処理のスレッドがあればステップＳ８０２へ進み、なければステップＳ８０６へ進む。

ステップＳ８０２では、xが再利用性の高いメモリか否かを判定し、再利用性の高いメモリであればステップＳ８０３へ進み、そうでなければステップＳ８０４へ進む。ここで、再利用性の高いメモリとは、何度も処理される可能性の高いデータを保持するメモリを意味し、プログラム処理中のある期間に参照するデータがそのメモリ上に存在する可能性が高いメモリを意味する。

例えば、複数のプロセッサエレメント３０１１間で共通に使われる可能性のあるデータや、コンフィギュレーションを保持するメモリは再利用性の高いメモリとみなし、各プロセッサエレメント３０１１間で別々に使うデータを保持するメモリは再利用性の低いメモリとみなす。なお、再利用性が高い・低いという判定は一つの目安であり、この判定が異なっても命令転送スケジューリング処理の結果に誤りが発生するわけではなく、ＤＲＰ向けコンパイラ１００が出力するプログラムの処理性能が変化する程度である。実際、ハードウェアシステムやコンパイラ設計によってこの判断は分かれるであろうし、このような区別がつきにくいメモリもあると考えられる。

ステップＳ８０３では、以降の処理において利用するread時間を０とする。これは、参照するデータがそのメモリに存在する可能性が高いので、下層メモリから読み込む必要がないことをモデル化している。一方、ステップＳ８０４では、read時間を「一つ下層のメモリyからのスレッド命令読込み時間」とする。これは、参照するデータがそのメモリに存在する可能性が低いので、下層のメモリから読み込む必要があることをモデル化している。

ステップＳ８０５では、第１メモリ占有期間を「スレッド実行時間」または「xより一つ上層のメモリへのスレッド命令書込み時間」、第２メモリ占有期間を第１メモリ占有期間にread時間を加えた期間とする。例えば、図６の階層メモリの場合は、「スレッド実行時間」は、xがスレッドのプログラムを格納するＴＭ３５０である場合に用いる。一方、「xより一つ上層のメモリへのスレッド命令書込み時間」は、xがセルコンフィギュレーション３４０１を格納するＣＭ３４０である場合に用いる。

次に、ステップＳ８０６で、第２メモリ占有期間を区間とするスレッド区間グラフ１０６を作成して、内側ループから順にスレッドにメモリxのメモリユニット割当てを行う。ここで、スレッド区間グラフは、「中田育男著、コンパイラの構成と最適化、朝倉書店、p.384」において定義されているものであり、レジスタ割当て処理でよく使われるものである。

次に、ステップＳ８０７で、一つ下層のメモリyからのスレッド命令読込みのスケジューリングを行い、必要な場合には同期命令を挿入する。ここで、スケジューリングは「中田育男著、コンパイラの構成と最適化、朝倉書店、p.358」において定義されているものであり、ＣＰＵに対する命令列の最適化処理でよく使われるものである。また、同期命令は、使用中のメモリユニットへの上書きを避ける場合などに、メモリユニットの使用終了を待つ目的で挿入される処理である。

最後に、ステップＳ８０８で、冗長な同期命令を削除する。例えば、１箇所に複数の同期命令がある場合、同期命令を一つに削減する。以上で命令転送スケジューリング処理を終了し、図７のステップＳ７０５へ戻る。

ステップＳ７０５では、yと同じ階層でxとデータ転送またはデータ転送の制御が可能な未処理メモリがあるか否かを判定する。もしあれば、再度ステップＳ７０４を実行し、もしなければ、ステップＳ７０６へ進む。

ステップＳ７０６では、yと同じ階層のメモリ間で整合・冗長削除処理を行う。ここでは、同種のデータを格納するメモリが複数ある場合、それらの間で重複するデータがあるか否かを判定し、重複するデータがある場合には、可能であればいずれか一方のみを残し、他方を削除する。この時、両者のデータのメモリ占有期間や同期命令を合わせたものを残されたデータの占有期間や同期命令とし、データ転送などにおいて支障や矛盾が生じないように整合を取る。

次に、ステップＳ７０７では、xと同じ階層の未処理メモリがあるか否かを判定する。もしあればステップＳ７０３へ戻り、なければステップＳ７０８へ進む。ステップＳ７０８では、xと同じ階層のメモリ間で整合・冗長削除処理を行う。ここでの処理内容は、ステップＳ７０６と同様である。

次に、ステップＳ７０９で、xより一つ下の階層のメモリのうちの一つを選択する。次に、ステップＳ７１０で、ステップＳ７０９で選択したメモリが最下位の階層のメモリか否かを判定する。最下位層のメモリでなければステップＳ７０３へ戻り、最下位層のメモリであればステップＳ７１１へ進む。最後に、ステップＳ７１１で、最下位階層メモリにおいてメモリ割当て処理を行う。

以下、実際のプログラム例について、階層メモリ向けコード生成部１０２でどのように処理が行われるのかについて説明する。図９は、本実施の形態のＤＲＰ向けコンパイラ１００に入力するソースプログラム１１０の例を示した図である。文９０３と文９０４、文９０５と文９０６、文９０７と文９０８は、それぞれループを示す。本実施の形態でのＤＲＰ３００では、各ループの実行はそれぞれスレッドとしてプロセッサアレイ３０１にマッピングされるものとする。

図１０は、図９のソースプログラム１１０をスレッド化したものに対する階層スレッドグラフ１０５の例を示した図である。ノード１０００は、図９の文９０１の関数funcに対応するノードである。ノード１００１は、ノード１０００の下の階層に対する最初のノードを表す。これは処理の便宜上設けたノードであり、これに対応する文は図９のソースプログラム１１０中にはない。

ノード１００２は、図９の文９０３と文９０４が表すループを変換したスレッドに対応するノードである。また、ノード１００３は、文９０５と文９０６が表すループを変換したスレッドに対応するノードである。同様に、ノード１００４は、文９０７と文９０８が表すループを変換したスレッドに対応するノードである。ノード１００５は、ノード１０００の下の階層に対する最後のノードを表す。これも処理の便宜上設けたノードであり、これに対応する文は図９のソースプログラム１１０中にはない。

図１１は、図１０の階層スレッドグラフ１０５を実際に表現するデータ構造の例を示した図である。テーブル１１００は、図１０のノード１０００に対応するテーブルである。ここで、nextフィールドとprevフィールドは、それぞれ同じ階層における直前直後のテーブルへのポインタを示す。図１０の例では、ノード１０００は関数を表すノードであり、これと同じ階層のノードはないのでこれらの値はNULLとなる。フラグfunc_kは、このテーブル１１００が関数に対するテーブルであることを示す。beginpフィールドは、テーブル１１００より下の階層のスレッドグラフの最初のテーブル１１０１へのポインタを示す。endpフィールドは、テーブル１１００より下の階層のスレッドグラフの最後のテーブル１１０５へのポインタを示す。

テーブル１１０１は、図１０のノード１００１に対応するテーブルであり、この階層のスレッドグラフにおける最初のテーブルである。フラグbegin_kがそのことを示す。upperフィールドは、上の階層においてこの階層に接続されたテーブル１１００へのポインタを示す。図１１の階層スレッドグラフ１０５以外の階層の例としては、ループやif文などがある。すなわち、ループやif文に対応したテーブルが上の階層になり、ループ内の文やif文のthen側およびelse側の各文が下の階層になる。この時、ループ内の文の最初のテーブルに含まれるupperフィールドは、ループを表すテーブルへのポインタになり、then側の文の最初のテーブルに含まれるupperフィールドは、if文を表すテーブルへのポインタになる。entryフィールドは、後述するスレッド区間グラフ１０６へのポインタを示す。

テーブル１１０２は、図１０のノード１００２に対応するテーブルである。ここで、threadpフィールドは、スレッドコードへのポインタを示す。b-cycleフィールドは、本スレッドの開始サイクルを示す。最初のテーブル１１０１の直後のテーブルのサイクルは０とする。e-cycleフィールドは、本スレッドの実行終了時のサイクルを示す。

フラグpw-kは、ポスト処理もしくはウェイト処理を行うか、その両方とも行うかを示すフラグである。ポスト処理は何らかの対象に本スレッドの終了を知らせる処理であり、ウェイト処理は何らか対象の終了を待つ処理である。フラグr-load-kは、スレッド実行開始と同時にＴＭ３５０内のコンフィギュレーションをＲＦ４０８に転送するかどうかを示すフラグである。tm-numフィールドは、上記転送で使われるＴＭ３５０内のメモリバンク番号を示す。rf-numフィールドは、上記転送で使われるＲＦ４０８内のレジスタ番号を示す。

テーブル１１０３は、図１０のノード１００３に対応するテーブルであり、テーブル１１０４は、図１０のノード１００４に対応するテーブルである。これらのテーブルの内容は、前述したテーブル１１０２と同様である。テーブル１１０５は、図１０のノード１００５に対応するテーブルであり、この階層のスレッドグラフにおける最後のテーブルである。フラグend_kがそのことを示す。

次に、プロセッサアレイ３０１内の各プロセッサエレメント３０１１の配置およびデータの転送方向について説明する。図１２は、プロセッサアレイ３０１内の各プロセッサエレメント３０１１に対して定めた座標の例を示した図である。図１２の例では、６つのプロセッサエレメント３０１１に対して図示するようにx軸、y軸を定義し、座標によってプロセッサエレメント３０１１を特定できるようにしている。

図１３は、あるプロセッサエレメント３０１１とその周囲のプロセッサエレメント３０１１とを接続する配線の方向を表す記号を示した図である。この記号はプロセッサエレメント３０１１に対する入力にも出力にも適用され、データの転送方向を表すことができる。例えば、一つ上に位置するプロセッサエレメント３０１１からの入力配線には記号"u"が付き、一つ上に位置するプロセッサエレメント３０１１への出力配線にも記号"u"が付く。同様にして、一つ下に位置するプロセッサエレメント３０１１との間の入出力には記号"d"を、一つ左に位置するプロセッサエレメント３０１１との間の入出力には記号"l"を、一つ右に位置するプロセッサエレメント３０１１との間の入出力には記号"r"を用いる。

図１４は、以上に説明したプロセッサエレメント３０１１の配置およびデータの転送方向の指定方法に基づいて、図９のソースプログラム１１０の各ループをアセンブラ記述を用いて表したスレッドコードを示した図である。文１４０１の#threadがスレッドの開始を示し、その後の数字がスレッド番号を示す。また、文１４０８の#/threadがスレッドの終了を示す。従って、文１４０１と文１４０８で囲まれた文が、スレッド１に対応するアセンブラコードとなり、文１４０９と文１４１６で囲まれた文が、スレッド２に対応するアセンブラコードとなり、文１４１７と文１４２４で囲まれた文が、スレッド３に対応するアセンブラコードとなる。

文１４０２において、最初の"(1,1)"は、この命令が実行されるプロセッサエレメント３０１１の座標を表す。この座標は前述の図１２の例に従って設定される。その後のdlyは、この座標のプロセッサエレメント３０１１に配置されるディレイ命令を表す。"dly l,r"とあるのは、左方向（l）からデータを入力して、右方向（r）からデータを出力することを表す。このデータの転送方向は前述の図１３の例に従って設定される。同様に、例えば文１４０４は、左と下方向からデータを入力し、加算結果（add）を右方向に出力することを示す。また、文１４１０における"#'C1'"は、ディレイ用バッファに格納された即値"C1"を示す。以上の内容は、他の文についても同様に当てはまる。

図１５は、図１４のスレッドコードをプロセッサアレイ３０１にマッピングした例を示した図である。図１５の（ａ）はスレッド１を、（ｂ）はスレッド２を、（ｃ）はスレッド３をそれぞれマッピングした結果を示している。（ａ）において、６つの矩形はそれぞれプロセッサエレメント３０１１を示す。また、図の左側のxとyは、入力配列の値xとyを示し、右側のｚ１は出力配列の値ｚ１を示す。また、図中の矢印はデータの流れを示す。

dlyは１サイクルディレイ、addは加算、thrはディレイ無しのデータ転送、nopは何もしないことを示す。各矢印の上側に記載されている数字は、データ入力時点を０サイクルとして、矢印に該当するデータ転送が行われた時点での経過サイクル数を示す。本実施の形態でのＤＲＰ３００では、プロセッサエレメント３０１１に同じサイクルに到達したデータ同士が演算されるので、このマッピングによってスレッド１での演算は正しく行われることになる。図１５の（ｂ）、（ｃ）についても同様である。なお、（ｂ）におけるmulは乗算、subは減算、rshftは右への１ビットシフトを表す。

図１６は、図９のソースプログラム１１０に対する中間ＣＰＵコード１０３の例を示した図である。文１６０２のconf1には、スレッド１の各プロセッサエレメント３０１１のコンフィギュレーション、すなわち、図１４の文１４０２から文１４０７までのスレッドコードが格納されている。また、文１６０５のth1では、conf1の中の各コンフィギュレーションを参照していることを示している。すなわち、conf1をＣＭ３４０に置き、th1をＴＭ３５０に置くことで、スレッド１のコンフィギュレーションをプロセッサアレイ３０１にロードする準備が整う。

文１６０８は、th1を使ってconf1のセルコンフィギュレーションを各プロセッサエレメント３０１１中のＲＦ４０８の１番レジスタに格納する処理を表す。また、文１６０９は、配列xの５００要素を、ローカルデータメモリ３０３の１番バンクにロードする処理を表す。同様に、文１６１０は、配列yの５００要素を、ローカルデータメモリ３０３の２番バンクにロードする処理を表す。文１６１１は、ＤＲＰ３００の実行を開始することを表す。また、文１６１２は、ＤＲＰ３００の実行が終了するのを待つことを表す。文１６１３は、ローカルデータメモリ３０３の３番バンクにある５００要素のデータを配列z1へストアする処理を表す。以上の内容は、その他の文についても同様に当てはまる。

図１７は、階層スレッドグラフ１０５とスレッド区間グラフ１０６を表現するデータ構造の例を示した図である。テーブル１１０１〜１１０５は、図１１の階層スレッドグラフ１０５のデータ構造例に示した各テーブルである。テーブル１７０１は、ＲＦ４０８、ＣＭ３４０、ＴＭ３５０などのメモリに割り当てるべき、コンフィギュレーションなどのデータを示すテーブルである。ここで、r-nextフィールドは、このテーブルに関連するテーブルであるテーブル１７０２へのポインタを示す。kindフィールドは、コンフィギュレーション名などのデータ名を示す。d-nextフィールドは、他のデータ名に対応するテーブル１７０１と同様のテーブルへのポインタを示す。

テーブル１７０２は、あるサイクル区間にテーブル１７０１で示されるデータ名がどのメモリ位置に割り当てられるかを示すテーブルである。ここで、r-nextは、同じデータ名に対応するテーブル１７０２と同様の次のテーブルへのポインタを示す。b-cycleは、あるデータが割り当てられる最初のサイクルを示す。e-cycleは、あるデータが割り当てられる最後のサイクルを示す。

m-elemは、あるデータが割り当てられるあるメモリ内の位置を示す。m-kindは、あるデータが割り当てられるメモリの種類（ＣＭ３４０など）を示す。pw-kは、ポスト処理もしくはウェイト処理を行うか、その両方とも行うかを示すフラグである。ポスト処理は何らかの対象に本スレッドの終了を知らせる処理であり、ウェイト処理は何らか対象の終了を待つ処理である。

図１８は、図６の階層メモリにおいて最上層のメモリであるＲＦ４０８に対するスレッド区間グラフ１０６の例を示した図である。このグラフは、スレッドとそのスレッドの実行期間を表したグラフである。図１７の表記法で記載すると複雑になるので、説明の便宜上、以降図１８のような表記法で説明する。

図１８において、横軸はスレッドの実行サイクル数の経過を表す時間軸である。時間軸は期間に区切られており、時間軸上には該当期間で実行されるスレッドのスレッド番号（thread1〜thread3）が示されている。図１８の例では３つの期間に区切られており、それぞれの期間が、図１７の階層スレッドグラフ１０５の例における３つの階層（テーブル１１０２〜１１０４）に相当する。

区間１８０１は、スレッド１が実行されている区間を示したものである。この場合、スレッド１の実行に対応するデータ名はth1であり、対象がスレッドテーブル、すなわち、図１６の文１６０５のth1であることを示す。区間１８０２は、スレッド１の実行前にコンフィギュレーションをＴＭ３５０とＣＭ３４０とを使ってＲＦ４０８に転送する時間が必要であり、そのサイクル数をread区間として示したものである。以下、スレッド２、スレッド３についても同様である。

図６、図１８の例に基づいて、図７、図８で示した処理の内容を具体的に説明すると以下の通りとなる。まず図７のステップＳ７０２で、最上位メモリであるＲＦ４０８が選択される。次にステップＳ７０３で、ＲＦ４０８をxとし、ＲＦ４０８の１つ下の階層のメモリであるＴＭ３５０が選択される。次にステップＳ７０４で、ＴＭ３５０をyとし、図８の処理に移る。

まずステップＳ８０２において、xであるＲＦ４０８は再利用性の少ないメモリであるため、ステップＳ８０４へ進み、read時間をＴＭ３５０からＲＦ４０８へのデータのロード時間（前述のようにＴＭ３５０とＲＦ４０８との間では直接のデータ転送は行われないが、説明の便宜上このように記載しており、以下同様とする）である、図１８における区間１８０２とする。さらにステップＳ８０５で、第１メモリ占有期間を、ＲＦ４０８のスレッド実行期間である、図１８における区間１８０１とし、第２メモリ占有期間を、図１８の区間１８０１と区間１８０２とを合わせた区間とする。

次にステップＳ８０６において、メモリユニットの割当てとして、ＲＦ４０８のレジスタ数は２個なので、それぞれのread区間に１または２の数字を割り当てる。図１８の各read区間に記載されているr1、r2の文字は、その割当て結果を表しており、r1はＲＦ４０８の１番レジスタに、r2は２番レジスタに対してreadがなされることを示している。その後、ステップＳ８０７で各read処理のスケジューリングを行う。その結果を表したものを図１９に示す。

図１９は、ＲＦ４０８におけるロード命令のスケジューリングを行った結果のスレッド区間グラフ１０６の例を示した図である。本実施の形態でのＤＲＰ３００では、図１１で説明したようにスレッド実行開始と同時にＲＦ４０８へのロードが可能という特徴がある。この特徴を考慮して図１８のread区間１８０３に対してロード命令の移動を行った結果が図１９のread区間１９０１である。すなわち、２つのread処理r1とr2は、スレッドの実行開始と同時に行われる。

次に図８の処理を終了し、図７のステップＳ７０５に戻る。図６より、yに相当するＴＭ３５０とＣＭ３４０は同じ階層であるが、両メモリは協調して動作するので、この場合は一つのメモリとみなす。従って、この階層には他の未処理のメモリはないことになる。次にステップＳ７０６に移るが、yの階層は１つのメモリのみであるため整合・冗長削除の処理を行う必要がない。

ステップＳ７０７およびＳ７０８では、xの階層のメモリはＲＦ４０８のみであるため、処理は行われない。次にステップＳ７０９で、xより一つ下の階層のメモリとしてＴＭ３５０を選択し、ステップＳ７１０では、ＴＭ３５０は最下位層メモリではないためステップＳ７０３に戻る。ステップＳ７０３では、ＴＭ３５０をxとし、一つ下の階層のメモリとしてメインメモリ３２０を選択する。ステップＳ７０４では、メインメモリ３２０をyとして、図８の処理に移る。

ステップＳ８０２において、xであるＴＭ３５０も再利用性の少ないメモリであるため、ステップＳ８０４で、メインメモリ３２０からＴＭ３５０へのread時間を考慮する。次にステップＳ８０５では、図１９におけるＲＦ４０８のＴＭ３５０からのread時間は、ＴＭ３５０の視点からはＴＭ３５０からＲＦ４０８へのwrite時間になるため、ＴＭ３５０のスレッド実行区間に該当する。これを表したものを図２０に示す。

図２０は、ＴＭ３５０に対するスレッド区間グラフ１０６の例を示した図である。ステップＳ８０５の処理により、図１９のread区間１９０２は、図２０ではwrite区間２００１となっている。また、ＴＭ３５０は再利用性の少ないメモリであるため、メインメモリ３２０からのread時間を考慮する必要があり、read区間が加えられている。ステップＳ８０６において、ＴＭ３５０のメモリバンクは２つであるため、各read区間には２つのメモリバンクの一方を割り当てる。図２０の各read区間に割り当てられたr1、r2の文字は、その割当て結果を表している。その後、ステップＳ８０７でスケジューリングを行う。

図２１は、ＴＭ３５０におけるロード命令のスケジューリングを行った結果のスレッド区間グラフ１０６の例を示した図である。ポスト処理２１０１は、th3のスレッドに対応するread区間の終了時にポスト処理を行い、ウェイト処理２１０２は、thread2の開始時にウェイト処理を行うことを示す。このウェイト処理２１０２により、ポスト処理２１０１が完了していることを確認してから、ＴＭ３５０からＲＦ４０８への書込みが開始されるため、プロセッサアレイ３０１によるスレッド３の実行時にスレッド３のコンフィギュレーションがＲＦ４０８にあることが保証される。

次に、ＴＭ３５０と同様に、図７の処理においてＣＭ３４０をxとし、メインメモリ３２０をyとして図８の処理に移る。図２２は、ステップＳ８０６でメモリユニットの割当てが行われた時点での、ＣＭ３４０に対するスレッド区間グラフ１０６の例を示した図である。図の左端の命令群は、プロセッサエレメント３０１１に与えれらる命令を示す。その右に記載されている数字は、ＣＭ３４０の７個のメモリバンクのバンク番号を表し、各命令に対して通常のレジスタ割当てと同じアルゴリズムを使って、ＣＭ３４０の７個のメモリバンクのうちの該当のバンク番号に割り当てたことを示している。

write区間２２０１は、図２０のwrite区間２００１を表している。write区間２２０２は、NOPが存在するスレッドが３つあるので、NOP命令をreadする区間も３つあることを示している。同様に、write区間２２０３は、"add l,d,r"の命令が１番目と３番目のスレッドにのみ存在することを示している。

図２３は、ステップＳ８０７により、ＣＭ３４０におけるロード命令のスケジューリングを行った結果のスレッド区間グラフ１０６の例を示した図である。ポスト処理２３０１とウェイト処理２３０２は、図２２において、"sub l,d,r"の命令に対して、"dly l,r"の命令と同じバンク番号（"5"）が割り当てられたことによる同期命令である。これによって、"dly l,r"の命令が有効な間、このデータは上書きされないことが保証される。

ポスト処理２３０３とウェイト処理２３０４は、最後の３行の命令に対するロードの終了をチェックするための同期命令である。これによって、プロセッサアレイ３０１がスレッド２を実行するときに、スレッド２のコンフィギュレーションがＲＦ４０８にあることが保証される。また、図の左端のm1、m2は、このスケジューリング結果に伴い、メインメモリ３２０上で連続配置することが望ましい命令群を示したものである。

図２４は、前述したＴＭ３５０に対するスレッド区間グラフ１０６と、ＣＭ３４０に対するスレッド区間グラフ１０６とを統合したスレッド区間グラフ１０６を示した図である。ＣＭ３４０とＴＭ３５０は、異なる種類のデータを格納するメモリであるため、これらのメモリ間については整合・冗長削除処理を行うステップＳ７０６およびＳ７０７では処理は行われない。従って、図２４のスレッド区間グラフ１０６は、図２１のスレッド区間グラフ１０６と図２３のスレッド区間グラフ１０６とを単に統合したものとなる。

図２５は、図９のソースプログラム１１０に対して、図２４のスレッド区間グラフ１０６に基づいて出力された最終ＣＰＵコード１３０を示した図である。文２５０２のm1は、図２４のm1に対応するセルコンフィギュレーションの集合である。ここでm1は、図２４のm1に含まれる１番目から５番目の命令までに対するコンフィギュレーションを上から順（r1〜r5の順）に含んでいる。

同様に、文２５０３のm2は、図２４のm2に対応するセルコンフィギュレーションの集合である。ここでm2は、図２４のm2に含まれる１番目から３番目の命令までに対するコンフィギュレーションを下から１番目、上から１番目、上から２番目の順（r5,r6,r7の順）に含んでいる。文２５０２のm1、文２５０３のm2には、それぞれ上記の順に各命令に対するセルコンフィギュレーションが４バイトずつ格納されている。

文２５０４〜文２５０６は、図１４の各スレッドコードの各文に対する命令プールメモリＣＭ３４０上のセルコンフィギュレーションへのポインタを初期値代入した配列である。文２５０７は、メインメモリ３２０からＴＭ３５０へのデータ転送を行う命令を表す。文２５０４で示されたメインメモリ３２０上のポインタ配列th1をＴＭ３５０上の１番目のエントリへ転送することを示している。

文２５０８は、メインメモリ３２０からＣＭ３４０へのデータ転送を行う命令を表す。文２５０２で示されたメインメモリ３２０上の配列m1を、５要素分、ＣＭ３４０上の配列のcm[0]から始まる５要素に転送することを示している。これにより、図２４のm1に含まれる５命令に対応するセルコンフィギュレーションが、上述した順序でcm[0]からcm[4]に格納される。

これにより、文２５０４のポインタ配列th1の最初の３要素cm[4]、cm[1]、cm[3]は、それぞれ、"dly l,r"、"thr l,r"、"add l,d,r"の命令を指すことになる。これらの命令は、図１４のスレッドコードにおける文１４０２、文１４０３、文１４０４にそれぞれ該当する。以上により、文２５０４のポインタ配列th1はスレッドコードを保持する。文２５０５および文２５０６のポインタ配列th2とth3についても同様である。

文２５０９は、ＴＭ３５０を使ったＣＭ３４０からＲＦ４０８へのデータ転送を行う命令を表す。ポインタ配列th1の内容に従って、ＣＭ３４０上のセルコンフィギュレーションをＲＦ４０８の１番目のエントリへ転送することを示している。

文２５１０は、文２５０５で示されたメインメモリ３２０上のポインタ配列th2をＴＭ３５０上の２番目のエントリへ転送する命令を表す。文２５１１は、文２５０３で示されたメインメモリ３２０上の配列m2を３要素分、ＣＭ３４０上の配列のcm[4]から始まる３要素に転送することを示している。これにより、図２４のm2に含まれる３命令に対応するセルコンフィギュレーションが、上述した順序でcm[4]からcm[6]に格納される。

この処理において、文２５０８でデータを格納したcm[4]へ別のデータを上書きすることになるが、この配列要素cm[4]の指す内容は文２５０９の処理によってＲＦ４０８に転送済みなので、ＣＭ３４０上のこの要素は不要である。従って、文２５１１でこの要素cm[4]にデータを上書きしても問題はない。これにより、文２５０７〜文２５１１によって、図２４におけるr5のread区間でロードしたデータへの上書きを避けるための同期命令であるポスト処理２３０１とウェイト処理２３０２に相当する内容が実現されている。

文２５１２は、メインメモリ３２０上の配列xをローカルデータメモリ３０３の１番目のエントリへ５００要素分転送する命令を表す。同様に、文２５１３は、メインメモリ３２０上の配列yをローカルデータメモリ３０３の２番目のエントリへ５００要素分転送することを表す。

文２５１４は、文２５０６で示されたメインメモリ３２０上のポインタ配列th3をＴＭ３５０上の１番目のエントリへ転送する命令を表す。データ転送終了後、変数flagの値には１が代入される。文２５０７でポインタ配列th1をＴＭ３５０上の同じエントリへ転送したが、この配列th1の指す内容は文２５０９においてＲＦ４０８に転送済みなので、ＴＭ３５０上のこのエントリは不要である。従って、文２５１４でこのエントリにデータを上書きしても問題はない。文２５１５は、シーケンサコード１２０を格納しているメモリの１番目のエントリからシーケンサを起動する命令を表す。

ここで、図２６は、シーケンサメモリ３３０の各エントリの内容を文の形で記述したシーケンサコード１２０の例を示した図である。文２６０１は、ＴＭ３５０上の２番目のエントリth2とＣＭ３４０を使って、コンフィギュレーションをＲＦ４０８の２番目のエントリに転送するコードである。このコードを実行直後に、制御は次の文２６０２に移る。

文２６０２は、ＲＦ４０８の１番目のエントリを使ってＤＲＰ３００を再構成した後、５００サイクルの間処理を実行し、処理終了後、文２６０１の転送コードの終了を待つコードである。文２６０２において文２６０１の処理の終了を待つことによって、図２４における同期命令であるポスト処理２３０３とウェイト処理２３０４に相当する内容が実現されている。

文２６０３および文２６０４も、文２６０１および文２６０２と同様な動作を行う。文２６０４において文２６０３の処理の終了を待つことによって、図２４における同期命令であるポスト処理２１０１とウェイト処理２１０２に相当する内容が実現されている。文２６０５も文２６０２と同様な動作を行うが、処理終了後、何も待たずに次の文の処理に移る。ここでは次に実行すべき文はないので、シーケンサコード１２０の処理は終了し、図２５の処理に戻る。

図２５の文２５１６では、変数flagの値が１、かつ、ＤＲＰ３００で実行中のスレッドに対するコンフィギュレーションが格納されたＲＦ４０８のエントリ番号が２になるまで待つ。前者の条件は文２５１４の転送処理が終了していることを意味する。文２５１７は、スレッド１の処理の結果として得られる、ローカルデータメモリ３０３のエントリ１に格納されたデータを配列z1に５００要素分転送する命令である。文２５１６の判定により、スレッド１の実行が終了し、スレッド２が実行中であることが確認できているので、この転送処理は安全に行うことができる。

文２５１８では、ＤＲＰ３００で実行中のスレッドに対するコンフィギュレーションが格納されたＲＦ４０８のエントリ番号が１になるまで待つ。文２５１９は、スレッド２の処理の結果として得られる、ローカルデータメモリ３０３のエントリ２に格納されたデータを配列z2に５００要素分転送する命令である。文２５１６の判定によりスレッド２が実行中であり、文２６１８の判定により、スレッド２の実行が終了し、スレッド３が実行中であることが確認できているので、この転送処理は安全に行うことができる。

文２５２０では、ＤＲＰ３００の動作が終了するまで待つ。文２５２１は、スレッド３の処理の結果として得られる、ローカルデータメモリ３０３のエントリ３に格納されたデータを配列z3に５００要素分転送する命令である。以上により、図９のソースプログラム１１０に対応する処理が実行されることになる。

なお、本実施の形態では動的再構成可能プロセッサに対するオブジェクトプログラムを生成するＤＲＰ向けコンパイラ１００について説明しているが、アドレッシング可能な３階層以上の階層を持つ階層メモリシステムを持つプロセッサに対するオブジェクトプログラムを生成するコンパイラについても同様に適用可能である。

また、本実施の形態ではＤＲＰ向けコンパイラ１００がオブジェクトプログラムを生成する構成としているが、例えば、ＤＲＰ向けコンパイラ１００はアセンブリ言語プログラムを出力し、別途、アセンブラやリンケージエディタ等によりオブジェクトプログラムを生成するような構成であってもよい。また、ＤＲＰ向けコンパイラ１００による処理の前に、ソースプログラム１１０に対してプリプロセッサ等による処理を行ってもよい。このような、ＤＲＰ向けコンパイラ１００を含む一連の処理をツールチェインとして構成することも可能である。

以上に説明したように、階層メモリにプロセッサエレメント３０１１に対する命令列またはコンフィギュレーションを格納する命令プール用メモリＣＭ３４０と、ＣＭ３４０中の複数の命令列またはコンフィギュレーションを指す命令ブロックテーブルを格納する命令ブロックテーブル用メモリＴＭ３５０とを有する情報処理装置に対して、本実施の形態のＤＲＰ向けコンパイラ１００は、オブジェクトプログラムである最終ＣＰＵコード１３０およびシーケンサコード１２０を出力する。

このオブジェクトプログラムは、ＣＭ３４０より下層であるメインメモリ３２０からＣＭ３４０へ命令列またはコンフィギュレーションを転送し、また、ＴＭ３５０より下層であるメインメモリ３２０からＴＭ３５０へ命令ブロックテーブルを転送し、さらに、ＣＭ３４０からこれより上層のメモリであるＲＦ４０８へ、ＴＭ３５０中の命令ブロックテーブルの指す命令列またはコンフィギュレーションを転送するものである。

これにより、ＣＭ３４０においてコンフィギュレーションを共用することが可能になり、ある機能に再構成するためのコンフィギュレーションの一部がＣＭ３４０に存在する可能性が高くなり、結果として全てのコンフィギュレーションをメインメモリ３２０から転送する可能性が低くなるため、メインメモリ３２０からコンフィギュレーションを転送するとしても、従来技術より短時間で転送を行うことができる。また、ＣＭ３４０上ではデータの重複がないように制御されるため、このようなデータ共用をサポートする階層メモリを効率的に使用することができる。

また、このオブジェクトプログラムは、階層メモリの下層から上層へ段階的にデータを転送するものであり、ＤＲＰ向けコンパイラ１００により適切な同期命令の挿入と命令スケジューリングが行われていることから、実行中にキャッシュの場合のように必要なデータが自動的に追い出されてしまうようなことがなく、また、転送途中に下層からの転送データにより上層のデータが上書きされてしまうこともないため、階層メモリにおいて、必要なときには必ず指定したメモリ上に必要な命令列またはコンフィギュレーションが存在するようにすることができる。

以上に説明したように、本実施の形態のＤＲＰ向けコンパイラ１００によって生成されるオブジェクトプログラムは、実行時にソフトウエア的にキャッシュ制御を行うことなく階層メモリを有効に使うことができるため、アドレッシング可能な階層メモリを持つＤＲＰ等のアクセラレータにおいて、命令列やコンフィギュレーションのロードにかかるオーバーヘッドを極力少なくし、アクセラレータの高速処理能力を最大限に生かすことができる。

以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。

本発明は、ソースプログラムを入力してオブジェクトプログラムを出力するコンパイラおよびコンパイラを含むツールチェインに利用可能である。

本発明の一実施の形態であるＤＲＰ向けコンパイラの構成を示した図である。 本発明の一実施の形態における、ＤＲＰ向けコンパイラが稼動するコンピュータシステムのハードウェア構成例を示した図である。 本発明の一実施の形態における、最終ＣＰＵコードが稼動する情報処理装置のハードウェア構成例を示した図である。 本発明の一実施の形態における、プロセッサエレメントの構成例を示した図である。 本発明の一実施の形態における、ＣＭとＴＭとの関係の例を示した図である。 本発明の一実施の形態における、ＬＳＩの構成における階層メモリを示した図である。 本発明の一実施の形態における、階層メモリ向けコード生成部の処理の流れを示すフローチャートである。 本発明の一実施の形態における、命令転送スケジューリング処理の流れを示すフローチャートである。 本発明の一実施の形態における、ＤＲＰ向けコンパイラに入力するソースプログラムの例を示した図である。 本発明の一実施の形態における、ソースプログラムをスレッド化したものに対する階層スレッドグラフの例を示した図である。 本発明の一実施の形態における、階層スレッドグラフを実際に表現するデータ構造の例を示した図である。 本発明の一実施の形態における、プロセッサアレイ内の各プロセッサエレメントに対して定めた座標の例を示した図である。 本発明の一実施の形態における、あるプロセッサエレメントとその周囲のプロセッサエレメントとを接続する配線の方向を表す記号を示した図である。 本発明の一実施の形態における、ソースプログラムの各ループをアセンブラ記述を用いて表したスレッドコードを示した図である。 本発明の一実施の形態における、スレッドコードをプロセッサアレイにマッピングした例（ａ）、（ｂ）、（ｃ）を示した図である。 本発明の一実施の形態における、ソースプログラムに対する中間ＣＰＵコードの例を示した図である。 本発明の一実施の形態における、階層スレッドグラフとスレッド区間グラフを表現するデータ構造の例を示した図である。 本発明の一実施の形態における、ＲＦに対するスレッド区間グラフの例を示した図である。 本発明の一実施の形態における、ＲＦにおけるロード命令のスケジューリングを行った結果のスレッド区間グラフの例を示した図である。 本発明の一実施の形態における、ＴＭに対するスレッド区間グラフの例を示した図である。 本発明の一実施の形態における、ＴＭにおけるロード命令のスケジューリングを行った結果のスレッド区間グラフの例を示した図である。 本発明の一実施の形態における、メモリユニットの割当てが行われた時点での、ＣＭに対するスレッド区間グラフの例を示した図である。 本発明の一実施の形態における、ＣＭにおけるロード命令のスケジューリングを行った結果のスレッド区間グラフの例を示した図である。 本発明の一実施の形態における、ＴＭに対するスレッド区間グラフと、ＣＭに対するスレッド区間グラフとを統合したスレッド区間グラフを示した図である。 本発明の一実施の形態における、スレッド区間グラフに基づいて出力された最終ＣＰＵコードを示した図である。 本発明の一実施の形態における、シーケンサメモリの各エントリの内容を文の形で記述したシーケンサコードの例を示した図である。

符号の説明

１００…ＤＲＰ向けコンパイラ、１０１…コード生成部、１０２…階層メモリ向けコード生成部、１０３…中間ＣＰＵコード、１０４…スレッドコード、１０５…階層スレッドグラフ、１０６…スレッド区間グラフ、１１０…ソースプログラム、１２０…シーケンサコード、１３０…最終ＣＰＵコード、
２００…メモリ、２０１…ＣＰＵ、２０２…ディスプレイ、２０３…ＨＤＤ、２０４…キーボード、２０５…バス、
３００…動的再構成可能プロセッサ（ＤＲＰ）、３０１…プロセッサアレイ、３０２…クロスパスネットワーク、３０３…ローカルデータメモリ（ＬＭ）、３１０…ＣＰＵ、３２０…メインメモリ、３３０…シーケンサメモリ、３４０…ＣＭ、３５０…ＴＭ、３６０…シーケンサ（ＳＥＱ）、３７０…データ転送用バス、３８０…コンフィギュレーション転送用バス、３０１１…プロセッサエレメント、
４０１…ＤＬＹ、４０２…ＡＬＵ、４０３…ＭＵＬ、４０４…データ入力用配線、４０５…スイッチ、４０６…データ出力用配線、４０７…スイッチ、４０８…レジスタファイル（ＲＦ）、４０９…スイッチ、４１０…信号線、４１１…信号線、４１２…スイッチ、
３４０１…セルコンフィギュレーション、３５０１…命令ブロックテーブル、３５０２…命令ブロックテーブル。

Claims (6)

1. ソースプログラムを入力し、アドレッシング可能なメモリからなる少なくとも３階層の階層メモリを有する情報処理装置において稼動するオブジェクトプログラムをコンピュータに出力させる際に、前記情報処理装置のプロセッサに対する命令列またはコンフィギュレーションを、前記階層メモリにおいて、前記プロセッサに近いメモリを上層として、前記情報処理装置に、下層のメモリから上層のメモリへ段階的に転送させるコードを前記コンピュータに出力させるコンパイラであって、
   該コンパイラが前記コンピュータに出力させるオブジェクトプログラムが稼動する前記情報処理装置が有する前記階層メモリは、前記プロセッサ内のプロセッサエレメントに対する命令列またはコンフィギュレーションを格納する命令プール用メモリと、前記命令プール用メモリ中の複数の命令列またはコンフィギュレーションを指す命令ブロックテーブルを格納する命令ブロックテーブル用メモリとを有し、
   前記コードには、前記情報処理装置が命令列またはコンフィギュレーションを利用するスレッドの実行サイクルの開始までに、該命令列またはコンフィギュレーションが最上層のメモリに書き込まれるよう、前記情報処理装置に、前記命令プール用メモリより下層のメモリから前記命令プール用メモリへ該命令列またはコンフィギュレーションを転送させるコード、並びに、前記命令ブロックテーブル用メモリより下層のメモリから前記命令ブロックテーブル用メモリへ命令ブロックテーブルを転送させるコード、および前記命令プール用メモリからこれらより上層のメモリへ、前記命令ブロックテーブル用メモリ中の命令ブロックテーブルの指す該命令列またはコンフィギュレーションを転送させるコードを含み、
   前記コンピュータに、前記ソースプログラムに基づいて中間ＣＰＵコード、スレッドコード、および階層スレッドグラフを出力させ、さらに、前記情報処理装置によって各命令列またはコンフィギュレーションが前記命令プール用メモリから上層のメモリに対して転送開始される時間から転送終了するまでの時間を、該命令列またはコンフィギュレーションのメモリ占有期間とみなして、前記コンピュータに、前記中間ＣＰＵコード、前記スレッドコード、および前記階層スレッドグラフに基づいてスレッド区間グラフを生成させ、前記スレッド区間グラフに基づいて、前記情報処理装置に前記命令プール用メモリに対して該命令列またはコンフィギュレーションを保持するためのメモリを割り当てさせるような前記コードを前記コンピュータに出力させることを特徴とするコンパイラ。
2. 請求項１に記載のコンパイラにおいて、
   前記命令プール用メモリ上において命令列またはコンフィギュレーションが重複しないように前記情報処理装置に命令列またはコンフィギュレーションを転送させるよう、前記コンピュータに前記コードを出力させることを特徴とするコンパイラ。
3. 請求項１または２に記載のコンパイラにおいて、
   前記情報処理装置に命令列またはコンフィギュレーションを前記階層メモリにおける下層のメモリから上層のメモリへ段階的に転送させる前記コードを、前記コンピュータに、前記階層メモリの上層のメモリから下層のメモリに向かって順に、対象のメモリに対して該命令列またはコンフィギュレーションを保持するための領域を前記情報処理装置に割り当てさせるコードを出力する処理と、前記情報処理装置に一つ下層のメモリから該命令列またはコンフィギュレーションを読み込んで対象のメモリに書き込ませる転送命令に対する命令スケジューリングとを実行させることによって出力させることを特徴とするコンパイラ。
4. 請求項３に記載のコンパイラにおいて、
   前記コンピュータによる前記階層メモリにおける上層のメモリについての命令スケジューリングの結果として得られる、前記情報処理装置による下層のメモリから前記上層のメモリへの転送命令の実行開始から実行終了までの期間を、前記下層のメモリにおけるメモリ占有期間とみなすことによって、前記情報処理装置に前記下層のメモリに対して各命令列またはコンフィギュレーションを保持するためのメモリを割り当てさせるような前記コードを前記コンピュータに出力させることを特徴とするコンパイラ。
5. 請求項１〜４のいずれか１項に記載のコンパイラにおいて、
   該コンパイラが前記コンピュータに出力させるオブジェクトプログラムが稼動する前記情報処理装置の前記プロセッサは、動的再構成可能プロセッサであることを特徴とするコンパイラ。
6. ツールチェインに含まれることを特徴とする請求項１〜５のいずれか１項に記載のコンパイラ。

Images