JPH07319710A - コンパイル処理方法 - Google Patents

コンパイル処理方法

Info

Publication number
JPH07319710A
JPH07319710A JP6106572A JP10657294A JPH07319710A JP H07319710 A JPH07319710 A JP H07319710A JP 6106572 A JP6106572 A JP 6106572A JP 10657294 A JP10657294 A JP 10657294A JP H07319710 A JPH07319710 A JP H07319710A
Authority
JP
Japan
Prior art keywords
data
processing
analysis step
input
output
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.)
Pending
Application number
JP6106572A
Other languages
English (en)
Inventor
Nobufusa Iwanishi
信房 岩西
Katsuyuki Kaneko
克幸 金子
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Priority to JP6106572A priority Critical patent/JPH07319710A/ja
Priority to US08/444,886 priority patent/US6038397A/en
Publication of JPH07319710A publication Critical patent/JPH07319710A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G06F8/443—Optimisation
    • G06F8/4434—Reducing the memory space required by the program code

Landscapes

  • Engineering & Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)
  • Multi Processors (AREA)

Abstract

(57)【要約】 【目的】 マルチタスク処理や並列処理を行う計算機に
おいてデータの最適化を行い、使用するメモリ量を最小
にすることが可能となるコンパイル処理方法を提供す
る。 【構成】 プログラムソース７を入力として字句の解析
を行なう字句解析１と、字句解析１の出力を入力として
その構文を解析する構文解析２と、構文解析２の出力を
入力として構文の意味解析を行なう意味解析３と、意味
解析３の出力を入力としてプログラムをより小さな処理
グループに分割し該処理グループ間でのデータの参照関
係を抽出するデータ参照関係解析４と、データ参照解析
４の出力を入力として前記処理グループ内でのデータ依
存関係グラフを作成するデータ依存関係処理５と、デー
タ依存関係処理５の出力を入力として実行コード８を生
成して出力するコード生成６より構成される。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はコンパイラの最適化技術
に係わり、特にマルチタスク処理や並列処理をおこなう
計算機においてデータの配置を最適化して使用するメモ
リ量を最小にするコンパイラ技術に関する。
【０００２】
【従来の技術】近年、計算機の高速化の進展によってよ
り大きな問題が計算可能になってきており、これに伴っ
て計算機のメモリ量増大に対する需要が増加している。
半導体技術や実装技術等の進展によって計算機のメモリ
コストや実装可能なメモリ量は増加しつつあるが、この
ような物理的な解決方法には限界がある。このために、
プログラミング言語の機能や計算アルゴリズムにおいて
もメモリ量を節約する手段が提案、考案されている。
【０００３】図１３は数値計算等で見られる典型的な構
造を持つＦＯＲＴＲＡＮプログラムの例である。このプ
ログラムにおいて、４つの処理；処理１〜処理４がＩＦ
文で定義される一定の条件を満たすまで繰り返し実行さ
れる。処理１においては変数Ａ、Ｖの代入と参照および
変数Ｘ，Ｙの参照が行われるものとする。同様に処理２
では変数ＢとＷの代入と参照および変数Ｖの参照が、処
理３においては変数Ｃ，Ｘの代入と参照および変数Ｗの
参照が、処理４においては変数Ｄ、Ｙの代入と参照およ
び変数Ｖの参照が行われる。図１４はこのプログラムを
実行する場合のメモリマップを示している。このプログ
ラムは変数を８個使用しているためメモリ上では８語の
領域を占めている。
【０００４】図１３に示すプログラムは、次のようにし
て使用するメモリ量を節約することが可能である。すな
わち、図１５に示すように、各々の処理；処理１〜処理
４の中でのみ使用されていることが明らかな変数Ａ、
Ｂ、Ｃ、Ｄに対してメモリ上で１つの領域を共通に割り
当てる命令であるＣＯＭＭＯＮ文を用いる。図１６は図
１５のＦＯＲＴＲＡＮプログラムでのメモリマップであ
る。ＣＯＭＭＯＮ文を用いることによって４個の変数
Ａ、Ｂ，Ｃ、Ｄが同一のメモリ領域に割り当てられ、こ
の結果、使用するメモリ量が節約できる。
【０００５】
【発明が解決しようとする課題】このように、従来、メ
モリの削減は言語が用意する特殊な文法を用いてプログ
ラマがプログラムの各処理でのデータの依存関係を解析
して行っていた。このため、最適なメモリ削減が困難で
あった。
【０００６】上記した従来例は単一の計算機におけるメ
モリの削減方法を示しているが、並列計算機でのプログ
ラミングにおけるメモリ削減はさらに困難である。この
主な理由は参照される変数が増加することとプロセッサ
間通信によって変数間の参照関係が複雑になることであ
る。並列計算機で問題を解く場合には、問題をプロセッ
サ数以上の数に分割して、プロセッサ間で通信（データ
転送）を行いながら実行するが、分割された領域間の計
算やデータの交換、プロセッサ間でのデータ転送を行う
ために一時的な変数が使われる。さらに、偏微分方程式
を反復的な解法で解く場合等では、いくつかの処理を以
前の処理で求められた値を用いて反復的に行う場合がお
おく、さらに多くの変数が必要で、変数間の依存関係も
複雑になる。このためにＦＯＲＴＲＡＮ言語におけるＣ
ＯＭＭＯＮ文のようなメモリ空間の共有化をユーザが陽
に明示して指定するような方法によって解決する方法
は、非常に困難かつ非効率的であり、高いメモリ使用効
率が得にくいといった問題点を有していた。
【０００７】従って、本発明の目的は、マルチタスク処
理や並列処理を行う計算機においてデータの最適化を行
い、使用するメモリ量を最小にすることが可能となるコ
ンパイル処理方法を提供することにある。
【０００８】
【課題を解決するための手段】本発明は、係る問題点に
対して変数間の依存関係を解析的に行い、この結果を用
いて一時的なデータの保持に使用されている変数を抽出
し、これらの変数の中で互いに依存関係のない複数の変
数を同一のメモリ上に静的に割り当てることによってメ
モリの使用効率を上げるものである。
【０００９】具体的には、第１の解決手段として計算機
の実行コードを生成するコンパイラにおいて、プログラ
ムソースを入力として、字句の解析を行なう字句解析ス
テップと、この字句解析の出力を入力としてその構文を
解析する構文解析ステップと、この構文解析ステップの
出力を入力として構文の意味解析を行なう意味解析ステ
ップと、この意味解析ステップの出力を入力としてプロ
グラムをより小さな処理グループに分割し、該処理グル
ープ間でのデータの参照関係を抽出するデータ参照関係
解析ステップと、このデータ参照解析ステップの出力を
入力として処理グループ内でのデータ依存関係グラフを
作成するデータ依存関係処理ステップと、このデータ依
存関係処理ステップの出力を入力として処理プログラム
コードを生成して出力するコード生成ステップを設け、
データ参照解析ステップは、抽出された処理グループ各
々において該処理グループで値が更新されるが該処理グ
ループの再実行時に以前の値を保存しておく必要がなく
該処理グループ以外では参照のみされる第１のデータ
と、処理グループ単位内においてのみ値の代入および参
照がなされるような第２のデータのいずれかもしくは両
方を認識して抽出する機能を有し、データ依存関係ステ
ップは、前記データ参照解析ステップが上記した第１お
よび第２のデータを抽出した場合は、この処理グループ
間で該当するデータに対してオーバーラップしないよう
に共通のメモリ領域を割り当てたデータ依存関係グラフ
を作成する機能を有するようにするものである。
【００１０】また第２の解決手段は、複数のプロセッサ
エレメント（以下、ＰＥと略す）とこれらのＰＥ間を結
合するネットワークより構成される分散メモリ型の並列
計算機の実行コードを生成するコンパイラにおいて、プ
ログラムソースを入力として、字句の解析を行なう字句
解析ステップと、この字句解析の出力を入力としてその
構文を解析する構文解析ステップと、この構文解析ステ
ップの出力を入力として構文の意味解析を行なう意味解
析ステップと、この意味解析ステップの出力を入力とし
てプログラムをＰＥ間で大域的に同期して処理されるよ
り小さな処理グループに分割し、この処理グループ間お
よびＰＥ間でのデータの参照関係を抽出するデータ参照
関係解析ステップと、このデータ参照解析ステップの出
力を入力として各ＰＥにおける各処理グループ内でのデ
ータ依存関係グラフを作成するデータ依存関係処理ステ
ップと、このデータ依存関係処理ステップの出力を入力
として各ＰＥの処理プログラムコードを生成して出力す
るコード生成ステップを備え、データ参照解析ステップ
は、抽出された各ＰＥにおける処理グループ各々におい
て、次に示すような第１及び第２のデータの両方もしく
はいずれかを認識、抽出する機能をもち、データ依存関
係処理ステップは、データ参照解析ステップによって抽
出された上記第１および第２のデータに依存関係がない
場合には該当するデータに対して各処理グループ間で共
通のメモリ領域を割り当てるようなデータ依存関係グラ
フを作成する機能を有するようにするものである。ここ
で、第１のデータは自処理グループで値が更新されるが
自処理グループの再実行時に以前の値を保存しておく必
要がなく、自ＰＥの自処理グループ以外またはネットワ
ークを介してデータが転送される場合には転送先のＰＥ
では参照のみされるデータであり、第２のデータは参照
関係の範囲が常に自ＰＥ内の処理グループ単位内である
ようなデータである。
【００１１】更に第３の解決手段は、複数のＰＥとこれ
らのＰＥ間を結合するネットワークより構成され、各Ｐ
Ｅが複数の仮想プロセッサエレメントの役割を逐次的に
行う分散メモリ型の並列計算機の実行コードを生成する
コンパイラにおいて、プログラムソースを入力として、
字句の解析を行なう字句解析ステップと、この字句解析
の出力を入力としてその構文を解析する構文解析ステッ
プと、この構文解析ステップの出力を入力として構文の
意味解析を行なう意味解析ステップと、この意味解析ス
テップの出力を入力としてプログラムを仮想ＰＥ間で大
域的に同期して処理されるより小さな処理グループに分
割し、自処理グループ間およびＰＥ間でのデータの参照
関係を抽出するデータ参照関係解析ステップと、このデ
ータ参照解析ステップの出力を入力として各仮想ＰＥに
おける各処理グループ内でのデータ依存関係グラフを作
成するデータ依存関係処理ステップと、このデータ依存
関係処理ステップの出力を入力として各ＰＥの処理プロ
グラムコードを生成して出力するコード生成ステップを
備え、データ参照解析ステップは、抽出された各仮想Ｐ
Ｅにおける処理グループ各々において、以下に示すよう
な第１および第２のデータの両方もしくはいずれかを認
識して抽出する機能を備え、データ依存関係処理ステッ
プは、データ参照解析ステップによって抽出された上記
第１および第２のデータに依存関係がない場合には該当
するデータに対して各処理グループ間で共通のメモリ領
域を割り当てるようなデータ依存関係グラフを作成する
機能を有するようにするものである。ここで、第１のデ
ータは自処理グループで値が更新されるが、自処理グル
ープの再実行時には以前の値を保存しておく必要がな
く、自ＰＥ内の自仮想ＰＥ以外またはネットワークを介
して他のＰＥへデータが転送される場合には転送先のＰ
Ｅでは参照のみされるデータであり、第２のデータは参
照関係の範囲が常に自仮想ＰＥ内の処理グループ単位内
に限られるようなデータである。
【００１２】
【作用】上記構成により、第１の解決手段においては、
単一のＰＥおよび単一のメモリから構成される計算機に
おいて、データ参照関係解析ステップが多重に使用可能
なデータの認識を行い、データ依存関係処理ステップが
これら複数のデータを唯一のメモリ領域に割り付けた場
合のデータ依存関係グラフを生成することができる。こ
れにより効率的なメモリマッピングがおこなわれＰＥ内
での余分なメモリ領域をなくすことによりメモリの使用
効率を向上させることが可能になる。
【００１３】また、第２の解決手段においては、各々が
専用のメモリをもった複数のＰＥとＰＥ間のネットワー
クから構成される計算機において、データ参照関係解析
ステップが各ＰＥ内で多重に使用可能なデータの認識を
行い、データ依存関係処理ステップがこれら複数のデー
タを唯一のメモリ領域に割り付けた場合のデータ依存関
係グラフを生成することができる。これにより効率的な
メモリマッピングがおこなわれＰＥ内での余分なメモリ
領域をなくすことによりメモリの使用効率を向上させる
ことが可能になる。
【００１４】更に、第３の解決手段においては、各々が
専用のメモリを持ち多重タスクを実行する複数のＰＥお
よびＰＥ間ネットワークから構成される計算機におい
て、データ参照関係解析ステップが各ＰＥの各タスクで
多重に使用可能なデータの認識を行い、データ依存関係
処理ステップがこれらの各タスクにまたがる複数のデー
タを唯一のメモリ領域に割り付けた場合のデータ依存関
係グラフを生成することができる。これにより効率的な
メモリマッピングがおこなわれＰＥ内での余分なメモリ
領域をなくすことによりメモリの使用効率を向上させる
ことが可能になる。
【００１５】
【実施例】
（実施例１）以下本発明の第１の実施例について、図面
を参照しながら説明する。
【００１６】図１は本発明の第１の実施例におけるコン
パイル処理方法のフロー図である。同図において、１は
字句解析ステップ、２は構文解析ステップ、３は意味解
析ステップ、４はデータ参照関係解析ステップ、５はデ
ータ依存関係処理ステップ、６はコード生成ステップで
ある。
【００１７】字句解析ステップ１ではソースコード７を
読み込んで、このソースコードで用いられている言語、
例えばＦＯＲＴＲＡＮで定義されている基本構成要素に
分解する。構文解析ステップ２は、字句解析ステップ１
の出力を入力として構文が文法的に正しいかどうかを検
査する。ソースプログラムに文法的な問題がなければ構
文解析スッテプ２の出力は意味解析ステップ３に渡さ
れ、ここでこの構文の意味解析がなされ、変数や制御フ
ロー等に関する種々の情報がテーブル化される。データ
参照関係解析ステップ４は、意味解析ステップ３で生成
された情報を基に変数データのデータグラフを生成し、
このデータグラフを用いてプログラムを複数のより小さ
な処理グループに分割して各処理グループでの変数デー
タのデータグラフを生成してデータの依存関係の検査を
行う。この結果を用いてメモリの割当の最適化をおこな
い、データグラフを書き換える。このデータ参照関係解
析ステップの出力はデータ依存関係処理ステップ５に渡
され、ここで最適化されたデータグラフに応じたメモリ
割当を行う。コード生成ステップ６はこのデータ依存関
係処理ステップ５の出力を用いて実行コードを生成す
る。
【００１８】図２は、図１におけるデータ参照関係解析
ステップ４の詳細なフロー図である。同図において、１
０はデータグラフ生成ステップであり、意味解析ステッ
プ３の出力をもとに処理グループへの分割と変数の依存
関係を示すデータグラフの生成を行う。このデータグラ
フは、データ依存関係検査ステップ１１において、共通
のメモリ領域を割り当てられる複数の変数が存在するか
どうかが検査される。具体的には、ある処理グループ内
で参照関係が閉じている変数、ある処理グループで更新
もしくは参照と更新された変数が引き続く処理グループ
において参照のみされるようなデータ依存関係をもつ変
数を抽出する。このような変数は、共通割当が可能な変
数の候補となる。この共通割当が可能な変数が複数ある
場合には、メモリ割当最適化ステップ１２においてメモ
リ領域が最小になるように共通の変数を割り付けてデー
タグラフを書き換える。共通割当が可能な変数がない場
合には処理を終了する。このブロックの出力はデータ依
存関係処理ステップ５に渡される。
【００１９】図３を用いて、図２に示したデータ参照関
係解析の動作を説明する。同図は、図１３に示したプロ
グラムでのデータの参照関係を示した関係図である。
【００２０】まず最初に、図１３に示したプログラム全
体に対するデータグラフが作成れる。次にこのデータグ
ラフが解析され、参照関係が比較的希薄な部分を検知
し、この部分でデータグラフを切断することによってプ
ログラム全体を複数の比較的小さな処理グループ（処理
１〜処理４）に分割する。
【００２１】次に、これらの処理グループ内および処理
グループ間での変数の参照関係が解析される。図３はこ
の関係を示したテーブルであり、例えば第１カラムは変
数Ａは処理グループ１内で代入と参照がなされているが
他の処理グループでは全く使用されていないことを示し
ており、いちばん下のカラムの変数Ｙは処理グループ１
では参照のみがなされ処理グループ４では代入と参照が
行われていることを示している。このテーブルから、変
数Ａの領域は処理グループ２〜４で使用可能であり、変
数Ｂ，Ｃ，Ｄの領域はそれぞれ１と３〜４、１〜２と
４、１〜３で使用可能、変数Ｖの領域は共用が不可能、
変数Ｗの領域は１と４で共用可能、変数Ｘの領域は処理
グループ２のみ使用可能、変数Ｙは２〜３で使用可能で
あることが分かる。変数ｘでは処理グループ３で代入が
行われて処理グループ１でその参照が行われるので処理
グループ４では使うことができない。以上の共用使用可
能な変数をメモリ領域が最小になるように組み合わせて
割り当てることによって、実際に使用するメモリ領域を
最小にすることができる。この最適化の方法は、例えば
図３において、各処理グループをセルとし、各変数の各
グループでの占有状態をセル間のパスと見立てたチャネ
ル配線領域でのトラック数の最小化問題と同様な手法が
適用できる。このようにして図３のテーブルは図４に示
すようなテーブルにコンパクションされる。変数Ａ、
Ｂ、Ｃ、Ｄが１つのメモリ領域を共用し、変数Ｗおよび
Ｙがメモリ領域を共用している。このような情報を用い
て各処理グループでのデータグラフが書き直され、この
データグラフを用いて各処理グループの実行コードが生
成される。この結果、図２０に示すプログラムのデータ
のメモリマップは図５のようになり、従来８ワード必要
であったデータメモリ領域が４ワードに低減される。
【００２２】以上のように、本実施例によれば、プログ
ラムを複数の小さな処理グループに分け、各処理グルー
プの実行順序を考慮しながら処理グループ間で共用可能
な変数を同じメモリ領域に割り付けることによって、プ
ログラムが占有するデータメモリ領域を減じることがで
き、コードサイズ（データメモリサイズ）の小さな実行
コードを生成することができる。
【００２３】（実施例２）以下、第２の実施例として分
散メモリ型の並列計算機のコンパイラにおけるメモリ割
り付け方法を説明する。図６は分散メモリ型の並列計算
機の構成図であって、複数の演算エレメント６０がネッ
トワーク６１を介して結合されている。各演算エレメン
トはプロセッサ６２、メモリ６３、各演算エレメント６
０のメモリ６３の間でデータの交換を行うデータ転送装
置６４から構成されている。この構成で、各演算エレメ
ント６０は全体的な同期をとりながら各プロセッサ６２
での演算と各メモリ６３間のデータ転送装置６４を用い
たデータの交換を交互に斉一に行いながら処理を実行す
る。このような処理の例として３次元の数値計算問題を
方向毎に分離して解くような問題を考える。
【００２４】図７はこのような問題が持つ典型的なフロ
ーチャートであって、例えば３次元の偏微分方程式をＡ
ＤＩ（交互方向）法で反復的に解く場合に相当する。同
図においてＡｘ，Ａｙ，Ａｚはそれぞれｘ，ｙ，ｚ方向
で問題を解く場合の未知変数であり、処理５〜７での
ｆ，ｇ，ｈは関数名であってこれに続く（）内の変数を
用いた方向依存のある一定の処理を表わしている。Ａ
ｘ，Ａｙ，Ａｚは複数の演算エレメント６０内のメモリ
６３に関数ｆ，ｇ，ｈが並行して計算できるように分散
配置されている。このため、処理５〜７は各演算エレメ
ント内で独立に実行可能である。転送５〜７は、ある方
向に依存して分散配置された右辺の変数を別の方向に依
存して分散配置された左辺の変数にネットワーク６１を
介して置き換える処理である。処理８は処理５〜７で新
たに計算された変数とＡｚを比較して収束判定をする処
理であり、収束していれば全体の処理を終了し、収束し
ていなければ上記した処理および転送を繰り返す。
【００２５】この計算機に対するコンパイラの構成は第
１の実施例における図１および図２に示したものと基本
的な構成と動作はほぼ同様であるが、以下の点で異な
る。すなわち、字句解析ステップ１および構文解析ステ
ップ２はこの並列計算機の言語の文法に沿った字句と構
文の解析を行う。意味解析ステップ３では、プロセッサ
での演算以外に演算エレメント間の通信処理や同期処理
の認識が行われる。データ参照関係解析ステップ４は、
意味解析ステップ３の出力をもとに、演算エレメント内
での演算および演算エレメント間の通信を単位とした処
理グループへの分割と変数の依存関係の解析が行われ、
各処理グループ（また、場合によっては各演算エレメン
ト）でのデータグラフがつくられる。コード生成ステッ
プ６はプロセッサ６０の実行コードに加えてデータ転送
装置が処理するコードも生成する。図２でのデータグラ
フ生成ステップ１０、データ依存関係検査ステップ１１
およびメモリ割当最適化ステップ１２の動作は、演算エ
レメント６０間で行われる個々の通信をそれぞれ別々の
処理グループとして扱う以外は同様である。
【００２６】図７〜図１２を用いて、図６に示した並列
計算機で用いられるコンパイラのデータ参照関係解析の
動作を説明する。図８は、図７に示したプログラムでの
データの参照関係を示した関係図である。
【００２７】まず最初に、図７に示したプログラム全体
に対するデータグラフが作成される。次にこのデータグ
ラフが解析され、各演算エレメントのプロセッサ内で独
立して行われる処理５〜処理８およびこれらの処理間で
行われるデータの転送５〜転送７が検知され、これらが
独立した処理グループとして認識される。次に、これら
の処理グループ内および処理グループ間での変数の参照
関係が解析される。図８はこの関係を示したテーブルで
あり、例えば第１カラムは各演算エレメントに分散して
配置された配列Ａｘは、処理５で代入と参照が、転送５
で参照が、転送７で代入が、処理８で参照がなされてい
ることを示しており、いちばん下のカラムは配列Ａｚの
計算のためのワーク領域は処理７のみで使われているこ
とを示している。
【００２８】データ依存関係検査ステップ１１では、こ
のテーブルからｘ，ｙ，ｚ方向のワーク変数が共用可能
であることを検知し、この結果、メモリ割り当て最適化
ステップ１２ではこれらを同一のメモリ領域に割り当て
ることによって実際に使用するメモリ領域を低減する。
このようにして図８のテーブルは図９に示すようなテー
ブルにコンパクションされ、３方向のワーク変数が共通
の変数に割り当てられるフローグラフが生成される。デ
ータ依存関係処理ステップ５、コード生成ステップ６は
このデータグラフを用いて各処理グループの実行コード
を生成する。この結果、図７に示すプログラムのデータ
のメモリマップの大略は図１１のようになり、従来３ブ
ロックあったワークメモリ領域が１／３に低減される。
【００２９】またデータ依存関係検査ステップ１１で
は、図８に示したテーブルから次のような情報も検知可
能である。すなわち、Ａｘの変数領域は処理５〜転送
５、転送７〜処理８で使用され、処理６〜転送７では使
用されない。同様にＡｙの変数領域は処理５、処理７で
は使用されず，Ａｚの変数領域は処理５〜処理６では使
用されない。一方、ｘ，ｙ，ｚ方向のワーク変数はそれ
ぞれ処理５、６、７でのみ使われるだけであるから、こ
れらの領域はＡｘ、Ａｙ、Ａｚの内の使用されない変数
領域と共用可能であることが検知可能である。この結
果、メモリ割り当て最適化ステップ１２ではこれらを同
一のメモリ領域に割り当てることによって実際に使用す
るメモリ領域を低減する。このようにして図８のテーブ
ルは、図１０に示すようなテーブルにコンパクションさ
れ、３方向のワーク変数がそれぞれの処理で使用されな
いＡｘ，Ａｙ，Ａｚいずれかの変数領域に割り当てられ
るフローグラフが生成される。データ依存関係処理ステ
ップ５、コード生成ステップ６はこのデータグラフを用
いて各処理グループの実行コードを生成する。この結
果、図７に示すプログラムのデータのメモリマップの大
略は図１２のようになり、従来必要であったワークメモ
リ領域が不要となる。
【００３０】以上のように、本実施例によれば、並列計
算機上で実行されるプログラムを複数の演算処理グルー
プと転送処理グループに分け、各処理グループの実行順
序を考慮しながら処理グループ間で共用可能な変数を同
じメモリ領域に割り付けることによって、プログラムが
占有するデータメモリ領域を減じることができ、コード
サイズ（データメモリサイズ）の小さな実行コードを生
成することができる。
【００３１】分散メモリ型の並列計算機においては、演
算エレメント数を仮想化することによって、すなわち、
１つの演算エレメントが複数の演算エレメントの役割を
順次実行することによって、解くべき問題のプログラミ
ングが実際のＰＥ数に依存しないようにされる場合が多
い。このような場合には、１つの実演算エレメントがマ
ルチタスキングによって複数の仮想的なＰＥの振舞いを
するように実行コードが生成される。このような計算機
においては、実演算エレメント内の複数の仮想演算エレ
メント間では実施例１に示したような変数のメモリ割り
当てによるメモリの削減ができ、実演算エレメント間で
は実施例２で述べたような変数のメモリ割り当て手法で
使用するメモリ領域の削減ができる。このように、２つ
の方法を組み合わせることによって非常に多量のメモリ
量が節約できる。
【００３２】
【発明の効果】以上のように本発明は、コンパイラでの
データ参照解析ステップが、抽出された処理グループ各
々において該処理グループで値が更新されるが該処理グ
ループの再実行時に以前の値を保存しておく必要がなく
該処理グループ以外では参照のみされる第１のデータと
参照関係が常に処理グループ単位内において完結するよ
うな第２のデータの両方もしくはいずれかを認識して抽
出する機能を備え、データ依存関係ステップがデータ参
照解析ステップの抽出した上記第１および第２のデータ
に対して前記処理グループ間で共通のメモリ領域を割り
当てるようなデータ依存関係グラフを作成する機能を有
することによって、メモリ使用量の削減が可能となる。
【００３３】また、複数のプロセッサエレメントとこれ
らのプロセッサエレメント間を結合するネットワークよ
り構成される分散メモリ型の並列計算機の実行コードを
生成するコンパイラのデータ参照解析ステップが、各プ
ロセッサエレメントにおける処理グループ各々におい
て、次のような２種類のデータ、つまり、第１のデー
タ：該処理グループで値が更新されるが該処理グループ
の再実行時に以前の値を保存しておく必要がなく、自プ
ロセッサエレメントの該処理グループ以外またはネット
ワークを介してデータが転送される場合には転送先のプ
ロセッサエレメントでは参照のみされるデータ、第２の
データ：参照関係が常に自プロセッサエレメント内の処
理グループ単位内において完結するようなデータ、の両
方もしくはいずれかを認識して抽出する機能を備え、デ
ータ依存関係処理ステップが前記データ参照解析ステッ
プによって抽出されたこれらのデータに依存関係がない
場合には該当するデータに対して各処理グループ間で共
通のメモリ領域を割り当てるようなデータ依存関係グラ
フを作成する機能を有することにより各ＰＥでのメモリ
使用量の削減が可能となる。
【００３４】更に、複数のプロセッサエレメントとこれ
らのプロセッサエレメント間を結合するネットワークよ
り構成され、各プロセッサエレメントが複数の仮想プロ
セッサエレメントの役割を逐次的に行う分散メモリ型の
並列計算機の実行コードを生成するコンパイラのデータ
参照解析ステップが抽出された各仮想プロセッサエレメ
ントにおける処理グループ各々において、次のような２
種類のデータ、つまり第１のデータ：該処理グループで
値が更新されるが該処理グループの再実行時に以前の値
を保存しておく必要がなく、自プロセッサエレメント内
の自仮想プロセッサエレメント以外またはネットワーク
を介してデータが転送される場合には転送先のプロセッ
サエレメントでは参照のみされるデータ、第２のデー
タ：参照関係が常に自仮想プロセッサエレメント内の処
理グループ単位内において完結するようなデータ、の両
方もしくはいずれかを認識して抽出する機能を備え、デ
ータ依存関係処理ステップがデータ参照解析ステップに
よって抽出されたこれらのデータに依存関係がない場合
には該当するデータに対して各処理グループ間で共通の
メモリ領域を割り当てるようなデータ依存関係グラフを
作成する機能を有することによって各仮想ＰＥのメモリ
量および各実ＰＥのメモリ量の両方を削減することがで
きる。
【図面の簡単な説明】
【図１】本発明のコンパイル方式のフロー図
【図２】図１に示すコンパイル方式のデータ参照解析解
析ステップのフロー図
【図３】本発明の第１の実施例におけるメモリ割り当て
最適化前の変数割り当て関係図
【図４】本発明の第１の実施例におけるメモリ割り当て
最適化後の変数割り当て関係図
【図５】本発明の第１の実施例におけるメモリ上の変数
マップ図
【図６】分散メモリ型の並列計算機の構成図
【図７】本発明の第２の実施例で説明するＡＤＩ（相互
方）法の典型的なフローチャート
【図８】本発明の第２の実施例におけるメモリ割り当て
最適化前の変数割り当て関係図
【図９】本発明の第２の実施例におけるメモリ割り当て
最適化後の変数割り当て関係図
【図１０】本発明の第２の実施例における他のメモリ割
り当て最適化後の変数割り当て関係図
【図１１】図９に示す変数割り当てテーブルによるメモ
リ上の変数マップ図
【図１２】図１０に示す変数割り当てテーブルによるメ
モリ上の変数マップ図
【図１３】ＦＯＲＴＲＡＮのプログラムを示した図
【図１４】図１３に示すプログラムのメモリ上の変数マ
ップ図
【図１５】ＣＯＭＭＯＮ文を用いて使用メモリの削減を
図ったＦＯＲＴＲＡＮのプログラムを示した図
【図１６】図１５に示すプログラムのメモリ上の変数マ
ップ図
【符号の説明】 １ 字句解析ステップ ２ 構文解析ステップ ３ 意味解析ステップ ４ データ参照関係解析ステップ ５ データ依存関係処理ステップ ６ コード生成ステップ １０ データグラフ生成ステップ １１ データ依存関係検査ステップ １２ メモリ割り当て最適化ステップ ６０ 演算エレメント ６１ ネットワーク ６２ プロセッサ ６３ メモリ ６４ データ転送装置

