JPH064498A - マルチプロセッサ処理装置 - Google Patents

Abstract

(57)【要約】 【目的】 並列処理系のハードウェアの構成が変わった
場合でも、オブジェクトコードを再コンパイルする事無
くマルチプロセッサによる並列処理を可能にすること。 【構成】 少なくとも共有メモリ資源割り当てに対して
アクセスを発生するプログラム記述の解析を行ない排他
制御を指示する手段と、並列処理可能なプログラム処理
単位に対する記述の解析を行ないプロセッサ割り当てを
行なう手段とを有するコンパイル機構と、前記コンパイ
ル機構の出力した中間言語を実行するインタープリット
機構と、前記インタープリット機構により実現される並
列実行の処理ブロック割り当てを動的に行なう機構とに
よって構成されている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はアーキテクチャの異なる
マルチプロセッサによる並列実行処理に関する。

【０００２】

【従来の技術】同一のプロセッサを複数用いることで均
質な並列処理を行なうシステムは既に知られている。

【０００３】一方、異なるアーキテクチャを持つプロセ
ッサを複数用いることで並列処理を行なうシステムにつ
いては、コンパイルにより直接機械語に落とす方法は知
られている。例えば、特開昭６２ー３４２７５号で述べ
られている大型コンピュータのベクトルプロセッサ装置
などはこれに該当する。しかし、この方法では個々のア
ーキテクチャの差を吸収し、均質なマルチプロセッサ処
理系と等価な実行環境を実現することはできなかった。

【０００４】そこで、その問題を解決する方法としてコ
ンパイルにより直接機械語に落とさずに、その間に中間
コードを介在させる方法が特開昭６３−４１９３４号で
提案されている。この方法では中間言語オブジェクトコ
ードを発生するコンパイラと中間言語インタープリタに
より処理が行なわれ、それによりＣＰＵと外部メモリ間
のアクセス頻度を減少させている。

【０００５】

【発明が解決しようとする課題】しかし、上記従来発明
は並列処理に必要な共有変数の排他制御、実行単位の分
散を実現するものではなかったため、並列記述言語によ
って書かれた目的プログラムが実際には並列実行されな
いという問題点があった。

【０００６】本発明はこの様な問題を解決するために鑑
みられたもので、その目的とするところは、異なるアー
キテクチャを持つプロセッサを複数用いることで並列処
理を行なうシステムにおいて、並列記述言語仕様に基づ
いて書かれた目的プログラムにより並列実行を実現する
ことと、プロセッサユニットの変更があった場合でも目
的プログラムの変更を行ない、再コンパイルするという
一連の作業なく並列実行を可能にすることにある。

【０００７】

【課題を解決するための手段】この様な課題を解決する
ために本発明のマルチプロセッサ処理装置は、少なくと
も共有メモリ資源割り当てに対してアクセスを発生する
プログラム記述の解析を行ない排他制御を指示する手段
と、並列処理可能なプログラム処理単位に対する記述の
解析を行ないプロセッサ割り当てを行なう手段とを有す
るコンパイル機構と、前記コンパイル機構の出力した中
間言語を実行するインタープリット機構と、前記インタ
ープリット機構により実現される並列実行の処理ブロッ
ク割り当てを動的に行なう機構とによって構成されてい
る。

【０００８】

【実施例】実施例の説明は次の各項目に従って行なう。

【０００９】０．はじめに １．ソースコードのコンパイル １−１．ターゲットシステムの説明 １−２．並列実行及び同期、排他制御の記述方法 １−３．字句解析、構文解析の処理 １−３−１．引数リスト解析処理（Ｓ４０４） １−３−２．ブロック間の従属関係の抽出（Ｓ４０５、
Ｓ４１６） １−３−３．共有変数処理（Ｓ４１２） ２．中間言語によるコード生成 ２−１．並列実行時のコード生成手段１０８ ２−２．共有資源アクセス手続きのコード生成手段（Ｓ
４１８） ２−３．オブジェクトファイル作成手段１０９の動作 ３．中間言語インタープリタ ３−１．中間言語インタープリタ間の通信 ３−２．中間言語インタープリタの動作状態 ３−３．並列記述部分の実行時処理 ３−４．共有資源アクセスの実行時処理 ３−５．実行プロセッサを明示する手続き ４．説明の補足 ４−１．コンパイラ、インタープリタの使用する表 ４−２．本実施例の展開 ４−２−１．排他制御と共有資源管理 ４−２−２．中間言語インタープリタの実装 ０．はじめに 図１は本発明の一実施例として好適なマルチプロセッサ
システムとそのコンパイラの構成図である。ソースコー
ド１０１のコンパイルは、ターゲットシステムと異なる
コンピュータ上で行なわれても良い。この時、ソースコ
ード１０１を入力として、中間言語オブジェクト１１０
が出力される。この中間言語オブジェクト１１０が実際
のターゲットシステムにおいて実行される。

【００１０】図２はターゲットシステムの一実施例とし
て好適なパーソナルコンピュータ２００の構成図であ
る。

【００１１】１．ソースコードのコンパイル １−１．ターゲットシステムの説明 本実施例のターゲットシステムであるパーソナルコンピ
ュータ２００は、制御装置２０４によって、表示装置、
入力装置等のユーザーインターフェース装置を制御し、
使用者の操作を受けつける。プロセッサ１１３は汎用の
マイクロコンピュータであり、オペレーティングシステ
ム２０３の処理を実行し、プロセッサ資源、メモリ資源
の管理を行なっている。中間言語インタープリタ１１１
はこのオペレーティングシステム２０３の機能を呼び出
して実行される独立したプロセスである。プロセスはオ
ペレーティングシステムにおけるプロセッサ資源、メモ
リ資源割り当ての実行時の単位である。本実施例でプロ
セスは、プロセスの識別子及び実行管理、メモリ管理の
ための情報を含むプロセスヘッダと、中断の際に現在の
プロセッサのレジスタの状態を保存するための領域と、
オブジェクトコード領域、スタック領域からなる。パー
ソナルコンピュータ２００において多重処理を行なう場
合は、複数のプロセスを起動し、プロセスに対するスケ
ジュールによって処理を多重化する。また、中間言語で
記述された目的プログラムのオブジェクトコードは、そ
れぞれ中間言語インタープリタ１１１を起動してこのイ
ンタープリタ上で実行される。

【００１２】パーソナルコンピュータ２００のプロセッ
サ１１３に対して使用者は、ハードウェア付加によって
機能向上を図ることができる。パーソナルコンピュータ
２００はこの目的に応えるため外部拡張用のシステムバ
ス２０２を持つ。図２の構成ではシステムバス２０２を
使用して付加ハードウェア２０１を拡張した様子を示し
た。ここで、プロセッサ１１４はプロセッサ１１３の処
理の部分を分担し、後述する方法で並列実行する事によ
ってパーソナルコンピュータ２００の処理速度を向上さ
せる。この様な付加ハードウェアはその役割からアクセ
ラレータと呼ばれる事がある。プロセッサ１１４はシス
テムバス２０２を介してのデータの授受、割り込み等を
処理するためカーネルプログラム２０５を実行する。中
間言語インタープリタ１１２はこのカーネル２０５に管
理されるプロセスである。プロセッサ１１４がこれらプ
ログラム実行をプロセッサ１１３とは独立して行なうた
め、局所メモリ２０６が使用される。また、プロセッサ
１１４とシステムバス２０２の接続は先入れデータを先
に取り出すことが出来るように構成された順序付きメモ
リであるＦＩＦＯ２０７、２０８によって行なわれる。
ＦＩＦＯ２０７、２０８は、プロセッサ１１３のメモリ
空間にアドレス割り当てされプロセッサ１１３からアク
セスされる。

【００１３】１−２．並列実行及び同期、排他制御の記
述方法 本実施例では、複数プロセッサによる並列実行をプログ
ラム言語記述の段階でソースコード中に明示的に記述す
る。このために並列記述を認める言語仕様が必要であ
る。ここでは言語Pascalに並列記述のための述語を追加
した言語を取り上げて説明する。本実施例では説明の簡
略化のため言語Pascalの文法の中でprocedure文またはf
unction文で開始される副プログラムをブロックと呼
び、代入文とif、while、repeat、for等の出発記号で開
始される文をステートメントと呼ぶ。またbegin...end
で囲まれた「文」の並びは、通常は「複合文（compound
statement）」と呼ぶが、ここではこれもステートメン
トと呼ぶ。追加した仕様は次の２種類である。

【００１４】（１）cobegin,coend cobegin,coendはそれぞれ並列実行を認めるブロックの
開始文および終了文である。

【００１５】（２）モニタ(monitor)型 モニタ（monitor）型は、並列実行される複数のブロッ
クによってアクセスされるいわゆる共有変数を宣言する
型付け（typing）である。モニタ型は共有資源を抽象化
して表す形式と見なす事もできるが、プログラム上は特
定された手続きによってだけアクセスできる資源を与え
る。この方法で共有変数に対する排他制御及び同期を取
り扱う方法は複数の公知例に詳しい（例えば、上田和紀
著：並列プログラミング言語、情報処理、Vol.27、No.
9、pp.995-1004(1986)、Brinch Hansen,P.著：The Prog
ramming Language Concurrent Pascal、IEEE Trans. So
ftware Eng.、 Vol.1、No.2、pp.199-207(1975)など)。

