JPS63503176A - コンピュータにおける制御フローに関する改良 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 コンピュータにおける制御フローに関する改良本発明は、少なくとも２つのプロ セッサを備えたコンピュータにおける制御フローの改良に関する。

１つのプロセッサを設けたコンピュータの場合、プログラム内の制御フローは、 通常プロセッサに送られる単一の命令ストリーム内にデータ操作命令を点在させ た制御フロー命令を実行するプロセッサより得られる。今日、演算速度を速くす るために、１つ以上のプロセッサを備えたコンピュータが知られている。そのう ちの１つは、（１）複数の独立した処理要素と（２）処理要素同士を調整してそ れ自体が制御と調整機能の実行に使用されるプロセッサを備えるコントローラと を設けた演算プロセッサより成る。かかるコンピュータは、米国特許第４１０１ ９６０号と例えば「個別データフローアーキテクチャ：アーキテクチャ　コンセ プトＪ　（ＩＥＥＥコンピュータのトランザクション、１９８３年５月）中でレ キュアとマクグローの両氏によって開示されている通りである。前記コンピュー タにおいて、制御フロー命令と演算プロセッサに対する命令とを共に含むプログ ラムブロックは、まずコントローラのプロセッサに送られてそこで制御フロー命 令はコントローラにより抜き出されて実行され、その後データ処理命令が演算プ ロセッサへ送られる。

機械語コードやアセンブリ言語よりも従来の高水準言語でコンピュータをプログ ラムできることが望ましい、しかしながら、多くのマルチプロセッサコンピュー タは標準的な高水準言語ではプログラムネ可能である。レキュアとマクグロー両 氏による論文は高水準言語を編集する問題について論じてイル、シカシナがら、 両氏により提案された！類のコンピュータアーキテクチャは、その上で効率的に 実行可能なプログラムのタイプが制限されている。

それ故、本発明の目的は、高水準言語で書かれたプログラムを１つ以上のプロセ ッサを有するコンピュータで使用できる方法を改良することである。

従って、本発明は、 （１）　演算プロセッサ、 （２１前記波Ｋ　７’ロセツサに接続したコントローラ、（３）　制御フロー命 令と演算命令とが互いに混ざり合ったソースコードの表示を受けとる手段、 （４）　前記ソースコードの表示から （ａｌ　何れの命令ブロックも５ＥＳＥブロツクであるような一連のブロックか ら成る演算プロセッサプログラムと、（ｂｌｓＥｓＥブロックが演算プロセッサ により実行される順序を制御するための制御フロープログラムと、を生成するた めのコンパイル機、 ＋５１　（ｉ　）前記プログラムをコントローラ内へ入力するためのプログラム 入力手段、 （ｉｉ　）制御フロープログラムを実行するための制御フロープロセンサ、およ び （ｉｉｉ　）制御フロープロセッサの制御下に前記５ＥＳＥブロツクを演算プロ セッサへ移送するための手段、とから成るコントローラ、 とから構成されるコンピュータを提供するものである。

本発明をもう一つの面から見ると、少なくとも２つのプロセンサを有するコンピ ュータを操作するプロセスは、＋１１　制御フロー命令と演算命令とが互いに混 ざり合ったソースコードの表示を２つの分離したプログラム、すなわち、ｆａｌ 　命令ブロックが５ＥＳＥブロツクであるような演算プログラム、および （ｂ）ＳＥＳＥ命令が演算プロセッサにより実行される順序を制御するための制 御フロープログラムに変換し、− （２）　制御フロープロセッサ上で制御フロープログラムを実行し、 （３）演算プロセッサで演算プログラムを実行し、（４）制御フロープロセッサ 内で実行されるプログラムに従って演算プログラムのフローを変更する、ことよ り構成される。

前記の“プロセッサ”という用語は、特定の処理操作を遂行するために使用され る構造全体を指すために、コンピュータの設計と構築の当業者によって使用され ている。該用語は、また構造全体で特定の処理ステップを遂行する装置を指すた めにも使用される。かくして、例えば“アレイプロセッサ”とはデータ配列の処 理を遂行する構造ということになる。アレイプロセッサは、複数の独立した処理 要素より構成することができる。それぞれの処理要素は、メモリと単一の論理演 算回路（Ａ　Ｌ　Ｕ）を有する“プロセッサ”とから成る。しかしながら、当業 者は文脈より“プロセッサ“という用語が所定の場合に使用される時の意味で容 易に理解するであろう。

演算プロセッサは、２進数で演算を実行することにより数値問題に対する解を与 えることができる。また、同様にして、テキスト操作の一部としてアルファベッ ト文字のコードを表わす２進数で演算を行うこともできる。

”　５ＥＳＥ”ブロックは、コンパイラの設計に携わっているものには周知の用 語である０本願中に使用する“５ＥＳＥ”ブロックは、１つの入口点と１つの出 口点とを有し、該ブロック内に制御のシーケンシャルフローを有している。すな わち、ブロック内には、ループもジャンプもサブルーチンの呼出しも存在しない 。

