JP3633404B2

JP3633404B2 - Memory allocation optimization system, method, and recording medium

Info

Publication number: JP3633404B2
Application number: JP31413099A
Authority: JP
Inventors: 均村井
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1999-11-04
Filing date: 1999-11-04
Publication date: 2005-03-30
Anticipated expiration: 2019-11-04
Also published as: JP2001134446A

Description

【０００１】
【発明の属する技術分野】
本発明は、分散メモリ型並列計算機におけるメモリ割り付けの最適化方法に関し、特に、再コンパイルによって並列プログラムに対するメモリ割り付けを最適化するメモリ割り付け最適化方法に関する。
【０００２】
【従来の技術】
分散メモリ型並列計算機とは、各々がローカルメモリを持つ複数のプロセッサが、相互結合網（ネットワーク）で結合された構造の計算機システムである。通常、データは、各プロセッサ・エレメント（ＰＥ）のローカルメモリに分散して配置される。
【０００３】
逐次ソースプログラムから分散メモリ型並列計算機向けのオブジェクトプログラムを生成するコンパイラは、ソースプログラムに現れるデータ（配列）を、各ＰＥのローカルメモリ上に分割・配置する。
【０００４】
これを実現する方式として、宣言された配列の領域（グローバル領域）のうち、各ＰＥに分割・配置されたローカルな領域だけをローカルメモリに割り付ける方式がある（本明細書中、当該方式をＳＨＲＵＮＫ方式と呼ぶことにする）。この方式では、ソースプログラムでは、グローバル領域上の添字式でアクセスされるよう記述されるのに対し、オブジェクトプログラムでは、ローカルメモリ領域上の添字式でアクセスする必要がある。従って、当該方式では、実行時にグローバル領域上の添字からローカル領域上の添字への変換処理が必要になる。
【０００５】
また、配列の分割を変更する際には、配列の領域を動的に割り付けたり、元の領域から値をコピーしたりする処理が必要になる。これらの処理は、プログラムの実行時間を増大させる要因となる。
【０００６】
尚、複数のＰＥ間に亘って共有すべきデータがある場合、そのデータは、共有メモリや、データを使用する各ＰＥのローカルメモリ等に配置される。
【０００７】
一方、配列を各プロセッサに配置する際に領域を分割せず、全プロセッサが配列の全体に等しい領域を保持し、そのうちのローカルな部分のみを用いるという方法も考えられる（ここでは、当該方式をＮＯＳＨＲＵＮＫ方式と呼ぶことにする）。この方法は、ＨＰＦ／ＪＡ（ＨｉｇｈＰｅｒｆｏｒｍａｎｃｅＦｏｒｔｒａｎ２．０公式マニュアル，ＨｉｇｈＰｅｒｆｏｒｍａｎｃｅＦｏｒｔｒａｎＦｏｒｕｍ，シュプリンガー・フェアラーク東京（１９９９））では、「フルシャドウ（ＦＵＬＬ−ＳＨＡＤＯＷ）」と呼ばれている。この方法では、必要な添字変換や領域の動的割り付けといった処理は不要であるため、実行時間を削減することができる。しかし、ＳＨＲＵＮＫ方式に比べると、メモリの使用効率が悪く、巨大な配列を扱うプログラムに適用することはできない。
【０００８】
配列に対してメモリ割り付け方法を個別に決めることができる場合、計算機システムのメモリサイズの範囲内でできるだけ多くの配列をＮＯＳＨＲＵＮＫ方式で割り付ける方がよい。しかし、どの配列をＮＯＳＨＲＵＮＫ方式で割り付けるのが最適であるかは、一般には利用可能なメモリサイズに依存し、利用可能なメモリサイズは種々に変化し得るため、最適なメモリ割り付け方法をコンパイル時に決定することはできない。
【０００９】
以下では、並列プログラムを記述するのに、ＨＰＦ／ＪＡの記法を用いる。
【００１０】
【発明が解決しようとする課題】
第１の問題点は、ＳＨＲＵＮＫ方式では、実行時に添字変換や領域の動的割り付けといったオーバヘッドが発生することである。これは、ソースプログラムとオブジェクトプログラムでは配列のメモリ割り付け方法が異なることに起因する。
【００１１】
第２の問題点は、ＮＯＳＨＲＵＮＫ方式では、巨大な配列を扱えないことである。これは、当該方法では、配列全体をローカルメモリに配置しようとすることに起因する。
【００１２】
第３の問題点は、最適なメモリ割り付け方法をコンパイル時に決定することは一般にはできないことである。当該計算機システムの処理内容に応じて、システムの環境が変化すると、それに伴って、利用可能なメモリサイズも変化するからである。
【００１３】
従って、本発明の目的は、プログラムの必要メモリサイズを、現在利用可能なメモリサイズ以下に抑えつつ、以上の問題点を解決するメモリ割り付け最適化方法を提供することである。
【００１４】
【課題を解決するための手段】
本発明の第１の実施態様によれば、プログラムが複数のプロセッサエレメントを備える並列計算機で実行される場合に、当該プログラムが使用する各データの前記プロセッサエレメントのメモリへの割り付けを最適化するメモリ割り付け最適化システムにおいて、前記プロセッサエレメントで現在利用可能なメモリのサイズを取得する実行モニタと、当該プログラムのソースプログラム、前記メモリのサイズ、及び前記各データの重要度に基づいて、各データの最適なメモリ割り付け方法を決定する最適割り付け決定部とを有するメモリ割り付け最適化システムが提供される。
【００１５】
また、本発明の第２の実施態様によれば、プログラムが複数のプロセッサエレメントを備える並列計算機で実行される場合に、当該プログラムが使用する各データの前記プロセッサエレメントのメモリへの割り付けを最適化するメモリ割り付け最適化システムにおいて、前記プロセッサエレメントで現在利用可能なメモリのサイズを取得する実行モニタと、当該プログラムのソースプログラム及び前記取得された前記メモリのサイズに基づいて、前記各データの最適なメモリ割り付け方法を決定する最適割り付け決定部と、前記決定された各データの最適なメモリ割り付け方法に基づいて、前記ソースプログラムを変形し再コンパイルすることにより、オブジェクトプログラムを生成するダイナミックコンパイラと、前記オブジェクトプログラムを、対応する元のオブジェクトプログラムと置換することにより、実行中の実行可能プログラムを変更するダイナミックリンカと、前記各構成要素の動作を制御する実行マネージャとを有するメモリ割り付け最適化システムが提供される。
【００１６】
また更に、本発明の第３の実施態様によれば、プログラムが複数のプロセッサエレメントを備える並列計算機で実行される場合に、当該プログラムが使用する各データの前記プロセッサエレメントのメモリへの割り付けを最適化するメモリ割り付け最適化方法において、前記プロセッサエレメントで現在利用可能なメモリのサイズを取得するステップと、当該プログラムのソースプログラム、前記メモリのサイズ、及び前記各データの重要度に基づいて、各データの最適なメモリ割り付け方法を決定するステップとを有するメモリ割り付け最適化方法が提供される。
【００１７】
また更に、本発明の第４の実施態様によれば、プログラムが複数のプロセッサエレメントを備える並列計算機で実行される場合に、当該プログラムが使用する各データの前記プロセッサエレメントのメモリへの割り付けを最適化するメモリ割り付け最適化方法において、前記プロセッサエレメントで現在利用可能なメモリのサイズを取得するステップと、当該プログラムのソースプログラム及び前記取得された前記メモリのサイズに基づいて、前記各データの最適なメモリ割り付け方法を決定するステップと、前記決定された各データの最適なメモリ割り付け方法に基づいて、前記ソースプログラムを変形し再コンパイルすることにより、オブジェクトプログラムを生成するステップと、前記オブジェクトプログラムを、対応する元のオブジェクトプログラムと置換することにより、実行中の実行可能プログラムを変更するステップとを有するメモリ割り付け最適化方法が提供される。
【００１８】
更に、本発明の第５の実施態様によれば、プログラムが複数のプロセッサエレメントを備える並列計算機で実行される場合に、当該プログラムが使用する各データの前記プロセッサエレメントのメモリへの割り付けを最適化するメモリ割り付け最適化方法を実現させるプログラムを記録したコンピュータ読み取り可能な記録媒体が提供され、前記方法を実現させるプログラムは、前記プロセッサエレメントで現在利用可能なメモリのサイズを取得するステップと、当該プログラムのソースプログラム、前記メモリのサイズ、及び前記各データの重要度に基づいて、各データの最適なメモリ割り付け方法を決定するステップとを有する。
【００１９】
また更に、本発明の第６の実施態様によれば、プログラムが複数のプロセッサエレメントを備える並列計算機で実行される場合に、当該プログラムが使用する各データの前記プロセッサエレメントのメモリへの割り付けを最適化するメモリ割り付け最適化方法を実現させるプログラムを記録したコンピュータ読み取り可能な記録媒体が提供され、前記方法を実現させるプログラムは、前記プロセッサエレメントで現在利用可能なメモリのサイズを取得するステップと、当該プログラムのソースプログラム及び前記取得された前記メモリのサイズに基づいて、前記各データの最適なメモリ割り付け方法を決定するステップと、前記決定された各データの最適なメモリ割り付け方法に基づいて、前記ソースプログラムを変形し再コンパイルすることにより、オブジェクトプログラムを生成するステップと、前記オブジェクトプログラムを、対応する元のオブジェクトプログラムと置換することにより、実行中の実行可能プログラムを変更するステップとを有する。
【００２０】
【発明の実施の形態】
図１を参照して、本発明の第１の実施形態について図面を参照して詳細に説明する。
【００２１】
本発明のメモリ割り付け最適化システム１０は、実行マネージャ１１と、ダイナミックコンパイラ１２と、ダイナミックリンカ１３と、実行モニタ１４とを含む。
【００２２】
実行マネージャ１１は、最適割り付け決定部１９を備えている。
【００２３】
実行マネージャ１１は、ダイナミックコンパイラ１２、ダイナミックリンカ１３、実行モニタ１４の制御を行う。
【００２４】
ダイナミックコンパイラ１２は、実行マネージャ１１より最適割り付け方法Ｉｎｓ−ｏｐｔを受け取って、ソースプログラム１５を再コンパイルし、最適なメモリ割り付けを実現するオブジェクトプログラム１６を生成する。ダイナミックコンパイラ１２は、任意の配列がＳＨＲＵＮＫ方式またはＮＯＳＨＲＵＮＫ方式で割り付けられるようにソースプログラム１５をコンパイルできる。
【００２５】
ダイナミックリンカ１３は、実行可能プログラム１７に含まれる手続きのうちダイナミックコンパイラ１２の再コンパイル対象になったものを、新しいオブジェクトプログラム１６で置換した後、リンクを行い、新しい実行可能プログラムを生成する。
【００２６】
実行モニタ１４は、実行可能プログラム１７や計算機システム１８のオペレーティングシステムまたはハードウェアより、現在のメモリ割り付け方法Ｉｎｓ−ｃｕｒｒｅｎｔ、現在利用可能なメモリのサイズＭａｌｌを受け取り、実行マネージャ１１に伝達する。
【００２７】
ここで、メモリ割り付け方法Ｉｎｓとは、ＮＯＳＨＲＵＮＫ方式で割り付けられる配列の集合である。また、利用可能なメモリとは、ある１つのＰＥが有するローカルメモリであって、実行可能プログラム１７に関するスカラデータや種々の実行時データが割り付けられているメモリ、あるいは計算機システム１８上で動作する他の実行可能プログラムが使用中のメモリなどを除いたものである。
【００２８】
最適割り付け決定部１９は、実行モニタ１４より受け取った実行時情報とソースプログラム１５から得られる情報を元に、計算機システム１８における、ソースプログラム１５に対する最適なメモリ割り付け方法を決定する。決定された方法は、ダイナミックコンパイラ１２に伝達される。
【００２９】
ここで、最適なメモリ割り付け方法Ｉｎｓ−ｏｐｔの決定方法について説明する。
【００３０】
プログラム中で使われる配列Ａ１，Ａ２，…，Ａｎを、ＳＨＲＵＮＫ方式およびＮＯＳＨＲＵＮＫ方式で割り付ける場合に必要となるメモリサイズをそれぞれ、ｍ１，ｍ２，…，ｍｎおよびＭ１，Ｍ２，…，Ｍｎとする。また、配列の重みをｗ１，ｗ２，…，ｗｎとする。ここで、ｗｉは、一定時間内に配列Ａｉがアクセスされた回数（アクセス頻度）とする。ｗｉの値の設定に関しては、例えば、動的割り付けが生じる回数など他の基準も考えられるが、本発明の実施の形態はｗｉの値として何が設定されるかにはよらない。
【００３１】
このとき、最適割り付けを決定する問題は、次の式１、及び式２を用いて記述される。
【００３２】
（以下で、Ｉ≡｛１，２，…，ｎ｝とする）。
【００３３】
【数１】

