(57)【要約】【課題】  データの寿命によるメモリ使用の最適化システムおよび最適化方法を提供する。【解決手段】  データを記憶する方法は、データ要素のインデックスされた集合の各メンバの各寿命を識別するステップであって、データ要素のそれぞれが、有効なデータ要素インデックスの集合を表すデータインデックス空間で参照可能である、識別するステップと、オーバーラップした寿命を有するデータ要素の対の集合を識別するステップと、オーバーラップした寿命を有するデータ要素の対の集合に基づいて、データインデックス空間からアドレスオフセット空間へのマッピングを生成するステップと、を含む、データを記憶するステップを含む。
2006505058.tif 000002
【特許請求の範囲】
【請求項１】
データを記憶する方法であって、
データ要素のインデックスされた集合の各メンバの各寿命を識別するステップであって、前記データ要素のそれぞれが、有効なデータ要素インデックスの集合を表すデータインデックス空間で参照可能である、識別するステップと、
オーバーラップした寿命を有する前記データ要素の対の集合を識別するステップと、
前記オーバーラップした寿命を有する前記データ要素の対の前記集合に基づいて、前記データインデックス空間からアドレスオフセット空間へのマッピングを生成するステップと、
を含む、方法。
【請求項２】
前記アドレスオフセット空間に対応するメモリロケーションに前記データ要素を記憶するコンピュータ実行可能命令コードを生成するステップ、をさらに含む、請求項１に記載のデータを記憶する方法。
【請求項３】
任意の１つのイベント時間の間ライブであるデータ要素の最大の部分集合を保持するのに十分な複数の前記メモリロケーションを含むように前記アドレスオフセット空間を規定するステップ、をさらに含む、請求項１に記載のデータを記憶する方法。
【請求項４】
前記アドレスオフセット空間に対応するより小さなアドレス空間に多次元データ構造体をマッピングするステップ、をさらに含む、請求項１に記載のデータを記憶する方法。
【請求項５】
前記アドレスオフセット空間のアドレスオフセットへ前記多次元配列の要素のインデックスを変換するステップであって、モジュロ算術を実行するステップを含む変換するステップ、をさらに含む、請求項４に記載のデータを記憶する方法。
【請求項６】
前記生成するステップは、線形オフセットマッピングを使用し、これに続いて、単一のモジュロオペレーションを使用して、多次元データインデックス空間からより小さなアドレスオフセット空間への変換を行うことを含む、請求項５に記載のデータを記憶する方法。
【請求項７】
前記生成するステップは、第２のデータインデックス空間への線形マッピングを使用し、これに続いて、該第２のデータインデックス空間のインデックスに適用される複数のモジュロオペレーションを使用し、これに続いて、アドレスオフセット空間への線形オフセットマッピングを使用して、多次元データインデックス空間からより小さなアドレスオフセット空間への変換を行うことを含む、請求項５に記載のデータを記憶する方法。
【請求項８】
データを記憶する方法であって、
プログラムの配列データ構造体を特定するステップと、
該配列データ構造体の各要素について、最早の書き込み時刻および最後の読み出し時刻を特定するステップと、
オーバーラップする寿命を有する前記要素の対の集合の表現を見つけるステップと、
前記オーバーラップした寿命を有する前記要素の対の前記集合のインデックスの差の集合を求めるステップと、
該差の集合と共通した非ゼロベクトルの点を有しない整数束を求めるステップと、
該整数束を使用して、前記配列データ構造体のデータインデックス空間からアドレスオフセット空間へマッピングするステップと、
を含む方法。
【請求項９】
式
Ｍ１（Ｍ２ａ  ｍｏｄ  ｒ）
を使用して、配列インデックス「ａ」を有する前記配列データ構造体の配列要素のアドレスオフセットを生成することを含むプログラムをコンパイルするステップ、
をさらに含み、
ここで、Ｍ２は底を変換した行列であり、Ｍ１はベクトルの乗数であり、ｒはベクトルの基数である、
請求項８に記載のデータを記憶する方法。
【請求項１０】
ｒのエントリの積に等しく、かつ、前記配列データ構造体の前記配列要素を記憶するのに使用される複数のセルを割り当てるステップ、
をさらに含む、請求項９に記載のデータを記憶する方法。
【請求項１１】
行列Ｍ２が１行を有し、ベクトルｒが１つの要素を有し、行列Ｍ１が１に等しいという制限をさらに有する、請求項９に記載のデータを記憶する方法。
【請求項１２】
整数束の行列式を最小にするように試みることを含む該整数束を求めるステップ、をさらに含む、請求項８に記載のデータを記憶する方法。
【請求項１３】
コンピュータ可読媒体に記憶されたコンピュータプログラムであって、
データ要素のインデックスされた集合の各メンバの各寿命を識別するコンピュータ実行可能コードであって、前記データ要素のそれぞれが、有効なデータ要素インデックスの集合を表すデータインデックス空間で参照可能である、コンピュータ実行可能コードと、
オーバーラップした寿命を有する前記データ要素の対の集合を識別するコンピュータ実行可能コードと、
前記オーバーラップした寿命を有する前記データ要素の対の前記集合に基づいて、前記データインデックス空間からアドレスオフセット空間へのマッピングを生成するコンピュータ実行可能コードと、
を含む、コンピュータプログラム。
【請求項１４】
前記アドレスオフセット空間に対応するメモリロケーションに前記データ要素を記憶するコンピュータ実行可能命令コードを生成するコンピュータ実行可能コード、をさらに含む、請求項１３に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項１５】
任意の１つのイベント時間の間ライブであるデータ要素の最大の部分集合を保持するのに十分な複数の前記メモリロケーションを含むように前記アドレスオフセット空間を規定するコンピュータ実行可能コード、をさらに含む、請求項１３に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項１６】
前記アドレスオフセット空間に対応するより小さなアドレス空間に多次元データ構造体をマッピングするコンピュータ実行可能コード、をさらに含む、請求項１３に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項１７】
前記アドレスオフセット空間のアドレスオフセットへ前記多次元配列の要素のインデックスを変換するコンピュータ実行可能コードであって、モジュロ算術を実行することを含むコンピュータ実行可能コード、をさらに含む、請求項１６に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項１８】
前記生成するコンピュータ実行可能コードは、線形オフセットマッピングを使用し、これに続いて、単一のモジュロオペレーションを使用して、多次元データインデックス空間からより小さなアドレスオフセット空間への変換を行うコンピュータ実行可能コードを含む、請求項１７に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項１９】
前記生成するコンピュータ実行可能コードは、第２のデータインデックス空間への線形マッピングを使用し、これに続いて、該第２のデータインデックス空間のインデックスに適用される複数のモジュロオペレーションを使用し、これに続いて、アドレスオフセット空間への線形オフセットマッピングを使用して、多次元データインデックス空間からより小さなアドレスオフセット空間への変換を行うコンピュータ実行可能コードを含む、請求項１７に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項２０】
コンピュータ可読媒体に記憶されたコンピュータプログラムであって、
プログラムの配列データ構造体を特定するコンピュータ実行可能コードと、
該配列データ構造体の各要素について、最早の書き込み時刻および最後の読み出し時刻を特定するコンピュータ実行可能コードと、
オーバーラップする寿命を有する前記要素の対の集合の表現を見つけるコンピュータ実行可能コードと、
前記オーバーラップした寿命を有する前記要素の対の前記集合のインデックスの差の集合を求めるコンピュータ実行可能コードと、
該差の集合と共通した非ゼロベクトルの点を有しない整数束を求めるコンピュータ実行可能コードと、
該整数束を使用して、前記配列データ構造体のデータインデックス空間からアドレスオフセット空間へマッピングするコンピュータ実行可能コードと、
を含むコンピュータプログラム。
【請求項２１】
式
Ｍ１（Ｍ２ａ  ｍｏｄ  ｒ）
を使用して、配列インデックス「ａ」を有する前記配列データ構造体の配列要素のアドレスオフセットを生成することを含むプログラムをコンパイルするコンピュータ実行可能コード、
をさらに含み、
ここで、Ｍ２は底を変換した行列であり、Ｍ１はベクトルの乗数であり、ｒはベクトルの基数である、
請求項２０に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項２２】
ｒのエントリの積に等しく、かつ、前記配列データ構造体の前記配列要素を記憶するのに使用される複数のセルを割り当てるコンピュータ実行可能コード、
をさらに含む、請求項２０に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項２３】
前記複数のセルを割り当てるコンピュータ実行可能コードは、行列Ｍ２が１行を有し、ベクトルｒが１つの要素を有し、行列Ｍ１が１に等しいという制限を実施する、請求項２０に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【請求項２４】
整数束の行列式を最小にするように試みることを含む該整数束を求めるコンピュータ実行可能コード、をさらに含む、請求項２０に記載のコンピュータ可読媒体に記憶されたコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的には、データ処理に関し、より詳細には、データの寿命によりメモリ使用を最適化することに関する。
【０００２】
［関連出願の相互参照］
この出願は、同時に出願され同時係属中の「Method and System for the Design of Pipelines of Processors」という発明の名称の特許出願第［１００１１０５５７−１号］に関連する。この出願の開示は、参照により本明細書に援用される。
【背景技術】
【０００３】
［関連技術の説明］
従来のコンピュータアーキテクチャは、通常、メインメモリシステムおよびさまざまな入出力（Ｉ／Ｏ）設備に接続された中央処理装置（ＣＰＵ）を含む。命令を含むデータは、メインメモリとＣＰＵとの間を移動する。メインメモリとＣＰＵとの間の全帯域幅は、メモリアクセス時間、ワードサイズ、バス幅およびバス速度等を含むいくつかのファクタによって制限される。ほとんどの場合、特に大量のデータを伴う場合（例えば、科学コンピュータアプリケーションおよび／または画像／ビデオ処理）には、ＣＰＵとメインメモリとの間のメモリ帯域幅がボトルネックを生み出し、全体的なシステム性能を許容できないレベルまたは望ましくないレベルにまで低下させることがある。
【０００４】
一般的な汎用コンピュータシステムおよび専用デバイス（例えば、携帯情報端末、および、デジタルカメラ、娯楽デバイス、プログラマブルテスト機器、コンピュータ制御された製造機器等の専用デバイス）の双方のストレージ要件を満たすさまざまなメモリシステムが考案されてきた。性能が増加し続ける一方で、メモリのコストが減少し続ける限り、当然の結果として、このようなメモリ資源に対する要件は、同様に絶えず増大する割合で増大する。したがって、メモリ資源を効率的に配備して使用する技法、方法、およびシステムに対する要求が絶えず増大している。このようなメモリ資源には、メインメモリ、さまざまなレベルのキャッシュ、スクラッチパッドメモリ（ＳＰＭ）等が含まれ得るが、これらに限定されるものではない。
【０００５】
例えば、一般的なコンピュータシステムは階層的なメモリ構造を使用する。この階層的なメモリ構造は、プロセッサを含むさまざまな構造によって直接アクセス可能な限られた個数の非常に高速なレジスタ、大量のオフチップのレベル２キャッシュによって増大可能な、大きいが幾分低速なオンチップのレベル１キャッシュメモリのアレイ、さらに低速であるがより多くのメインメモリ等から成る。このように、メインメモリとＣＰＵとの間の潜在的なボトルネックを低減するために、コンピュータ設計者は、メインメモリおよび１つまたは２つ以上のレベルの中間キャッシュメモリの使用を含むメモリ階層等のマルチレベルのメモリ階層を使用することがある。キャッシュメモリは、ＣＰＵがデータにアクセスするのに必要な時間を減少させ、それによって、データ待ち時間を最小にする。その結果、キャッシュメモリは、実行中のアプリケーションの性能を改善する。
【０００６】
これらのシステムのキャッシュメモリは、一般に、プログラマには直接利用可能ではない。すなわち、キャッシュメモリは、一般に、アプリケーションプログラムインターフェースの一部ではなく、その代わり、専用コントローラまたは同様のハードウェアによって制御される。プログラムをコンパイルするコンパイラ、ならびに、メインメモリへの「ロード」コマンドおよび「ストア」コマンドを実行するプログラムは、プログラマからの要求を受け取ることなくキャッシュメモリを利用する。さらに、ランタイムには、ハードウェアは、メインメモリの或る範囲のアドレスに関連した、頻繁にアドレス指定されるデータおよび／または命令をキャッシュに自動的に転送することができる。それらのアドレスに記憶されたデータに対するＣＰＵの要求は、キャッシュから自動的に満たされる。
【０００７】
デジタル信号プロセッサやカスタムコンピュータエンジン等の高性能ハードウェアを必要とするシステムは、システムの高速計算をサポートする高いメモリ帯域幅を必要とする。上述したような標準的なキャッシュ機構は、これらのタイプのシステムに十分なメモリ帯域幅を提供せず、たとえキャッシュがメインメモリを補完するために使用できるとしても、依然として、ボトルネックは最終的には発生する。キャッシュメモリに加えて、ボトルネックが発生しないか、または、発生する可能性を低くするようにローカルメモリの帯域幅を追加して提供するため、コンピュータ設計者は、スクラッチパッドメモリ（ＳＰＭ）と呼ばれる小さく高速なローカルメモリを自身のコンピュータ設計に含めることもできる。ＳＰＭは、プログラマが使用するのに利用できるローカルメモリであり、アプリケーションプログラムインターフェースを通じて利用できるローカルメモリである。例えば、プログラムの「ロード」命令および「ストア」命令は、メインメモリ領域または特定のローカルＳＰＭ領域のいずれかを明示的にアドレス指定することができる。プログラムは、所与のデータアイテムをこれらの別個のメモリ空間の一方に明示的に配置する。ＳＰＭは、メインメモリ帯域幅もキャッシュメモリ内の空間も使用することなく、ＣＰＵに直接データを提供することができる。したがって、ＳＰＭは、システム性能をさらに改善し、ＣＰＵがデータにアクセスするのに必要な時間を減少させる。その結果、ＳＰＭは、実行中のアプリケーションの性能を改善する。
【０００８】
現在のところ、データは、コンピュータプログラマによってＳＰＭに再配置されており、プログラムのコンパイル時にコンパイラによって自動的には挿入されない。したがって、ＳＰＭの使用を自動的に構成し、ＳＰＭを最も効率的に利用することが望まれている。
【０００９】
効率的なデータおよび情報の処理を提供してサポートするために、ＳＰＭに加えて、他のメモリ資源の使用も最適化されるべきである。
【００１０】
高性能を必要とするいくつかのアプリケーションでは、専用ハードウェアプロセッサが構築されることがある。ネストループとして表されたソフトウェア機能が、専用プロセッサまたは処理エレメントのアレイによってハードウェアに実施されることがある。より複雑なソフトウェア機能は、ネストループのシーケンスから成るプログラムフラグメントによって表されることがあり、１つまたは２つ以上の処理エレメントのアレイから成るパイプラインによって実施されることがある。このようなパイプラインを設計する際に、設計者は、パイプラインの最初のステージの開始を基準にして、あらゆる計算オペレーションが実行される正確なクロックサイクルを決定するスケジュールを選ぶことができる。これらのオペレーションには、メモリへのロードおよびストアが含まれ得る。このような設計は、従来、手動で作成されていた。
【００１１】
【特許文献１】米国特許第６４３８７４７号
【特許文献２】米国特許第４９９１０８８号
【特許文献３】米国特許第６３７４４０３号
【非特許文献１】PANDA P R ET AL: "Efficient utilization of scratch-pad memory in embedded processor applications" EUROPEAN DESIGN AND TEST CONFERENCE, 1997. ED&TC 97. PROCEEDINGS PARIS, FRANCE 17-20 MARCH 1997, LOS ALAMITOS, CA, USA,IEEE COMPUT. SOC, US, 17 March 1997 (1997-03-17), pages 7-11, XP010218471 ISBN: 0-8186-7786-4 page 7, column 1 - page 11, column 2
【非特許文献２】KANDEMIR M ET AL: "Compiler-directed selection of dynamic memory layouts" PROCEEDINGS OF THE 9TH. INTERNATIONAL WORKSHOP ON HARDWARE/SOFTWARE CODESIGN. CODES 2001. COPENHAGEN, DENMARK, APRIL 25 - 27, 2001, PROCEEDINGS OF THE INTERNATIONAL WORKSHOP ON HARDWARE/SOFTWARE CODESIGN. NEW YORK NY : ACM, US, 25 April 2001 (2001-04-25), pages 219-224, XP0l0543444 ISBN: 1-58113-364-2 page 219, column 2 - page 224 column 2
【非特許文献３】GRUN P ET AL: "APEX: access pattern based memory architecture exploration" 14TH. INTERNATIONAL SYMPOSIUM ON SYSTEM SYNTHESIS. ISSS. MONTREAL, CANADA, SEPT. 30 - OCT. 3, 2001, INTERNATIONAL SYMPOSIUM ON SYSTEM SYNTHESIS. ISSS, NEW YORK, NY : ACM, US, 30 September 2001 (2001-09-30), pages 25-32, XP010563555 ISBN: 1-58113-418-5 page 25 - page 32
【非特許文献４】CATTHOOR F ET AL: "Hot topic session: How to solve the current memory access and data transfer bottlenecks: at the processor architecture or at the compiler level ? " UNIVERSITY PAPER, 27 March 2000 (2000-03-27), pages 426-433, XP010377501 page 426 - page 433
【非特許文献５】KANDEMIR M ET AL: "Exploiting scratch-pad memory using presburger formulas" 14TH. INTERNATIONAL SYMPOSIUM ON SYSTEM SYNTHESIS. ISSS. MONTREAL. CANADA, SEPT. 30 - OCT. 3, 2001, INTERNATIONAL SYMPOSIUM ON SYSTEM SYNTHESIS. ISSS, NEW YORK, NY : ACM, US, 30 September 2001 (2001-09-30), pages 7-12, XP010563552 ISBN: 1-58113-418-5 page 7, column 1 - page 11, column 1
【発明の開示】
【課題を解決するための手段】
【００１２】
［発明の簡単な概要］
本発明の一態様によると、データを記憶する方法は、データ要素のインデックスされた集合の各メンバの各寿命を識別するステップであって、データ要素のそれぞれが、有効なデータ要素インデックスの集合を表すデータインデックス空間で参照可能である、識別するステップと、オーバーラップした寿命を有するデータ要素の対の集合を識別するステップと、オーバーラップした寿命を有するデータ要素の対の集合に基づいて、データインデックス空間からアドレスオフセット空間へのマッピングを生成するステップと、を含む。
【００１３】
本発明の別の態様によると、データを記憶する方法は、プログラムの配列データ構造体を特定するステップと、配列データ構造体の各要素について、最早の書き込み時刻および最後の読み出し時刻を特定するステップと、オーバーラップする寿命を有する要素の対の集合の表現を見つけるステップと、オーバーラップした寿命を有する要素の対の集合のインデックスの差の集合を求めるステップと、差の集合と共通した非ゼロベクトルの点を有しない整数束を求めるステップと、整数束を使用して、配列データ構造体のデータインデックス空間からアドレスオフセット空間へマッピングするステップと、を含む。
【００１４】
本発明のさらに別の態様によると、コンピュータ可読媒体に記憶されたコンピュータプログラムは、データ要素のインデックスされた集合の各メンバの各寿命を識別するコンピュータ実行可能コードであって、データ要素のそれぞれが、有効なデータ要素インデックスの集合を表すデータインデックス空間で参照可能である、コンピュータ実行可能コードと、オーバーラップした寿命を有するデータ要素の対の集合を識別するコンピュータ実行可能コードと、オーバーラップした寿命を有するデータ要素の対の集合に基づいて、データインデックス空間からアドレスオフセット空間へのマッピングを生成するコンピュータ実行可能コードと、を含む。
【００１５】
本発明のさらに別の態様によると、コンピュータ可読媒体に記憶されたコンピュータプログラムは、プログラムの配列データ構造体を特定するコンピュータ実行可能コードと、配列データ構造体の各要素について、最早の書き込み時刻および最後の読み出し時刻を特定するコンピュータ実行可能コードと、オーバーラップする寿命を有する要素の対の集合の表現を見つけるコンピュータ実行可能コードと、オーバーラップした寿命を有する要素の対の集合のインデックスの差の集合を求めるコンピュータ実行可能コードと、差の集合と共通した非ゼロベクトルの点を有しない整数束を求めるコンピュータ実行可能コードと、整数束を使用して、配列データ構造体のデータインデックス空間からアドレスオフセット空間へマッピングするコンピュータ実行可能コードと、を含む。
【発明を実施するための最良の形態】
【００１６】
［詳細な説明］
本発明は、通常ならば単一の多次元データ配列に記憶されるようなデータを記憶する代替的な方法および構造を実施する。この方法および構造では、配列の各要素がメモリにおける一意のロケーションに割り当てられる。しかしながら、従来のデータ配列と異なり、２つまたは３つ以上の配列要素が、メモリロケーションを共有することができ、その配列が消費するストレージロケーションの個数は、配列の要素数よりも少ない。さらに、本発明の実施の形態は、配列インデックス（ｉ，ｊ）から線形アドレス空間の位置へのマッピングを、配列のベースアドレスと、配列へのオフセットを指定する１次関数の合計として計算する必要がない。すなわち、直線オフセットマッピング（ＬＯＭ（linear-offset mapping））を使用する必要がない。
【００１７】
その代わり、本発明の実施の形態は、データ構造体（例えば、配列）に記憶することができるデータの特定の「ライブ」要素を特定する処理と、適切なオブジェクトコードを生成して、このような必要なデータを容易にアクセス可能な場所またはバッファで利用可能にする処理とを含むことができる。容易にアクセス可能な場所またはバッファは、メインメモリ、キャッシュ、スクラッチパッドメモリ（ＳＰＭ）等である。配列の要素等のデータが、或る後の時点で読み出される値であるか、または、そのような値を記憶する場合に、そのデータは、或る時点で「ライブ」であるとみなすことができる。したがって、本発明の実施の形態では、配列によって消費されるメモリロケーションの個数を、配列要素の個数よりもはるかに少なくすることができる。したがって、複数の配列要素を同じメモリワードにマッピングすることができる。メモリの時分割使用を実施するために、任意の２つの配列要素が同時にライブである場合に、それら２つの配列要素が同じメモリロケーションに配置されないように、計算のスケジュールおよび配列要素のメモリロケーションへのマッピングを定式化することができる。物理メモリを共有することによって、プログラムデータを記憶するためのハードウェアメモリの使用がより小さくなり、それによって、ハードウェアコストが削減される。さらに、通常は共にサイズが制限されるキャッシュおよびＳＰＭを含むメモリ使用がより効率的になる。
【００１８】
本発明の一実施の形態は、とりわけ専用ハードウェアプロセッサのパイプラインを使用して高性能を必要とする用途に特に適用することができる。ハードウェアパイプラインの自動設計ツールは、最小のハードウェアコストで必要な性能レベルを達成するように試みる。ハードウェアコストを最小にするために、自動化設計ツールは、バッファおよびスクラッチパッドメモリを効率的に利用すべきである。本発明の一実施の形態は、自動化設計ツールが、プロセッサまたはプロセッサのパイプラインから成るハードウェアの一実施態様において所与の性能レベルを達成するのに必要なハードウェアメモリおよびレジスタの量を削減できる方法を提供する。同時に出願された「Method And System For The Design Of Pipelines Of Processors」という発明の名称の関連した米国特許出願第（代理人整理番号第１００１１０５５７−１号）は、本発明のバッファメモリ最小化方法を使用できるプロセッサパイプライン設計方法を記載している。
【００１９】
図１は、本発明の一実施の形態に準拠したコンピュータ１００の詳細図を示している。
このコンピュータ１００は、メインメモリ１０１、バッファメモリ１０３（例えば、キャッシュ、ＳＰＭ等）、２次記憶デバイス１０４、中央処理装置（ＣＰＵ）１０６、ビデオ表示装置１０７、および入出力デバイス１０８を含む。これらはシステムバスによって接続されている。メインメモリ１０１はコンパイラ１０２を記憶する。コンパイラ１０２は、２次記憶デバイス１０４に記憶されたソースコード１０５に処理を行い、実行可能オブジェクトコードを生成することができる。簡略化のために、例えばリンクおよびロードを含む関連機能が必要に応じて実行されて、実行可能オブジェクトモジュールが提供されるものと仮定する。したがって、メモリ割り当ては、ＳＰＭを含めて、ソフトウェアおよび他のシステムの組み合わせによって実行することができる。このソフトウェアおよび他のシステムには、コンパイラ、リンカ、ローダ、専用ユーティリティ等が含まれるが、これらに限定されるものではない。
【００２０】
本発明の一実施の形態と一致した方法およびシステムと共に使用するのに適したコンパイラの一例は、任意の一般的なＣコンパイラである。本発明の一実施の形態と一致した方法およびシステムと共に使用するのに適したアーキテクチャ合成プログラムの一例は、ＨＰ  ＬａｂｓのＰＩＣＯシステムである。このＰＩＣＯシステムは、所与の機能を実施するのに必要なメモリハードウェアの量を最小にする技法を使用することができる。コンパイラは、本発明による機能を提供して、例えばメモリの時分割使用といったインテリジェントなメモリの使用を可能にする適切なオブジェクトコード（オブジェクトコードファイル（複数可）および／またはオブジェクトモジュール（複数可）ならびにロードモジュール）を自動的に生成することができる。配列を記憶するのに必要なメインメモリの量を最小にすることによって、必要なキャッシュの量も削減されるので、コンパイラはさらに利益を得る。２次記憶デバイス１０４はソースコード１０５を収容することができる。ソースコード１０５は、Ｃプログラミング言語等の高級言語で記述されたプログラムとすることができる。ソースコード１０５はループネストを含み、データ配列は、それらのループネスト内で（すなわち、それらのループネスト内に含まれる命令に応答して）アクセス（読み出しおよび書き込み）される。
【００２１】
２次記憶デバイス１０４は、オブジェクトモジュールをさらに記憶することができる。このオブジェクトモジュールは、ライブラリモジュールおよび実行可能モジュール、または、特にオペレーションのページモードが大きなプログラムの実行に使用される場合にはそれらの一部を含む。
【００２２】
本発明と一致した方法およびシステムと共に使用するのに適したコンパイラの一例は、通常はソースコード命令の形のプログラムを解析する機能を含み、データを記憶するのに使用される配列等の記憶構造体を識別することができる。次に、コンパイラは、同時にライブ要素の部分集合を決定するように動作することができ、データを時分割メモリアドレス空間に再マッピングすることができる。
【００２３】
図２Ａおよび図２Ｂは、メインメモリ１０１およびバッファメモリ１０３に記憶されたデータ構造体のロケーションを示すデータマップのより詳細な図を示している。メインメモリ１０１は、ＣＰＵ１０６によって処理される全要素を含んだオリジナル配列２０１を収容することができる。オリジナル配列２０１は、どの特定のプロセッサ時刻またはイベント時刻においても、ライブ要素および休止状態要素の双方を含む。バッファメモリ１０３は、理想的にはＣＰＵによって処理されるオリジナル配列２０１からの要素の部分集合を含んだホスト配列２０２を収容することができる。この部分集合は、任意の特定のプログラム実行期間または特定の時間の間（すなわち、ループネストに通常通り入って出て行くと仮定する）、一定のループネストによってアクセスされると実際に予想される、オリジナル配列２０１のライブ要素のみ等である。
【００２４】
本発明の一実施の形態によると、或る機能が時間依存マッピングを提供する。この時間依存マッピングは、オリジナル配列２０１の要素にアクセスするのに使用されるより大きなアドレス空間から、ホスト配列２０２に要素の部分集合を記憶するより小さな時分割アドレス空間へのマッピングである。この部分集合は、アクセスされるオリジナル配列２０１のライブ要素を含む一方、このような期間中、使用されない要素、すなわちオリジナル配列２０１の休止状態要素、を排除するか、または、その要素数を最小にしたものである。
【００２５】
説明したように、ホスト配列２０２の要素は、オリジナル配列２０１の要素よりも高速に処理することができる。その理由は、ＣＰＵ１０６が、メインメモリ１０１とインターフェースすることもなく、共有システムバス設備へのアクセスを得るために競争することもなく、バッファメモリ１０３に直接アクセスできるからである。バッファメモリ１０３のホスト配列は、オリジナル配列のインデックスからホスト配列のインデックスへの時間依存マッピング（time-dependent mapping）の適切な選択肢を選択することによってできるだけ小さくされる。また、コンパイラが、メインメモリ１０１ではなくバッファメモリ１０３からの要素を使用できる（すなわち、その要素を参照するオブジェクトモジュールを生成できる）ように、オリジナル配列２０１からホスト配列２０２へ要素を移動させることもできる。ＣＰＵ１０６が、例えばループネストといった任意の所与のコードセグメントの要素を処理した後は、それらの要素をメインメモリ１０１に戻すことができる。コンパイラは、例えばオブジェクトモジュールの一部として、適切なデータ転送を行う適切なコードを生成し、メインメモリ１０１とバッファメモリ１０３との間で移動を行う。
【００２６】
一例として、Ｃプログラムの単一のｎ次元配列を考える。この配列の各要素は、正確に判明した寿命を有することができる。すなわち、データがプログラム命令によってその配列に最初に記憶された最初の時刻または最初のイベントと、そのデータが命令によってアクセスされる最終時刻とを有することができる。（最初および最終という用語は、考慮の対象となっている特定のコードセグメントに関して使用されることに留意されたい。したがって、特定のデータ要素の一生は、プログラム全体よりも小さくなることがある特定の１組の命令のストレージ要件に関して決定される。）
【００２７】
場合によって、コンパイラ時またはハードウェア合成時に、配列の要素等の１組のデータ要素のそれぞれに対するすべてのランタイム読み出しアクセスおよびランタイム書き込みアクセスの組を知ることができない場合がある。この不確実性は、例えば、データに依存した分岐が原因の場合もあるし、１組の計算について動的に決定されるスケジュールを使用することが原因の場合もあるし、他の或る理由による場合もある。しかしながら、このような状況であっても、各データ要素について、最早に起こり得る書き込み時刻および最後に起こり得る読み出し時刻を確かめることは可能な場合がある。これらの２つの時刻は、当該データ要素の寿命の上限および下限を提供する。本発明の一実施の形態は、データ要素の期間または間隔がその実際の寿命を含むと判明している各データ要素の潜在的な寿命（コンパイル時に判明する）を使用することができる。
【００２８】
要素が読み出されるクロックサイクルおよび要素が書き込まれるクロックサイクルが判明すると、所与の要素が「フル」になって意味のある値を保持する時間間隔、および、所与の要素が空になってプログラムの振る舞いがこの要素がどの値を保持するかに全く依存しない時間を計算することが可能になる。（用語「時間」は、本明細書では、処理およびメモリ使用に関連したイベントの実際の機構、マシン機構、および他の時間的機構を包含するその最も広い意味で使用されることに留意されたい。配列インデックス「ａ」から物理メモリロケーション「ａｄｄｒ」へのマッピングは、決定されると、以下の形で定義することができる。
【００２９】
モジュロオフセットマッピング（ＭＯＭ（Modulo-offset mapping））：ａｄｄｒ＝ｂａｓｅ＿ａｄｒｅｓｓ＋ｏｆｆｓｅｔ（ベースアドレス＋オフセット）
【００３０】
オフセット計算：ｏｆｆｓｅｔ＝Ｍ１（Ｍ２ａ  ｍｏｄ  ｒ）
【００３１】
ＭＯＭにおいて、「ａ」は、配列インデックスのｎ次元整数ベクトルである。マッピングのパラメータは、１行ｍ列整数行列Ｍ１、ｍ行ｎ列整数行列Ｍ２、およびｍ元列ベクトルｒ＝（ｒ１，…，ｒｍ）Ｔである。（上付き文字Ｔは、行列の転置を示す。本発明者等は、列ベクトルとｎ行１列行列とを区別せず、行ベクトルと１行ｎ列行列も区別しない。）
【００３２】
ＭＯＭが使用される場合、ｍｏｄオペレーションは、ベクトルｒの対応する要素を基数として使用して、ベクトル（Ｍ２ａ）の要素に対して実行される。したがって、ｍモジュロオペレーションが実行されることになる。
【００３３】
本発明の一態様によると、整数パラメータｍの値は配列ｎの次元に等しい。
【００３４】
本発明の別の態様によると、整数パラメータｍの値は１であり、この場合、整数行列Ｍ１も１に等しい。
【００３５】
ＭＯＭが使用される場合、ライブデータを記憶するのに使用される物理メモリ（例えば、バッファ、キャッシュ、ＳＰＭ等）はサイズｓを有する。このサイズｓは、ベクトルｒの要素の積となるように定義される。ＭＯＭでは、（Ｍ２ａ  ｍｏｄ  ｒ）が整数ベクトルであり、その値は、範囲がｒ１，ｒ２，…，ｒｍであり、したがって、面積がｓに等しい長方形に含まれることから、これは事実である。行列Ｍ１は、０とｓ−１との間で変動する１次元オフセットへのこのベクトルの簡単な線形オフセットマップを実施する。本発明のこの実施の形態は、ＭＯＭの形のマッピングを使用し、従来の線形オフセットマッピングの形（ＬＯＭ）を使用しないことに留意されたい。
【００３６】
特別な場合（後に説明）を除いて、ＭＯＭの合法的パラメータを決定する「素朴な」方法が存在するが、この方法は、不十分な結果を生み出す可能性がある。（本明細書で使用されるように、用語「素朴な」は、限られた用途を有するＭＯＭパラメータを決定する簡単な方法を指す。）詳細には、ＣやＦｏｒｔｒａｎのマッピング等、配列軸（array axes）の順列（permutation）から得られた線形オフセット関数を有する線形オフセットマッピングを考える。各時点ｔについて、所与のＬＯＭの下で、既知のオフセットを有する、その時刻においてライブである１組の配列要素が存在する。マッピングのパラメータを得る簡単な手法は、時刻ｔでライブである最大オフセットと時刻ｔでライブである最小オフセットとの差を計算することを含むことができる。この差は、時刻ｔにおけるライブ範囲を表す。次に、ｍを１に等しいとする。パラメータｒ１は、ライブの範囲の全時間にわたって最大に等しくなるように選択することができる。次に、パラメータＭ２はＬＯＭと同じ線形関数に等しく、Ｍ１は１である。この結果、ｓが配列の境界の積よりも決して大きくない場合にＭＯＭは有効になり、それによって、ＬＯＭマッピングを比較して、メモリ記憶空間が多少節減される。しかしながら、以下に示すように、この手法は、次のように与えられるより洗練された手順によって達成可能なものと比較して、十分でない結果になることがある。
【００３７】
以下の説明は、束（格子：lattice）として知られている数学的オブジェクトのクラスを参照する。束は、基底集合の整数線形結合のすべてから成る（ｎタプルの実数のような）ベクトルの集合である。この基底集合は、ベクトルの線形独立集合である。
【００３８】
あらゆる束は、単位セル（単位胞体）（unit cell）を決定し、この単位セルのボリュームは、その束の行列式と呼ばれる。束の基底集合が行列Ｂの列として配列される場合、その束の行列式は正方行列ＢＴＢの行列式に等しくなる。
【００３９】
Ｂが、線形独立列を有する行列である場合、その列は、束の基底（格子基底：lattice basis）を形成する。本発明者等は、Ｂの列が基底集合を形成する束をｌａｔｔｉｃｅ（Ｂ）によって表記することにする。
【００４０】
図３のフローチャートを参照して、メモリ使用を最適化する方法の一実施の形態がステップ３０１で開始する。ステップ３０２において、プログラム命令の特定のセグメントによって定義され、かつ／または、使用される各配列を処理するループに入る。ステップ３０３において、各配列を最小化するために、同時にライブである配列要素が決定される。ステップ３０４は、同時にライブである要素の配列インデックスの差の集合を決定する。ここでは、この同時にライブである要素の配列インデックスの差の集合を部分集合として含む集合を決定することが可能である。ステップ３０５において、差の集合を含むポリトープ（polytope）を決定することができる。このポリトープから、ゼロベクトル以外に当該ポリトープと共通したベクトルを有しない整数束の基底が、ステップ３０６において決定される。他の実施態様では、ステップ３０６において決定された整数束が、ステップ３０５においてオプションとして決定されたポリトープを参照するのではなく、ステップ３０４において決定された差の集合を直接使用することによって決定される。マッピングによって必要とされるストレージ（複数可）の量は、この束の行列式に等しくなる。ステップ３０７は、列が束の基底である行列から、マッピングのパラメータＭ１およびＭ２ならびにｒを決定する。配列インデックスがａである配列要素のアドレスを生成するために、プログラムのソースコードのマシン（またはオブジェクト）コードへのコンパイルをステップ３０８に従って実施することができる。これらのアドレスは、ステップ３０７で決定されたパラメータＭ１およびＭ２ならびにｒを有する式（ＭＯＭ）を使用することによって生成される。ステップ３０９において、この配列を保持するストレージのｓ個のセルのみの割り当てが実行される。ここで、ｓはｒの要素の積として計算され、これは、ステップ３０６で選択された束の行列式と等しい。この値は、オフセットの範囲を収容するのに十分である。次に、処理はステップ３１０において終了する。
【００４１】
あらゆる時点で同時にライブである２つの要素を同じメモリセルにマッピングすることができないので、同時にライブである配列インデックスａ１およびａ２を有するどの２つの配列要素も、異なるアドレスにマッピングしなければならない。したがって、ＣＳを同時にライブである要素の対（ａ１，ａ２）の集合とする。定義により、ＣＳは対称関係である。すなわち、（ａ１，ａ２）は、（ａ２，ａ１）もＣＳに属する場合に限ってＣＳに属する。ＤＣＳはＣＳの要素の差の集合である。
【００４２】
ＤＣＳ＝｛ｘ｜ｘ＝ａ１−ａ２，（ａ１，ａ２）はＣＳに属する｝。ＣＳの対称性により、ＤＣＳは、０に関して対称である。すなわち、ｄがＤＣＳに属する場合に、−ｄもＤＣＳに属する。
【００４３】
例えば、図４に示すプログラムが与えられ、パイプラインを形成するネスト１およびネスト２について、１０個の並列処理エレメントを使用してこのプログラムを実施することが望ましいと仮定し、ループネスト１の繰り返し（ｉ，ｊ）の実行時刻がｔｉｍｅ１（ｉ，ｊ）＝ｉ＋ｊとなるように、ループネスト１の繰り返しがスケジュールされると仮定する。ループネスト２の繰り返しは、ｔｉｍｅ２（ｉ，ｊ）＝ｉ＋ｊ＋１となるようにスケジュールされる。この場合、その結果として、配列ｘの要素ａ＝（ｉ，ｊ）が時刻（ｉ＋ｊ）で書き込まれ、かつ、時刻（ｉ＋ｊ＋１）で読み出され、それによって、その寿命が定義される。したがって、要素（ｉ，ｊ）および（ｉ´，ｊ´）は、
（１）  ｜（ｉ＋ｊ）−（ｉ´＋ｊ´）｜≦１
である場合に限って同時にライブである。
この不等式は、配列境界
（２）  ０≦ｉ，ｉ´≦９，０≦ｊ，ｊ´≦９
と共に、衝突する配列インデックスベクトルの対の集合ＣＳを定義する。集合ＤＣＳは、２次元ベクトルの集合であることに留意されたい。（１）が
（３）  ｜（ｉ−ｉ´）＋（ｊ−ｊ´）｜≦１
と同じであることに気付くことにより、その結果として、ＤＣＳは、この場合、
（４）  −１≦（ｄｉ＋ｄｊ）≦１
かつ
（５）−９≦ｄｉ≦９，−９≦ｄｊ≦９
の２次元ベクトルｄ＝（ｄｉ，ｄｊ）の集合から成る。
【００４４】
プログラムの各配列は、それ自身のＣＳ関係およびＤＣＳ集合を有することに留意されたい。また、配列の読み出し時刻および書き込み時刻が未知である場合に、そのＣＳ関係は、配列境界を個別に満たす配列インデックスのすべての対を含むことになることにも留意されたい。この場合、ＤＣＳ集合は、上記式（５）の上限および下限等の上限および下限によって規定される配列インデックスのすべての差の集合から成る。
【００４５】
ベクトルの要素のアフィン関数に対して不等式の系を満たすすべてのベクトルから成る集合（この例で定義された集合等）は、ポリヘドラ（polyhedra）として知られており、これらの集合は、有界である場合にポリトープと呼ばれる。例えば、２つの次元のあらゆるポリゴンはポリトープである。
【００４６】
最初に、ＤＣＳがポリトープであると仮定することができる。ＤＣＳがポリトープでない場合、当該ＤＣＳは、そのＤＣＳを含む任意のポリトープと置き換えることができる。（配列インデックスａは配列境界によって制限されるので、ＤＣＳも同様に制限され、ポリトープ内に囲むことができることに留意されたい。）
【００４７】
以下の解説では、ＭＯＭのパラメータＭ１およびＭ２ならびにｒを決定する可能な一方法を説明する。
【００４８】
図３のステップ３０６を再び参照して、整数束は次のように形成される。ゼロ対称のポリトープＳｙｍＰｏｌが与えられると、基底Ｂを有する順序長方形境界束（ＯＲＢＬ（Ordered Rectangular Bounding Lattice））を求めるヒューリスティックアルゴリズムが存在する。このＯＲＢＬは、以下の特別な特性を有する束である。
【００４９】
１．  ｌａｔｔｉｃｅ（Ｂ）およびＳｙｍＰｏｌは、共通の起点（origin）（ゼロベクトル）のみを有する。
【００５０】
２．  基底集合Ｂ＝｛ｂ１，ｂ２，…，ｂｎ｝は、標準基底の倍数から成る。すなわち、これが長方形束である。したがって、ｌａｔｔｉｃｅ（Ｂ）は、（Ｒ１×ｙ１，Ｒ２×ｙ２，…，Ｒｎ×ｙｎ）の形のすべてのベクトルから成る。ここで、Ｒ１，Ｒ２，…，Ｒｎは所与の整数であり、ｙ１，ｙ２，…は任意の整数である。
【００５１】
３．  最大で軸の順列までは、Ｌの基底Ｂはこれらの特性を有する。
【００５２】
３．ａ．  ｂ１＝Ｒ１×ｅ１である。ここで、ｅ１＝（１，０，…，０）は標準基底の最初の要素であり、Ｒ１は正の整数である。
【００５３】
３．ｂ．  ＳｙｍＰｏｌのすべてのｘ＝（ｘ１，ｘ２，…，ｘｎ）について、Ｒ１＞｜ｘ１｜である。すなわち、ＳｙｍＰｏｌのすべては、−Ｒ１＜ｘ１＜Ｒ１を満たすストリップ（strip）に含まれる。
【００５４】
３．ｃ．  特性３．ａおよび３．ｂは、ｂ２，…，ｂｎ、および、ＳｙｍＰｏｌの超平面｛ｘ｜ｘ１＝０｝との交差によって与えられるｎ−１次元のポリトープにも当てはまる。
【００５５】
この証明は構成的である。すなわち、これは、ＳｙｍＰｏｌのＯＲＢＬについて、最も厳しい連続間隔アルゴリズム（successive tightest interval algorithm）と呼ばれる、ＯＲＢＬを構成するプロセスである。換言すると、最初に、ＳｙｍＰｏｌの任意の要素のｘ１成分よりも大きな最小の整数としてＲ１を求める。次に、ＳｙｍＰｏｌを超平面｛ｘ｜ｘ１＝０｝への射影を使用する再帰的呼び出しによって、Ｂの残りの要素を構成する。特性２および３が自明に当てはまることを実証することができる。特性１も、以下のように正しく当てはまる。
【００５６】
Ｌを２および３が当てはまる任意の束とする。
【００５７】
ｘをＳｙｍＰｏｌの要素とする。ＳｙｍＰｏｌは特性３．ｂを満たすので、ｘ１＝０でない場合に、ｘは束に属することはできない。したがって、ｘ１は０でなければならない。
【００５８】
再帰的に続けると、ｘ２、ｘ３等も０であることが示される。したがって、ＬおよびＳｙｍＰｏｌは、共通に０ベクトルのみを有し、これが、本発明者等が証明しようとしたものである。
【００５９】
これらの理由から、軸のあらゆる順列について、最も厳しい連続間隔アルゴリズムを使用してＯＲＢＬを求めることができる。さらに、可能な順列のすべてを調べて、上述した最も厳しい連続間隔アルゴリズムを使用することによってＯＲＢＬを求めることもできる。次に、最小の行列式を有するＯＲＢＬをもたらす順列を選択することが、唯一、好都合である。
【００６０】
２つの配列インデックスａおよびａ´が、オーバーラップする寿命を有し（その結果、（ａ−ａ´）がＤＣＳに属する）、かつ、Ｒ＝（Ｒ１，Ｒ２，…，Ｒｎ）である場合、ａ  ｍｏｄ  Ｒは、ａ´  ｍｏｄ  Ｒに等しくないことにさらに留意されたい。同様に、ａがａ´に等しくない場合に、（ａ−ａ´）  ｍｏｄ  Ｒは０に等しくない。
【００６１】
ステップ３０７を参照して、Ｍ１およびＭ２ならびにｒは、ＯＲＢＬから決定することができ、これらは、メモリ所要量を最小にするのに使用することができる。詳細には、ＯＲＢＬは、ｎ個の次元の順序付けおよびｎ次元ベクトルＲによって定義される。
【００６２】
ｍ＝１とする。ｒ１＝ｐｒｏｄ（Ｒ）として、ｒ＝（ｒ１）とする。（これは、使用されるメモリセルの個数である。）
【００６３】
軸の順列またはＯＲＢＬが（１，２，…，ｎ）であると仮定すると、以下の関係が適用される。
【００６４】
ｌｉｎｅａｒ＿ｏｆｆｓｅｔ（ａ）（線形オフセット（ａ））＝（ａ１＋Ｒ１×（ａ２＋Ｒ２×（ａ３…）…）  ｍｏｄ  ｒ
【００６５】
パラメータＭ２は以下の式によって与えられるようにされる。
【００６６】
Ｍ２＝（１，Ｒ１，Ｒ１×Ｒ２，…，Ｒ１×Ｒ２×…×Ｒ（ｎ−１））
【００６７】
順列が１，２，…，ｎではなく、ｐ１，ｐ２，…，ｐｎである場合、Ｍ２（ｐ１）＝１、Ｍ２（ｐ２）＝Ｒ（ｐ１）、Ｍ２（ｐ３）＝Ｒ（ｐ２）×Ｍ２（ｐ１）、以下同様となる。
【００６８】
ＭＯＭのパラメータを取得するこの特定の方法を完了するために、パラメータＭ１は整数１とされる。
【００６９】
これによって、ステップ３０７は完了する。このステップ３０７は、ＯＲＢＬから、ステップ３０８で使用されるマッピングの３つのパラメータＭ１およびＭ２ならびにｒに至るプロセスである。
【００７０】
ＯＲＢＬ方法は、一般に、最初に詳述した素朴な方法よりも改善された結果を提供することに留意されたい。上記で与えた例を取り上げる。ＬＯＭには、ＦｏｒｔｒａｎスタイルまたはＣスタイルのいずれかの２つの選択肢がある。いずれの場合も、最大のライブ範囲は８９である。ＬＯＭを単独で使用すると、１００個のメモリロケーションが必要となる。ＬＯＭが生成したアドレス空間におけるライブ要素の集合の範囲を使用することによってパラメータを求める「素朴な」方法を使用することにより生成された「ＭＯＭ」を使用すると、８９個のメモリロケーションのみが必要とされる。一方、ＯＲＢＬを使用すると、行列式２０の束が特定され、これは、この方法で必要とされるメモリセルの個数である。時刻１０において、１９個のライブな配列要素が存在するので、２０は、メモリ所要量の可能な最良の最小化の１つに含まれる。
【００７１】
本発明によるこの方法を使用することによって、（ＬＯＭ）の形の標準的なマッピングに代わるものとして使用可能な（ＭＯＭ）の形の優れたマッピングが得られる。この方法は、配列の要素に対する判明しているアクセス（読み出しおよび書き込み）スケジュールを利用する。本発明の方法によるマッピングのクラス（ＭＯＭ）を使用して、マッピングのパラメータを決定することにより、線形オフセットを含めて、他の方法のいずれによるよりもはるかに少ないメモリセルを使用して配列を記憶することが可能になる。
【００７２】
図５は、本発明による方法の別の実施の形態を示すのに使用される。この図を参照して、この方法はステップ５０１で開始し、ステップ５０２において、対象となるプログラムのすべての配列が特定される。ステップ５０３および５０４は、このような各配列および各配列の各要素を調べて、それぞれが書き込まれる時刻およびそれぞれが読み出される時刻をステップ５０５で求める。配列の任意の２つの要素について、それらが同時に「ライブ」であるかどうかを判断するために、代替的な方法も使用できることに留意されたい。例示のため、プログラムは、ｉｎｔ  Ａ［１００］［１００］という文によって宣言される配列Ａを使用すると仮定する。
【００７３】
したがって、Ａは１０，０００個の要素から成り、これらの要素のそれぞれは、ｉｎｔ［ｅｇｅｒ ｔｙｐｅ］である。
【００７４】
配列Ａの要素は、それぞれ、判明している時刻に書き込まれる。詳細には、要素Ａ［ｉ］［ｊ］は、時刻ｉ＋ｊに書き込まれる。それ以前に、この要素は判明した意味のある内容を有しない。同様に、要素は判明している時刻に読み出される。すなわち、要素Ａ［ｉ］［ｊ］は、時刻ｉ＋ｊ＋１で読み出される。その時刻の後、その内容は無関係なものとなる。したがって、例えば、要素Ａ［２］［３］は、時刻（クロックサイクル）５で書き込まれ、時刻６で読み出される。５から６の時間がこの要素の寿命である。要素Ａ［２］［４］は、６から７の寿命を有し、要素Ａ［２］［５］は７から８の寿命を有する。
【００７５】
２つの要素がオーバーラップしない（または交わらない）寿命を有する場合、それら要素は、同じ物理ストレージロケーションを共有できることに留意されたい。
【００７６】
ステップ５０６において、このような各配列について、オーバーラップした寿命を有する要素の対の集合の表現が見つけられる。これは、集合ＣＳ（競合集合（Conflict Set））と呼ばれ、ストレージを共有できない要素の集合を特定するものである。この例では、Ａ［ｉ１］［ｊ１］およびＡ［ｉ２］［ｊ２］は、（ｉ１＋ｊ１）と（ｉ２＋ｊ２）との差が０または１または−１である場合にオーバーラップした寿命を有する。そうでない場合には、これらの要素は交わらない寿命を有する。本発明の一実施の形態によると、この集合は、要素のインデックスを含んだ線形不等式の系を使用して表すことができる。
【００７７】
ステップ５０７は、集合ＤＣＳと呼ばれるオーバーラップした寿命を有する要素のインデックスの差の集合を求める。換言すると、インデックスベクトル（ａ，ｂ）の対がＣＳに属する場合、それらの差は、ベクトルｄ＝（ａ−ｂ）となり、ＤＳに属する。−ｄ＝（ｂ−ａ）も同様である。この例では、ＤＣＳは、平面上のポリゴンに存在する整数ベクトルの集合である。図６を参照して、図の左側に列挙した６つの頂点の集合が与えられると、その結果のポリゴンは、図の右のグラフによって示される。本発明の一実施の形態によると、ＤＣＳは、線形不等式の集合によって定義されたポリトープ（ｎ次元ポリゴン）として表すことができる。本発明の別の実施の形態によると、部分集合としてＤＣＳを含むポリトープをＤＣＳの代わりに使用することができる。
【００７８】
ステップ５０８は、小さな行列式を有する整数束であって、ゼロベクトルを除いて集合ＤＣＳと共通した点を有しない整数束を求める。この束は、Ｌと呼ばれ、その束の基底である列を有するｎ行ｎ列正方行列Ｂによって表すことができる。配列の次元は、ｎによって与えられる。ｎは、この例では２に等しい。したがって、Ｌは以下の基底を有する束であると解釈することができる。
【００７９】
2006505058.tif 000003
【００８０】
この基底は行列式２００を有する束である。
【００８１】
束Ｌの行列式ｓに等しい物理メモリの量は、２つの要素の寿命がオーバーラップする場合に、それらの要素がストレージを共有しない状態で、配列の要素を記憶するのに使用される。ステップ５０９において、Ｌの行列式が計算され、計算された行列式に基づいて、いくつかの記憶セルが割り当てられる。
【００８２】
前述したように、ストレージロケーションを生成する専用で低コストの方法であって、小さな行列式を有するＯＲＢＬを構成することによって機能する方法がある。また、配列のライブ要素を記憶するのに必要なメモリ量を大きく削減できる点でより効率的である、汎用ではあるが高コストの方法もある。すなわち、最初の簡単な方法は、ＯＲＢＬの構造を有する束といった一部の束についてのみ機能する。一方、汎用であるが高コストの方法は、ステップ５０８でどの束が選択されても、その束がゼロ以外に集合ＤＣＳと共通した点を有しない限り機能する。したがって、ステップ５１０において、束は、ストレージロケーションを生成する高速な専用方法を利用できるかどうかについて調べるために検査される。利用できる場合には、処理はステップ５１２に続く。詳細には、この簡略化された方法は、束の基底がこの例の行列Ｂのように対角行列を形成し、さらに、対角線上の第１の要素が、ＤＣＳの任意の要素の第１（ｄ１）の同等物（coordinate）よりも大きく、第２の要素が、（ｄ１＝０）によって定義された線に沿って求められたＤＣＳの部分の任意の要素よりも大きく、以下についても同様の場合に機能する。
【００８３】
ステップ５１２において、ＭＯＭのパラメータが専用方法について決定される。整数ｍは１であり、行列Ｍ１も１に等しく、ベクトルｒは１つの要素、すなわちステップ５０９で計算されたｓ（束の行列式）を有し、行列Ｍ２は束の基底から計算される。
【００８４】
基底が行列Ｂである束では、専用方法の使用が可能である。この簡単な場合では、配列要素Ａ［ｉ］［ｊ］が、サイズ２００の１次元メモリ配列のストレージロケーションオフセット＝（ｉ＋１００ｊ）  ｍｏｄ  ２００に記憶される。ｎ次元の場合には、配列インデックスベクトルは、
ＦａｓｔＯｆｆｓｅｔ（ａ）（高速オフセット（ａ））＝Ｍ２ａ  ｍｏｄ  ｒ＝ａ１＋Ｒ１×（ａ２＋Ｒ２×（ａ３＋…Ｒ（ｎ−１）ａｎ）…）  ｍｏｄ  ｓ
となるようなａ＝（ａ１，ａ２，…，ａｎ）と表記される。ここで、基底行列Ｂの対角要素はＲ１，Ｒ２，…，Ｒｎであり、ｓは束の行列式であり、Ｒ１，Ｒ２，…，Ｒｎの積に等しい。
【００８５】
ステップ５１２の簡単な手法が使用できない場合には、ステップ５１３〜５１８によって提供される、より一般的な手法を利用することができる。ストレージロケーションを求めるこのより一般的な方法は、どの束が選択されていようが、この場合も、その束がゼロ以外に集合ＤＣＳと共通したものを有しない限り機能する。
【００８６】
ステップ５１３を参照して、ｎ行ｎ列行列Ｂの形の束の基底が与えられると、ＭＯＭのパラメータ（これらのパラメータは、整数ｍ、行列Ｍ１、行列Ｍ２、およびベクトルｒを含む）が求められ、インデックスベクトルで配列要素に割り当てられたストレージオフセットが、これらのパラメータを有するＭＯＭによって計算される。これらのパラメータは、以下のステップに従って求められる。
【００８７】
ステップ５１４：Ｍ２およびｒを求めるために、行列Ｂのスミス標準形（Smith Normal Form）（A.J. Shrijver著「Theory of Linear and Integer Programming」, John Wiley and Sons, 1986を参照されたい。この文献は、その全内容が参照により本明細書に援用される。）が計算される。行列Ｂのスミス標準形は、以下のように、Ｂを因数分解したものである。
Ｂ＝Ｑ１ＳＱ２
ここで、Ｓは対角行列であり、Ｑ１およびＱ２は、整数の逆数（integer inverse）を有する整数行列である。
【００８８】
ステップ５１５：行列Ｍ２が、Ｑ１の逆行列を計算することによって得られる。ベクトルｒは、Ｓの対角要素によって与えられる。行列Ｍ１は、形状がｒによって与えられる配列の線形化を介して決定される。
【００８９】
次に、ステップ５１６〜５１８に示すように、ｎに等しい整数ｍを有するモジュロオフセットマッピング（ＭＯＭ）式を使用して、プログラムがコンパイルされる。
【００９０】
ステップ５１６：ＳｌｏｗＯｆｆｓｅｔ（スローオフセット）．１  ａ´＝ｒｅｄｕｃｅｄ＿ｉｎｄｅｘ＿ｖｅｃｔｏｒ（ａ）（削減されたインデックスベクトル（ａ））＝Ｍ２ａとなる。（すなわち、行列Ｍ２がベクトルａと乗算されて、ベクトルａ´が生成される。）
【００９１】
ステップ５１７：ＳｌｏｗＯｆｆｓｅｔ．２  ａ″＝ｍｏｄｕｌｏ＿ｒｅｄｕｃｅｄ＿ｖｅｃｔｏｒ（ａ´）＝ａ´  ｍｏｄ  ｒとなる。
【００９２】
（すなわち、ａ´のモジュロの各要素について、ｒの対応する要素が求められ、ａ″の対応する要素が得られる。）
【００９３】
ステップ５１８：ＳｌｏｗＯｆｆｓｅｔ．３  次元がｒによって与えられる配列について、インデックスベクトルａ″を標準的な方法で線形化する。これを行う可能な一方法では、オフセットは次のように表される。
ｏｆｆｓｅｔ＝ａ″１＋ｒ１×（ａ″２＋ｒ２×（ａ″３＋…＋ｒ（ｎ−１）×ａ″ｎ）…）
【００９４】
この方法は、所与の配列インデックスベクトルａ″のオフセットを計算するコストに関して僅かに低速である。その理由は、ａをＭ２と乗算し、次いで、いくつかのモジュロオペレーションを行わなければならないのに対して、専用高速方法は１つだけのｍｏｄオペレーションのみを必要とするからである。
【００９５】
パラメータＭ２およびｒが上述の通りであり、かつ、パラメータＭ１が１行ｎ列行列（１，ｒ１，ｒ１ｒ２，…，ｒ１ｒ２ｒ（ｎ−１））であるＭＯＭのこのマッピングに留意すべきである。
【００９６】
このプロセスはステップ５１９で終了する。
【図面の簡単な説明】
【００９７】
【図１】本発明の一実施の形態と一致したコンピュータシステムのブロック図である。
【図２Ａ】図１に示すメインメモリおよびスクラッチパッドメモリ（ＳＰＭ）メモリの形のバッファのより詳細な図である。
【図２Ｂ】図１に示すメインメモリおよびスクラッチパッドメモリ（ＳＰＭ）メモリの形のバッファのより詳細な図である。
【図３】本発明の一実施の形態による、ソースコードのコンパイル時に実行されるステップのフローチャートである。
【図４】本発明の一実施の形態による、列挙された頂点の集合によって規定された入力配列により占有されるアドレス空間の図である。
【図５】プログラムのいくつかの部分の間に必要とされるデータ記憶資源を特定し、プロセッサ等のデータコンシューマによってすぐにアクセスできるようにバッファまたはスクラッチパッドメモリにデータのライブ部分集合を記憶する、本発明の一実施の形態による方法のフローチャートである。
【図６】本発明の一実施の形態による、プログラムを実施するプログラムソースコードの一例である。
【符号の説明】
【００９８】
１００  コンピュータ
１０１  メインメモリ
１０２  コンパイラ
１０３  バッファメモリ
１０４  ２次記憶デバイス
１０５  ソースコード
１０６  ＣＰＵ
１０７  ビデオ表示装置
１０８  Ｉ／Ｏデバイス
２０１  オリジナル配列
２０２  ホスト配列
【図１】
2006505058.tif 000004
【図２Ａ】
2006505058.tif 000005
【図２Ｂ】
2006505058.tif 000006
【図３】
2006505058.tif 000007
【図４】
2006505058.tif 000008
【図５】
2006505058.tif 000009
【図６】
2006505058.tif 000010
【国際調査報告】
2006505058.tif 000011
2006505058.tif 000012
2006505058.tif 000013
2006505058.tif 000014