Claims (3)

    【特許請求の範囲】
  1. 【請求項１】プログラムソースを入力として字句の解析
    を行なう字句解析ステップと、 前記字句解析の出力を入力としてその構文を解析する構
    文解析ステップと、 前記構文解析ステップの出力を入力として構文の意味解
    析を行なう意味解析ステップと、 前記意味解析ステップの出力を入力としてプログラムを
    より小さな処理グループに分割し該処理グループ間での
    データの参照関係を抽出するデータ参照関係解析ステッ
    プと、 前記データ参照解析ステップの出力を入力として前記処
    理グループ内でのデータ依存関係グラフを作成するデー
    タ依存関係処理ステップと、 前記データ依存関係処理ステップの出力を入力として処
    理プログラムコードを生成して出力するコード生成ステ
    ップを備え、 前記データ参照解析ステップは、抽出された処理グルー
    プ各々において該処理グループで値が更新されるが該処
    理グループの再実行時に以前の値を保存しておく必要が
    なく該処理グループ以外では参照のみされる第１のデー
    タと、処理グループ単位内においてのみ値の代入および
    参照がなされるような第２のデータのいずれかもしくは
    両方を認識して抽出し、 前記データ依存関係ステップは、前記データ参照解析ス
    テップが上記第１および第２のデータを抽出した場合は
    前記処理グループ間で該当するデータに対してオーバー
    ラップしないように共通のメモリ領域を割り当てたデー
    タ依存関係グラフを作成することを特徴としたコンパイ
    ル処理方法。
  2. 【請求項２】複数のプロセッサエレメントとこれらのプ
    ロセッサエレメント間を結合するネットワークより構成
    される分散メモリ型の並列計算機の実行コードを生成す
    るコンパイラであって、 プログラムソースを入力として、字句の解析を行なう字
    句解析ステップと、 前記字句解析の出力を入力としてその構文を解析する構
    文解析ステップと、 前記構文解析ステップの出力を入力として構文の意味解
    析を行なう意味解析ステップと、 前記意味解析ステップの出力を入力としてプログラムを
    プロセッサエレメント間で大域的に同期して処理される
    より小さな処理グループに分割し該処理グループ間およ
    びプロセッサエレメント間でのデータの参照関係を抽出
    するデータ参照関係解析ステップと、 前記データ参照解析ステップの出力を入力として各プロ
    セッサエレメントにおける各処理グループ内でのデータ
    依存関係グラフを作成するデータ依存関係処理ステップ
    と、 前記データ依存関係処理ステップの出力を入力として各
    プロセッサエレメントの処理プログラムコードを生成し
    て出力するコード生成ステップを備え、 前記データ参照解析ステップは、抽出された各プロセッ
    サエレメントにおける処理グループ各々において、 該処理グループで値が更新されるが該処理グループの再
    実行時に以前の値を保存しておく必要がなく、自プロセ
    ッサエレメントの該処理グループ以外、またはネットワ
    ークを介してデータが他のプロセッサエレメントに転送
    される場合には転送先のプロセッサエレメントでは参照
    のみされる第１のデータと、 代入および参照が常に自プロセッサエレメント内の処理
    グループ単位内においてのみなされる第２のデータと
    の、両方もしくはいずれかを認識して抽出し、 前記データ依存関係処理ステップは、前記データ参照解
    析ステップによって抽出された上記第１および第２のデ
    ータに依存関係がない場合には該当するデータに対して
    各処理グループ間でオーバーラップしないように共通の
    メモリ領域を割り当てたデータ依存関係グラフを作成す
    ることを特徴としたコンパイル処理方法。
  3. 【請求項３】複数のプロセッサエレメントとこれらのプ
    ロセッサエレメント間を結合するネットワークより構成
    され、各プロセッサエレメントが複数の仮想プロセッサ
    エレメントの役割を逐次的に行う分散メモリ型の並列計
    算機の実行コードを生成するコンパイラであって、 プログラムソースを入力として字句の解析を行なう字句
    解析ステップと、 前記字句解析の出力を入力としてその構文を解析する構
    文解析ステップと、 前記構文解析ステップの出力を入力として構文の意味解
    析を行なう意味解析ステップと、 前記意味解析ステップの出力を入力としてプログラムを
    仮想プロセッサエレメント間で大域的に同期して処理さ
    れるより小さな処理グループに分割し、該処理グループ
    間およびプロセッサエレメント間でのデータの参照関係
    を抽出するデータ参照関係解析ステップと、 前記データ参照解析ステップの出力を入力として各仮想
    プロセッサエレメントにおける各処理グループ内でのデ
    ータ依存関係グラフを作成するデータ依存関係処理ステ
    ップと、 前記データ依存関係処理ステップの出力を入力として各
    プロセッサエレメントの処理プログラムコードを生成し
    て出力するコード生成ステップを備え、 前記データ参照解析ステップは、抽出された各仮想プロ
    セッサエレメントにおける処理グループ各々において、 該処理グループで値が更新されるが該処理グループの再
    実行時に以前の値を保存しておく必要がなく、自プロセ
    ッサエレメント内の自仮想プロセッサエレメント以外、
    またはネットワークを介して他のプロセッサエレメント
    にデータが転送される場合には、転送先のプロセッサエ
    レメントでは参照のみされる第１のデータと、 代入および参照が常に自仮想プロセッサエレメント内の
    処理グループ単位内においてのみなされる第２のデータ
    との、両方もしくはいずれかを認識して抽出し、 前記データ依存関係処理ステップは、前記データ参照解
    析ステップによって抽出された上記第１および第２のデ
    ータに依存関係がない場合には該当するデータに対して
    各処理グループ間でオーバーラップしないように共通の
    メモリ領域を割り当てたデータ依存関係グラフを作成す
    ることを特徴としたコンパイル処理方法。