の元で、
【数２】

を最大にするようなＩｎｓ（⊆ Ｉ）を求める。ここで、式１の左辺の第１項は、ある１つのＰＥにおいて、実際にＳＨＲＵＮＫ方式で割り当てられる配列のメモリサイズの合計であり、第２項は、当該ＰＥにおいて、実際にＮＯＳＨＲＵＮＫ方式で割り当てられる配列のメモリサイズの合計を示す。式１は、実際に割り当てられるメモリサイズの合計が、１つのＰＥの使用可能ローカルメモリの合計サイズを越えないことを示している。
【００３４】
このような条件は、一般には、当該計算機システム内のＰＥ全てを考慮して設定すべきであるが、ここでは、問題を単純化するため、ある１つのＰＥについて考える。このとき、他のＰＥでも前記１つのＰＥと同一の動作（即ち、同一のメモリ割り当て）が行われていると仮定する。
【００３５】
ここで、
Ｍ’ｉ ≡ Ｍｉ − ｍｉ．．．．（式３）
とすると、この問題は次の式４、及び式５を用いて書き換えられる。但し、上記式３におけるＭｉとｍｉはそれぞれ、配列ＡｉをＮＯＳＨＲＵＮＫ方式で割り当てるとした場合のメモリサイズ、配列ＡｉをＳＨＲＵＮＫ方式で割り当てるとした場合のメモリサイズを示しており、これらが実際に同時に割り当てられる訳ではない。式１に示すように、ある配列Ａｉのローカルメモリへの割り当てに関しては、ＮＯＳＨＲＵＮＫ方式かＳＨＲＵＮＫ方式のどちらかが用いられる。
【００３６】
【数３】

