JP2786574B2

JP2786574B2 - コンピュータ・システムにおける順不同ロード動作の性能を改善する方法と装置

Info

Publication number: JP2786574B2
Application number: JP5080421A
Authority: JP
Inventors: マハムト・ケマル・エブチオウル; エリック・ポール・クロンスタット; マノジ・クマール
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1992-05-06
Filing date: 1993-04-07
Publication date: 1998-08-13
Anticipated expiration: 2013-08-13
Also published as: JPH06214799A; EP0568842A3; EP0568842A2; US5542075A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般にコンピュータ・
システムに関し、詳しくはディジタル・コンピュータ・
システムの効率及び速度を改善するための方法と装置に
関する。さらに詳しくは、本発明は、動作をより速くす
るためにコンピュータ・プログラム中での命令の順序を
並べ換えるための方法と装置に関する。

【０００２】

【従来の技術】速度は、コンピュータについて判断を下
す際の重要な基準である。当業界の一般的な長期的傾向
は、ますます効率的なより速いコンピュータを開発する
ことである。

【０００３】コンピュータの実行速度を増加させる１つ
の方法は、メモリ待ち時間を短縮することである。メモ
リ待ち時間とは、命令サイクルの開始時にメモリからオ
ペランドを要求してから、そのオペランドがプロセッサ
内の適切なレジスタに供給されるまでの、時間的遅延で
ある。プロセッサとＣＰＵが今日情報を処理できる速度
と効率が与えられているとすると、メモリ待ち時間のた
めに、メモリ要求を開始した後にプロセッサが遊休状態
になってから、要求されたデータがメモリから戻されて
実際に作業サイクルが開始できるまでに、比較的長時間
の遅延が生じる可能性がある。実際にはプロセッサは、
作業のためにオペランドまたは情報を待つのに、データ
処理に費やすよりも多くのプロセッサ時間を容易に費や
す可能性がある。

【０００４】理想的な状況は、オペランドとレジスタの
両方が使用可能になるとすぐに、オペランドをプロセッ
サ内の適当なレジスタに運ぶことであろう。多くの場
合、これは、プロセッサがオペランドを必要とする前に
うまく行うことができる。そうすると、オペランドが、
必要なときプロセッサにとってただちに使用可能とな
り、メモリからオペランドが渡されるのを待つ損失時間
がなくなる。しかし、このようなプロセッサ内の適当な
レジスタへのオペランドの早期ロードを妨げる障害がい
くつか存在する。

【０００５】このような障害の１つは、コンピュータ
が、その出力の保全性を維持するために、その動作をか
なり硬直した順序パターンで実行しなければならないこ
とである。コンピュータがその動作を順序通り実行する
には、必要な命令をプロセッサにロードし、その命令に
必要な特定のオペランドを適当なレジスタにロードする
こと必要である。その後、プロセッサは、１つまたは複
数のオペランドに対して求められた動作を実行する。次
にコンピュータは結果を記憶する。結果の記憶が完了す
ると、プロセッサは、次の命令サイクルを開始して、必
要な命令を取り出し、次いで必要な１つまたは複数のオ
ペランドなどを取り出して、およそ同じプロセスを続行
する。一般に、前の命令サイクルを完了し、その結果を
記憶してからでないと、次の命令が開始できない。

【０００６】最近の開発によって、前述の障害のいくつ
かが解決された。このような最近の開発の１つに、命令
パイプラインまたは待ち行列機構を備えた設計のプロセ
ッサがあり、この命令パイプラインまたは待ち行列機構
によってプロセッサは一度に複数の命令を取り出すこと
ができ、実行のためにプロセッサがこれらの命令を必要
とする前に使用可能にすることができる。各命令サイク
ルの完了時に、コンピュータには、実行すべき次の命令
がプロセッサ内で使用可能なので、メモリからの次の命
令を待つことによって生ずる遅延はない。これは、単一
プロセッサとより精巧なプロセッサに共通の機構であ
る。また、ほとんどすべての高性能コンピュータは、い
くつかの命令の実行をオーバーラップすることができ
る。高性能コンピュータは、そのハードウェア資源を最
適に使用するために、しばしば元のプログラム中で指定
された順序とは異なる順序で命令（またはそれらの命令
を含む原始動作）を実行する。

【０００７】コンピュータの動作で命令または演算をオ
ーバーラップさせる方法がいくつかある。１つの方法
は、ハードウェアのみを通じてそれを実施するものであ
るが、これは複雑でそれほど有望な方法ではない。もう
１つの方法は、コンパイラに、最適化プロセスを通じて
プログラムの実行順序を並び換えさせるもので、これ
は、はるかにより効率的で効果的な方法である。

【０００８】コンパイラは、プログラムのコンパイル中
に命令順序を並べ換え、実行がオーバーラップできる１
組の命令を形成する。コンパイラが、プログラム解析に
よって、ある命令によってもたらされた結果を記憶する
メモリまたはレジスタが、他の命令がその入力オペラン
ドを取り出し等するために使用するものとは異なること
を保証できる場合にのみ、２つの命令の実行がオーバー
ラップでき、すなわちプログラム中で指定された順序と
異なる順序で実行することができる。この主題に関する
文献では、これらのことは、反出力／真データ依存制約
条件として知られている。

【０００９】オペランドがレジスタから取り出され、結
果がレジスタに記憶されるときは、上述の制約条件を強
制することは容易である。しかし、オペランドがメモリ
から取り出され、あるいは結果がメモリに記憶されると
きは、この課題ははるかに困難である。命令によって参
照されるメモリ位置のアドレスが、プログラムがコンピ
ュータによって実行されるときに計算される場合には、
この問題は特に深刻である。この状況では、２つのアド
レス計算が、プログラムの実行時に同じアドレスをもた
らすかどうかを決定することは、理論的に不可能であ
り、あるいは近い将来にコンパイラからは期待されない
複雑なプログラム解析能力が必要となる。また、データ
依存性をコンパイル時に解析しつつ行うことは、データ
へのアクセスに間接的アドレス指定またはポインタを使
用するときには、極めて実現しにくい。

【００１０】プログラム中で計算され使用される２つの
アドレスがプログラム実行時に同一になるか異なるもの
になるかをコンパイラは判定できないが、プログラム解
析技法での経験によれば、アドレスが異なる確率が非常
に高い。しかし、コンパイラは、プログラムの保全性と
正確性のために、アドレスが同じになる場合のことを想
定する結果、得られる並列性、動作効率、及び速度の大
きな損失が生じることになる。コンパイラが逆の動作を
し、アドレスの衝突がないであろうと仮定するのは、コ
ンパイラ最適化としては安全でないであろう。

【００１１】

【発明が解決すべき課題】したがって問題は、簡単に言
えば、どのようにしてコンパイラが順不同のオペランド
取出しの可能性を完全に最適化できるようにするかであ
る。順不同のオペランド取出しとは、最適化コンパイル
済みプログラム中におけるストア動作に先立つオペラン
ドのロード動作であり、このオペランドのロード動作
は、最適化コンパイルされていないプログラム中におい
ては該ストア動作に後続して存在した。

【００１２】ロード動作をストア動作より前に順不同で
実行できるようにすることによって、コンパイラにプロ
グラムの実行を最適化させようとする１つの試みが、ア
レクサンドル・ニコラウ（Alexandru Nicolau）、ＩＥ
ＥＥTransactions On Computers, Vol.38, No.5（1989
年5月）"Run-Time Disambiguation:Coping with Static
ally Unpredictable Dependencies"に記載されている。
ニコラウの論文は、コンパイラが、記憶動作の前にロー
ド動作を移すことができる時を識別して、必要なコーデ
ィングを挿入し、その結果、プロセッサが、プログラム
がコンピュータによって実行される時に検査を行って、
記憶動作とロード動作のアドレスが一致するかどうか判
定できるようにする方法を記載している。一致しない場
合には、プロセッサは、記憶動作の前にロード動作が移
された、最適化された命令シーケンスへの分岐動作を実
行する。一致する場合には、プロセッサは、記憶動作の
前にロード動作を移させないセーフ・コードに分岐す
る。プロセッサに検査を行わせて、ロードの移動前のア
ドレスとプログラム実行中に記憶機構に割り当てられる
アドレスが一致するかどうかを判定させるのは、実行速
度増加の妨げとなる。実際に、プログラムを元の最適化
されていない順序で実行するときよりも、ニコラウの構
成で実行する方が時間がかかることが時々ある。ニコラ
ウはこのことをその論文に記している。実行時明確化プ
ロセスの難点の１つは、プロセッサまたはＣＰＵが、ア
ドレスの比較というＣＰＵには適していないプロセスを
含めて、すべての作業を行わなければならないことであ
る。ＣＰＵ内の各演算論理機構（ＡＬＵ）は、一時にロ
ード動作の１つのアドレスを記憶動作の１つのアドレス
としか比較できない。ＣＰＵは、ロード動作が順不同で
実行される前に、記憶動作のアドレスを生成し、それを
ロード動作のアドレスと比較しなければならない。

【００１３】本発明の目的は、既存の技術に伴う上記の
問題を解決し、コンピュータの全体的処理速度を増加さ
せ、その動作をより効率的にすることである。

【００１４】本発明は、コンピュータ・プログラムの実
行中に普通なら存在するはずのメモリ待ち時間の大部分
をなくすことによって、コンピュータ・システムの速度
と効率を向上させる。

【００１５】本発明の他の目的は、誤りのないコンピュ
ータ動作を保証しながら、コンピュータ動作における速
度と効率の増加を果たすことである。

【００１６】

【課題を解決するための手段】本発明は、コンュータ・
システムと組み合わせたとき、正確さを失わずに速度及
び効率の向上という所望の結果を達成する、いくつかの
新しい主要構成要素を包含する。新しい要素とは、オプ
ティマイザを含む改良されたコンパイラ、命令セット中
に新しい命令を有する改良されたＣＰＵまたはプロセッ
サ、及び、本明細書でアドレス比較機構（ＡＣＵ）と称
する、新しいＣＰＵ命令に応答して、ＣＰＵアドレスを
以前に生成されたアドレスと速やかに比較するための新
しいハードウェアである。ＡＣＵは通常、連想メモリ
（内容アドレス可能メモリとも呼ばれる）を使用して実
施されるが、他の実施態様も可能である。

【００１７】簡単に言えば、改良されたコンパイラ、連
想メモリまたはＡＣＵ、及び改良されたプロセッサまた
はＣＰＵを新しい命令と共に使用して、順不同ロード動
作を誤りなく実行するための方法が提供される。本発明
による方法の基本的態様では、プログラムのコンパイル
中に、オプティマイザを含む改良されたコンパイラが、
関連する記憶動作の前に順序を移すことのできるロード
動作を識別し、次いで関連する記憶動作の前にそのロー
ド動作を移す。関連する記憶動作はコンパイルされた形
のプログラムでその前に移されたロード動作を用いて識
別される。プロセッサによるコンパイル済みプログラム
の実行中に、順不同ロード動作によって取り出されたオ
ペランドのアドレスが、ＡＣＵにセーブされる。ＡＣＵ
は、ロード動作中にセーブされたアドレスを、記憶動作
が実行されるとき、プロセッサにより関連する記憶動作
によって生成されたアドレスと比較する。比較したアド
レスが異なる場合には、プロセッサはプログラムの実行
を続け、次いでＡＣＵ内にセーブされたロード動作のア
ドレスを、それがもはや必要ないときは消去する。比較
したアドレスが同じ場合には、記憶動作が打ち切られ、
回復プログラムが実行される。回復プログラムの目的
は、ロード命令と記憶命令が同じメモリ位置にアクセス
するときに、これらの命令の順序を逆にすることによっ
て発生する誤りを除くことである。

