JPH04225431A - 命令キャッシュ効率を増大するコンピュータ命令をコンパイルする方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は命令キャッシュを使用す
るコンピュータ処理システムに関するものである。特に
、命令キャッシュ汚染と命令キャッシュ誤りを低減する
ように命令メモリ内の命令をコンパイルする方法が記載
されている。

【０００２】

【従来の技術】命令キャッシュの使用は高速プロセッサ
と命令メモリの低速アクセス時間との間の動作速度の不
一致を低減してきた。プログラム内の命令はキャッシュ
レジスタ内へ先取りされる命令のラインへグループ化さ
れる。実行されるべき特定の命令を確認するプログラム
カウンタに従って、プロセッサが命令を参照し且つ実行
する。参照された命令は命令キャッシュから実行のため
にプロセッサへ転送される。その命令キャッシュがその
プロセッサにより命令のラインの実行により利用できる
スペースを有する場合には、命令の付加的ラインが次の
利用できるバスサイクルの間にプログラムメモリから命
令キャッシュ内へ取り込まれる。

【０００３】これらの命令キャッシュ技術の効率は、次
に必要な命令の組を先取りすることに依存している。プ
ロセッサがキャッシュ内にない命令を参照する場合には
、誤りが生じ且つメモリサイクルが参照される命令を含
んでいるラインを先取りするために用いられる。命令は
プロセッサにより先取りされていない命令キャッシュ内
で先取りされてもよい。これらの命令が命令キャッシュ
に対する汚染を表現しており、他の必要な命令を記憶す
るためのスペースの総量を制限する。ライン内の幾つか
の命令のみがプロセッサにより参照される場合には、ラ
イン内に汚染が生じる。

【０００４】ほとんどの命令キャッシュは、完全なプロ
グラムを保持できるほど充分大きくはない。従って、キ
ャッシュに対する装荷過程が逐次的である場合には、常
に、条件付き命令文とプログラムループとがそのキャッ
シュ内にない命令の参照となる。必要な命令を含んでい
るラインの取り込みが生じる間に、これらの実行はシス
テムバスを煩わせるメモリアクセスを必要とし、従って
キャッシュの効率を減少させる。

【０００５】

【発明が解決しようとする課題】命令キャッシュの効率
を改善することが本発明の目的である。

【０００６】命令キャッシュの汚染を減少させることが
もっと詳細な本発明の目的である。

【０００７】起こりそうなキャッシュ誤り又はキャッシ
ュ汚染を減少させる順番でプログラム命令をコンパイル
することが、本発明の更にもう一つの目的である。

【０００８】

【課題を解決するための手段】本発明のこれらの及びそ
の他の目的は、命令キャッシュ効率を改善する順番でプ
ログラムのうちの命令をコンパイルする方法により与え
られる。そのプログラムはプログラム内の制御の非逐次
的な転送となる命令のために解析される。分岐命令文と
プログラムループとの存在が確認され、同時にこれらの
条件に対する命令実行過程が確認される。プログラムが
順番にコンパイルされ、それが少ししかないキャッシュ
誤り及び少ないキャッシュ汚染となる。

【０００９】この解析が命令のラインに、全ラインが実
行されるか又はライン内の全ての命令が実行されないか
のいずれかのように形成されることを許容する。従って
、部分的なラインの汚染は回避される。

【００１０】命令は部分的なライン汚染を回避するため
に、命令メモリ内に再位置付けされる。分岐命令は高い
可能性の目標命令が決定命令を引き継ぐように位置決め
される。命令のループは開始命令がラインの境界にある
ようにメモリ内に位置決めされる。

【００１１】この命令メモリ内の命令の再位置付けがメ
モリの細分化となる。使用されない記憶スペースがプロ
グラムの次の部分の間に実行されるべき重複命令を含ん
でもよい。

【００１２】

【実施例】図１は命令キャッシュ１３を使用している主
演算処理装置１１を図解している。この命令キャッシュ
１３は中央メモリ命令源１２ともっと非常に高速の主演
算処理装置１１との間のインターフェイスを与える。こ
の命令キャッシュ１３は主演算処理装置１１によるアク
セスのために中央メモリ命令源１２内に記憶される命令
のラインを先取りする。