の元で、
【数４】

を最大にするようなＩｎｓ（⊆ Ｉ）を求める。
【００３７】
これは、いわゆるナップザック問題として把握することが可能である。ナップザック問題はＮＰ問題であることが知られており、配列の数ｎに対して多項式時間内で解くことはできない。しかし、多項式時間内で近似解を得る方法は多く知られており（Ｓａｈｎｉ，ＳａｒｔａｊＫ．， ”Ａｐｐｒｏｘｉｍａｔｅａｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅ０／１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍ， ”ＪｏｕｒｎａｌｏｆｔｈｅＡＣＭ，ｖｏｌ．２２，ｎｏ．１，ｐｐ．１１５−１２４，Ｊａｎｕａｒｙ，１９７５を参照されたい）、最適割り付け決定部１９は、そのうちの任意の１つの方法でＩｎｓ−ｏｐｔの近似解を求めることができる。
【００３８】
次に、図１および図２を参照して本実施の形態の動作について詳細に説明する。
【００３９】
実行モニタ１４は、実行可能プログラム１７や計算機システム１８のオペレーティングシステムまたはハードウェアより、現在のメモリ割り付け方法Ｉｎｓ−ｃｕｒｒｅｎｔ、現在利用可能なメモリサイズＭａｌｌを受け取り、実行マネージャ１１に伝達する（図２のステップ２１）。
【００４０】
最適割り付け決定部１９は、現在利用可能なメモリサイズＭａｌｌおよびソースプログラムの配列出現情報から、最適なメモリ割り付け方法Ｉｎｓ−ｏｐｔを求める（ステップ２２）。
【００４１】
実行マネージャ１１は、実行モニタ１４より得たＩｎｓ−ｃｕｒｒｅｎｔがＩｎｓ−ｏｐｔと等しいか否かを判定する（ステップ２３）。
【００４２】
Ｉｎｓ−ｃｕｒｒｅｎｔがＩｎｓ−ｏｐｔと異なる場合、実行マネージャ１１は、ダイナミックコンパイラ１２を起動し、Ｉｎｓ−ｏｐｔを伝達する。
【００４３】
ダイナミックコンパイラ１２は、配列Ａｉ（ｉはＩｎｓ−ｏｐｔに含まれる）がＮＯＳＨＲＵＮＫ方式で、配列Ａｊ（ｊはＩｎｓ−ｏｐｔに含まれない）がＳＨＲＵＮＫ方式でそれぞれ割り付けられるようにソースプログラム１５をコンパイルし、新しいオブジェクトプログラム１６を生成する（ステップ２４）。
【００４４】
本実施形態は、プログラムの実行の間に、対象の手続きが複数回実行される場合に大きな効果がある。従って、例えば、図３のプログラムのように、ループ中から呼ばれて複数回実行される手続きを対象とすることが好ましい。
【００４５】
ここで、メインプログラムは、ダイナミックコンパイラ１２の再コンパイル処理の対象にはできない。このような制限が存在するのは、ダイナミックコンパイラ１２における再コンパイルが、メインプログラム内の手続き呼び出しを対象として行われるためである。
【００４６】
また、メモリ割り付け最適化の対象となるのは、ダイナミックコンパイラ１２の再コンパイル処理の対象手続き内でのみ割り付けが行われる配列である。
【００４７】
ダイナミックリンカ１３は、まず実行可能プログラム１７の動作を一時的に中断させる。次に、実行可能プログラム１７に含まれる手続きのうちダイナミックコンパイラの再コンパイル対象になったものを、新しいオブジェクトプログラム１６で置換する。次に、それらのオブジェクトプログラムをリンクして新しい実行可能プログラムを生成し、実行可能プログラムの動作を再開させる（ステップ２５）。
【００４８】
ステップ２３において、Ｉｎｓ−ｃｕｒｒｅｎｔがＩｎｓ−ｏｐｔと等しい場合、本発明の実施の形態は何もせずに処理を終了する。
【００４９】
次に、具体的な実施例を用いて本実施の形態の動作を説明する。
【００５０】
配列Ａ１ないしＡ８の現れる、図３のようなプログラムを考える。この場合の、ｍｉ，Ｍｉ，Ｍ’ｉ，ｗｉのそれぞれの値が、図４の表に示されている。
【００５１】
ここで、Ａ１はメインプログラムで割り付けられるので、上述の通り、本実施形態における最適化の対象にはならない。
【００５２】
また、Ｍａｌｌ＝１０００であるとする。
【００５３】
図４を参照すると、全ての配列がＳＨＲＵＮＫ方式で割り付けられた場合には、
Ｍ’ａｌｌ＝Ｍａｌｌ − Σ ｍｉ＝１０００ − １６０＝８４０
となる。
【００５４】
ここで、全ての配列がＳＨＲＵＮＫ方式で割り付けられるようにコンパイルされた実行可能プログラムが、計算機システム上で動作しているものとする。このとき、
Ｍｃｕｒｒｅｎｔ＝１６０
Ｉｎｓ−ｃｕｒｒｅｎｔ＝｛｝
である。
【００５５】
ステップ２１において、実行モニタは、計算機システムおよび実行可能プログラムから、上記のＭａｌｌ，Ｍｃｕｒｒｅｎｔ，Ｉｎｓ−ｃｕｒｒｅｎｔを得て、実行マネージャへ伝達する。
【００５６】
ステップ２２において、実行マネージャは最適割り付け決定部を起動する。
【００５７】
最適割り付け決定部は、実行マネージャより伝達されたＭａｌｌとソースプログラムから抽出した配列情報から、最適割り付け方法Ｉｎｓ−ｏｐｔを計算する。
【００５８】
ここでは、ｗｉの値の大きい配列から順にＩｎｓ−ｏｐｔに加えていく「ｇｒｅｅｄｙアルゴリズム」を用いる。その結果、
Ｉｎｓ−ｏｐｔ＝｛３，６，７，８｝
が得られる。
【００５９】
ステップ２３において、Ｉｎｓ−ｃｕｒｒｅｎｔとＩｎｓ−ｏｐｔは異なるので、ステップ２４に移る。
【００６０】
ステップ２４において、実行マネージャはダイナミックコンパイラを起動する。ダイナミックコンパイラは、Ｉｎｓ−ｏｐｔに含まれる配列Ａ３，Ａ６，Ａ７，Ａ８がＮＯＳＨＲＵＮＫ方式で、その他の配列がＳＨＲＵＮＫ方式で割り付けられるようにソースプログラムを再コンパイルし、新しいオブジェクトプログラムを生成する。
【００６１】
ステップ２５において、ダイナミックリンカは、新しいオブジェクトプログラムと、実行可能プログラムに含まれるオブジェクトプログラムを置換する。
【００６２】
その結果、
Ｍｃｕｒｒｅｎｔ＝９１６ ≦ Ｍａｌｌ
となり、Ｍａｌｌの範囲内で、４つの配列Ａ３，Ａ６，Ａ７，Ａ８をＮＯＳＨＲＵＮＫ方式で割り付けることができる。
【００６３】
次に、本発明の第２の実施形態の動作について説明する。
【００６４】
上述した第１の実施形態においては、実行モニタ１４及び実行マネージャ１１は、任意のタイミングで１度だけ実行され得る。これに対し、第２の実施形態では、所定のタイミングで実行マネージャを起動することにより、第１の実施形態で行われた処理を繰り返し行う。実行マネージャを起動するタイミングとしては、例えば、計算機システム上で動作する他の実行可能プログラムが終了した時点や配列の分割・配置方法が変更された時点などが考えられる。
【００６５】
本実施形態では、プログラムの実行中に計算機システムの状態が変化した場合であっても、それに応じてメモリ割り付け方法を動的に変化させることができる。
【００６６】
次に、本発明の第３の実施形態の動作について説明する。
【００６７】
第１の実施形態では、メインプログラムを再コンパイルの対象にできなかった。即ち、メインプログラムで割り付けが行われる配列に対しては割り付け方法を最適化できなかった。そこで、本発明の第３の実施形態では、ダイナミックコンパイラ１２がダミーのメインプログラムを生成し、本来のメインプログラムはこのダミーのメインプログラムから呼び出されるようにソースプログラムを変形する。この際に、本来の再コンパイル対象である手続き呼び出しを囲むループにストリップマイニングを適用し、その外側ループはダミーのメインプログラムに置く。また、本来のメインプログラム内で宣言される変数は共通ブロック実体とする。その後、本来のメインプログラムであった手続きを再コンパイルの対象として、第１の実施形態を適用する。
【００６８】
図３のソースプログラムに本実施形態を適用すると、ダイナミックコンパイラ１２は、図５のプログラムを生成する。この場合のｍｉ，Ｍｉ，Ｍ’ｉ，ｗｉのそれぞれの値は、図６の表に示すようなものである。
【００６９】
また、Ｍａｌｌ＝１０００とする。
【００７０】
従って、図６の表から、Ｍ’ａｌｌ＝Ｍａｌｌ − Σ ｍｉ＝１０００ − ２００＝８００が得られる。
【００７１】
ここで、第１の実施形態を適用すれば、
Ｉｎｓ−ｏｐｔ＝｛１，３，８｝
が得られる。
【００７２】
本実施形態では、上述のように、メインプログラムも再コンパイルの対象にすることができるため、メインプログラムで割り付けが行われる配列に対しても本発明を適用できる。
【００７３】
次に、本発明の第４の実施形態について詳細に説明する。
【００７４】
前述の通り、第１の実施形態では、再コンパイル対象の各手続きに対して個別に最適割り付け方法を決定する。従って、ある手続き呼び出しに関して、実引数と仮引数で異なる割り付け方法が選択される可能性があり、その場合、実行時に割り付け方法を変換するオーバヘッドが生じる。
【００７５】
例えば、
ＣＡＬＬＳＵＢ１（Ａ１，Ａ２）
ＣＡＬＬＳＵＢ２（Ａ２，Ａ３）
というコードが、再コンパイルされるプログラムのソースコードに記述されている場合、本発明の第１の実施形態では、手続き単位に、各配列に対してＳＨＲＵＮＫ方式かＮＯＳＨＲＵＮＫ方式が決定されるため、上記ＳＵＢ１の引数に示された配列Ａ２が、ＳＨＲＵＮＫ方式と決定され、上記ＳＵＢ２の引数に示された配列Ａ２がＮＯＳＨＲＵＮＫ方式と決定される場合がある。実際には、１つの方法で配列Ａ２が配置されるため、当初決定された方式で配置されなかったことになる手続き、ＳＵＢ１、ＳＵＢ２のどちらかは、配列Ａ２をアクセスする際に、その異なる方式用に、アドレス等の変換を行う必要が生じる。
【００７６】
そこで、第４の実施形態では、最適割り付け決定部は、手続き呼び出しの実引数と仮引数の割り付け方法をできるだけ一致させるように各配列の割り付け方法を決定する。具体的には、決定された１つの配列の割り付け方式が、手続き間で異なっている場合に、当該割り付け方法を、ローカルメモリの合計を越えないという条件の下で、どちらかの方法に統一し、その統一された方法に基づいてオブジェクトプログラムを生成（又は再生成）する。
【００７７】
本実施形態により、割り付け方法を変換するための実行時オーバヘッドを削減することができる。
【００７８】
次に、図７を参照して、本発明の各実施形態が実行される分散メモリ型並列計算機システムの一構成例について説明する。尚、図１に示した構成要素と同一の要素については、同一の符号が付されている。
【００７９】
当該計算機システム１８は、ｎ個のプロセッサエレメントＰＥ１ないしＰＥｎ（３１_１〜３１_ｎ）を有している。ＰＥの数は、例えば４、８、１６といった数である。これら複数のＰＥは、ネットワーク３２によって相互に接続されている。また、各ＰＥは、それぞれ、ローカルメモリ及びプロセッサを有している。各プロセッサは、対応するローカルメモリ（又は共有メモリ）にロードされたプログラムに従って、ローカルメモリ内のデータその他に対して並列処理を実行する。
【００８０】
本発明によるメモリ割り付け最適化システム１０は、ネットワーク３２に接続され、そのネットワークを介して、各ＰＥに動的に再コンパイルされたプログラムを送信し、データの割り付けの変更等を指示する。また、メモリ割り付け最適化システム１０内の実行モニタ１４は、当該ネットワーク３２を介して、各ＰＥのローカルメモリの空き容量の状況等を取得する。
【００８１】
この例では、メモリ割り付け最適化システム１０は、ＰＥとは異なる、例えばホストマシン内で実行されるものとして示されているが、１つのＰＥを使用して当該システム１０を実現することも可能である。
【００８２】
記録媒体３３は、ソースプログラム１５や、メモリ割り付け最適化方法を実現するためのプログラム自体を含み、必要に応じてメモリ割り付け最適化システム１０で読み取られる。こうした記録媒体３３の代表的な例は、フロッピーディスクやＣＤ−ＲＯＭである。
【００８３】
【発明の効果】
以上に説明したように、本発明では、以下の効果を得ることが出きる。
【００８４】
第１の効果は、頻繁にアクセスされる配列を、重要度に応じて、できるだけオーバヘッドの小さいＮＯＳＨＲＵＮＫ方式で割り付けることにより、添字変換や動的割り付けといったオーバヘッドを削減できることである。
【００８５】
第２の効果は、必要メモリの小さいＳＨＲＵＮＫ方式で割り付けることにより、巨大な配列を扱えることである。
【００８６】
第３の効果は、実行時に、計算機システムの現在の状態に応じて最適なメモリ割り付け方式を決定し、それに従って生成されたオブジェクトプログラムで、実行中の実行可能プログラムの一部を（実行を停止することなく）置換するため、計算機システムの状態に応じて、常に最適なメモリ割り付け方式を達成できることである。
【図面の簡単な説明】
【図１】本発明の第１、第２、第３および第４の実施形態の構成を示すブロック図である。
【図２】本発明の第１の実施形態の動作を示す流れ図である。
【図３】本発明の第１の実施形態において入力されるソースプログラムのコードの一部を示す図である。
【図４】各配列毎に、ＳＨＲＵＮＫ方式、ＮＯＳＨＲＵＮＫ方式によるメモリ割り当てサイズ等を示す表である。
【図５】本発明の第３の実施形態において入力されるソースプログラムのコードの一部を示す図である。
【図６】各配列毎に、ＳＨＲＵＮＫ方式、ＮＯＳＨＲＵＮＫ方式によるメモリ割り当てサイズ等を示す表である。
【図７】本発明が実行される分散メモリ並列処理計算機システムの一構成例を示すブロック図である。
【符号の説明】
１０メモリ割り付け最適化システム
１１実行マネージャ
１２ダイナミックコンパイラ
１３ダイナミックリンカ
１４実行モニタ
１５ソースプログラム
１６オブジェクトプログラム
１７実行可能プログラム
１８計算機システム
１９最適割り付け決定部
３１_１〜３１_ｎプロセッサエレメント（ＰＥ）
３２ネットワーク
３３記録媒体[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a memory allocation optimization method in a distributed memory parallel computer, and more particularly to a memory allocation optimization method for optimizing memory allocation for a parallel program by recompilation.
[0002]
[Prior art]
The distributed memory type parallel computer is a computer system having a structure in which a plurality of processors each having a local memory are connected by an interconnection network. Usually, data is distributed and arranged in the local memory of each processor element (PE).
[0003]
A compiler that generates an object program for a distributed memory parallel computer from a sequential source program divides and arranges data (array) appearing in the source program on the local memory of each PE.
[0004]
As a method for realizing this, there is a method of allocating only a local region divided and arranged in each PE in a declared array region (global region) to a local memory (this method is referred to as SHRUNK in this specification). I will call it a method). In this method, the source program is described to be accessed with a subscript expression on the global area, whereas the object program needs to be accessed with a subscript expression on the local memory area. Therefore, this method requires conversion processing from the subscript on the global area to the subscript on the local area at the time of execution.
[0005]
Further, when changing the division of the array, it is necessary to dynamically allocate the area of the array or copy the value from the original area. These processes increase the program execution time.
[0006]
When there is data to be shared among a plurality of PEs, the data is placed in a shared memory, a local memory of each PE that uses the data, or the like.
[0007]
On the other hand, there is also a method in which the area is not divided when arranging the array in each processor, and all the processors hold an area equal to the entire array, and only a local part of the area is used (here, this method is used). This will be referred to as the NOSHRUNK system). This method is called “FULL SHADOW” in HPF / JA (High Performance Fortran 2.0 Official Manual, High Performance Fortran Forum, Springer Fairlake Tokyo (1999)). This method does not require processing such as necessary subscript conversion or dynamic region allocation, and can therefore reduce execution time. However, compared to the SHRUNK method, the memory use efficiency is poor and cannot be applied to a program that handles a huge array.
[0008]
When the memory allocation method can be individually determined for the array, it is better to allocate as many arrays as possible within the range of the memory size of the computer system using the NOSHRUNK method. However, which array is best allocated using the NOSHRUNK method generally depends on the available memory size, and the available memory size can vary, so the optimal memory allocation method is determined at compile time. I can't do it.
[0009]
In the following, the HPF / JA notation is used to describe a parallel program.
[0010]
[Problems to be solved by the invention]
The first problem is that in the SHRUNK method, overhead such as subscript conversion and dynamic allocation of areas occurs at the time of execution. This is because the array memory allocation method differs between the source program and the object program.
[0011]
The second problem is that the NOSHRUNK method cannot handle a huge array. This is due to the fact that the method attempts to place the entire array in local memory.
[0012]
The third problem is that an optimum memory allocation method cannot generally be determined at compile time. This is because when the system environment changes according to the processing contents of the computer system, the available memory size changes accordingly.
[0013]
Accordingly, an object of the present invention is to provide a memory allocation optimizing method that solves the above-mentioned problems while suppressing the required memory size of a program below a currently available memory size.
[0014]
[Means for Solving the Problems]
According to the first embodiment of the present invention, when a program is executed by a parallel computer including a plurality of processor elements, the memory for optimizing the allocation of each data used by the program to the memory of the processor elements In the allocation optimization system, the optimum of each data is determined based on the execution monitor that obtains the size of the memory currently available in the processor element, the source program of the program, the size of the memory, and the importance of each data. There is provided a memory allocation optimization system having an optimal allocation determination unit for determining a proper memory allocation method.
[0015]
Further, according to the second embodiment of the present invention, when a program is executed by a parallel computer having a plurality of processor elements, the allocation of each data used by the program to the memory of the processor elements is optimized. In the memory allocation optimizing system, an optimum monitor for each data is obtained based on an execution monitor that acquires a size of a memory that is currently available in the processor element, a source program of the program, and the acquired size of the memory. An optimal allocation determination unit that determines a memory allocation method, a dynamic compiler that generates an object program by transforming and recompiling the source program based on the optimal memory allocation method of each determined data; and Object program A memory allocation optimization system is provided that includes a dynamic linker that changes an executable program that is being executed by replacing a corresponding original object program with a corresponding original object program, and an execution manager that controls the operation of each component. The
[0016]
Still further, according to the third embodiment of the present invention, when the program is executed on a parallel computer having a plurality of processor elements, the allocation of each data used by the program to the memory of the processor elements is optimized. In the memory allocation optimizing method, each data is obtained based on the step of obtaining the size of the memory currently available in the processor element, the source program of the program, the size of the memory, and the importance of each data. Determining an optimal memory allocation method. A memory allocation optimization method is provided.
[0017]
Still further, according to the fourth embodiment of the present invention, when a program is executed by a parallel computer having a plurality of processor elements, the allocation of each data used by the program to the memory of the processor elements is optimized. In the memory allocation optimizing method, the optimum size of each data is obtained based on the step of obtaining the size of the memory currently available in the processor element, and the source program of the program and the obtained size of the memory. A step of determining a memory allocation method, a step of generating an object program by transforming and recompiling the source program based on the determined optimal memory allocation method of each data, and the object program, The corresponding original object By replacing the transfected program, memory allocation optimization method and a step of changing the executable program being executed is provided.
[0018]
Furthermore, according to the fifth embodiment of the present invention, when a program is executed by a parallel computer having a plurality of processor elements, the allocation of each data used by the program to the memory of the processor elements is optimized. There is provided a computer-readable recording medium recording a program for realizing a memory allocation optimization method, and the program for realizing the method includes obtaining a size of a memory currently available in the processor element, and the program Determining an optimal memory allocation method for each data based on the source program, the size of the memory, and the importance of each data.
[0019]
Still further, according to the sixth embodiment of the present invention, when a program is executed by a parallel computer having a plurality of processor elements, the allocation of each data used by the program to the memory of the processor elements is optimized. There is provided a computer-readable recording medium storing a program for realizing a memory allocation optimization method to be realized, and the program for realizing the method includes obtaining a size of a memory currently available in the processor element; Determining an optimal memory allocation method for each piece of data based on a source program of the program and the obtained size of the memory; and, based on the determined optimal memory allocation method for each piece of data, the source Transform and recompile the program By having the step of generating the object program, the object program, by substituting the corresponding original object program, and changing the executable programs.
[0020]
DETAILED DESCRIPTION OF THE INVENTION
With reference to FIG. 1, a first embodiment of the present invention will be described in detail with reference to the drawings.
[0021]
The memory allocation optimization system 10 of the present invention includes an execution manager 11, a dynamic compiler 12, a dynamic linker 13, and an execution monitor 14.
[0022]
The execution manager 11 includes an optimal allocation determination unit 19.
[0023]
The execution manager 11 controls the dynamic compiler 12, the dynamic linker 13, and the execution monitor 14.
[0024]
The dynamic compiler 12 receives the optimal allocation method Ins-opt from the execution manager 11, recompiles the source program 15, and generates an object program 16 that realizes optimal memory allocation. The dynamic compiler 12 can compile the source program 15 so that an arbitrary array is allocated by the SHRUNK method or the NOSHRUNK method.
[0025]
The dynamic linker 13 replaces the procedure included in the executable program 17 that has been recompiled by the dynamic compiler 12 with the new object program 16, and then links to generate a new executable program.
[0026]
The execution monitor 14 receives the current memory allocation method Ins-current and the currently available memory size Mall from the executable program 17 and the operating system or hardware of the computer system 18 and transmits them to the execution manager 11.
[0027]
Here, the memory allocation method Ins is a set of arrays allocated by the NOSHRUNK method. Further, the usable memory is a local memory included in one PE, a memory to which scalar data related to the executable program 17 and various kinds of runtime data are allocated, or other operating on the computer system 18. Excluding the memory in use by the executable program.
[0028]
The optimal allocation determination unit 19 determines an optimal memory allocation method for the source program 15 in the computer system 18 based on the runtime information received from the execution monitor 14 and the information obtained from the source program 15. The determined method is transmitted to the dynamic compiler 12.
[0029]
Here, a method for determining the optimal memory allocation method Ins-opt will be described.
[0030]
The memory sizes required for allocating the arrays A1, A2,..., An used in the program by the SHRUNK method and the NOSHRUNK method are m1, m2,. Also, the array weights are w1, w2,. Here, wi is the number of times the array Ai is accessed within a certain time (access frequency). Regarding the setting of the value of wi, other criteria such as the number of times dynamic allocation occurs can be considered, but the embodiment of the present invention does not depend on what is set as the value of wi.
[0031]
At this time, the problem of determining the optimal allocation is described using the following