高水準言語で提示されるソースプログラムは、種々の形で生成させることができ る。一般的にいって、高水準言語内で使用される記号を表わす英数字は、一定の 形の記憶媒体、例えば磁気ディスク上に格納されたコードに変換されることにな る。その後、このコードは記憶媒体より抽出しコンパイルコンパイル機は、コン パイル処理の高速化のために無視し得るものであれば専用機となりうる。しかし ながら、一般にコンパイル機の機能は、コンパイラプログラムの制御下に汎用コ ンピュータによって与えられることになる。コンパイラの設計法に関しては、今 日、広範な文献が存在し、所定の高水準言語のためのコンパイラ、例えば字句解 析機、構文解析機、コード生成機の如きものを設計するための通常のエレメント がよく知られている。

本発明で使用するためのコンパイル機の特に望ましい構成は、以下の特徴を備え ている。

（１１コンパイル機は、高水準言語で表わされたソースプログラムを入力と、し て受取る。

（２）　前記ソースプログラムは、字句、構文および意味を解析されて、標準技 法を用いたソースプログラムを表わす中間的な形がつくりだされる。

（３）前記中間の形は一般に“オプティマイ：４ｙ（最適化機）”として知られ るものに移送され、そこで標準技法を用いてさらに“ペイシックブロック（基本 ブロック）”が検出される。これらの基本ブロックは、次いで単一人口、単一出 口（Ｓ　Ｅ　Ｓ　Ｅ）ブロックに変形される。制御フロー命令は、基本ブロック から５ＥＳＥブロツクへ変形される中で識別される。

（４１３ＥＳＦ、ブロックは、コード生成機へ移送され、演算プロセッサプログ ラムを生成し出力する。

（５）制御フロー命令がコード生成機に移送され、制御フロープログラムを生成 し出力する。

コンパイル機により性成された２つの出力プログラムは、制御フロープロセンサ と演算プロセッサ内で直接実行できるようなものでよい、しかしながら、何れか 所定のプロセッサでも実行できない汎用プログラムコードではあるが、任意の所 定のプロセッサ用のコードに容易に変換できるような中間コードを生成させるこ とが好ましいかもしれない、このことによって、単一のコンパイル機を種々の異 なるプロセッサに対して使用することが可能になる。

コンパイラの設計と使用用語についての詳細は、「コンパイラ段重の原理」アル フレンド　ヴイ、エイホ、ジエフリーディ、ウルマン、アディソンーウエズリイ 著、１９７７年と、「ディジタルコンピュータ用のコンパイラ構造」ディピント 　グリース、ウィリー著、１９７１年および「コンパイラの理解と書き方」リチ ャード　ボーナンド、マクミラン著、１９７９年を参照されたい、基本ブロック を論じたものが、以上の本文中箱４１２−４１３頁（エイホ、ウルマン）、第２ ５６頁（グリース）、および第１６０頁（ボーナフト）中に見出される。エイホ とウルマンは、第４１２−４１３ｉテ基本ブロック検出のためのアルゴリズムを 規定している。

２つの出力プログラムは、コンパイル機からコントローラへ直接供給することが できる。しかしながら、出力プログラムをコントローラへ供給する前に、この出 力プログラムを一定の形式の中間記憶装置に記憶することが、一般的に望ましい であろう。

ソースプログラムを供給するための手段とコンパイル機とは、コントローラと演 算プロセッサに物理的に隣接していることが一般的にいって好都合であるが、そ れらが適当な通信リンクにより接続される限り、幅広（隔たった位置に配置する ことも可能である。

先に示した如く、高水準言語プログラムは、制御フロープロセッサと演算プロセ ッサとによって直接実行可能な別個の機械語コードプログラムへコンパイルして もよい、しかしながら、コンバイリングにより得られる別個のプログラムは、中 間コードもしくはアセンブリ言語の形をとっても差支えない、それぞれのプログ ラムは、その後順次機械語コードへ変換され、プロセッサ上で適当なアセンブラ によって実行される。アセンブラの設定は、当業者のよく知るところである。

制御フロープロセッサのためにコンパイルされるプログラムがアセンブラプログ ラムである場合には、該プログラムは次のフォーマットの命令を含むことができ る。すなわち、個々の命令を一義的に識別するための命令ラベル、５ＥＳＥブロ ツクを演算プロセッサへ移送する命令形式の識別子、演算プロセッサへ移送され る５ＥＳＥブロックを識別するプロンク識別子フィールド、および制御フロープ ロセッサで実行される少なくとも一つの連続命令の命令ラベルである。

命令を含むことになろう、かくして、例えば、プログラムは以下のフォーマット を有する命令によって終了させることができる。すなわち、命令を一義的にｉΔ 別するための命令ラベルと、制御フロープログラムの実行を終了させる命令形式 の識別子とである。

演算プロセッサは、演算プロセッサにより実行されるプログラム中のテスト条件 が満たされたかどうかを制御フロープロセッサに表示するための手段を備えてい ることが望ましい。

このような場合、５ＥＳＥブロツクが演算プロセッサに移送されることにより生 じる命令形式の識別子を含む制御フロープロセッサのアセンブリプログラム中の 命令は、２つの相異なる命令ラベルに従う、これらのうちの一つは、５ＥＳＥブ ロツク内のテスト条件が満たされた場合に、制御フロープロセッサにより実行さ れる次の命令を識別するための命令ラベルである。他方は、テスト条件が満たさ れていない場合に、制御フロープロセッサにより実行される異なる命令の命令ラ ベルである。