【００１８】本発明のもう１つの態様では、コンパイラ
は、プログラムの実行効率を向上させるために関連する
記憶動作の前に移すことのできるロード動作を識別した
後、そのような最適化が安全であることを証明できない
場合には、そのロード動作にフラグを付ける。好ましい
実施例では、コンパイラは、ロード命令をロード・セー
ブ命令に変えることによってフラグ付けを行う。さらに
コンパイラは関連する記憶動作を変更し、フラグを付け
る。好ましい実施例では、コンパイラは、記憶動作を記
憶・検査命令に変えることによってフラグ付けを行う。
次いで、コンパイラは、記憶・検査命令の前にロード・
セーブ命令を移す。次いでコンパイラは、記憶・検査命
令の後に追加の命令、すなわち、ロード動作によってセ
ーブされたオペランドのアドレスを、コンパイル済みプ
ログラムの実行中に記憶動作が使用するアドレスと比較
した後に消去することを目的とする命令を追加する。ま
た、ロード動作中にセーブされたオペランドのアドレス
が、コンパイル済みプログラムの実行中に記憶動作によ
って生成されるアドレスと同じ場合には、コンパイラ
は、コンパイル済みプログラムの実行中に使用される回
復シーケンスも生成する。本発明のさらに１つの態様で
は、プロセッサは、コンパイル済みプログラムを実行
し、またフラグ付きロード動作、好ましい実施例ではフ
ラグ付きのロード・セーブ動作を認識して、そのロード
動作によって取り出されるオペランドのメモリ・アドレ
スをＡＣＵにセーブする手段を有する。プロセッサはま
た、フラグ付き記憶動作、好ましい実施例では記憶・検
査動作を認識する手段も有する。フラグ付き記憶動作を
プロセッサが識別すると、アドレスが生成されて連想メ
モリに送られ、ロード動作によって連想メモリ内にセー
ブされたアドレスと比較される。

【００１９】本発明のもう１つの態様では、「アドレス
比較機構」（ＡＣＵ）が、ロード・セーブ動作中にプロ
セッサから送られてきたアドレスを受け取り、それをＡ
ＣＵ内の特定のメモリ位置にセーブする。その後、記憶
・検査命令とプロセッサが記憶動作のために生成したア
ドレスを受け取ると、ＡＣＵは、その生成されたアドレ
スをロード動作によってセーブされたアドレスと比較す
る。記憶動作によって生成されたアドレスとロード動作
中にセーブされたアドレスが一致しない場合には、コン
ピュータはプログラムの実行を続行する。しかし、比較
時にアドレスが一致した場合には、連想メモリまたはＡ
ＣＵはプロセッサに信号を送って、そのことを通知す
る。

【００２０】アドレス比較機構はまた、好ましい実施例
では「ＡＣＵ消去」命令によって生成された適当な消去
信号を受け取ると、アドレス比較機構が記憶しているセ
ーブされたアドレスを消去する。

【００２１】プロセッサは、検査のために送られたアド
レスとＡＣＵにセーブされているアドレスが一致すると
の信号をＡＣＵから受け取った場合、回復コードを実行
する。

【００２２】本発明の他の態様では、アドレス比較機構
は、アドレスをセーブする複数のメモリ・レジスタから
成る。これらのメモリ・レジスタの各々に、１つの有効
ビット位置または別の等価の機構が関連づけられてお
り、これは、メモリ・レジスタにセーブされたアドレス
が有効で検査すべきか否か、または、そこに関連アドレ
スがなく、メモリ・レジスタが追加情報を受け取るため
に使用可能であるか否かを、システムに知らせる。さら
に、各メモリ・レジスタおよびその対になった有効ビッ
トと共に、制御ポートがあり、これはシステムの残りの
部分から信号を受け取り、これらの信号に従って、必要
なセーブ動作、比較動作、または消去動作を実施する。
この制御ポートは復号器によって活動化され制御され
る。

【００２３】本発明の他の態様では、ＡＣＵは、適当な
信号を受け取ったとき、その中に含まれるアドレスを別
のメモリ位置にセーブし、それ自体が使用可能になっ
て、システムが開始する恐らくは別のアプリケーション
によって生成される追加のアドレスを受け取ることがで
きる。システムは、以前にはＡＣＵ外の位置にセーブさ
れていたアドレスをＡＣＵに戻して復元し、元のアプリ
ケーションを前に中断した所から続行することができ
る。

【００２４】

【実施例】前述のように、本発明の目的は、コンピュー
タの効率を維持し、かつ誤りのない動作を確保しなが
ら、コンピュータの実行速度を向上させることである。
メモリ待ち時間を著しく短縮することができれば、コン
ピュータの効率と速度が著しく向上できることは、当業
者には既によく知られている。また、１つまたは複数の
記憶動作の前にロード動作を移した順不同オペランド取
出しを可能にすることは、速度と効率の向上を達成する
１つの方法である。本発明の目的は、これらの目的を達
成し、それに誤りがないことを確保する手段を提供する
ことである。

【００２５】本発明の装置の主要構成要素には、図１に
示すように、改良されたコンパイラ２１、命令セットに
４つの新しい命令が加えられた改良されたプロセッサ２
４、アドレス比較機構（ＡＣＵ）２２、及びメモリ２３
が含まれる。システムはまた、適切な相互接続、すなわ
ち制御線２５、２６、アドレス・バス２７、データ・バ
ス２８、並びにアドレス検査信号線３０とＡＣＵレジス
タ番号線２９を含む。図１の矢印は信号の流れの方向を
示す。命令セットに加えられた４つの新しい命令は、ロ
ード・セーブ命令、記憶・検査命令、ＡＣＵ消去命令、
及びＡＣＵ読取り命令と称する。

【００２６】図１のコンピュータ・システムの全般的動
作を、これから簡単に説明する。

【００２７】改良されたコンパイラ２１は基本的に、ロ
ード・セーブ、記憶・検査、及びＡＣＵ消去という新し
い命令を使用できる標準のコンパイラである。当技術分
野で周知のように、コンパイラは、ＰａｓｃａｌやＦＯ
ＲＴＲＡＮなどの高水準言語をコンピュータに読取り可
能な機械コードに変換する。しかし本発明の改良された
コンパイラは、いつどこでそれがプログラムの実行を最
適化し、ハードウェアの使用によって本発明の実行の速
度及び効率を向上させることができるかの判断も行う。

【００２８】コンパイル過程中に、改良されたコンパイ
ラは、安全でないコンパイラ最適化をもたらすことがし
ばしばあるとしても、いつどこでそれが１つまたは複数
の記憶動作の前にロード動作を移すことができるかを判
断することによって、プログラムの実行順序を最適化す
る。コンパイラは、記憶動作の前にロード動作を移すよ
う判断を下した時、ロード動作に関連するロード・コマ
ンドをロード・セーブ・コマンドに変更する。コンパイ
ラは、ロード動作によって取り出されるオペランドのア
ドレスとプログラム実行時に記憶動作によって生成され
るアドレスが異なると判定できないときでも、ロード・
セーブ・コマンドを記憶コマンドの前に移す。コンパイ
ル過程中に、上記のようにして１つまたは複数のロード
動作がその前に移された記憶動作に遭遇すると、コンパ
イラはその記憶動作を記憶・検査動作に変更し、同時
に、その記憶・検査コマンド及び適切な信号をプロセッ
サが受け取ったときに実行される割込みハンドラ内の条
件付き分岐動作が到達する回復シーケンスとのすぐ後に
ＡＣＵ消去命令を加える。コンパイラは、プログラムの
コンパイルが完了するまでこの過程を続ける。割込みハ
ンドラ、及びそのソフトウェアとハードウェアの諸態様
は、当技術分野で周知である。

【００２９】したがって、コンパイラ２１は、上記の追
加行為を伴う通常の方式でプログラムをコンパイルし、
ＣＰＵまたはプロセッサが実行できるようにプログラム
を準備する。次いで、本発明で構想する追加部分をもつ
コンパイル済みプログラムが、実行のためコンピュータ
のメモリ内に置かれる。

【００３０】コンパイル済みプログラムの実行中にロー
ド・セーブ・コマンドに遭遇した時は、ＣＰＵ２４は、
通常のロード・コマンドを実行する。これには、通常、
メモリ２３内の特定の位置からのオペランドの取出し、
及びそのオペランドのＣＰＵ２４内のレジスタへの転送
が含まれる。次いでＣＰＵ２４は、ロード・セーブ・コ
マンドの一部として、そのオペランドのメモリ・アドレ
スをＡＣＵ２２内のレジスタにセーブする。この特定の
ロード・セーブ・コマンドには、プログラム・コンパイ
ル中にＡＣＵ２２内の特定のレジスタが事前に割り当て
られている。そのレジスタにはオペランドのメモリ・ア
ドレスがセーブされ、そのレジスタ番号が、レジスタ番
号線２９を介してＡＣＵ２２に送られる。当技術分野で
周知のように、プログラムがコンパイルされ最適化され
るとき、ロード動作によってオペランドがそこから取り
出されるメモリ・アドレスは通常は知られていない。そ
のアドレスは、プログラム実行中にロード・コマンドが
実行されるときに、ロード動作によって生成または計算
される。

【００３１】ＣＰＵが記憶・検査命令に遭遇するとき
は、ＣＰＵは、記憶動作のためのメモリ・アドレスを生
成することによって通常の記憶動作を開始する。しか
し、ＣＰＵ２４は、記憶動作を実際に実行する前に、生
成されたアドレスをＡＣＵ２２に送り、ＡＣＵ２２がそ
れを、前のロード・セーブ・コマンドによってＡＣＵ２
２にセーブされたアドレスと比較する。記憶動作によっ
て生成されたアドレスが以前にセーブされたどのアドレ
スとも同じでない場合は、コンパイル済みプログラムの
実行が続行される。アドレスの検査が完了すると、ＡＣ
Ｕ消去命令が、記憶・検査動作によって生成された他の
どのアドレスとも比較する必要のないロード・セーブ動
作のすべてのアドレスをＡＣＵ２２から消去する。一
方、記憶動作によって生成されたアドレスがＡＣＵ２２
内にセーブされているいずれかのアドレスと同じである
場合には、ＡＣＵ２２が信号を生成し、アドレス検査信
号線３０を介してＣＰＵ２４に送る。この信号を受け取
ると、ＣＰＵは、以前に準備されコンパイラによってこ
の状況のためにコンパイルされ最適化されたプログラム
中に入れられた、回復プログラムの実行を開始する。こ
の回復シーケンスの目的は、あとで詳述するが、誤って
いた計算を再計算することである。この誤りとは、ロー
ド・セーブ・コマンドによって前に取り出されたオペラ
ンドのアドレスと同じアドレスが記憶・検査コマンドに
よって生成されることである。また、最適化されていな
い形のプログラム中でロード・セーブ・コマンドの後に
記憶・検査コマンドが続くことである。記憶・検査コマ
ンドによってメモリ内に記憶され、ロード・セーブ・コ
マンドによって取り出される値は、この２つのコマンド
が最適化されていないプログラムの元の順序にある場
合、誤った値でプログラミングされたすべての計算を再
計算するのに使用される。また、この事象シーケンスで
は、ＡＣＵ消去命令が、ＡＣＵ２２内にセーブされたも
はや必要ではないアドレスを消去する。