equations

1 and 2.
[0032]
(Hereafter, I≡ {1, 2,..., N}).
[0033]
[Expression 1]

Under
[Expression 2]

Find Ins (⊆ I) that maximizes. Here, the first term on the left side of Equation 1 is the total memory size of the array that is actually allocated by the SHRUNK method in a certain PE, and the second term is actually allocated by the NOSHRUNK method in the PE. Indicates the total memory size of the resulting array. Equation 1 shows that the total memory size that is actually allocated does not exceed the total available local memory size of one PE.
[0034]
In general, such a condition should be set in consideration of all PEs in the computer system. Here, in order to simplify the problem, a single PE is considered. At this time, it is assumed that the same operation (that is, the same memory allocation) as that of the one PE is performed in other PEs.
[0035]
here,
M'i ≡ Mi-mi. . . . (Formula 3)
Then, this problem can be rewritten using the following equations 4 and 5. However, Mi and mi in Equation 3 above indicate the memory size when the array Ai is assigned by the NOSHRUNK method, and the memory size when the array Ai is assigned by the SHRUNK method. It is not necessarily done. As shown in Expression 1, for allocation of a certain array Ai to a local memory, either the NOSHRUNK system or the SHRUNK system is used.
[0036]
[Equation 3]

Under
[Expression 4]