制御フロープロセッサにより実行される機械語コードプログラムは、制御フロー プログラムを格納するメモリのアドレス置換した命令形式の識別子に従うラベル を有することになろう、前記識別子は、命令ラベルの代りに命令を識別すること になろう。

種々の５ＥＳＥ命令ブロツクのうちの何れが演算プロセッサに移送されるべきか を識別するブロックムロ割子フィールドは、アセンブル中にメモリアドレスに変 換されるラベルで差支えない、５ＥＳＥブロツクは、制御フロープログラムの実 行を開始する前に、独立のアドレス可能なメモリロケーションを有する命令メモ リ内に格納し、５ＥＳＥブロツク識別子がブロックの長さもしくはその最終アド レスと共に５ＥＳＥブロツクの格納が開始されるメモリロケーションのアドレス となることが望ましい。

コンパイル動作の示範として、高水準言語で表わしたプログラムの一例が仮想的 スタックに基づいた機械のための“擬似”アセンブラ言語で同一プログラムに変 換されることになろう、基本ブロックおよび次の５ＢＳＥブロツクおよび制御フ ロー命令は、擬似機械言語プログラム中で識別され、これは出願人の係属出願（ ケース６１４７／６３２６）中に開示した形式のコンピュータによる使用に通し た形式のプログラム表示に変換されることになろう。

以下に説明する簡単なプログラムは、制御フロープロセッサと単一の演算プロセ ッサとから成るコンピュータに使用することができよう、従来、簡単なデモンス トレーションプログラムは、基本原理を明確に提示して、複数の処理要素と共に 並行処理を行うコンピュータの動作の説明を試みる場合に必要となる複雑な説明 の要求を回避するために用いられてきた。デモンストレーションプログラムは、 簡単でありで、サブルーチンや手続きを呼出す必要がない、しかしながら、制御 フロープログラム中で、サブルーチンを活用することができ、このことは如何に して行うことができるかについての注記は、以下の本文中に若干組込んである。

ソースプログラム用の高水準言語表記法としてフォートラン（ＦＯＲＴＲＡＮ） を選択することは自由である。擬似機械言語で等測的なプログラムへ変換可能な プログラムを書き表わす際に使用できる高水準言語であれば、何れも選択するこ とができるであろう。

高水準言語フォートランでプログラム例を以下に示す、フォートランの形式と意 味は、ＡＮＳ　ＩＸ３．９−１９７８の「アメリカ規格プログラミング言語フォ ートラン」中に明らかにされている。このプログラム例は、フィボナフチ数列中 の最初の１０語と開始値１．１との和を演算する。

ＰＲＯＧＲＡＭ　ＦＩＢＯＮＡ ＣＰＲＯＧＲＡＭ　ＴＯＣＡＬＣＵＬＡＴＥ　Ｔ）ＩＥ　ＳＵＭ　ＯＦ　ＴＨＥ 　ＦＩＲＳＴ　ＴＥＮＦＩＢＯＮＡＣＣＩ　ＮＬＩＭＢＥＲ３−ＣＴＨＥ　ＲＥ ＳＵＬＴ　Ｉｓ　）ＩＥＬＤ　ＩＮ　ＶＡＲＩＡＢＬＥ　ＡＮＳＷＥＲＩＮＴＥ ＧＥＲＮ１．Ｎ２．ＮＥ讐、　ＳＵＭ、　ＡＮＳＷＥＩ？１Ｎ２＝ １ＳＵ　＝　Ｎ１＋　Ｎ２ Ｄｏ　１０１　＝３．１Ｏ ＮＥＷ　＝　Ｎ１＋　Ｎ２ Ｎ１　＝Ｎ２ Ｎ２　＝ＮＥＷ ＳＩＩＭ　＝　ＳＵＭ　十ＮＥＷ １０　Ｃ０ＮＴＩＮ［ｌＥ ＡＮＳＷＥＲ二ＳＵＭ ＮＤ 同じプログラムの擬似アセンブラ言語表示を以下に示す。

擬似アセンブラ言語は、コンパイラがソースプログラムの字句、構文および意味 を解析した結果生成させることができる。

以上の解析を実行するための技法はよく知られており、コンパイラに関するどの 参考書にも見出すことができる。生成した擬似アセンブラ言語は、仮想的スタッ クをベースとした機械用のものである。スタックをベース（もしくはゼロアドレ ス）とした機械を徹底的に論じたものとしては、「コンピュータアーキテクチャ 序説」、サイエンス　リサーチ　アソシ１−ツ７１　１９７５年、第７章、「ス タックコンピュータ」。

ウィリアム　エム、マツキーマン著、第２８１．−３１７頁を参照されたい。擬 似アセンブラ命令の右側の注記は命令の使用法を説明したものである。

基本ブロックを検出およびマーキングした前記リストの擬似アセンブラ言語を以 下に示す、この基本ブロックの検出は、「コンパイラ設計の原理」アルフレンド 　ヴイ、エイホ、ジェフリー　ディー、ウルマン、アディソンーウエズリー著。

