JPH0355634A - キャッシュ再ロード・オーバーヘッドを減少させる方法およびコンピュータ・システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明は一般に高性能データ処理システムにおけるキャ
ッシュ・メモリ管理に関し、具体的には、プログラムの
フットプリント（足跡）が小さくなるとき、コンテキス
トを交換するための交換点を適時に選択することにより
、コンテキスト交換点でのキャッシュ・ミスのコストを
減少させる手法に関する。

Ｂ．従来の技術 多重プログラム式または多重タスク処理コンピュータ・
システムでは、１台のプロセッサが、そのプロセッサで
走行するプログラムまたはタスクを定期的に変更するこ
とにより、多くの異なるプログラム間で共用される。キ
ャッシュ・メモリを使用するコンピュータ・システムで
は、１つのプログラム′またはタスクが中断されて別の
ものが開始される時点で、キャッシュは、中断されたプ
ログラムに属する多くの行（ライン）を含んでいる。こ
れらの行は次のプログラムが走行するとき、キャッシュ
から取り除かれ、中断されたプログラムがプロセッサの
制御を再び得るとき、それを再ロードしなければならな
くなる。これらの行を再ロードするためのオーパヘッド
は、キャッシュ再ロード・トランジエントと呼ばれる。

Ｄ．Ｆ．ティボー（Ｔｈｉｅｂａｕｔ）とＨ．Ｓ．スト
ーン（Ｓｔｏｎｅ　）は、論文「キャッシュのフットプ
リント（Ｆｏｏｔｐｒｉｎｔｓｉｎ　ｔｈｅ　Ｃａｃｈ
ｅ）　Ｊ　ｓ　　Ａ　Ｃ　ＭＴｒａｎｓａｃｔｉｏｎ　
ｏｎ　Ｃｏｍｐｕｔｉｎｇｓ　　Ｖ　ｏ　１　．５％　
　Ｎ　ｏ　．４　（１９８７年１１月）、ｐ１）．３０
５−３２９に、この問題についての彼らの研究を報告し
、様々なケース・スタディで彼らが確認したトランジエ
ントのサイズを計算するためのモデルを提案している。

そのトランジエントのサイズは、プログラムのフットプ
リントのサイズ、すなわちプログラムがキャッシェ中に
もつ活動行の数に関係している。

できるだけ変更を小さくすることによってコンテキスト
交換のコストを減らしたり、あるいは他の方法でコンテ
キスト交換のオーバヘッドを減らすことが従来技術で知
られている。ただし、従来技術では、交換要求が出され
たときにコンテキスト交換を行なわなければならないと
仮定している。

米国特許第４４２２１４５号明細書は、将来のデータ要
求に関する知識を利用して、バッファ・メモリ内のペー
ジのプールを管理することを記載している。その方法で
は、この知識を使って、将来出される可能性が最も大き
い要求を迅速に検索できるパッファ・プールに保持する
。この発明は、ページをタスクに割り振る問題を解決す
ることを目的とするものである。

米国特許第４４８３４２４号明細書は、上記の特許第４
４２２１４５号の発明に類似した発明を記載しているが
、細部で異なっている。この発明では、タスク挙動を測
定して、キャッシュ・メモリ・ミスの数を減少させるに
はメモリを個々のタスクにどら割り振ればよいかを決定
する。しかし、キャッシュ・メモリに対する要求は、受
信された順序で処理される。

米国特許第４４８４２７４号明細書は、割込みが発生し
たとき、あるプロセスの状態のどの部分を実際にセーブ
する必要があるかを識別する処理手順を記載している。

すなわち、ある割込みが処理されるものとすると、この
処理手順は、できるだけセーブする個所を少なくしよう
とする。米国特許第４３８２２７８号明細書では、作業
空間を切り替えることにより、コンテキスト交換オーバ
・ヘッドを減らす方法を教示している。これによって、
コンテキスト交換時の作業の量が減少する。