【００１３】１９８３年にＲｅｓｔｏｎ　Ｐｕｂｌｉｓ
ｈｉｎｇ　Ｃｏｍｐａｎｙ，　Ｉｎｃ．　より発行され
たＡ．Ｖ．Ｐｏｈｍ及びＯ．Ｐ．Ａｇｒａｗａｈｌ共著
の書籍”Ｈｉｇｈ　Ｓｐｅｅｄ　Ｍｅｍｏｒｙ　Ｓｙｓ
ｔｅｍｓ”　から既知のように、そのような命令キャッ
シュが高速主演算処理装置１１と低速中央メモリ命令源
１２との間の見えない橋として働く。

【００１４】命令キャッシュ１３に関連する先取りプロ
セッサが中央メモリ１２内に記憶された命令のラインを
順次に先取りする。利用できるバスサイクルの間に、命
令の複数のラインが中央メモリ命令源１２から命令キャ
ッシュ１３へ移動される。主演算処理装置１１のプログ
ラムカウンタが必要な命令を参照する場合には、これら
の命令はその後主演算処理装置１１により実行すること
が可能となる。

【００１５】この種類のシステムでは既知のように、主
演算処理装置１１が命令キャッシュ１３内にない命令を
要求する場合には、キャッシュ誤りが生じる。この生じ
た誤りが次の利用できるバスサイクルにおいて、命令キ
ャッシュ１３が命令キャッシュ１３に対する誤りが生じ
た特定の参照された命令をアドレスすることを要求する
。

【００１６】中央メモリ命令源１２内の命令は命令のラ
イン内に組織される。ラインは命令キャッシュ１３へユ
ニットとして転送されるべき二つ又はそれ以上の命令を
含み得むことができる。主演算処理装置１１により参照
されたラインの個別の命令は命令キャッシュ１３からの
実行に対して利用できる。

【００１７】キャッシュ誤りの前述の問題は、中央メモ
リ命令源１２の特定の参照を要求することによりシステ
ムバスを煩わすので、要求された命令が利用できるよう
になるまで、主演算処理装置１１を停止する。命令の先
取りの間は、そのバスは主演算処理装置１１により実行
されることが必要なその他の業務を行うことができない
。その結果がシステム効率の低下となる。

【００１８】キャッシュ汚染とキャッシュ誤りとは、中
央メモリ命令源１２内のプログラムの命令を何時でもラ
インが実行されるように再位置付けすることにより低減
され得て、ラインの全ての命令が実行されるか又はライ
ンの命令の全ての命令が実行されないかのいずれかであ
る。それ故に、少なくとも全ての命令が少なくとも一回
は実行されることが保証される。

【００１９】ラインベース上の命令の取り込みは主演算
処理装置１１により参照されていないラインの幾つかの
命令を必ず生じ得る。その他の必要な命令のためのスペ
ースを侵害するキャッシュ内へ挿入される使用されない
命令を有することにより、これが命令キャッシュ１３の
汚染となる。

【００２０】プログラムが実行されているので、キャッ
シュ誤りと汚染結果とは完全に逐次的ではない。ループ
と条件付き命令文とに遭遇した場合には、主演算処理装
置１１は目標命令を参照するか又はループの最初へ帰り
、それが非逐次的実行となる。従って、命令が厳密に逐
次的なベース上に先取りされた場合には、これらの条件
がキャッシュ誤りを生じる。

【００２１】中央メモリ命令源に対するプログラム命令
の組織が、図２Ａに図式的に示してある。Ｂ１，　Ｂ２
，　Ｂ３及びＢ４は命令のブロックである。ブロックＢ
２とＢ３とは条件付き命令の通路である。条件付き命令
はブロックＢ１内に置かれて、試験された条件の結果に
応じて、プログラム制御がＢ２か又はＢ３かのいずれか
へ推移させる。マージング通路がブロックＢ４として分
岐Ｂ２とＢ３との各々に対して示してある。