【００１６】図３は、モニタを用いたプログラムの説明
図である。プログラム３００は、手続き３０５が何らか
の整数型のデータを生成し、手続き３０６がそれを次々
に消費していくという処理内容を並列記述言語によって
記述した例である。これは例えば、手続き３０５が外部
装置からデータを受信する処理で、手続き３０６がその
データを加工して表示する場合などに相当する。ここで
変数bufをモニタ型であるbuffertypeとして宣言した事
により、メモリ上の共有資源の実態である変数（変数名
はbuffer）３０８にはモニタ型の宣言３０１内部で定義
した手続き３０２または３０３によってしかアクセスす
る事ができない。またモニタ内の各変数は手続き３０４
で初期化される。生産者手続き３０５が手続きbuf.appe
nd(v)によって変数３０８への代入を行なおうとする
と、実際には処理３０２が実行される。この時、既に配
列変数３０８であるbufferの中味が全て満たされている
とすると、この要求は待ち行列putqを作って待たされる
（３０９）（これを手続きwait(putq)として表示し
た）。それ以外の場合は配列変数３０８への要素の追加
が行なわれ、ポインタが更新された後、手続きsignal(g
etq)が呼び出される（３１０）。手続きsignal(getq)
は、待ち行列getqを作って待たされているデータ取得の
処理呼び出しが有ればそれを実行し、結果を返す処理を
行なう。消費者手続き３０６が手続きbuf.fetch(v)によ
って変数３０８の内容の１要素を読み取ろうとすると、
処理手続き３０３が実行される。この時、配列変数３０
８であるbufferの内容が空であれば、この要求は待ち行
列getqを作って待たされる（処理３１１の手続きwait(g
etq)）。それ以外の場合は配列変数３０８の内容が読み
出され、ポインタの更新が行なわれた後、手続きsignal
(putq)が呼び出される（３１２）。手続きsignal(putq)
は上記と同様に待ち行列putqに手続き呼び出しが有れば
それを実行し、結果を返す。モニタ型の構造はモニタ型
のデータが宣言されたブロックの管理下にある資源と見
なされる。本実施例ではこの資源へのアクセスは中間言
語インタープリタによって行なわれる。インタープリタ
の処理自体は逐次的な処理であるから、結果的に共有変
数への排他制御および処理同期が保証できる。モニタ型
定義を検出した場合の中間言語発生方法は次に述べる。

【００１７】１−３．字句解析、構文解析の処理 ソースコード１０１を読み取ったコンパイラ１０２は、
字句解析手段１０３により字句解析を行なう。ここで
は、ソースコード１０１の中に現われる文字列を順次読
み取ることによって手続き、変数、定数、文字定数、デ
ータ型定義、文字列等の名前と値、さらに演算子、特種
記号、プログラム言語の予約語の取り出しを行なう。こ
の読み取り結果はコンパイラ１０２の作業領域内に記録
される。

【００１８】次に、字句解析手段１０３の読み取り結果
のデータを入力として構文解析手段１０４が実施され
る。本実施例の構文解析符は言語Pascalの文法がLL(1)
と呼ばれる性質の文法であるため、周知の下降解析を行
なう（下降解析に関する公知例には中田育男著：コンパ
イラ、産業図書(1981)等多数がある）。言語Pascal等の
ブロック構造を持つ言語においては、変数名、ブロック
名は宣言されたブロック内を有効範囲とする。このた
め、変数の値の決定、参照にはブロックの深さと（ブロ
ックの深さが同じ場合は）ブロックの登場順序を表す情
報が必要である。構文解析手段１０４ではプログラム開
始のレベルをブロックレベル＝０とみなして処理を進め
る。この後、ブロックの入れ子の状態が１段深くなる毎
にブロックレベルの値は＋１される。同じく、入れ子の
構造を１段抜け出す度に、ブロックレベルの値は−１さ
れる。すなわち主プログラムがブロックレベル＝０であ
り、主プログラム内で宣言される手続きがブロックレベ
ル＝１である。

【００１９】本実施例の構文解析手段１０４が従来方法
と異なる部分は、その内部で共有メモリ資源検出手段１
０５と、並列実行検出手段１０６を処理する点である。
前者は、並列実行される複数の処理単位によってアクセ
スされる変数を定義し、その変数への処理手順を確立す
る実行コードを生成する。後者は、並列に実行される手
続き、関数呼び出しのためのコードを生成する。

【００２０】構文解析手段１０４の処理手順を図４の流
れ図を用いて説明する。ブロック構造を持つ言語の構文
解析を行なう事から、本実施例の構文解析手段１０４
は、再帰的な下降解析を行なう。すなわち、ブロック検
出とブロック内での構文解析を行ない、ブロック内に更
にブロックの定義があれば、自分自身の処理を再帰的に
呼び出し、ブロック検出を行なう。これは、疑似的なプ
ログラム言語で次の様に書くことができる。

【００２１】 procedure block(....); var ident : 述語; ...; begin (* 次の述語を取り出しidentに代入 *) ident := next_word_in_source; if (ident = 'procedure') or (ident = 'function') then block(...) (*再帰*) else begin ....その他の構文...; end end; この繰り返しを正しく制御するため手続きまたは関数の
宣言を検出しブロックに入ると（Ｓ４０１）、ブロック
レベルを＋１し（Ｓ４０２）、ブロック番号を＋１する
（Ｓ４０３）。この一方で、ブロックの終了を検出した
場合は、ブロックレベルを−１し（Ｓ４２３）、その結
果ブロックレベルの大きさが０より小さいか調べる（Ｓ
４２４）。ブロックレベルが０より小さくなった場合
は、主プログラムのレベルで、ブロックの終了を検出し
た事になり、プログラムの構文解析が完了した事を示し
ている。また、ブロックレベルが０以上であればさらに
構文は続く可能性があり、処理を継続する。以上が構文
解析手段１０４の処理の流れの概要である。次に個々の
処理ついてさらに説明する。

【００２２】構文解析の処理では、個々の処理ブロック
について実行コードの開始番地、変数表の格納位置、引
数渡しに使用するスタック領域の大きさ等の情報を記録
する必要がある。本実施例はこの目的に実行時ブロック
管理テーブル５０１とブロック番号管理テーブル８０１
を使用する。図５は本実施例で使用する実行時ブロック
管理テーブル５０１のデータ構造を説明する図である。
実行時ブロック管理テーブル５０１は、データ構造５０
２を一つの要素とする配列の形式をとる。データ構造５
０２は、ブロック番号５０３、下位ブロックへの連鎖５
０４、オブジェクトコード上でのオフセット５０５、引
数渡しに消費するスタックの深さ５０６、引数リストへ
の連鎖アドレス５０７によって構成される。

【００２３】再び流れ図に戻り処理手順の説明を続け
る。

【００２４】処理Ｓ４０３によって、ソースコード中の
全ての処理ブロック（手続き、関数）はユニークなブロ
ック番号が与えられる。各処理ブロックのブロック番号
とブロックレベルの関係を保持するため、本実施例の処
理では図８ａに示すブロック番号管理テーブル８０１が
生成される。ブロック番号管理テーブルの１つの要素
は、ブロック番号８０２、ブロックレベル８０３、テー
ブルエントリ８０４からなるデータ構造である。処理Ｓ
４０３では、この内ブロック番号８０２、ブロックレベ
ル８０３の値の記録が行われる。また処理Ｓ４０３は、
現在の処理ブロックのコード生成の開始位置が全プログ
ラムのオブジェクトコード開始位置から相対位置で何バ
イトの位置であるか計算を行う。この値は実行時ブロッ
ク管理テーブルのデータ構造５０５に記録される。

【００２５】個々のブロック（手続きか関数）はその呼
び出し時に引数を受け取ることができる。このとき、中
間言語インタープリタでは、スタック領域として確保し
たメモリにその引数を積み、処理呼び出しを行なう。そ
こで並列実行時にある手続きを別のプロセッサにスケジ
ュールして実行するためには、このスタック領域に配置
される引数を解釈し、別プロセッサの中間言語インター
プリタの作業領域に複写する必要がある。このため、引
数リスト解析処理（Ｓ４０４）が行なわれる。この処理
は、引数リストを実行時ブロック管理テーブル５０１の
データ構造５０７に連結リストとして記録する。この処
理の詳細は次の節で説明する。

【００２６】続いてブロック間のリンク発生を行なう
（Ｓ４０５）。これは並列実行時の処理ブロック転送に
必要な情報を生成するものである。詳細は後述する。

【００２７】この後処理は定数宣言を検出した場合（Ｓ
４０６）はそれを名前表に登録し（Ｓ４０７）、型宣言
を検出した場合（Ｓ４０８）は、型宣言辞書への登録を
行なう（Ｓ４０９）。通常、構文解析処理ではソースプ
ログラム中に現われる予約語以外の名前は定数名、変数
名、手続き名、関数名、変数型名を区別せず名前表に登
録し、この表中に名前と共にそのオブジェクトタイプを
記録する方法を採る場合が多い。これは名前の多重定義
（関数名と定数名が同一など）の不都合を未然に検出す
る上で合理的な方法である。本実施例も構文解析手段１
０４における名前（識別子）の管理はこの方法によっ
た。