Find Ins (⊆ I) that maximizes.
[0037]
This can be grasped as a so-called knapsack problem. The knapsack problem is known to be an NP problem and cannot be solved in polynomial time for the number n of arrays. However, there are many known methods for obtaining an approximate solution in polynomial time (Sahni, Sartaj K., “Approximate algorithms for the 0/1 knacksack problem,” Journal of the ACM, vol. 22, vol. 22). 115-124, January, 1975), the optimal allocation determination unit 19 can obtain an approximate solution of Ins-opt by any one of them.
[0038]
Next, the operation of the present embodiment will be described in detail with reference to FIG. 1 and FIG.
[0039]
The execution monitor 14 receives the current memory allocation method Ins-current and the currently available memory size Mall from the executable program 17 and the operating system or hardware of the computer system 18 and transmits them to the execution manager 11 (FIG. 2). Step 21).
[0040]
The optimal allocation determination unit 19 obtains an optimal memory allocation method Ins-opt from the currently available memory size Mall and the source program array appearance information (step 22).
[0041]
The execution manager 11 determines whether or not the Ins-current obtained from the execution monitor 14 is equal to Ins-opt (step 23).
[0042]
When the Ins-current is different from the Ins-opt, the execution manager 11 activates the dynamic compiler 12 and transmits the Ins-opt.
[0043]
The dynamic compiler 12 compiles the source program 15 so that the array Ai (i is included in the Ins-opt) is allocated by the NOSHRUNK method and the array Aj (j is not included in the Ins-opt) is allocated by the SHRUNK method. A new object program 16 is generated (step 24).
[0044]
This embodiment has a great effect when the target procedure is executed a plurality of times during the execution of the program. Therefore, for example, it is preferable to target a procedure that is called from a loop and executed a plurality of times, such as the program of FIG.
[0045]
Here, the main program cannot be a target of recompilation processing of the dynamic compiler 12. Such a limitation exists because recompilation in the dynamic compiler 12 is performed for a procedure call in the main program.
[0046]
In addition, the target of the memory allocation optimization is an array that is allocated only within the target procedure of the recompile process of the dynamic compiler 12.
[0047]
The dynamic linker 13 first temporarily suspends the operation of the executable program 17. Next, of the procedures included in the executable program 17, those that have been recompiled by the dynamic compiler are replaced with the new object program 16. Next, these object programs are linked to generate a new executable program, and the operation of the executable program is resumed (step 25).
[0048]
In step 23, when Ins-current is equal to Ins-opt, the embodiment of the present invention does nothing and ends the processing.
[0049]
Next, the operation of this embodiment will be described using specific examples.
[0050]
Consider a program as shown in FIG. 3 in which arrays A1 to A8 appear. The values of mi, Mi, M′i, and wi in this case are shown in the table of FIG.
[0051]
Here, since A1 is allocated by the main program, as described above, it is not an optimization target in the present embodiment.
[0052]
Assume that Mall = 1000.
[0053]
Referring to FIG. 4, when all the arrays are allocated in the SHRUNK method,
M'all = Mall-Σmi = 1000-160 = 840
It becomes.
[0054]
Here, it is assumed that an executable program compiled so that all the arrays are allocated by the SHRUNK method is operating on the computer system. At this time,
McCurrent = 160
Ins-current = {}
It is.
[0055]
In step 21, the execution monitor obtains the above-mentioned Mall, Current, Ins-current from the computer system and the executable program, and transmits them to the execution manager.
[0056]
In step 22, the execution manager activates the optimum allocation determination unit.
[0057]
The optimal allocation determination unit calculates the optimal allocation method Ins-opt from the Mall transmitted from the execution manager and the sequence information extracted from the source program.
[0058]
Here, a “greedy algorithm” that is added to Ins-opt in order from the array with the largest value of wi is used. as a result,
Ins-opt = {3, 6, 7, 8}
Is obtained.
[0059]
In step 23, since Ins-current and Ins-opt are different, the process proceeds to step 24.
[0060]
In step 24, the execution manager invokes the dynamic compiler. The dynamic compiler recompiles the source program so that the arrays A3, A6, A7, and A8 included in Ins-opt are allocated by the NOSHRUNK method and the other arrays are allocated by the SHRUNK method, thereby generating a new object program.
[0061]
In step 25, the dynamic linker replaces the new object program with the object program included in the executable program.
[0062]
as a result,
McCurrent = 916 ≤ Mall
Thus, within the range of Mall, the four arrays A3, A6, A7, and A8 can be assigned by the NOSHRUNK method.
[0063]
Next, the operation of the second exemplary embodiment of the present invention will be described.
[0064]
In the first embodiment described above, the execution monitor 14 and the execution manager 11 can be executed only once at an arbitrary timing. On the other hand, in the second embodiment, the execution manager is activated at a predetermined timing, thereby repeatedly performing the processing performed in the first embodiment. Possible timings for starting the execution manager include, for example, the time when another executable program operating on the computer system is terminated, or the time when the array division / arrangement method is changed.
[0065]
In this embodiment, even if the state of the computer system changes during execution of the program, the memory allocation method can be changed dynamically accordingly.
[0066]
Next, the operation of the third embodiment of the present invention will be described.
[0067]
In the first embodiment, the main program cannot be recompiled. In other words, the allocation method could not be optimized for an array that is allocated by the main program. Therefore, in the third embodiment of the present invention, the dynamic compiler 12 generates a dummy main program, and the original main program is modified so that the original main program is called from the dummy main program. At this time, strip mining is applied to the loop surrounding the procedure call to be originally recompiled, and the outer loop is placed in a dummy main program. Variables declared in the original main program are common block entities. Thereafter, the first embodiment is applied with the procedure that was the original main program as the target of recompilation.
[0068]
When this embodiment is applied to the source program of FIG. 3, the dynamic compiler 12 generates the program of FIG. The values of mi, Mi, M′i, and wi in this case are as shown in the table of FIG.
[0069]
Also, Mall = 1000.
[0070]
Therefore, M′all = Mall−Σmi = 1000−200 = 800 is obtained from the table of FIG.
[0071]
Here, if the first embodiment is applied,
Ins-opt = {1, 3, 8}
Is obtained.
[0072]
In the present embodiment, as described above, the main program can also be a target of recompilation. Therefore, the present invention can also be applied to an array that is allocated by the main program.
[0073]
Next, a fourth embodiment of the present invention will be described in detail.
[0074]
As described above, in the first embodiment, the optimum allocation method is determined individually for each procedure to be recompiled. Therefore, with respect to a certain procedure call, different allocation methods may be selected for the actual argument and the dummy argument. In this case, an overhead for converting the allocation method occurs at the time of execution.
[0075]
For example,
CALL SUB1 (A1, A2)
CALL SUB2 (A2, A3)
Is described in the source code of the recompiled program, in the first embodiment of the present invention, the SHRUNK method or the NOSHRUNK method is determined for each array for each procedure. The array A2 indicated in the argument of SUB1 may be determined as the SHRUNK method, and the array A2 indicated in the argument of SUB2 may be determined as the NOSHRUNK method. Actually, since the array A2 is arranged by one method, one of the procedures SUB1 and SUB2 that has not been arranged by the originally determined method is different from the method used when accessing the array A2. Therefore, it is necessary to convert an address or the like.
[0076]
Therefore, in the fourth embodiment, the optimum allocation determining unit determines the allocation method of each array so that the allocation method of the actual argument and the dummy argument of the procedure call is matched as much as possible. Specifically, if the allocation method of one determined array differs between procedures, the allocation method is unified to either method under the condition that the total of local memory is not exceeded. The object program is generated (or regenerated) based on the unified method.
[0077]
According to the present embodiment, it is possible to reduce the runtime overhead for converting the allocation method.
[0078]
Next, a configuration example of a distributed memory type parallel computer system in which each embodiment of the present invention is executed will be described with reference to FIG. In addition, the same code | symbol is attached | subjected about the element same as the component shown in FIG.
[0079]
The computer system 18 includes n processor elements PE1 to PEn (31 ₁ ~ 31 _n )have. The number of PEs is a number such as 4, 8, or 16, for example. The plurality of PEs are connected to each other by a network 32. Each PE has a local memory and a processor. Each processor executes parallel processing on data and the like in the local memory according to a program loaded in the corresponding local memory (or shared memory).
[0080]
The memory allocation optimization system 10 according to the present invention is connected to a network 32 and transmits a dynamically recompiled program to each PE via the network, and instructs a change in data allocation or the like. In addition, the execution monitor 14 in the memory allocation optimization system 10 acquires the status of the free capacity of the local memory of each PE via the network 32.
[0081]
In this example, the memory allocation optimization system 10 is shown as being different from a PE, for example, executed in a host machine. However, the system 10 can be realized by using one PE. is there.
[0082]
The recording medium 33 includes the source program 15 and the program itself for realizing the memory allocation optimization method, and is read by the memory allocation optimization system 10 as necessary. Typical examples of such a recording medium 33 are a floppy disk and a CD-ROM.
[0083]
【The invention's effect】
As described above, according to the present invention, the following effects can be obtained.
[0084]
The first effect is that overhead such as subscript conversion and dynamic allocation can be reduced by allocating frequently accessed arrays in accordance with the importance according to the NOSHRUNK method having as little overhead as possible.
[0085]
The second effect is that a huge array can be handled by allocating in the SHRUNK method with a small required memory.
[0086]
The third effect is that, at the time of execution, an optimal memory allocation method is determined according to the current state of the computer system, and a part of the executable program being executed is stopped (execution is stopped) by the object program generated accordingly. Therefore, an optimum memory allocation method can always be achieved according to the state of the computer system.
[Brief description of the drawings]
FIG. 1 is a block diagram showing the configuration of first, second, third and fourth embodiments of the present invention.
FIG. 2 is a flowchart showing the operation of the first exemplary embodiment of the present invention.
FIG. 3 is a diagram showing a part of code of a source program input in the first embodiment of the present invention.
FIG. 4 is a table showing a memory allocation size and the like according to SHRUNK system and NOSHRUNK system for each array;
FIG. 5 is a diagram showing a part of code of a source program input in the third embodiment of the present invention.
FIG. 6 is a table showing memory allocation sizes and the like according to SHRUNK system and NOSHRUNK system for each array;
FIG. 7 is a block diagram showing a configuration example of a distributed memory parallel processing computer system in which the present invention is executed.
[Explanation of symbols]
10 Memory allocation optimization system
11 execution manager
12 Dynamic compiler
13 Dynamic linker
14 Execution monitor
15 Source program
16 Object program
17 Executable programs
18 Computer system
19 Optimal allocation decision section
31 ₁ ~ 31 _n Processor element (PE)
32 network
33 Recording media

