JPH0255812B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明はメモリをスタツクとして使用する場
合に生じる主記憶とキヤツシユメモリ間の無駄な
データ転送を削減するのに適した制御手段を備え
たキヤツシユメモリのメモリ制御装置に関するも
ので、特に、ライト・スワツプ方式に属するキヤ
ツシユメモリに関し、主記憶からの無駄なデータ
の読み出しと主記憶への無駄なデータの書き出し
を削減するものである。

〔従来の技術〕

キヤツシユメモリ装置の方式としては、CPU
からデータの書き込みを行う際にデータをキヤツ
シユメモリ内と主記憶の両方に同時に書き込むラ
イト・スル−方式と書き込み時にはキヤツシユメ
モリ内にだけ書き込みを行い、書き込んだ領域が
後になつて別のアドレスのキヤツシユアクセスに
使用される時点で以前のデータを主記憶へ書き出
すライト・スワツプ方式の二つがある。

ここで、本願の対象とする後者による従来のラ
イト・スワツプ方式のキヤツシユメモリの書き込
み方式について、図を用いて説明する。

第１１図はキヤツシユメモリ装置の一例の構成
図である。図において、アドレス・レジスタ３０
は、キヤツシユメモリをアクセスする場合のアド
レスを保持するレジスタで、上位アドレス部３
１、中位アドレス部３２、下位アドレス部３３の
三つの部分から成る。データ・メモリ２０はデー
タを記憶するためのメモリで、その記憶容量（語
数）は中位アドレス部３２、下位アドレス部３８
を合わせたビツト数で指定できるだけの大きさを
持つ。データ・メモリ２０中のデータは１語ずつ
管理されるのではなく、下位アドレス部３３のビ
ツト数で指定できる大きさのブロツクと呼ぶ単位
でヒツト、ミスヒツトの管理や主記憶との間のデ
ータ入れ替えの管理が行われる。以後本例では、
１ブロツクの大きさを４語として説明を行う。デ
ータ・メモリ２０中には、中位アドレス部３２の
ビツト数で指定できるだけの個数のブロツクが存
在する。

しかして、デイレクトリ・メモリ１０は、デー
タ・メモリ２０の中の各ブロツクが有効か無効
か、どこのアドレスに対応するデータが置かれて
いるのか、主記憶からキヤツシユメモリに読み込
まれた後に内容が変更されたか否かの情報を保持
し、キヤツシユメモリの読み書き時に、ヒツトか
ミスヒツトか、主記憶との間にデータ転送の必要
があるか否かの管理に使用されるもので、このデ
イレクトリ・メモリ１０は、有効フラツグ部１
１、変更フラツグ部１２、キーアドレス部１３か
ら構成され、デイレクトリ・メモリ１０のエント
リ数は、データ・メモリ２０中のブロツクの個数
に等しい。

また、比較器１４は、アドレス・レジスタ３０
中の上位アドレス部３１の値と、キーアドレス部
１３の値を比較し、その結果がキヤツシユのヒツ
ト、ミスヒツトの判定に使用される。この場合、
デイレクトリ・メモリ１０は中位アドレス部３２
を用いて検索される。カウンタ３４は、下位アド
レス部３３と同じビツト幅を持ち（本例では２ビ
ツトとする）、ゼロクリア、下位アドレス部３３
からの値のロード、＋１の機能を持ち、データ・
メモリ２０のブロツクの中身（４語）を順次主記
憶へ書き出す処理（ライトバツク）および主記憶
からデータ・メモリ２０のブロツクへ順にデータ
を読み込む（ブロツクロード）場合の、最下位
（２ビツト）のアドレス生成に使用される。

さらに、データ選択器３５は、データ・メモリ
２０および主記憶へ供給するアドレスの最下位
（２ビツト）として、下位アドレス部３３の値を
使うか、カウンタ３４の値を使うかを決定するも
のであるが、通常は下位アドレス部３３の方を選
択しているものとする。書き込みデータ・レジス
タ２１は、キヤツシユメモリに書き込むべきデー
タを保持するレジスタである。主記憶インタフエ
ース２４は、主記憶とのデータ、アドレス、制御
信号の受渡しを行う部分であり、アドレス情報と
して中位、下位アドレスについては、データ・メ
モリ２０に供給されているものと同じ情報が、上
位アドレスについては、本例ではキーアドレス部
１３の内容がそれぞれ使用される。制御回路４０
は、キヤツシユ命令レジスタ４１に置かれたキヤ
ツシユ命令に従いキヤツシユメモリの読み書きを
開始し、デイレクトリ・メモリ１０の内容に従
い、ヒツト、ミスヒツトの別、主記憶との間のデ
ータ転送の要否を判定して、判定結果に従つた制
御手順を実行する。なお、第１１図において、２
２は読み出しデータ・レジスタ、２３はキヤツシ
ユ・データバスである。