【００３２】コンパイラとコンパイル過程：コンパイラ
は、ＦＯＲＴＲＡＮ、ＢＡＳＩＣ、Ｐａｓｃａｌなどの
原始言語で書かれたコンピュータ・プログラムを機械語
に変換する、複雑なコンピュータ・プログラムである。
本発明の原理によれば、コンパイラはこれ以上のことを
行う。すなわちコンパイラはさらに、ＡＣＵハードウェ
アを使用してプログラムの実行を最適化する。コンパイ
ラはこれを、コンパイラの一部をなすオプティマイザで
行う。オプティマイザとは、コンパイル中にコンピュー
タ・プログラムを実行効率が向上するように変更するた
めに使用される、コンパイラ内のルーチンまたはプロセ
スである。一般に求められている効率は、より高い実行
速度である。これを達成するために利用できる手法、及
び本発明で使用される方法の１つは、プログラムの一部
分の実行順序の並べ換えである。

【００３３】本発明のオプティマイザは、記憶動作の前
にロード動作を移して、プロセッサが必要とするオペラ
ンドが適切な時に使用可能となるようにし、したがって
ほとんどのメモリ待ち時間をなくすることによって、そ
の目的を達成する。オプティマイザは、コンパイル過程
中に次の３つの可能性に直面する。ａ）問題がない。プ
ログラム実行時に記憶動作に割り当てられたアドレスが
順不同ロード動作のアドレスと異なることが確信でき
る。ｂ）記憶動作に割り当てられたアドレスが順不同ロ
ード動作のアドレスと同じになる確率が非常に高い。
ｃ）２つのアドレスが同じになるかどうかコンパイル時
には判定できず、したがって記憶動作に割り当てられた
アドレスが順不同ロード動作のアドレスと同じになる機
会がわずかにある。

【００３４】上記の３つの可能性が与えられているとす
ると、従来型のオプティマイザでは、それができること
は非常に限られる。図２に、どのようなオプションがあ
るかを図式的に示す。図２を見るとわかるように、プロ
グラム実行時に記憶動作に割り当てられたアドレスとロ
ード動作のアドレスが一致しないことをオプティマイザ
が確信できないかぎり、オプティマイザは記憶動作の前
にロード動作を移すことはできない。これを、図３に示
すような、本明細書に記載するシステムでオプティマイ
ザができることと対比されたい。この改良されたオプテ
ィマイザは、安全でないコンパイラ最適化状況下におい
ても同然のことを行うことができる。このオプティマイ
ザは、前段に記載の"ａ"と"ｃ"の２つの状況下で、記憶
動作の前にロード動作を移す。安全でないコンパイラ最
適化状況である状況"ｃ"については、改良されたオプテ
ィマイザは、この異常または誤りの有無の検査を支援す
るコードを生成する。このコードについては後で述べ
る。当業者なら、コンパイル中に記憶動作の前に移すこ
とのできるほとんどの潜在的ロード動作では、プログラ
ム実行時に記憶動作に割り当てられるアドレスが順不同
ロード動作によって取り出されるオペランドのアドレス
と同じになる確率が僅かであることを知っていよう。し
たがって、記憶動作に割り当てられたアドレスとロード
動作のアドレスが同じになるまれな場合を検出する効果
的で効率的な方法があれば、プログラムの実行速度がか
なり増大することになる。異常検査の方法を、性能の低
下を引き起こさない異常修正の方法と組み合わせると、
安全でないコンパイラ最適化の手順が、安全かつ効果的
に使用できるようになるはずである。あとで詳しく実証
するように、本明細書に記載の本発明は、後述の適切な
回復シーケンスと組み合わせて使用するとき、上記のま
れな異常を検出するための効果的で効率的な方法を提供
する。

【００３５】図４に示すような従来型のオプティマイザ
は、分岐動作境界を越えてコードを移動することによっ
て最適化を実施することはまれである。一方、図５を見
るとわかるように、本明細書に記載のシステムで使用さ
れるオプティマイザは、極めて容易に分岐動作の前にロ
ード動作を移すことができる。実際に、本明細書に記載
のシステムで使用するオプティマイザが行うことは、ロ
ード・セーブ動作の実行が、分岐動作の結果としてその
ＡＣＵ消去コマンドを迂回するかどうか判定し、次い
で、そのようなＡＣＵ消去コマンドが予め挿入されてい
ない場合には、ＡＣＵ消去コマンドに通じていない分岐
動作のすべての目標にＡＣＵ消去コマンドを挿入するこ
とである。さらに、このコンパイラは、ＡＣＵ消去命令
中に、ロード動作のアドレスがセーブされるＡＣＵ中の
ＡＣＵレジスタ番号を挿入する。このようにしてコンパ
イラは、分岐動作の前にロード・セーブ動作を移すこと
ができる。移動先は、プログラム実行継続時において分
岐の実行終了時に到達すべき位置である。

【００３６】コンパイラ、その動作及びプログラミング
は、当業者には周知である。したがってここで詳述する
必要はない。コンパイラの最適化、その使用、プログラ
ミング及び原理に関する良い一般的な参考文献は、A.V.
アホ（Aho）及びR.セティ（Sethi）著 Compilers:Princ
iples, Techniques and Tools, Addison-Wesley社、
（１９８６年）である。コンパイル過程の検討の際に
は、本発明に独特の、また関係するある態様だけを示
す。

【００３７】コンパイラがコンパイル過程で行う通常の
機能の他に、２つの追加の過程がある。１つは最適化で
あり、他の１つは必要なコード変更と必要な回復シーケ
ンスの追加である。

【００３８】最適化過程では、改良されたコンパイラ
は、オプティマイザとして機能し、いつ記憶の前にロー
ドを移すことができるかに関する決定を行う。この態様
については先に述べた。前述のように、オプティマイザ
として機能するコンパイラは、通常は安全でないコンパ
イラ最適化を行うことになる。当然のことながら、前述
のように、異常の確率が非常に高い場合においては、記
憶動作の前にロード動作を移さないという決定がなされ
る。しかし、大部分の場合においては異常が起こる確率
が低い場合ので記憶動作の前にロード動作を移すことに
なる。

【００３９】コンパイラが最適化の判断を下し、またプ
ログラム実行時に異常が発生する機会が僅かであると判
定すると、コンパイラは、プログラム実行時に適切な検
査過程を保証するために、必要なコードとプログラム変
更を生成する。図７および８は、ステップ３６でコンパ
イラが最適化の基本的判断を下し、１つまたは複数の記
憶動作の前にロード動作を移した後の、事象シーケンス
を示す流れ図である。次にステップ３７で、コンパイラ
は、移動されたロード命令をロード・セーブ命令に変更
する。次のステップ３８で、コンパイラは、その記憶命
令、またはその前にロード動作が移されたすべての記憶
命令が、すでに記憶・検査命令に変換されているか否か
を判定する。以前に記憶・検査命令に変更されていない
記憶命令がある場合には、次のステップ３９で、これら
の記憶命令がすべて記憶・検査命令に変更される。次の
ステップ４０で、コンパイラは次の２つの処置のうちの
１つを講じる。その特定のロード命令が記憶命令と交換
されたのが最初ではないと判定した場合には、コンパイ
ラはルーチンの終りまで進み、ステップ４４で回復コー
ドを作成し、それからルーチンを出て、通常のコンパイ
ル過程に戻ることになる。しかし、ステップ４０で、そ
れがロード命令が記憶命令と交換された最初であると判
定した場合には、コンパイラは次のステップ４１に進
み、そこでコンピュータが、記憶・検査命令にＡＣＵ消
去命令が付加されているか否かを判定する。付加されて
いない場合には、コンパイラはステップ４２に進んで、
ＡＣＵ消去命令を生成し、図８のステップ４３に進む。
ステップ４１で、コンパイラが、記憶・検査命令の後に
ＡＣＵ消去命令が続くと判定した場合には、コンパイラ
は直接ステップ４３に進む。ステップ４３で、コンパイ
ラはＡＣＵ消去命令にレジスタ番号ビットを挿入して、
ＡＣＵレジスタからロード動作中にセーブされたアドレ
スのエントリを消去する。次いでコンパイラは次のステ
ップ４４に進み、必要な回復コードを生成し、これをコ
ンパイル済みプログラムに加える。これが完了すると、
コンパイラはルーチンを出て、通常のコンパイル過程に
進む。

【００４０】改良されたコンパイラによってコンパイル
済みプログラムに挿入された回復コードには、異常が発
生した場合に実行される割込み処理ルーチン内の条件付
き分岐動作から到達する。前述のように、異常が発生す
るのは、ＡＣＵにおける比較によって、記憶動作に割り
当てられたアドレスが１つのロード・セーブ動作中にセ
ーブされたアドレスの１つと同じであると判定されたと
きである。記憶動作のアドレスは、前述のように、記憶
・検査動作が開始する時点でプロセッサによって生成さ
れる。回復コードの生成と準備は、当技術分野で周知で
ある。

【００４１】前述のように、本発明では、分岐動作の処
理、特にプログラムのコンパイル中に遭遇することのあ
る条件付き分岐動作の処理は難しくはない。一般に、遭
遇することのある最も普通の形の分岐動作は、条件付き
のものである。条件付き分岐動作によってもたらされる
問題は、分岐動作の前にロード動作が移され、関連する
記憶・検査動作とＡＣＵ消去動作がこの分岐動作のいく
つかの目標の１つである時に発生する。分岐動作が、活
動化されて実行されるはずであり、記憶・検査命令、及
び特に、ＡＣＵからの以前のロード命令のアドレスを消
去することを意味するＡＣＵ消去命令を含む目標を選択
しないはずである場合、ロード・セーブ動作によってセ
ーブされたアドレスを適時にＡＣＵから適当に除去する
ことに失敗する可能性がある。しかしコンパイラは、プ
ログラム・コンパイル時に、分岐動作の実行によって必
要なＡＣＵ消去命令が迂回できる可能性があるかどうか
を判定することができる。可能性があると判定した場合
には、コンパイラは、元々はロード・セーブ動作を回避
していた分岐動作の目標に追加のＡＣＵ動作を加える。
このようにして、どの分岐目標を取ったかには関係な
く、ロード・セーブ・コマンドによってＡＣＵ内にセー
ブされた情報は、適時に除去される。

【００４２】前述のように、コンパイラとそのオプティ
マイザは、命令セットに加えられた４つの新しいコマン
ドのうちの３つだけを使用する。図６は、本明細書に記
載のシステムでコンパイラが使用する３つのコマンドを
示す。図６の各見出しの下は、コンパイル後にプログラ
ム行がどう現れるかの例である。例えば、見出し「ロー
ド・セーブ・コマンド」の下で、最初に現れる項目は実
命令「ロード・セーブ」であり、次に現れる項目はオペ
ランドがロードされる先のＣＰＵレジスタであり、Ｄｅ
ｓｔ＿Ｒｅｇで示されている。次の情報部分は、そこか
らオペランドがロードされる、メモリ内のアドレスであ
る。この情報は、コンピュータ内でプログラムが実行さ
れる時に計算される可能性が最も高い。これはＡＣＵに
セーブされるアドレスでもある。最後に、ＡＣＵバッフ
ァ番号ＡＣＵ＿Ｂｕｆｆｅｒ＿Ｎｏ_nがある。バッファ
番号は、プログラム実行中にロード動作のアドレスがセ
ーブされる、ＡＣＵ内の特定のレジスタを識別する。後
述するように、ＡＣＵは、各レジスタに１つのアドレス
を記憶することができる個別に制御されたレジスタから
成る連想メモリ装置である。