１９７７年、第４１２−４１３頁に述べられた用語法と仮想的スタックに基づい た機械と一致するように修正したアルゴリズムを使用して行う。このアルゴリズ ムは以下の通りである。

入カニゼロアドレス命令のシーケンス。

出カニそれぞれのゼロアドレス命令を正確に１ブロツク中に有する基本ブロック のリスト。

方法＝１．コンパイラは、まず基本ブロックの最初の命令群である先導部の組を 決定する。使用される規則は以下の通りである。

ｉ）最初の命令は先導部である。

ｉｉ）条件付きもしくは無条件分岐命令の目標であるような命令は何れも先導部 である。

ｉｉｉ　）直ちに条件付き分岐命令に従う命令は何れも先導部である。

２、それぞれの先導部毎にその基本ブロックを構成する。前記基本ブロックは、 先導部および次の先導部もしくはプログラム終了、但しこれら次の先導部とプロ グラム終了は含まない、に至る全命令より構成される。１ブロツク内に配置され ない命令は、何れも決して実行されることはあり得ないから、必要であれば除去 してもよい。

前記アルゴリズムは、ステップ１内に追加的なサブステップを含めることによっ て、サブルーチンを処理すべく修正することができる。

ｉｖ）サブルーチン呼出し命令の次に来る命令は先導部である。

全アルゴリズムは、独立してそれぞれのサブルーチンに応用することができる。

基本ブロックをマーキングした擬似コードＰＵＳＨ１規則１　（ｉ）による先導 部ＰＯＰ　ＮＩ ＰＵＳＨＩ ＰＯＰ　Ｎ２ ＰＵＳＨＮ２ ＰＵＳＨＮＩ ＤＤ ＰＯＰ　ＳｔＪＭ　基本ブロック磁Ｉ ＰＵＳＨ１０ ＰＯＰ　Ｉ？Ｅ ＰＵＳＨＩ ＰＯＰ　Ｉ？５ ＰＵＳＨ３ ＵＢＲ Ｌｌ：ＰＵＳＨＩ　規則１（ｉｉ）による先導部ＰＵＳＨＩ？Ｓ ＤＤ ＰＯＰ　Ｉ　基本ブロック１１ｈ２ ＰＵＳＨＩ ＰＵＳＨＩ？Ｅ ５ＴＬＴ ＢＲＣＬ２ ＰＵＳＨＮ２　規則１（ｉｉｉ）による先導部ＰＵＳＨＮＩ ＤＤ ＰＯＰ　ＮＥＷ ＰＬＩＳＨＮ２ ＰＯＰ　ＮＩ ＰＵＳＩ　ＮＦ、Ｗ　基本ブロック階３ＰＯＰ　Ｎ２ ＰＵＳＨＮＥＷ ＰＵＳＨＳｔＪＭ ＤＤ ＰＯＰ　ＳＵＭ Ｌ２：ＰＵＳＨＳＵＭ　基本ブロック隘４規則１（ｉｉ）による先導部 Ｐ　ＯＰ　ＡＮＳＷＥＲ 前記列挙した基本ブロックより派生する５ＥＳＥブロツクを“５ＥＳＥ　ＢＬＯ ＣＫＳゝの見出しの下に以下に列挙する。基本ブロックより派生する制御フロー 命令は“制御フロー命令”の見出しの下に以下に列挙する。

コントローラと複数の処理要素とから成るマルチプロセッサコンピュータは、制 御フローと演算プログラムを作成する手続きを説明した後、以下に説明する。処 理要素は、それらが実行中のプログラム内のテスト条件が全ての処理要素により 満たされるかどうかに応じて、基準値をコントローラへ通信することができる。

基準値は、処理要素による投票の結果と見なすことができる。投票は、テスト条 件が全ての処理要素により満たされていれば真であり、満たされていなければ誤 すである。コンパイルプロセスの説明において、以下に述べる投票ごと投票誤り の命令を使用することは、マルチプロセッサコンピュータの解説中に示されてい る通りである。

投票真と投票誤りの命令の使用法は、以下の詳細な説明に示されているが、その 場合演算プロセッサにより生成される信号（投票信号）が、コントローラへ戻さ れプログラムの未決定フローを決定するために使用される。この信号は、特定の 実施例でのプログラムフローが全ての処理要素について同一の信号（全部一致投 票）を与えるかどうかにかかっているため、“投票”信号として説明される。

制御フロー命令は、次のフォーマットを有する。

ＬＩ　ＢＲＤ（ｉｄ）→Ｌ２１Ｌ３ 但し、Ｌｌは命令ラベル。

ｉｄは５ＥＳＥブロツク識別子フイールド。

Ｌ２は投票誤り命令ラベルフィールド。

Ｌ３は投票真命令ラベルフィールドである。

もし投票真命令ラベルフィールドと先行するバーが抜けていれば、投票真命令ラ ベルフィールドが投票誤り命令ラベルフィールドと同一であると想定される。投 票真命令ラベルフィールドと投票誤り命令ラベルフィールドとは、他の定義され た命令ラベルとの照会を行う、その他、実行されるべき第１の制御フロー命令の ラベルは“大ロー”後に見出され、制御フローの実行は“出口”に続く命令ラベ ルで終了する。