Ｔ．Ｇ．ラング（Ｌａｎｇ）　は、ＩＢＭテクニカノレ
・ディスクロージャ・ブルテン、１９８６年７月、ｐ．
９４７で、コンテキストをセーブするプロセスに関連す
るオーパヘッドを減少させることにより、コンテキスト
交換の速度を高める手段を記載ている。

Ｃ．発明が解決しようとする課題 本発明の目的は、プログラムが中断可能となる時を注意
深く選定することにより、キャッシュ再ロード・トラン
ジエントのオーバーヘッドを減少させる方法を提供する
ことにある。

本発明の他の目的は、現タスクのフットプリントが小さ
いときにすなわちキャッシュにストアされている行数が
少ないときにコンテキスト交換を実施する方法を備えた
、多重タスク処理コンピュータ・システムを提供するこ
とである。

Ｄ．課題を解決するための手段 本発明によれば、多重プログラミングまたは多重タスク
処理環境で走行するプログラムの中断を、中断されるプ
ログラムまたはタスクのフットプリントが比較的小さい
ときに行なわせる。フットプリントが小さくなるのは、
そのプログラムが異なる動作段階に移動したため、ある
プロセスがキャッシュ内のデータまたは命令記憶域を解
放するときである。具体的には、本発明は、小フットプ
リント点で発生するように準備された割込み、及びこウ
した点がいつ発生するかを検出する手段に関するもので
ある。

本発明は、上記のものを含めて他の従来技術のシステム
でも、またそれらのシステムなしでも実施でき、多重プ
ログラム式または多重タスク処理コンピュータ・システ
ムの動作をさらに向上させることができる。本発明は、
上記の特許第４４２２１４５号の発明が、コンテキスト
交換のコストを減少させるために要求を据え置くという
考えを含んでいない点で、その発明とは異なっている。

要求は、プロセッサに提示された順に処理され、メモリ
管理は、受け取った要求及び将来予期される要求の結果
として実行される。上記の特許第４４８３４２４号の発
明は、ミスの数を減らすためにこうした要求を据え置い
たり順序を変えたりしない。上記の発明は、メモリ資源
に対する要求のシーケンスに応答してメモリ資源を管理
するが、本発明では、低コストで処理できるようになる
まで要求を据え置く。また、上記の特許第４４８４２７
４号、第４３８２２７８号、ラングの論文はどれも、本
発明の基本概念であるコンテキスト交換をいつ行なうか
に関するものではない。

すなわち、現況技術では、コンテキスト交換が開始され
るのは、プログラムがその割り振られた時間量子を越え
るとき、またはプログラミングされた待機もしくは入出
力動作に達したとき、あるいは他の同様の理由による。

本発明では、２つの時間がそれに関連している点で通常
の量子時間切れ割込みとは異なる、コンテキスト交換割
込みを組み込む。最初の時間は、コンテキスト交換が準
備される時を告げる最小時間である。この最小時間が経
過するまで、割込みは通知できない。最小時間の後、コ
ンテキスト交換割込みが準備され、プログラム・フット
プリントのサイズが減少したことを示す信号を受け取っ
たとき、それが通知される。

コンテキスト交換に関連する第２の時間は最大時間であ
る。最大時間に達するまでにコンテキスト交換割込みが
通知されない場合、その時点でコンテキスト交換割込み
が通知される。すなわち、コンテキスト交換割込みは、
プログラムが、余り長く走行できないようにする点で量
子時間切れ割込みに似ているが、また将来のオーバヘッ
ドが下がるようなときにプログラムを交換する傾向があ
る。

Ｅ．実施例 汎用コンピュータは、通常オペレーティング・システム
と呼ばれる実行制御プログラムの制御下で走行すると言
われる。オペレーティング・システムとは、コンビエー
夕のハードウェアを制御する、ソフトウェア、ファーム
ウェア、マイクロコードまたはこれら３つの組合せで実
施されるプログラムである。オペレーティング●システ
ムは、コンピュータ上で走行するアブリケーシロン・プ
ログラムまたはタスクからの呼出しに応答して、データ
を表示画面に書き込み、データをディスク記憶ＨＩ！に
記憶し、データをディスク記憶装置から検索し、リポー
トを印刷する。アプリケーシ式冫・プログラムまたはタ
スクは、オペレーティング・システム上で走行すると言
われる。本明細書では、プログラムとタスクは、同じ意
味で使用し、アブリケーシーン・プログラムを意味する
ものとする。

本発明は、Ｈ．ローり冫（Ｌｏｒｉｎ）及びＭ．Ｍ．デ
ィテル（Ｄｅｉｔｅｌ　）の著書「オペレーティング・
システム（Ｏｐｅｒａｔｆｎｇ　Ｓｙｓｔｅｍ）　Ｊ　
、アジソン・ウェズリー出版社（Ａｄｄｉｓｏｎ−Ｖｅ
ｓｌｅｙ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏ．）、１９８１
年刊、！）！）．８１−８８の第３．６節「多重プログ
ラミング●システム（Ｍｕｌｔｉｐｒｏｇｒａ＋ｕ＋−
ｉｎｇ　Ｓｙｓｔｅ鵬ｓ）　Ｊ　ｓ及びハーヴエイ（Ｈ
ａｒｖｅｙ）　Ｍ．ディテル（Ｄｅｉｔｅｌ　）の著書
「オペレーティング・システム入門（Ａｎ　Ｉｎｔｒｏ
ｄｕｃｔｉｏｎ　ｔｏ　ＯｐｅｒａｔｉｎｇＳｙｓｔｅ
ｍ）　Ｊ　、アジソン・ウェズリー出版社、１９８４年
刊、ｐｐ．１５５−１７４の第７章「実記憶装置（Ｒｅ
ａｌ　Ｓｔｏｒａｇｅ）　Ｊに一般的に記載された形式
の多重ブログラ【ング・システムの分野におけるもので
ある。本明細書では、多重プログラミングと多重タスク
処理は同じ意味に使用する。

本発明の好ましい実施例では、多重プログラムまたは多
重タスク処理コンピュータ・システムの通常動作モード
は、実行制御プログラムまたはオペレティング・システ
ムの制御下で動作するものと仮定する。オペレーティン
グ・システムは実行可能タスクのリストを維持する。オ
ペレーテイング・システムは、実行可能タスクのリスト
から直ちに実行すべきタスクを選択し、選択したタスク
に最大実行時間を割り振り、その時点で将来発生する割
込みを投定する。この最大時間を時間量子と呼ぶ。次に
、オペレーティング・システムは選択したタスクの実行
を開始する。選択されたタスクは、それに割り振られた
時間量子の間実行され、その時間が経過すると、割振り
が発生してタスクが中断される。次に、オペレーティン
グ・システムは、実行可能タスクのリストから別のタス
クを選択し、上記のステップを繰り返す。

場合によっては、現在走行中のプログラムまたはタスク
は、その時間量子を完了することができない。そうなる
のは、以下のいずれかである。

１．プログラムまたはタスク自体が、入出力動作の完了
など外部事象の発生を待たなければならない。外部事象
が発生すると、そのタスクを直ちに中断し、実行可能タ
スクのリストから取り除かなければならない。その時点
で、オペレーテイング・システムは、異なるプログラム
またはタスクを開始しなければならない。

２．入出力動作の完了など外部事象が認識される。

外部事象があると、オペレーティング・システムが、入
出力プログラムを開始し、実行の準備ができていて外部
事象を待っているタスクのリストを変更することが必要
となる。オペレーテイング・システムは、割込みを受け
たタスクに戻ってその時間量子を完了させるか、または
新しいタスクを選択することができる。

３．外部事象が認識された場合、及び実行中のタスクが
一時的に中断された場合、中断時間中にその累積実行時
間は増加しない。

上記の環境の説明は、本発明を支援する可能な環境の代
表例であるが、本発明は、この特定の環境のみに限られ
るものではない。本発明の目的は、時間量子の終りに割
込みを据え置き、コンテキスト交換のコストが比較的低
くなりそうな時にそれを行なわせることである。本発明
は、上記の通常動作を以下のように修正する。

オペレーティング・システムは、時間量子ヲ選択したタ
スクに割り振るとき、時間量子の最も早い終り及び時間
量子の最も遅い終りの２つの時間で時間量子を表す。量
子終り割込みは、最も早い時間より前には発生できず、
その時点より前に実行プログラムによってトリガされな
い限り、最も遅い時間に発生することが保証される。オ
ペレーティング・システムは、選択したタスクの実行を
開始し、選択したタスクは、それに割り振られた最小時
間量子の間実行され、それが終了した時点で量子終り割
込みが準備される。量子終り割込みが準備されている間
、タスクは実行を継続する。

そのタスクが量子終り割込みをトリガする命令を実行す
る場合は、その割込みは直ちに処理される。

タスクが割り振られた最大時間の間実行される前に量子
終り割込みがトリガされない場合、量子終り割込みがト
リガされる。量子終り割込みがどのようにしてトリガさ
れようと、オペレーテイング・システムは、その割込み
を通常の量子終り割込みとして処理する。実行中のタス
クが準備された量子終り割込みをもっている間に外部事
象が割込みをトリガする場合、そのタスクは、その量子
の終りに達したものとして扱われ、保留中の割込みが除
去される。

図面、特に第１図を参照すると、本発明による据置き可
能割込みを実施するための機構が示されている。この機
構は、３つのレジスタと２つの加算器を含む。それらの
レジスタは、経過時間レジスタ１０１最小量子レジスタ
２０、及び最大量子レジスタ３０である。第１の加算器
４０は、最小量子と経過時間の値の差をとる。経過時間
が最小量子時間を越えた場合は、結果の符号は負となる
。

負の符号のとき、割込みが下記のように準備される。同
様に、第２の加算器５０は最大量子と経過時間の値の差
をとる。この加算の結果が負の場合、下記のように割込
みが通知される。

第１図と従来技術の違いは、従来の経過時間に基づく割
込みの実施態様では、最大時間レジスタ３０、経過時間
レジスタ１０１及び加算器５０Ｌか使用しないことであ
る。割込みは、加算器の結果の符号を検査することによ
って通知される。この従来技術は、割込みを準備する手
段を含んでいないので、第１図に示される最小時間レジ
スタ２０と加算器４０の使用を教示していない。

第２図は、タスクを開始する前にオペレーティング・シ
ステムがとるステップを示す。オペレーティング・シス
テムは、機能ブロック６０でタスクの経過時間をゼロに
初期設定し、第２図の機能ブロック７０と８０で最小及
び最大量子時間を初期設定する。第２図の最終ステップ
は、９０で示すようにタスクを開始することである。機
能ブロック８０１７０、８０で実行される動作の順序は
重要ではない。オペレーティング・システムは、こうし
たタスク間に散在するオペレーティング・システム依存
タスクを実行することもできる。従来技術で教示されて
ない第２図の態様は、ブロック７０での最小量子時間の
設定である。

第３図は、割込みを準備するのに必要な論理回路を示す
。走行中のタスクの経過時間が第３図のクロックで示さ
れる。クロックは機能ブロック１００で示すよろに進め
られる。ブロック１００の実行の間隔はシステムによっ
て異なり、システム中の最も速いクロック速度で実行す
る必要はない。

クロックが進む度に、判断ブロック１１０で検査を行な
って、量子時間割込みの準備ができているかどうか判定
する。準備ができている場合、第４図の判断ブロック１
５０に進んで、下記のような次の検査を行なう。準備が
できていない場合、判断ブロック１２０で経過時間の現
在値を最小量子時間と比較する。現在値が最小量子時間
を越える場合、機能ブロック１３０に示すように量子時
間割込みが準備される。