【００２２】各ブロックを構成している命令がライン内
に配置され、そこで各ラインがそのブロックに対する二
つ又はそれ以上の命令を含み得る。図２Ａに図解したよ
うに、ブロックＢ１がこのブロックに対する命令を全て
含んでいるライン１と２との中に収容される。ブロック
Ｂ２はライン４と同時にライン３内に見出される命令を
含んでいる。ライン４はブロックＢ３の始まりを構成し
ている付加的な命令を含んでいる。同様に、ライン６は
ブロックＢ４に対する始まりの命令と同時にブロックＢ
３の命令を含んでいる。

【００２３】このプログラム構造は、真の（ｔｒｕｅ）
分岐Ｂ２が実行されるべき場合には、必要とされる６個
のライン１，２，３，４，６及び７となり、ブロックＢ
３を含んでいる偽の（ｆａｌｓｅ）　分岐が実行される
べき場合には６個のライン１，２，４，５，６及び７と
なる。真の分岐が取られる場合には、ライン３と４とが
先取りされて実行されないはずのブロックＢ３に属して
いる命令による汚染を含むことが明らかである。

【００２４】図２Ｂは真の分岐Ｂ２又は偽の分岐Ｂ３の
いずれかを実行するために取り込まれることが少しのラ
インしか必要でないようにコードを再位置付けすること
の効果を図解している。図２Ａにおいては、ライン４が
Ｂ２にのみ属する命令に制限される。ライン５と６とと
はＢ３にのみ属している命令を含んでおり、ライン７は
マージングブロックであるブロックＢ４に属している命
令を含んでいる。

【００２５】図２Ａの構造により５個のラインのみが、
即ちライン１，２，３，４，７のみが真の分岐Ｂ２に対
して取り込まれることが必要であり、５個のラインのみ
が、即ちライン１，２，５，６，７のみが偽の分岐Ｂ３
に対して取り込まれる必要がある。

【００２６】コードの再位置付けすることの結果として
中央メモリ命令源細分化の増加によりキャッシュ特性を
改善する。しかしながら、メモリ命令源１２内の空白メ
モリスペースの残りが、付加的数のメモリスペースを設
けるために安価ではあるが、少しのコストがかかるよう
に見える。

【００２７】中央メモリ命令源１２内のコードの再位置
付けすることは、先取り過程により妨害せず、且つ汚染
の減少と同じ実行をするために少ししか必要でないメモ
リサイクルとにより、キャッシュ特性での恩恵を満たす
。

【００２８】汚染とキャッシュ誤りとを低減するような
、コードを再位置付けするための方法論を与えるために
、キャッシュ汚染及び起こり得るキャッシュ誤りの源泉
を確認する制御フローグラフが用いられてもよい。

【００２９】この過程はそのプログラム内に含まれるプ
ログラムループと条件付き命令文とを確認する必要があ
る。純粋な逐次的命令実行順序から条件付き命令文の目
標命令、又はプログラムループからの始まりのループ命
令文への制御の変換を予想する再位置付けの規則が開発
された。

【００３０】さて、図３Ａ及び３Ｂを参照して、一般的
な再位置付け規則が決定され得て、その規則はループ実
行には伴われない命令のラインを先取りすることを回避
できる。プログラムループは一般に何回か実行され、高
い命令キャッシュ特性を達成することはこの実行の間は
基本的である。理想的には、このキャッシュは全体のル
ープ本体を保持するのに充分な大きさでありたい。しか
しながら、キャッシュ寸法制限が課せられているので、
これは普通は実際的ではない。キャッシュがマイクロ回
路内で履行され、且つキャッシュに対するスペースが制
限されている場合には、これは特に真である。

【００３１】図３Ａからわかるように、ライン１はブロ
ックＢ２に対する始まり命令と同時にブロックＢ１に対
する命令を含んでいる。それ故に、ブロックＢ２内に表
現されたループを実行する間に、ループがブロックＢ３
へ出ていく場合には、ライン１がライン２，３及び４と
一緒に存在することを要求される。ブロックＢ１に属す
るライン１内のそれらの命令は従ってキャッシュに対す
る汚染を構成する。

【００３２】図３Ｂに示した汚染のもう一つの源泉はラ
イン４であり、そのライン４はそのループが実行される
際に毎回先取りされなくてはならない。これらのループ
は一般に多数回実行されるので、キャッシュ汚染がブロ
ックＢ３からの連続的な先取り命令から生じる。