JP6106572A 1994-05-20 1994-05-20 コンパイル処理方法 Pending JPH07319710A (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP6106572A JPH07319710A (ja) 1994-05-20 1994-05-20 コンパイル処理方法
US08/444,886 US6038397A (en) 1994-05-20 1995-05-19 System for allocating the memory area of second data which value need not be preserved to another data of some of the processes

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP6106572A JPH07319710A (ja) 1994-05-20 1994-05-20 コンパイル処理方法

Publications (1)

Publication Number Publication Date
JPH07319710A true JPH07319710A (ja) 1995-12-08

Family

ID=14436967

Family Applications (1)

Application Number Title Priority Date Filing Date
JP6106572A Pending JPH07319710A (ja) 1994-05-20 1994-05-20 コンパイル処理方法

Country Status (2)

Country Link
US (1) US6038397A (ja)
JP (1) JPH07319710A (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012038219A (ja) * 2010-08-10 2012-02-23 Toshiba Corp プログラム変換装置、およびそのプログラム
JP2018200731A (ja) * 2018-10-01 2018-12-20 オムロン株式会社 サポート装置およびサポートプログラム

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6243775B1 (en) * 1998-01-20 2001-06-05 Micron Technology, Inc. System for extending the available number of configuration registers
US6272576B1 (en) 1998-01-20 2001-08-07 Micron Technology, Inc. Method for extending the available number of configuration registers
US7010783B2 (en) * 2002-03-18 2006-03-07 Sun Microsystems, Inc. Method and apparatus for deployment of high integrity software using reduced dynamic memory allocation
US6996802B2 (en) * 2002-03-18 2006-02-07 Sun Microsystems, Inc. Method and apparatus for deployment of high integrity software using initialization order and calling order constraints
US6912633B2 (en) * 2002-03-18 2005-06-28 Sun Microsystems, Inc. Enhanced memory management for portable devices
US7181737B2 (en) * 2002-03-18 2007-02-20 Sun Microsystems, Inc. Method and apparatus for deployment of high integrity software using static procedure return addresses
JP2004021425A (ja) * 2002-06-13 2004-01-22 Hitachi Ltd コンパイラにおけるメモリ配置方式
DE102004018243A1 (de) 2004-04-15 2005-11-10 Giesecke & Devrient Gmbh Erzeugen und Verwenden von Speicherbelegungsinformationen bei einem tragbaren Datenträger
GB2451253A (en) * 2007-07-24 2009-01-28 Ezurio Ltd Indicating the position of a next declaration statement in object code when declaring a variable object code
CA2675686C (en) 2009-08-27 2011-10-11 Ibm Canada Limited - Ibm Canada Limitee Object collocation

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4763255A (en) * 1984-10-31 1988-08-09 International Business Machines Corporation Method for generating short form instructions in an optimizing compiler
JP2738692B2 (ja) * 1988-01-29 1998-04-08 株式会社日立製作所 並列化コンパイル方法
US5418965A (en) * 1988-06-24 1995-05-23 Mahar; Robert C. Subroutine-type computer program for enhancing the speed of data processing in data management programs systems
DE68926956T2 (de) * 1988-09-20 1997-03-27 Digital Equipment Corp Anordnung zur teilung eines generischen kodes für ein digitales datenverarbeitungssystem
US5301327A (en) * 1989-06-30 1994-04-05 Digital Equipment Corporation Virtual memory management for source-code development system
JPH03126133A (ja) * 1989-10-11 1991-05-29 Matsushita Electric Ind Co Ltd コンパイラ処理方法
JPH0475139A (ja) * 1990-07-18 1992-03-10 Toshiba Corp ループ並列化装置
US5339428A (en) * 1991-09-04 1994-08-16 Digital Equipment Corporation Compiler allocating a register to a data item used between a use and store of another data item previously allocated to the register
US5355494A (en) * 1991-12-12 1994-10-11 Thinking Machines Corporation Compiler for performing incremental live variable analysis for data-parallel programs
JPH05257704A (ja) * 1992-03-16 1993-10-08 Nec Corp メモリ領域管理方式
US5535392A (en) * 1992-06-26 1996-07-09 Digital Equipment Corporation Using hint generation to cause portions of object files to remain the same

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012038219A (ja) * 2010-08-10 2012-02-23 Toshiba Corp プログラム変換装置、およびそのプログラム
JP2018200731A (ja) * 2018-10-01 2018-12-20 オムロン株式会社 サポート装置およびサポートプログラム

Also Published As

Publication number Publication date
US6038397A (en) 2000-03-14

Similar Documents

Publication Publication Date Title
US8869121B2 (en) Method for the translation of programs for reconfigurable architectures
US5303357A (en) Loop optimization system
JP4339907B2 (ja) マルチプロセッサ向け最適コード生成方法及びコンパイル装置
US5339429A (en) Parallel processing system and compiling method used therefor
US7181730B2 (en) Methods and apparatus for indirect VLIW memory allocation
US11733983B2 (en) Method and apparatus for generating metadata by a compiler
JPH07319710A (ja) コンパイル処理方法
Plevyak et al. Type directed cloning for object-oriented programs
US20090006072A1 (en) Method and Apparatus Performing Automatic Mapping for A Multi-Processor System
CN119311253A (zh) 基于领域特定语言的任务执行方法以及软件开发工具链
US11915056B2 (en) Combination of multiple data processing and machine learning frameworks for a target hardware
CN110673877B (zh) 一种基于手动向量化的并行计算方法
US20030126589A1 (en) Providing parallel computing reduction operations
US6460176B1 (en) Method of, apparatus for, and recording medium storing a program for, parallelizing a program containing an array designated to undergo indirect and irregular division
Goguen et al. Rewrite Rule Machine.
Brezany Input/output intensive massively parallel computing: language support, automatic parallelization, advanced optimization, and runtime systems
Zhou et al. A parallel, out-of-core algorithm for RNA secondary structure prediction
Baloukas et al. Mapping embedded applications on MPSoCs: the MNEMEE approach
JPH07105013A (ja) レジスタ割り付け方式
CN121478673B (zh) 内存分配方法、装置、电子设备、存储介质及芯片
JPH06103462B2 (ja) ベクトル・レングス制御範囲分割処理方式
JPS62219130A (ja) プログラムの最適化方式
CN121614243A (zh) 管理寄存器的方法和装置
JPH05210645A (ja) 並列処理システムとそのためのコンパイル方法
JPS617946A (ja) 最適化コンパイル方式