第４図は、量子時間割込みがどのようにして通知される
かを示す。この図は従来技術を反映したものである。判
断ブロック１５０で、現在経過時間を最大量子時間と比
較する。現在値が最大量子時間を越える場合、機能ブロ
ック１６０に示すように割込みが通知される。

第５図は、プログラムが、準備された割込みをどのよう
に発生させるかを示す。プログラムは、コンテキスト交
換オーバヘッドが他の場所で生じるオーバヘッドよりも
局所的に小さいプログラムに入れられた特殊命令を実行
する。この命令の実行を機能ブロック２００に戻す。こ
の命令の実行により、判断ブロック２１０に示すように
割込みの状態が検査される。割込みが準備されている場
合、機能ブロック２２０で割込みを通知する。割込みの
通知は、量子の終りを意味する。オペレーティング・シ
ステムは、時間量子の終りに応じて、従来技術で利用可
能な技法を使ってタスクを中断することにより、割込み
に応答する。割込みが準備できていない場合、この特殊
命令は、割込み命令を取り出して解釈するのに必要な時
間を利用すること以外、プログラム実行に影響を及ぼさ
ない。

第６図は、外部事象が量子終り端割込みをどのようにト
リガするかを示す。機能ブロック３００で、外部事象に
よって割込みが通知される。これが発生すると、判断ブ
ロック３１０で量子時間割込みを検査する。それも準備
されている場合、機能ブロック３２０で、それも割込み
として通知されるので、少なくとも２つの割込みが現在
に保留中となる。それも準備できていない場合は、機能
ブロック３３０で、走行中のタスクの経過時間の記録専
用のレジスタが動作不能になる。この時点で、オペレー
ティング●システムは走行中のタスクを中断し、外部事
象に関連するタスクのスケジュールを立てる。

従来技術で教示されてな′い第６図の重要な新しい考え
は、外部事象が、通常なら後まで行なわれないコンテキ
スト交換を強制する好機となることである。第２のタス
クが走行できるよウに元のタスクが短時間中断されるの
で、第２のタスクは）それ自体をキャッシュ・メモリに
ロードして、第１のタスクに関連する状態の一部を除去
する。これにより、第１のタスクに関連する状態のサイ
ズが局所的に縮小される。第２タスクの走行が完了する
と、オペレーティング・システムは通常、第１のタスク
に戻る。というのは、その時間量子が終わっていないか
らである。しかし、量子割込みが準備されている場合は
、交換される状態のサイズが比較的小さいどの時点でも
割込みを行なうことができる。そうなるのは、割込みタ
スクの処理の終りである。第６図の機能ブロック３２０
で示すように、量子時間割込みを通知することにより、
オペレーティング●システムは、割込みタスクを処理し
た後に元のタスクに戻らず、そのためコンテキスト交換
が局所的に好ましい時点で行なわれる。

すなわち、準備された量子時間割込みは、命令の実行ま
たは外部事象割込みの通知によって通知できる。一般に
、準備された割込みは、局所的に小さいコンテキストを
生成することが認められているどんな条件下でも通知さ
れる。どんな条件でそうなるかは、コンピュータ・シス
テムの特徴によって変わる。

広義に述べると、本発明は、（１）プログラム・フット
プリントが小さいときに発生する傾向にあるコンテキス
ト交換のための割込みと、（２）フットプリントのサイ
ズが減少する点で割込みをトリガする手段から構成され
る。コンテキスト交換割込みは、以下の事象でトリガさ
れる。

１．基本ブロックからの出口。

２．ファイルのクローズ（バッファ記憶機構が戻される
とき）及び ３，記憶機構が他の目的で使用されるために戻されると
きの他の同様の検出可能な事象。

これらの事象は、コンパイラによってコードに入れられ
た特殊割込み命令によって通知される。

特殊命令の働きは、コンテキスト交換割込みが準備され
ている場合に割込みを引き起こすこと、及びそうでない
場合は影響を及ぼさないことである。