【００３３】さて図４Ａと４Ｂとを参照すると、キャッ
シュを汚染するのを回避するために再位置付けされた図
３Ａと３Ｂとの各ループが示されている。図４Ａにおい
て、ライン１はブロックＢ１からの命令のみを含んでい
る。このループはすっかりライン２と３と内の命令を有
するブロックＢ２に制限されている。最後に、ブロック
Ｂ３がライン４内で始まる。図４Ｂは図３Ｂのループの
同様な再位置付けを図解している。

【００３４】再位置付けがキャッシュに対する汚染と同
時に、主メモリの何らかの細分化に帰着することが認識
され得て、ここでライン１は命令により完全に占有され
ていない。しかしながら、プログラムのこの部分は普通
は一回だけ実行され、且つ複数回実行されるブロックＢ
２により確認されるプログラムの部分は、キャッシュ内
に汚染を与えない。ループの外側の汚染はそれ故にルー
プの実行の間の低いキャッシュ汚染と引換えにして増加
される。

【００３５】ループの再位置付けの結果は、その再位置
付けが１だけループにより占有されるキャッシュライン
の数を減少させる場合に、及びキャッシュラインサイズ
がもう一つのブロックに属しているラインを占有してい
るループの命令の数より大きい場合に、ライン境界で開
始するようにループが再位置付けされることを要求する
ように要約され得る。

【００３６】ループの再位置付けはループを実行するた
めに取り込まれるべき一つの小さいキャッシュラインに
帰着する。プロセッサがそのキャッシュ内に必要な命令
を見出さない場合に誤りを生じるラインが参照される場
合に、実行中のキャッシュの汚染は、バストラフィック
と同時にそれによって低減される。誤りの面倒を見るた
めに他方で必要とされるであろうその他の業務を成就す
るために、これがこのシステムを解放する。

【００３７】非逐次的命令実行系列を生じるその他の条
件は分岐命令に関連する。図５Ａ及び５Ｂに、図５Ａの
逐次的フォーマットから図５Ｂに示したような再位置付
けされたフォーマットへ、再コンパイルされた分岐命令
が示されている。各分岐がブロックＢ２とＢ３とを具え
ている。真の分岐Ｂ２が入られた場合には、この分岐の
実行はライン１，２及び３からの命令を含んでいる。ラ
イン３は偽の分岐を構成するブロックＢ３からの命令を
含んでいる。従ってこれらの付加的命令が命令キャッシ
ュへの汚染を構成する。図５Ｂはいかにしてこの汚染を
除去するかを図解している。

【００３８】最も実行されることがありそうな分岐に関
して評価がなされる。図５Ｂの例ではこれは真の分岐で
あるブロックＢ２である。ライン１，２及び３が全部の
分岐命令コードを含むように、命令コードが再位置付け
される。第２分岐Ｂ３がライン４により限定される境界
で真の分岐を直ちに引き継いで位置決めされる。

【００３９】図５Ａのライン５内に表現された汚染は、
分岐Ｂ３からの命令をブロックＢ４により確認されるマ
ージング通路と組み合わせることによっても、除去され
得る。 図５ＢはブロックＢ３に属している分岐命令をライン５
の境界上の終端へ局限することを図解している。

【００４０】前述の規則を用いた場合、図６Ａに示した
ように、分岐Ｂ２又はＢ３内に汚染を有することが可能
である。境界上の終端への各分岐に対する順番で、幾つ
かの空白スペースがライン４及び７に相当しているｅ１
及びｅ２により確認されるメモリ内に残される。これら
のスペースはブロックＢ４内に見出されるであろうコー
ドを重複するために用いられてもよい。ブロックＢ４か
らの命令のこれらのラインはブロックＢ２とＢ３とによ
り表現される各分岐の完成に続いて実行されるべきであ
るから、この重複はキャッシュを汚染しない。二つの通
路に沿って重複された命令の数は、最低可能な満たされ
ないスペースが、通路の一つに沿って残されるようでな
くてはならない。

【００４１】汚染を創造する命令を先取りすることを回
避するための付加的手順として、プログラムの実行を偏
移させる条件付き命令として、同じライン内に目標命令
を集めることができる。従って、各目標命令は条件付き
命令文の先取りによりきっと含まれている。