【００２８】但し変数宣言を検出した時（Ｓ４１０）、
共有メモリ資源検出手段１０５においてモニタ型変数が
検出された場合（Ｓ４１１）は、通常の名前表への登録
の他に後述するような共有変数処理（Ｓ４１２）が実施
される。モニタ型以外の変数であればブロック内の変数
についての表作成が行われ（Ｓ４１３）、さらに、局所
変数割り当てのコード生成が処理される（Ｓ４１４）。
ここで、処理Ｓ４１３でブロック内の変数について作成
された変数表のコンパイラ１０２の作業領域上での開始
番地がブロック番号管理テーブル８０１中のテーブルエ
ントリ８０４の値として記録される。

【００２９】次にブロック開始以外の構文についての処
理の流れを説明する。

【００３０】本実施例では言語仕様に並列記述を認めて
いるため、並列実行すべき部分はソースコード中に明示
的にに記述することを要求している。言い換えるとcobe
gin、coendで囲まれた範囲に含まれない処理ブロックは
逐次処理環境での実行コードが生成される。これを構文
解析手段１０４、コード生成手段１０７、１０８、１１
７の立場から見れば、cobegin、coendで並列実行を指定
された処理単位以外のブロックの実行コードは通常のコ
ンパイル処理時と同じコード生成を行うことになる。そ
こで構文解析手段１０４は並列実行検出手段１０６を実
施する。その処理はソースコードの構文中に予約語cobe
ginを検出すると並列実行フラグ＝［真］と設定し（Ｓ
４２０）、予約語coendを検出した場合は並列実行フラ
グ＝［偽］とする（Ｓ４２１）処理である。実際の実行
コード（中間言語文）の生成はこのフラグの真偽を判断
しながら行われる。

【００３１】取り出された述語が識別子であってしかも
名前表登録を検索した結果、手続き名あるいは関数名で
あったとすると、他の処理ブロックを呼び出す処理であ
ると判断できる（Ｓ４１５）。この判断が［真］である
ときはまずブロック間のリンク処理が行われ（Ｓ４１
６）、次にブロック呼び出しのコード生成が行われる
（Ｓ４２５）。この時、上述した「並列実行フラグ」の
内容が検査され、フラグ＝［真］の場合はコード生成手
段１０８が実行される。その他の場合はコード生成手段
１１７が実行される。

【００３２】また、取り出した述語が「モニタ型変数
名」＋「．」＋「手続き名」という名前の構造を持つ時
はモニタ型変数名によって名前表を検索し、名前が存在
した場合モニタ型手続き呼び出しであると判断できる
（Ｓ４１７）。この場合は共有資源アクセス手続き生成
処理（Ｓ４１８）が実行される。この処理の下部構造と
してさらにコード生成手段１０７が処理され、中間言語
文が成生される。

【００３３】以上が構文解析手段１０４の処理の概要で
ある。次に、各部分の動作について順次説明する。

【００３４】１−３−１．引数リスト解析処理（Ｓ４０
４） 周知の様にPascal系の言語では手続きに引数が渡される
場合、引数参照の形式には２通りある。「値を渡す引数
（call by value）」と「名前を渡す引数（call by ref
erence）」である。本実施例では、引数参照型の内部表
現として値渡しの場合”参照型＝０”、名前を渡す場
合”参照型＝１”とした。

【００３５】引数の並びは構文の中ではブロック名に続
く”（”で開始され、変数名と変数のデータ型（整数、
配列、文字等）の対で表記される。また引数並びの終了
は”）；”である。さらに「名前を渡す引数」は、予約
語”var”で開始される。引数リスト解析処理Ｓ４０４
は、予約語”var”を検出した場合、参照型＝１とし、
それ以外の場合は参照型＝０とする。次に変数のデータ
型を解析し、そのデータ型に与えられた内部表現の値を
取り出す。使用可能なデータ型には全て内部表現として
ユニークな値（整数値）が与えられている。解析処理Ｓ
４０４は、この”参照型、変数型”の値を実行時ブロッ
ク管理テーブルの連鎖アドレス５０７から続くデータ構
造５０９のリストに追加する。データ構造５０９は、連
結リストのデータ型をとり、データの末尾は連鎖アドレ
スである。連鎖アドレス５０７からの連鎖５０９は、引
数リストとしてコード生成処理時に参照される。

【００３６】１−３−２．ブロック間の従属関係の抽出
（Ｓ４０５、Ｓ４１６） 本実施例の処理系では、並列実行される対象のブロック
は（それが可能であれば）別のプロセッサの局所メモリ
空間に転送され実行される。このためには、ある処理ブ
ロックを他のプロセッサに配置した時、この処理ブロッ
クから呼び出される手続き、関数のすべてを取り出し、
この複写を前記の処理ブロックと同じプロセッサの局所
メモリに配置することが望まれる。これはある処理ブロ
ックが下位ブロックを呼び出す度にプロセス間通信する
必要を除くための処理である。この実現には、並列実行
の対象となるある処理ブロックに注目した時、その処理
ブロックが呼び出す（以下これを従属すると書く）ブロ
ックを特定できる様な管理手段が実施されれば良い。本
実施例は各処理ブロック間の従属関係を保持するデータ
構造を実行時ブロック管理テーブル５０１に保持するこ
とでこの管理手段を実現した。

【００３７】図４の流れ図中の処理Ｓ４０５、Ｓ４１６
はこの実行時ブロック管理テーブル中に、実際のブロッ
ク間のリンクを記述する処理である。

【００３８】本実施例の言語の特性から図６のソースコ
ードの様にプログラムが記述された時、処理単位間のブ
ロック構造と構文解析時に処理Ｓ４０３で与えたブロッ
ク番号を図示すると図７の様に示すことができる。変数
名、手続き名など識別子に与えられたスコープ（有効範
囲）の考え方に従うと、例えばブロック番号１１である
手続きp321の処理内部では手続きp32,p3など上位構造の
変数にアクセス可能であるが、手続きp31,p2等の変数へ
のアクセスは許されない。

【００３９】この様な変数スコープの関係を正しく維持
しながら、処理ブロックの階層関係を取り出すため処理
Ｓ４０５はブロック番号管理テーブル８０１を参照しな
がら処理を行う。この処理を図９の流れ図に示した。自
ブロックのブロックレベルが０、１のどちらかであれ
ば、自ブロックはトップレベルで宣言されており、上位
階層へ従属しないためリンク発生が不要である（Ｓ９０
１）。これ以外の場合は、ブロック番号管理テーブル８
０１の自ブロックの位置からテーブル内の要素をさかの
ぼり、ブロックレベルの値が自ブロックのブロックレベ
ルの値より一つ小さな値を持つ要素を捜す（Ｓ９０
２）。その要素のブロック番号を取り出し（Ｓ９０
３）、そのブロック番号の値をキーとして実行時ブロッ
ク管理テーブル５０１の中から一致するブロック番号５
０３を持つブロックの位置を見つけ、その要素へアクセ
スする。この要素の下位ブロックへの連鎖アドレス５０
４からの連鎖５０８を生成する（Ｓ９０４）。以上の処
理によって上位構造に位置するブロックについて自ブロ
ックへの連鎖を記録することができる。図８ｂは図６の
プログラムを例に採ってブロック間のリンク動作を説明
した図である。解りやすくするため、ブロック番号管理
テーブル８０１の内容の右側にブロック間のリンクの様
子を矢印で示した。図６のプログラムから図７のように
ブロック構造に従ってブロック番号を与えた時、例えば
ブロック番号＝１０の手続きp32はブロック番号＝５の
手続きp3に従属する。図８ｂに示すように手続きp32の
ブロックレベルの値は２であるから、ブロック番号管理
テーブル８０１をブロックレベル＝１であるような要素
を捜してさかのぼるとブロック番号＝５の手続きp3の位
置を検出できる。

【００４０】他方、処理Ｓ４１６は自ブロックが呼び出
すブロックへの連鎖を生成する処理である。この処理は
より単純である。すなわち、構文中の識別子に従って名
前表を検索した結果、その名前が手続きあるいは関数の
名前であったら、そのブロック番号を取り出す。このブ
ロック番号の値を実行時ブロック管理テーブルの自ブロ
ックの位置の連鎖アドレス５０４に続く連鎖５０８に書
き加えるだけである。また、この連鎖５０８の生成にあ
たり既に同一ブロック番号の要素が連鎖上にあれば重複
を避けるため連鎖への追加は行わない。

【００４１】１−３−３．共有変数処理（Ｓ４１２） 共有変数処理Ｓ４１２は実際のモニタ型変数へのアクセ
スを伴う実行コードの領域を確保する。次にこの領域に
中間言語インタープリタの標準手続きとして用意された
モニタ型手続きの目的コードをロードする。この時、個
々のモニタ型変数にはソースコード内で宣言された順に
ユニークな番号が与えられる。これは図１０に示したデ
ータ構造を持つ共有資源管理テーブル１００１に記録さ
れる。共有資源管理テーブル１００１の一つの要素は、
資源番号１００２、共有変数名１００３、共有資源を宣
言した処理ブロックのブロック番号１００４、モニタ型
手続きの目的コード１００６へのオフセットの値１００
５から構成される。

