JPH01251248A - スタックデータ構造用キャッシュ制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 、［発明の目的］ （産業上の利用分野） この発明は、主記憶に確保されたスタックを直接アクセ
スすることなくスタックアクセスが実現可能なタックデ
ータ構造用キャッシュメモリ制御方式に関する。

（従来の技術） 主記憶内に確保したスタックを利用する情報処理装置で
は、通常のメモリスペースとスタック用のメモリスペー
スとを区別せず、したがってキャッシュメモリも共通に
使用するのが一般的である。このような情報処理装置に
おけるキャッシュメモリの構成には、離散的なメモリア
クセスに対してヒツト率の高い連想記憶方式を用い、マ
ルチプロセッサ、入出力等を考慮してライトスル一方式
（即ち書込み時には主記憶にも書込みを行ってキャッシ
ュメモリの書込み内容と主メモリの対応領域の内容とを
一致させる方式）が適用される。

一方、スタックに対するメモリアクセスには、−度書込
んだデータはその直後に読出されることが多いという特
徴がある。このため、スタックアクセスにおいて通常メ
モリアクセスと共通のキャッシュメモリを用いる従来方
式では、上記ライトスル一方式による主記憶書込みのバ
スサイクル終了まで次の読出しアクセスが行えず、性能
が低下する問題があった。また、スタックアクセスでキ
ャッシュメモリに格納されたデータが、通常メモリアク
セスでキャッシュメモリから追出され、ヒツト率が低下
する問題もあった。

（発明が解決しようとする課８） 上記したように従来は、スタックアクセスにおいても通
常のメモリアクセスと同様に共通のキャッシュメモリを
利用していたため、キャツシュヒツト率の低下、更には
スタックアクセスのオーバヘッドの増加等を招く問題が
あった。

したがってこの発明は、スタックアクセスの特徴を最大
限生かすことが可能な新規なスタックデータ構造専用の
キャッシュメモリ（ブロックメモリ）により通常最も頻
繁に発生するスタックアクセスの高速化が図れるように
することを解決すべき課題とする。

〔発明の構成］ （課題を解決するための手段） この発明は、主記憶に確保されたスタックのスタックフ
レームと対応付けられる複数ブロックから成る循環バッ
ファ方式のブロックメモリをスタックデータ構造専用の
キャッシュメモリとして設け、スタック書込み要求され
た場合にはブロックメモリ内の最新の有効ブロックの次
のブロックを対象にデータ書込みを行い、この書込みに
よりブロックメモリ内の有効ブロック数が第１の所定数
に達した場合にはブロックメモリ内の最も古い有効ブロ
ックのデータをスタックに転送し、スタック読出しが要
求された場合にはブロックメモリ内の最新の有効ブロッ
クを対象にデータ読出しを行い、この読出しによってブ
ロックメモリ内の有効ブロック数が第２の所定数を下回
り、且つスタックに有効スタックフレームが存在する場
合には、最新の有効スタックフレームの内容をブロック
メモリ内の最も古い有効ブロックの直前のブロックに転
送するようにしたことを特徴とする。

（作用） スタックに対するメモリアクセスには、前記した ■−度書込んだデータはその直後に読出されることが多
い。

という特徴の他に、 ■スタックポインタの指すアドレス近傍にアクセスが集
中する。

■書込み時には何ワードかまとめて書込み、その書込み
タイミングをさほど気にしない。即ち、ライトスル一方
式を適用する必要がない。

という特徴がある。上記の構成は、この特徴を利用した
もので、新しい有効ブロックはど先に読出すことが可能
な構造となっており、−度ブロックメモリに書込んだ後
は必ず同ブロックメモリから高速に読出すことができる
。また、主記憶への追出しは最も古い有効ブロックから
行われるので、このブロックのデータの転送中に同デー
タを参照するスタックアクセスが発生する虞は（上記■
。

■のスタックアクセスの特徴から明らかなように）なく
、したがって上記ブロック転送をバスの空き時間を利用
してタイミングを気にせずに行うことができ、スタック
アクセス（特に書込み直後の読出しアクセス）のオーバ
ヘッドを低下することができる。

（実施例） 第１図はこの発明を適用する情報処理装置のこの発明に
直接関係する部分の一実施例を示すブロック構成図であ
る。同図において、１０はＣＰＵ。