Claims

In a memory allocation optimization system that optimizes allocation of each data used by a program to a memory of the processor element when the program is executed on a parallel computer including a plurality of processor elements,
An execution monitor that obtains the size of memory currently available in the processor element;
An optimal allocation determining unit that determines an optimal memory allocation method for each data based on the source program of the program and the acquired size of the memory;
Based on the determined optimal memory allocation method for each data, the source program is transformed and recompiled to generate an object program, and the object program is replaced with the corresponding original object program. A dynamic linker that changes the executable program that is running,
An execution manager that controls the operation of each component;
The dynamic compiler modifies the source program so that the part corresponding to the main program is called from the new main program in order to perform the optimal allocation for the memory related to the data directly used in the main program. Memory allocation optimization system characterized by

In a memory allocation optimization system that optimizes allocation of each data used by a program to a memory of the processor element when the program is executed on a parallel computer including a plurality of processor elements,
An execution monitor that obtains the size of memory currently available in the processor element;
An optimal allocation determining unit that determines an optimal memory allocation method for each data based on the source program of the program and the acquired size of the memory;
Based on the determined optimal memory allocation method for each data, the source program is transformed and recompiled to generate an object program, and the object program is replaced with the corresponding original object program. A dynamic linker that changes the executable program that is running,
An execution manager that controls the operation of each component;
Memory allocation optimization characterized in that determination by the optimal allocation determination unit is performed for each procedure call in the program, and an allocation method is determined for each piece of data specified as an argument of the procedure call system.

