(57)【要約】【課題】    【解決手段】  本発明に従った方法、システム、及び製品は、プログラムに関連する命令の実行を管理するメモリ命令マネージャを提供する。メモリ命令マネージャは、第一のグループ識別子をプログラムに関連する第一の命令とプログラムに関連する第二の命令とに割り当て、第一の命令の後で、第一のグループ識別子を有するメモリバリア命令を提供して、第一のメモリ命令が実行されるまで、プログラムに対するアクセスを有する一つ以上のプロセッサが第二のメモリ命令を実行するのを禁止されるようにする。【選択図】  図１
2005332387.tif 000002
【特許請求の範囲】
【請求項１】
プログラムに関連する複数の命令の実行を管理するデータ処理システムにおける方法であって、
前記複数の命令のうちの第一の命令の後に前記プログラムに現れる前記複数の命令のうちの一つ以上の命令に第一のグループ識別子を割り当てるステップと、
前記第一のグループ識別子とは異なる第二のグループ識別子を第一のメモリ命令に割り当てるステップと、
前記プログラムに対してアクセス可能な一以上のプロセッサが、前記メモリバリア命令に関連する前記第二のグループ識別子に従った順序で、前記プログラムの前記複数の命令を実行するよう、前記第一のメモリ命令に関連し且つ前記第二のグループ識別子を有するメモリバリア命令を提供するステップと、
を備える方法。
【請求項２】
請求項１記載の方法であって、
前記一以上のプロセッサは、前記第一の命令の前に前記第一のグループ識別子が割り当てられている前記一以上の命令を実行することが認められている間、前記第一の命令の前に前記第二の命令を実行することを禁止される、方法。
【請求項３】
請求項１記載の方法であって、更に、
前記第一の命令の前に前記プログラムに現れる前記命令のうちの第三の命令に第三のグループ識別子を割り当てるステップを備え、前記第二のグループ識別子を有する前記メモリバリア命令は、前記一以上のプロセッサに、前記第三の命令の前に前記第一の命令を実行させる、方法。
【請求項４】
請求項１記載の方法であって、
前記複数の命令は、少なくとも二つのクラスを含み、前記第一及び第二の命令と前記メモリバリア命令とは、前記第二のグループ識別子に従った前記少なくとも二つのクラス間の順序の制約を反映する、方法。
【請求項５】
請求項１記載の方法であって、
前記複数の命令は、少なくとも二つのクラスを含み、前記第一及び第二の命令と前記メモリバリア命令とは、前記第二のグループ識別子に従った前記少なくとも二つのクラスの一つにおける順序の制約を反映する、方法。
【請求項６】
請求項１記載の方法であって、
前記メモリバリア命令は、前記メモリバリア命令の前に前記プログラムに現れ、前記第二のグループ識別子を有する前記複数の命令のそれぞれを、前記メモリバリア命令の後で前記プログラムに現れる前記複数の命令の一つの前に、前記一以上のプロセッサに実行させる完了の制約を反映する、方法。
【請求項７】
請求項１記載の方法であって、
第二のグループ識別子を割り当てる前記ステップは、更に、
前記第二のグループ識別子を有する前記複数の命令の数を決定するステップと、
前記数が所定の値を上回るかを判断するステップと、
前記数が前記所定の値を上回らないと判断したことに応答して、前記第一のメモリ命令に前記第二のグループ識別子を割り当てるステップと、
を備える方法。
【請求項８】
プログラムに関連する複数のメモリ命令の実行を管理するデータ処理システムにおける方法であって、
前記複数のメモリ命令のうちの第一のメモリ命令の前に、前記メモリ命令のうちの第二のメモリ命令を実行することで、前記プログラムの並列性能が増加するかを判断するステップと、
前記第一のメモリ命令の前に前記第二のメモリ命令を実行することで前記プログラムの並列性能が増加すると判断された際、前記第一のメモリ命令に割り当てられていない複数のグループ識別子の一つを、前記第二のメモリ命令に割り当てるステップと、
前記プログラムに対してアクセス可能な一以上のプロセッサに、前記第一のメモリ命令の前に前記第二のメモリ命令を実行させるよう、前記第二のメモリ命令に関連し且つ前記一つのグループ識別子を有するメモリバリア命令を提供するステップと、
を備える方法。
【請求項９】
請求項８記載の方法であって、
複数のグループ識別子の一つを割り当てる前記ステップは、更に、
前記一つのグループ識別子を有する前記複数のメモリ命令の数を決定するステップと、
前記数が所定の値を上回るかを判断するステップと、
前記数が前記所定の値を上回らないと判断したことに応答して、前記第二のメモリ命令に前記一つのグループ識別子を割り当てるステップと、
を備える方法。
【請求項１０】
プログラムに関連する複数の命令の実行を管理する方法を実行するデータ処理システムを制御するための命令を含むコンピュータ読み取り可能な媒体であって、
前記方法は、
複数の命令のうちの第一の命令の後で前記プログラムに現れる前記複数の命令のうちの一以上に第一のグループ識別子を割り当てるステップと、
前記第一のグループ識別子とは異なる第二のグループ識別子を前記第一の命令に割り当てるステップと、
前記プログラムに対するアクセスを有する一以上のプロセッサが、前記メモリバリア命令に関連する前記第二のグループ識別子に従った順序で、前記プログラムの前記複数の命令を実行するように、前記第一の命令に関連し且つ前記第二のグループ識別子を有するメモリバリア命令を提供するステップと、
を備えるコンピュータ読み取り可能な媒体。
【請求項１１】
請求項１０記載のコンピュータ読み取り可能な媒体であって、
前記一以上のプロセッサは、前記第一の命令の前に前記第一のグループ識別子を割り当てられた前記一以上の命令を実行することが認められている間、前記第一の命令の前に前記第二の命令を実行することを禁止される、コンピュータ読み取り可能な媒体。
【請求項１２】
請求項１０記載のコンピュータ読み取り可能な媒体であって、更に、
前記第一の命令の前に前記プログラム内に現れる第三の前記命令に第三のグループ識別子を割り当てるステップを備え、前記第二のグループ識別子を有する前記メモリバリア命令は、前記第三の命令の前に前記第一の命令を実行することを前記一以上のプロセッサに促す、コンピュータ読み取り可能な媒体。
【請求項１３】
請求項１０記載のコンピュータ読み取り可能な媒体であって、
前記複数の命令は、少なくとも二つのクラスを含み、前記第一及び第二の命令と前記メモリバリア命令とは、前記第二のグループ識別子に従った前記少なくとも二つのクラス間の順序の制約を反映する、コンピュータ読み取り可能な媒体。
【請求項１４】
請求項１０記載のコンピュータ読み取り可能な媒体であって、
前記複数の命令は、少なくとも二つのクラスを含み、前記第一及び第二の命令と前記メモリバリア命令とは、前記第二のグループ識別子に従った前記少なくとも二つのクラスの一つにおける順序の制約を反映する、コンピュータ読み取り可能な媒体。
【請求項１５】
請求項１０記載のコンピュータ読み取り可能な媒体であって、
前記メモリバリア命令は、前記メモリバリア命令の前に前記プログラムに現れ、前記第二のグループ識別子を有する前記複数の命令のそれぞれを、前記メモリバリア命令の後で前記プログラムに現れる前記複数の命令の一つの前に、前記一以上のプロセッサに実行させる完了の制約を反映する、コンピュータ読み取り可能な媒体。
【請求項１６】
請求項１０記載のコンピュータ読み取り可能な媒体であって、
第二のグループ識別子を割り当てる前記ステップは、更に、
前記第二のグループ識別子を有する前記複数の命令の数を決定するステップと、
前記数が所定の値を上回るかを判断するステップと、
前記数が前記所定の値を上回らないと判断したことに応答して、前記第一の命令に前記第二のグループ識別子を割り当てるステップと、
を備えるコンピュータ読み取り可能な媒体。
【請求項１７】
プログラムに関連する複数のメモリ命令の実行を管理する方法を実行するデータ処理システムを制御するための命令を含むコンピュータ読み取り可能な媒体であって、
前記方法は、
前記複数のメモリ命令のうちの第一のメモリ命令の前に、前記メモリ命令のうちの第二のメモリ命令を実行することで、前記プログラムの並列性能が増加するかを判断するステップと、
前記第一のメモリ命令の前に前記第二のメモリ命令を実行することで前記プログラムの並列性能が増加すると判断された際、前記第一のメモリ命令に割り当てられていない複数のグループ識別子の一つを、前記第二のメモリ命令に割り当てるステップと、
前記プログラムに対するアクセスを有する一以上のプロセッサに前記第一のメモリ命令の前に前記第二のメモリ命令を実行させるよう、前記第二のメモリ命令に関連し且つ前記一つのグループ識別子を有するメモリバリア命令を提供するステップと、
を備える、コンピュータ読み取り可能な媒体。
【請求項１８】
請求項１７記載のコンピュータ読み取り可能な媒体であって、
複数のグループ識別子の一つを割り当てる前記ステップは、更に、
前記一つのグループ識別子を有する前記複数のメモリ命令の数を決定するステップと、
前記数が所定の値を上回るかを判断するステップと、
前記数が前記所定の値を上回らないと判断したことに応答して、前記第二のメモリ命令に前記一つのグループ識別子を割り当てるステップと、
を備えるコンピュータ読み取り可能な媒体。
【請求項１９】
データ処理システムであって、
複数の命令を有する第一のプログラムと、
前記複数の命令のうちの第一の命令の後に前記第一のプログラムに現れる前記複数のメモリ命令の一つ以上に第一のグループ識別子を割り当て、前記第一のグループ識別子とは異なる第二のグループ識別子を前記第一の命令に割り当て、前記第一の命令に関連し且つ前記第二のグループ識別子を有するメモリバリア命令を提供する命令マネージャプログラムと、
を含むメモリデバイスと、
前記メモリバリア命令に関連する前記第二の一グループ識別子に従った順序で前記第一のプログラムの前記複数の命令を実行するように、前記命令マネージャプログラム及び前記第一のプログラムを実行する、
一以上のプロセッサと、
を備えるデータ処理システム。
【請求項２０】
請求項１９記載のデータ処理システムであって、
前記一以上のプロセッサは、前記第一のメモリ命令の前に前記第一の識別子を割り当てられた前記一つ以上の命令を実行することが認められている間、前記第一の命令の前に前記第二の命令を実行することを禁止される、データ処理システム。
【請求項２１】
請求項１９記載のデータ処理システムであって、
前記命令マネージャプログラムは、更に、前記第一の命令の前に前記プログラムに現れる前記命令のうちの第三の命令に第三のグループ識別子を割り当てるステップを備え、前記第二のグループ識別子を有する前記メモリバリア命令は、前記一以上のプロセッサに前記第三の命令の前に前記第一の命令を実行させる、データ処理システム。
【請求項２２】
請求項１９記載のデータ処理システムであって、
第二のグループ識別子を割り当てる前記ステップは、更に、
前記第二のグループ識別子を有する前記複数の命令の数を決定するステップと、
前記数が所定の値を上回るかを判断するステップと、
前記数が前記所定の値を上回らないと判断したことに応答して、前記第一の命令に前記第二のグループ識別子を割り当てるステップと、
を備えるデータ処理システム。
【請求項２３】
データ処理システムであって、
複数のメモリ命令を有する第一のプログラムと、
前記複数のメモリ命令のうちの第一のメモリ命令の前に前記メモリ命令のうちの第二のメモリ命令を実行することで前記プログラムの並列性能が増加するかを判断し、前記第一のメモリ命令の前に前記第二のメモリ命令を実行することで前記プログラムの並列性能が増加すると判断された際、複数のグループ識別子の一つを、前記第一のメモリ命令に割り当てられていない前記第二のメモリ命令に割り当て、前記第二のメモリ命令に関連し且つ前記一つのグループ識別子を有するメモリバリア命令を提供する命令マネージャプログラムと、
を有するメモリデバイスと、
前記メモリバリア命令を実行することに応答して、前記第一のメモリ命令の前に前記第二のメモリ命令を実行するのを促されるように、前記命令マネージャプログラム及び前記第一のプログラムを実行する、
一以上のプロセッサと、
を備えるデータ処理システム。
【請求項２４】
請求項２３記載のデータ処理システムであって、
複数のグループ識別子の一つを割り当てる前記ステップは、更に、
前記一つのグループ識別子を有する前記複数のメモリ命令の数を決定するステップと、
前記数が所定の値を上回るかを判断するステップと、
前記数が前記所定の値を上回らないとの判断に応答して、前記第二のメモリ命令に前記一つのグループ識別子を割り当てるステップと、
を備えるデータ処理システム。
【請求項２５】
システムであって、
複数の命令のうちの第一の命令の後でプログラムに現れる前記複数の命令のうちの一以上に第一のグループ識別子を割り当てる手段と、
前記第一のグループ識別子とは異なる第二のグループ識別子を前記第一の命令に割り当てる手段と、
前記プログラムに対するアクセスを有する一以上のプロセッサが、前記メモリバリア命令に関連する前記第二のグループ識別子に従った順序で、前記プログラムの前記複数の命令を実行するよう、前記第一のメモリ命令に関連し且つ前記第二のグループ識別子を有するメモリバリア命令を提供する手段と、
を備えるシステム。
【請求項２６】
請求項２５記載のシステムであって、
前記一以上のプロセッサは、前記第一の命令の前に前記第一のグループ識別子を割り当てられた前記一つ以上の命令を実行することが認められている間、前記第一の命令の前に前記第二の命令を実行することを禁止される、システム。
【請求項２７】
請求項２５記載のシステムであって、更に、
前記第一のメモリ命令の前に前記プログラム内に現れる前記メモリ命令のうちの第三のメモリ命令に第三のグループ識別子を割り当てる手段を備え、前記第二のグループ識別子を有する前記メモリバリア命令は、前記一以上のプロセッサに前記第三の命令の前に前記第一の命令を実行させる、システム。
【請求項２８】
請求項２５記載のシステムであって、
第二のグループ識別子を割り当てる前記手段は、更に、
前記第二のグループ識別子を有する前記複数の命令の数を決定する手段と、
前記数が所定の値を上回るかを判断する手段と、
前記数が前記所定の値を上回らないと判断したことに応答して、前記第一の命令に前記第二のグループ識別子を割り当てる手段と、
を備える、システム。
【請求項２９】
システムであって、
複数のメモリ命令のうちの第一のメモリ命令の前に、プログラムの前記複数のメモリ命令のうちの第二のメモリ命令を実行することで、前記プログラムの並列性能が増加するかを判断する手段と、
前記第一のメモリ命令の前に前記第二のメモリ命令を実行することで前記プログラムの並列性能が増加すると判断された際、
前記第一のメモリ命令に割り当てられていない複数のグループ識別子の一つを前記第二のメモリ命令に割り当てる手段と、
前記プログラムに対してアクセス可能な一以上のプロセッサに、前記第一のメモリ命令の前に前記第二のメモリ命令を実行させるよう、前記第二のメモリ命令に関連し且つ前記一つのグループ識別子を有するメモリバリア命令を提供する手段と、
を備えるシステム。
【請求項３０】
請求項２９記載のシステムであって、
複数のグループ識別子の一つを割り当てる手段は、更に、
前記一つのグループ識別子を有する前記複数のメモリ命令の数を決定する手段と、
前記数が所定の値を上回るかを判断する手段と、
前記数が前記所定の値を上回らないとの判断に応答して、前記第二のメモリ命令に前記一つのグループ識別子を割り当てる手段と、を備えるシステム。
【請求項３１】
データ処理システムであって、
メモリバリア命令を含む複数の命令を有する第一のプログラムを備え、前記メモリバリア命令と前記複数のメモリ命令のそれぞれが複数のグループ番号のそれぞれに関連づけられている、
メモリと、
前記メモリバリア命令に関連づけられている前記グループ番号のそれぞれに従った順序で、前記第一のプログラムの前記複数の命令を実行するように構成される、
処理ユニットと、
を備えるデータ処理システム。
【請求項３２】
請求項３１記載のデータ処理システムであって、
前記メモリバリア命令を実行することに応答して、前記処理ユニットは、同じグループ番号を有し、前記プログラムに前記メモリバリア命令の後に現れる前記複数のメモリ命令のうちの第二のメモリ命令を実行する前に、前記メモリバリア命令と同じ前記グループ番号の一つに関連づけられており、前記プログラム内の前記メモリバリア命令の前に現れる前記複数のメモリ命令のうちの第一のメモリ命令を実行する、データ処理システム。
【請求項３３】
請求項３２記載のデータ処理システムであって、
前記複数のメモリ命令のうちの第三のメモリ命令は、前記グループ番号の異なる一つに関連づけられ、前記プログラムの前記メモリバリア命令の後に現れ、
前記プロセッサは、前記メモリバリア命令の実行に応答して、前記第一のメモリ命令の前に、前記第三のメモリ命令を実行することを禁止されない、データ処理システム。
【請求項３４】
請求項３２記載のデータ処理システムであって、
前記複数のメモリ命令のうちの第四のメモリ命令は、前記グループ番号の異なる一つに関連づけられ、前記プログラムの前記メモリバリア命令の前に現れ、
前記プロセッサは、前記メモリバリア命令の実行に応答して、前記第四のメモリ命令の前に、前記第一のメモリ命令を実行することを促される、データ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の説明
本願は、出典を明示することにより法律で認められる範囲で本願明細書の一部とする２００４年５月４日出願の米国仮出願第６０／５６８４９４号「命令をグループ化及び管理する方法及びシステム」の出願日の利益を主張する。
【０００２】
本発明は、プログラムのランタイム性能を改善する方法及びシステムに関する。特に、本発明に従った方法及びシステムは、一つ以上のプロセッサで実行するプログラムに関連するメモリ命令をグループ化及び管理することに関する。
【背景技術】
【０００３】
コンピュータプログラムの速度を高める方法の一つは、動作を別個のタスクに分割し、こうしたタスクを多数のプロセッサで同時に実行することである。多数のプロセッサは、共通のメモリを共有してよく、或いは共有しなくてもよい。コンピュータシステムにおいて最も低速の動作の一つは、メモリ常駐データに関する動作である。（一つ以上のプロセッサ命令に関連する）オペランドのメモリからのフェッチは、プロセッサのレジスタからの同じオペランドのフェッチに比べて、数百倍又は数千倍低速となり得る。メモリでのデータの格納も、同様に低速となる可能性がある。様々な一般的手法は、こうした待ち時間をアプリケーションから隠す上で有効であるが、待ち時間は、依然としてプロセッサ設計に影響し、したがって、アプリケーションの性能に影響する。
【０００４】
直前に参照されたデータと、その直前に参照されたデータの近くにあるデータとを格納する高速キャッシュを取り付けることは、プロセッサ設計において一般的な方法である。キャッシュは、キャッシュに格納されたメモリ常駐データのコピーを迅速に供給することで、フェッチ又はリードメモリアクセスの待ち時間を隠す。キャッシュは、更に、様々な手段で、メモリ書き込みアクセスの待ち時間も隠蔽する。
【０００５】
キャッシュは、キャッシュラインの単位でメモリとの情報のやり取りを行う。キャッシュラインは、通常、３２〜５１２バイト程度で、通常はキャッシュとメモリとの間でのやり取りの最小単位となる。プロセッサがキャッシュに存在しない値をメモリから要求する時、メモリは、プロセッサが要求したデータを含むキャッシュラインのサイズのデータの塊を転送する。データのライン全体が、キャッシュに格納される。次に、キャッシュは、要求されたデータを、メモリから転送されたラインより抽出し、プロセッサへ戻す。プロセッサがキャッシュにおいて表現されるアドレスにデータを書き込む時、キャッシュのコピーは更新され、キャッシュラインは「ダーティ」としてマークされる。ラインがキャッシュ後部からメモリへフラッシュされる時、メモリ内のラインが更新される。プロセッサがキャッシュにおいて表現されないアドレスにデータを書き込む時、ラインは、リードのために上記のようにメモリから読み出され、その後、新しいデータが上記のようにキャッシュに書き込まれる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
メモリ待ち時間を隠す上でのキャッシュの有効性は、いくつかの要素によって減じられる。第一に、キャッシュのサイズは、強く制約されており、合計物理メモリのパーセンテージとして、単一のキャッシュのサイズは、縮小を続けている。一例として、Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．（商標）のＥ１５Ｋマシン又はコンピュータは、２39バイトまでのリードアクセスメモリ（ＲＡＭ）を有することが可能だが、Ｅ１５Ｋマシンにおいて通常使用されるＵｌｔｒａＳｐａｒｃ−ＩＩＩTMプロセッサは、僅か２23のキャッシュしか有しておらず、１：２16の比となる。Ｅ１５Ｋマシンにおける進展には、２52バイトのＲＡＭを組み込むことが含まれる可能性があり、プロセッサ当たりのキャッシュサイズは、１：２16の比を維持するのに必要とされる２56バイトには程遠いものとなる。上記及びその他の理由から、キャッシュは、大きなワーキングセットと不連続アクセスパターンとを有するプログラムでは有効性が低下しており、これは対象範囲の割合の減少と共に所望の値がキャッシュ内に存在する確立が下落しているためである（対象範囲の割合とは、特定のキャッシュによりカバーできるメモリのパーセンテージを指す。例えば、メモリ５１２メガバイトのシステム上で、８メガバイトのキャッシュは８／５１２×１００≒１．６％をカバーする）。
【０００７】
第二に、従来のシステムでは、メモリとの距離が、サイクルの点から見て増加しており、通常、これによりメモリアクセス速度は増加し、性能の問題が生じる。メモリとの距離が数百サイクルから数千サイクルになると、待ち時間を隠す難しさは、急激に増加する。プロセッサは動作を完了まで追跡する必要があるため、待ち時間の増加は、プロセッサ設計における問題も発生させる。簡略して言えば、ライトは、通常、メモリが更新された時に完了したと見なされる。メモリがプロセッサから１０００サイクル離れており、全てのサイクルでライトを発行可能である場合、プロセッサは、ライトバッファフルによる機能停止を回避するために、少なくとも２０００の未解決メモリトランザクションを追跡する必要がある（２０００トランザクション＝１トランザクション／サイクル＝データをメモリへ送信する１０００サイクル及び肯定応答を返送する１０００サイクル）。２０００の独立したトランザクションを追跡することは、通常、極めて困難である。
【０００８】
従来のシステムでは、更に、従来のプロセッサが特定のデータ構造を使用するプログラムを実行する方法によって、メモリアクセス速度が増加し、並列性能は低下する。従来のプロセッサは、通常、同種のメモリ動作の連続と順番に相互作用する。例えば、プロセッサは、ライトよりもリードを優先し得るが、通常は、個々のリードの相対的な重要性を区別しない。多数のプロセッサ上で並行して動作するプログラム内のスレッドを実行するプロセッサは、演算処理に関連する一連のメモリ動作を行い、その後、最後のメモリ動作を行って、並行して動作する他のプロセッサと自分の活動を同期させる場合が多い。次に、自分のために更なる作業を取得して、演算処理の独立した部分へ進めるように、メモリ動作を発行してよく、更なる作業に関する要求が充足されるまでは、全ての処理をブロックする。多くの演算処理では、更なる作業を取得することは、以前の作業の完了を報告することよりも遙かに重要だが、プロセッサがメモリ動作のストリームと相互作用する方法は、順次的な性質であるため、重要な要求は、重要性の低い要求の後方で停止する。メモリとの距離が増加し、関連する待ち時間をキャッシュのような手法で隠せなくなるにつれ、重要な動作を、重要性の低い遙かに低速の動作の後ろで停止させる問題は、更に切迫したものとなっている。
【０００９】
したがって、上記及びこれまでに経験された他の問題を克服する方法及びシステムに対する必要性が、長らく存在してきた。
【課題を解決するための手段】
【００１０】
本発明に従った方法、システム、及び製品は、プログラム内の複数の命令を複数のグループ識別子のそれぞれに関連付け、グループ識別子に従ってプログラムに関連する複数の命令の実行を管理することで、プログラムの並列性能を改善する。
【００１１】
本発明に従った方法によれば、プログラムに関連する複数の命令の実行を管理するデータ処理システムにおける方法が提供される。方法は、複数の命令のうちの第一の命令の後にプログラムに現れる複数の命令のうちの一つ以上の命令に第一のグループ識別子を割り当てるステップと、第一のグループ識別子とは異なる第二のグループ識別子を第一のメモリ命令に割り当てるステップと、プログラムに対してアクセス可能な一以上のプロセッサが、メモリバリア命令に関連する第二のグループ識別子に従った順序で、プログラムの複数の命令を実行するよう、第一のメモリ命令に関連し且つ第二のグループ識別子を有するメモリバリア命令を提供するステップと、を含む。
【００１２】
本発明に従った方法によれば、プログラムに関連する複数のメモリ命令の実行を管理するデータ処理システムにおける方法が提供される。方法は、複数のメモリ命令のうちの第一のメモリ命令の前に、メモリ命令のうちの第二のメモリ命令を実行することで、プログラムの並列性能が増加するかを判断するステップと、第一のメモリ命令の前に第二のメモリ命令を実行することでプログラムの並列性能が増加すると判断された際、第一のメモリ命令に割り当てられていない複数のグループ識別子の一つを、第二のメモリ命令に割り当てるステップと、プログラムに対してアクセス可能な一以上のプロセッサに、第一のメモリ命令の前に第二のメモリ命令を実行させるよう、第二のメモリ命令に関連し且つ一つのグループ識別子を有するメモリバリア命令を提供するステップと、を含む。
【００１３】
本発明に従った製品によれば、プログラムに関連する複数の命令の実行を管理する命令を含むコンピュータ読み取り可能な媒体となる。方法は、複数の命令のうちの第一の命令の後でプログラムに現れる複数の命令のうちの一以上に第一のグループ識別子を割り当てるステップと、第一のグループ識別子とは異なる第二のグループ識別子を第一の命令に割り当てるステップと、プログラムに対するアクセスを有する一以上のプロセッサが、メモリバリア命令に関連する第二のグループ識別子に従った順序で、プログラムの複数の命令を実行するように、第一の命令に関連し且つ第二のグループ識別子を有するメモリバリア命令を提供するステップと、を含む。
【００１４】
本発明に従った製品によれば、プログラムに関連する複数のメモリ命令の実行を管理する命令を含むコンピュータ読み取り可能な媒体となる。方法は、複数のメモリ命令のうちの第一のメモリ命令の前に、メモリ命令のうちの第二のメモリ命令を実行することで、プログラムの並列性能が増加するかを判断するステップと、第一のメモリ命令の前に第二のメモリ命令を実行することでプログラムの並列性能が増加すると判断された際、第一のメモリ命令に割り当てられていない複数のグループ識別子の一つを、第二のメモリ命令に割り当てるステップと、プログラムに対するアクセスを有する一以上のプロセッサに第一のメモリ命令の前に第二のメモリ命令を実行させるよう、第二のメモリ命令に関連し且つ一つのグループ識別子を有するメモリバリア命令を提供するステップと、を含む。
【００１５】
本発明に従ったシステムによれば、データ処理システムが提供される。データ処理システムは、メモリデバイスと、一以上のプロセッサとを備える。メモリデバイスは、複数の命令を有する第一のプログラムと、複数の命令のうちの第一の命令の後に第一のプログラムに現れる複数のメモリ命令の一つ以上に第一のグループ識別子を割り当て、第一のグループ識別子とは異なる第二のグループ識別子を第一の命令に割り当て、第一の命令に関連し且つ第二のグループ識別子を有するメモリバリア命令を提供する命令マネージャプログラムを含む。一以上のプロセッサは、メモリバリア命令に関連する第二の一グループ識別子に従った順序で第一のプログラムの複数の命令を実行するように、命令マネージャプログラム及び第一のプログラムを実行する構成となる。
【００１６】
本発明に従ったシステムによれば、データ処理システムが提供される。データ処理システムは、メモリデバイスと、一以上のプロセッサとを備える。メモリデバイスは、複数のメモリ命令を有する第一のプログラムを含む。メモリデバイスは、複数のメモリ命令のうちの第一のメモリ命令の前にメモリ命令のうちの第二のメモリ命令を実行することでプログラムの並列性能が増加するかを判断し、第一のメモリ命令の前に第二のメモリ命令を実行することでプログラムの並列性能が増加すると判断された際、複数のグループ識別子の一つを、第一のメモリ命令に割り当てられていない第二のメモリ命令に割り当て、第二のメモリ命令に関連し且つ一つのグループ識別子を有するメモリバリア命令を提供する命令マネージャプログラムを含む。一以上のプロセッサは、メモリバリア命令を実行することに応答して、第一のメモリ命令の前に第二のメモリ命令を実行するのを促されるように、命令マネージャプログラム及び第一のプログラムを実行する構成となる。
【００１７】
本発明に従ったシステムによれば、複数の命令のうちの第一の命令の後でプログラムに現れる複数の命令のうちの一以上に第一のグループ識別子を割り当てる手段と、第一のグループ識別子とは異なる第二のグループ識別子を第一の命令に割り当てる手段と、プログラムに対するアクセスを有する一以上のプロセッサが、メモリバリア命令に関連する第二のグループ識別子に従った順序で、プログラムの複数の命令を実行するよう、第一のメモリ命令に関連し且つ第二のグループ識別子を有するメモリバリア命令を提供する手段とを含むシステムが提供される。
【００１８】
本発明に従ったシステムによれば、複数のメモリ命令のうちの第一のメモリ命令の前に、プログラムの複数のメモリ命令のうちの第二のメモリ命令を実行することで、プログラムの並列性能が増加するかを判断する手段と、第一のメモリ命令の前に第二のメモリ命令を実行することでプログラムの並列性能が増加すると判断された際、第一のメモリ命令に割り当てられていない複数のグループ識別子の一つを第二のメモリ命令に割り当て、プログラムに対してアクセス可能な一以上のプロセッサに、第一のメモリ命令の前に第二のメモリ命令を実行させるよう、第二のメモリ命令に関連し且つ一つのグループ識別子を有するメモリバリア命令を提供する手段と、を含むシステムが提供される。
【００１９】
本発明に従ったシステムによれば、データ処理システムが提供される。データ処理システムは、メモリと、処理ユニットとを備える。メモリは、複数の命令を有する第一のプログラムを含み、複数の命令は、複数のメモリ命令と、メモリバリア命令とを含み、メモリバリア命令と複数のメモリ命令のそれぞれが複数のグループ番号のそれぞれに関連づけられている。処理ユニットは、メモリバリア命令に関連づけられているグループ番号のそれぞれに従った順序で、第一のプログラムの複数の命令を実行する構成となる。
【００２０】
発明の効果
本発明の上記及びその他の特徴、有用性、及び利点は、添付図面と併せて、本発明の好適な実施形態の以下の詳細な説明から明らかとなろう。
【００２１】
本発明のその他のシステム、方法、特徴、及び利点は、以下の図及び詳細な説明を調べることで、当業者には明らかとなろう。こうした全ての追加的なシステム、方法、特徴、及び利点は、本説明の中に含まれ、本発明の範囲内にあり、添付図面によって保護されることが意図される。
【００２２】
添付図面は、本明細書に組み込まれ、その一部を構成するものであり、本発明の一つ以上の実施を例示し、説明と共に、本発明の利点及び原理を明らかにする役割を果たす。
【発明を実施するための最良の形態】
【００２３】
本発明に従った方法、システム、及び製品によれば、一つ以上のプロセッサにより実行するプログラムに関連するメモリ命令をグループ化及び管理するために、メモリ命令マネージャが提供される。
【００２４】
図１は、本発明に従った方法及びシステムでの使用に適したデータ処理システム１００のブロック図を示している。データ処理システム１００は、中央演算処理装置（ＣＰＵ）１０２と、入出力Ｉ／Ｏユニット１０４と、メモリ１０６と、キャッシュ１０７と、二次記憶装置１０８と、ビデオディスプレイ１１０とを備える。データ処理システム１００は、更に、キーボード、マウス、又は音声処理手段（それぞれ例示なし）のような標準的入力デバイスを備えてもよい。データ処理システム１００は、メモリ１０６又は二次記憶装置１０８に含まれるプログラムの並列処理命令のために第二のＣＰＵ１０３を含んでもよい。こうしたデータ処理システムの様々なコンポーネントは、物理的に互いに離れて位置してよく、ネットワークを介して接続してよい。
【００２５】
メモリ１０６は、プロセッサ１０２及び１０３を使用して実行されるアプリケーション又はプログラムの動作を管理するオペレーティングシステム１１１を含んでもよい。メモリ１０６は、更に、コンパイラ１１２と、対応するオブジェクトコードモジュール（例えば、１１８〜１２０）を生成するためにコンパイラ１１２によって変換されるソースコードモジュールＡ〜Ｎ（例えば、１１４〜１１６）とを含んでもよい。コンパイラ１１２又はリンカ（図示なし）は、ＣＰＵ１０２及び１０３のような一つ以上の対象プロセッサを使用して実行されるアプリケーション又は実行可能プログラム１２２を生成するために、オブジェクトモジュール１１８〜１２０をリンクさせてよい。実行可能プログラム１２２は、ソースモジュール１１４〜１１６に従ったプログラム順序でコンパイラによって編成された複数の命令（図１に図示なし）を有する。ＣＰＵ１０２及び１０３は、実行順序でプログラム１２２内の命令を実行してよく、実行順序は、プログラム順序に対応していなくてもよいが、以下で更に説明するように、少なくとも、予期しない結果が発生せず、プロセッサの自己一貫性が維持されるように、プログラム順序に従う。
【００２６】
コンパイラ１１２は、静的コンパイラ、対象プロセッサ１０２又は１０３のためにランタイムでソースモジュール１１４〜１１６を解釈する動的コンパイラ（Ｓｕｎ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ（商標）等）、又は両方の組み合わせにしてよい。
【００２７】
コンパイラ１１２は、更に、メモリ命令マネージャ１３０と、本発明に矛盾しない方法及びシステムに従ってＣＰＵ１０２及び１０３によって認識されるメモリ命令セット１３２とを含んでよい。以下で更に詳細に説明するように、メモリ命令マネージャ１３０は、プログラム１２２に含まれるコンパイル済み又はオブジェクトモジュール１１８〜１２０のメモリ命令に対応するセット１３２内のメモリ命令を特定すること、および、プログラム１２２に含まれるメモリ命令をプロセッサ１０２及び１０３が実行する順序を管理することを実施可能に構成される。
【００２８】
メモリ命令マネージャ１３０は、それぞれの動作を実行するための命令を含む一つ以上のコードセクションを構成してよく、或いは、こうしたコードセクションに含まれてよい。最適化ツール１３０及びその他のプログラム（例えば、コンパイラ１１２）はソフトウェアとして実施されるものとして説明されているが、本実施は、ハードウェア及びソフトウェアの組み合わせとして、或いはハードウェアのみで実施してもよい。更に、当業者は、プログラムがデータ処理デバイスを構成してよく、或いは、こうしたデータ処理デバイスに含まれてよく、データ処理デバイスは、データ処理システム１００と通信するサーバにしてよいことを理解するであろう。
【００２９】
加えて、図１に示した一実施の態様はメモリに格納されるものとして示しているが、当業者は、本発明に従ったシステム及び方法の全部又は一部を、ハードディスク、フレキシブルディスク、及びＣＤ−ＲＯＭのような二次記憶装置、インターネットのようなネットワークから受領された搬送波、或いは現在公知であるか若しくは今後開発される他の形態のＲＯＭ又はＲＡＭ等、その他のコンピュータ読み取り可能な媒体に格納してよく、或いは、こうした媒体から読み出してもよいことを理解するであろう。更に、データ処理システム１００の特定のコンポーネントについて説明したが、当業者は、本発明に従った方法、システム、及び製品での使用に適したデータ処理システムが追加的又は異なるコンポーネントを含んでもよいことを理解するであろう。
【００３０】
メモリ動作又は命令は、リードメモリ命令、ライトメモリ命令、原子的更新命令、キャッシュ動作、又は制御動作にしてよく、それぞれが命令セット１３２に含まれる。原子的更新命令は、プロセッサ１０２又は１０３がカウンタのメモリ位置を同時に読み取り、別のプロセッサ１０３又は１０２がメモリ位置に対する書き込みを行っていない場合に同じバス動作でカウンタを増分する際の（誤った更新の発生を防止する）動作として、メモリ命令マネージャ１３０によって認識される。
【００３１】
一実施において、命令セット１３２は、フラッシュ命令及び無効化命令として定義される二つのキャッシュ動作を含む。関連するグループ番号を有するフラッシュ命令によって、プロセッサ１０２又は１０３は、フラッシュ命令によって指定されたメモリアドレスを含むキャッシュラインを更新する未解決の全てのライトをプロセッサ１０２又は１０３が完了させ、その後、ダーティデータをメモリに書き込むまで、同じグループ番号を有するプログラム１２２内の別のメモリ命令のフェッチ、ロード、デコード、又は実行をブロックする。フラッシュ動作によって、プロセッサ１０２又は１０２は、後続の無効化動作によって有効データを失うリスクを生じることがないように、キャッシュライン内の全てのダーティデータをメモリに書き込む。一実施において、プロセッサ１０２及び１０３は、非ダーティデータがメモリの修正に使用されないように構成される。この制約により、プロセッサ１０２及び１０３は、ライン全体がダーティではない限り、キャッシュライン全体の書き込みを禁じられる。フラッシュ命令は、本発明に従った方法及びシステムによる制御動作（以下で説明するメモリバリア命令等）を処理する時のライト動作としてプロセッサ１０２及び１０３に認識される。
【００３２】
無効化命令により、プロセッサ１０２又は１０３は、無効化命令に関連するアドレスを含むキャッシュライン上の有効ビット（図示なし）を消去する。キャッシュライン内にダーティデータを保存する必要がある場合、プログラマ又はコンパイラ１１２は、フラッシュ命令を無効化命令に先行させてよい。無効化命令は、本発明に従った方法及びシステムによる制御動作（以下で説明するメモリバリア命令等）を処理する時のライト動作としてプロセッサ１０２及び１０３に認識される。各無効化動作は、無効化動作に対するメモリバリア命令を可能にするグループ番号を有するが、無効化動作に影響されるライン内のデータは、任意のグループ番号を使用したライトメモリ命令又はその他の動作に由来してよい。
【００３３】
以下で詳細に説明するように、メモリ命令マネージャ１３０は、プロセッサ１０２又は１０３が最適な順序でプログラム内の動作又は命令を完了するように導くために、グループ番号をプログラム内の制御動作に関連付ける。プロセッサ１０２及び１０３は、公知の手法に従って、リードメモリ命令と、ライトメモリ命令と、原子的更新命令とを処理するが、但し、プロセッサ１０２及び１０３は、各リードメモリ、ライトメモリ、及び原子的更新命令が関連するグループ番号を有することを認識し、関連するグループ番号は、一致するグループ番号を有する制御命令と連動して、それぞれの命令が実行される時期を制御する。
【００３４】
一実施において、以下で説明するメンバ命令は、プログラム１２２内のメモリ動作のグループの動作を制御するために、本発明に従った方法及びシステムによるメモリ命令マネージャ１３０によってグループ番号を割り当てられることを除き、ＳＰＡＲＣアーキテクチャマニュアル、バージョン９において説明されるＳＰＡＲＣ  Ｖ９メンバメモリ命令のバリエーションである。
【００３５】
メンバ命令は、以下の三つの機能、即ち、プログラム１２２内のメモリ動作間に順序の制約を提供すること、プログラム１２２内のメモリ動作が完了する時期を制御すること、及びプロセッサ１０２又は１０３に対して、現在プロジェクト内のどの動作が実行の重要性が高いかに関する通知を行うことの一つ以上を実行するために、メモリ命令マネージャ１３０によって使用されてよい。
【００３６】
一実施において、メンバ命令で使用されるアセンブリ言語の構文は、「ｍｅｍｂｅｒ  ｍｅｍａｒ＿ｍａｓｋ［．ｇｒｏｕｐｅ  ｎｕｍｂｅｒ］」である。この実施において、ｍｅｍａｒ＿ｍａｓｋは、以下で説明するように、メンバ命令内のｍｍａｓｋフィールド（例えば、ビット０〜３）とｃｍａｓｋフィールド（例えば、ビット４〜６）とのビット単位のＯＲである。メンバ命令のグループ番号（例えば、ビット７〜１２）は、プロセッサ１０２又は１０３が処理をブロックするメモリ命令のグループ（例えば、プログラム１２２内の他の未決のリード又はライトメモリ動作）を特定する。例えば、メンバ命令に割り当てられたグループ番号がゼロである場合、プロセッサ１０２又は１０３は、プログラム１２２内の全ての未解決又は未決メモリ動作にメンバ命令を適用する。
【００３７】
以下で更に詳細に説明するように、メモリ命令マネージャ１３０は、プログラム内でメンバ命令の前に現れるメモリ動作とメンバ命令に続くメモリ動作とのクラス間に順序の制約を導入するために、プログラム１２２内にメンバ命令を提供する。メモリ動作の特定のクラスは、以下の表１に示すようにｍｍａｓｋフィールドによって指定される。メモリ動作クラスは、ロード（例えば、メモリ参照からプロセッサ１０２又は１０３へのリード）とストア（例えば、プロセッサ１０２又は１０３からメモリ参照へのライト）とを含む。メンバ命令は、発行するプロセッサ１０２又は１０３によって参照される全てのアドレス空間内の全メモリ動作に適用するが、他のプロセッサによるメモリ参照には影響を与えない。ｍｍａｓｋフィールドは、プログラム１２２内でメンバ命令の前後に現れるメモリ参照に対して順序の制約を強制する。表１で説明したｍｍａｓｋビットのいずれか又は全部を、メモリ命令マネージャ１３０によって設定してよい。
【００３８】
【表１】
2005332387.tif 000003
【００３９】
表２において説明するようなｃｍａｓｋフィールドのビットは、メモリ動作の順序とプロセッサ１０２及び１０３による命令の処理とに対する追加的制約を指定する。メンバ命令のｍｅｍｂａｒ＿ｍａｓｋにおいてｃｍａｓｋビットが設定されていない場合、メンバ命令によって、プロセッサ１０２又は１０３は、ｍｍａｓｋフィールドによって指定された部分的順序を強制する。ｃｍａｓｋフィールドがゼロではない場合、メンバ命令に割り当てられたグループ番号に基づいて、プロセッサ１０２及び１０３は、完了及び部分的順序の制約を適用する。
【００４０】
【表２】
2005332387.tif 000004
【００４１】
並列処理の対象ではないメモリ動作に割り当てられるグループ番号とは異なるグループ番号を、並列処理の対象となるメモリ動作に割り当て、その後、以下で説明するように異なるグループ番号を有するメンバ命令を提供することにより、メモリ命令マネージャ１３０は、異なるグループ番号を有するメンバ命令の実行に応答して、異なるグループ番号を有するメモリ動作へのアクセスをプロセッサにブロックさせることで、プロセッサ１０２及び１０３によるメモリ命令の実行を管理できる。したがって、メモリ命令マネージャ１３０は、特に、グループ番号が割り当てられたメンバ命令を提供することで、プログラム１２２の並列処理のランタイム速度を大幅に改善できる。
【００４２】
例えば、以下の表３は、以下で更に詳細に説明するように、メモリ命令マネージャ１３０が並列処理可能であるものとして認識して、一つ以上の先行するメモリ命令（例えば（ａ）「．．．メッセージのワードを書く」）に一致するグループ番号を有するメンバ命令（例えば（ｂ）「．．．＃ＳｔｏｒｅＳｔｏｒｅを設定する」）を提供する擬似コード内で表現される、プログラム１２２内の命令のシーケンス又は一部を示している。本発明に従ったシステム及び方法によれば、プロセッサ１０２及び１０３は、メモリ１０６又はキャッシュ１０７へメッセージを書き、リーダに対してメッセージが完了したことを示すためにメモリに対してワードを書き（例えば（ｃ））、メモリに対する無関係のリード及びライトの実行をブロックすることなく、命令（ａ）、（ｂ）及び（ｃ）と並列に、一連のリード及びライトメモリ命令を実行する（例えば（ｄ）「．．．ループ演算を行う」）ことで、表３のシーケンスを実行する。
【００４３】
【表３】
2005332387.tif 000005
【００４４】
この例において、メンバ命令（ｂ）には、メモリ命令マネージャ１３０によってグループ番号３が割り当てられており、これにより、プロセッサ１０２及び１０３は、全てのライトメモリ命令（ａ）が完了するまで、同じグループ番号３を有するライトメモリ命令（ｃ）をブロックする。しかしながら、メモリ命令マネージャ１３０は（ｄ）において、リード及びライトメモリ命令に３ではない異なるグループ番号を割り当てているため、メモリ命令マネージャ１３０は、（ｄ）のリード及びライト命令とプログラム１２２内の任意の後続のメモリ及び非メモリ動作（表３に示していない）とを、並行して（開始をブロックせずに）、プロセッサ１０２及び１０３に実行させることができる。
【００４５】
図２Ａ、図２Ｂは、本発明に従った方法、システム、及び製品による、プログラム内の実行命令をグループ化及び管理するメモリ命令マネージャ１３０によって実行される例示的プロセス２００を示すフロー図である。メモリ命令マネージャ１３０は、プログラムの並列実行中に、重要な動作又は命令が重要性の低い動作の後方で停止するのを阻止することで、プログラムの性能を改善する。本発明に従ったシステム及び方法は、プログラムのメモリ動作をグループに分類し、その後、メモリ制御動作をグループの一つに関連付け、その一グループに割り当てられていないメモリ制御動作の処理をプロセッサに迅速に実行させる。
【００４６】
最初に、メモリ命令マネージャ１３０は、実行するべきプログラムを受け取る（ステップ２０２）。メモリ命令マネージャ１３０は、プログラム１２２のコンパイル中にコンパイラ１２２を介してプログラム１２２を受領してよい。別の実施において、プログラマ又はユーザは、ユーザインタフェース（図示なし）上でのキーボード入力又はマウスクリックといった、公知のデータ入力手法を使用して、メモリ命令マネージャ１３０に対してプログラム１２２を特定してよい。
【００４７】
メモリ命令マネージャ１３０は、次に、プログラム内の全てのメモリ動作にグループ番号を割り当てる（ステップ２０４）。一実施において、メモリ命令マネージャ１３０は、プログラム１２２内の各メモリ命令を特定し、ゼロ等のデフォルトグループ番号をそれぞれに割り当ててよい。メモリ命令マネージャ１３０は、命令セット１３２を使用して、プログラム１２２内のメモリ動作又は命令を特定してよい。別の代替において、命令セット１３２内のメモリ命令には、それぞれのグループ番号を事前に割り当ててよい。この実施では、プログラム１２２がコンパイルされる際、プログラム１２２内の各メモリ動作には、命令セット１３２内のそれぞれのメモリ命令に事前に割り当てられたものと同じグループ番号がコンパイラ１２２によって割り当てられる。
【００４８】
図３は、メモリ命令マネージャ１３０が命令３０２、３０４、３０６、３０８、３１０、又は３１２にグループ番号を割り当てる前に、メモリ命令マネージャ１３０によって特定された、非メモリ命令３０２、３０４、及び３０６とメモリ命令３０８、３１０、及び３１２とを有するプログラム１２２の一部の例３００を示している。
【００４９】
図４は、プロセッサ１０２及び１０３を対象とするアセンブリ言語におけるプログラム１２２の一部３００の表現例４００を示しており、これにおいて、アセンブリメモリ命令４０４、４０８、４１８と非メモリ命令４０２、４０６、４１０、４１２、４１４、４１６とは、プログラム１２２の「ＳＵＭ＝０」命令３０２と「ループ実行」部分３１４とに対応する。非メモリ命令４０２、４０６、４１０、及び４１２は、それぞれ、メモリ位置ではなく、一つ以上のプロセッサレジスタのコンテンツにアクセスし、それぞれの動作を完了する。しかしながら、当業者は、非メモリ命令４０２、４０６、４１０、及び４１２を命令４０４、４０８、及び４１８と同様にコード化し、「ループ実行」部分３１４のそれぞれのメモリ動作３０６又は３０８を完了するためにアクセスするメモリ位置を、プロセッサ１０２又は１０３のレジスタが保持するようにしてよいことを理解するであろう。
【００５０】
図５は、メモリ命令マネージャ１３０がグループ番号５０４、５０８、５１８を各メモリ命令４０４、４０８、及び４１８に割り当てた後の図４に示したプログラム１２２の一部３００の表現例５００を示している。メモリ命令マネージャ１３０は、更に、グループ番号５０２、５０６、５１０、５１２、５１４、及び５１６を、非メモリ動作４０２、４０６、４１０、４１２、４１４、及び４１６に割り当ててよい。一実施において、グループ番号５０４、５０８、又は５１８は、グループ１に割り当てられるロード（又はリード）メモリ動作及びグループ２に割り当てられるストア（又はライト）メモリ動作のように、メモリ動作のタイプに基づいて割り当ててよい。代替実施形態において、メモリ命令マネージャは、各メモリ動作４０４、４０８、及び４１８に、グループ番号０等の同じ初期グループ番号を割り当ててよい。
【００５１】
図２Ａに戻ると、メモリ命令マネージャ１３０は、並行して実行されるべきプログラム１２２の一部を特定する（ステップ２０６）。プログラマ又はコンパイラ１１２は、デリミタを使用して部分の境界を定めることで、並行して実行されるべきプログラム１２２の部分をメモリ命令マネージャ１３０に対して示してよい。図３に示した例において、開始デリミタ３１６（例えば、「｜＄ｏｍｐ  ｐａｒａｌｌｅｌ」）と、終了デリミタ３１８（例えば、「｜＄ｏｍｐ  ｅｎｄ」）とは、コンパイラ１１２が使用して、二つのデリミタ３１６及び３１８間のプログラム１２２の部分３１４を並列処理のために特定してよい。
【００５２】
次に、メモリ命令マネージャ１３０は、プログラム１２２の部分内の第一のメモリ動作（ステップ２０８）と第二のメモリ動作（ステップ２１０）とを特定する。上記のように、メモリ命令マネージャ１３０は、命令４０４、４０８、及び４１８をメモリ命令として認識することが可能であり、これらのメモリ命令４０２、４０８、及び４１８は、並行して実行されるべきプログラム１２２の「ループ実行」部分３１４に対応する。図３〜図５に示した例において、メモリ命令マネージャ１３０は、最初に、メモリ命令４０４を第一のメモリ動作、メモリ命令４０８を第二のメモリ命令として特定する。以下で説明するように、メモリ命令マネージャ１３０は、その後、本発明に従って、メモリ命令４０８を第一のメモリ動作、メモリ命令４１８を第二のメモリ動作として認識する。メモリ命令マネージャ１３０は、代替として、第一及び第二のメモリ動作をプログラム順序から特定してもよい。
【００５３】
メモリ命令マネージャ１３０は、次に、第二のメモリ動作が第一のメモリ動作に関連するかを判断する（ステップ２１２）。メモリ命令マネージャ１３０は、両方のメモリ動作が同じメモリ位置、アドレス、又はアドレスのバンクを参照する時、第二のメモリ動作が第一のメモリ動作に関連すると判断してよい。上の表３で述べた例では、したがって、メモリ命令マネージャは、メモリ命令（ｃ）がメモリ命令（ａ）と同じアドレス又はアドレスのバンクを参照する（例えば、同じメッセージを参照する）と判断できる。図４及び５に示した例では、両方の命令がレジスタ「％ｇ１」に格納された同じメモリアドレスを参照するため、メモリ命令マネージャ１３０は、メモリ命令４０４がメモリ命令４０８に関連すると判断できる。メモリ命令４１８はレジスタ「％ｇ３」に格納された別のメモリアドレスを参照するため、メモリ命令マネージャ１３０は、メモリ命令４１８がメモリ命令４０４又は４０８に関連しないと判断できる。
【００５４】
第二のメモリ動作が第一のメモリ動作に関連する場合、メモリ命令マネージャ１３０は、第二のメモリ命令の実行が第一のメモリ命令に依存するかを判断する（ステップ２１４）。例えば、第一のメモリ命令によって、プロセッサ１０２又は１０３が値をメモリアドレスに格納し、第二のメモリ命令によって、プロセッサ１０２又は１０３がメモリアドレスからの格納済みの値にアクセスすることを求められる時、第二のメモリ命令は、第一のメモリ命令に依存する。したがって、メモリ命令マネージャ１３０は、プロセッサ１０２又は１０３がプロセッサの自己一貫性規則を順守し、プログラム１２２の順序に違反する結果を取得するのを回避する必要がある場合に、あるメモリ命令が別のものに依存するのを認識できる。例えば、メモリ命令マネージャ１３０は、図３のメモリ命令３０８がプロセッサ１０２又は１０３に対して、「ＡＢ（Ｉ）」を５２６により拡大し（例えば、命令４０４及び４０６を実行し）、その後、拡大済みのＡＢ（Ｉ）の値を再び同じメモリ位置に書き込む（例えば、メモリ命令４０８を実行する前）ことを要求するのを認識できる。したがって、メモリ命令マネージャ１３０は、プログラム順序に従わずにメモリ命令４０４及び４０８を実行することで、プログラム順序での実行とは矛盾する結果が生じ、これによりランタイムエラーが発生する可能性が高いため、メモリ命令４０８がメモリ命令４０４に依存することを認識できる。表３を参照して説明した例において、第二のメモリ命令（ｃ）は、第二のメモリ命令（ｃ）の実行を完了するために、必ずしも第一のメモリ命令（ａ）が参照するものと同じメモリ位置からの値を使用しないため（例えば、命令（ａ）が完了するのを待った後で、命令（ｃ）を完了することによりリーダに信号を送るため）、メモリ命令マネージャ１３０は、第二のメモリ命令（ｃ）が第一のメモリ命令（ａ）に関連しているが依存していないことを認識できる。
【００５５】
第二のメモリ動作が第一のメモリ動作に関連しているが依存していない場合、メモリ命令マネージャ１３０は、第一のメモリ命令に異なるグループ番号を割り当て（ステップ２１６）、第二のメモリ命令に異なるグループ番号を割り当てる（ステップ２１８）。図３に示した例において、メモリ命令マネージャ１３０は、メモリ命令（ａ）及びメモリ命令（ｃ）にグループ番号「３」を割り当て、メモリ命令マネージャ１３０は、以下で更に詳細に説明するように、グループ番号「３」を未使用グループ番号として認識する。
【００５６】
次に、命令マネージャ１３０は、第一のメモリ動作の後、或いはこれに関連させて、異なるグループ番号を有するメモリバリア命令を提供する（ステップ２１８）。表３を参照して説明した実施形態において、命令マネージャ１３０は、メモリ命令（ａ）と同じグループ番号「３」を有するメンバ命令（ｂ）を提供する。加えて、命令マネージャ１３０は、プロセッサ１０２又は１０３が第一のメモリ命令（例えば、命令（ａ））の前に第二のメモリ命令（例えば、表３の命令（ｃ））を完了させるのを阻止する一方で、第三又はその他の無関係の命令（例えば、図３の命令（ｃ））をプログラム順序に従わずに実行するのを可能にするために必要な順序又は完了の制約（例えば「ＳｔｏｒｅＳｔｏｒｅ」）に対応するｍｍａｓｋ又はｃｍａｓｋビットを設定してもよい。
【００５７】
第二のメモリ動作が第一のメモリ動作に関連及び依存する場合、メモリ命令マネージャ１３０は、以下で説明するステップ２２２において処理を継続する。図４、図５に示した例において、メモリ命令マネージャ１３０は、プロセッサ１０２又は１０３がメモリ命令４０４の前にメモリ命令４０８を実行して自己一貫性規則に違反しそうにはない状態で、メモリ命令４０８がメモリ命令４０４に依存することを判断できる。したがって、メモリ命令マネージャ１３０は、この事例において、関連及び依存するメモリ命令間に順序の制約を強制するメンバ命令は必要ないと認識する。
【００５８】
次に、メモリ命令マネージャ１３０は、並行して実行されるべきプログラム１２２の部分内にメモリ動作が更に存在するかを判断する（ステップ２２２）。メモリ動作が更に存在する場合、メモリ命令マネージャ１３０は、第二のメモリ動作を第一のメモリ動作として参照し（ステップ２２４）、並行して実行されるべきプログラム１２２の部分内の次のメモリ動作を特定し（ステップ２２６）、次のメモリ動作を第二のメモリ動作として参照し（ステップ２２８）、その後、ステップ２１２の処理を継続する。したがって、図５に示した例において、メモリ動作マネージャ１３０は、ここで、メモリ命令４０８を第一のメモリ命令として特定し、次のメモリ命令４１８を第二のメモリ命令として特定して、ステップ２１２の処理を継続する。
【００５９】
第二のメモリ動作が第一のメモリ動作に関連しない場合、メモリ命令マネージャ１３０は、第一のメモリ動作の前に第二のメモリ動作の実行を促すかを判断する（ステップ２３０）。一実施において、メモリ命令マネージャは、あるプロセッサ（例えば、プロセッサ１０２）による並列性能が別のプロセッサ（例えば、プロセッサ１０３）による第二のメモリ動作の実行を待って停止している時、第一のメモリ動作の前に第二のメモリ動作の実行を促す。
【００６０】
図５に示した例において、メモリ命令マネージャ１３０は、更に、図３のプログラム１２２の部分３１４内の「ループ実行」が「ＡＢ」の最初のＮ要素を５２６で拡大し、これらを合計して「ＳＵＭ」にすることを認識できる。部分３１４の並列処理に対応するために、メモリ命令マネージャ１３０は、利用可能なプロセッサ１０２及び１０３全体でループの反復を分割し、各プロセッサ１０２及び１０３が他のプロセッサと並行して、命令４０４、４０６、４０８、４１０、４１２、及び４１６を「ループ実行」の一部（例えば、プログラム１２２の部分３１４）として実行するようにする。ループの終了時、各プロセッサ１０２及び１０３は、ＡＢの一部の要素の合計に対応する部分合計（例えば、図４及び５において、プロセッサレジスタ「％ｆ６」に格納される）を有する。図４及び５に示した例の「ループ実行」部分３１４を完了させるために、コンパイラ１１２又はメモリ命令マネージャ１３０では、メモリ命令４１８を介して最初にそれぞれの部分和をメモリに格納することで、プロセッサ１０２及び１０３が部分合計を組み合わせて、メモリ命令３１０に従った一つの最終合計にすることが求められる。プロセッサ１０２及び１０３のそれぞれが各自の部分合計を格納するためにメモリ命令４１８を実行すれば、プロセッサ１０２及び１０３は、別の命令へ進んでよい（例えば、図３の３１２）。
【００６１】
しかしながら、プログラム１２２の部分３００、４００、又は５００がプロセッサ１０２及び１０３によってプログラム順序で実行された時、メモリ命令３０８では、部分合計メモリ命令４１８の前に、ＡＢを５２６により拡大し、その後、再びメモリへ書き込むことが求められる。図４及び５に示したように、メモリ命令３１０は、アセンブリメモリ命令４０４（現在のＡＢ値を取り出す）と、非メモリ命令４０６（現在のＡＢ値を２５６により拡大する）と、メモリ命令４０８（それぞれの拡大済みＡＢ値をメモリへ戻す）とに対応する。そのため、本発明がなければ、プロセッサ１０２及び１０３は、「ループ実行」部分３１４を処理するプロセッサ１０２及び１０３のそれぞれによる拡大済みＡＢ値のメモリへの全ての書き込み（例えば、メモリ命令４０８）が完了するまで、メモリ命令４１８を実行してプロセッサのそれぞれの部分合計をメモリに書き込むのを待つ必要があり、完了するまでの時間は非常に長くなり得る。したがって、一方のプロセッサ（例えば、１０２）は、他方のプロセッサ（例えば、１０３）がメモリ命令４１８を実行して自分の部分合計をメモリに書き込むのを待って停止する可能性がある。本発明に従った方法及びシステムによれば、メモリ命令マネージャ１３０は、第一のメモリ命令の前に第二のメモリ命令を実行するとプログラムの結果を変更することなく並列性能が高まる時に、プロセッサ１０２及び１０３がプログラム順序に従わずにメモリ命令を実行するのを促すことで、並列性能を改善する。図５に示した例において、メモリ命令マネージャ１３０は、任意の未決メモリ命令４０８の前にプロセッサ１０２及び１０３にメモリ命令４１８を実行させると、プロセッサ１０２又は１０３の機能停止が阻止され、並列性能が増加することを認識できる。
【００６２】
図２Ｂに戻ると、第二のメモリ動作を第一のメモリ動作の前に実行するべきである場合、メモリ命令マネージャ１３０は、並行して実行されるべき部分のメモリ命令に、異なるグループ番号を割り当て（ステップ２３２）、第一のメモリ動作の後、或いはこれに関連させて、異なるグループ番号を有するメモリバリア命令を提供する（ステップ２３４）。図５に示した例で続けると、メモリ命令マネージャ１３０は、グループ番号「３」（プログラム１２２内の命令に最初に割り当てたグループ番号「０」とは異なる）を第二のメモリ命令４１８に割り当て、図６に示したように、異なるグループ番号６０４を有するメンバ命令６０２を提供する。プロセッサ１０２及び１０３が第一のメモリ命令４０８の前に第二のメモリ命令４１８を実行するのを更に促すために、メモリ命令マネージャ１３０は、第一及び第二のメモリ命令に従って、表２において特定された一つ以上のｃｍａｓｋビットを設定する。例えば、「Ｓｙｎｃ」のためのｃｍａｓｋビットをメンバ命令６０２に設定して、グループ番号「３」を有する全ての未決メモリ動作が完了するまで、プロセッサ１０２及び１０３が将来のメモリ及び非メモリ動作を停止させるように促す。プロセッサ１０２及び１０３が「ループ実行」部分６００の処理を継続するためにメモリ命令４０８の一回以上の反復の完了を遅延させたと仮定すると、メンバ命令６０２の実行に応答して、プロセッサ１０２及び１０３は、メモリ４１８が完了するまで、遅延又は未決メモリ命令４０８の実行を待ち続ける可能性が高い。
【００６３】
メモリ命令マネージャ１３０は、次に、並行して実行するべきプログラム１２２の部分に更に多くのメモリ動作が存在するかを判断するために、ステップ２２２での処理を継続する。並行して実行するべきプログラム１２２の部分に更に多くのメモリ動作が存在しない場合、メモリ動作マネージャ１３０は、次に、並行して実行するべきプログラム１２２の部分が更に存在するかを判断する（ステップ２３６）。並行して実行するべき部分が更に存在する場合、メモリ命令マネージャ１３０は、並行して実行するべきプログラムの次の部分を特定し（ステップ２３８）、ステップ２０８での処理を継続する。並行して実行するべきプログラムの部分が他に存在しない場合、メモリ命令マネージャ１３０は、プロセッサ１０２及び１０３が実行するプログラム１２２にアクセスするのを許可し（ステップ２４０）、その後、処理を終了する。
【００６４】
図７は、プログラム内のメモリ命令に対するグループ番号の特定及び割り当てを行うためにメモリ命令マネージャ１３０によって実行される例示的プロセス７００を示すフローチャートを表している。一実施において、メモリ命令マネージャ１３０は、本発明に従った方法及びシステムにより並列性能が増加するように、プログラム１２２内の未決命令に対して使用されていない又は割り当てられていないグループ番号を特定する。
【００６５】
図８は、プロセス７００を実施するために、メモリ命令マネージャ１３０によって生成し得る例示的コード８０２を示す。図８に示したように、コード８０２は、後続のメモリ命令（例えば、図８の４１８）及び関連するメモリバリア命令（例えば、図８の６０２）で使用するために、それぞれのプロセッサ１０２又は１０３が未使用のグループ番号を特定できるように、メモリ命令マネージャ１３０によってプログラム１２２に挿入してよい。
【００６６】
最初に、メモリ命令マネージャ１３０は、現在のグループ番号を、プログラム１２２内のメモリ動作に割り当て得る複数のグループ番号の第一のものに設定する（ステップ７０２）。図８に示した実施において、メモリ命令マネージャ１３０は、プロセッサ１０２及び１０３に、現在のグループ番号８０４を「１」に設定させる（例えば、命令８０６及び８０８によって、プロセッサ１０２及び１０３は、レジスタ「％ｉ０」に格納された値を最初に「０」に設定し、その後、値を「１」に増分する）。
【００６７】
メモリ命令マネージャ１３０は、次に、現在のグループ番号を有するプログラム１２２内のメモリ命令の数を特定する（ステップ７０４）。一実施において、メモリ命令マネージャ１３０は、現在のグループ番号８０４を使用するプログラム１２２内の命令の数を決定するために、現在のグループ番号８０４が割り当てられるメモリ命令（例えば、メモリ命令４１８）に先行するプログラム１２２内の各メモリ命令を調べてよい。別の実施において、メモリ命令セット１３２は、プロセッサ１０２又は１０３に現在のグループ番号８０４を有するプログラム１２２内の命令の数をランタイムで特定させるために、メモリ命令マネージャ１３０がコード８０２の一部としてプログラム１２２に挿入し得る、一つ以上のクエリ命令８１０及び８１２を含んでよい。例えば、メモリ命令セット１３２は、クエリリード命令８１０において指定された現在のグループ番号８０４に一致するグループ番号を有する任意の未解決のリード又はロード動作が存在するかをプロセッサ１０２又は１０３に特定させるクエリリード命令８１０を含んでよい。メモリ命令セット１３２は、クエリライト命令８１２において指定された現在のグループ番号８０４に一致するグループ番号を有する任意の未解決のライト又はストア動作が存在するかをプロセッサ１０２又は１０３に特定させるクエリライト命令８１２を含んでよい。二つ以上のクエリ命令８１０及び８１２がコード８０２に提供された時、メモリ命令マネージャ１３０は、更に、別の命令８１４を提供し、プロセッサに、現在のグループ番号８０４を有するメモリ命令の数８１６を計算させてよい。
【００６８】
次に、メモリ命令マネージャ１３０は、現在のグループ番号を有するプログラム１２２内のメモリ命令の数が所定の限界を上回るかを判断する（ステップ７０６）。図８に示した実施において、メモリ命令マネージャは、グループ番号８０４を有する未解決メモリ命令の数８１６が所定の限界であるゼロを上回るかをランタイムで決定する命令８１８をプロセッサ１０２又は１０３に実行させる。代替の実施において、メモリ命令マネージャ１３０は、ゼロではない所定の限界をプロセッサ１０２又は１０３に対して特定してよい。
【００６９】
数が所定の限界を上回る場合、メモリ命令マネージャ１３０は、現在のグループ番号を、プログラム１２２内の命令に割り当て得る複数のグループ番号の次のものに設定する（ステップ７０８）。図８に示す例示的実施において、数が所定の限界を上回る場合、メモリ命令マネージャは、プロセッサ１０２又は１０３に、現在のグループ番号８０４を増分させる（例えば、命令８０８を繰り返させる）。
【００７０】
数が所定の限界を上回らない場合、メモリ命令マネージャ１３０は、現在のグループ番号をプログラム１２２内のメモリ動作に割り当て（ステップ７０８）、その後、処理を終了する。図８に示すように、メモリ命令マネージャ１３０は、後続のメモリ命令４１８とメモリバリア命令６０２とに対する現在のグループ番号８０４の割り当てをランタイムでプロセッサに実行させてよい。
【００７１】
本発明の例示的実施の上記の説明は、例示及び説明の目的で提示したものである。上記の説明は、包括的なものではなく、開示した正確な形態に本発明を限定するものではない。変形及び変更が、上記の教示内容を踏まえて可能となり、或いは本発明の実践から取得し得る。例えば、説明した実施はソフトウェアを含むが、本実施は、ハードウェア及びソフトウェアの組み合わせ、或いはハードウェアのみで実施してよい。本発明は、オブジェクト指向及び非オブジェクト指向の両方のプログラムシステムで実施してよい。本発明の範囲は、特許請求の範囲及びその均等物によって画定される。
【図面の簡単な説明】
【００７２】
【図１】本発明に従った方法及びシステムでの使用に適したデータ処理システムのブロック図。
【図２Ａ】本発明に従った、プログラム内の命令をグループ化及び管理するメモリ命令マネージャによって実行される例示的プロセスを示すフローチャート。
【図２Ｂ】本発明に従った、プログラム内の命令をグループ化及び管理するメモリ命令マネージャによって実行される例示的プロセスを示すフローチャート。
【図３】メモリ命令マネージャによって特定されるメモリ命令を有するプログラムの例を示す図。
【図４】プロセッサ１０２及び１０３を対象とするアセンブリ言語における図３のプログラムの表現例を示す図。
【図５】プロセッサ１０２及び１０３を対象とするアセンブリ言語における図４のプログラムの表現例を示す図。
【図６】プロセッサ１０２及び１０３を対象とするアセンブリ言語における図５のプログラムの表現例を示す図。
【図７】プログラム内のメモリ命令に対するグループ番号の特定及び割り当てを行うためにメモリ命令マネージャによって実行される例示的プロセスを示すフローチャート。
【図８】図７のプロセスを実施するために、メモリ命令マネージャによってプログラムに挿入し得る例示的コードを示す図。
【図１】
2005332387.tif 000006
【図２Ａ】
2005332387.tif 000007
【図２Ｂ】
2005332387.tif 000008
【図３】
2005332387.tif 000009
【図４】
2005332387.tif 000010
【図５】
2005332387.tif 000011
【図６】
2005332387.tif 000012
【図７】
2005332387.tif 000013
【図８】
2005332387.tif 000014
【外国語明細書】
1. TITLE OF THE INVENTION
METHODS AND SYSTEMS FOR GROUPING AND MANAGING MEMORY INSTRUCTIONS
2. DETAILED DESCRIPTION OF THE INVENTION
CROSS REFERENCE TO RELATED APPLICATIONS
This application claims the benefit of the filing date of U.S. Provisional Application No. 60/568,494, entitled "METHODS AND SYSTEMS FOR GROUPING AND MANAGING INSTRUCTIONS," filed on May 4, 2004, which is incorporated herein by reference to the extent permitted be law.  
FIELD OF THE INVENTION
The present invention relates to methods and systems for improving the run-time performance of a program.  In particular, methods and systems consistent with the present invention relate to grouping and managing memory instructions associated with a program for execution by one or more processors.  
BACKGROUND
One way to increase the speed of a computer program is to divide its operations into separate tasks and execute those tasks concurrently on multiple processors.  The multiple processors may or may not share a common memory.  One of the slowest operations in a computer system is an operation involving memory-resident data.  Fetching operands (associated with one or more processor instructions) from memory may be hundreds or thousands of times slower than fetching those same operands from a register in the processor.  Storing data in memory can be comparably slow.  Although various common techniques are effective in hiding that latency from an application, the latency still affects the processor design and, thus, the performance of the application.  
It is common practice in processor design to attach a high-speed cache that stores the most recently referenced data and data near that recently referenced data.  A cache hides the latency of a fetch or read memory access by quickly supplying a copy of memory resident data that is stored in the cache.  A cache also hides the latency of a write memory access by various means.  
A cache interacts with the memory in units of cache lines.  A cache line is typically on the order of 32-512 bytes and is typically the smallest unit of exchange between the cache and the memory.  When a processor requests a value from memory that is not resident in the cache, the memory transfers a cache-line-sized chunk of data containing the data requested by the processor.  The entire line of data is stored in the cache.  The cache then extracts the requested data from the line transferred from memory and returns it to the processor.  When a processor writes data to an address that is represented in its cache, the cache copy is updated and the cache line is marked as "dirty."  When the line is flushed from cache back to memory, the line in memory is updated.  When a processor writes data to an address that is not represented in its cache, the line is read from memory as described above for a read and then the new data is written into the cache as described above for writes.
The effectiveness of caches in hiding memory latency is attenuated by several factors.  First, cache sizes are strongly constrained and the size of a single cache as a percentage of total physical memory continues to shrink.  As an example, Sun Microsystem, Inc.'s (trademark) E15K machine or computer can have up to 239 bytes of read access memory (RAM), but the UltraSparc-III (trademark) processor typically used in the E15K machine has only 223 cache, a ratio of 1:216.  Advances in the E15K machine may include incorporating 252 bytes of RAM and a per-processor cache size nowhere close to the 236 bytes that would be required to maintain a 1:216 ratio.  For this and other reasons, caches are becoming less effective for programs with a large working set and non-sequential access patterns because the likelihood of a desired value being in cache is dropping with the decline of the percentage of coverage.  (Percentage of coverage refers to the percentage of memory that can be covered with a particular cache.  For example, on a computer system with 512 megabytes of memory, an 8 megabytes cache covers 8/512*100 ≒ 1.6%.)  
Secondly, in conventional systems distance to memory is increasing in cycle terms, which typically causes memory access speed to increase, resulting in a performance problem.  As the distance to memory goes from hundreds of cycles to thousands of cycles, the difficulty of hiding the latency sharply increases.  The increased latency also causes problems in processor design because the processor needs to keep track of an operation until it is complete.  Informally speaking, a write is typically considered complete when memory is updated.  If memory is 1000 cycles away from the processor and a write can be issued in every cycle then the processor must keep track of at least 2000 outstanding memory transactions in order to avoid stalling on a write-buffer-full (2000 transactions = 1 transaction/cycle = 1000 cycles to send the data to memory and 1000 cycles for the acknowledgement to return.).  Keeping track of 2000 independent transactions is typically quite difficult.  
In conventional systems, memory access speed is also increased and parallel performance decreased by the way that conventional processors execute programs that use certain data structures.  Conventional processors typically interact sequentially with a sequence of homogeneous memory operations.  For example, a processor may give preference to reads over writes, but does not usually distinguish between the relative importances of individual reads.  A processor executing a thread in a program running in parallel on multiple processors often does a series of memory operations related to computation and then a final memory operation to synchronize its activities with the other processors operating in parallel.  It may then issue memory operations to get more work for itself so that it may proceed on an independent part of the computation and it will block all processing until its requests for more work are satisfied.  In many computations, it is much more important to get more work than to report that previous work has completed, but the sequential nature of the way that processors interact with streams of memory operations stalls that important request behind less important requests.  As the distance to memory increases and techniques such as caching become less capable of hiding the latencies involved, the problem of having important operations stalled behind ever-slower operations of lower importance becomes more pressing.
Therefore, a need has long existed for a method and system that overcome the problems noted above and others previously experienced.
SUMMARY
Methods, systems, and articles of manufacture consistent with the present invention improve the parallel performance of a program by associating a plurality of instructions in the program with a respective one of a plurality of group identifiers and managing the execution of a plurality of instructions associated with a program in accordance with the group identifiers.  
In accordance with methods consistent with the present invention, a method in a data processing system for managing the execution of a plurality of instructions associated with a program is provided.  The method includes assigning a first group identifier to one or more of the plurality of instructions appearing in the program after a first of the plurality of instructions; assigning a second group identifier to the first instruction, wherein the second group identifier is different than the first group identifier; and providing a memory barrier instruction associated with the first instruction and having the second group identifier such that one or more processors with access to the program execute the plurality of instructions of the program in an order in accordance with the second group identifier associated with the memory barrier instruction.
In accordance with methods consistent with the present invention, a method in a data processing system for managing the execution of a plurality of memory instructions associated with a program is provided.  The method includes determining whether execution of a second of the memory instructions before a first of the plurality of memory instructions increases parallel performance of the program.  When it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program, the method further includes assigning one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction.  The method may also include providing a memory barrier instruction associated with the second memory instruction and having the one group identifier such that one or more processors with access to the program are prompted to execute the second memory instruction before the first memory instruction.  
In accordance with articles of manufacture consistent with the present invention, a computer-readable medium containing instructions for managing the execution of a plurality of instructions associated with a program.  The method includes assigning a first group identifier to one or more of the plurality of instructions appearing in the program after a first of the plurality of instructions; assigning a second group identifier to the first instruction, wherein the second group identifier is different than the first group identifier; and providing a memory barrier instruction associated with the first instruction and having the second group identifier such that one or more processors with access to the program execute the plurality of instructions of the program in an order in accordance with the second group identifier associated with the memory barrier instruction.  
In accordance with articles of manufacture consistent with the present invention, a computer-readable medium containing instructions for managing the execution of a plurality of memory instructions associated with a program.  The method includes determining whether execution of a second of the memory instructions before a first of the plurality of memory instructions increases parallel performance of the program; when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program, assigning one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction; and providing a memory barrier instruction associated with the second memory instruction and having the one group identifier such that one or more processors with access to the program are prompted to execute the second memory instruction before the first memory instruction.
In accordance with systems consistent with the present invention, a data processing system is provided.  The data processing system comprises a memory device and one or more processors.  The memory device includes a first program having a plurality of instructions.  The memory device further includes an instruction manager program that assigns a first group identifier to one or more of the plurality of instructions appearing in the first program after a first of the plurality of instructions, assigns a second group identifiers to the first instruction, wherein the second group identifier is different than the first group identifier, and provides a memory barrier instruction associated with the first instruction and having the second group identifier.  The one or more processors are configured to run the instruction manager program and the first program such that the processors execute the plurality of instructions of the first program in an order in accordance with the second group identifier associated with the memory barrier instruction.
In accordance with systems consistent with the present invention, a data processing system is provided.  The data processing system comprises a memory device and one or more processors.  The memory device includes a first program having a plurality of memory instructions.  The memory device further includes an instruction manager program that determines whether execution of a second of the memory instructions before a first of the plurality of memory instructions increases parallel performance of the program, when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program, assigns one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction, and provides a memory barrier instruction associated with the second memory instruction and having the one group identifier.  The one or more processors are configured to run the instruction manager program and the first program such that the one or more processors are prompted to execute the second memory instruction before the first memory instruction in response to executing the memory barrier instruction. 
In accordance with systems consistent with the present invention, a system is provided that includes means for assigning a first group identifier to one or more of a plurality of instructions appearing in a program after a first of the plurality of instructions; means for assigning a second group identifier to the first memory instruction, wherein the second group identifier is different than the first group identifier; and means for providing a memory barrier instruction associated with the first memory instruction and having the second one group identifier such that one or more processors with access to the program execute the plurality of instructions of the first program in an order in accordance with the different one group identifier associated with the memory barrier instruction.
In accordance with systems consistent with the present invention, a system is provided that includes means for determining whether execution of a second of a plurality of memory instructions in a program before a first of the plurality of memory instructions increases parallel performance of the program; means for, when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program, assigning one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction; and providing a memory barrier instruction associated with the second memory instruction and having the one group identifier such that one or more processors with access to the program are prompted to execute the second memory instruction before the first memory instruction.
In accordance with systems consistent with the present invention, a data processing system is provided.  The data processing system comprises a memory and a processing unit.  The memory includes a first program having a plurality of instructions, the plurality of instructions including a plurality of memory instructions and a memory barrier instruction, the memory barrier instruction and each of the plurality of memory instructions being associated with a respective one of a plurality of group numbers.  The processing unit is configured to execute the plurality of instructions of the first program in an order in accordance with the respective one of the group numbers associated with the memory barrier instruction.
The above-mentioned and other features, utilities, and advantages of the invention will become apparent from the following detailed description of the preferred embodiments of the invention together with the accompanying drawings.
Other systems, methods, features, and advantages of the invention will become apparent to one with skill in the art upon examination of the following figures and detailed description.  It is intended that all such additional systems, methods, features, and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying drawings.
The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate one or more implementations of the invention and, together with the description, serve to explain the advantages and principles of the invention.  
DETAILED DESCRIPTION
In accordance with methods, systems, and articles of manufacture consistent with the present invention, a memory instruction manager is provided to group and manage memory instructions associated with a program for execution by one or more processors.  
Figure 1 depicts a block diagram of a data processing system 100 suitable for use with methods and systems consistent with the present invention.  Data processing system 100 comprises a central processing unit (CPU) 102, an input output I/O unit 104, a memory 106, a cache 107, a secondary storage device 108, and a video display 110.  Data processing system 100 may further comprise standard input devices such as a keyboard, a mouse or a speech processing means (each not illustrated).  Data processing system 100 may also include a second CPU 103 for parallel processing instructions of a program contained in memory 106 or secondary storage 108.  These various components of a data processing system may be physically located remotely from each other and connected via a network.  
Memory 106 may contain an operating system 111 for managing the operation of applications or programs run using the processors 102 and 103.  Memory 106 may also contain a compiler 112 and source code modules A-N (e.g., 114-116) translated by the compiler 112 to produce corresponding object code modules A-N (e.g., 118-120).  The compiler 112 or a linker (not shown in figures) may link the object modules 118-120 to produce an application or executable program 122 to be run using one or more target processors, such as CPU 102 and 103.  The executable program 122 has a plurality of instructions (not shown in Figure 1) organized by the compiler in program order in accordance with source modules 114-116.  CPUs 102 and 103 may perform the instructions in program 122 in an execution order, which may not correspond with the program order but is at least consistent with program order such that an unexpected result does not occur and processor self consistency is maintained as further explained below.  
The compiler 112 may be a static compiler, a dynamic compiler (such as a Sun Virtual Machine(trademark)) that interprets source modules 114-116 at run-time for the target processor 102 or 103, or a combination of the two.
Compiler 112 may also include a memory instruction manager 130 and a set of memory instructions 132 that are recognized by the CPUs 102 and 103 in accordance with methods and systems consistent with the present invention.  As discussed in further detail below, the memory instruction manager 130 is operably configured to identify memory instructions in the set 132 that correspond to compiled or object module 118-120 memory instructions contained in the program 122, and to manage the order of execution of the memory instructions contained in the program 122 by the processors 102 and 103.   
The memory instruction manager 130 may comprise or may be included in one or more code sections containing instructions for performing respective operations.  While the optimization tool 130 and other programs (e.g., compiler 112) are described as being implemented as software, the present implementation may be implemented as a combination of hardware and software or hardware alone.  Also, one of skill in the art will appreciate that programs may comprise or may be included in a data processing device, which may be a server, communicating with data processing system 100.
In addition, although aspects of one implementation shown in Figure 1 are depicted as being stored in memory, one skilled in the art will appreciate that all or part of systems and methods consistent with the present invention may be stored on or read from other computer-readable media, such as secondary storage devices, like hard disks, floppy disks, and CD-ROM; a carrier wave received from a network such as the Internet; or other forms of ROM or RAM either currently known or later developed.  Further, although specific components of data processing system 100 have been described, one skilled in the art will appreciate that a data processing system suitable for use with methods, systems, and articles of manufacture consistent with the present invention may contain additional or different components.
A memory operation or instruction may be a read memory instruction, a write memory instruction, an atomic update instruction, a cache operation, or a control operation, each of which are included in instruction set 132.  An atomic update instruction is recognized by the memory instruction manager 130 as an operation during which processor 102 or 103 simultaneously reads a memory location for a counter and increments the counter in the same bus operation if another processor 103 or 102 has not written to the memory location (preventing an erroneous update from occurring).
In one implementation, instruction set 132 includes two cache operations defined as a flush instruction and an invalidate instruction.  A flush instruction with an associated group number causes the processor 102 or 103 to block fetching, loading, decoding, or execution of another memory instruction in the program 122 having the same group number, until the processor 102 or 103 completes all outstanding writes to update the cache line containing the memory address specified by the flush instruction and then writes dirty data to memory.  The flush operation causes the processor 102 or 102 to write all dirty data in a cache line to memory so that a subsequent invalidate operation does not run the risk of losing valid data.  In one implementation, the processor 102 and 103 are configured such that non-dirty data is not used to modify memory.  This restriction inhibits the processor 102 and 103 from writing an entire cache line unless the entire line is dirty.  The flush instruction is recognized by the processors 102 and 103 as a write operation when processing a control operation (such as a memory barrier instruction described below) in accordance with methods and systems consistent with the present invention. 
An invalidate instruction causes the processor 102 or 103 to clear a valid bit (not shown in figures) on the cache line containing an address associated with the invalidate instruction.  If it is necessary to preserve dirty data in the cache line then a programmer or compiler 112 may precede the invalidate instruction with a flush instruction.  The invalidate instruction is recognized by the processors 102 and 103 as a write operation when processing a control operation (such as a memory barrier instruction described below) in accordance with methods and systems consistent with the present invention.  Each invalidate operation has a group number to allow memory barrier instructions against the invalidate operation, but data in the line that is affected by the invalidate operation may come from a write memory instruction or other operation using any group number.
As described in detail below, the memory instruction manager 130 associates a group number with a control operation in the program to guide the processor 102 or 103 to complete operations or instructions in the program in an optimal order.  
Processors 102 and 103 handle a read memory instruction, a write memory instruction, and an atomic update instruction in accordance with known techniques except that the processors 102 and 103 recognize that each read memory, write memory, and atomic update instruction has an associated group number, which in conjunction with a control instruction having a matching group number controls when the respective instruction is executed.
In one implementation, the membar instruction as described below is a variation of the SPARC V9 membar memory instruction described in The SPARC Architecture Manual, Version 9 except that the membar instruction is assigned a group number by the memory instruction manager 130 in accordance with methods and systems consistent with the present invention to control the operation of groups of memory operations in the program 122.  
The membar instruction may be used by the memory instruction manager 130 to perform one or more of the following three functions:  to provide order constraints between memory operations in the program 122, to control when a memory operation in the program 122 is completed, and to inform the processor 102 or 103 as to which operations in the project are currently more important to execute.  
In one implementation, the assembly language syntax used for the membar instruction is:  "membar membar_mask [,group number]."  In this implementation, the membar_mask is the bitwise OR of a mmask field (e.g., bits 0-3) and a cmask field (e.g., bits 4-6) in the membar instruction as described below.  The group number (e.g., bits 7-12) of the membar instruction identifies the group of memory instructions (e.g., other pending read or write memory operations in the program 122) on which the processor 102 or 103 is to block processing.  For example, if the group number assigned to the membar instruction is zero, the processor 102 or 103 applies the membar instruction to all outstanding or pending memory operations in the program 122.
As described in further detail below, the memory instruction manager 130 provides a membar instruction in a program 122 to introduce an order constraint between classes of memory operations appearing before the membar instruction and memory operations following the membar instruction in the program.  The particular classes of memory operations are specified by the mmask field as shown in Table 1 below.  Memory operation classes include a load (e.g., read from memory reference into processor 102 or 103) and a store (e.g., write to memory reference from processor 102 or 103).  The membar instruction applies to all memory operations in all address spaces referenced by the issuing processor 102 or 103, but has no effect on memory references by other processors.  The mmask field imposes an order constraint on memory references appearing before and after the membar instruction in the program 122.  Any or all of the mmask bits described in Table 1 may be set by the memory instruction manager 130.  
2005332387.tif 000015
Bits in the cmask field as described in Table 2 below specify additional constraints on the order of memory operations and the processing of instructions by processors 102 and 103.  If no cmask bits are set in the membar_mask of a membar instruction, then the membar instruction causes the processor 102 or 103 to enforce the partial ordering specified by the mmask field.  If cmask field is nonzero, then completion as well as partial order constraints are applied by the processors 102 and 103 based on the group number assigned to the membar instruction.
2005332387.tif 000016
By assigning a group number to memory operations subject to parallel processing that is different than a group number assigned to memory operations not-subject to parallel processing and then providing a membar instruction with the different group number as described below, the memory instruction manager 130 is able manage the execution of the memory instructions by the processors 102 and 103 by causing the processors to block access to the memory operations with the different group number in response to executing the membar instruction with the different group number.  Thus, the memory instruction manager 130 is able to significantly improve, among other things, the run-time speed of the parallel processing of the program 122 by providing a membar instruction with an assigned group number.  
For example, Table 3 below depicts a sequence or portion of instructions in the program 122 represented in psuedo code that the memory instruction manager 130 recognizes as being capable of parallel processing and provides a membar instruction (e.g., (b) "Set membar #StoreStore ...") having a group number that matches one or more preceding memory instructions (e.g., (a) "Write the words of a message ...") as described in further detail below.  In accordance with systems and methods consistent with the present invention, processors 102 and 103 execute the sequence in Table 3 by writing a message to memory 106 or cache 107, writing a word to memory to indicate to a reader that the message is complete (e.g., (c)), and performing, in parallel with instructions (a), (b), and (c), a series of read and write memory instructions (e.g., (d) "Do loop computation ...") unrelated to the message without blocking the execution of the unrelated reads and writes to memory.
2005332387.tif 000017
In this example, the membar instruction (b) is assigned a group number of 3 by the memory instruction manager 130, which causes the processor 102 and 103 to block the write memory instruction (c) having the same group number of 3 until all write memory instructions (a) are complete.  However, since the memory instruction manager 130 assigns a different group number not equal to 3 to the read and write memory instructions in (d), the memory instruction manager 130 is able to cause processors 102 and 103 to perform in parallel (rather than block initiating) the read and write instructions in (d) as well as any subsequent memory and non-memory operation (not shown in Table 3) in program 122.
Figures 2A-2B depict a flow diagram illustrating an exemplary process 200 performed by the memory instruction manager 130 for grouping and managing for execution instructions in a program in accordance with methods, systems, and articles of manufacture consistent with the present invention.  The memory instruction manager 130 improves the performance of the program by inhibiting important operations or instructions from being stalled behind operations of lower importance during parallel execution of the program.  Systems and methods consistent with the present invention classify memory operations of a program into groups and then associate a memory control operation with one of the groups to cause a processor to expedite processing of the memory control operations not assigned to the one group.  
Initially, the memory instruction manager 130 receives a program to be executed (step 202).  The memory instruction manager 130 may receive a program 122 via the compiler 122 during compilation of the program 122.  In another implementation, a programmer or user may identify the program 122 to the memory instruction manager 130 using a known data input technique, such as keyboard entry or a mouse click on a user interface (not shown in figures). 
The memory instruction manager 130 then assigns every memory operation in the program a group number (step 204).  In one implementation, the memory instruction manager 130 may identify each memory instruction in the program 122 and assign each a default group number, such as zero.  The memory instruction manager 130 may use the instruction set 132 to identify a memory operation or instruction in the program 122.  In another alternative, memory instructions in instruction set 132 may be pre-assigned a respective group number.  In this implementation, when the program 122 is compiled, each memory operation in the program 122 is associated by the compiler 112 with the same group number as pre-assigned for the respective memory instruction in instruction set 132.  
Figure 3 depicts an example portion 300 of program 122 having non-memory instructions 302, 304, 306 and memory instructions 308, 310, and 312 identified by memory instruction manager 130 before the memory instruction manager 130 assigns a group number to an instruction 302, 304, 306, 308, 310, or 312.  
Figure 4 depicts an example representation 400 of the portion 300 of program 122 in an assembly language targeted for processor 102 and 103, in which assembly memory instructions 404, 408, 418 and non-memory instructions 402, 406, 410, 412, 414, 416 correspond to "SUM=0" instruction 302 and a "do loop" portion 314 of the program 122.  Non-memory instructions 402, 406, 410, and 412 each access contents of one or more processor registers rather than a memory location to complete the respective operation.  However, one skilled in the art will appreciate that non-memory instructions 402, 406, 410, and 412 may be coded similar to instructions 404,408, and 418, such that a register of processor 102 or 103 holds a memory location to access in order to complete the respective memory operation 306, or 308 of the "do loop" portion 314.  
Figure 5 depicts an example representation 500 of the portion 300 of program 122 shown in Figure 4 after the memory instruction manager 130 assigns a group number 504, 508, 518 to each memory instruction 404, 408, and 418.  The memory instruction manager 130 may also assign a group number 502, 506, 510, 512, 514, and 516 to non-memory operations 402, 406, 410, 412, 414, and 416.  In one implementation, the group number 504, 508, or 518 may be assigned based upon the type of memory operation, such as load (or read) memory operations being assigned to group 1 and store (or write) memory operations being assigned to group 2.  In an alternative embodiment, the memory instruction manager may assign each memory operation 404, 408, and 418 the same initial group number, such as the group number 0.  
Returning to Figure 2A, the memory instruction manager 130 identifies a portion of the program 122 that is to be run in parallel (step 206).  A programmer or the compiler 112 may indicate to the memory instruction manager 130 a portion of the program 122 to be run in parallel by demarcating the portion using delimiters.  In the example shown in Figure 3, a beginning delimiter 316 (e.g., "!$omp parallel") and an end delimiter 318 (e.g., "!$omp end") may be used by compiler 112 to identify the portion 314 of the program 122 between the two delimiters 316 and 318 for parallel processing.  
Next, the memory instruction manager 130 identifies a first memory operation (step 208) and a second memory operation in the portion of the program 122 (step 210).  As described above, the memory instruction manager 130 is able to recognize instructions 404, 408, and 418 as memory instructions and that these memory instructions 402, 408, and 418 correspond to the "do loop" portion 314 of the program 122 to be run in parallel.  In the example shown in Figures 3 through 5, the memory instruction manager 130 initially identifies memory instruction 404 as the first memory operation and memory instruction 408 as the second memory instruction.  As discussed below, the memory instruction manager 130 may subsequently identify memory instruction 408 as the first memory operation and memory instruction 418 as the second memory operation in accordance with the present invention.  The memory instruction manager 130 may alternatively identify first and second memory operations out of program order.  
The memory instruction manager 130 then determines whether the second memory operation is related to the first memory operation (step 212).  The memory instruction manager 130 may determine that the second memory operation is related to the first memory operation when both memory operations reference the same memory location, address or bank of addresses.  In the example set forth in Table 3 above, the memory instruction manager is thus able to determine that memory instruction (c) references the same address or bank of addresses (e.g., refers to the same message) as memory instruction (a).  In the example shown in Figures 4 and 5, the memory instruction manager 130 is able to determine that memory instruction 404 is related to memory instruction 408 because both of these instructions reference the same memory address stored in register "%g1."  The memory instruction manager 130 is also able to recognize that memory instruction 418 is not related to memory instruction 404 or 408 because memory instruction 418 references another memory address stored in register "%g3."
If the second memory operation is related to the first memory operation, the memory instruction manager 130 determines whether execution of the second memory instruction is dependent on the first memory instruction (step 214).  The second memory instruction is dependent on the first memory instruction when, for example, the first memory instruction causes the processor 102 or 103 to store a value to a memory address and the second memory instruction requires the processor 102 or 103 to access the stored value from the memory address.  Thus, memory instruction manager 130 is able to recognize when one memory instruction is dependent on another where the processor 102 or 103 is required to adhere to processor self-consistency rules and avoid obtaining a result that violates the order of the program 122.  For example, memory instruction manager 130 is able to recognize that memory instruction 308 in Figure 3 requires that processor 102 or 103 scale "AB(I)" by 526 (e.g., perform instructions 404 and 406) before the scaled AB(I) value is written back to the same memory location (e.g., before performing memory instruction 408).  Thus, the memory instruction manager 130 is able to recognize that memory instruction 408 is dependent on memory instruction 404 as executing memory instructions 404 and 408 out of program order would generate a result that is not consistent with program order execution and likely to cause a run-time error.  In the example described in reference to Table 3, the memory instruction manager 130 is able to recognize that the second memory instruction (c) is related but not dependent on the first memory instruction (a) because the second memory instruction (c) does not necessarily use a value from the same memory location as referenced by the first memory instruction (a) in order to complete the execution of the second memory instruction (c) (e.g., waiting for the instruction (a) to be completed before signaling the reader by completing instruction (c)).
If the second memory operation is related but not dependent on the first memory operation, the memory instruction manager 130 assigns the first memory instruction a different group number (step 216) and assigns the second memory instruction the different group number (step 218).  In the example shown in Figure 3, the memory instruction manager 130 assigns memory instruction (a) and memory instruction (c) a group number of "3," which the memory instruction manager 130 recognizes as being an unused group number as described in further detail below.  
Next, the instruction manager 130 provides a memory barrier instruction with the different group number after or in association with the first memory operation (step 218).  In the embodiment discussed in reference to Table 3, the instruction manager 130 provides the membar instruction (b) with the same group number "3" as the memory instruction (a).  In addition, the instruction manager 130 may also set the mmask or cmask bits to correspond with the order or completion constraint (e.g., "StoreStore") required to inhibit processor 102 or 103 from completing the second memory instruction (e.g., instruction (c) in Table 3) before the first memory instruction (e.g., instruction (a)) but allowing a third or other unrelated instruction to be performed out of program order (e.g., instruction (c) in Table 3).  
If the second memory operation is related and dependent on the first memory operation, the memory instruction manager 130 continues processing at step 222 described below.  In the example shown in Figures 4-5, the memory instruction manager 130 is able to determine that memory instruction 408 depends on memory instruction 404 such that the processor 102 or 103 will not likely not violate self-consistency rules to perform memory instruction 408 before memory instruction 404.  Thus, memory instruction manager 130 recognizes that in this instance a membar instruction is not required to impose an order constraint between related and dependent memory instructions.
Next, the memory instruction manager 130 determines whether there are more memory operations in the portion of the program 122 to be run in parallel (step 222).  If there are more memory operations, the memory instruction manager 130 references the second memory operation as the first memory operation (step 224), identifies the next memory operation in the portion of the program 122 to be run in parallel (step 226), and references the next memory operation as the second memory operation (step 228) before continuing processing at step 212.  Thus, in the example shown in Figure 5, the memory operation manager 130 now identifies memory instruction 408 as the first memory instruction, identifies the next memory instruction 418 as the second memory instruction, and continues processing at step 212.
If the second memory operation is not related to the first memory operation, the memory instruction manager 130 determines whether to prompt execution of the second memory operation before the first memory operation (step 230).  In one implementation, the memory instruction manager prompts execution of the second memory operation before the first memory operation when parallel performance by one processor (e.g., processor 102) is stalled awaiting the execution of the second memory operation by another processor (e.g., processor 103).  
In example shown in Figure 5, the memory instruction manager 130 is also able to recognize that the "do loop" in the portion 314 of the program 122 of Figure 3 scales the first N elements of "AB" by 526 and sums them into "SUM."  To accommodate parallel processing of the portion 314, the memory instruction manager 130 divides the loop iterations over the available processors 102 and 103 so that each processor 102 and 103 performs instructions 404, 406, 408, 410, 412, and 416 for part of the "do loop" (e.g., portion 314 of the program 122) in parallel with the other processors.  At the end of the loop, each processor 102 and 103 has a partial sum (e.g., store in processor register "%f6" in Figures 4 and 5) corresponding to the sum of the elements in its part of AB.  To complete the "do loop" portion 314 in the examples shown in Figures 4 & 5, the compiler 112 or memory instruction manager 130 requires that the processors 102 and 103 combine their partial sums into one final sum in accordance with memory instruction 310 by first storing their respective partial sum to memory via memory instruction 418.  Once each of the processors 102 and 103 have executed memory instruction 418 to store its respective partial sum, the processor 102 and 103 may proceed to another instruction (e.g., 312 of Figure 3).  
However, when the portion 300, 400, or 500 of program 122 is executed in program order by processors 102 and 103, memory instruction 308 requires that AB be scaled by 526 and then written back to memory before the partial sum memory instruction 418.  As shown in Figures 4 and 5, memory instruction 310 corresponds to assembly memory instruction 404 (for retrieving the current AB value), non-memory instruction 406 (for scaling the current AB value by 256), and memory instruction 408 (for storing the respective scaled AB value back to memory).  Therefore, without the present invention, the processors 102 and 103 must wait to execute memory instruction 418 to write the processor's respective partial sum to memory until the completion of all writes to memory of the scaled AB values (e.g., memory instruction 408) by each of the processors 102 and 103 processing the "do loop" portion 314, which may be quite a long time.  Thus, one processor (e.g., 102) may be stalled waiting for the other processor (e.g., 103) to execute memory instruction 418 to write its respective partial sum to memory.  In accordance with methods and systems consistent with the present invention, the memory instruction manager 130 improves parallel performance by prompting processors 102 and 103 to execute memory instructions out of program order when execution of a second memory instruction before a first memory instruction increases parallel performance without altering a program result.  In the example shown in Figure 5, the memory instruction manager 130 is able to recognize that causing processors 102 and 103 to perform memory instruction 418 before any pending memory instruction 408 will inhibit processor 102 or 103 from stalling and increase parallelism performance. 
Returning to Figure 2B, if the second memory operation should be executed before the first memory operation, the memory instruction manager 130 assigns the memory instruction in the portion to be run in parallel a different group number (step 232) and provides a memory barrier instruction with the different group number after or in association with the first memory operation (step 234).  Continuing with the example shown in Figure 5, the memory instruction manager 130 assigns the group number "3" (which is different from the group number "0" initially assigned to instructions in program 122) to the second memory instruction 418 and provides the membar instruction 602 with the different group number 604 as depicted in Figure 6.  To further prompt the processor 102 and 103 to execute the second memory instruction 418 before the first memory instruction 408, the memory instruction manager 130 sets one or more of the cmask bits identified in Table 2 in accordance with the first and second memory instructions.  For example, the cmask bit for "Sync" is set in membar instruction 602 to prompt the processor 102 or 103 to stall future memory and non-memory operations until all pending memory operations having the group number "3" are completed.  Assuming processors 102 and 103 have delayed completion of one or more iterations of memory instruction 408 in order to continue processing the "do loop" portion 600, in response to executing membar instruction 602, processors 102 and 103 will likely continue to wait to execute the delayed or pending memory instructions 408 until memory instruction 418 is completed.  
The memory instruction manager 130 then continues processing at step 222 to determine whether there are more memory operations in the portion of the program 122 to run in parallel.  If there are no more memory operations in the portion of the program 122 to run in parallel, the memory operation manager 130 then determines whether there are more portions of the program 122 to run in parallel (step 236).  If there are more portions to run in parallel, the memory instruction manager 130 identifies the next portion of the program to run in parallel (step 238) and continues processing at step 208.  If there are no more portions of the program to run in parallel, the memory instruction manager 130 allows processors 102 and 103 to access the program for execution 122 (step 240) and then ends processing.
Figure 7 depicts a flow chart illustrating an exemplary process 700 performed by the memory instruction manager 130 to identify and assign a group number to a memory instruction in the program.  In one implementation, the memory instruction manager 130 identifies a group number that is unused or not currently assigned to a pending instruction in the program 122 so that parallel performance is increased in accordance with methods and systems consistent with the present invention.  
Figure 8 depicts exemplary code 802 that may be generated by the memory instruction manager 130 to implement the process 700.  As shown in Figure 8, the code 802 may be inserted by the memory instruction manager 130 into the program 122 to allow the respective processor 102 or 103 to identify an unused group number for use with a subsequent memory instruction (e.g., 418 in Figure 8) and an associated memory barrier instruction (e.g., 602 in Figure 8).
Initially, the memory instruction manager 130 sets a current group number to the first of a plurality of group numbers that may be assigned to the memory operation in the program 122 (step 702).  In the implementation shown in Figure 8, the memory instruction manager 130 causes processor 102 and 103 to set current group number 804 to "1" (e.g., instructions 806 and 808 cause processors 102 and 103 to set value stored in register "%i0" initially to "0" and then increment the value to "1").
The memory instruction manager 130 then identifies the number of memory instructions in the program 122 that have the current group number (step 704).  In one implementation, the memory instruction manager 130 may review each memory instruction in the program 122 preceding the memory instruction (e.g., memory instruction 418) to be assigned the current group number 804 to determine the number of instructions in the program 122 using the current group number 804.  In another implementation, memory instruction set 132 may include one or more query instructions 810 and 812 that the memory instruction manager 130 may insert in the program 122 as part of the code 802 to cause the processor 102 or 103 at run-time to identify the number of instructions in the program 122 having the current group number 804.  For example, the memory instruction set 132 may include a query-read instruction 810 that causes the processor 102 or 103 to identify whether there are any read or load operations outstanding with a group number that matches the current group number 804 specified in the query read instruction 810.  The memory instruction set 132 may also include a query-write instruction 812 that causes the processor 102 or 103 to identify whether there are any write or store operations outstanding with a group number that matches the current group number 804 specified in the query-write instruction 812.  When two or more query instructions 810 and 812 are provided in the code 802, the memory instruction manager 130 may also provide another instruction 814 to cause the processor to calculate the number 816 of memory instructions having the current group number 804.
Next, the memory instruction manager 130 determines whether the number of memory instructions in the program 122 that have the current group number exceeds a predetermined limit (step 706).  In the implementation shown in Figure 8, the memory instruction manager causes the processor 102 or 103 to execute instruction 818 to determine at run-time whether the number 816 of outstanding memory instructions having the group number 804 exceeds the predetermined limit of zero.  In an alternative implementation, memory instruction manager 130 may identify a non-zero predetermined limit to the processor 102 or 103.
If the number exceeds the predetermined limit, the memory instruction manager 130 sets the current group number to the next of the plurality of group numbers that may be assigned to an instruction in the program 122 (step 708).  In the example implementation shown in Figure 8, if the number exceeds the predetermined limit, the memory instruction manager causes the processor 102 or 103 to increment the current group number 804 (e.g., repeat instruction 808).
If the number does not exceed the predetermined limit, the memory instruction manager 130 assigns the current group number to the memory operation in the program 122 (step 708) and then ends processing.  As shown in Figure 8, the memory instruction manager 130 may cause the processor to assign the current group number 804 to the subsequent memory instruction 418 and memory barrier instruction 602 at run-time.
The foregoing description of exemplary implementations of the invention has been presented for purposes of illustration and description.  It is not exhaustive and does not limit the invention to the precise form disclosed.  Modifications and variations are possible in light of the above teachings or may be acquired from practicing the invention.  For example, the described implementation includes software but the present implementation may be implemented as a combination of hardware and software or hardware alone.  The invention may be implemented with both object-oriented and non-object-oriented programming systems.  The scope of the invention is defined by the claims and their equivalents.
3. BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 depicts a block diagram of a data processing system suitable for use with methods and systems consistent with the present invention; 
Figures 2A-2B depict a flow chart illustrating an exemplary process performed by a memory instruction manager grouping and managing instructions in a program consistent with the present invention; 
Figure 3 depicts an example of a program having memory instructions identified by the memory instruction manager;
Figure 4 depicts an example representation of the program of Figure 3 in an assembly language targeted for processor 102 and 103; 
Figure 5 depicts an example representation of the program of Figure 4 in an assembly language targeted for processor 102 and 103; 
Figure 6 depicts an example representation of the program of Figure 5 in an assembly language targeted for processor 102 and 103; 
Figure 7 depicts a flow chart illustrating an exemplary process performed by the memory instruction manager to identify and assign a group number to a memory instruction in the program; and
Figure 8 depicts exemplary code that may be inserted by the memory instruction manager into the program to implement the process in Figure 7.
1.  A method in a data processing system for managing the execution of a plurality of instructions associated with a program, the method comprising the steps of:
assigning a first group identifier to one or more of the plurality of instructions appearing in the program after a first of the plurality of instructions; 
assigning a second group identifier to the first memory instructions; 
wherein the second group identifier is different than the first group identifier; and 
providing a memory barrier instruction associated with the first memory instruction and having the second group identifier such that one or more processors with access to the program executes the plurality of instructions of the program in an order in accordance with the second group identifier associated with the memory barrier instruction.
2.  The method of claim 1, wherein the one or more processors are inhibited from executing the second instruction before the first instruction while being allowed to execute the one or more instructions assigned the first group identifier before the first instruction. 
3.  The method of claim 1, further comprising assigning a third group identifier to a third of the instructions appearing in the program before the first instruction, wherein the memory barrier instruction having the second group identifier prompts the one or more processors to execute the first instruction before the third instruction.
4.  The method of claim 1, wherein the plurality of instructions includes at least two classes, the first and second instructions and the memory barrier instruction reflect an order constraint between the at least two classes in accordance with the second group identifier.
5.  The method of claim 1, wherein the plurality of instructions includes at least two classes, the first and second instructions and the memory barrier instruction reflect an order constraint among one of the at least two classes in accordance with the second group identifier.
6.  The method of claim 1, wherein the memory barrier instruction reflects a completion contraint that causes the one or more processors to perform each of the plurality of instructions appearing in the program before the memory barrier instruction and having the second group identifier before one of the plurality of instructions appearing in the program after the memory barrier instruction. 
7.  The method of claim 1, the step of assigning a second group identifier further comprises:
determining a number of the plurality of instructions that have the second group identifier; 
determining whether the number exceeds a predetermined value; and 
assigning the second group identifier to the first memory instruction in response to determining that the number does not exceed the predetermined value.
8.  A method in a data processing system for managing the execution of a plurality of memory instructions associated with a program, comprising the steps of:
determining whether execution of a second of the memory instructions before a first of the plurality of memory instructions increases parallel performance of the program;
when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program,
assigning one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction; and 
providing a memory barrier instruction associated with the second memory instruction and having the one group identifier such that one or more processors with access to the program are prompted to execute the second memory instuction before the first memory instruction.
9.  The method of claim 8, the step of assigning one of a plurality of group identifiers further comprises:
determining a number of the plurality of memory instructions that have the one group identifier; 
determining whether the number exceeds a predetermined value; and 
assigning the one group identifier to the second memory instruction in response to determining that the number does not exceed the predetermined value.
10.  A computer-readable medium containing instructions for controlling a data processing system to perform a method for managing the execution of a plurality of instructions associated with a program, the method comprising the steps of:
assigning a first group identifier to one or more of the plurality of instructions appearing in the program after a first of the plurality of instructions; 
assigning a second group identifier to the first instruction, wherein the second group identifier is different than the first group identifier; and 
providing a memory barrier instruction associated with the first instruction and having the second group identifier such that one or more processors with access to the program execute the plurality of instructions of the program in an order in accordance with the second group identifier associated with the memory barrier instruction.
11.  The computer-readable medium of claim 10, wherein the one or more processors are inhibited from executing the second instruction before the first instruction while being allowed to execute the one or more instructions assigned the first group identifier before the first instruction. 
12.  The computer-readable medium of claim 10, further comprising assigning a third group identifier to a third of the instructions appearing in the program before the first instruction, wherein the memory barrier instruction having the second group identifier prompts the one or more processors to execute the first instruction before the third instruction.
13.  The computer-readable medium of claim 10, wherein the plurality of instructions includes at least two classes, the first and second instructions and the memory barrier instruction reflect an order constraint between the at least two classes in accordance with the second group identifier.
14.  The computer-readable medium of claim 10, wherein the plurality of instructions includes at least two classes, the first and second instructions and the memory barrier instruction reflect an order constraint among one of the at least two classes in accordance with the second group identifier.
15.  The computer-readable medium of claim 10, wherein the memory barrier instruction reflects a completion contraint that causes the one or more processors to perform each of the plurality of instructions appearing in the program before the memory barrier instruction and having the second group identifier before one of the plurality of instructions appearing in the program after the memory barrier instruction. 
16.  The computer-readable medium of claim 10, the step of assigning a second group identifier further comprises:
determining a number of the plurality of instructions that have the second group identifier; 
determining whether the number exceeds a predetermined value; and 
assigning the second group identifier to the first instruction in response to determining that the number does not exceed the predetermined value.
17.  A computer-readable medium containing instructions for controlling a data processing system to perform a method for managing the execution of a plurality of memory instructions associated with a program, the method comprising the steps of:
determining whether execution of a second of the memory instructions before a first of the plurality of memory instructions increases parallel performance of the program;
when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program,
assigning one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction; and 
providing a memory barrier instruction associated with the second memory instruction and having the one group identifier such that one or more processors with access to the program are prompted to execute the second memory instuction before the first memory instruction.
18.  The computer-readable medium of claim 17, the step of assigning one of a plurality of group identifiers further comprises:
determining a number of the plurality of memory instructions that have the one group identifier; 
determining whether the number exceeds a predetermined value; and 
assigning the one group identifier to the second memory instruction in response to determining that the number does not exceed the predetermined value.
19.  A data processing system, comprising:
a memory device further comprising:
a first program having a plurality of instructions; and
an instruction manager program that assigns a first group identifier to one or more of the plurality of memory instructions appearing in the first program after a first of the plurality of instructions, assigns a second group identifier to the first instruction and wherein the second group identifier is different than the first group identifier and provides a memory barrier instruction associated with the first instruction and having the second group identifier; and
one or more processors that run the instruction manager program and the first program such that the one or more processors execute the plurality of instructions of the first program in an order in accordance with the second one group identifier associated with the memory barrier instruction.
20.  The data processing system of claim 19, wherein the one or more processors are inhibited from executing the second instruction before the first instruction while being allowed to execute the one or more instructions assigned the first identifier before the first memory instruction. 
21.  The data processing system of claim 19, the instruction manager program further comprises assigning a third group identifier to a third of the instructions appearing in the program before the first instruction, wherein the memory barrier instruction having the second group identifier prompts the one or more processors to execute the first instruction before the third instruction.
22.  The data processing system of claim 19, wherein the step of assigning a second group identifier further comprises:
determining a number of the plurality of instructions that have the second group identifier; 
determining whether the number exceeds a predetermined value; and 
assigning the second group identifier to the first instruction in response to determining that the number does not exceed the predetermined value.
23.  A data processing system, comprising:
a memory device further comprising:
a first program having a plurality of memory instructions; and
an instruction manager program that determines whether execution of a second of the memory instructions before a first of the plurality of memory instructions increases parallel performance of the program, when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program, assigns one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction, and provides a memory barrier instruction associated with the second memory instruction and having the one group identifier; and
one or more processors that run the instruction manager program and the first program such that the one or more processors are prompted to execute the second memory instuction before the first memory instruction in response to executing the memory barrier instruction. 
24.  The data processing system of claim 23, wherein the step of assigning one of a plurality of group identifiers further comprises:
determining a number of the plurality of memory instructions that have the one group identifier; 
determining whether the number exceeds a predetermined value; and 
assigning the one group identifier to the second memory instruction in response to determining that the number does not exceed the predetermined value.
25.  A system, comprising:
means for assigning a first group identifier to one or more of a plurality of instructions appearing in a program after a first of the plurality of instructions; 
means for assigning a second group identifier to the first instruction, wherein the second group identifier is different than the first group identifier; and 
means for providing a memory barrier instruction associated with the first memory instruction and having the second group identifier such that one or more processors with access to the program executes the plurality of instructions of the program in an order in accordance with the second group identifier associated with the memory barrier instruction.
26.  The system of claim 25, wherein the one or more processors are inhibited from executing the second instruction before the first instruction while being allowed to execute the one or more memory instructions assigned the first group identifier before the first instruction. 
27.  The system of claim 25, further comprising means for assigning a third group identifier to a third of the memory instructions appearing in the program before the first memory instruction, wherein the memory barrier instruction having the second group identifier prompts the one or more processors to execute the first instruction before the third instruction.
28.  The system of claim 25, wherein the means for assigning a second group identifier further comprises:
means for determining a number of the plurality of instructions that have the second group identifier; 
means for determining whether the number exceeds a predetermined value; and 
means for assigning the second group identifier to the first instruction in response to determining that the number does not exceed the predetermined value.
29.  A system, comprising:
means for determining whether execution of a second of a plurality of memory instructions in a program before a first of the plurality of memory instructions increases parallel performance of the program;
means for, when it is determined that execution of the second memory instruction before the first memory instruction increases parallel performance of the program, assigning one of a plurality of group identifiers to the second memory instruction that is not assigned to the first memory instruction; and providing a memory barrier instruction associated with the second memory instruction and having the one group identifier such that one or more processors with access to the program are prompted to execute the second memory instuction before the first memory instruction.
30.  The system of claim 29, wherein means for assigning one of a plurality of group identifiers further comprises:
means for determining a number of the plurality of memory instructions that have the one group identifier; 
means for determining whether the number exceeds a predetermined value; and 
means for assigning the one group identifier to the second memory instruction in response to determining that the number does not exceed the predetermined value.
31.  A data processing system comprising:
a memory comprising a first program having a plurality of instructions, the plurality of instructions including a memory barrier instruction, the memory barrier instruction and each of the plurality of memory instructions being associated with a respective one of a plurality of group numbers; and
a processing unit that is configured to execute the plurality of instructions of the first program in an order in accordance with the respective one of the group numbers associated with the memory barrier instruction.
32.  The data processing system of claim 31, wherein in response to executing the memory barrier instruction, the processing unit executes a first of the plurality of memory instructions associated with the same one of the group numbers as the memory barrier instruction and appearing before the memory barrier instruction in the program before executing a second of the plurality of memory instructions having the same one group number and appearing after the memory barrier instruction in the program.
33.  The data processing system of claim 32, wherein:
a third of the plurality of memory instructions is associated with a different one of the group numbers and appears after the memory barrier instruction in the program; and
the processor is not inhibited from executing the third memory instruction before the first memory instruction in response to executing the memory barrier instruction. 
34.  The data processing system of claim 32, wherein:
a fourth of the plurality of memory instructions is associated with a different one of the group numbers and appears before the memory barrier instruction in the program; and
the processor is prompted to execute the first memory instruction before the fourth memory instruction in response to executing the memory barrier instruction. 
1. ABSTRACT
Methods, systems, and articles of manufacture consistent with the present invention provide a memory instruction manager for managing the execution of instructions associated with a program.  The memory instruction manager assigns a first group to a first instruction associated with a program and to a second instruction associated with the program, and provides, after the first instruction, a memory barrier instruction having the first group identifier such that one or more processors with access to the program are inhibited from executing the second memory instruction until the first memory instruction is executed.  
2. REPRESENTATIVE DRAWING
Fig.1
2005332387.tif 000018
2005332387.tif 000019
2005332387.tif 000020
2005332387.tif 000021
2005332387.tif 000022
2005332387.tif 000023
2005332387.tif 000024
2005332387.tif 000025
2005332387.tif 000026