【００４３】図６の見出し「記憶・検査コマンド」の下
は、この特定の命令がコンパイル後にコンピュータ・プ
ログラム中でどう現れるかの例である。記憶・検査命令
の後に、メモリにセーブされるオペランドを含むＣＰＵ
レジスタを識別するステートメントＤａｔａ＿Ｒｅｇが
ある。次の項目Ａｄｄｒｅｓｓは、記憶動作が実行され
る時にコンピュータによって生成されるメモリ・アドレ
スである。生成されたこのアドレスは、ＡＣＵ内にセー
ブされたアドレスと突き合わせて検査される。

【００４４】ＡＣＵ消去コマンドは通常、プログラム中
の大部分の記憶・検査コマンドの後に続く。コンパイル
済みプログラム中でこの命令がどう現れるかを、図６の
見出し「ＡＣＵ消去コマンド」の下に示す。最初の項目
は命令自体Ｃｌｅａｒ＿ＡＣＵであり、その後に消去す
べきすべてのバッファの番号が続き、この例では、ＡＣ
ＵＢｕｆｆｅｒ＿Ｎｏ₁、...ＡＣＵＢｕｆｆｅｒ＿
Ｎｏ_nで表されている。コンパイラは、ロード動作のア
ドレスがセーブされる先のＡＣＵレジスタを割り当てる
ので、コンパイル時に、消去すべきレジスタを識別する
ことができる。またコンパイラは、コンパイル過程中
に、その前にロード動作が移された特定の記憶動作を知
っている。各記憶動作の位置は、記憶動作の前に移され
たロード・セーブ動作を除き、コンパイル過程で変更さ
れないままである。したがってコンパイラは、どの記憶
・検査動作が、その前に特定のロード・セーブ動作が移
された最後のものであるかを知っている。コンパイラ
は、この最終記憶・検査動作に到達すると、その後に続
くＡＣＵ消去命令に、前記のロード・セーブ動作のアド
レスがセーブされた先のレジスタの番号を加える。これ
は、その保存がもはや必要でないためである。

【００４５】例示の目的で、図９、図１０、図１１、図
１２はそれぞれ、コンピュータ・プログラムのコンパイ
ル前のシーケンス、本発明を使用せずにコンパイルされ
たシーケンス、本発明を使用してコンパイルされたシー
ケンス、及びコンパイラによって生成される回復コード
を示す。

【００４６】図９で、命令"ｉ１"はレジスタ１３と１５
の内容を加算し、結果をレジスタ１３に戻す（このプロ
グラム・シーケンス中で参照されるレジスタは、別段の
明記がない限りＣＰＵのレジスタである）。命令"ｉ２"
は、レジスタ１３の内容にオフセット０を加えてメモリ
・アドレスを形成し、このメモリ・アドレスを使用して
メモリから値を取り出し、取り出した値をレジスタ１３
に戻す。命令"ｉ３"は、レジスタ１３の新しい内容にオ
フセット１１２を加えてメモリ・アドレスを形成し、こ
のメモリ・アドレスを使ってレジスタ１の内容をメモリ
に記憶する。命令"ｉ４"は、レジスタ１２の内容にオフ
セット１８を加えてメモリ・アドレスを形成し、このメ
モリ・アドレスを使ってメモリから値を取り出し、取り
出した値をレジスタ２に戻す。命令"ｉ５"は、レジスタ
１３の内容にオフセット１１６を加えてメモリ・アドレ
スを形成し、このメモリ・アドレスを使ってレジスタ３
の内容をメモリに記憶する。命令"ｉ６"は、レジスタ１
２の内容にオフセット１０を加えてメモリ・アドレスを
形成し、このメモリ・アドレスを使用してメモリから値
を取り出し、取り出した値をレジスタ４に記憶する。命
令"ｉ７"は、レジスタ２の内容からレジスタ４の内容を
引き、結果をレジスタ２に戻して記憶する。命令"ｉ８"
は、レジスタ２とレジスタ６の内容を加算して、結果を
レジスタ２に戻して記憶する。

【００４７】前述のように図１０のプログラム・シーケ
ンスは、本発明の改良されたコンパイラを使用しないコ
ンパイル後に現れるので、図９に示したプログラム・シ
ーケンスと同じである。

【００４８】図１１は、本発明の最適化処理とコンパイ
ル法を使用して図９に示すプログラム・シーケンスをコ
ンパイルした後に、プログラムがどのように現れるかを
示す図である。コンパイル過程中にオプティマイザは、
このコード・セグメントの実行時間を減らすために、共
にロード動作である図９の行ｉ４とｉ６を、順序を外し
て記憶動作ｉ３、ｉ５の前に移すべきであると決定す
る。図９の行ｉ４は、ロード・セーブ動作に変更され、
１つの記憶動作の前に移されて、図１１の命令行２にな
る。図９の行ｉ６のロード動作は、ロード・セーブ動作
に変更され、２つのセーブ動作の前に移されて、コンパ
イル済みプログラムの図１１の行３になる。両方のロー
ド・セーブ動作、図１１の行２、３には、ＡＣＵ内のレ
ジスタ番号が割り当てられている。図１１の行２では、
割り当てられたＡＣＵレジスタ番号は、行末の"１"であ
り、行３ではそれは"２"であり、行末に現れている。し
たがって、これらのロード動作は、順序を外して様々な
記憶動作の前に移されており、こうしてこれらがロード
するオペランドは、実質的にＣＰＵがそれを必要とする
ようになる時より前に、ＣＰＵ内のレジスタに移され
る。そうすると、オペランドは必要になればすぐにＣＰ
Ｕが使用できるようになり、プロセッサの機能実行にお
けるあらゆる遅延がなくなり、したがって付随するメモ
リ待ち時間がなくなる。

【００４９】図９の行ｉ３は、プログラムのコンパイル
時に図１１の行６になり、この命令は記憶・検査命令に
変更される。コンパイラはまた、ＡＣＵのレジスタ１に
セーブされたアドレスを消去するため、図１１の行７に
ＡＣＵ消去１命令を加える。このアドレスは、図１１の
行２のロード・セーブ命令中にロードされるオペランド
のアドレスである。ＡＣＵのレジスタ１内のアドレス
は、この１つの記憶命令の前に移されただけで、他のど
のアドレスとも比較する必要はない。図９の行ｉ５は、
コンパイル中に図１１の行８となり、この命令は記憶・
検査命令に変更される。図１１の行９のすぐ後に、ＡＣ
Ｕのレジスタ２内のアドレスを消去するため、ＡＣＵ消
去２命令が加えられる。ＡＣＵのレジスタ２内のアドレ
スの保存はもはや必要ではない。すなわち、このアドレ
スは、その前にそれが移された両方の記憶動作中に生成
されたアドレスと比較済みである。

【００５０】図１１に示す２つの記憶・検査命令用の回
復コードを図１２に示す。最初の記憶・検査命令"Store
-Check R1,112(R13)"については、この最初の命令は打
ち切られた記憶・検査動作を再実行して、これを完了す
る。次の２つの命令は、２つの完全でないロード命令、
すなわち図１１の命令２、３を再実行する。"SR R2,R4"
命令も、対称形ロード命令によって作成された値を使用
し、対応する記憶・検査命令の前に実行されるので、再
実行される。次いで、"Go To L1"ステートメントがある
ので、制御が回復コードから主プログラムに戻される。
このステートメントは、図１１の行７で制御を主プログ
ラムに返す。

【００５１】第２の記憶・検査命令"Store-Check R13,1
16(R13)"については、回復コードの実行は次のことを含
む。すなわち、（ａ）未完了の記憶命令を再実行し、こ
の記憶命令に関して対称的に実行される唯一のロード命
令である、"L R4, 10 (R12)"ロード命令を再実行する。
（ｂ）ロード命令に依存する"SR R2, R4"命令を実行す
る。その後、回復コードは、命令"Go To L2"に従って主
プログラムに分岐する。

【００５２】回復コード・シーケンスは各記憶・検査命
令に付随する。記憶・検査例外が発生すると、例外を引
き起こした記憶・検査命令のアドレスが、プロセッサに
使用可能となり、各記憶・検査命令用の回復コード・シ
ーケンスの開始アドレスを列挙したテーブルを使って適
切な回復コード順序を選択するために、それが使用され
る。

【００５３】特定の記憶動作を超えて多数のロード動作
が移動される場合には、そのどれか１つが記憶動作と同
じメモリ・アドレスを使用し、記憶・検査例外を引き起
こす可能性がある。この状況では、回復コードは、「Ａ
ＣＵ読取り」コマンドを使ってＡＣＵの内容を照会し
て、どのロード動作が例外を引き起こしたかを識別し、
そのロード命令とその影響を受ける後続の命令のみを再
実行することができる。しかし図９ないし図１２の例で
は、最初の記憶・検査動作には、それに関して順不同で
実行されるロード動作は２つしかない。したがって、た
だ１つのロード動作が例外を引き起こしたかどうか判定
してそのロード動作だけを再実行するよりも、両方のロ
ード動作を再実行する方が都合がよい。

【００５４】コンパイラは、回復コードに関連する記憶
・検査命令が首尾よく完了する前に、回復コードが必要
とする値が、主プログラム中で破壊されないように保証
しなければならない。

【００５５】システム全体のハードウェア構成要素とコ
ンパイル後の動作：図１３は全体的コンピュータ・シス
テムとその基本要素を図１より詳しく示している。プロ
セッサまたはＣＰＵ３４は、その３つの構成要素であ
る、制御装置（ＣＵ）５３、演算論理機構（ＡＬＵ）５
０、及びレジスタ・ファイル５２に分かれている。コン
ピュータ・システムの他の２つの主要要素であるＡＣＵ
２２とメモリ２３は、接続回路に関してより詳細に示さ
れている。ＡＣＵ２２は、線７４によってアドレス・バ
ス２７に接続され、それを介してロード動作のメモリ・
アドレスを受け取ることができる。ＡＣＵ制御線２６
は、ＣＵ５３からＡＣＵ２２に通じている。ＡＣＵ−Ｃ
ＰＵインターフェースの概略図である図１６を見ると、
別々の４本の制御線、すなわちＡＣＵ消去命令用の線１
２４、ロード・セーブ命令用の線１２５、記憶・検査命
令用の線１２６、及びＡＣＵ読取り命令用の線１２７が
ある。図１３に戻ると、アドレス検査信号線３０がＡＣ
Ｕ２２からＣＵ５３に通じている。この線は、記憶動作
に割り当てられたアドレスがＡＣＵ２２内に含まれるロ
ード・セーブ動作のアドレスと同じである場合に、それ
を介して信号が送られる線である。最後にＡＣＵバッフ
ァ番号線２９があり、これはＣＵ５３をＡＣＵ２２に接
続している。この線を介してＣＵ５３はＡＣＵ２２に、
どのレジスタにアドレスをセーブするかを通知する。