The memory allocation optimization system according to claim 2 ,
A first method of allocating only a portion of the data related to the processor element to the memory of the processor element;
A second method of allocating the entire data to the memory of the processor element;
The optimum allocation determining unit refers to the importance of each data, allocates each data by either the first method or the second method, and consequently all data to be allocated to the processor element. A memory allocation optimization system, wherein an allocation method for each data is determined such that at least a portion related to the processor element is accommodated in the memory.

The memory allocation optimization system according to claim 3 ,
The optimal allocation determination unit is for each processor element,
(1) The total size of the memory of the processor is the sum of the total size of the data allocated by the first method on the memory and the total size of the data allocated by the second method on the memory. And
(2) A memory allocation optimization system, wherein an allocation method of each data is determined so that importance corresponding to the data allocated by the second method is maximized.

The memory allocation optimization system according to claim 3 ,
The memory allocation optimization system, wherein the allocation method is determined using a method for obtaining an approximate solution of an NP problem.

The memory allocation optimization system according to claim 3 ,
The memory allocation optimization system, wherein the importance is a frequency with which the data is accessed by the program.

The memory allocation optimization system according to claim 2 ,
A memory allocation optimization system, characterized in that, when there are a plurality of allocation methods determined by the optimal allocation determination unit, one allocation method is unified.