【００４２】２．中間言語によるコード生成 次に、中間言語の生成手順について説明する。説明の簡
単のため中間言語についてその機能を説明する表の一部
を図１１に図示した。但しTOPは中間言語インタープリ
タの作業領域に取ったスタック型データ領域の最上段の
番地を表し、SPはスタック型データ領域を指し示すポイ
ンタを表す。本実施例のインタープリタスタックはアド
レス値の小さい方に新たに要素を積み重ね、要素を取り
出す時はアドレス値の大きな方向にポインタを更新する
先入れ後出し型のメモリ構造である。また識別子xの格
納されるアドレスをaddr(x)と書き表す。

【００４３】中間言語インタープリタは、 LODV addr(x) と書かれた命令をアドレスaddr(x)に格納されている値
を取り出し、それを中間言語インタープリタの実行時の
スタックの最上段に格納せよという命令として解釈す
る。（以下の説明では記述の簡単のため、これを単に”
LODV x ”と書き表す。）また、 LODA addr(x) という命令はaddr(x)のアドレスの値そのものを評価
し、スタックの最上段に置く。

【００４４】LODN obj はobjが処理ブロックまたはモニタ型の共有資源であ
り、オブジェクトのブロック番号か資源番号の値を取り
出し、スタックの最上段に置く。

【００４５】LOD n はインタープリタの使用するスタック中で現在のスタッ
クポインタから+nバイトの深さのアドレスを計算しその
アドレスにあるデータを取り出し、スタックの最上段に
複写する。

【００４６】ALOC n は現在のスタックポインタを番地の少ない方向に向かっ
てn進め（つまりnだけ減算し）、局所変数のための領域
を割り当てる。

【００４７】UALC n はALOC nと対をなす命令で、スタックポインタの値にn
を加えALOC n 命令で空けた領域を元に戻す。

【００４８】CALL addr(x) は識別子Xの先頭番地へ処理分岐し、命令語RETを検出し
た場合、先にCALL Xを実行した次の命令位置に復帰す
る。

【００４９】ADD はスタック最上段の値と、スタックの次の位置にある値
を加え、スタックポインタを１段スタックの減る方向に
進めてスタックの新たな最上段に加算結果を格納する。

【００５０】中間言語はこのほか演算処理、条件分岐処
理等の命令語を持つ。いずれの命令もプロセッサのレジ
スタをアキュムレータとして使用せず、スタック上で演
算操作を行う形式とした。言うまでもなくこの中間言語
の仕様は並列実行する中間言語のインタープリタ間で統
一されてさえいれば他の仕様であっても構わない。ま
た、ここで使用するスタックは中間言語インタープリタ
の作業領域に取ったリニアなメモリ空間でプロセッサス
タックと異なる。

【００５１】図１３は中間言語記述生成の処理の一部を
疑似的なプログラム言語によって記述した説明図であ
る。記述はブロック呼び出し時のコード生成手順１３０
１と、cobegin、coend文を検出した場合のコード生成手
順１３０３を示している。ブロック呼び出し時の処理に
は引数に対するコード生成手順１３０２が含まれる。こ
の他に算術演算の際の中間言語生成が必要であるが、従
来方法と同じであるため省略した。中間言語生成の処理
はある条件を検出したとき、その条件に適用されるルー
ルに従い中間言語発生する方法をとる。従って処理は条
件の検出とルール化されたコード生成に対し、構文解析
で取り出した識別子、値、番地等の評価を組み込む処理
を繰り返す操作である。

【００５２】以下に例を挙げて上記中間言語を実行コー
ド中でどのように発生するかを説明する。

【００５３】２−１．並列実行時のコード生成手段１０
８ 中間言語による記述の生成を図１２を用いて説明する。
ソースコード中に１２００に示す手続きp1の定義が現わ
れた場合、構文解析手段１０４は図４の流れ図で示した
様に引数リスト解析を行う（Ｓ４０４）。第１引数１２
０１は識別子xで始まる。構文解析手段１０４はこれを
「値を渡す引数」であると判断する。この結果、参照型
＝０が記録され、次に引数の型がintegerであることか
ら整数型の内部表現である１が”型名”として記録され
る。第２引数１２０２は予約語varで始まる。ゆえに構
文解析手段１０４はこれを「名前を渡す引数」と判断
し、”参照型＝１”、”型名＝１”が記録される。この
結果、実行時ブロック管理テーブル５０１の連鎖アドレ
ス５０７からの連鎖５０９によって引数リストが形成さ
れる。手続きp1に関する引数リストの内容を取り出すと
１２０３のように図示できる。

【００５４】ソースコード中に記述１２０４が現われた
場合、並列実行されない場合はコード生成手段１１７が
実施され、引数リスト１２０３の内容に従い、中間言語
記述１２０５が生成される。この記述の生成は引数リス
ト１２０３に現われる順にルール化された命令語を配置
する方法によったもので周知の方法である。

【００５５】本実施例では並列実行する部分について、
従来方法と異なる中間言語記述の発生を行う。前提条件
として本実施例では並列実行が許される手続き、関数は
モニタ型変数以外の変数引数を認めない。これは変数引
数が代入を認める引数であることを考えれば当然であ
る。手続きp2を第１引数に値渡しの整数、第２引数に名
前渡しのモニタ型変数を持つ手続きとし、手続きp3を引
数を持たない手続きとする。ソースコード中に記述１２
０６が現われると本実施例の構文解析手段１０４は次の
手順の処理を実行する。

【００５６】手順１ 並列実行検出手段１０６がcobegi
n文を検出し並列実行フラグを［真］とする（図４の流
れ図では処理Ｓ４２０）。

【００５７】手順２ 構文解析手段１０４の中で記述”
p2(a,b);”が解析され、ブロック呼び出しであると検出
される（Ｓ４１５）。

【００５８】手順３ 並列実行フラグの内容が検査され
る。ここでは［真］であるためコード生成手段１０８が
実行される。

【００５９】手順４ コード生成手段１０８によってコ
ンパイラ１０２の作業領域の名前表が検索され、手続き
p2のブロック番号と引数リストが指定される。

【００６０】手順５ 引数リストの内容から、第１引数
が値渡し（参照型＝０）であり、整数型であると知るこ
とができる。

【００６１】手順６ コード生成手段１０８が生成ルー
ルに従い中間言語の述語を出力する。ここでのルールは
「値渡しの引数は、命令語｛LODV x｝形式を出力」であ
る。

【００６２】手順７ 引数リストの内容から、第２引数
が名前渡しの変数で、モニタ型であることを知ることが
できる。

【００６３】手順８ ルールとして「モニタ型変数引数
は、命令語｛LODN obj｝形式を出力」が用いられ、中間
言語記述が出力される。

【００６４】手順９ 手続きp2を呼び出す中間言語記述
を発生する。ここでは並列実行時のルール「手続き呼び
出しは命令語｛LODN obj、CALL addr(coexec)｝形式を
出力」が適用される。

【００６５】以下、同様に手続きp3についても処理が行
われる。さらに次の手順が処理される。

【００６６】手順１０ 並列実行検出手段１０６がcobe
nd文を検出し並列実行フラグを［偽］とする（図４の流
れ図では処理Ｓ４２１）。

【００６７】手順１１ 並列実行終了時のルールに従
い、命令語｛CALL addr(sync)｝が出力される。

【００６８】以上の手順の結果として記述１２０７が出
力される。ここで手続きcoexecとsyncは中間言語インタ
ープリタの組み込み手続きである。これら組み込み手続
きの動作は”３−３．並列記述部分の実行時処理”の節
で説明する。

【００６９】２−２．共有資源アクセス手続きのコード
生成手段（Ｓ４１８）構文解析手段１０４において、共
有資源へのアクセスを伴う構文が検出された時、処理Ｓ
４１８が実行される。共有資源へのアクセスを伴う中間
言語の発生は疑似的なプログラム言語で書き表すと、図
１３の１３０４のように示すことができる。モニタ型変
数へのアクセスを行うためには、モニタ型変数が非局所
変数として手続き中に指定される場合と、引数リスト中
に指定される場合がある。

【００７０】前者のコード生成は単純である。コードが
実行された場合を図１４ａを使って示すと、中間言語イ
ンタープリタはスタック上にモニタ型手続きへの引数１
４０４を置き、さらに上段にモニタ型資源番号の値１４
０５を置いてappend、fetchの手続き呼び出しを行う。
これはコード生成側から見ると次の手順による中間言語
発生を行うことで実現できる。

【００７１】手順１ 構文解析手段１０４の処理Ｓ４１
８が構文中に記述されたモニタ型の名前をキーとして共
有資源管理テーブル１００１を検索し、資源番号を取り
出す。手順２ コード生成手段１０７が呼び出される。

【００７２】手順３ プログラム１３０４で記述した手
順が実行される。直前までの目的コード生成によりモニ
タ型手続きに対する引数は、スタック最上段１４０４に
置かれる。これに続いて命令語｛LODN obj｝を出力す
る。