基本ブロックのリストから５ＥＳＥブロツクおよび制御フロー命令を引き出すた めに、コンパイラにより使用されるアルゴリズムは、次の通りである。

入カニそれぞれのゼロアドレスの命令を正確に１ブロツク内に有する基本ブロッ クのリスト。

出カニ　５ＥＳＥブロツクの実行順序で決定する単一人口単一出口（ＳＥＳＥ） のブロックのリストと制御フロー命令リスト。

方法；１）唯一つのブロック識別子を各基本ブロックへ付与し、 ２）各基本ブロックについてブロック開始点に“ブロックスタート”とブロック 識別子とをマーキングしてブロックの終りに１プロツ乞エンド”とブロック識別 子とをマーキングし、 ３）各基本ブロックにつき ｉ）一義的命令ラベルと、 ｉｉ）基本ブロックのブロック識別子にセットされた５ＥＳＥブロツク識別子フ イールドと、ｉｉｉ　）まだ決定されていない投票誤り命令ラベルフィールドと 、投票真命令ラベルフィールドと、を有する一つの制御フロー命令を生成させ、 ４）制御フロープログラム開始命令、例えば“入口−”後に、第１基本ブロック の基本ブロック識別子にセットされた５ＥＳＥブロツク識別子を有する制御フロ ー命令の命令ラベルに対して照会することによって、制御フロー人口点を生成さ せ、 ５）追加的な一義的命令ラベルを作り出すことによって制御フロー出口点を生成 させ、それを制御フロープログラム終了命令、例えば“出口”によって追跡し、 ６）前記ステップ３において生成した各制御フロー命令につき ｉ）現在制御フロー命令中の５ＥＳＥブロツク識別子フイールドにより照会され た基本ブロック中の最終命令を識別し、 もしその命令が条件付分岐命令ＢＲＣであればステップｖｉへ移行し、 もし命令が無条件分岐命令ＢＲであればステップＶへ移行し、 その他の場合にはステップ１１へ移行し、ｉｉ）もし現在制御フロー命令中の５ ＥＳＥブロツク識別子フイールドにより照会される基本ブロックが、基本ブロッ クの入力リスト中の最後の基本ブロックであれば、ステップｉｖへ移行し、その 他の場合にはステップｊＩｉへ移行し、ｉｉｉ　）次の基本ブロックの基本ブロ ック識別子にセットされた５ＥＳＥブロック識別子フイールドにより、制御フロ ー命令を見出しく次の基本ブロックは現在基本ブロックのすぐ次のプロ７りであ り、この現在基本ブロックは、現在制御フロー命令中の５ＥＳＥブロツク識別子 によって照会されるブロックであり）、現在制御フロー命令の投票誤り命令ラベ ルフィールド中に見出された制御フロー命令の命令ラベルを記入し、 ステップｖｉへ移行し、 ｉｖ）現在制御フロー命令の投票誤り命令ラベルフィールド内の制御フロー出口 点の命令ラベルを記入し、 ステップｖｉへ移行し、 ■）分岐命令の転送ラベルを格納する基本プロ、りの基本ブロック識別子にセッ トされた５ＥＳＥブロツク識別子フイールドにより制御フロー命令を見出し、現 在制御フロー命令の投票誤り命令ラベルフィールド中に見出された制御フロー命 令の命令ラベルを記入し、 ステップｖｉへ移行し、 ｖｉ）条件付分岐命令前で、しかも先行するテスト命令後に、“投票”命令を加 え、分岐命令の転送ラベルを格納する基本ブロックの基本ブロック識別子にセッ トされた５ＥＳＥブロック識別子フイールドにより制御フロー命令を見出し、現 在制御フロー命令の投票真命令ラベルフィールド中に見出された制御フロー命令 の命令ラベルを記入し、ステップｉｉへ移行し、 ｖｉ）前記ステップ３で生成した次の制御フロー命令についてはステップｉに復 帰し、 ７）各基本ブロックにつき全ラベルと全ての条件付および無条件分岐命令を削除 する。

前記プロセスは、所望に応じてサブルーチン呼出しおよびリターンを処理するた めに容易に拡張することができる。

ＰＵＳＨ１ ＰＯＰ　Ｎ２ Ｆ’ＵＳＨＮ２ ＰＵＳＨＮＩ ＤＤ ＰＯＰ　ＳＵＭ ＰＵＳＨ１０ ＵＢＲ ＰＵＳＨ１７５ ＰＵＳＨＩ　？Ｅ ｂｌｏｃｋ　ｅｎｄ　（ｃ２） ｂｌｏｃｋ　５ｔａｒｔ　（ｃＪ） ＰＵＳＨＮ２ ＰＵＳＨＮｌ ＤＤ ＰＯＰ　ＮＥＷ ＰＵＳＨＮ２ ＰＯＰ　ＮＩ ＰＵＳＨＮＥＷ ＰＯＰ　Ｎ２ ＰＵＳＨＮＥＷ ＰＵＳＨＳＵＭ ＤＤ ＰＯＰ　ＳＵＭ ｂｌｏｃｋ　ｅｎｄ　（ｃＪ） ｂｌｏｃｋ　５ｔａｒｔ　（ｃＪ） ＰＵＳＨＳＵＭ Ｐ　ＯＰ　ＡＮＳＷＥＩ？ ｂｌｏｃｋ　ｅｎｄ　（ｃＪ） ＬＩ　ＢＲＤ　（ｃ　１）　−Ｌ２ Ｌ２　ＢＲＤ（ｃ２）　−Ｌ３　ｌ　Ｌ４Ｌ３　ＢＲＤ　（ｃＪ）　−Ｌ２ Ｌ４　ＢＲＤ（ｃＪ）　Ｌ５ Ｌ５　出口 制御フロープログラムと演算命令プログラムは、（必要に応じ）各プロセッサに より使用される機械語コードに変換された後、制御フローメモリと命令メモリ内 に便宜上格納し、そこからそれらを各プロセッサにディスパッチングすることが できる。