【００４２】主演算処理装置には見えないが、非逐次的
である命令を先取りするためにキャッシュプロセッサに
より実行される、主プログラムメモリの戦略的位置に命
令を記憶することも有利であろう。

【００４３】再位置付けコードが中央メモリ命令源１２
内でコンパイルされるような、命令コードの再位置付け
の恩恵を得るために、この方法はフローグラフをサブグ
ラフに分解し且つこのサブグラフに再位置付けの規則を
適用する手順を組み込み得る。図７に、再位置付けプロ
グラム命令へのこのフローグラフ接近法の基本的ユニッ
ト構造が示してある。この図解は、基本ブロックと、条
件付きブロック及びループブロックのようなプログラム
構造の三つの基本的形態を確認している。

【００４４】この基本ブロックは順次に実行され且つ汚
染の源泉あるいはキャッシュ誤りに対する可能性を与え
ないような命令を具えている。

【００４５】条件付き構造は二つの分岐の一方へ入るた
めの基本ブロックと、二つの分岐を合併させるための基
本ブロックとを含んでいる分岐命令を図解している。図
解されている第３のプログラム構造はループである。

【００４６】図８Ａに表現されているフローグラフから
、図８Ｂの再位置付けトリーが発展させられ得て、且つ
コードを再位置付けするために相当するアルゴリズムと
共に用いられ得て、それによって少ない汚染と少ししか
ないキャッシュ誤りとを生じる前述の再位置付けコード
の利益を得る。図８Ａのフローグラフを解析することに
よって、このプログラム内に多くの基本プログラム構造
が存在することが明らかになる。１２と１３として確認
される、このプログラムに対する二つの大きいブロック
構造がある。構造１２はブロックＢ３により確認される
ループをも含んでいる分岐ルーチンである。ブロックに
対して必要なラインの数も図８Ａ内に示してある。

【００４７】図８ＢのフローグラフがＵ１とＵ２として
二つの主ノードを確認する。Ｕ２はループであるブロッ
クＢ５を具えている。

【００４８】Ｕ１は条件付き分岐１２を具えている全て
のブロックを含んでいる。図８Ｂに示したように、これ
が主ノードＵ１の別の子ノードに分解され得る。二つの
逐次的ブロックＢ１とＢ４とがブロック１２内の二つの
分岐Ｂ２とＢ３と一緒に確認される。かくしてフローグ
ラフとそれの再位置付けトリーを診断して、以下の工程
が種々のブロックを再位置付けするために取られ得る。 再位置付け（Ｕ）｛ｕ１，…ｕｎ　をＵの子ノードとす
る（ｉ＝１；ｉ≦ｎ；ｉ＋＋）ループに対して｛若しｕ
ｉ　が基本ブロックである場合には再位置付けは必要で
ない代わりにｕｉ　がループである場合には｛再位置付
け（ループ本体）；“ループ再位置付け規則”をｕｉ　
に適用｝代わりにｕｉ　が条件付き命令文である場合に
は｛再位置付け（真の分岐）；再位置付け（偽の分岐）
；“発散再位置付け規則”をｕｉ　に適用；“集束再位
置付け規則”をｕｉ　に適用｝代わりに再位置付け（ｕ
ｉ　）｝｝

【００４９】前述の再位置付け方法を履行した結果がＢ
１を再位置付けが必要でない基本ブロックとして認識す
る。Ｂ２は真の分岐に相当する条件付き分岐であるから
、前述の原理に従って図９Ａと９Ｂとに示したように再
位置付けされ、ここでＢ２に対する命令を含んでいるラ
インはその他の分岐Ｂ３に対する命令を含んでいない。 キャッシュラインサイズは１０命令であるように示され
ており、従って二つの空白命令によりＢ２をＢ３から分
離している。この例においては、キャッシュラインサイ
ズが４であることが示されている。

【００５０】各ブロックについて続けることにより、分
岐Ｂ３がＢ２からの次のライン間隔上で続いて、ブロッ
クＢ５により表現されるループがライン境界で始まるよ
うに再位置付けされることがわかる。