次に、第１２図はキヤツシユ命令として書き込
み（ライト）が指定された場合の制御手順の流れ
図である。デイレクトリ・メモリ１０の有効フラ
ツグと変更フラツグの値、および比較器１４の比
較結果により処理が分岐する。流れ図の中で枝６
１，６２，６３，６４は、各々次の場合を示す。
枝６１は当該ブロツク中に有効なデータがなくキ
ヤツシユ・ミスヒツトとなつた場合、枝６２はキ
ヤツシユ・ヒツトの場合、枝６３は当該ブロツク
中に有効なデータが存在するがキーアドレスが異
なるためにミスヒツトとなつた場合で、かつブロ
ツクの内容が主記憶から持つて来られた後に変更
を受けておらず（変更フラツグ＝０）主記憶へ書
き戻す必要がない場合、枝６４は枝６３と同様ミ
スヒツトの場合であるが変更フラツグが１であり
ブロツクの内容を主記憶へライトバツクする必要
がある場合である。

各々の場合の制御手順について説明すると、枝
６４の場合は、データ・メモリ２０の当該ブロツ
クには、別のアドレスに対応する有効なデータが
存在するため、まずブロツクの内容４語を主記憶
へ書き戻す。この処理が第１２図の枠６００の処
理である。こうしてブロツクを空にした後、枠６
０１の処理で今書き込もうとしている１語の書き
込みを行う。次に枠６０２，６０３でデイレクト
リ・メモリ１０の内容を更新する。最後に枠６０
４で、ブロツク内の残り３語に、主記憶の然るべ
きアドレスからデータを読み込み、処理を終了す
る。

枠６００の処理を詳細化したのが第１３図であ
る。ブロツク内の４語のデータを順次読み出し主
記憶へ書き込むために１ずつアドレスを変化させ
る必要があるが、この目的で第１１図のカウンタ
３４を使用する。また、枠６０４の処理を詳細化
したのが第１４図である。第１２図の枠６０１で
書き込みを行つたアドレスを除く同一ブロツク内
の３語について、主記憶からデータを読み込むた
めに、同じくカウンタ３４を用いる。第１３図と
の違いは、カウンタの初期値として始めにアドレ
スレジスタの下位アドレス部３３をロードし、そ
れを１増加しては主記憶読み出しのための下位ア
ドレス部として使用することである。枝６１およ
び６３の処理は、枝６４の処理から枠６００の処
理を除いたものに等しく、更に枝６２の処理は枝
６１の処理から枠６０３，６０４の処理を除いた
ものと全く等しい。

さらに、第１５図はキヤツシユ命令として読み
出し（リード）が指定された場合の制御手順の流
れ図である。第１２図と同様、デイレクトリ・メ
モリ１０の有効フラツグと変更フラツグの値、お
よび比較器１４の比較結果により処理が分岐す
る。流れ図の中で枝７１，７２，７３，７４は、
各々第１２図の枝６１，６２，６３，６４に対応
する。

各々の場合の制御手順について説明すると、枝
７４の場合は、データ・メモリ２０の当該ブロツ
クには、別のアドレスに対応する有効なデータが
存在するため、まずブロツクの内容４語を主記憶
へ書き戻す。この処理が第１５図の枠７００の処
理であり、第１３図で詳細に示した枠６００と等
しい。こうしてブロツクを空にした後、枠７０１
の処理で今要求されているブロツクを主記憶から
ブロツクロードしデータ・メモリ２０へ書き込
む。次に枠７０２の処理で要求されているアドレ
スのデータをデータ・メモリ２０から読み出しデ
ータレジスタ２２へ書き込み、最後に枠７０３で
デイレクトリ・メモリ１０の内容を更新する。枠
７０１の詳細を示したのが第１６図である。この
第１６図での処理は第１３図で示した枠６０４と
よく似た処理を行うが、カウンタの＋１タイミン
グと繰り返し回数のみが異なつている。第１５図
の処理において、枝７１および７３の処理は、枝
７４の処理から枠７００の処理を除いたものに等
しく、更に枝７２の処理は枝７１の処理から枠７
０１，７０３の処理を除いたものと全く等しい。

〔発明が解決しようとする問題点〕

しかるに、以上述べたような従来例におけるキ
ヤツシユメモリの書き込み、及び読み出しの制御
手順を用いると、メモリをスタツクとして使用す
る場合、明らかに不要な主記憶の読み出し、及び
主記憶への書き出しが発生する。この様子を図を
用いて説明する。