In a memory allocation optimization method for optimizing allocation of each data used by a program to a memory of the processor element when the program is executed on a parallel computer including a plurality of processor elements,
Obtaining the size of memory currently available in the processor element;
Determining an optimal memory allocation method for each data based on the source program of the program, the size of the memory, and the importance of each data;
A method source programs of the program, the size of the memory, and on the basis the importance of each data to determine the optimal memory allocation method of the respective data,
Based on the determined optimum memory allocation method for each data, the source program is transformed and recompiled to generate an object program, and the object program is replaced with the corresponding original object program. And changing the running executable program,
In the step of generating the object program, the source corresponding to the main program is called from the new main program in order to optimally allocate the memory related to the data directly used in the main program. A memory allocation optimization method characterized by modifying a program .

In a memory allocation optimization method for optimizing allocation of each data used by a program to a memory of the processor element when the program is executed on a parallel computer including a plurality of processor elements,
Obtaining the size of memory currently available in the processor element;
Determining an optimal memory allocation method for each data based on the source program of the program and the acquired size of the memory;
Determining an optimal memory allocation method for each data based on the source program of the program and the acquired size of the memory, and based on the optimal memory allocation method for each determined data, by recompiling modifying the source program and generating an object program, the object program, by substituting the corresponding original object program, and a step of changing the executable program running ,
The determination in the step of determining the memory allocation method is performed for each procedure call in the program, and the allocation method is determined for each piece of data specified as an argument of the procedure call Allocation optimization method.

A computer recording a program for realizing a memory allocation optimization method for optimizing allocation of each data used by the program to a memory of the processor element when the program is executed by a parallel computer including a plurality of processor elements A readable recording medium,
A program for realizing the method obtains a size of memory currently available in the processor element;
Determining an optimal memory allocation method for each data based on the source program of the program, the size of the memory, and the importance of each data ;
Based on the determined optimum memory allocation method for each data, the source program is transformed and recompiled to generate an object program, and the object program is replaced with the corresponding original object program. in particular from, and a step of changing the executable program being executed,
In the step of generating the object program, the source corresponding to the main program is called from the new main program in order to optimally allocate the memory related to the data directly used in the main program. A computer-readable recording medium having a program recorded thereon, the program being modified .

A computer recording a program for realizing a memory allocation optimization method for optimizing allocation of each data used by the program to a memory of the processor element when the program is executed by a parallel computer including a plurality of processor elements A readable recording medium, which realizes the method,
Obtaining the size of memory currently available in the processor element;
Determining an optimal memory allocation method for each data based on the source program of the program and the acquired size of the memory;
Determining an optimal memory allocation method for each data based on the source program of the program and the acquired size of the memory;
Based on the determined optimum memory allocation method for each data, the source program is transformed and recompiled to generate an object program, and the object program is replaced with the corresponding original object program. And changing the running executable program ,
The determination in the step of determining the memory allocation method is performed for each procedure call in the program, and the allocation method is determined for each piece of data specified as an argument of the procedure call. A computer-readable recording medium on which is recorded.