【００５１】プログラムを再位置付けし且つコンパイル
するためのフローグラフ解析への代わりの接近法として
、再位置付けは制御依存グラフを用いて達成され得る。 制御依存グラフを用いると、それの実行が真であるべき
同じ制御条件を必要とする命令文から成る領域へ、プロ
グラムが分割される。制御領域内の命令文が実行される
場合には、その命令文は制御領域内の残りの命令文であ
る。従って、キャッシュが同じ制御領域の命令文からの
命令のラインを含んでいる場合には、キャッシュ汚染は
絶対にあり得ない。制御依存グラフは制御フローグラフ
に従った再位置付けよりも小さいキャッシュ汚染を潜在
的に提供できるプログラム再位置付けに帰着することが
できる。図９Ａ及び９Ｂは制御フローグラフ解析がキャ
ッシュ汚染を除去するのを失敗した二つの状態を図解し
ている。図９Ａにおいては、ライン１内の汚染が両ブロ
ックＢ１とＢ２とに対する命令を含むことにより生じる
。前述の制御フローグラフ解析はこの汚染の源泉を除去
しない。しかしながら、制御依存グラフ技術を用いるこ
とにより、Ｂ１とＢ４とは同じ制御領域に属しているか
ら、二つのブロックからの命令の分類はキャッシュ汚染
を生じないことが認識できる。付加的なキャッシュ汚染
が、図９Ａにおける基本ブロックＢ２の終端で用いられ
ないメモリ位置により生じる。前述の技術を用いてはこ
れも除去されない。

【００５２】図１０Ａ　及び１０Ｂ　の各プログラム構
造に対する制御依存グラフが図１１Ａ　及び１１Ｂ　に
示してある。この制御依存グラフは同じ制御領域にある
プログラム構造を図解している。適当な分岐命令が導入
された場合には、命令は所定の領域のブロックの間を前
後に動かされ得る。例えば、Ｂ４からの命令がブロック
Ｂ１からの命令のラインと共に含まれる場合には、条件
付き命令文はＢ４に対するあらゆる命令を実行する前に
全てのＢ１命令が実行されることを確信することを含ま
れている。制御依存グラフを用いたコードを再位置付け
する方法は、制御データグラフの最低レベルにおける領
域に相当する一番奥の命令文が最初に処理される制御フ
ローグラフに用いられる方法に類似している。領域に対
するコードがラインの整数と合致せず、且つそのような
コードを達成しようと試みる場合には、整数のライン内
の合致はコード移動によって達成される。

【００５３】その他の再位置付け技術は、全ての分岐目
標が同じライン内へ先取りされるような分岐命令の二つ
の通路の命令を再位置付けすることを含み得る。それ故
に、毎回キャッシュラインが取り込まれ、そのキャッシ
ュラインが両通路に対する命令を含んでいる。

【００５４】再位置付け命令コード内に、細分化された
メモリキャッシュ指令のメモリスペースが含まれ得る。 キャッシュ指令はキャッシュ制御器のみに見え、且つそ
の他は予想される命令を直接取り込む特別の命令である
。

【００５５】かくして、中央メモリ内の命令コードを有
効に再位置付けし且つコンパイルするための技術が説明
された。再位置付け命令コードが、命令キャッシュ先取
りルーチンを変更することなく、小さい命令キャッシュ
汚染と少ししかないキャッシュ誤りに帰着する。この技
術に熟達した人々は添付の特許請求の範囲によりもっと
詳細に説明した更に他の態様をも認識できるであろう。

【図面の簡単な説明】

【図１】図１は命令キャッシュを用いるコンピュータ処
理システムの図解である。

【図２】図２Ａは命令ブロックを具えた命令のラインへ
のコンピュータプログラムの編集をを図解している。図
２Ｂは図２Ａの編集よりも少ない汚染を生じるラインへ
の図２Ａの再位置付けされた命令を図解している。

【図３】図３Ａと３Ｂとはプログラムループを形成して
いる命令の編集を図解している。

【図４】図４Ａと４Ｂとはループにより占有されるキャ
ッシュラインの数を減少するための図３Ａと３Ｂとのル
ープ命令の再位置付けを図解している。

【図５】図５Ａと５Ｂとはキャッシュ誤りを回避し且つ
キャッシュ汚染を減少するための分岐命令の編集と分岐
命令の再位置付けとを図解している。