第１７図はメモリをスタツクとして使用する場
合の概念図である。書き込み前の図ではスタツク
の先頭は1001(h)番地にあり、これから1002(h)番地
にデータの書き込みを行おうとするところである
（(h)は16進表示を示す）。破線はキヤツシユメモリ
のブロツクの境界を示す。またキヤツシユメモリ
には、異なるアドレスに対応する有効なデータが
変更フラグ＝１のものが存在しているものとす
る。1002(h)番地への書き込みを実行すると、キヤ
ツシユメモリはミスヒツトを起こし、第１２図の
枝６４の制御手順が実行されて、まずブロツク内
の元のデータ４語が主記憶へ書き戻され、次に
1002(h)番地へ書き込むべきデータが当該ブロツク
に書き込まれ、デイレクトリ・メモリ１０が更新
され、そしてブロツク内の残りの３語が主記憶か
ら読み込まれる。第１７図の書き込み後の図は、
斜線が主記憶から読み込まれたデータを示し、格
子縞が書き込まれたデータを示す。次に1003(h)番
地への書き込みを行なうと、キヤツシユメモリは
ヒツトし、第１２図の枝６２の制御手順が実行さ
れて、データの書き込みと変更フラグのセツトだ
けが行われ、第１７図の書き込み後の図の1003(h)
番地は、斜線から格子縞に変わる（第１８図の書
き込み前の図）。次に1004(h)番地へ書き込みを行
なうと、再びミスヒツトが起こり、第１２図の枝
６４の制御手順が実行されて、第１８図の書き込
み後の図のように、1004(h)には書き込みデータ
が、1005(h)〜1007(h)番地には主記憶から読み込ま
れたデータが存在することになる。こうして書き
込みをくり返し、1002(h)から100D(h)番地までの
12語に書き込みを完了した時の図が第１９図であ
る。1002(h)から100D(h)番地までに書き込んだデ
ータが存在し、1000(h)，1001(h)，100E(h)，100F
(h)番地には自動的に主記憶から読み込まれたデー
タが存在している。この状態でスタツクの先頭は
100D(h)番地であり、それより大きいアドレスの
データはスタツクを利用する者にとつて意味のな
いデータである。またここで注意すべきことは、
1002(h)，1004(h)，1008(h)，100C(h)番地の書き込
み時にはキヤツシユはミスヒツトして、主記憶か
らそれぞれ３語ずつ合計12語のデータが読み込ま
れたが、その内の８語、番地でいうと1003(h)，
1005(h)，1006(h)，1007(h)，1009(h)，100A(h)，
100B(h)，100D(h)番地のデータは、使用されない
まま書き込みデータが上書きされていることであ
る。さらにスタツク利用の意味上、不要な100E
(h)，100F(h)番地のデータを含めて、10語もの不
要なデータが主記憶から読み込まれている。

このように、各アドレスへのデータ書き込みの
際のヒツト、ミスヒツトの区別、その時起動され
たキヤツシユ制御手段の区別、主記憶への書き出
し、主記憶からの読み込みデータの語数をまとめ
たものが第２０図である。キヤツシユメモリへの
12語のデータ書き込みに対して、12語の主記憶か
らのデータ読み込みが発生し、その中の10語のデ
ータは上述のごとく無駄な読み込みとなつてい
る。

次に、従来の読み出し命令（リード命令）を用
いてスタツクの内容を読み出した場合について説
明する。第１９図の状態から100D(h)番地〜1002
(h)番地まで12語を順次読み出すと12回のリード命
令は全てヒツトし、スタツクの先頭は1001(h)番地
に戻る。この状態で他のアドレスに対するキヤツ
シユアクセスによつて1000(h)番地〜100F(h)番地
の４ブロツク16語がキヤツシユを追い出されると
合計16語の主記憶への書き出しが発生する。しか
しながらスタツクの特性から1002(h)番地〜100F
(h)番地の14語のデータは再び参照されることはな
いため、本来主記憶への書き出しを必要としない
データである。

以上の如く、メモリをスタツクとして使用した
場合、従来方式のキヤツシユメモリ制御方式では
主記憶との間で無駄なデータ転送を行つており、
主記憶アクセスのために余分な時間がかかつてい
る。

この発明は上記のような従来のライト・スワツ
プ方式のキヤツシユメモリのメモリ制御装置にお
いて、メモリをスタツクとして使用する場合に明
らかに無駄と分る主記憶とキヤツシユメモリとの
間のデータ転送が発生し、その主記憶アクセスの
ために余分な処理時間がかかるという欠点を除去
するためになされたものである。

〔問題点を解決するための手段〕

この発明に係るメモリ制御装置は、データの書
き込みを行なう際に、該データをキヤツシユメモ
リ内のみに書き込み、該書き込んだ領域が後に別
のアドレスのキヤツシユアクセスに使用される時
に、該領域に書き込まれているデータを主記憶に
書き戻すライト・スワツプ方式のキヤツシユメモ
リのメモリ制御装置において、書き込みアドレス
のデータセルを含むブロツクでなるデータの管理
単位がキヤツシユメモリ内に存在しない場合、当
該ブロツクをキヤツシユメモリ内に確保した後に
書き込みデータを当該アドレスのデータセルに書
き込み、ブロツク内の他のデータセルについては
主記憶からデータの読み込みを行なうライト・ス
ワツプ方式における第１の書き込み制御手段と、
上記第１の書き込み制御手段と同じ制御を行ない
つつ、書き込みアドレスがブロツクの先頭データ
セルであつて、かつ当該ブロツクがキヤツシユメ
モリ内に存在しない場合に限り、当該ブロツクを
キヤツシユメモリ内に確保した後に書き込みデー
タを当該アドレスのデータセルに書き込み、ブロ
ツク内の他のデータについては主記憶から読み出
すことなく当該ブロツクを有効化せしめる第２の
書き込み制御手段と、読み出しアドレスのデータ
セルを含むブロツクが、キヤツシユメモリ内に存
在しない場合に当該ブロツクをキヤツシユメモリ
内に確保した後主記憶より該ブロツクのデータを
読み出してキヤツシユメモリに格納する第１の読
み出し制御手段と、上記第１の読み出し制御手段
と同じ制御を行ないつつ、読み出しアドレスがブ
ロツクの先頭データセルの場合でかつ当該ブロツ
クがキヤツシユメモリ内に存在しなかつた場合
は、当該データのみを主記憶から読み出し、キヤ
ツシユメモリには何ら変化を残さない制御を行な
い、読み出しアドレスがブロツクの先頭データセ
ルの場合で、かつ当該ブロツクがキヤツシユメモ
リ内に存在した場合には、当該データをキヤツシ
ユメモリから読み出した後、キヤツシユメモリ内
の該ブロツクを直ちに無効化せしめる第２の読み
出し手段を備えたメモリ制御装置を提供する。