【００７３】手順４ 構文解析結果がappend呼び出しか
fetch呼び出しか判断し、命令語｛CALL addr(appendま
たはfetch)｝を出力する。

【００７４】一方、複数の共有資源が有り、同一手続き
を使用しながらもアクセスする資源を場合によって区別
したいという要求の下では、モニタ型引数が必要とな
る。この場合のコード生成はやや複雑である。モニタ型
引数を含むコードとはソースコード中に記述１２０８が
現われた場合等である。図１４ｂの実行時のスタックの
使用の履歴１４０１を用いて説明する。

【００７５】手続き呼び出し時の引数は、スタック上に
積み重ねられる。この後、実際に手続きが呼び出される
と手続き内の局所的な変数を確保するため命令｛ALOC
N｝が実行され、局所領域１４０２が確保される。さら
に演算等の目的コードがスタックを消費し、現在の処理
結果がこの時点でのスタックの最上段１４０４に配置さ
れる。これがモニタ型手続きへの引数である。次にモニ
タ型の資源番号をスタックの最上段に置く。このために
命令語｛LOD +d｝が実行され、スタックの＋ｄバイトの
深さの位置から矢印１４０３の様に値をスタックトップ
に複写する。続いてappend、fetchの手続き呼び出しが
実行される。これはコード生成側から見ると、次の手順
による中間言語発生を行うことで実現できる。

【００７６】手順１ 局所変数のための領域の展開を行
う。このために命令語｛ALOC N｝を出力する。

【００７７】手順２ 他の目的コード生成をする。

【００７８】手順３ モニタ型手続き呼び出しで検出し
たら引数リスト中のモニタ型変数がスタックに置かれた
位置までの深さを計算する。計算結果をｄとして命令語
｛LOD+d｝を発生する。

【００７９】手順４ 構文解析結果がappend呼び出しか
fetch呼び出しか判断し、命令語｛CALL addr(appendま
たはfetch)｝を出力する。

【００８０】手順５ もし必要ならさらに他の目的コー
ド生成をする。その後命令語｛UALC N,RET｝の順に出力
する。

【００８１】以上の処理手順の結果としてソースコード
の記述１２０８から中間言語による目的コード１２０９
が出力される。

【００８２】２−３．オブジェクトファイル作成手段１
０９の動作 上述した手順によって目的コード記述が得られる。オブ
ジェクトファイル生成手段はコード生成手段１０７、１
０８、１１７により生成される目的コード記述を入力と
して中間言語オブジェクト１１０を出力する。目的コー
ド記述は、手続き呼び出しを手続きの名前（識別子）に
結び付けられたブロック番号で記述している。これは実
質的に名前と等価であるから上記説明では手続き名を用
いて説明した。しかし、実行時に必要なのは手続きの名
前ではなく、その手続きがプログラム中で先頭位置から
相対値で何バイトの位置に記録されているかである。こ
の情報は既に説明した実行時ブロック管理テーブル５０
１のデータ構造５０５によって保持されている。そこで
オブジェクトファイル作成手段１０９は、目的コード記
述を読み取り、ブロック名の呼び出しを検出するとこの
ブロック名（正確にはブロック番号）をキーとして実行
時ブロック管理テーブル５０１を検索し、実行コードで
の相対位置５０５を取り出す。次にこの値によって中間
言語記述のブロック名を相対位置５０５の値に置き換え
る。

【００８３】同様に共有資源であるモニタ型変数／手続
きが目的コード記述では資源番号で指定されている。オ
ブジェクトファイル作成手段１０９はこれについても資
源番号をキーとして共有資源管理テーブル１００１を検
索し、実行コード上でのオフセットの値１００５を取り
出し、目的コード記述の中で資源番号として記述されて
いる部分を置き換える。

【００８４】以上の処理に続き、オブジェクトファイル
作成手段１０９は実行時ブロック管理テーブル５０１と
共有資源管理テーブル１００１の内容を目的コード記述
の後に書き加え、中間言語オブジェクト１１０としてフ
ァイル出力する。

【００８５】３．中間言語インタープリタ ３−１．中間言語インタープリタ間の通信 上述したコンパイラ処理系はターゲットシステム上で実
行される必要はない。他のコンピュータシステムをホス
ト装置として中間言語オブジェクト１１０を生成するこ
とが可能である。生成された中間言語オブジェクトはフ
ァイル出力され、ターゲットシステムには磁気ディスク
媒体、半導体ＲＯＭ、通信手段等によって伝達される。
あるいはターゲットシステムで直接上述の構成のコンパ
イラを実行し、ソースコードから中間言語オブジェクト
１１０を生成することも可能である。

【００８６】中間言語インタープリタは、この中間言語
オブジェクト１１０を入力として動作する処理系であ
る。中間言語インタープリタは与えられた中間言語を解
釈し実行できる事が必要条件であり、このためにどのよ
うな実現形態でも良い。もっとも単純な実施例は図１６
の流れ図に示す様な無限ループを続ける装置を用いる方
法である。本実施例は図２で示すようにプロセッサ１１
３が実行するオペレーティングシステム２０３の上にプ
ロセス１１１を起動し、このプロセス１１１によって図
１６の流れ図の処理を実現した。また、プロセッサ１１
４では割り込み処理等をサポートするカーネル２０５の
上にプロセス１１２を起動し、同様の処理の流れを実現
した。従ってここではプロセス１１１、１１２を中間言
語インタープリタ（以下ＩＰＲと略す）と呼ぶ。また説
明のため主プログラムの起動が行われたプロセッサをロ
ーカルプロセッサと呼ぶ。また、並列実行記述を検出し
た後、一部の処理ブロックが分散され並列実行を担うプ
ロセッサをリモートプロセッサと呼ぶ。同様に主プログ
ラムの起動が行われたコンピュータ上の中間言語インタ
ープリタをマスタＩＰＲと呼び、リモートプロセッサ上
で実行される中間言語インタープリタをスレブＩＰＲと
呼ぶ。

【００８７】ＩＰＲとして動作するプロセスは、図１７
のプロセス１７０２として表す構成をとる。プロセス１
７０２はプロセス管理のための情報が記録されるプロセ
スヘッダと、プロセッサプログラムカウンタ１７０３が
指し示す実行コード領域と、作業領域と、プロセッサス
タックポインタ１７１０が指し示すプロセッサスタック
１７１１からなる。実行コード領域には、インタープリ
タプログラムのオブジェクトコード１７０４と、組み込
み手続き群のオブジェクトコード１７０５が格納され
る。中間言語オブジェクトコードが配置されるコード領
域１７０６と、中間言語用のスタック領域１７０７は、
プロセスの作業領域に配置される。また同じ作業領域に
は中間言語用の命令ポインタ１７０８と、中間言語用の
スタックポインタ１７０９が置かれ、この他、実行時ブ
ロック管理テーブル５０１、共有資源管理テーブル１０
０１、実行時プロセッサ管理テーブル１７０１が置かれ
る。ＩＰＲ１１１、１１２はFIFO２０７、２０８を使っ
て通信しあう事ができる。FIFO２０８にデータ書き込み
があるとシステムバス２０２を介してプロセッサ１１３
に割り込みが発生する。この割り込みはオペレーティン
グシステム２０３の処理ルーチンに取り出され、ＩＰＲ
１１１に伝達される。またFIFO２０７にはシステムバス
２０２によりプロセッサ１１３のアドレス空間における
アドレス割り当てが行われている。このためプロセッサ
１１３がこのアドレスにデータ書き込みを行うとFIFO２
０７はプロセッサ１１４への割り込み信号を発生するこ
とができる。プロセッサ１１４のカーネル２０５は割り
込みサービスルーチンによってFIFO２０７に書き込まれ
たデータを取り出し、ＩＰＲ１１２に伝達する。

【００８８】ＩＰＲ１１１、１１２はこのFIFO２０７、
２０８を用いて通信しあうプロセスと見なすことができ
る。本処理系の設計上、パーソナルコンピュータ２００
に対し付加されるハードウェアは複数個許容できる。こ
のため、マスタＩＰＲ（この場合はＩＰＲ１１１）とス
レブＩＰＲの通信は１対１の通信に限定されない。そこ
で、本実施例ではＩＰＲとして動作するプロセス間の通
信に図１５に示す１５０１、１５０５または１５１０の
形式のデータ構造を持つデータ列を用いる。このデータ
構造において、プロセッサ番号１５０３はシステムで一
意に決定する各プロセッサの番号であり、プロセス番号
１５０４は各プロセッサがプロセス生成時にプロセスに
割り当てた番号である。従って、複数のプロセスが存在
してもプロセッサ番号１５０３とプロセス番号１５０４
の両者を指定する事であるプロセスを特定できる。一
方、コマンド１５０２として使用されるのは｛コネクト
・ロック｝、｛ロード｝、｛実行｝、｛リリース｝、
｛フェッチ｝、｛アペンド｝の６つである。通信１５０
１、１５０５を受信したＩＰＲは応答として１５１０の
データ構造からなるメッセージを返す。ここで状態コー
ド１５１１として｛ビジー｝、｛レディ｝、｛アクセプ
ト｝、｛ダーン｝、｛フェイル｝の５つが使用される。