２０は各種プログラムデータ等が格納される主記憶であ
る。この主記憶２０には、レジスタ退避等に供されるス
タック（スタック領域）２１が必要に応じて確保される
。ＣＰＵｌ０には、スタック２１等を管理するためのス
タック管理機構１１．およびスタック２１のスタックフ
レームと対応付けられる複数ブロックから成る循環バッ
ファ方式のブロックメモリ（以下、ＢＭと称する）１２
が設けられる。８Ｍ１２はスタックデータ構造専用のキ
ャッシュメモリとして設けられたもので、スタックに格
納すべきデータを同スタックに代えて格納するように構
成される。

スタック管理機構１１には、スタック書込み要求に対し
てスタック２１に代えて書込むべき８Ｍ１２内ブロツク
（の位置）を指定するためのブロックメモリポインタＢ
ＭＰを設定するブロックメモリポインタレジスタ（以下
、ＢＭＰレジスタと称する）　１３と、８Ｍ１２が存在
しない（従来例の）場合であればスタック書込み要求に
対する書込み先となるスタック２１内スタツクフレーム
（の位置）を指定するための周知のスタックポインタＳ
ＰＩを設定するスタックポインタレジスタ（以下、ＳＰ
Ｉ　レジスタと称する）１４と、スタックポインタＳＰ
２を設定するスタックポインタレジスタ（以下、ＳＰ２
レジスタと称する）１５とが設けられる。このスタック
ポインタＳＰ２は、８Ｍ１２において有効なデータが格
納されている最も古いブロック（最も古い有効ブロック
）をスタック２１に追出す際の追出し先（スタック２１
内スタツクフレーム）を指定するのに用いられる。ここ
で、ブロックメモリポインタＢＭＰの初期値は８Ｍ１２
の先頭ブロックを示ず０、スタックポインタｓｐｉ。

ＳＦ３の初期値は上記ｔａ２０内スタック２１の先頭ス
タックフレームを示すＳＰｏｒｇである。なお、８Ｍ１
２内ブロツクおよびスタック２１内スタツクフレームは
複数エントリから構成されており、したがってそのエン
トリを指定するためには、オフセット（オフセットアド
レス）も必要であるが、ブロック（スタックフレーム）
を指定する情報とオフセットにより目的エントリをアク
セスする技術は周知であることから、オフセットについ
ては説明を省略する。

次に、第１図の構成の動作を第２図のフローチャートを
参照して説明する。まず、ＣＰＵｌ０においてスタック
アクセス要求（命令）が発せられると、スタック管理機
構１１は同要求が（スタック２１への）書込み要求であ
るか否（読出し要求である）かを調べ（ステップＳ１）
、書込み要求であればＢＭＰレジスタ１３に設定されて
いるブロックメモリポインタＢＭＰの指すＢＭＬ２内ブ
ロツブロックとして、従来であればスタック２１へ格納
すべきデータの書込みを行う（ステップＳ２）。ここで
はＳＰＩ　レジスタ１４に設定されているスタックポイ
ンタＳＰＩの指すスタック２１内スタツクフレームへの
書込みが行われないことに注意されたい。

スタック管理機構１１は、ステップＳ２を終了するとＢ
ＭＰレジスタ１３のブロックメモリポインタＢＭＰを次
のブロックを指定するように進め、ＳＰＩ　レジスタ１
４のスタックポインタＳＰ１を次のスタックフレームを
指定するように進める（ステップ８３〜Ｓ６）。ここで
、上記した“次のブロック“とは、現ＢＭＰが８Ｍ１２
内最終ブロツクを指すＢＭＰｍａｘに一致していなけれ
ばＢＭＰ　十１で示されるブロックであり、Ｂ　Ｍ　Ｐ
　ｌ１ａｘに一致しているならば０で示されるブロック
（先頭ブロック）である。即ち、８Ｍ１２は、循環バッ
ファ方式で用いられる。明らかなように、ステップｓ３
〜Ｓ６実行後のポインタＢＭＰの指定するスタック管理
機構ｌｌ内ブロックの直前のブロックは、最新の有効ブ
ロックとなっている。

スタック管理機構１１は、ステップ８３〜ｓ６を終了す
ると、８Ｍ１２内の有効ブロック数が第１の所定数（例
えば８Ｍ１２が持つブロック数）に達したか否かをＳＰ
Ｉレジスタ１４のスタックポインタＳＰＩをもとに（例
えばＳＰＩがＳＰｏｒｇ＋Ｂ　Ｍ　Ｐ　ａ＋ａｘより大
きいか否かにより）判定する（ステップＳ７）。もしス
テップＳ７の判定がＹＥＳであれば（ここでは、８Ｍ１
２がＦＵＬＬ状態になったことが判定されたならば）、
スタック管理機構１１は空きブロック（無効ブロック）
を確保する（ここではＢＭＰの指す８Ｍ１２内ブロツク
を空きブロックとする）ために、ＢＭＰレジスタ１３の
ブロックメモリポインタＢＭＰの指す８Ｍ１２内ブロツ
クの内容をＳＰ２レジスタ１５のスタックポインタＳＰ
２の示すスタック２１内スタツクフレームへ転送し、し
かる後にスタックポインタＳＰ２を次のスタックフレー
ムを指すように進めてスタックアクセス（書込み）要求
に対する処理を終了する（ステップＳ８．３９）。これ
に対して、ステップＳ７の判定がＮＯであれば（ここで
は、８Ｍ１２がＦＵＬＬ状態になければ）、スタック管
理機構１１はそのままスタックアクセス（書込み）要求
に対する処理を終了する。なおＳＦ３＞ＳＰＯｒｇ場合
には、Ｓ　Ｐｏｒｇ　−８Ｐ２−１で示される各スタッ
クフレームが有効スタックフレームとなっていることは
明らかである。

次に、スタックアクセス要求が（スタック２１からの）
読出し要求である場合について説明する。

この場合、スタック管理機構１１はＳＰＩレジスタ１４
のスタックポインタＳＰＩを直前のスタックフレームを
指定するように戻し、且つＢＭＰレジスタ１３のブロッ
クメモリポインタＢＭＰを旧ＢＭＰ（ポインタＢＭＰｏ
ｌｄ）として内部保持する（ステップＳＩＯ，５ｌｌ）
。次にスタック管理機構１１は、ＢＭＰレジスタ１３の
ポインタＢＭＰを直前のブロックを指定するように戻し
くステップＳ１２〜５１４）、このブロック（即ち、最
新の有効ブロック）からの（従来であればキャッシュメ
モリまたはスタック２１から読出すべき）データの読出
しを行う（ステップ５１５）。なお、上記した“直前の
ブロック″とは、ステップ８１２〜Ｓ１４実行前のＢＭ
Ｐ　（ＢＭＰｏｌｄ　）がＢＭＬ２内先頭ブロックを指
す０に一致していなければＢＭＰ−１で示されるブロッ
クであ、す、一致しているならばＢ　Ｍ　Ｐ　ＩａＸで
示されるブロック（最終ブロック）である。

スタック管理機構１１は、ステップＳ１５を終了す゛る
と、８Ｍ１２内の有効ブロック数が第２の所定数を下回
り、且つスタック２■に有効スタックフレームが存在す
るか否かを判定する。ここでは、上記の第２の所定数は
８Ｍ１２が持つブロック数であり、したがってステップ
３１５を行えば必ず第２の所定数を下回ることから、こ
の点に関する判定は不要である。そこでここでは、上記
２種の判定のうち、スタック２１に有効スタックフレー
ムが存在するか否かの判定だけが、例えばＳＰ２レジス
タ１５のスタックポインタＳＰ２がＳＰｏｒｇより大き
いか否かをもとに行われる（ステップ８１６）。もし、
ＳＦ３がＳＰｏｒｇより大きい場合、即ちスタック２１
に有効スタックフレームが存在する場合、スタック管理
機構１１はスタック２１内の最新の有効スタックフレー
ムを指定するためにＳＰ２レジスタ１５のスタックポイ
ンタＳＰ２を戻した後、この新たなＳＦ３の指すスタッ
ク２■内のスタックフレーム（最新の有効スタックフレ
ーム）の内容をステップＳｌｌで内部保持しておいたＢ
　Ｍ　Ｐ　ｏｌｄ　　（旧ＢＭＰ）の指す８Ｍ１２内ブ
ロツクへ転送し、スタックアクセス（読出し）要求に対
する処理を終了する（ステップＳ　１７．　　Ｓ　１８
）。これに対して、ステップＳ１Ｂの判定がＮｏであれ
ば（スタック２１に有効なスタックフレームが存在しな
ければ）、スタック管理機構１１はそのままスタックア
クセス（読出し）要求に対する処理を終了する。

以上は、１つのスタックアクセス要求を実行する毎にス
タックポインタＳＰＩ、　　ブロックメモリポインタＢ
ＭＰが更新される場合について説明したが、ローカル変
数処理などのように１つのスタックフレームを対象とし
て書込み／読出しが繰返される場合にも、応用できる。

また、前記実施例では、前記のスタック管理に用いられ
るスタックポインタＳＰＩの他に、スタックポインタＳ
Ｐ２およびブロックメモリポインタＢＭＰを設けて、ス
タックデータ構造専用のキャッシュメモリ制御を行うも
のとして説明したが、ＳＦ３゜ＢＭＰを用意しなくても
ＳＦ３．ＢＭＰに要求される機能はＳＰｌと８Ｍ１２の
ブロック数をもとに実現することは可能である。

［発明の効果］ 以上詳述したようにこの発明によれば、次に列挙する作
用効果を奏することができる。

■　スタックアクセスの特徴を最大限生かすことが可能
な新規なスタックデータ構造専用のギャッシュメモリ（
ブロックメモリ）を対象としてスタックアクセスが行わ
れるため、処理速度が向上する。

■　スタック書込みアクセスにおいて、主記憶への書込
みのためのバスアクセスが生じないため、特にスタック
書込みアクセスの直後にスタック読出しアクセスを行お
うとした場合のオーバヘッドが解消される。

■　ブロックメモリから主記憶への転送（追出し）対象
となるブロックは、その時点で最も古い有効ブロックで
あるため、このブロックのデータの転送中に同データを
参照するためのスタ・ツクアクセスが発生ずる虞はなく
、シたがって上記の転送はバスの空き時間に行えばよく
、この転送に起因するメモリアクセスのオーバヘッドは
殆どない。

■　ブロックメモリから主記憶へ転送された（追出され
た）ブロックデータは、同データが参照されるまでには
ブロックメモリに戻され、データ参照時には最新のブロ
ックデータとなるため、ブロックメモリを対象とするデ
ータ参照が行える。

【図面の簡単な説明】

第１図はこの発明の一実施例を示すブロック構成図、第
２図は動作を説明するためのフローチャートである。 ■１・・・スタック管理機構、１２・・・ブロックメモ
リ（ＢＭ）　、１３・・・ブロックメモリポインタレジ
スタ（ＢＭＰレジスタ）、１４・・・スタックポインタ
レジスタ（Ｓ　Ｐｉ　レジスタ）、１５・・・スタック
ポインタレジスタ（Ｓ　Ｐ２レジスタ）、２０・・・主
記憶、２１・・・スタック。 出願人代理人　　弁理士　鈴江武彦 第１図 第２図

Claims (1)

【特許請求の範囲】
1. 主記憶に確保されたスタックに格納すべきデータを同ス
   タックに代えて格納するための上記スタックのスタック
   フレームと対応付けられる複数ブロックから成る循環バ
   ッファ方式のブロックメモリと、スタック書込み要求に
   応じ上記ブロックメモリ内の最新の有効ブロックの次の
   ブロックを対象にデータ書込みを行うブロックメモリ書
   込み手段と、このブロックメモリ書込み手段の書込みに
   より上記ブロックメモリ内の有効ブロック数が第１の所
   定数に達した場合に上記ブロックメモリ内の最も古い有
   効ブロックの内容を上記主記憶に転送して上記スタック
   に積む第１転送手段と、スタック読出し要求に応じ上記
   ブロックメモリ内の最新の有効ブロックを対象にデータ
   読出しを行うブロックメモリ読出し手段と、このブロッ
   クメモリ読出し手段の読出しによって上記ブロックメモ
   リ内の有効ブロック数が第２の所定数を下回り、且つ上
   記スタックに有効スタックフレームが存在する場合には
   、最新の有効スタックフレームの内容を上記ブロックメ
   モリに転送し、同メモリ内の最も古い有効ブロックの直
   前のブロックに書込む第２転送手段とを具備し、上記ス
   タック書込みまたは読出し要求に応じて上記ブロックメ
   モリをキャッシュメモリとしてアクセスするようにした
   ことを特徴とするスタックデータ構造用キャッシュ制御
   方式。