〔作用〕

この発明による第２の書き込み制御手段及び第
２の読み出し制御手段を、メモリをスタツクとし
て使用する場合に適用すると、論理的な不都合を
生じせしめることなく機能し、かつ主記憶とキヤ
ツシユメモリとの間のデータ転送量が減少する。

〔実施例〕

以下、この発明の一実施例について図を用いて
説明する。第１図はこの発明の実施例の１つであ
るキヤツシユメモリのメモリ制御装置の構成図で
ある。本実施例は、第１１図ないし第１９図を用
いて説明した従来のキヤツシユメモリのメモリ制
御装置の一例に対して、ライト・スタツクと呼ぶ
新たなキヤツシユ命令と、リード・スタツクと呼
ぶ新たなキヤツシユ命令を追加し、その命令の制
御手順を実現するためのスタツク操作命令用制御
回路５０、スタツク操作命令用キヤツシユ命令デ
コーダ４７を付加したものである。制御回路４
３、キヤツシユ命令デコーダ４６は、第１１図の
制御回路４０、キヤツシユ命令デコーダ４５に相
当するものであり、第１２図に制御手順の流れ図
を示したキヤツシユ命令の「ライト」、第１５図
に制御手順の流れ図を示したキヤツシユ命令「リ
ード」をはじめとする従来のキヤツシユ命令の制
御手順を実現する。ただし、キヤツシユ命令レジ
スタ４１にキヤツシユ命令「ライト・スタツク」
又は「リード・スタツク」が置かれた場合には、
キヤツシユ命令デコーダ４６は命令解読信号を制
御回路４３へ転送せず、制御回路４３は制御信号
線４４とデイレクトリ・メモリ１０の有効フラツ
グ部１１、変更フラツグ部１２へデータを送出す
る信号線を開放して、キヤツシユメモリ装置の制
御権をスタツク操作命令用制御回路５０へ渡す。
また、スタツク操作命令用キヤツシユ命令デコー
ダ４７はライト・スタツクおよびリード・スタツ
ク命令を解読して命令解読信号をスタツク操作命
令用制御回路５０へ送出し、スタツク操作命令用
制御回路５０は制御信号線５１を通じて制御信号
を送出し、ライト・スタツク及びリード・スタツ
クのキヤツシユ命令に対応する制御手順を実行す
る。第１図中の他の構成要素は第１１図のものと
同じである。

上記第１図構成において、アドレス・レジスタ
３０はキヤツシユメモリをアクセスする場合のア
ドレスを保持するレジスタで、上位アドレス部３
１、中位アドレス部３２、下位アドレス部３３の
三つの部分から成る。また、データ・メモリ２０
はデータを記憶するためのメモリで、その記憶容
量（語数）は中位アドレス部３２、下位アドレス
部３３を合わせたビツト数で指定できるだけの大
きさを持つ。データ・メモリ２０中のデータは１
語ずつ管理されるのではなく、下位アドレス部３
３のビツト数で指定できる大きさのブロツクと呼
ぶ単位でヒツト、ミスヒツトの管理や主記憶との
間のデータ入れ替えの管理が行われる。以後本例
では、１ブロツクの大きさを４語として説明を行
う。上記データ・メモリ２０中には、中位アドレ
ス部３２のビツト数で指定できるだけの個数のブ
ロツクが存在する。

しかして、デイレクトリ・メモリ１０は、デー
タ・メモリ２０の中の各ブロツクが有効が無効
か、どこのアドレスに対応するデータが置かれて
いるのか、主記憶からキヤツシユメモリに読み込
まれた後に内容が変更されたか否かの情報を保持
し、キヤツシユメモリの読み書き時に、ヒツトか
ミスヒツトか、主記憶との間にデータ転送の必要
があるか否かの管理に使用されるもので、このデ
イレクトリ・メモリ１０は、有効フラツグ部１
１、変更フラツグ部１２、キーアドレス部１３か
ら構成され、デイレクトリ・メモリ１０のエント
リ数は、データ・メモリ２０中のブロツクの個数
に等しい。

また、比較器１４は、アドレス・レジスタ３０
中の上位アドレス部３１の値と、キーアドレス部
１３の値を比較し、その結果がキヤツシユのヒツ
ト、ミスヒツトの判定に使用される。この場合、
デイレクトリ・メモリ１０は中位アドレス部３２
を用いて検索される。カウンタ３４は、下位アド
レス部３３と同じビツト幅を持ち（本例では２ビ
ツトとする）、ゼロクリア、下位アドレス部３３
からの値のロード、＋１の機能を持ち、データ・
メモリ２０のブロツクの中身（４語）を順次主記
憶へ書き出す処理（ライトバツク）および主記憶
からデータ・メモリ２０のブロツクへ順にデータ
を読み込む（ブロツクロード）場合の、最下位
（２ビツト）のアドレス生成に使用される。デー
タ選択器３５は、データ・メモリ２０および主記
憶へ供給するアドレスの最下位（２ビツト）とし
て、下位アドレス部３３の値を使うか、カウンタ
３４の値を使うかを決定するものであるが、ここ
では下位アドレス部３３の方を選択しているもの
とする。書き込みデータ・レジスタ２１は、キヤ
ツシユメモリに書き込むべきデータを保持するレ
ジスタである。主記憶インタフエース２４は、主
記憶とのデータ、アドレス、制御信号の受渡しを
行う部分であり、アドレス情報として中位、下位
アドレスについては、データ・メモリ２０に供給
されているものと同じ情報が、上位アドレスにつ
いては、本例ではキーアドレス部１３の内容がそ
れぞれに使用される。

第２図は第１図のスタツク操作命令用制御回路
５０で実現するライト・スタツク命令の制御手順
の流れ図である。アドレスレジスタ３０（番号は
以後第１図または第２図中のものを指す）の下位
アドレス部３３の値、デイレクトリメモリ１０の
有効フラツグ部１１と変更フラツグ部１２の値、
および比較器１４の比較結果により制御手順の流
れが分岐する。ここで、枝８０は書き込みアドレ
スがブロツクの先頭データセルを指していなかつ
た場合、枝８５は書き込みアドレスがブロツクの
先頭データセルを指している場合である。また、
枝８１及び枝８６はアドレス・レジスタ３０の中
位アドレス部３２で指定されるブロツク中に有効
なデータがなくキヤツシユ・ミスヒツトとなつた
場合、枝８２及び枝８７はキヤツシユ・ヒツトの
場合、枝８３及び枝８８は当該ブロツク中に有効
なデータが存在するが、キーアドレスの比較結果
が不一致のためのミスヒツトした場合で、かつブ
ロツクの内容が主記憶から持つと来られた後変更
を受けておらず（変更フラツグ＝０）主記憶へ書
き戻す必要のない場合、枝８４及び枝８９は枝８
３及び枝８８と同様のミスヒツトであるが、変更
フラツグが１のためブロツクの内容を主記憶へラ
イトバツクする必要のある場合である。

以下各々の場合の制御手順について説明する
と、枝８０の場合、第１２図で示したライト命令
の制御手順と全く同じであり、枝８１，８２，８
３，８４は各々第１２図の枝６１，６２，６３，
６４に相当する。すなわち枝８４の場合は、デー
タ・メモリ２０の当該ブロツクには、別のアドレ
スに対応する有効なデータが存在するため、まず
ブロツクの内容４語を主記憶へ書き戻す。この処
理が第２図の枠８００の処理である。こうしてブ
ロツクを空にした後、枠８０１の処理で今書き込
もうとしている１語の書き込みを行う。次に枠８
０２，８０３でデイレクトリ・メモリ１０の内容
を更新する。最後に枠８０４で、ブロツク内の残
り３語に、主記憶の然るべきアドレスからデータ
を読み込み、処理を終了する。

枠８００の処理を詳細化したのが第３図であ
る。ブロツク内の４語のデータを順次読み出し主
記憶へ書き込むために１ずつアドレスを変化させ
る必要があるが、この目的で第１図のカウンタ３
４を使用する。また、枠８０４の処理を詳細化し
たのが第４図である。第２図の枠８０１で書き込
みを行つたアドレスを除く同一ブロツク内の３語
について、主記憶からデータを読み込むために、
同じくカウンタ３４を用いる。第３図との違い
は、カウンタの初期値として始めにアドレスレジ
スタの下位アドレス部３３をロードし、それを１
増加しては主記憶読み出しのための下位アドレス
として使用することである。枝８１および８３の
処理は、枝８４の処理から枠８００の処理を除い
たものに等しく、更に枝８２の処理は枝８１の処
理から枝８０３，８０４の処理を除いたものと全
く等しい。

さらに、枝８５はこの発明による新しい制御手
順であつて、書き込みアドレスがブロツクの先頭
を指している（下位アドレス＝０）場合に実行さ
れる。枝８９の場合は、データ・メモリ２０の当
該ブロツクには、異なるキーアドレスの有効なデ
ータが存在するため、まずブロツクの内容４語を
主記憶へ書き戻す。この処理が第２図の枠８２０
の処理である。こうして書き込み対象ブロツクを
確保した後、枠８２１の処理で書き込みデータ・
レジスタ２１中のデータをデータ・メモリ２０中
の当該ブロツク内の指定アドレスのデータセルに
書き込む。この場合アドレスとして、ブロツクを
指定するのに中位アドレス部３２が、ブロツク内
のデータセルを指定するのに下位アドレス部３３
が使用される。

次に枠８２２、枠８２３でデイレクトリ・メモ
リ１０の内容を更新し処理を終了する。枝８４と
異なり主記憶からのデータ読み込み（枠８０４）
は行なわない。枠８２０の処理は第３図に詳細を
示した枠８００の処理と全く同じである。枝８６
および枝８８の処理は枝８９の処理から枠８２０
の処理を除いたものに等しく、枝８７の処理は枝
８２の処理と等しい。

しかして、第５図は第１図のスタツク操作命令
用制御回路５０で実現するリード・スタツク命令
の制御手順の流れ図である。アドレスレジスタ３
０の下位アドレス部３３の値、デイレクトリメモ
リ１０の有効フラツグ部１１と変更フラツグ部１
２の値、および比較器１４の比較結果により制御
手順の流れが分岐する。枝９０は書き込みアドレ
スがブロツクの先頭データセルを指していなかつ
た場合、枝９５は書き込みアドレスがブロツクの
先頭データセルを指している場合である。枝９１
及び枝９６はアドレス・レジスタ３０の中位アド
レス部３２で指定されるブロツク中に有効なデー
タがなくキヤツシユ・ミスヒツトとなつた場合、
枝９２及び枝９７はキヤツシユ・ヒツトの場合、
枝９３は当該ブロツク中に有効なデータが存在す
るが、キーアドレスの比較結果が不一致のために
ミスヒツトした場合で、かつブロツクの内容が主
記憶から持つて来られた後変更を受けておらず
（変更フラツグ＝０）主記憶へ書き戻す必要のな
い場合、枝９４は枝９３と同様のミスヒツトであ
るが、変更フラツグが１のため、ブロツクの内容
を主記憶へライトバツクする必要がある場合、枝
９８は当該ブロツク中に有効なデータが存在する
が、キーアドレスの比較結果が不一致のためミス
ヒツトした場合である。以下各々の場合の制御手
順について説明する。

枝９０の場合、第１５図で示したリード命令の
制御手順と全く同じであり、枝９１，９２，９
３，９４は各々第１５図の枝７１，７２，７３，
７４に相当する。

枝９４の場合は、データ・メモリ２０の当該ブ
ロツクには、別のアドレスに対応する有効なデー
タが存在するため、まずブロツクの内容４語を主
記憶へ書き戻す。この処理が第５図の枠９００の
処理であり、第３図で詳細を示した枠８００と等
しい。こうしてブロツクを空にした後、枠９０１
の処理で今要求されているブロツクを主記憶から
ブロツクロードしデータ・メモリ２０へ書き込
む。次に枠９０２の処理で要求されているアドレ
スのデータをデータ・メモリ２０から読み出しデ
ータレジスタ２２へ書き込み、最後に枠９０３で
デイレクトリ・メモリ１０の内容を更新する。枠
９０１の詳細を示したのが第６図である。第４図
で示した枠８０４とよく似た処理を行うが、カウ
ンタの＋１タイミングと繰り返し回数のみが異な
つている。枝９１および９３の処理は、枝９４の
処理から枠９００の処理を除いたものに等しく、
更に枝９２の処理は枝９１の処理から枠９０１，
９０３の処理を除いたものと全く等しい。

また、枝９５はこの発明による新しい制御手順
であつて、読み出しアドレスがブロツクの先頭を
指している（下位アドレス＝０）場合に実行され
る。

枝９７の場合は、データ・メモリ２０内に求め
るデータが存在するため、枠９３２の処理で該デ
ータを取り出す。次に枠９３５で該ブロツクのデ
ータを主記憶に書き戻すことなく無効化する。枝
９６及び枝９８の場合はキヤツシユメモリに変化
を残すことなく主記憶より読み出しアドレスのデ
ータを読み出し、読み出しデータレジスタ２２に
書き込んで処理を終了する。

以上に述べたように、ライト・スタツク及びリ
ード・スタツクのキヤツシユ命令を実現する制御
手段を導入することにより、メモリをスタツクと
して使用し、かつスタツクに対する書き込みにラ
イト・スタツク、スタツクの読み出しにリード・
スタツクのキヤツシユ命令を使用することによつ
てキヤツシユメモリと主記憶との間の不必要なデ
ータ転送を減少させ、スタツク操作の高速化を図
ることができる。

以下では、ライト・スタツク命令を用いてスタ
ツクにデータを書き出してゆく場合のスタツク上
のデータの状態、およびその時に主記憶との間で
受け渡しされるデータ語数について第７図〜第１
０図を用いて説明する。

第７図は、メモリ1002(h)番地（(h)は16進数を示
す）から100D(h)番地まで連続してデータを書き
込んでゆく場合のヒツトがミスヒツトかの別、処
理手段の流れ図のどの枝が使用されるかの別、各
キヤツシユ命令実行時の主記憶への書き出し回
数、主記憶からの読み込み回数についてまとめた
ものである。