【００５６】メモリ２３は、制御線２５を介してＣＵ５
３によって制御され、必要なときに活動化される。メモ
リ装置２３は、両方向コネクタ６８によってデータ・バ
ス２８と接続されている。両方向コネクタ６８は、デー
タ・バス２８をメモリ・データ・レジスタ５７に接続し
ている。さらに、アドレス・バス２７は、線６９を介し
て、メモリ２３に接続され、最終的にはメモリ・アドレ
ス・レジスタ５８に接続される。したがって、ＣＵ５３
は、メモリ２３内のある位置へのアクセスを望むとき、
制御線２５を介して活動化信号を送り、それと同時にア
ドレス・バス２７を介しコネクタ６９を経て、アクセス
しようとする特定のデータ記憶位置のアドレスを送る。
通常の復号動作が起こり、次いで要求された情報が線６
８を介してデータ・バス２８に送られ、レジスタ・ファ
イル５２またはＣＵ５３内の命令レジスタ５４に送られ
る。線３１はＡＣＵ２２をデータ・バス２８に接続して
いる。ＡＣＵ読取りコマンドが実行されるとき、ＡＣＵ
２２内のアドレスが、線３１を介しデータ・バス２８を
経て、次に線６８を介してメモリ２３に送られる。

【００５７】ＣＵ５３内には、２つのより小さなサブ・
ユニットである、命令レジスタ（ＩＲ）５４及びプログ
ラム・カウンタ（ＰＣ）５５がある。命令レジスタ５４
及びプログラム・カウンタ５５は、連携して動作する。
すなわち、プログラム・カウンタ５５は次の命令のアド
レスを、線７０を経てアドレス・バス２７を介してメモ
リ２３に送る。命令自体はデータ・バス２８を経て線７
１を介してＣＵ５３に返送され、命令レジスタ５４に入
れられる。これによって、明らかに必要な命令がその固
有の順序でＣＵ５３に提供されることになる。

【００５８】実データ処理はＡＬＵ５０で行われる。Ａ
ＬＵ５０が作用するオペランドはレジスタ・ファイル５
２内に置かれており、必要に応じてＡＬＵ５０にとって
使用可能になる。要求されると、オペランドはレジスタ
・ファイル５２から線７３を介してＡＬＵ５０に送られ
る。ＣＵ５３から制御線２５を介して送られてきた命令
に応じて、ＡＬＵ５０がオペランドに対して適切な動作
を実施する。この動作が完了すると、結果が線７２を介
してレジスタ・ファイル５２に返送される。

【００５９】動作を始めるに当たっては、本発明の教示
によるコンパイラが準備したコンパイル済みのプログラ
ムが、コンピュータのメモリ２３にロードされる。これ
は図１４の流れ図の開始ブロック１０５に相当する。次
に図１４のプログラム・ブロック１０６で、コンピュー
タは実行を開始する。図１４のブロック１０７で、コン
ピュータは、プログラムの実行中に、時々ロード・セー
ブ・コマンドに遭遇する。このコマンドに遭遇すると、
コンピュータは、図１３のメモリ２３からの適切なオペ
ランドを図１３のレジスタ・ファイル５２の適切なレジ
スタにロードするなど、通常のロード動作を完了する。
次いでコンピュータは、図１４のステップ１１６で、オ
ペランドがそこから来たメモリ２３のアドレスをＡＣＵ
内の適切なレジスタにセーブする追加ステップをとる。
プログラムのコンパイル時にＡＣＵレジスタ番号が割り
当てられたので、アドレスを図１３のＡＣＵ２２にセー
ブする過程の一環として、ＣＵ５３がＡＣＵバッファ番
号線２９を介して、アドレスがセーブされるＡＣＵレジ
スタの番号を送る。この番号はＡＣＵ２２によって復号
され、適切なレジスタが活動化されて、アドレスを受け
入れることができるようになる。同時に、このレジスタ
の有効ビットが有効になる。この特定の態様については
後でさらに詳しく述べる。現時点では、有効ビットはそ
のレジスタに関連する１つの１ビット・メモリ位置であ
ってよく、その高状態または低状態によって、そのアド
レスがまだ関連があって検査すべきか、それとももはや
有効ではなくて実際に消去すべきかを示すことができる
と言うにとどめておく。

【００６０】コンピュータがプログラムの実行を続ける
と、図１４のブロック１０８で、ある点で記憶・検査コ
マンドに遭遇する。記憶・検査コマンドに遭遇すると、
図１３のＣＵ５３は、適切な信号をＡＣＵ制御線２６を
介してＡＣＵ２２に送る。これは個別の制御線であり、
図１６の１２６に示されている。記憶・検査命令の実行
中に生成されたアドレスはＡＣＵに送られる。次にこの
アドレスが、図１５のブロック１０９でＡＣＵにセーブ
された消去されていないすべてのアドレスと突き合わせ
て検査される。記憶動作のために割り当てられたアドレ
スが、ＡＣＵ内にセーブされた有効な、ロード動作のど
のアドレスとも同じでない場合には、ＡＣＵによって信
号は生成されない（図１５のブロック１１０）。その結
果、コンピュータは、図１５のブロック１１２でプログ
ラムの順次実行を続けることになる。

【００６１】しかし、記憶動作のアドレスとＡＣＵにセ
ーブされている有効アドレスが一致する場合には、ＡＣ
Ｕによって信号が生成され（図１４のブロック１０
９）、図１３の線３０を介してＣＵ５３に送られる。

【００６２】アドレスが一致してＡＣＵによって信号が
生成されても、アドレスが一致せず信号が生成されなく
ても、後続の命令、すなわちＡＣＵ消去命令がＣＵから
ＡＣＵに送られる（図１５のブロック１１０）。このＡ
ＣＵ消去命令は、追加の記憶・検査コマンドと突き合わ
せて検査する必要のないすべてのレジスタを消去させる
（図１５のブロック１１８）。

【００６３】ここでＣＵの応答に戻ると、ＣＵは、図１
３の線３０を介して肯定アドレス検査信号を受け取る
と、記憶動作を完了せず、それを打ち切る。図１５の１
１１で、ＣＵはコンパイラが事前に準備した回復シーケ
ンスを実行する。この回復シーケンスの目的は、アドレ
ス間の一致によって生じた誤りから回復することであ
る。本発明の好ましい実施例では、回復プログラムは、
打ち切られた記憶動作を再実行し、次いでロード動作
と、最適化されていない形のプログラム中でこのロード
動作の後に続き、このロード動作に依存し、最適化の結
果として記憶動作の前に移された動作があればそれを再
実行する。この時点で回復シーケンスは終了し、コンピ
ュータは、割込み中の記憶・検査命令の直後に、コンパ
イルされ最適化されたプログラムの主シーケンスの実行
を再開する。

【００６４】このシナリオは、プログラムが実行され、
誤りまたは異常が発生する度に繰り返される（図１５の
ブロック１１３）。

【００６５】アドレス比較機構：上述のように、システ
ムの一部分は、アドレス比較機構（ＡＣＵ）と呼ばれる
特別の装置を含み、この装置は、新しい命令セット、改
良されたＣＰＵ、及びシステムの他の部分と共に動作す
る。この独特のＡＣＵ装置は、このシステム内で非常に
特有で重要な機能を果す。この新しい装置は、ロード・
セーブ・コマンドの実行時に順不同ロードによって取り
出されたオペランドのアドレスをセーブする。次いでセ
ーブ検査コマンドを実行して、そこに送られたアドレス
をそれがセーブしたアドレスと突き合わせて検査する。
前述のように、セーブされたアドレスと記憶・検査命令
の実行中に検査のために送られたアドレスが一致する場
合には、ＡＣＵ装置は信号を、上記のアドレス検査信号
線を介してＣＰＵに送る。次いで最後に、ＡＣＵ装置
は、セーブしてあったが、もはや検査用に必要でないア
ドレスを消去する。

【００６６】ＡＣＵの重要性は、セーブ及び記憶を行
い、記憶動作によって生成されたアドレスと、プログラ
ム・コンパイル中に記憶動作の前に移されたロード動作
によってセーブされたアドレスが一致することによる異
常の可能性があるかどうか検査しなければならないとい
う負担を、ＣＰＵから取り除くことである。このタスク
をプロセッサから分離した装置に割り当てることによっ
て、ＡＣＵは、プロセッサがより効率的かつ迅速に動作
できるようにする。プロセッサは上記のような動作を行
うためには設計されておらず、前述のように、非常に非
効率的にしかそれを行うことができない。

【００６７】ＡＣＵの好ましい実施例では連想メモリを
使用する。図１６にＡＣＵ／ＣＰＵインターフェースを
図示する。ＡＣＵ内のデータは、データ・バス２８によ
ってコネクタ３１を介してアクセスされ、データはアド
レス・バス２７を介してＡＣＵに送られる。ＡＣＵレジ
スタ番号線２９がＡＣＵに接続され、ＡＣＵ内の記憶位
置を選択する。ＡＣＵは、アドレス検査信号線３０を介
して、記憶・検査動作中に発生した異常をＣＰＵに信号
で知らせる。ここに記載する実施例では、ＡＣＵは、Ｃ
ＰＵの制御装置から来る４本の別々の制御線によって制
御される。これらは、ＡＣＵ消去線１２４、ロード・セ
ーブ線１２５、記憶・検査線１２６、及びＡＣＵ読取り
線１２７である。しかし、上記の好ましい実施例の趣旨
を理解すれば、当業者なら、本発明の概念から逸脱する
ことなくここに記載する概念を実施する方法が他にもあ
ることがわかるであろう。

【００６８】アドレスがセーブされるＡＣＵレジスタま
たはエントリを１２８に示す。このような各レジスタに
は、後で詳しく論じる有効ビット１２９が付随してい
る。最後に、各レジスタまたはエントリ１２８に制御ポ
ート１２０が付随している。制御ポートは、実際にレジ
スタへのアクセスおよびレジスタからのアクセスを制御
し、様々な制御線を介して送られてきた制御信号に応答
する。好ましい実施例ではこの制御ポートがどのように
設計できるかを示す１つの詳細な構成を、図１８に図示
する。これについては後で詳細に論じる。

【００６９】図１７は、ＡＣＵの１つの可能な好ましい
実施例の基本図であり、そのもっとも基本的な要素と接
続を図示してある。順不同ロード動作のアドレスがセー
ブされるレジスタ１２８は、好ましい実施例では１６個
から６４個までのどの数にすることもできる。ただし、
レジスタの数はこれより多くても少なくてもよい。各レ
ジスタ１２８に、有効ビット位置１２９が付随してい
る。有効ビット位置１２９は、付随するレジスタ内に含
まれるアドレスが関連するもので検査すべきか、それと
も関連がなく、そのレジスタがセーブすべき新しいアド
レスを受け取るために使用可能であるかを判定するため
に、システムがそこを見る。好ましい実施例では、レジ
スタ１２８にセーブされたアドレスが関連するもので検
査すべきである場合には、有効ビット１２９は２進値１
を含む。逆の場合は、有効ビット位置１２９は２進値ゼ
ロを含み、レジスタに含まれる情報が関連がなく、比較
すべきで使用可能なアドレスがないことを示すことにな
る。その場合、有効ビットは、ロード・セーブ動作中に
順不同ロードのアドレスがセーブされるまで「低」であ
り、セーブされると「高」になる。システムが、このア
ドレスの比較をそれ以上続ける必要がないと判断する
と、ＡＣＵ消去信号が実際に有効ビットを１からゼロに
変更し、レジスタを実際に消去する。図１７の各レジス
タ１２８は、それ自体の個別のポート１２０によって制
御される。図１８の破線内に、レジスタと有効ビット位
置の両方を制御するようにこのポートを構成する１つの
方法を示す。図１８に示す制御ポートについては後で詳
述する。