前記の制御フローメモリと演算命令メモリとは、制御フロープロセッサと演算プ ロセッサ用の命令の個別のシーケンスを格納するメモリである。それらは、制御 フロー命令と演算命令とを共に格納する命令のブロックから取り除いた制御フロ ー命令を一時的に格納するプロセッサ内のレジスタと区別される。

前記の本発明の説明は、一つの制御フロープロセッサと１つの演算処理要素とか ら成るシステムへの応用について行った。しかしながら、本発明は、複数の処理 要素から成る演算プロセッサにおいて、並行演算を行うシステムに適用した場合 、特に有利である。ＳＩＭＤもしくはロック−ステップモードで動作する複数の 独立した処理要素から成るコンピュータは、周知のところである。かかるコンピ ュータシステムは、例えばストーン外部の「コンピュータアーキテクチャ序説。

ニスアールエイ　リサーチ　アソシェイッ社、１９７５年、第３２７〜３５４頁 に説明されている通りである。

本発明は、出願人の係属出願（ケース６１４７／６３２６）中に開示したコンピ ュータを使用する場合に、特に好適である。かかるコンピュータと共に本発明の 実施につき図面を参照して説明する。

第１図は、ホストコンピュータがコントローラに接続され、コント、ローラは複 数の処理要素に接続された本発明のマルチプロセッサコンピュータの線図、 第２図は、第１図に示すものの変形例であって３つの処理要素のみを選択的に示 した線図、そして第３図は、コントローラの線図である。

第１図において、ホストコンピュータＡは、コントローラＢに接続され、コント ローラＢはＣで表示した複数の処理要素に接続される。ホストコンピュータは、 システム全体の操作と外部との通信に関与する。ホストコンピュータＡは、ホス トの操作を制御するプロセッサＤを備え、ディスクファイルＥから導入されたコ ンパイラプログラムによってコンパイラとして動作するように計画することがで きる。ディスクファイルＦからのコンパイラソースコードとしての動作が２つの 別個のプログラムに変換された場合、演算プログラムと制御フロープログラムは 、その後ディスクファイルＧおよびＨに格納される。マルチプロセッサコンピュ ータの動作に際して、これらのプログラムはディスクファイルからホストコンピ ュータＡを介してコントローラＢ内のメモリに送られる。

コンパイルプロセスは、第１図に関して前述した通りである。さらに、コンピュ ータの操作を第２図および第３図について説明する。

コンピュータは、一般的に、所定の長さの２進桁（ビット）の群（ワード）によ って動作する。一つの命令は、幾つかのワードを採用することにより、完全な一 つの命令のディスパンチングがメモリ内の個々のアドレスに格納された幾つかの ワードを連続的にディスパンチングすることを伴う。一つの命令のディスパンチ ングに関する説明においては、個々のワードのディスパンチングについて述べる ことであり、個々のワードは全命令または命令の一部を含むことがある。

第２図は、ホスト通信バス３により、ホストコンピュータ２　（第１図のＡに相 当する）に接続されたＳＩＭＤコンピコンピュータ１１図の要素Ｂ、Ｃに相当す る）を示す。コントローラ４は、複数の処理要素６に接続され、わかり易いよう にそのうち３つだけを示しである。

命令は、演算命令バス５により処理要素に発することができる。処理要素は、コ ントローラに接続された投票信号線により制御のフローに影響を及ぼすことがで きる。

第３図において、制御フロープロセッサ８は、バス１０に沿って制御フローメモ リ９から制御フローに関する命令を取出す。メモリ９は、コントローラ内のメモ リであり、このメモリには第１図に関して説明したように（バス３により）、制 御フロープログラムがホストコンピュータから移送される。

制御フロープロセッサ８は、演算命令のブロックを選択して処理要素により実行 させるが、この選択は制御フロー命令に従って行われる。命令転送手段１１は、 制御フロープロセッサによりバス１２に沿ってアドレス情報が提供される。制御 信号は、信号線１３により制御フロープロセッサ８に送り戻すことができる。命 令転送手段１１は、命令メモリ１４に対しバス１５により個々の演算命令のアド レスを供給する。命令メモリ１４は、コンパイラにより作成されバス３によりコ ントローラへ送られる演算プログラムを格納するメモリである。

演算命令は、演算命令バス５を介して処理要素へ送られる。

