JP2809073B2 - 配列のメモリ割り付け方式 - Google Patents
配列のメモリ割り付け方式Info
- Publication number
- JP2809073B2 JP2809073B2 JP5321229A JP32122993A JP2809073B2 JP 2809073 B2 JP2809073 B2 JP 2809073B2 JP 5321229 A JP5321229 A JP 5321229A JP 32122993 A JP32122993 A JP 32122993A JP 2809073 B2 JP2809073 B2 JP 2809073B2
- Authority
- JP
- Japan
- Prior art keywords
- array
- memory
- size
- distributed memory
- code
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 230000015654 memory Effects 0.000 title claims description 109
- 238000000034 method Methods 0.000 title claims description 20
- 238000006243 chemical reaction Methods 0.000 claims description 19
- 238000003491 array Methods 0.000 claims description 6
- 238000004458 analytical method Methods 0.000 description 9
- 238000010586 diagram Methods 0.000 description 8
- 238000000605 extraction Methods 0.000 description 6
- 238000005457 optimization Methods 0.000 description 5
- 230000006870 function Effects 0.000 description 3
- 239000000284 extract Substances 0.000 description 2
- 230000010365 information processing Effects 0.000 description 1
- 230000001131 transforming effect Effects 0.000 description 1
Landscapes
- Multi Processors (AREA)
- Complex Calculations (AREA)
- Devices For Executing Special Programs (AREA)
Description
【０００１】
【産業上の利用分野】本発明はソースプログラムから目
的プログラムを生成するコンパイラに関し、特にソース
プログラム中の実行文において定義または参照される配
列を分割し、各々を、分散メモリマルチプロセッサシス
テムを構成するそれぞれ異なるプロセッサ対応の分散メ
モリ上に割り付けるようにした、配列のメモリ割り付け
方式に関する。
的プログラムを生成するコンパイラに関し、特にソース
プログラム中の実行文において定義または参照される配
列を分割し、各々を、分散メモリマルチプロセッサシス
テムを構成するそれぞれ異なるプロセッサ対応の分散メ
モリ上に割り付けるようにした、配列のメモリ割り付け
方式に関する。
【０００２】
【従来の技術】ＦＯＲＴＲＡＮコンパイラ等のコンパイ
ラにおいては、ソースプログラム中の実行文で定義また
は参照される配列に対して、その配列を格納するための
配列領域をメモリ上の連続した領域に割り付けるように
している。これは、複数のプロセッサから構成されるマ
ルチプロセッサシステム向けのコンパイラでも同じであ
った。
ラにおいては、ソースプログラム中の実行文で定義また
は参照される配列に対して、その配列を格納するための
配列領域をメモリ上の連続した領域に割り付けるように
している。これは、複数のプロセッサから構成されるマ
ルチプロセッサシステム向けのコンパイラでも同じであ
った。
【０００３】
【発明が解決しようとする課題】マルチプロセッサシス
テムには、複数のプロセッサが全メモリをほぼ同じアク
セス時間で均等にアクセスできるシステム以外に、例え
ば図６に示すように、各プロセッサＰ１〜Ｐｎ対応に分
散メモリＭ１〜Ｍｎを備えると共に各分散メモリＭ１〜
ＭｎおよびプロセッサＰ１〜Ｐｎに接続されたスイッチ
網ＳＷを備え、各プロセッサＰ１〜Ｐｎは自プロセッサ
対応の分散メモリＭ１〜Ｍｎは直接的に高速にアクセス
できるが、他プロセッサ対応の分散メモリはスイッチ網
ＳＷを通じて間接的にしかアクセスすることができない
システム、いわゆる仮想共有メモリ方式の分散メモリマ
ルチプロセッサシステムがある。
テムには、複数のプロセッサが全メモリをほぼ同じアク
セス時間で均等にアクセスできるシステム以外に、例え
ば図６に示すように、各プロセッサＰ１〜Ｐｎ対応に分
散メモリＭ１〜Ｍｎを備えると共に各分散メモリＭ１〜
ＭｎおよびプロセッサＰ１〜Ｐｎに接続されたスイッチ
網ＳＷを備え、各プロセッサＰ１〜Ｐｎは自プロセッサ
対応の分散メモリＭ１〜Ｍｎは直接的に高速にアクセス
できるが、他プロセッサ対応の分散メモリはスイッチ網
ＳＷを通じて間接的にしかアクセスすることができない
システム、いわゆる仮想共有メモリ方式の分散メモリマ
ルチプロセッサシステムがある。
【０００４】一般にマルチプロセッサシステムでは、１
つの配列に対する処理を複数のプロセッサに分担させる
ことが行われるため、配列領域をメモリ上の連続した領
域に割り付ける方法によると、複数のプロセッサが全メ
モリを均等にアクセスできるマルチプロセッサシステム
の場合には特に問題は生じないが、上述した分散メモリ
マルチプロセッサシステムの場合、配列領域が自己の分
散メモリ上に割り付けられたプロセッサでは高速に配列
要素をアクセスし得るのに対し、それ以外のプロセッサ
では高速なアクセスが行えず、負荷のアンバランスが生
じて並列化の性能が低下するという問題点がある。
つの配列に対する処理を複数のプロセッサに分担させる
ことが行われるため、配列領域をメモリ上の連続した領
域に割り付ける方法によると、複数のプロセッサが全メ
モリを均等にアクセスできるマルチプロセッサシステム
の場合には特に問題は生じないが、上述した分散メモリ
マルチプロセッサシステムの場合、配列領域が自己の分
散メモリ上に割り付けられたプロセッサでは高速に配列
要素をアクセスし得るのに対し、それ以外のプロセッサ
では高速なアクセスが行えず、負荷のアンバランスが生
じて並列化の性能が低下するという問題点がある。
【０００５】そこで本発明の目的は、分散メモリマルチ
プロセッサシステムにおいて配列の処理を各プロセッサ
に分担させる場合に、各プロセッサ間で負荷のアンバラ
ンスが生じないように配列をメモリに割り付けるように
した、配列のメモリ割り付け方式を提供することにあ
る。
プロセッサシステムにおいて配列の処理を各プロセッサ
に分担させる場合に、各プロセッサ間で負荷のアンバラ
ンスが生じないように配列をメモリに割り付けるように
した、配列のメモリ割り付け方式を提供することにあ
る。
【０００６】なお、特開昭６３−１２７３４０号公報
に、配列要素を所定の順序でアクセスする際に特定のメ
モリバンクや特定のバッファにアクセスが集中しないよ
うに配列の次元の寸法を拡大して配列の次元間に隙間を
入れる技術が提案されているが、この技術は分散メモリ
マルチプロセッサシステム向けのコンパイラに適用され
るものではない。また、この技術を分散メモリマルチプ
ロセッサシステムに応用して、例えばＡ（１６，１６）
という配列の第１次元の寸法を分散メモリのサイズに等
しく拡大して、図７に示すように各分散メモリＭ１，Ｍ
２，…に割り付けるようにすると、図中の＊で示す分散
メモリの領域が実質的に他の目的に使用できない無駄な
領域となり、メモリ効率が極端に悪化する。
に、配列要素を所定の順序でアクセスする際に特定のメ
モリバンクや特定のバッファにアクセスが集中しないよ
うに配列の次元の寸法を拡大して配列の次元間に隙間を
入れる技術が提案されているが、この技術は分散メモリ
マルチプロセッサシステム向けのコンパイラに適用され
るものではない。また、この技術を分散メモリマルチプ
ロセッサシステムに応用して、例えばＡ（１６，１６）
という配列の第１次元の寸法を分散メモリのサイズに等
しく拡大して、図７に示すように各分散メモリＭ１，Ｍ
２，…に割り付けるようにすると、図中の＊で示す分散
メモリの領域が実質的に他の目的に使用できない無駄な
領域となり、メモリ効率が極端に悪化する。
【０００７】そこで本発明の別の目的は、配列の次元の
寸法を拡大することなく、各プロセッサの配列処理にか
かる負荷のアンバランスを解消することにある。
寸法を拡大することなく、各プロセッサの配列処理にか
かる負荷のアンバランスを解消することにある。
【０００８】
【課題を解決するための手段】本発明は上記の目的を達
成するために、ソースプログラムを入力し、各プロセッ
サ対応に分散メモリを備え各プロセッサは自プロセッサ
対応の分散メモリを直接アクセスし得ると共に他プロセ
ッサ対応の分散メモリをスイッチ網を通じて間接的にア
クセスし得るように構成された仮想共有メモリ方式の分
散メモリマルチプロセッサシステムで実行可能な目的プ
ログラムを生成するコンパイラにおいて、前記ソースプ
ログラム中の実行文において定義または参照される配列
を分割し、各々を、前記分散メモリマルチプロセッサシ
ステムを構成するそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付ける配列のメモリ割り付け
方式において、 前記ソースプログラムから配列宣言を取
り出す配列取り出し手段と、 取り出された配列宣言にか
かる配列に対して分割サイズを求める分割サイズ決定手
段と、 前記配列宣言にかかる配列が前記ソースプログラ
ム中の実行文に定義または参照される配列として現れた
場合に、その配列を前記求められた分割サイズで分割
し、得られた個々の配列部分に対応するコードとして、
個々の配列部分がそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付けられるような仮想共有メ
モリアドレスで表現されたコードを生成するアドレス変
換コード生成手段とを有し、かつ、 前記アドレス変換コ
ード生成手段は、インデックスｉの配列要素に対して、 ｂａｓｅ＋Ｎ｛ｉｎｔ（ｉ／ｂ）×（ｐ−ｂ）＋ｉ｝ 但し、ｂａｓｅ；当該配列のベースとなるアドレス ｂ；分割サイズ ｐ；各プロセッサに割り当てられた分散メモリのサイズ Ｎ；１つの配列要素が占めるメモリ上の記憶単位数 で示される仮想共有メモリアドレスに変換したコードを
生成する ようにしている。
成するために、ソースプログラムを入力し、各プロセッ
サ対応に分散メモリを備え各プロセッサは自プロセッサ
対応の分散メモリを直接アクセスし得ると共に他プロセ
ッサ対応の分散メモリをスイッチ網を通じて間接的にア
クセスし得るように構成された仮想共有メモリ方式の分
散メモリマルチプロセッサシステムで実行可能な目的プ
ログラムを生成するコンパイラにおいて、前記ソースプ
ログラム中の実行文において定義または参照される配列
を分割し、各々を、前記分散メモリマルチプロセッサシ
ステムを構成するそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付ける配列のメモリ割り付け
方式において、 前記ソースプログラムから配列宣言を取
り出す配列取り出し手段と、 取り出された配列宣言にか
かる配列に対して分割サイズを求める分割サイズ決定手
段と、 前記配列宣言にかかる配列が前記ソースプログラ
ム中の実行文に定義または参照される配列として現れた
場合に、その配列を前記求められた分割サイズで分割
し、得られた個々の配列部分に対応するコードとして、
個々の配列部分がそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付けられるような仮想共有メ
モリアドレスで表現されたコードを生成するアドレス変
換コード生成手段とを有し、かつ、 前記アドレス変換コ
ード生成手段は、インデックスｉの配列要素に対して、 ｂａｓｅ＋Ｎ｛ｉｎｔ（ｉ／ｂ）×（ｐ−ｂ）＋ｉ｝ 但し、ｂａｓｅ；当該配列のベースとなるアドレス ｂ；分割サイズ ｐ；各プロセッサに割り当てられた分散メモリのサイズ Ｎ；１つの配列要素が占めるメモリ上の記憶単位数 で示される仮想共有メモリアドレスに変換したコードを
生成する ようにしている。
【０００９】
【作用】本発明においては、コンパイラがソースプログ
ラム中の実行文において定義または参照される配列を分
割し、個々の配列部分をそれぞれ異なる分散メモリ上に
割り付けることにより、各プロセッサの配列処理にかか
る負荷のアンバランスを解消する。具体的には、配列取
り出し手段がソースプログラムから配列宣言を取り出
し、分割サイズ決定手段が取り出された配列宣言にかか
る配列に対して分割サイズを求め、アドレス変換コード
生成手段が、配列宣言にかかる配列が前記ソースプログ
ラム中の実行文に定義または参照される配列として現れ
た場合に、その配列を前記求められた分割サイズで分割
し、得られた個々の配列部分に対応するコードとして、
個々の配列部分がそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付けられるような仮想共有メ
モリアドレスで表現されたコードを生成する。
ラム中の実行文において定義または参照される配列を分
割し、個々の配列部分をそれぞれ異なる分散メモリ上に
割り付けることにより、各プロセッサの配列処理にかか
る負荷のアンバランスを解消する。具体的には、配列取
り出し手段がソースプログラムから配列宣言を取り出
し、分割サイズ決定手段が取り出された配列宣言にかか
る配列に対して分割サイズを求め、アドレス変換コード
生成手段が、配列宣言にかかる配列が前記ソースプログ
ラム中の実行文に定義または参照される配列として現れ
た場合に、その配列を前記求められた分割サイズで分割
し、得られた個々の配列部分に対応するコードとして、
個々の配列部分がそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付けられるような仮想共有メ
モリアドレスで表現されたコードを生成する。
【００１０】
【実施例】次に本発明の実施例について図面を参照して
詳細に説明する。
詳細に説明する。
【００１１】図１は本発明を適用したコンパイラの一実
施例の構成図である。本例のコンパイラ１は、ソースプ
ログラム２を入力して、コンパイル過程で第１中間テキ
スト３および第２中間テキスト４を順次生成しながら、
最終的に分散メモリマルチプロセッサシステム向けの目
的プログラム５を生成出力する機能を有している。
施例の構成図である。本例のコンパイラ１は、ソースプ
ログラム２を入力して、コンパイル過程で第１中間テキ
スト３および第２中間テキスト４を順次生成しながら、
最終的に分散メモリマルチプロセッサシステム向けの目
的プログラム５を生成出力する機能を有している。
【００１２】コンパイラ１は、ソースプログラム２を入
力して字句解析，構文解析，意味解析等を行って第１中
間テキスト３を出力する解析部１１と、第１中間テキス
ト３を入力して最適化やベクトル化にかかる処理，メモ
リ割り付け処理等を行って第２中間テキスト４を出力す
る処理部１２と、第２中間テキスト４を入力して機械語
で記述された目的プログラム５を出力する目的プログラ
ム生成部１３とを含んでいる。
力して字句解析，構文解析，意味解析等を行って第１中
間テキスト３を出力する解析部１１と、第１中間テキス
ト３を入力して最適化やベクトル化にかかる処理，メモ
リ割り付け処理等を行って第２中間テキスト４を出力す
る処理部１２と、第２中間テキスト４を入力して機械語
で記述された目的プログラム５を出力する目的プログラ
ム生成部１３とを含んでいる。
【００１３】そして、配列のメモリ割り付けに関連する
機能的手段として、解析部１１内に配列取り出し手段１
１１，分割サイズ決定手段１１２および分散メモリサイ
ズ取り出し手段１１３を備え、処理部１２内にアドレス
変換コード生成手段１２１を備えている。
機能的手段として、解析部１１内に配列取り出し手段１
１１，分割サイズ決定手段１１２および分散メモリサイ
ズ取り出し手段１１３を備え、処理部１２内にアドレス
変換コード生成手段１２１を備えている。
【００１４】以下、このように構成されたコンパイラ１
の動作を説明する。
の動作を説明する。
【００１５】コンパイラ１の解析部１１はソースプログ
ラム２を入力し、通常のコンパイラと同様に字句解析，
構文解析，意味解析等を行う。このとき、ソースプログ
ラム２中に配列宣言が現れると、配列取り出し手段１１
１は、この配列宣言を取り出し、配列名，配列の型，次
元数，配列長等の配列にかかる情報を図示しないテーブ
ル等に保持する。
ラム２を入力し、通常のコンパイラと同様に字句解析，
構文解析，意味解析等を行う。このとき、ソースプログ
ラム２中に配列宣言が現れると、配列取り出し手段１１
１は、この配列宣言を取り出し、配列名，配列の型，次
元数，配列長等の配列にかかる情報を図示しないテーブ
ル等に保持する。
【００１６】また、当該宣言された配列に関する分割サ
イズを指定する記述がソースプログラム２中に現れる
と、分割サイズ決定手段１１２は、この記述から当該配
列に関する分割サイズを取得して図示しないテーブル等
に保持する。
イズを指定する記述がソースプログラム２中に現れる
と、分割サイズ決定手段１１２は、この記述から当該配
列に関する分割サイズを取得して図示しないテーブル等
に保持する。
【００１７】なお、本実施例では配列の分割サイズをユ
ーザがソースプログラム中に記述しておく方法を採用し
ているが、分割サイズ決定手段１１２に、対象となる分
散メモリマルチプロセッサシステムのプロセッサ数を調
べて各プロセッサに分散される配列部分のサイズが全て
均等、または配列サイズをプロセッサ台数で割ったとき
に余りがでるときは少なくとも１つのプロセッサを除き
均等となるような分割サイズを自動的に求める機能を持
たせるようにしても良い。
ーザがソースプログラム中に記述しておく方法を採用し
ているが、分割サイズ決定手段１１２に、対象となる分
散メモリマルチプロセッサシステムのプロセッサ数を調
べて各プロセッサに分散される配列部分のサイズが全て
均等、または配列サイズをプロセッサ台数で割ったとき
に余りがでるときは少なくとも１つのプロセッサを除き
均等となるような分割サイズを自動的に求める機能を持
たせるようにしても良い。
【００１８】更に、各プロセッサの分散メモリのサイズ
を指定する記述がソースプログラム２中に現れると、分
散メモリサイズ取り出し手段１１３は、この記述から分
散メモリのサイズを取得して図示しないテーブル等に保
持する。
を指定する記述がソースプログラム２中に現れると、分
散メモリサイズ取り出し手段１１３は、この記述から分
散メモリのサイズを取得して図示しないテーブル等に保
持する。
【００１９】なお、本実施例では分散メモリのサイズを
ユーザがソースプログラム中に記述しておく方法を採用
しているが、コンパイラオプションで指定するようにし
ても良い。更に、分散メモリサイズ取り出し手段１１３
では分散メモリのサイズを取り出すコードを生成するよ
うにしておき、このコードの実行により目的プログラム
の実行開始時に分散メモリのサイズを取得するようにし
ても良い。このときは、後述のアドレス変換コード生成
手段１２１では、分散メモリサイズ取り出し手段１１３
で生成されたコードによって取り出された分散メモリの
サイズが代入される変数を含むコードを生成する構成が
採られる。ここで、分散メモリのサイズは一般的にはマ
シンアーキテクチャに従ってオペレーティング・システ
ムが制御するアドレス機構により定まる。
ユーザがソースプログラム中に記述しておく方法を採用
しているが、コンパイラオプションで指定するようにし
ても良い。更に、分散メモリサイズ取り出し手段１１３
では分散メモリのサイズを取り出すコードを生成するよ
うにしておき、このコードの実行により目的プログラム
の実行開始時に分散メモリのサイズを取得するようにし
ても良い。このときは、後述のアドレス変換コード生成
手段１２１では、分散メモリサイズ取り出し手段１１３
で生成されたコードによって取り出された分散メモリの
サイズが代入される変数を含むコードを生成する構成が
採られる。ここで、分散メモリのサイズは一般的にはマ
シンアーキテクチャに従ってオペレーティング・システ
ムが制御するアドレス機構により定まる。
【００２０】さて、ソースプログラム２が解析部１１で
処理されて第１中間テキスト３が生成されると、処理部
１２がこれを入力して最適化，ベクトル化，メモリ割り
付け等の処理を行って第２中間テキスト４を出力する。
処理されて第１中間テキスト３が生成されると、処理部
１２がこれを入力して最適化，ベクトル化，メモリ割り
付け等の処理を行って第２中間テキスト４を出力する。
【００２１】このとき、アドレス変換コード生成手段１
２１は、ソースプログラム２中の実行文において定義ま
たは参照される配列については、配列取り出し手段１１
１，分割サイズ決定手段１１２および分散メモリサイズ
取り出し手段１１３で図示しないテーブル等に保持され
た分割サイズ，分散メモリサイズ等を考慮して、配列を
分割し、各々を、対象となる分散メモリマルチプロセッ
サシステムを構成するそれぞれ異なるプロセッサに割り
当てられた分散メモリ上に割り付ける。
２１は、ソースプログラム２中の実行文において定義ま
たは参照される配列については、配列取り出し手段１１
１，分割サイズ決定手段１１２および分散メモリサイズ
取り出し手段１１３で図示しないテーブル等に保持され
た分割サイズ，分散メモリサイズ等を考慮して、配列を
分割し、各々を、対象となる分散メモリマルチプロセッ
サシステムを構成するそれぞれ異なるプロセッサに割り
当てられた分散メモリ上に割り付ける。
【００２２】そして、処理部１２によって第２中間テキ
スト４が生成されると、目的プログラム生成部１３がこ
れを機械語に変換して目的プログラム５を生成する。
スト４が生成されると、目的プログラム生成部１３がこ
れを機械語に変換して目的プログラム５を生成する。
【００２３】次に、具体例を挙げて、本実施例の動作を
より具体的に説明する。
より具体的に説明する。
【００２４】今、ソースプログラム２中に図２に示すよ
うな配列宣言２１があり、実行文中に配列Ａの参照文を
含むＤＯループ２２が存在しているとする。また、この
配列Ａに対して分割サイズが「８６」と指定され、分散
メモリのサイズはｐであるものとする。
うな配列宣言２１があり、実行文中に配列Ａの参照文を
含むＤＯループ２２が存在しているとする。また、この
配列Ａに対して分割サイズが「８６」と指定され、分散
メモリのサイズはｐであるものとする。
【００２５】このような配列Ａに対して、アドレス変換
コード生成手段１２１は、配列Ａを８６要素数の第１の
配列部分，８６要素数の第２の配列部分，８４要素数の
第３の配列部分に分割し、図３に示すように、各々がサ
イズｐの分散メモリＭ１，Ｍ２，Ｍ３（アドレスは分散
メモリＭ１を先頭に全分散メモリにわたって連続して振
られている）のうちの分散メモリＭ１に第１の配列部分
３１を割り付け、分散メモリＭ２に第２の配列部分３２
を割り付け、分散メモリＭ３に第３の配列部分３３を割
り付けるようなコードを生成する。
コード生成手段１２１は、配列Ａを８６要素数の第１の
配列部分，８６要素数の第２の配列部分，８４要素数の
第３の配列部分に分割し、図３に示すように、各々がサ
イズｐの分散メモリＭ１，Ｍ２，Ｍ３（アドレスは分散
メモリＭ１を先頭に全分散メモリにわたって連続して振
られている）のうちの分散メモリＭ１に第１の配列部分
３１を割り付け、分散メモリＭ２に第２の配列部分３２
を割り付け、分散メモリＭ３に第３の配列部分３３を割
り付けるようなコードを生成する。
【００２６】即ち、アドレス変換コード生成手段１２１
は、配列Ａのインデックスｉの配列要素に対して、 ｂａｓｅ＋Ｎ｛ｉｎｔ（ｉ／ｂ）×（ｐ−ｂ）＋ｉ｝ で示される仮想共有メモリアドレスに変換したコードを
生成する。ここで、ｂａｓｅは当該配列のベースとなる
アドレスであり、添字の値が０から始まらない場合は仮
想的に０から始まるようにずらされる。また、ｂは分割
サイズ、ｐは分散メモリのサイズ、Ｎは１つの配列要素
が占めるメモリ上の記憶単位数（今の場合は１）、ｉｎ
ｔ（ ）は（ ）の値の整数部分のみを取り出す整数化
関数である。
は、配列Ａのインデックスｉの配列要素に対して、 ｂａｓｅ＋Ｎ｛ｉｎｔ（ｉ／ｂ）×（ｐ−ｂ）＋ｉ｝ で示される仮想共有メモリアドレスに変換したコードを
生成する。ここで、ｂａｓｅは当該配列のベースとなる
アドレスであり、添字の値が０から始まらない場合は仮
想的に０から始まるようにずらされる。また、ｂは分割
サイズ、ｐは分散メモリのサイズ、Ｎは１つの配列要素
が占めるメモリ上の記憶単位数（今の場合は１）、ｉｎ
ｔ（ ）は（ ）の値の整数部分のみを取り出す整数化
関数である。
【００２７】従って、図２の配列Ａを含むループ２２に
対してコンパイラ１が生成するコードのイメージは図４
に示すようになる。但し図４は説明の為にコンパイラ１
が生成するコードをソースプログラムの形に置き直した
ものであり、実際のオブジェクトコードを示すものでは
ない。
対してコンパイラ１が生成するコードのイメージは図４
に示すようになる。但し図４は説明の為にコンパイラ１
が生成するコードをソースプログラムの形に置き直した
ものであり、実際のオブジェクトコードを示すものでは
ない。
【００２８】このようにすることにより、配列Ａを各プ
ロセッサ対応の分散メモリにほぼ均等に分散することが
できるので、分散メモリマルチプロセッサシステムを構
成する各プロセッサに自プロセッサ対応の分散メモリＭ
１，Ｍ２，Ｍ３上の配列部分の処理を分担させることに
より、各プロセッサの配列処理にかかる負荷のアンバラ
ンスが均等化され、並列処理における各プロセッサの仕
事量が均一に小さくなって並列処理の効率が向上する。
ロセッサ対応の分散メモリにほぼ均等に分散することが
できるので、分散メモリマルチプロセッサシステムを構
成する各プロセッサに自プロセッサ対応の分散メモリＭ
１，Ｍ２，Ｍ３上の配列部分の処理を分担させることに
より、各プロセッサの配列処理にかかる負荷のアンバラ
ンスが均等化され、並列処理における各プロセッサの仕
事量が均一に小さくなって並列処理の効率が向上する。
【００２９】以上の実施例では、図２のようにＤＯルー
プ内で用いられている線形配列、すなわちインデックス
ｉが一次式である配列に対して図４のイメージのような
オブジェクトコードを生成したが、図４から明らかなよ
うに、変換後においてはインデックスが線形でなくなっ
ている。一般に、配列のインデックスが線形でないと、
生成されたコードに対する最適化やベクトル化に支障が
生じるため、最適化等を考慮すると、インデックスは線
形であることが望まれる。
プ内で用いられている線形配列、すなわちインデックス
ｉが一次式である配列に対して図４のイメージのような
オブジェクトコードを生成したが、図４から明らかなよ
うに、変換後においてはインデックスが線形でなくなっ
ている。一般に、配列のインデックスが線形でないと、
生成されたコードに対する最適化やベクトル化に支障が
生じるため、最適化等を考慮すると、インデックスは線
形であることが望まれる。
【００３０】インデックスの線形性を保つようにするた
めには、以下のようにすれば良い。即ち、アドレス変換
コード生成手段１２１では、インデックスｉが一次式で
ある配列を含むＤＯループを、ループの初期値，終値，
増分値を適切に設定することにより、配列インデックス
が一次式で表現された内側ループとこのループを包含す
る外側ループとの二重ループに変形した上でオブジェク
トコードを生成することである。
めには、以下のようにすれば良い。即ち、アドレス変換
コード生成手段１２１では、インデックスｉが一次式で
ある配列を含むＤＯループを、ループの初期値，終値，
増分値を適切に設定することにより、配列インデックス
が一次式で表現された内側ループとこのループを包含す
る外側ループとの二重ループに変形した上でオブジェク
トコードを生成することである。
【００３１】このような方法によれば、図２の配列Ａを
含むループ２２に対しては、ソースプログラムのイメー
ジで置き換えて表現した図５に示すようなコードが生成
され、配列アクセスは内側のループの制御変数（ｉ２）
に関して線形性を保つことができる。ここで、外側ルー
プは各プロセッサ対応の分散メモリを渡るループであ
り、内側ループは個々のプロセッサ対応の分散メモリ内
の配列部分の先頭から終了までを渡るループである。
含むループ２２に対しては、ソースプログラムのイメー
ジで置き換えて表現した図５に示すようなコードが生成
され、配列アクセスは内側のループの制御変数（ｉ２）
に関して線形性を保つことができる。ここで、外側ルー
プは各プロセッサ対応の分散メモリを渡るループであ
り、内側ループは個々のプロセッサ対応の分散メモリ内
の配列部分の先頭から終了までを渡るループである。
【００３２】なお、ループ内に現れない配列や、ループ
内に現れても元々線形でない配列は図４に例示した方法
でオブジェクトコードを生成する必要がある。
内に現れても元々線形でない配列は図４に例示した方法
でオブジェクトコードを生成する必要がある。
【００３３】
【発明の効果】以上説明したように、本発明は、配列を
複数に分割し、個々の配列部分をそれぞれ異なる分散メ
モリ上に割り付けるようにしたので、分散メモリマルチ
プロセッサシステムを構成する各プロセッサに自プロセ
ッサ対応の分散メモリ上の配列部分の処理を分担させる
ことにより、各プロセッサの配列処理にかかる負荷のア
ンバランスを解消することができ、且つ、配列にかかる
並列処理の高速化が可能となる。
複数に分割し、個々の配列部分をそれぞれ異なる分散メ
モリ上に割り付けるようにしたので、分散メモリマルチ
プロセッサシステムを構成する各プロセッサに自プロセ
ッサ対応の分散メモリ上の配列部分の処理を分担させる
ことにより、各プロセッサの配列処理にかかる負荷のア
ンバランスを解消することができ、且つ、配列にかかる
並列処理の高速化が可能となる。
【００３４】また、配列の次元の寸法は拡大しないた
め、分散メモリ上の配列部分を割り付けた残りの部分は
他の配列部分の割り付け等に有効に活用することができ
る。
め、分散メモリ上の配列部分を割り付けた残りの部分は
他の配列部分の割り付け等に有効に活用することができ
る。
【００３５】更に、配列がループ内に現れ且つそのイン
デックスが一次式で表現されている場合、そのループ
を、配列インデックスが一次式で表現された内側ループ
とそれを包含する外側ループとの二重ループに変形した
上でオブジェクトコードを生成することにより、配列を
含むループを最適化やベクトル化の対象とすることがで
きる。
デックスが一次式で表現されている場合、そのループ
を、配列インデックスが一次式で表現された内側ループ
とそれを包含する外側ループとの二重ループに変形した
上でオブジェクトコードを生成することにより、配列を
含むループを最適化やベクトル化の対象とすることがで
きる。
【図１】本発明を適用したコンパイラの一例を示すブロ
ック図である。
ック図である。
【図２】ソースプログラム中に現れる配列宣言および配
列を含む実行文の例を示す図である。
列を含む実行文の例を示す図である。
【図３】分散メモリへの配列の割り付け例を示す図であ
る。
る。
【図４】アドレス変換コード生成手段で生成されるコー
ドの一例をソースプログラムの表現形式に置き換えて示
した図である。
ドの一例をソースプログラムの表現形式に置き換えて示
した図である。
【図５】アドレス変換コード生成手段で生成されるコー
ドの別の例をソースプログラムの表現形式に置き換えて
示した図である。
ドの別の例をソースプログラムの表現形式に置き換えて
示した図である。
【図６】分散メモリマルチプロセッサシステムの構成例
を示すブロック図である。
を示すブロック図である。
【図７】従来の問題点の説明図である。
１…コンパイラ １１…解析部 １１１…配列取り出し手段 １１２…分割サイズ決定手段 １１３…分散メモリサイズ取り出し手段 １２…処理部 １２１…アドレス変換コード生成手段 １３…目的プログラム生成部 ２…ソースプログラム ３…第１中間テキスト ４…第２中間テキスト ５…目的プログラム
フロントページの続き (56)参考文献 特開 平３−256129（ＪＰ，Ａ) 特開 平５−290000（ＪＰ，Ａ) 情報処理学会研究会報告（92−ＡＲＣ −97）、92〜97！（1992−12．）、Ｐ. 41−48 情報処理、34〜９！（1993−９）、 Ｐ．1150−1157、「自動並列化コンパイ ラ」 (58)調査した分野(Int.Cl.6，ＤＢ名) G06F 9/45 G06F 15/16 ＪＩＣＳＴファイル（ＪＯＩＳ)
Claims (7)
- 【請求項１】 ソースプログラムを入力し、各プロセッ
サ対応に分散メモリを備え各プロセッサは自プロセッサ
対応の分散メモリを直接アクセスし得ると共に他プロセ
ッサ対応の分散メモリをスイッチ網を通じて間接的にア
クセスし得るように構成された仮想共有メモリ方式の分
散メモリマルチプロセッサシステムで実行可能な目的プ
ログラムを生成するコンパイラにおいて、前記ソースプ
ログラム中の実行文において定義または参照される配列
を分割し、各々を、前記分散メモリマルチプロセッサシ
ステムを構成するそれぞれ異なるプロセッサに割り当て
られた分散メモリ上に割り付ける配列のメモリ割り付け
方式において、 前記ソースプログラムから配列宣言を取り出す配列取り
出し手段と、 取り出された配列宣言にかかる配列に対して分割サイズ
を求める分割サイズ決定手段と、 前記配列宣言にかかる配列が前記ソースプログラム中の
実行文に定義または参照される配列として現れた場合
に、その配列を前記求められた分割サイズで分割し、得
られた個々の配列部分に対応するコードとして、個々の
配列部分がそれぞれ異なるプロセッサに割り当てられた
分散メモリ上に割り付けられるような仮想共有メモリア
ドレスで表現されたコードを生成するアドレス変換コー
ド生成手段とを有し、かつ、 前記アドレス変換コード生成手段は、インデックスｉの
配列要素に対して、 ｂａｓｅ＋Ｎ｛ｉｎｔ（ｉ／ｂ）×（ｐ−ｂ）＋ｉ｝ 但し、ｂａｓｅ；当該配列のベースとなるアドレス ｂ；分割サイズ ｐ；各プロセッサに割り当てられた分散メモリのサイズ Ｎ；１つの配列要素が占めるメモリ上の記憶単位数 で示される仮想共有メモリアドレスに変換したコードを
生成する ことを特徴とする配列のメモリ割り付け方式。 - 【請求項２】 前記アドレス変換コード生成手段は、前
記配列がループ内に現れ且つそのインデックスが一次式
で表現されている場合、該ループを、配列インデックス
が一次式で表現された内側ループと該内側ループを包含
する外側ループとの二重ループに変形した上でコードを
生成することを特徴とする請求項１記載の配列のメモリ
割り付け方式。 - 【請求項３】 前記アドレス変換コード生成手段は、イ
ンデックスｉが一次式である配列を含むＤＯループを、 ＤＯ ｉ１＝１，ｉｎｔ（（ｎ＋ｂ−１）／ｂ） ＤＯ ｉ２＝ｉ１×ｐ＋１，ｍｉｎ（ｉ１×ｐ＋ｂ，ｉｎｔ（ｎ／ｂ） ×（ｐ−ｂ）＋ｎ） ａ（ｉ２） として二重ループ化することを特徴とする請求項２記載
の配列のメモリ割り付け方式。 - 【請求項４】 前記分割サイズ決定手段は、ソースプロ
グラム中に記述された配列の分割サイズを認識して分割
サイズを求めることを特徴とする請求項２または３記載
の配列のメモリ割り付け方式。 - 【請求項５】 前記分割サイズ決定手段は、対象となる
分散メモリマルチプロセッサシステムのプロセッサ数を
調べて各プロセッサに分散される配列部分のサイズが少
なくとも１つのプロセッサを除き均等となるような分割
サイズを求めることを特徴とする請求項２または３記載
の配列のメモリ割り付け方式。 - 【請求項６】 各プロセッサ対応の分散メモリのサイズ
がソースプログラム中またはコンパイラオプションで指
定されることを特徴とする請求項４または５記載の配列
のメモリ割り付け方式。 - 【請求項７】 各プロセッサ対応の分散メモリのサイズ
を取り出すコードを生成する分散メモリサイズ取り出し
手段を備え、 前記アドレス変換コード生成手段は、前記分散メモリサ
イズ取り出し手段で生成されたコードによって取り出さ
れた分散メモリのサイズが代入される変数を含むコード
を生成することを特徴とする請求項４または５記載の配
列のメモリ割り付け方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5321229A JP2809073B2 (ja) | 1993-11-26 | 1993-11-26 | 配列のメモリ割り付け方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5321229A JP2809073B2 (ja) | 1993-11-26 | 1993-11-26 | 配列のメモリ割り付け方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH07152582A JPH07152582A (ja) | 1995-06-16 |
| JP2809073B2 true JP2809073B2 (ja) | 1998-10-08 |
Family
ID=18130258
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5321229A Expired - Fee Related JP2809073B2 (ja) | 1993-11-26 | 1993-11-26 | 配列のメモリ割り付け方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2809073B2 (ja) |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03256129A (ja) * | 1990-03-07 | 1991-11-14 | Hitachi Ltd | 並列計算機用のプログラム変換方法及びその装置 |
-
1993
- 1993-11-26 JP JP5321229A patent/JP2809073B2/ja not_active Expired - Fee Related
Non-Patent Citations (2)
| Title |
|---|
| 情報処理、３４〜９！（１９９３−９）、Ｐ．１１５０−１１５７、「自動並列化コンパイラ」 |
| 情報処理学会研究会報告（９２−ＡＲＣ−９７）、９２〜９７！（１９９２−１２．）、Ｐ．４１−４８ |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH07152582A (ja) | 1995-06-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3551353B2 (ja) | データ再配置方法 | |
| EP1119807B1 (en) | Program code conversion | |
| EP0806725B1 (en) | Method and apparatus for early insertion of assembler code for optimization | |
| US20030196196A1 (en) | Program interpreter | |
| JPH09330233A (ja) | 最適目的コード生成方法 | |
| JP2000231545A (ja) | 並列プログラム生成方法 | |
| US6175935B1 (en) | Software debugging method and recording medium to which debugging program has been recorded | |
| US6334212B1 (en) | Compiler | |
| US6134708A (en) | Program compilation execution system | |
| JP2809073B2 (ja) | 配列のメモリ割り付け方式 | |
| JPH01118931A (ja) | プログラム変換方式 | |
| JP3430635B2 (ja) | 定数参照最適化処理装置 | |
| JPH08212081A (ja) | メモリ割り付け方法、並びにコンパイル方法およびコンパイラ | |
| JPH07105013A (ja) | レジスタ割り付け方式 | |
| JPH11345127A (ja) | コンパイラ | |
| JP3338466B2 (ja) | 主記憶アクセス最適化処理装置 | |
| JPS6234240A (ja) | デ−タ割付け方式 | |
| JP3239963B2 (ja) | マルチ・プロセッサ計算機システム | |
| JP2000020318A (ja) | メモリアクセス命令削減装置および記録媒体 | |
| JP3551352B2 (ja) | ループ分割方法 | |
| JPH07129408A (ja) | 言語処理プログラムの実行方式 | |
| JP3566602B2 (ja) | コンパイル方法、および、コンパイル用プログラムを記録した記録媒体 | |
| JPH0689187A (ja) | インライン展開最適化方法 | |
| McFarlin et al. | Library function selection in compiling Octave | |
| JPH04256132A (ja) | 高級プログラム言語の代入文最適化方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |