JPH01126730A - スタック・メモリ装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は計算機におけるスタック機能を少ないハードウ
ェアによって効率よく実現することにより処理速度を増
大させて複雑な応用プログラムを広い範囲で利用可能に
するためのものである。

（従来の技術） スタック機能は、計算機の動作において一時的に状態を
保存し、関連する他の動作が終了した時点で前記保存し
た状態に復帰する機能であり、古くから頻繁に使用され
てきた基本的な機能である。一般にスタックは複数の状
態を次々に積み上げて論理的に無限のエントリを保持し
得るよう構成する必要がある。ところがハードウェアの
量的な制限により現実にはこれをすべてハードウェアで
実現することは困難である。この問題を解決するため、
従来比較的高価な少量の高速メモリと比較的安価な大容
量の低速メモリとの組み合わせにより実現されてきた。

この２階層のメモリの間のデータの出し入れは動作が複
雑であり、従来主としてソフトウェアおよびマイクロプ
ログラムによって実現されてきた。

（発明が解決しようとする問題点） スタック操作は非常に頻繁に発生するものであり、その
実現効率はシステム効率に大きく影響をおよぼすもので
ある。とくにＬＩＳＰやＰＲＯＬＯＧに代表され・るよ
うなスタック操作をプログラミング言語自体の基本メカ
ニズムとして含む言語の実行においてはその効率が極め
て重要である。論理的に無限の状態を保存し得る状態を
作り出す為には従来、システムの基本的機能としてソフ
トウェアおよびファームウェアによって実現されてきた
が、効率上およびシステム資源の限界上多くの問題を抱
えている。したがって従来より多くの発明がなされてき
たが、ハードウェアによるサポートによる実現に於いて
は複雑な動作に対応してハードウェア量が増加する傾向
があった。

より具体的には、２つのメモリ階層の間の入れ替えを行
うタイミングの検出と実際の入れ替え動作の効率が大き
な問題であった。

本発明の目的はこれらの問題点を解決したスタック・メ
モリ装置を提供することにある。

：（問題点を解決するための手段） 本発明は、スタックとして使用する２のべき乗のエント
リを格納する高速メモリと、スタック内容を退避するた
めの外部メモリと、スタック・トップカウンタと、スタ
ック・ベースカウンタと、前記２種類のカウンタの内容
を１だけ減算した出力を発生する減算器Ａと、前記スタ
ック・ベースカウンタの内容を１だけ減算した出力を発
生する減算器Ｂと、前記２種類のカウンタの内容および
前記減算器Ａ、前記減算器Ｂの出力を互いに比較し一致
を検出する一致回路と、前記スタック・ベースカウンタ
の最上位への桁上がり信号でセットされるフリップフロ
ップから成り、スタックプッシュ操作において前記一致
回路によって前記メモリのエントリがすべて満たされた
事を検出したときに前記フリップフロップの状態が変更
されるまで前記外部メモリに前記高速メモリの内容を退
避し、また、スタックポツプ捜査において前記一致回路
によって前記メモリの内容がすべて空になった事を検出
したときには前記フリップフロップの状態が変更される
まで前記外部メモリより高速メモリに復帰することによ
り、常にスタックの先頭のデータ群を前記高速メモリに
保持することを特徴とするスタック・メモリである。

（作用） スタック機能は、ある時点での状態を保持し、さらに引
き続く時点の状態を次々に保持し、アクセスされたとき
には最も最近に保持された状態を出力するラストインフ
ァーストアウト（Ｌａｓｔ　ＩｎＦｉｒｓｔ　０ｕｔ）
メモリ（ＬＩＦＯメモリ）で実現される。ここで前者を
ブツシュ操作、後者をポツプ操作と呼ぶ。ブツシュ操作
は論理的には無限回行える必要があるが、ハードウェア
量は限界がある。スタック操作を効率よく実現するため
には少量の高速だが高価なメモリと低速だが安価な故に
大容量化が可能なメモリとの組み合わせによって構成す
る。