命令転送手段１１は、演算命令アドレスのシーケンスを発生させることによって 、命令ブロック全体をシーケンシャルに処理要素へ発する。同報通信手段１６は 、命令転送手段が次の演算命令アドレスに順次変化する時間を制御する。同報通 信手段１６は、処理要素から一般的に１７で示した制御線に沿って、送られる共 通制御信号に応答し、これによって全ての処理要素がそれを受領する準備が整う まで、次の演算命令がディスパンチングされないようにする。制御線１８は、制 御信号を命令転送手段と同報通信手段との間で交換することを可能にする。

制御フロープロセッサは、制御フローメモリから制御フロー命令を取出す、制御 フロープログラムは、制御フロー命令ポインタにより制御フロープロセッサが従 う制御フロー命令の連係リストによって表示される。制御フロー命令は、処理要 素により実行される演算命令のブロックを識別することができる。かかるブロッ クは、命令メモリ内のそのアドレスとその長さくブロック内の演算命令の数）に より識別される。

制御フロープロセッサは、ブロック識別情報を命令転送手段へ送り、該手段はブ ロック内の最初の演算命令のアドレスで命令メモリにアドレスする。同報通信手 段が全ての処理要素につき、次の演算命令を受取る準備が整ったと判断すると、 命令転送手段はそれが命令メモリに供給しているアドレスをインクリメントする 。このことは、１つの命令ブロックが命令メモリ内の連続するロケーションに格 納されていることから、ブロック内の次の演算命令を選択する効果を育する。命 令転送手段は、同時にまた、未だディスパンチングされていない演算命令の数を 格納するレジスタをデクリメントするが、このレジスタはブロックの長さを初期 ロードしている。このレジスタがゼロ値を格納する場合には、ブロック全体がデ ィスパンチングされて、命令転送手段は制御フロープロセッサに終了の信号を送 る。

制御フロー命令の幾つかは、演算命令を照会しないものもあり、それらは制御フ ロープロセッサにより完全に処理される。サブルーチン呼出しとリターン操作は 、このように制御フロープロセッサ内のスタックを用いて処理される。

制御フロー命令は、２つの可能な連続命令を有することがあり、その場合にはそ の２つのうちの１つを選択する必要がある。制御フロープロセッサは、処理要素 から送信される投票信号の値に従って、２つの連続命令のうちの１つを選択する 。それぞれの処理要素は、１つのピント投票レジスタを有し、同しジスクを真値 または誤り値にセットすることができる。レジスタのセツティングは、コンパイ ル作業と関連して上述した投票命令によって実行される。投票信号は、これら全 ての投票信号の論理積であり、換言すれば、投票信号はもし全ての投票レジスタ が真でなければ誤りとなる。このような手段によって、データに依存した制御フ ローが達成される。

国際調査報告 ＡＮＮＥＸ　Ｔｏ　ｉ’ＨＥ　ＩＮＴＥＲＮＡＴＩＯＮＡＬ　５ＥＡＲＣＲＲＥ ＰＯＲＴ　ＯＮ

Claims (1)