【００７０】図１７に戻ると、システムのアドレス・バ
ス２７は、制御ポート１２０を介してレジスタ１２８に
接続している。アドレス・バス２７からレジスタ１２８
へのアクセスは、各レジスタの制御ポート１２０によっ
て制御される。これによって、システムはセーブすべき
アドレスをＡＣＵのレジスタ１２８に転送することがで
きる。データ・バス２８とそのＡＣＵからの接続３１に
よって、システムは、コンピュータがそう望む場合、Ａ
ＣＵレジスタ１２８にセーブされたアドレスを検索する
ことができる。制御ポート１２０は、アドレス復号器１
３３によって制御され活動化される。アドレス復号器１
３３は、アクセスすべきレジスタのレジスタ番号をその
バッファ番号線２９を介してコンピュータから受け取
る。アドレス復号器１３３がバッファ番号線２９を介し
てレジスタ番号を受け取ると、このレジスタ番号は復号
され、次いで、アドレス復号器１３３を様々な制御ポー
トに接続する特定の制御線１３６を介して、アクセスす
べきレジスタ１２８の特定の制御ポート１２０を活動化
する信号が送られる。この信号は、この特定の制御ポー
ト１２０を活動化し、それが制御するレジスタに情報が
出入りすることを告げる。制御線２６は、どの動作を実
施すべきか、すなわちロード・セーブ動作か、記憶・検
査動作か、ＡＣＵ消去動作か、それともＡＣＵ読取り動
作かを各ポート１２０に指令する手段である。記憶・検
査動作中に、記憶動作に割り当てられたアドレスが、Ａ
ＣＵ１２０のレジスタ内に記憶されたアドレスの１つと
同じであると判定された場合、アドレス検査信号線３０
を介してプロセッサに信号が送られる。

【００７１】好ましい実施例で実施できる制御ポートの
ハードウェア実施態様を、図１８に示す。図１８の破線
内に示すハードウェア論理回路は、各レジスタまたはＡ
ＣＵテーブルの各エントリごとに複製され、制御ポート
を指定される。

【００７２】用語「テーブル」は、バッファと同義語と
して使用され、共に順不同ロード動作のアドレスがセー
ブされるＡＣＵ内のすべてのメモリ位置の総称である。
用語「レジスタ」及び「エントリ」も同義語として使用
され、共にロード動作によってセーブされたアドレスが
記憶されるＡＣＵ内の各個別メモリ位置をいう。

【００７３】図１８で、プロセッサがロード・セーブ・
コマンドを実行するとき、セーブすべきメモリ・アドレ
スがアドレス・バス２７上に置かれる。すなわち、書き
込まれるレジスタ番号またはＡＣＵテーブルのビットが
バッファ番号線２９上に置かれ、またＡＮＤゲート９１
への入力であるロード・セーブ・コマンド信号が、プロ
セッサの制御装置によって高にアサートされる。バッフ
ァ番号線２９の内容が、アドレス復号論理回路１３３に
よって復号され、バッファ番号線２９上のアドレスによ
って指定されたＡＣＵレジスタのＡＮＤゲート９１の第
２入力に接続された１つの出力上に、論理高信号が生成
される。論理低信号は、アドレス復号回路１３３の他の
出力上に生成され、バッファ番号線２９によって選択さ
れないＡＣＵレジスタ内の"ＡＮＤ"ゲート９１の入力端
に供給される。

【００７４】ＡＮＤゲート９１の２つの入力が上で定義
したようなものであるとすると、その出力はバッファ番
号線２９によって選択されたＡＣＵについてのみ、かつ
ロード・セーブ・コマンド信号がアサートされるときだ
け高となる。ＡＮＤゲート９１の出力は、ロード・セー
ブ・コマンドがアサートされたとき、メモリ・アドレス
・バス２７の内容を選択されたＡＣＵのレジスタ１２８
に記憶する、書込み開始信号として使用される。各ＡＣ
Ｕレジスタ内の有効ビット１２９に対応する「フリップ
・フロップ」８８は、レジスタ１２８が記憶・検査命令
中にアドレス・バス２７上に同報通信されるアドレスと
比較すべき有効ロード・アドレスを含んでいるかどうか
を示すために使用される。レジスタ１２８の内容とバス
２７上のアドレスの実際の比較は、ＸＮＯＲゲート８４
によって各マシン・サイクルで実施され、この両者がビ
ットごとに一致し、かつ「フリップ・フロップ」８８
が、レジスタ１２８の内容が有効であることを示す場合
には、高信号がＡＮＤゲート９４によってＯＲゲート９
５の入力端でアサートされる。線２７上のアドレスとレ
ジスタ１２８の内容が一致しないか、あるいはレジスタ
１２８の内容が「フリップフロップ」８８によって無効
であることが示された場合には、そのＡＣＵエントリか
ら"ＯＲ"ゲート９５への入力は低のままとなる。

【００７５】ＯＲゲート９５の出力は、有効ないずれか
のＡＣＵエントリがバス２７上で同報通信されるアドレ
スと一致する場合に高になり、この出力はＡＮＤゲート
９６の入力の１つに印加される。プロセッサは、記憶・
検査コマンドを実行しているとき、線１２６を論理高と
してアサートし、それがＡＮＤゲート９６の第２入力を
形成する。ＡＮＤゲート９６の出力は、線３０上のアド
レス検査信号であり、プロセッサにフィードバックされ
る。装置８４、９４、９５、９６、及び１２６の動作に
より、線３０上のアドレス検査信号は、プロセッサが記
憶・検査コマンドを実行中であり、かつ有効ＡＣＵエン
トリの１つがプロセッサによってアドレス・バス２７上
で同報通信されるアドレスと一致する場合にのみ、高に
アサートされる。

【００７６】有効ビット１２９の状態遷移は、ＮＡＮＤ
ゲート９０、ＡＮＤゲート８９、及びＯＲゲート８７に
よって制御される。これらを図１８に示す方法で相互接
続することによって、ＡＣＵレジスタの有効ビット１２
９は、それが前サイクルで高であった場合、またはロー
ド・セーブ・コマンドが前サイクルでそのエントリにあ
るアドレスを記憶した場合、またはそれが前サイクルで
高であり、かつこのＡＣＵレジスタへの有効ビットを消
去するためにＡＣＵ消去コマンドが前サイクルで実行さ
れなかった場合には、所定のサイクルで論理高になる。
言いかえれば、有効ビットは、それがオフのときは、ロ
ード・セーブ・コマンドによってオンにされるまでオフ
のままであり、オンになった後は、ロード・セーブ・コ
マンドによってオフにされるまでオンのままである。

【００７７】ロード・セーブ・コマンドは、所定のサイ
クルで１つのＡＣＵエントリのみの有効ビットに作用す
ることができ、このエントリはバッファ番号線２９によ
って選択される。しかし、ＡＣＵ消去コマンドは、所定
のサイクルで複数のＡＣＵエントリの有効ビットを消去
することができる。装置９２は、アドレス・バス２７か
らＡＣＵテーブル・エントリへのビットの直接的マッピ
ングである。ＡＣＵテーブル内のエントリの数がアドレ
ス・バス２７上のビットの数より少ないときには、１つ
のワードが、ＡＣＵ消去コマンドと共にアドレス・バス
を介して送られ、アドレス・バス上の異なるビットが異
なるＡＣＵテーブル・エントリを制御する。

【００７８】前述のように、各ＡＣＵ消去コマンドは、
レジスタまたはバッファ番号、または消去すべきレジス
タの数を含んでいた。レジスタまたはバッファ番号は、
最下位ビットから最上位ビットまでの範囲の１つまたは
複数のワード中の１つのビット位置に対応する。この１
つまたは複数のワードは、ＡＣＵ消去動作中にアドレス
・バス２７を介して送られる。各レジスタの番号はビッ
ト・マップ９２に対応し、どのレジスタを消去するかを
ＡＣＵに知らせる。

【００７９】ＡＣＵテーブル・エントリの数がアドレス
・バス上のビットの数より多いときには、複数のワード
がＡＣＵ消去コマンドと共にアドレス・バスを介して転
送され、各ＡＣＵメモリ位置に関連する装置９２がその
情報を復号し、事前に指定されたサイクルにアドレス・
バスを介して転送されたワードから有効ビットを選択す
る。

【００８０】本発明のコンピュータ・システムは、多重
プログラミング環境または多重タスク処理環境で使用で
きる。このシステムは、プロセッサが１つのプログラム
を実行できるようにし、ＡＣＵを利用できるようにする
能力を有し、割込みが行われて他のプログラムを実行す
るように要求されたとき、プロセッサは、そのレジスタ
の状態をセーブして後でそのプログラムの実行に戻れる
ようにするステップの一環として、信号すなわちＡＣＵ
読込み信号をＡＣＵに送り、ＡＣＵが、そのＡＣＵレジ
スタ内のアドレスをメモリ内の他の位置にセーブできる
ようにする。その後、コンピュータは、それに割り当て
られた新しいプログラムを実行し、または新しいタスク
に対して作業をすることになる。コンピュータは、その
タスクを完了するか、または割り込まれて別のプログラ
ムに進むときも、同じことを行う。次いで、最終的に
は、それが作業していた元のプログラムに戻る。そのと
き、プロセッサのレジスタが元の割込み時の状態に復元
されるだけでなく、ＡＣＵのレジスタまたはエントリ
も、元のＡＣＵ読取り命令を受け取った時の状態に復元
される。したがって、これによって、システムが、多重
プログラミング環境または多重タスク処理環境で異なる
複数のプログラムまたは適用業務に使用できるようにな
る。

【００８１】図１８に戻ると、プロセッサはＡＣＵ読取
りコマンドを実行するとき、ＮＡＮＤゲート８３の入力
の１つに印加されるＡＣＵ読取りコマンド線１２７をア
サートする。プロセッサはまた、それが読み取ろうとす
るＡＣＵレジスタのアドレスをバッファ番号線２９上に
置き、このアドレスは復号回路１３３によって復号さ
れ、次いで複方回路１３３が、読み取られるＡＣＵエン
トリまたはレジスタ内のＮＡＮＤゲート８３の第２入力
に高信号を印加し、他のＡＣＵエントリまたはレジスタ
内のＮＡＮＤゲート８３に低信号を印加する。この結
果、ＮＡＮＤゲート８３の出力は、選択されたＡＣＵレ
ジスタ内で低となり、そのエントリ内のレジスタ１２８
の内容を、ゲート８５を介し線３１を経てデータ・バス
２８に転送させる。データ・バスは３状態バスでなけれ
ばならない。したがって、ゲート８５は３状態ゲートで
ある。位置１２８からデータ・バスに転送されたアドレ
スはその後メモリに記憶される。