【００８９】以下図１６の流れ図に従ってＩＰＲの動作
を説明する。ＩＰＲはコマンドを受信すると（Ｓ１６０
１）その内容が｛コネクト・ロック｝か判断する（Ｓ１
６０２）。｛コネクト・ロック｝であればＩＰＲ内部の
状態コードを｛ビジー｝とし（Ｓ１６０３）コネクト処
理Ｓ１６０４を実行する。コネクト処理Ｓ１６０４は受
信したデータ列からプロセッサ番号１５０３とプロセス
番号１５０４を取り出し、内部作業領域に記録し、｛コ
ネクト・ロック｝処理を発生したプロセスに対し状態コ
ード｛アクセプト｝を返す。これ以降はコマンドを受け
取った後、これを送信したプロセスがコネクト処理の対
象となったプロセスであるか判断し（Ｓ１６０５）、No
であれば状態コード｛ビジー｝を返す（Ｓ１６０６）。
コネクト処理の対象となったプロセスからのコマンドを
受け取った場合は、｛ロード｝、｛リリース｝、｛実
行｝のいずれかのコマンドを実行する。｛アペンド｝、
｛フェッチ｝コマンドは、コネクトされたプロセス以外
のプロセスに対しても応答される。

【００９０】コマンドが｛リリース｝の場合は、状態コ
ードを｛レディ｝とし（Ｓ１６０７）、コネクト処理の
ため記録したプロセッサ番号、プロセス番号を廃棄し、
コマンド読み取り処理Ｓ１６０１に戻る。

【００９１】コマンドが｛ロード｝であればロード処理
Ｓ１６０８を実行する。ロード処理Ｓ１６０８はスレブ
ＩＰＲの作業領域に中間言語記述されたオブジェクトコ
ード１５０７を読み込み、次にスタック初期化データ１
５０８を読み込み、このデータの指示に従いスタックに
初期状態のデータを格納しスタックポインタを設定す
る。続いて、テーブル初期化データ１５０９を読み込
み、実行時ブロック管理テーブル５０１、共有資源管理
テーブル１００１の内容を初期設定する。

【００９２】コマンドが｛実行｝の時は、実行状態に入
り、コード領域１７０６の命令ポインタの指定する命令
から、逐次実行処理（Ｓ１６０９）に入る。逐次実行処
理Ｓ１６０９は命令語処理群１６１０を実行するほか、
処理内容に応じて組み込み手続き処理群１６１１の処理
内容を実行する。また、逐次実行の処理ループにある場
合、命令実行後にポーリング処理Ｓ１６１２を実行す
る。これはsync命令語実行後のスレブＩＰＲの処理終了
を確認する場合及び他のＩＰＲからの要求に｛ビジー｝
応答する場合に、それぞれ通信ポートからの待ち行列を
検査する必要から行なわれる。

【００９３】以上がＩＰＲの動作概要である。

【００９４】３−２．中間言語インタープリタの動作状
態 本実施例のＩＰＲには初期起動という動作状態が有る。
この動作状態は、中間言語オブジェクト１１０がオペレ
ーティグシステム２０３の管理下で実行された直後にオ
ペレーティグシステム２０３により作り出される動作状
態である。オペレーティングシステム２０３は、中間言
語オブジェクト１１０のファイル属性からこれがＩＰＲ
１１１によって実行管理されるファイルであるという判
断をする。オペレーティングシステム２０３は、この判
断の結果、ＩＰＲ１１１を起動する。（この方法と別
に、コマンドシェルと呼ばれるオペレーティングシステ
ム用命令の通訳系を持つシステムではコマンドシェル用
のテキストとして類似の操作を記述できる）。

【００９５】一方、ＩＰＲはその起動時にオペレーティ
ングシステムから渡される引数を取得できる。上記操作
によりこの引数として中間言語オブジェクトファイル１
１０のファイル参照番号（ファイル管理情報）が渡され
る。このときＩＰＲは中間言語オブジェクト１１０をそ
の作業領域にロードし実行する。ここで起動されたＩＰ
Ｒ１１１が以下マスタＩＰＲとなり、スレブＩＰＲであ
るＩＰＲ１１２に対し必要に応じてコマンドを送り処理
の一部を分担させる。

【００９６】初期起動の状態にあるＩＰＲは状態コード
が｛ビジー｝である。従って、他のＩＰＲが処理の並列
実行の処理分担を要求し、｛コネクト・ロック｝メッセ
ージをこのＩＰＲに発行しても要求が受けつけられな
い。これに対し初期起動の以外の動作状態であるＩＰＲ
は常にスレブＩＰＲとして動作することができる。

【００９７】３−３．並列記述部分の実行時処理 次に図１８を用いて並列実行時のＩＰＲの動作を説明す
る。

【００９８】マスタＩＰＲの命令語解析処理１８０１が
中間言語オブジェクト１１０の記述中に命令語｛CALL a
ddr(coexec)｝を検出した場合、cobegin文処理１８０２
が呼び出される。cobegin文処理１８０２はシステムバ
ス２０２を用いて全てのプロセッサに｛コネクト・ロッ
ク｝コマンドを送る。応答が｛ビジー｝であるか、また
は一定時間を経ても応答がない場合は、それらプロセッ
サが並列実行を分担できない状態に有ることが判断でき
る。一方で、プロセッサ資源の余裕度によっては複数の
ＩＰＲを実行中のプロセッサが存在し、複数の｛アクセ
プト｝メッセージを受信できる場合が有る。そこでマス
タＩＰＲはその作業領域に実行時プロセス管理テーブル
１７０１を作成する。実行時プロセス管理テーブル１７
０１の内容は、｛アクセプト｝メッセージを受け取るこ
とのできたプロセッサ番号及びプロセス番号と、このプ
ロセスをスレブＩＰＲと見なして分散した（あるいはす
る予定の）処理ブロックのブロック番号と、各プロセス
に対する要求待ち行列１８０７へのポインタである。

【００９９】並列実行の対象となるブロックの数が、獲
得したスレブＩＰＲのプロセスの数より小さい場合、マ
スタＩＰＲは不必要なスレブＩＰＲに｛リリース｝メッ
セージを送りコネクトを開放する。これとは反対に並列
実行すべき処理ブロック数が、獲得したスレブＩＰＲよ
り多い場合は、獲得したスレブＩＰＲに対し待ち行列１
８０７を作り、この待ち行列の要素に並列実行したい処
理ブロックを追加する。この処理はcobegin文処理１８
０２が呼び出したスケジューラ１８０３によって処理さ
れる。本実施例のスケジュールアルゴリズムは、スケジ
ューラが検出した新たな要求は、最も短い長さの待ち行
列１８０７に配置するという単純なアルゴリズムであ
る。

【０１００】一方処理ブロックの一部はマスタＩＰＲに
おいても処理可能である。このためスケジューラは述語
展開処理１８０６を実行する。述語展開処理１８０６
は、中間言語記述の LODN foo CALL addr(coexec) という述語の並びを取り出し、 NOP CALL addr(foo) という述語の並びに置き換える。ここでfooはある手続
きまたは関数の相対番地であり、命令語NOPは｛作用し
ない｝命令語を表す。述語展開処理１８０６により書き
換えられた命令語記述は、再び命令語解析処理１８０１
に返され、そこで評価される。このため、命令語解析処
理１８０１および述語展開処理１８０６は、中間言語の
命令ポインタ１７０８を処理内容に従い書き換える。

【０１０１】以上の処理において、並列実行の対象とな
る複数の処理ブロックをどの様な順序でマスタＩＰＲと
スレブＩＰＲに分配するかはスケジューラ１８０３で決
定される。本実施例のスケジューラ１８０３は後述する
特殊な命令を使用しないかぎり、少なくとも一つの処理
ブロックはマスタＩＰＲへの割り当てを行なう。

【０１０２】マスタＩＰＲは、スレブＩＰＲ１８０８に
対する待ち行列１８０７に前述した｛ロード｝メッセー
ジのデータ構造に従うデータ列と、｛実行｝メッセージ
をエンキューする。この処理要求を実行するスレブＩＰ
Ｒは処理終了後データ構造１５１０からなるメッセージ
を返す。この時の状態コードは正常終了であれば｛ダー
ン｝が返される。これに対し、何らかの実行時エラーを
検出した場合は状態コード｛フェイル｝が返される。エ
ラー処理に関して目的プログラムのソースコードが何ら
かの対応をする必要が有るが、これは従来のプログラミ
ングと同じである。状態コード｛ダーン｝によって正常
終了した処理は、もし処理ブロックが関数であれば関数
の値をデータ１５１２によって返す。

【０１０３】並列実行を開始したマスタＩＰＲは、coen
d文によって並列実行の終了を待つ。既に説明した様にc
oend文に対し生成される中間言語記述は｛CALL addr(sy
nc)｝である。命令語解析処理１８０１は、この記述を
検出するとsync文処理１８０５を呼び出す。sync文処理
１８０５はスレブＩＰＲからの｛ダーン｝メッセージを
待ち、実行時プロセッサ管理テーブル１７０１のプロセ
ッサ番号、プロセス番号との一致を確認し処理終了を記
録する。全ての処理ブロックの処理終了が確認されると
sync文処理１８０５は終了する。既に述べた様にマスタ
ＩＰＲは、スケジューラ１８０３の制御に従い、少なく
とも一つの処理ブロックを実行するのでＩＰＲ自体が逐
次処理系であることからsync文処理１８０５が実行され
るのはマスタＩＰＲの分担した処理ブロックの実行が終
了した後である。