【図６】図６Ａと６Ｂとは再位置付けされた分岐命令の
編集と細分化されたメモリセル内に挿入される重複コー
ドとを図解している。

【図７】図７はフローグラフの基本ユニットを図解して
いる。

【図８】図８Ａと８Ｂとはフローグラフと再位置付けア
ルゴリズムを発生するための相当する再位置付けトリー
とを図解している。

【図９】図９Ａと９Ｂとは図８Ａの再位置付けコードと
中央主メモリ内のそれの記憶装置とを図解している。

【図１０】図１０Ａ　と１０Ｂ　とは制御依存グラフを
用いて再位置付けされるべきプログラム構造を図解して
いる。

【図１１】図１１Ａ　と１１Ｂ　とは制御依存グラフを
図解している。

【符号の説明】

１〜８　　ライン １１　　主演算装置 １２　　中央メモリ命令源 １３　　メモリキャッシュ Ｂ１〜Ｂ５　　ブロック

Claims (15)

【特許請求の範囲】
1. 【請求項１】　　記憶されたプログラム命令を実行する
   コンピュータ処理システムにおいて、前記プログラム命
   令の実行の順を決定する工程と、グループに従って前記
   プログラム命令をプログラムメモリ内に記憶する工程と
   を具えた命令キャッシュ特性を改善する方法であって、
   各グループは順次に実行する複数の命令を含んでおり、
   前記記憶工程はグループが命令キャッシュ内へ読み込ま
   れた場合にそのグループはキャッシュラインの境界で始
   まり、且つそのグループがキャッシュラインの整数に相
   当する長さを持たない場合には記憶位置がそのグループ
   の終端での位置調整情報を記憶するようにプログラムメ
   モリ内にグループを位置決めする工程を具えていること
   を特徴とする、命令キャッシュ効率を増大するコンピュ
   ータ命令をコンパイルする方法。
2. 【請求項２】　　位置調整情報は空白スペースであるこ
   とを特徴とする、請求項１記載の命令キャッシュ効率を
   増大するコンピュータ命令をコンパイルする方法。
3. 【請求項３】　　位置調整情報が継承するグループから
   の命令情報を具えていることを特徴とする、請求項１記
   載の命令キャッシュ効率を増大するコンピュータ命令を
   コンパイルする方法。
4. 【請求項４】　　前記グループが条件付き分岐命令内の
   条件の評価により到達できる命令の系列を具えているこ
   とを特徴とする、請求項１記載の命令キャッシュ効率を
   増大するコンピュータ命令をコンパイルする方法。
5. 【請求項５】　　前記グループが同じループ内に命令を
   具えていることを特徴とする、請求項１記載の命令キャ
   ッシュ効率を増大するコンピュータ命令をコンパイルす
   る方法。
6. 【請求項６】　　前記決定する工程が前記プログラム命
   令を具えている源泉コードコンパイラーにより実行され
   ることを特徴とする、請求項１記載の命令キャッシュ効
   率を増大するコンピュータ命令をコンパイルする方法。
7. 【請求項７】　　条件付き分岐命令の評価が第１の結果
   を与えた場合には前記グループの最初のグループが到達
   できる命令を具え、条件付き分岐命令の評価が第２の結
   果を与えた場合には前記グループの第２のグループが到
   達できる命令を具え、且つ前記位置決めする工程が、前
   記第１のグループが命令キャッシュ内へ読み込まれた場
   合に第１グループが第１キャッシュライン境界で始める
   ようにプログラムメモリ内に第１グループを位置決めす
   る工程と、前記第２のグループが命令キャッシュ内へ読
   み込まれた場合に第２グループが第２キャッシュライン
   境界で始め、その第２キャッシュライン境界は第１グル
   ープの終端の後にあるように、プログラムメモリ内に第
   ２グループを位置決めする工程とを具えていることを特
   徴とする、請求項１記載の命令キャッシュ効率を増大す
   るコンピュータ命令をコンパイルする方法。
8. 【請求項８】　　条件付き分岐命令の先取りの後に、第
   １グループと第２グループとを命令キャッシュ内へ一緒
   に先取りする工程を更に具えていることを特徴とする、
   請求項７記載の命令キャッシュ効率を増大するコンピュ
   ータ命令をコンパイルする方法。