【００８２】下記は、システムがＡＣＵ読取り命令をど
のように使用するかの例である。プロセッサは、オペレ
ーティング・システムから異なるプログラムまたは適用
業務を実行したいとの要求を受け取ると、ＡＣＵの内容
をメモリにセーブするために、ＡＣＵ読取り信号をＡＣ
Ｕに送る。オペレーティング・システムからの信号は割
込みの形をとることもできる。プロセッサは、ＡＣＵ読
取り命令を用いて、（上記のように）それ自体のレジス
タの内容とＡＣＵバッファの内容を様々なメモリ位置に
セーブする。多重タスク処理システムまたは多重プログ
ラミング・システム内のオペレーティング・システム
は、これらの割込み信号を生成することができる。オペ
レーティング・システムは、プログラム実行に割込みを
かけ、割り込まれたプログラムのＡＣＵレジスタの内容
をメモリにセーブした後、ある時点でこのプログラムの
実行に戻ることができる。ＡＣＵへのアドレスの復元
は、コンピュータが、割込みが行われたプログラムの実
行を再開する前に取られる処置の１つである。ＡＣＵの
復元を行う方法はいくつかある。ＡＣＵレジスタをプロ
グラム割込み時の状態に復元するための、ある種のハー
ドウェア及びソフトウェア実施態様を作成することがで
きる。しかし、ＡＣＵレジスタを復元する比較的容易な
方法は、メモリにセーブされたアドレスをアドレス・バ
スを経てＣＰＵ内のレジスタに移し、次いでＣＰＵレジ
スタからアドレス・バスに沿って、プログラム割込み時
にこれらのアドレスが記憶されていたＡＣＵ内のレジス
タに移すことであろう。この操作は、間接ロード・セー
ブ動作を用いて一部実施することができる。当技術分野
で周知の方法によって割込みハンドラに適切な変更を加
えると、容易にこれを実施することができる。

【００８３】プログラム・シーケンスの実行中にＡＣＵ
のレジスタ中で何が起こるかの例を次に説明する。図１
１と図１９を参照する。開始時に、ＡＣＵのすべてのレ
ジスタ１２８が消去される（図１９）。図１１のプログ
ラム・シーケンスが実行されると仮定すると、命令行１
はＲ１３とＲ１５の加算であり、プロセッサによって実
行される。次に、プロセッサは図１１のプログラム命令
行２を実行する。これはロード・セーブ動作である。こ
れと同時に、メモリ位置１８（Ｒ１２）から適切な情報
をロードし、また図１９のＡＣＵ内のレジスタＡＲ１に
メモリ・アドレス１８（Ｒ１２）をセーブする。同時
に、レジスタＡＲ１の有効ビットＶ１が、ゼロから１に
変更される。次にコンピュータは、プログラムの次の
行、図１１の行３を実行し、ロード・セーブ命令の実行
の一環として、アドレス１０（Ｒ１２）をレジスタＡＲ
２にセーブする。同時に、コンピュータは、レジスタＡ
Ｒ２の有効ビットＶ２をゼロから１に変更する。コンピ
ュータは、図１１の命令行６に達すると、記憶動作を実
行し、ＣＰＵレジスタＲ１すなわち１１２（Ｒ１３）の
オペランドをメモリから取り出すために使用したアドレ
スを、図１９に示すＡＣＵのＡＣＵレジスタ中にセーブ
された２つのアドレスと比較する。プログラムの次の
行、図１１の行７で、ＡＣＵ消去命令が、レジスタＲ２
の有効ビットＶ１を１からゼロに変更することによっ
て、レジスタＡＲ１を基本的に消去する。このときコン
ピュータは、この特定のバッファを、図１９に示すよう
に消去されているものと見なす。コンピュータはまた、
このＡＣＵレジスタを、将来のセーブのために使用でき
るものと見なし、かつ、有効ビットがゼロのままである
限り、将来の記憶・検査動作中に無視できるものと見な
す。次いでコンピュータは、図１１に示すようにプログ
ラムの命令行８を実行する。それに応じて、コンピュー
タは、記憶動作のために生成されたアドレスを、ＡＣＵ
のレジスタと突き合わせて検査する。検査の際に、コン
ピュータには、レジスタは図１９に示すように見える。
すなわち、レジスタＡＲ２だけが有効アドレスを有する
と見なされるが、レジスタまたはエントリＡＲ２は正す
なわち高状態の有効ビットＶ２しか有さないので、この
有効アドレスを検査する必要がある。

【００８４】精巧なコンピュータ・システムへの適用：
本発明のシステムが広範な応用分野を有することは、当
業者には容易にわかるであろう。これは、「単一プロセ
ッサ」、すなわち一時に１つの命令しか実行しないプロ
セッサと共に使用する際に適用できるだけでなく、はる
かに精巧なシステムにも、またスーパーコンピュータに
おいてさえ使用可能である。これは、ＶＬＩＷ（非常に
長い命令ワード）またはスーパースカラ・コンピュータ
・システムでの使用に理想的に適している。スーパース
カラ・コンピュータとは、各マシン・サイクルで複数の
命令が実行され、より高い実行速度が得られるコンピュ
ータである。典型的には、スーパースカラ・コンピュー
タは、１マシン・サイクルで２個または４個の命令を実
行し、１マシン・サイクルで実行される命令は、整数演
算、浮動小数点数演算、ロード操作、分岐操作など異な
る種類のものである。ＶＬＩＷ型のコンピュータ・アー
キテクチュアは、各マシン・サイクル中に複数の命令が
実行される形のものである。ＶＬＩＷコンピュータは通
常、各マシン・サイクル中にもっと多くの命令を実行す
るように設計され、複数の命令は同じ種類のものとする
ことができる。場合によっては、ＶＬＩＷコンピュータ
はまた、単一のマシン・サイクル中に複数の分岐命令を
も扱う。明らかに、ＶＬＩＷアーキテクチュアまたはス
ーパースケーラ・コンピュータの使用時にメモリ待ち時
間を減らせるなら、実行の効率と速度の実質的な向上が
得られるはずである。本明細書で提案するシステムは、
こうしたより精巧なアーキテクチュアに適用すると、効
率と速度に関してさらに大きな利得をもたらすことにな
る。ＶＬＩＷマシン用のコンパイラとコンパイル処理に
ついてのすぐれた参考文献は、Ｊ・Ｒ・エリス（Elli
s）の博士論文"Bulldog: A Compiler for VLIW Archite
ctures", MITPress（1986年）である。

【００８５】本発明を精巧なコンピュータ・システムの
動作とともにどのように有益に使用できるかの例を次に
説明する。この例は、ＶＬＩＷアーキテクチュアとＩＢ
ＭシステムＳ３７０式のアセンブリ言語を使用するコン
ピュータ・システムに関するものである。これは、先に
図９、１０、１１、１２に示すプログラム・シーケンス
の説明で既に使用したものと同じアセンブリ言語であ
る。同じ元のプログラム・シーケンスを再度使用し、図
２０に示す。図２０の各プログラム行の詳細な説明につ
いては、図９に関する先の議論を参照されたい。

【００８６】図２０に示すコード・フラグメントでは、
目的は、できるだけ早くコード・フラグメントの実行を
完了することである。コンパイラには、命令中で指定さ
れたオフセットをレジスタＲ１２とＲ１３の内容に加算
することによって生成されたアドレスが同じかそうでな
いかを知る手段はないと仮定する。前述のように、この
最適化されたコード用の例示的マシンでは、１サイクル
に複数の３７０命令を実行できるＶＬＩＷアーキテクチ
ュアが使用されていると仮定する。ただし、変位を伴う
３７０式のロードまたは記憶は、さらに複数の１サイク
ル原始動作に分割される可能性があるが、上記の仮定は
例を簡単にするためである。ＶＬＩＷ命令における動作
は、前の命令からの利用可能なレジスタの古い値を用い
て、上述のように並列に実行され、コンパイラは、これ
らの動作が互いにデータ依存性をもたないことを保証す
る。同じ命令中の記憶動作、記憶・検査動作、及びＡＣ
Ｕ消去動作は、これらが特別のマルチポート・キャッシ
ュ・ハードウェア及びロード動作によって並列に実行さ
れても、命令中におけるそれらの発生順序で左から右に
順次実行される場合と同じ効果をもち、同じ命令中に同
じメモリ位置への同時記憶動作がある場合でも、前のＶ
ＬＩＷ命令からの利用可能なメモリ位置の古い値を読み
取る。これらの仮定は実施態様の詳細であるが、例を理
解するために必要である。

【００８７】ＡＣＵ機能なしでＶＬＩＷマシンによって
このコード・フラグメント上で得ることのできる最小実
行時間を、図２１に示し、以下に説明する。コンパイラ
は、図２１の行４すなわち命令ＬＲ２，１８（Ｒ１
２）が行３の命令ＳＴＲ１，１１２（Ｒ１３）と衝突
する可能性があると想定しなければならない。また行４
の命令は行５の命令ＳＴＲ３，１１６（Ｒ１３）と衝
突する可能性があると想定しなければならない。また、
行６の命令ＬＲ４，１０（Ｒ１２）が行５の命令ＳＴ
Ｒ３，１１６（Ｒ１３）と衝突する可能性があると想
定しなければならない。したがって、コンパイラはこれ
らの命令の順序を並べ換えず、その結果、プログラムは
図２１に示す形にコンパイルされることになる。したが
って、このコード実行の所与の例で同じ位置を参照する
ロード動作及び記憶動作がないときでも、すべての実行
に７サイクルかかることになる。

【００８８】しかし、ＡＣＵをＶＬＩＷマシンに組み込
むと、上記のコード・フラグメントを、図２２に示すよ
うに３サイクルでスケジューリングできる。このスケジ
ュールでは、ロード動作と記憶動作の間に衝突がないと
仮定する。この３サイクルのコード・フラグメント実行
中にＡＣＵによってロード動作と記憶動作の間の衝突が
検出された場合は、追加の５サイクルがＶＬＩＷマシン
によって回復コードで費され（図２３）、さらに割込み
オーバーヘッドがあるが、その大きさは実施態様に依存
する。したがって、ロード・アドレスと記憶アドレスが
衝突しない場合の頻度がやや高い場合には、ＡＣＵ機能
によってこのコードの実行時間が著しく短縮されること
になる。

【００８９】図２３に示す回復コードは、図１２に示す
ものと類似しているが、下記の点が異なる。すなわち、
マシンはＶＬＩＷマシンであるので、ＶＬＩＷ命令にお
ける記憶・検査動作がアドレス検査例外を引き起こすと
きは、その命令中のすべての動作が打ち切られ、回復コ
ードで実行されなければならない。したがって、図１２
に示す記憶・検査Ｒ１，１１２（Ｒ１３）命令の動作に
加えて、２つのＡＣＵ消去動作と"ＡＲ"動作が、図２３
の回復コード中で繰り返される。図２２に示すように、
同じ命令中に複数の記憶・検査動作がある可能性があ
る。図２２では、命令３中で２つの記憶・検査動作が発
生する。どの記憶・検査動作がアドレス検査例外を引き
起こすかには関係なく、実行される回復コードは、両方
の記憶・検査動作によって引き起こされた例外から回復
するために必要な動作を含んでいる。この手法は、同じ
命令中の異なる記憶・検査動作用に別々の回復コードを
生成するよりもかなり簡単であり、性能に対する影響は
無視できる。

【００９０】当業者には容易にわかるように、各サイク
ルで複数のロード・セーブ命令と記憶・検査命令を支援
するためのマルチポート式ＡＣＵは、前述の単一ポート
式ＡＣＵの簡単な拡張である。複数のポートを実施する
ために追加のハードウェアが必要となる。