【０１０４】３−４．共有資源アクセスの実行時処理 次に、図１９の流れ図を用いてモニタ型手続き呼び出し
によって共有変数へのアクセスが発生した場合の処理に
ついて説明する。命令語解析処理１８０１は、手続きap
pendまたはfetchの呼び出しを検出すると、ＩＰＲスタ
ックの最上段からモニタ型の資源番号を取り出す（Ｓ１
９０１）。この資源番号１００２をキーとして共有資源
管理テーブル１００１を検索する（Ｓ１９０２）。検索
結果として、その資源が宣言されたブロック番号１００
４が取得できる（Ｓ１９０３）。このブロック番号を自
ブロックの番号と比較し（Ｓ１９０４）、一致する場合
は通常の手続き呼び出しと同じ処理を行なう（Ｓ１９０
７）。それ以外であれば、ＩＰＲは自プロセスが実行中
のブロック番号から実行時ブロック管理テーブル５０１
の要素５０２にアクセスし、下位ブロックへの連鎖アド
レス５０４からの連鎖５０８をたどる（Ｓ１９０５）。
この処理によってブロック番号の一致するブロックが見
つかれば（Ｓ１９０６）手続き呼び出し処理を行なう
（Ｓ１９０７）。連鎖５０８の終了まで検査しても一致
するブロック番号を検出できない時は、実行時ブロック
管理表によってモニタ型資源を保持するプロセッサ番
号、プロセス番号を取り出し、この２つの番号で指定さ
れるＩＰＲにメッセージ｛フェッチ｝あるいは｛アペン
ド｝を送り（Ｓ１９０８）処理結果のデータ列を受け取
るまで待機する（Ｓ１９０９）。

【０１０５】一方、このメッセージを受け取ったＩＰＲ
側では図１６に示す様にフェッチ処理Ｓ１６１３または
アペンド処理Ｓ１６１４を行なう。この処理はメッセー
ジのデータ部分からモニタ型共有資源の資源番号を取り
出し、この資源番号に従い共有資源管理テーブル１００
１の登録を検査する。次に該当する要素を取り出し、そ
のデータ構造１００５からモニタ型手続きの実行コード
上での番地計算を行ない、実際の処理を呼び出し、処理
結果を状態コード｛ダーン｝と共に、要求側ＩＰＲに返
す。

【０１０６】ここで、他のプロセッサにあるモニタ型変
数にアクセスを行なった場合は、メッセージを受信し応
答を返すＩＰＲの処理が逐次処理であるため、完全に排
他制御される。また、他のプロセッサのＩＰＲから応答
が有るまで要求側のＩＰＲは待機するため、要求側での
追い越し処理の発生も防ぐことができる。同一プロセッ
サ上で複数のプロセスが生成され、複数のＩＰＲを実行
中の場合もモニタ型では共有資源に対するアクセスを専
用の処理に限定しており、この処理の実行がＩＰＲによ
って逐次的に行なわれるため排他制御できる。

【０１０７】一方、共有資源の中に実際のデータ列が書
き込まれないうちに値を読み取ろうとしても処理内容は
無効なものとなる。また、バッファが全て満たされた状
態に更に書き込みを行なうと、先行するデータを（多重
書き込みにより）失ってしまう。これらの不都合を防ぐ
には同期機構が必要であるが、モニタ型内部の手続きと
して記述した待ち行列に対するwait及びsignal処理によ
って同期は維持される。

【０１０８】以上の処理によって本実施例では、排他制
御を行ないながら複数個のＩＰＲの実行が可能となる。

【０１０９】３−５．実行プロセッサを明示する手続き 以上に説明した処理系は実際にリモートプロセッサに配
置される処理ブロックも、またローカルプロセッサで実
行を継続する処理ブロックも、中間言語記述の上では同
様な命令語を使用する処理系であった。このため、中間
言語記述の中でプロセッサを特定する記述や、処理ブロ
ックをリモートプロセッサの局所メモリに転送するため
の記述を明示的書く必要が無い処理系の実現方法を説明
した。なぜなら、本発明がハードウェア変更により書き
換えの必要の無い処理系の実現を目的としたからであ
る。

【０１１０】一方、上記とは逆に専用プロセッサを付加
した場合（特に信号処理、画像処理等の特定分野では重
要であるが）、処理分散するプロセッサを明示的に特定
したい場合がある。このために本実施例の処理系は組み
込み関数として function processor(slot:integer) : boolean; を用意した。これは、システムバスの拡張基板用のスロ
ットの番号を引数slot（整数型）で指定すると、その拡
張基板用のスロットにプロセッサ基板が実装され、中間
言語インタープリタが実行されているとき、論理［真］
を返す関数である。この関数が呼び出されると、マスタ
ＩＰＲは、プロセッサ番号を指定して｛コネクト・ロッ
ク｝メッセージを送る。この応答として｛アクセプト｝
メッセージの応答があれば、関数の戻り値は｛TRUE｝が
代入される。また、一定時間以上応答が無い場合、また
は応答が｛ビジー｝である場合は関数の戻り値は｛FALS
E｝である。

【０１１１】さらに本実施例の処理系は、組み込み手続
きとして procedure distribute(slot:integer; procedure foo); を用意した。これは拡張基板用のスロットの番号を引数
slot（整数型）で指定し、かつそのスロットのハードウ
ェア上のプロセッサに手続き引数fooで指定される手続
きを配置し実行する手続きである。第２引数はfunction
foo:tt;等の様に指定しても構わない。ここでfooは関
数名、ttはデータ型名である。この手続きの実現のた
め、マスタＩＰＲはプロセッサ番号を指定して｛コネク
ト・ロック｝メッセージを送り、この応答として｛アク
セプト｝メッセージの応答があれば続けて｛ロード｝及
び｛実行｝メッセージを送る。この処理によって上記手
続き中に手続き引数あるいは関数引数で指定された処理
ブロックの実行を特定のハードウェアに割り当て処理す
る。上記の２つの組み込み処理を用い、プロセッサを特
定した実行を記述することができる。次はその記述の一
例である。引数ａ、ｂを持つ手続きPROC1と、引数ａを
持つ手続きPROC2を並列実行する場合であり、システム
バスのスロット４のプロセッサにPROC1を配置したいと
すると次のように書ける。

【０１１２】ｃｏｂｅｇｉｎ ｉｆ ｐｒｏｃｅｓｓｏｒ（４） ｔｈｅｎ ｄｉｓｔ
ｉｂｕｔｅ（４，ＰＲＯＣ１（ａ，ｂ）） ｅｌｓｅ ＰＲＯＣ１（ａ，ｂ）； ＰＲＯＣ２（ａ）； ｃｏｅｎｄ； この例では、拡張スロット４にプロセッサ基板が無い場
合は手続きＰＲＯＣ１、PROC2は通常のシーケンスで並
列実行される。

【０１１３】４．説明の補足 ４−１．コンパイラ、インタープリタの使用する表 図２０を用いて本実施例の説明の中で示した各種表構造
について、その役割をまとめる。

【０１１４】ブロック番号管理テーブル８０１はコンパ
イラ１０２の作業領域に生成され、コンパイル処理が終
了した時点で廃棄される。この表にはコンパイラ１０２
の構文解析手段１０４において、ブロック番号、ブロッ
ク内変数表のポインタ等が記録される。またこの表構造
を参照して実行時ブロック管理テーブル５０１のブロッ
ク間の連鎖生成が行なわれる。

【０１１５】実行時ブロック管理テーブル５０１は、コ
ンパイラ１０２の作業領域に生成された後、オブジェク
トファイル作成手段１０９によって中間言語オブジェク
ト１１０のファイルに出力される。さらに、中間言語オ
ブジェクト１１０が中間言語インタープリタにロードさ
れた後、中間言語インタープリタ内でも参照される。こ
の表にはコンパイラ１０２の構文解析手段１０４により
ブロック呼び出しの際の引数リストの解析結果、ブロッ
ク間の従属関係が記録される。

【０１１６】共有資源管理テーブル１００１はコンパイ
ラ１０２の作業領域に作成された後、オブジェクトファ
イル作成手段１０９によって中間言語オブジェクト１１
０のファイルに出力される。この表は中間言語オブジェ
クト１１０が中間言語インタープリタにロードされた
後、中間言語インタープリタ内でも参照される。中間言
語インタープリタ中ではモニタ型手続き処理にあたり参
照される。

【０１１７】実行時プロセッサ管理テーブル１７０１
は、インタープリタ作業領域に実行時に生成される。こ
の表は並列実行にあたり使用可能な（｛コネクト・ロッ
ク｝できた）プロセッサの管理および、並列実行した結
果のスケジュール管理に使用される。

【０１１８】上記表構造に加え、本実施例ではコンパイ
ラ１０２において変数名、ブロック名等の識別子の管理
に名前表およびブロック内変数表を用いた。