9. 【請求項９】　　条件のもっと適当な評価を表現するた
   めに前記第１グループを選択する工程を更に具えている
   ことを特徴とする、請求項７記載の命令キャッシュ効率
   を増大するコンピュータ命令をコンパイルする方法。
10. 【請求項１０】　　第１グループの終端と第２グループ
    の始まりとの間に、第１グループか第２グループかのい
    ずれかの実行の後に、自動的に続く命令を位置決めする
    工程を更に具えていることを特徴とする、請求項７記載
    の命令キャッシュ効率を増大するコンピュータ命令をコ
    ンパイルする方法。
11. 【請求項１１】　　前記決定する工程と記憶する工程と
    が源泉コードコンパイラーにより実行され、前記決定す
    る工程が前記コンピュータプログラム内の命令のブロッ
    クを確認する工程であって、そのブロックはループか、
    条件付き分岐を評価の結果として到達できるグループか
    、又は逐次的な命令の基本的ブロックかのうちの個別の
    一つを各々が構成する工程と、前記コンピュータプログ
    ラムのフローグラフと同等な表現を形成する工程であっ
    て、そのフローグラフは前記確認されたブロックの各々
    を表現するノードの系列と、前記ブロック内に含まれる
    ブロックを確認するサブノードの系列とを具える工程と
    を更に具え、前記位置決めする工程が位置決めする命令
    が命令キャッシュ内へ装荷された場合に各ノードがキャ
    ッシュライン境界で始めるように、プログラムメモリ内
    にノードに相当する位置決めする命令を更に具えている
    ことを特徴とする、請求項１記載の命令キャッシュ効率
    を増大するコンピュータ命令をコンパイルする方法。
12. 【請求項１２】　　前記決定する工程と記憶する工程と
    が源泉コードコンパイラーにより実行され、前記決定す
    る工程は、各領域が実行するために真であるべき同じ条
    件を必要とする命令を含んでいる領域に前記プログラム
    を分割する制御依存グラフに等価な表現を形成する工程
    を更に具え、前記位置決めする工程は、位置決めする命
    令が命令キャッシュ内へ装荷された場合に各領域がキャ
    ッシュライン境界で始めるように、プログラムメモリ内
    の領域に相当する命令を位置決めする工程を更に具えて
    いることを特徴とする、請求項１記載の命令キャッシュ
    効率を増大するコンピュータ命令をコンパイルする方法
    。
13. 【請求項１３】　　前記決定する工程と記憶する工程と
    が源泉コードコンパイラーにより実行され、その記憶す
    る工程はその組み合わされた命令が命令キャッシュ内へ
    読み込まれた場合に、それらがキャッシュライン境界で
    始めるように、条件付き分岐命令文の目標命令に属して
    いる命令を組み合わせる工程を更に具えていることを特
    徴とする、請求項１記載の命令キャッシュ効率を増大す
    るコンピュータ命令をコンパイルする方法。
14. 【請求項１４】　　記憶されたプログラム命令を実行す
    るためのコンピュータ処理システムにおいて、命令キャ
    ッシュ特性を改善する方法が前記プログラム命令の実行
    の順序を決定する工程と、そのグループの内の少なくと
    も一つが飛び越し入力点により始めるグループに従って
    プログラムメモリ内へ前記プログラム命令を記憶する工
    程とを具えており、前記記憶する工程は各非終端グルー
    プの出発点と次のグループの出発点との間の距離がキャ
    ッシュメモリ内の連続するライン間の距離の整数倍にな
    るようにそのグループをそのプログラムメモリ内に位置
    決めする工程と、そのグループが整数のキャッシュライ
    ンに相当する長さを有しない場合にはグループの終端に
    位置調整情報を記憶する工程とを具えていることを特徴
    とする、命令キャッシュ特性を改善する方法。
15. 【請求項１５】　　前記命令に対するプログラム実行過
    程を確認するデータ依存の存在のために前記命令キャッ
    シュ内の各ラインを試験する工程と、前記実行過程に従
    って前記命令を先取りする工程とを更に具えていること
    を特徴とする、請求項１１又は１２記載の命令キャッシ
    ュ効率を増大するコンピュータ命令をコンパイルする方
    法。