すなわち、最近にブツシュされた状態はアクセスされる
可能性が最も高いため、できる限り高速なメモリ上に置
いておくことが望ましい。ここで高速メモリへのブツシ
ュ操作が続き、高速メモリをオーバーフロラするときに
は、古い状態から順に低速メモリへの掃き出しを行い、
高速メモリは引き続くブツシュ操作に備えてクリアーす
る必要がある。この内容入れ替えのタイミングと入れ替
え処理の高速化が重要である。

本発明のスタックメモリは前記高速メモリのベースを指
すスタックベースカウンタとブツシュｌポツプ操作のた
めの前記メモリのアドレスを指すスタックトップカウン
タによってスタック操作を実現するとともに、前記高速
メモリがオーバーフロウするか否かをハードウェアによ
って検出し、高速な内容入れ替え動作を実現するための
ものである。

（実施例） 以下、本発明のスタックメモリの実施例について図面を
用いて詳細に説明する。

第１図は本発明の一実施例を示すブロック図である。図
において１０はスタックとして使用する２のべき乗のエ
ントリを格納する高速メモリ、２０は外部メモリ、３０
はスタックトップカウンタ（ＳＴと略称する）、４０は
スタックベースカウンタ（ＳＢと略称する）、５０は減
算器Ａ１６０は減算器Ｂ１７０は一致回路、８０はフリ
ップフロップ、１１，５１，７１．７２はセレクタであ
る。

簡単のため高速メモリ１０のエントリ数（アドレス）が
４である例について説明する。初期状態では５Ｔ３０お
よび５Ｂ４０はともに００”にセットされ、フリップフ
ロップ８０はリセットされる。

（ブツシュ操作） ブツシュ操作が行われるときの各セレクタは以下の状態
にセットされる。すなわち、セレクタ１１の入力は線３
０１、セレクタ７１の入力は線３０１、セレクタ７２の
入力は線６０１が選ばれる。初期状態におけるブツシュ
操作は、５Ｔ３０の内容が線３０１、セレクタ１１、線
１１１を介して番地付けされ、高速メモリ１０の“００
パ番地へデータレジスタ（図示せず）の内容が書き込ま
れることで実現され、５Ｔ３０はこの書き込み終了後に
１加算される。すなわち５Ｔ３０の出力は書き込み終了
時点で“０１″となり、次のブツシュ操作に備えた準備
が行われる。この値は、線３０１、セレクタ７１、線７
１１を介して一致回路７０の一方の入力として与えられ
る。−数回路７０の他方の入力は５Ｂ４０から１だけ減
算された値、すなわち１１°”である。−数回路はこ゛
の時点では一致を検出しないためこれ以。

上の動作を生起しない。

引き続きブツシュ操作が行われた時には一致回路７０が
一致を検出するまで上記と同様の動作が実行される。

（退避処理） 一致回路７０が一致を検出したときの５Ｔ３０と５Ｂ４
０の値は共に’ｏｏ”であり、高速メモリ１０のエント
リがすべて使われた状態を示している。この状態のとき
にブツシュ操作が行われると高速メモリ１０の内容を外
部メモリ２０へ掃き出す退避処理が必要となるがこのと
きの各セレクタの状態は以下のとおりである。すなわち
セレクタ１１の入力は線４０１、セレクタ５１の入力は
線３０１、セレクタ７１の入力は線５０１、セレクタ７
２の入力は線４０１が選択される。以後高速メモリ１０
の外部メモリ２０への退避処理が行われる。まず、８Ｂ
４０の内容がアドレスとして高速メモリ１０に与えられ
、“００′”番地の内容が外部メモリ２０への転送され
た後５Ｂ４０の値が１だけ加算される。５Ｂ４０の最上
位桁の出力は線４０２を介してフリップフロップ８０に
与えられ、桁上がりが起こるとセットされる。上記動作
はこのフリップフロップ８０がセットされるまで行われ
る。すなわち高速メモリ１０の半分の量が退避されるこ
とになる。最終エントリの退避が終了した時点での５Ｂ
４０の内容は“１０”になっている。したがってこの後
のスタック・ベースは高速メモリ１０の後半の先頭位置
となる。この状態からさらにブツシュ操作が行われ、高
速メモリ１０が再び一杯になるとフリップフロップ８０
がセットされているため高速メモリ１０の後半部分が退
避されスタックベースは再度１１００１１番地に更新さ
れる。以後の復帰処理終了は５Ｂ４０の最上位の桁上が
りによってフリップフロップ８０がリセット、される時
点である。また、高速メモリ１０から外部゛メモリ２０
への退避が行われたことは（図示しない）外部装置によ
って記憶される。