【０１１９】４−２．本実施例の展開 ４−２−１．排他制御と共有資源管理 上記の説明において、共有資源への排他制御、同期機構
としてモニタ型を挙げて説明した。これは本実施例にお
いて実現容易なものとして使用した。しかし、本実施例
と同一の構成において直ちに周知のセマフォに対しても
適用できる。このためには、どのブロックの管理下に有
るセマフォにアクセスするかを本実施例の実行時ブロッ
ク管理テーブル５０１と同様のデータ構造で記録し、自
プロセッサ外のセマフォに関しては通信を伴ってリモー
トにアクセスする組み込み手続きを用意するだけで良
い。

【０１２０】周知の排他制御、同期機構はセマフォを用
いて置き換え可能な場合が多い。このことから本実施例
はモニタ型以外の共有変数実現方法にも応用可能である
と言うことができる。

【０１２１】また本実施例で示したモニタ型において、
バッファメモリ割り当てを取り去った構造を用いた場
合、あるデータ型に結び付けられた特定手続きによる同
期的な通信経路が中間言語インタープリタにより実現さ
れたと見なすことができる。従って本発明の中間言語イ
ンタープリタは、インタープリタとインタープリタの間
でFIFO等のメモリ構造を用い通信経路を実現した場合に
対しても実装することができる。この場合、共有変数を
持たず、通信によって並列実行手続き間のデータ授受を
おこなう仕様のプログラム言語のコンパイラであって
も、本実施例と同様な中間言語出力を行なうことで複数
のプロセッサに実装した中間言語インタープリタにおい
て実行可能であると言える。

【０１２２】４−２−２．中間言語インタープリタの実
装 上記実施例の示したものと等価な中間言語インタープリ
タは、複数プロセッサからなる処理系に実現されても良
い。例えば４つのプロセッサからなるコンピュータ上に
並列処理を実現するカーネルプログラムを実装し、この
カーネルプログラム上に中間言語インタープリタプログ
ラムを走らせることが考えられる。これを更に発展させ
ると、トポロジーの異なる別々のマルチプロセッサシス
テム上にそれぞれ本発明の中間言語インタープリタを実
装し、トポロジー混在環境で実行可能な並列プログラム
を記述する事ができる。

【０１２３】この方法を使用すれば、画像処理の高速処
理に有利なシストリックアレイプロセッサシステムと、
信号処理、高速フーリエ変換処理などの処理に有利なベ
クトルプロセッサシステムを結合したシステム上で記述
可能な高級言語を実現することができる。

【０１２４】従来のコンパイラの中で、例えばベクトル
プロセッサの使用を前提として開発されたコンパイラの
出力コードは、ベクトルプロセッサ上で実行される機械
語コードを発生する。このオブジェクトコードはターゲ
ットシステムに依存したコードである。この種のコンパ
イラの出力結果は、ハードウェアの仕様の変更に対して
は再コンパイルしないと最適コードとならない。例え
ば、スカラープロセッサのみのハードウェアを実行環境
としてコンパイルされたオブジェクトコードを運用して
いたコンピュータに新たにベクトルプロセッサを付加し
たとしても、ベクトルプロセッサをサポートするコンパ
イラによって再度コンパイルし、オブジェクトコードを
生成し直さないと実行速度の向上効果は得られない。

【０１２５】これに対し、本実施例で示したコンパイラ
は中間コードインタプリタにより実行されるコードを発
生する。また中間コードは実行時にプロセッサに動的に
スケジュールされる。この２つの特徴からコンパイル済
みのオブジェクトコードを運用しているシステムに対
し、中間コードインタープリタを実装したハードウェア
（回路基板等）を付加した場合、再度コンパイルを行な
い目的プログラムのオブジェクトコードを生成し直す手
順が不要である。中間コードインタープリタを実装した
ハードウェアが付加された時点から目的プログラムのオ
ブジェクトコードは、付加ハードウェアのプロセッサと
従来から運用していたプロセッサによるマルチプロセッ
サ系によって実行される。このことは、商用アプリケー
ションを販売し運用する段階で極めて有利である。なぜ
なら、商用アプリケーションのほとんどは、プログラム
著作権を保護するためソースコードを含めないオブジェ
クトコードのみの状態で使用者に販売されるためであ
る。本実施例のコンパイラによって開発されたオブジェ
クトコードであれば、使用者がハードウェア付加を行な
ってもアプリケーションソフトウェアのオブジェクトコ
ードを変更する必要が無い。これにより、保守の容易
さ、運用の簡便さの両面で優れるという効果が生じる。

【０１２６】

【発明の効果】本発明は、並列実行時に共有される変数
へのアクセスを排他制御する機構と、中間言語の命令語
によって記述されたオブジェクトコードを生成するコン
パイラと、前記コンパイラの出力した中間言語を実行す
るインタープリタと、前記インタープリタにより実現さ
れる並列実行の処理ブロック割り当てを動的に行なう機
構とによって構成されているため、並列処理系のハード
ウェアの構成が変わった場合でもこのコンパイラを用い
て開発されたオブジェクトコードを再コンパイルする事
無く並列処理を実行することが可能である。

【０１２７】言い替えるなら、使用者が処理速度改善の
ためアクセラレータ等の付加ハードウェアを追加した場
合でも、本発明による処理系を実装したパーソナルコン
ピュータ向けのアプリケーションプログラムについて
は、ハードウェア追加によるプログラムの変更を必要と
せずに追加したハードウェアによる処理速度の改善を享
受できる。

【図面の簡単な説明】

【図１】本発明の実施例として好適なマルチプロセッサ
処理装置と、そのコンパイラ処理系の構成図。

【図２】図１のコンパイラ処理系で開発したオブジェク
トコードを実行するマルチプロセッサ処理装置であるパ
ーソナルコンピュータの構成図。

【図３】モニタ型の説明図。

【図４】構文解析手段１０４の処理の流れ図。

【図５】実行時ブロック管理テーブルの説明図。

【図６】例として挙げたプログラムの説明図。

【図７】例として挙げたプログラムのブロックの従属関
係の説明図。

【図８】ブロック管理テーブルの説明図。

【図９】ブロック間の従属関係を取り出す処理の流れ
図。

【図１０】共有資源管理テーブルの説明図。

【図１１】中間言語の機能の説明図。

【図１２】中間言語発生の処理の説明図。

【図１３】中間言語発生手順の説明図。

【図１４】中間言語処理時のスタック状態の説明図。

【図１５】中間言語インタープリタを形成するプロセス
間の通信に使用するデータ構造の説明図。

【図１６】中間言語インタープリタの処理の流れ図。

【図１７】中間言語インタープリタを実現するプロセス
の構成図。

【図１８】cobegin文、sync文処理の説明図。

【図１９】共有資源アクセス処理の実行時の流れ図。

【図２０】表構造の説明図。

【符号の説明】

１０１…ソースコード １０２…コンパイラ １０３…字句解析手段 １０４…構文解析手段 １０５…共有メモリ資源検出手段 １０６…並列実行検出手段 １０７…コード生成手段 １０８…コード生成手段 １０９…オブジェクトファイル作成手段 １１０…中間言語オブジェクト １１１…中間言語インタープリタ １１２…中間言語インタープリタ １１３…プロセッサ １１５…通信経路 ２００…パーソナルコンピュータ ２０１…付加ハードウェア ２０２…システムバス ２０３…オペレーティングシステム ３００…説明のためのソースコード ５０１…実行時ブロック管理テーブル ５０３…ブロック番号 ５０４…下位ブロックへの連鎖アドレス ５０７…引数リストへの連鎖アドレス ５０８…連鎖 ５０９…連鎖 ８０１…ブロック番号管理テーブル ８０２…ブロック番号 ８０３…ブロックレベル ８０４…テーブルエントリ １００１…共有資源管理テーブル １００２…資源番号 １００３…共有変数名 １００４…共有資源が宣言されたブロック番号 １００６…モニタ型手続きの実行コード １２０３…引数リスト １４０１…スタック使用の履歴 １５０１…データ構造 １５０２…コマンド １５０３…プロセッサ番号 １５０４…プロセス番号 １５０６…データ長 １５０７…オブジェクトコード １５０８…スタック初期化データ １５０９…テーブル初期化データ １５１１…状態コード １７０１…実行時プロセッサ管理テーブル １７０２…プロセス １７０６…コード領域 １７０７…スタック領域 １７０８…命令ポインタ １７０９…スタックポインタ １８０１…命令語解析処理 １８０３…スケジューラ １８０４…述語展開処理 １８０８…他の中間言語インタープリタ

Claims (1)

【特許請求の範囲】
1. 【請求項１】 少なくとも共有メモリ資源割り当てに対
   してアクセスを発生するプログラム記述の解析を行ない
   排他制御を指示する手段と、並列処理可能なプログラム
   処理単位に対する記述の解析を行ないプロセッサ割り当
   てを行なう手段とを有するコンパイル機構と、前記コン
   パイル機構の出力した中間言語を実行するインタープリ
   ット機構と、前記インタープリット機構により実現され
   る並列実行の処理ブロック割り当てを動的に行なう機構
   とによって構成されることを特徴とするマルチプロセッ
   サ処理装置。