ここでキヤツシユメモリの各ブロツクには異な
るキーアドレスを持つ有効なデータが存在してお
り、キヤツシユ・ミスヒツトを起すとブロツクの
内容のライトバツクが必要であるものとする。ま
た各ブロツクの境界アドレスは、第８図の破線で
示したところにあるものとする（これらの条件は
従来例で説明したものと同じである）。スタツク
への書き込みを開始する前のスタツクの先頭は
1001(h)番地であり、1001(h)以下のアドレスのデー
タは主記憶中に存在しているものとする。1002(h)
番地に対してライト・スタツク命令を実行する
と、キヤツシユ・ミスヒツトが発生して、第２図
の枝８４の制御手段が実行され、はじめにブロツ
ク中の古いデータ４語が主記憶に書き戻され、次
に1002(h)番地へ書き込むべきデータがブロツク内
の対応するデータセルに書かれ、最後に1000(h)，
1001(h)，1003(h)の各番地のデータが主記憶からブ
ロツク内の対応する各データセルへ読み込まれ
る。このときの状態を示したのが第８図の書き込
み後の図である。ここでは斜線で示した部分が主
記憶から読み込まれたデータ、格子縞で示した部
分がライトスタツク命令で書き込まれたデータで
ある。次に1003(h)に対するライトスタツク命令を
実行すると、キヤツシユはヒツトし、第２図枝８
２の制御手段によつて実行後のスタツクは第９図
の書き込み前の図のように1003(h)番地が斜線から
格子縞（書き込まれたデータを示す）に変わる。
次の1004(h)番地にたいするライト・スタツク命令
では、キヤツシユ・ミスヒツトとなり、第２図の
枝８９の制御手順が実行され、ブロツク内の古い
データ４語がライトバツクされたあと、同命令で
書き込まれるべきデータがブロツク中の1004(h)番
地に対応するデータセルへ書き込まれ、その後同
ブロツクは有効化されて、1005(h)〜1007(h)番地に
対応するデータセルには、主記憶からの読み込み
は行なわれず意味のないデータが残つたままの状
態である。しかしながら、これらのデータセル
は、引きつづくライト・スタツク命令が実行され
たときキヤツシユ・ヒツトして、ただちにデータ
が上書きされる。こうして100D(h)番地まで順に
ライト・スタツク命令により書き込みを行つた後
のスタツクの状態を示したのが第１０図である。
100C(h)〜100F(h)番地までのブロツクは、100C(h)
番地へ書き込みを行なつたとき有効化されるが、
書き込みを行つていない100E(h)，100F(h)の２つ
の番地に対応するブロツク中のデータセルには、
主記憶の同番地とは異なるデータが存在してい
る。しかしながら、スタツクの構造上、その先頭
（この場合100D(h)番地）よりも大きいアドレスに
対してメモリの読み書きが発生することはないか
ら、100E(h)，100F(h)の２つの番地はそのまま放
置して問題ない。以上の一連の書き込み処理につ
いて第７図を見ると、1002(h)，1004(h)，1008(h)，
100C(h)の４つのアドレスについてキヤツシユ・
ミスヒツトが発生しており、そのつど主記憶への
４語のライトバツクが発生しているが、主記憶か
らの読み込みは、1002(h)番地に対してライト命令
を実行したときの３語だけとなつている。この中
で主記憶からのデータ読み込みのうちむだと分か
るものは、1003(h)番地が読み込みのすぐ次のキヤ
ツシユ命令で上書きされてしまう１つだけで、従
来例の場合より大幅に減少している。

主記憶からの読み込み回数を従来例の第２０図
と比べると、12回のスタツクへのデータ書き込み
を実行した場合に、従来例では合計12回のメモリ
からのデータ読み込みがあり、そのうち不要と分
かるデータ読み込みが10回、それに対し第７図の
ライト・スタツク命令を使用した例では、主記憶
からのデータ読み込みが３回でこの内不要と分か
るものが１回である。このように、スタツクへの
連続的なデータ書き込みを行なう場合、ライト命
令を使用するよりも、ライト・スタツク命令を使
う方が、主記憶からの不要なデータ読み込みを大
幅に削減できることが分かる。

次に第１０図の状態からリード・スタツク命令
を用いて100D(h)番地〜1002(h)番地の12語のデー
タを読み出した時の動作について説明する。第１
０図の状態においては100D(h)番地〜1002(h)番地
のデータは全てキヤツシユメモリ内に存在するた
め12回のリード・スタツク命令は全てヒツトす
る。ただし100C(h)番地、1008(h)番地、1004(h)番
地に対するリード・スタツク命令は第５図の枝９
７によつて処理され、従つて該データが読み出さ
れると同時に該データを含むブロツクは無効化さ
れてキヤツシユメモリ内には存在しなくなる。ゆ
えに1002(h)番地まで読み出した後は第９図の書き
込み前の状態に戻つている。この状態においては
他のアドレスに対するキヤツシユアクセスによつ
て主記憶へ書き戻される可能性があるブロツクは
1000(h)〜1003(h)番地の１ブロツクのみであつて、
1004(h)〜100F(h)番地の３ブロツクは書き戻され
る可能性も必要性もない。従来例においては、上
記３ブロツクは主記憶に書き戻される必要性がな
いのにもかかわらず、書き戻される場合があつた
ため、明らかに不要と分る主記憶へのデータ書き
出しを行なつていたことになる。このようにメモ
リをスタツクとして用いる場合、データの読み出
しをリード・スタツク命令を用いることによつ
て、主記憶への不必要なデータ書き出しを削減で
きることが分る。

〔発明の効果〕

以上のように、この発明によれば、メモリをス
タツクとして使用し、その先端部分へ連続的にデ
ータを書き込む場合（特にキヤツシユメモリのブ
ロツクの大きさよりも多くのデータを書き込む場
合）に、主記憶からの不要なデータ読み込みが削
減され、書き込み時間が短縮されるという効果が
生じる。また、すでに読み出されてしまつたスタ
ツクの先端部分が不必要に主記憶へ書き戻される
ことが削減でき、後続のキヤツシユ命令に要する
処理時間が短縮される。

例えば、LISPやPROLOGプログラムをフアー
ムウエアで記述されたインタプリンタを用いて解
釈実行する場合に、実行制御情報をスタツクへ格
納する場合など、主記憶上にとられたスタツクへ
ある程度大きな一連のデータを連続書き込みする
場合に、キヤツシユ・ミスヒツトにともなう主記
憶からキヤツシユメモリへのむだなデータの読み
込みを削減することができ、主記憶アクセスに要
する時間を短縮できるものであり、この発明はき
わめて有益である。