（ポツプ操作） ポツプ操作が行われるときの各セレクタの状態は以下の
とおりである。すなわち、セレクタ１１の入力は線５０
１、セレクタ５１の入力は線３０１、セレクタ７１の入
力は線５０１、−セレクタ７２の入力は線４０１が選択
されている。５Ｔ３０は次にブツシュされるべき高速メ
モリ１０のアドレスを指示しているため、ポツプ操作に
おいて減算器５０によって１だけ以前のアドレスの読み
だしが行われることになる。この読みだしが終了した時
点で８Ｔ３０は１だけ減算される。−数回路７０には５
Ｂ４０の値と、５Ｔ３０の値から１だけ減算された値が
入力されている。ポツプ操作は一致回路７０が一致を検
出するまでは上記動作の繰り返しで実現される。

（復帰処理） 復帰処理が行われるときの各セレクタの状態は以下のと
おりである。すなわち、セレクタ１１の入力は線５０１
、セレクタ５１の入力は線４０１、セレクタ７１の入力
は線３０１、セレクタ７２の入力は線６０１が選択され
ている。前記ポツプ操作中に一致回路７０が一致を検出
するのは５Ｂ３０の内容が０１”、８Ｂ４０の内容が“
’ｏｏ”のときである。この直後には８Ｔ３０は”ｏｏ
’”に更新され、この時点でポツプ操作が行われるとア
ドレスパ１１”へアクセスが行われる。ここでもし、以
前に退避処理が行われていた時には復帰処理が行われな
ければならない。復帰は５Ｂ４０から１だけ減算された
アドレス１１１１＋１へ行われ、読みだしが終了した時
点で５Ｂ４０の値が１だけ減算される。この操作が５Ｂ
４０の最上位の桁下がりによってフリップフロップ８０
がリセットされるまで繰り返される。この操作によって
高速メモリ１０の半分の内容が高速メモリ１０へ復帰さ
れる。尚、復帰処理は外部装置によって高速メモリ１０
の内容が外部メモリ２ｏに退避されていることがわかっ
ているときのみ行われるのは言うまでもない。

以上の４種の動作説明により、実施例の内容がすべて説
明された。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図である。 図において、１０はスタックとして使用する２のべき乗
のエントリを格納する高速メモリ、２０は外部メモリ、
３０はスタックトップカウンタ、４０はスタックベース
カウンタ、５０．６０は減算器、７ｏは一致回路、８０
はフリップフロップ、１１，５１，７１．７２はセレク
タである。 工業技術院長 飯塚十三

Claims (1)

【特許請求の範囲】
1. スタックとして使用する２のべき乗のエントリを格納す
   る高速メモリと、スタック内容を退避するための外部メ
   モリと、スタック・トップカウンタと、スタック・ベー
   スカウンタと、前記２種類のカウンタの内容を１だけ減
   算した出力を発生する減算器Ａと、前記スタック・ベー
   スカウンタの内容を１だけ減算した出力を発生する減算
   器Ｂと、前記２種類のカウンタの内容および前記減算器
   Ａ、前記減算器Ｂの出力を互いに比較し一致を検出する
   一致回路と、前記スタック・ベースカウンタの最上位へ
   の桁上がり信号でセットされるフリップフロップから成
   り、スタックプッシュ操作において前記一致回路によっ
   て前記メモリのエントリがすべて満たされた事を検出し
   たときに前記フリップフロップの状態が変更されるまで
   前記外部メモリに前記高速メモリの内容を退避し、また
   、スタックポップ操作において前記一致回路によって前
   記メモリの内容がすべて空になった事を検出したときに
   は前記フリップフロップの状態が変更されるまで前記外
   部メモリより高速メモリに復帰することにより、常にス
   タックの先頭のデータ群を前記高速メモリに保持するこ
   とを特徴とするスタック・メモリ装置。