割込みを生成する簡単でうまいやり方は、サブルーチン
・リターン及び割込みリターンが実行されるときに割込
みを発生させることである。どの場合にも、プログラム
またはプロセスから出る最中であり、その状態が近い将
来に必要となる可能性は小さい。より効果的な方法は、
アルゴリズム分析を使って、サブルーチンが、大きな直
線コードでありあるいは１つまたは複数のネスティング
・レベルのループをもち、かつサブルーチンが触れる可
能性のあるデータ・セルと命令セルの総数がキャッシュ
・サイズと同程度であるといつ特徴をもつ、サブルーチ
ンからの出口がいつ発生するかを決定することである。

この特徴が検出されると、そのサブルーチンは、キャッ
シュの大きな部分を占有し、その部分を以後のコードは
必要としない。

あるサブルーチンの実行が終了する前にコンテキスト交
換割込みが発生する場合、サブルーチンから出る前に、
そのサブルーチンをキャッシュに再ロードしなければな
らない。サブルーチンから出るのを待ってコンテキスト
交換割込みが行なわれる場合、キャッシュ再ロード過渡
は回避される。

上記の特性をもつサブルーチンを識別することにより、
コンパイラはこうした各ルーチンの出口の前にコンテキ
スト交換割込みトリガを挿入することができる。本発明
は、割込みをトリガするどの手段を使っても性能の向上
をもたらす。性能の向上は、割込みがフットプリントの
サイズの最大の縮小を伴う場合に大きくなる傾向にある
。

本発明を１つの好ましい実施例に照らして説明したが、
当業者には周知の通り、本発明は、特許請求の範囲の精
神及び範囲に含まれる類似の修正を施して実施すること
ができる。

【図面の簡単な説明】

第１図は、据置き可能割込みを制御する手段を図示する
構成図である。 第２図は、据置き可能割込みを設定する手段を図示する
構成図である。 第３図は、据置き可能割込みが準備されたときに起こる
事象を示す流れ図である。 第４図は、最大量子時間に達したために据置き可能割込
みが通知されるときに起こる事象を示す流れ図である。 第５図は、割込みを認識すべき点に達したときに、準備
された据置き可能割込みをプログラムがどうトリガする
かを示す流れ図である。 第６図は、あるタスクが、その据置き可能割込みが準備
される前に割込みを受けた場合に、据置き可能割込みを
動作不能にするために取られる処置を示す流れ図である
。 １０・・・・経過時間レジスタ、２０・・・・最小量子
レジスタ、３０・・・・最大量子レジスタ、４０，５０
・・・・加算器。

Claims (2)

【特許請求の範囲】
1. （１）現在実行されているプログラムに関連してキャッ
   シュにストアされているラインの数が少ないときに発生
   する傾向のあるコンテキスト交換用の割込みを生成する
   ステップと、 プログラム・フットプリントのサイズが減少する点でそ
   の割込みをトリガするステップと、をコンピュータ・オ
   ペレーティング・システムによって実行する多重プログ
   ラム式コンピュータ・システムにおけるコンテキスト交
   換によるキャッシュ再ロード・オーバーヘッドを減少さ
   せる方法。
2. （２）多重プログラム式コンピュータ・システム上で１
   つのタスクを走行する時間に対応する値を記憶する経過
   時間レジスタ手段と、 前記タスクに割り当てられた最小量子時間に対応する値
   を記憶する最小量子時間レジスタ手段と、前記タスクに
   割り当てられた最大量子時間に対応する値を記憶する最
   大量子時間レジスタ手段と、前記経過時間レジスタ手段
   及び前記最小量子時間レジスタ及び最大量子時間レジス
   タ手段に接続された、経過時間を最小量子時間と比較し
   、かつ経過時間を最大量子時間と比較するための比較論
   理手段と、 を含む多重プログラム式コンピュータ・システムにおけ
   るコンテキスト交換によるキャッシュ再ロード・オーバ
   ーヘッドを減少させる装置。