【図面の簡単な説明】

第１〜１０図はこの発明に係るもので、第１図
はこの発明の一実施例のキヤツシユメモリのメモ
リ制御装置の構成図、第２図はキヤツシユメモリ
装置において、キヤツシユ命令としてライト・ス
タツク命令が指定された場合の制御手順の流れ
図、第３図は第２図の枠８００の処理を詳細に示
す処理内容図、第４図は第２図の枠８０４の処理
を詳細に示す処理内容図、第５図はキヤツシユメ
モリ装置において、キヤツシユ命令としてリー
ド・スタツク命令が指定された場合の制御手順の
流れ図、第６図は第５図の枠９０１の処理を詳細
に示す処理内容図、第７図はメモリへのデータ書
き込み時の処理結果を示す図表、第８図〜第１０
図は本発明の実施例においてスタツクにデータを
書き出してゆく場合のスタツク上のデータの状態
を示す状態図、第１１〜第２０図は従来例に係る
もので、第１１図は従来のキヤツシユメモリのメ
モリ制御装置の一例の構成図、第１２図はキヤツ
シユメモリ装置において、キヤツシユ命令として
書き込みが指定された場合の制御手順の流れ図、
第１３図は第１２図の枠６００の処理を詳細に示
す処理内容図、第１４図は第１２図の枠６０４の
処理を詳細に示す処理内容図、第１５図はキヤツ
シユメモリ装置において、キヤツシユ命令として
読み出しが指定された場合の制御手順の流れ図、
第１６図は第１４図の枠７０１の処理を詳細に示
す処理内容図、第１７図〜第１９図はキヤツシユ
メモリ装置において、メモリをスタツクとして使
用し、スタツクにデータを書き出してゆく場合の
スタツク上のデータの状態を示す状態図、第２０
図はメモリへの書き込み時の処理結果を示す図表
である。 図において、１０はデイレクトリ・メモリ、１
１は有効フラツグ部、１２は変更フラツグ部、１
３はキーアドレス部、１４は比較器、２０はデー
タメモリ、２１は書き込みデータ・レジスタ、２
２は読み出しデータ・レジスタ、２３はキヤツシ
ユ・データバス、２４は主記憶インタフエース、
３０はアドレス・レジスタ、３１は上位アドレス
部、３２は中位アドレス部、３３は下位アドレス
部、３４はカウンタ、３５はデータ選択器、４１
はキヤツシユ命令レジスタ、４３は制御回路、４
４は制御信号線、４６はキヤツシユ命令デコー
ダ、４７はスタツク操作命令用キヤツシユ命令デ
コーダ、５０はスタツク操作命令用制御回路、５
１は制御信号線。なお、図中、同一符号は同一、
又は相当部分を示す。

Claims (1)

【特許請求の範囲】
1. １ データの書き込みを行なう際に、該データを
   キヤツシユメモリ内のみに書き込み、該書き込ん
   だ領域が後に別のアドレスのキヤツシユアクセス
   に使用される時に、該領域に書き込まれているデ
   ータを主記憶に書き戻すライト・スワツプ方式の
   キヤツシユメモリのメモリ制御装置において、書
   き込みアドレスのデータセルを含むブロツクでな
   るデータの管理単位がキヤツシユメモリ内に存在
   しない場合、当該ブロツクをキヤツシユメモリ内
   に確保した後に書き込みデータを当該アドレスの
   データセルに書き込み、ブロツク内の他のデータ
   セルについては主記憶からデータの読み込みを行
   なう、ライト・スワツプ方式における第１の書き
   込み制御手段と、上記第１の書き込み制御手段と
   同じ制御を行ないつつ、書き込みアドレスがブロ
   ツクの先頭データセルであつて、かつ当該ブロツ
   クがキヤツシユメモリ内に存在しない場合に限
   り、当該ブロツクをキヤツシユメモリ内に確保し
   た後に書き込みデータを当該アドレスのデータセ
   ルに書き込み、ブロツク内の他のデータについて
   は主記憶から読み出すことなく当該ブロツクを有
   効化せしめる第２の書き込み制御手段と、読み出
   しアドレスのデータセルを含むブロツクが、キヤ
   ツシユメモリ内に存在しない場合に、当該ブロツ
   クをキヤツシユメモリ内に確保した後主記憶より
   該ブロツクのデータを読み出してキヤツシユメモ
   リに格納する第１の読み出し制御手段と、上記第
   １の読み出し制御手段と同じ制御を行ないつつ、
   読み出しアドレスがブロツクの先頭データセルの
   場合で、かつ当該ブロツクがキヤツシユメモリ内
   に存在しなかつた場合は、当該データのみを主記
   憶から読み出し、キヤツシユメモリには何ら変化
   を残さない制御を行ない、読み出しアドレスがブ
   ロツクの先頭データセルの場合で、かつ当該ブロ
   ツクがキヤツシユメモリ内に存在した場合には、
   当該データをキヤツシユメモリから読み出した
   後、キヤツシユメモリ内の該ブロツクを直ちに無
   効化せしめる第２の読み出し手段を備えたことを
   特徴とするメモリ制御装置。