【００９１】アドレス比較機構（ＡＣＵ）は、好ましい
実施例で述べた連想メモリ以外の方法を使って実施する
こともできる。連想メモリをもつ場合のように、各レジ
スタ／位置を備えた比較機構を設ける代わりに、読取り
ポート１個当り１つのマルチポート・レジスタ・ファイ
ルと１つの比較機構を使用することもできる。読取りポ
ートの数は、所望の性能目的を満たすように選択する。
その場合、余分にわずかなハードウェアを使用して、す
べての比較機構を重複なしに実際に使用されるすべての
ＡＣＵレジスタにアクセスさせることができる。この余
分のハードウェアが望ましくない場合には、レジスタ／
位置を、使用可能な比較機構の間で静的に区分すること
もできる。また時分割動作システムにおいてタイマー割
込み時にＡＣＵ内容をセーブし復元する必要がなくなる
ように、ＡＣＵ中に、異なるユーザ・プロセスに割り振
ることのできる複数のレジスタ・セットを準備すること
ができる。やはり本発明の範囲に含まれるＡＣＵのかな
り異なる実施態様は、セーブされるアドレスを生成する
命令が実行されるときに、実行時にセーブされるアドレ
ス用のＡＣＵレジスタを割り振ることである。これによ
ってコンパイラの実施が簡単になる。というのは、こう
するとコンパイラは、ＡＣＵレジスタの割振りと割振り
解除について気を使わなくてすむからである。その場
合、ＡＣＵはハードウェア・ハッシュ・テーブルとして
実施することができる。さらに、ＡＣＵ内の有効ビット
は、複数の値を表すことのできるタグ・フィールドで置
き換えることができる。非ゼロのタグ値は、有効エント
リを示す。またロード・セーブ・コマンドが、セーブさ
れるアドレスと共にセーブされるタグ値を指定すること
もできる。その後ＡＣＵ消去コマンドが、多くの方法の
１つで、タグ値の範囲（または１組のタグ値）を指定
し、この範囲（または組）内のエントリを単一コマンド
でＡＣＵから除去することができる。

【００９２】本発明の趣旨に反することなく性能向上の
ために、好ましい実施例で指定した特定の命令を修正す
ることができ、また追加の命令を加えることもできる。
好ましい実施例では、ＡＣＵ消去命令用のマスクは命令
自体の中で指定されている。主メモリに記憶されたマス
クを指すより小さな固定寸法の命令を実施することがさ
らに最適であろう。同様に、現在はＡＣＵ読取り命令を
使用してＡＣＵレジスタの内容を一時に１命令ずつ主メ
モリに移しているが、その代わりにベクトル移動型命令
を使用して、１命令中ですべてのＡＣＵレジスタのメモ
リへの転送を指定することもできる。この命令の性能
は、その内容をセーブしなければならないＡＣＵレジス
タを識別する（メモリ内の）ベクトル・マスクを指定す
ることによって、さらに最適化することができる。同様
に、ベクトル命令を使用して、単一の命令でＡＣＵの必
要なすべてのレジスタ／位置を復元することができる。
上記の命令の修正に加えて、新しい命令を追加すること
ができる。ＡＣＵが一致を見つけたとき、最適回復順序
を選択するのに、どのＡＣＵが一致をもたらしたかを知
ることが必要となる。ＡＣＵが、一致する位置のアドレ
スを記憶するための特別のレジスタを備え、ＣＰＵが、
特別の命令を使ってこのレジスタに照会することができ
る。複数の一致が発生する場合には、一致する位置の１
つのアドレス（多分、最下位）をＣＰＵに報告し、これ
とともに、追加の１ビット信号で、さらに一致する位置
があることを示すことができる。ＡＣＵがこのようなハ
ードウェア・サポートを持たない場合には、ＡＣＵ読取
りコマンドの、指定されたＡＣＵレジスタの内容を指定
のＣＰＵ汎用レジスタに転送するバージョンを備えるの
が有用であろう。

【００９３】また、本発明の範囲や趣旨を逸脱すること
なく、好ましい実施例で述べた回復機構を、多くの形で
修正することができる。例えば、ＣＰＵアーキテクチュ
アを、記憶・検査命令の実行によってＡＣＵ内で一致が
生じたときにだけセットされる、余分のビットを条件コ
ード・レジスタに含むように修正することができる。そ
の場合、ＣＰＵはこの条件コード・レジスタを他のＡＣ
Ｕコマンドと共に使用して正しい回復コードを選択する
ことができる。

【００９４】本発明を好ましい実施例に関して詳述した
が、本発明の範囲と趣旨を逸脱することなく形式と詳細
に様々な変更が可能なことが、当業者には理解できよ
う。

【図面の簡単な説明】

【図１】本発明のコンピュータ・システムの全容を示す
ブロック図である。

【図２】従来のオプティマイザの動作の流れ図である。

【図３】本発明の原理に従ったオプティマイザの動作の
流れ図である。

【図４】分岐動作における従来のオプティマイザの動作
の流れ図である。

【図５】分岐動作における本発明のオプティマイザの動
作の流れ図である。

【図６】本発明の改良されたコンパイラでコンパイルさ
れたコンピュータ・プログラムに現れる、命令セットの
４つの新しい命令のうちの３つの形式を示す図である。

【図７】改良されたコンパイラ内で動作するオプティマ
イザが本発明の教示に従ってプログラムをどのようにコ
ンパイルするかを示す流れ図である。

【図８】改良されたコンパイラ内で動作するオプティマ
イザが本発明の教示に従ってプログラムをどのようにコ
ンパイルするかを示す流れ図である。

【図９】コンパイルされず最適化されない形のコンピュ
ータ・プログラムのシーケンスの例である。

【図１０】本発明を使用せずにコンパイルされた図９か
らのコンピュータ・プログラムのシーケンスを示す図で
ある。

【図１１】本明細書に記載する改良されたコンパイラを
使ってコンパイルされた図１０からのコンピュータ・プ
ログラムのシーケンスを示す図である。

【図１２】図１１に示すコンパイル済みプログラム用
の、本発明の改良されたコンパイラによって生成される
回復コードの例を示す図である。

【図１３】図１より詳細な、本発明のコンピュータ・シ
ステム全体の概略図である。

【図１４】本発明によるコンパイルされたコンピュータ
・プログラムの、プロセッサによる実行を示す流れ図で
ある。

【図１５】本発明によるコンパイルされたコンピュータ
・プログラムの、プロセッサによる実行を示す流れ図で
ある。

【図１６】本発明のＡＣＵとＣＰＵの間のインタフェー
スを示す図である。

【図１７】ＡＣＵの構造全体を示す図である。

【図１８】ＡＣＵ内のメモリ・バッファを制御するポー
トの１つを、いくつかの回路とともに示す論理図であ
る。

【図１９】動作中のＡＣＵ内のレジスタの状態を示す図
である。

【図２０】コンパイルされず最適化されない形のコンピ
ュータ・プログラムのシーケンスを示す図である。

【図２１】本発明を使用せず、ＶＬＩＷコンピュータ上
で実行するためのコンパイル後の、図２０からのコンピ
ュータ・プログラムのシーケンスを示す図である。

【図２２】本発明を使用した、ＶＬＩＷコンピュータ上
で実行するためのコンパイル後の図２０からのコンピュ
ータ・プログラムのシーケンスを示す図である。

【図２３】図２２に示すコンパイルされた形のプログラ
ム用の、本発明を使用してコンパイラによって作成され
る回復コードを示す図である。

【符号の説明】

２１コンパイラ２２ＡＣＵ（アドレス比較機構）２３メモリ２４ＣＰＵまたはプロセッサ

───────────────────────────────────────────────────── フロントページの続き (72)発明者マノジ・クマールアメリカ合衆国10598、ニューヨーク州ヨークタウン・ハイツ、オーバールック・コモンズ２エイチ (56)参考文献特開昭54−150049（ＪＰ，Ａ) ＩＥＥＥＴＲＡＮＳＡＣＴＩＯＮＳＯＮＣＯＭＰＵＴＥＲＳ，38〜５！（1989−５．），Ｐ．663−678 (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06F 9/45 G06F 9/38 350 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims

(57)【特許請求の範囲】

【請求項１】プロセッサ（２４）と、それに付随してい
るコンパイラ（２１）と、前記プロセッサから命令を受
け取る、専用のアドレス比較装置であるＡＣＵ（２２）
と、を具備するシステムにおいてロード動作の実行効率
の向上を図る方法であって、前記付随するコンパイラによって対象となるプログラム
を最適化コンパイルする過程において、命令シーケンス
外に移動することによってそれと対となっているストア
動作より前に移動することのできるロード動作及び該ス
トア動作を検出し、前記ロード動作を前記ストア動作よ
り前に移動するステップと、最適化コンパイルされた前記プログラムを実行する過程
において、前記移動したロード動作により取り出された
オペランドのアドレスを前記ＡＣＵにセーブするステッ
プと、前記ＡＣＵが、前記セーブされたアドレスと前記対にな
っているストア動作を最適化コンパイルする過程におい
て生成されたアドレスを比較するステップと、前記比較の結果アドレスが相違していれば前記対になっ
ているストア動作を実行し、前記最適化コンパイルされ
たプログラムの実行を継続するステップと，前記比較の結果アドレスが同一であれば前記ストア動作
の実行を中断し、プログラムの回復を行うステップと、からなる方法。
【請求項２】前記回復を行うステップは、前記中断したストア動作実行を完了するステップと，その後前記ロード動作を実行し、それに後続する全ての
命令を最適化されていないプログラムの形式で実行する
ステップと、を含む請求項１の方法。
【請求項３】前記セーブされたアドレスを前記ＡＣＵか
ら異なったメモリに位置に移動することによって、異な
ったプログラムの実行を可能にするステップと、その
後、前記移動されたアドレスを連想メモリに戻し、前記最適
化コンパイルされたプログラムの実行を再開始するステ
ップと、をさらに含む請求項１の方法。
【請求項４】前記ロード動作を検出するステップは該ロ
ード動作をロード・セーブ命令に変更するステップを含
み、前記対になっているストア動作を検出するステップはス
トア動作をストア・チェック命令に変更するステップを
含み、前記セーブするステップは前記ロード・セーブ命令に応
答して実行され、前記比較するステップは前記ストア・チェック命令に応
答して実行される、請求項１の方法。
【請求項５】プロセッサ（２４）と、それに付随してい
るコンパイラ（２１）と、専用のアドレス比較装置であ
るＡＣＵ（２２）と、を具備するシステムにおいてロー
ド動作の実行効率の向上を図るシステムであって、前記付随するコンパイラによって対象となるプログラム
を最適化コンパイルする過程において、命令シーケンス
外に移動することによってそれと対となっているストア
動作より前に移動することのできるロード動作及び該ス
トア動作を検出し、前記ロード動作を前記ストア動作よ
り前に移動する手段と、最適化コンパイルされた前記プログラムを実行する過程
において、前記移動したロード動作により取り出された
オペランドのアドレスを前記ＡＣＵにセーブする手段
と、前記ＡＣＵが、前記セーブされたアドレスと前記対にな
っているストア動作を最適化コンパイルする過程におい
て生成されたアドレスを比較する手段と、前記比較の結果アドレスが相違していれば前記対になっ
ているストア動作を実行し、前記最適化コンパイルされ
たプログラムの実行を継続する手段と，前記比較の結果アドレスが同一であれば前記ストア動作
の実行を中断し、プログラムの回復を行う手段と、からなるシステム。