1. 【特許請求の範囲】 １．（１）演算プロセッサ、 （２）前記演算プロセッサにリンクされたコントローラ、（３）制御フロー命令 と演算命令とが互いに混合したソースコードの表示を受け取るための手段、（４ ）前記ソースコードの表示から （ａ）どの命令ブロックもＳＥＳＥブロックであるような一連のブロックから成 る演算プロセッサ命令／データプログラムと、 （ｂ）ＳＥＳＥブロックが演算プロセッサにより実行される順序を制御する制御 フロープログラムとを生成させるためのコンパイル機、 （５）（ｉ）前記プログラムをコントローラ内に入力するためのプログラム入力 手段と、 （ｉｉ）制御フロープログラムを実行するための制御フロープロセッサと、 （ｉｉｉ）制御フロープロセッサの制御の下に演算プロセッサプログラムを演算 プロセッサへ移送するための手段と からなるコントローラ、 によって構成されるコンピュータ。 ２．コントローラは、演算プロセッサプログラムを格納する命令メモリと、制御 フロープログラムを格納するための制御フローメモリとを有し、前記両メモリが プログラム入力手段へリンクされる請求の範囲第１項記載のコンピュータ。 ３．演算プロセッサは、ＳＩＭＤモードで操作可能な複数の処理要素を備える請 求の範囲第１項または第２項記載のコンピュータ。 ４（１）制御フロー命令と演算命令とが互いに混合されたソースコードの表示を 、２つの別個のプログラムすなわち、 （ａ）命令ブロックがＳＥＳＥブロックであるような演算プログラムと、 （ｂ）ＳＥＳＥ命令ブロックが演算プロセッサにより実行される順序を制御する ための制御フロープログラムと に変換し、 （２）制御ッロープロセッサで制御フロープログラムを実行し、 （３）演算プロセッサで演算プログラムを実行し、（４）制御フロープロセッサ で実行されるプログラムに従って演算プログラム中のッローを変更することから 成る少なくとも２つのプロセッサを備えるコンピュータ操作方式。 ５．下記のフオーマットの命令、すなわち、個々の命令を一義的に識別するため の命令ラベルと、ＳＥＳＥ命令／データブロックを演算プロセッサへ移送する命 令形式の識別子と、 演算プロセッサへ移送されるＳＥＳＥブロックを識別するブロック識別子ッィー ルドと、 制御ッロープロセッサで実行されるべき少なくとも１つの連続命令の命令ラベル と、 から構成される制御フローアセンブラプログラムに対し、ソースコードの表示変 換を行うことからなる請求の範囲第４項記載のコンピュータ操作方法。 ６．制御フロープログラムは、命令を一義的に識別するための命令ラベルと、制 御ッロープログラムの実行を終了させる命令形式の識別子とからなるフオーマッ トを有する命令により終了される請求の範囲第５項記載の方法。 ７．演算プロセッサは、制御フロープロセッサに対して演算プロセッサにより実 行されるプログラム内のテスト条件が満たされているかどうかを表示するための 手段を備え、該手段がソースコードの表示を下記のフオーマットの命令、すなわ ち、 命令を一義的に識別するための命令ラベルと、ＳＥＳＥブロックを演算プロセッ サへ移送させるために生じる命令識別子と、 ＳＥＳＥブロックを演算プロセッサへ移送させるために、識別するブロック識別 子ッィールドと、ＳＥＳＥブロック内のテスト条件が満たされた場合に制御フロ ープロセッサにより実行される次の命令を識別するための命令ラベルと、 テスト条件が満たされない場合に制御フロープロセッサにより実行される異なる 命令の命令ラベルと、を有する制御フローアセンブラプログラムへ変換を行うこ とからなる請求の範囲第４項ないし第６項の何れかに記載の方法。 ８．まずソースコードの表示を基本ブロックのリストへ変換し、基本ブロックの リストをＳＥＳＥブロックのリストと制御ッロー命令のリストとに変換した後、 下記のステップ、すなわち、 １）唯一つのブロック識別子を各基本ブロックへ付与し、２）各基本ブロックに ついてブロック開始点に“ブロックスタート”とブロック識別子とをマーキング してブロックの終りに“ブロックエンド”とブロック識別子とをマーキングし、 ３）各基本ブロックにつき ｉ）一義的命令ラベルと、 ｉｉ）基本ブロックのブロック識別子にセットされたＳＥＳＥブロック識別子フ ィールドと、 ｉｉｉ）未だ決定されていない投票誤り命令ラベルッィールドと投票真命令ラベ ルフィールドと、を有する１つの制御フロー命令を生成させ、４）制御フロープ ログラム開始命令後に、第１基本ブロックの基本ブロック識別子にセットされた ＳＥＳＥブロック識別子を有する制御フロー命令の命令ラベルに対して照会する ことによって、制御フロー入口点を生成させ、５）追加的な一義的命令ラベルを 作り出すことによって制御フロー出口点を生成させ、それを制御フロープログラ ム終了命令によって追跡し、 ６）前記ステップ３において生成した各制御ッロー命令につき、 ｉ）現在制御ッロー命令中のＳＥＳＥブロック識別子ッィールドにより照会され た基本ブロック中の最終命令を識別し、 もしその命令が条件付分岐命令であれば、ステップｖｉへ移行し、 もし命令が無条件分岐命令であればステップｖへ移行し、 その他の場合にはステップｉｉへ移行し、ｉｉ）もし現在制御ッロー命令中のＳ ＥＳＥブロック識別子ッィールドにより照会される基本ブロックが、基本ブロッ クの入力リスト中の最後の基本ブロックであればステップｉｖへ移行し、 その他の場合にはステップｉｉｉへ移行し、ｌｉｉ）次の基本ブロックの基本ブ ロック識別子にセットされたＳＥＳＥブロック識別子フィールドにより制御フロ ー命令を見出し、現在制御フロー命令の投票誤り命令ラベルフィールド中に見出 された制御フロー命令の命令ラベルを記入し、 ステップｖｉｉへ移行し、 ｉｖ）現在制御フロー命令の投票誤り命令ラベルッィールド内の制御フロー出口 点の命令ラベルを記入し、ステップｖｉｉへ移行し、 ｖ）分岐命令の転送ラベルを格納する基本ブロックの基本ブロック識別子にセッ トされたＳＥＳＥブロック識別子ッィールドにより制御ッロー命令を見出し、現 在制御フロー命令の投票誤り命令ラベルフィールド中に見出された制御フロー命 令の命令ラベルを記入し、ステップｖｉｉへ移行し、 ｖｉ）条件付分岐命令前で、しかも先行するテスト命令後に、“投票”命令を加 え、分岐命令の転送ラベルを格納する基本ブロックの基本ブロック識別子にセッ トされたＳＥＳＥブロック識別子フィールドにより制御フロー命令を見出し、現 在制御フロー命令の投票真命令ラベルフィールド中に見出された制御フロー命令 の命令ラベルを記入し、 ステップｌｉへ移行し、 ｖｉｉ）前記ステップ３で生成した次の制御フロー命令についてはステップ１に 復帰し、 ７）各基本ブロックにつき全うベルと全ての条件付および無条件分岐命令を削除 する、 ことを実行することにより、ＳＥＳＥブロックの実行順序を決定し、これらのス テップを１つのコンピュータで実行して演算プログラムおよび制御フロープログ ラムを作成する請求の範囲第４項ないし第７項のいずれかに記載のコンピユータ 操作方法。