JPS6142303B2

JPS6142303B2 -

Info

Publication number: JPS6142303B2
Application number: JP53156972A
Authority: JP
Inventors: Jeemusu Moogan Dagurasu; Suteiibun Manisu Barii
Original assignee: NCR Corp
Current assignee: NCR Voyix Corp
Priority date: 1977-12-22
Filing date: 1978-12-21
Publication date: 1986-09-20
Also published as: GB2011135B; GB2011135A; FR2412889A1; FR2412889B1; DE2854782C2; US4229789A; JPS5491153A; DE2854782A1

Description

【発明の詳細な説明】この発明は転送システムに関し、特に、低速大
容量バツク・アツプ記憶装置からの情報群を記憶
すべき高速小容量常用記憶装置の位置を選択する
選択システムに関する。

各組が固定数の構成要素から成る情況下におい
て、該組が満杯であり、そこに新たな構成要素を
加えることを希望する場合に、該要素の交換に関
する問題が発生する。この発明は、該１組の構成
要素が最近使用された情報ブロツクの再使用の蓋
然性が高い場合の置換問題の経済的解決を与え、
大型データ処理システムのメモリー・システムに
ついて発生する特別な問題に対して解決を与える
ものである。

単一の中央処理ユニツト、または複数の処理ユ
ニツトのいずれかで実行する数個のコンピユー
タ・プログラムが１つのメモリーを共有するよう
な方式は種々知られている。このような方法で、
プログラムによつて共有されるメモリーは直接接
続された両立性記憶装置の実際の容量よりも屡々
大きい容量のごく大きな記憶容量を必要とする。
このような状態に適応させるために、「仮想記
憶」の概念が使用される。該仮想記憶装置はセグ
メント、またはブロツクに分けられ、該各ブロツ
ク、またはセグメントは必要に応じて交換し得る
ように、主記憶装置全体にランダムに置かれる多
数の頁を有することができる。

電子式コンピユータにおいては、すべての情報
が直ちに制御され、処理され得るような方式で記
憶されることが望ましい。最高の処理速度を達成
するために、最良の記憶装置は、少くも、最大の
蓋然性のある問題を、最高速度で処理することを
要求できる程度の大きさの容量を持たなければな
らない。しかし、高速メモリーは高価であるた
め、他の該大容量高速メモリーに代え得るものが
提案された。この問題に対する経済的且つ実用可
能な解決方法の１つは、すべての希望する問題に
対して要求される情報のすべてを記憶するために
十分な容量を持つ大容量低速メモリーを併せ使用
することである。小容量高速メモリーも同時に使
用され、すべてのプログラムはすべての情報が全
低速メモリーと同様に拡大された容量を持つ高速
メモリーに記憶されているかの如くに書くことが
できる。それによつて、頁転送、または頁置換の
全システムはプログラムにとつては「透明」とな
る。

かゝる仮想メモリー記憶構成のための転送、ま
たは置換システムの１部として、第３の「連想」
メモリーが使用される。それは低速メモリーに記
憶されているデータは与えられたときには高速メ
モリーにも含まれるということを表わすものであ
る。コンピユータで作業中の与えられたプログラ
ムが特定の情報ワードを要求する場合、その語が
高速メモリーにあるかどうかのチエツクが行なわ
れる。該情報が高速メモリーにある場合は直ちに
引出されて使用される。該ワードが高速メモリー
にない場合は、該要求するワードは低速バツク・
アツプ・メモリーから高速メモリーに転送され
る。しかし、それは、該バツク・アツプ記憶装置
が低速のため、各種与えられたプログラムの命令
の順次的実行の過程を通して、該情報の交換を単
一ワード基準で行なうのは実際的でないというこ
とがわかつた。該転送による遅延は単一ワードの
転送か、またはワードのブロツクの転送かにほと
んど無関係であるということもわかつた。更に、
経験によると、あるワードが要求されると、その
場所の他のものもまた、要求プログラムまたは命
令プログラムの命令の実行過程中に必要とされる
蓋然性が高いということがわかつた。従つて、情
報ワードがバツク・アツプ・メモリーから要求さ
れるということが決定された場合、該バツク・ア
ツプ・メモリーからのこのワードを含むブロツク
全部を該高速メモリーに転送することにした。

前述したデータ・ブロツクの低速から高速コア
への転送の機械化は高速メモリーのアドレスに空
ブロツクがある限りにおいてのみ有効である。従
つて、高速メモリーが満杯の場合に置換の問題が
発生する。情報ブロツクの置換が要求される場
合、理想的置換基準は常に、最も長い間再使用さ
れなかつた情報ブロツクを置換させることであ
る。不幸にも、計算又は命令の実行の過程中に、
この基準に従つて実際に決定することは、不当に
時間を浪費し、そのため実際的ではない。そのた
め、置換されるべきブロツクをランダムに選択す
るか、先入先出（FIFO）基準で選択を行なつて
いる。現存するシステムは理想からははるかに遠
いものである。

更に最近、メモリーの固定長から成る各群の構
成要素の比較使用を考慮するような、先入先出演
算方式に代る手段を開発した。該比較使用基準は
それらに対する参照の順序に従つて情報ブロツク
（すなわち、該各群の構成要素）を理想的且つ動
的に配列することを含み、該ブロツクの置換の必
要性が発生したときに、最も長い期間、該参照が
行われなかつたブロツクを置換することにする。
このシステムは、最も最近参照（使用）された情
報ブロツクは最も近い将来もまた参照され易いと
いう、経験から決定した事実を使用している。こ
の基準を受ける置換システムの実施は広く変化の
ある置換、または再配置問題で良い結果を提供す
るということも知られており、この基準の十分且
つ厳密な実施は高価な電子装置を追加することを
も含み、比較的割高な手段であるということも確
かである。

動的再配置に代る手段はロバート・エー・ネル
ソン（Robert A.Nelson）ほかに発行された米国
特許第3541529号のシステムに含まれており、そ
れは使用され、交替されたときに該ブロツクにマ
ークを付し、マークのないブロツクのみを選択し
て置換するというものである。マークされないブ
ロツクの組がなくなつた場合には、すべてのブロ
ツクまたは最後のブロツクのみを残してすべての
ブロツクのマークを消す装置をも使用し、前と同
様に該処理を進める。

他の記憶ページング（Storage Paging）に対
して自主発見をうながす方策はエム・アイ・ダビ
ス（M.I.Davis）がISMテクニカル・デスクロー
ジヤ・ブリテン、（第16巻第１号、1973年６月発
行）に記載した「自動発見的記憶ページング機
構」（Automatic Heuristic Storage Paging
Mechanism）に説明されている。自主発見的ア
ドレス翻訳制御記憶配列はソフトウエアにとつて
平易であるため、仮想記憶動作はソフトウエア経
費の負担を減少させる効果がある。「自主発見
性」（heuristically adaptive）によつて、それは
各与えられた頁が呼出されたときに、置換可能活
動表示がセツトされることを意味するものであ
る。そして、自主発見衰退活動地区がアドレス翻
訳器の中に保持される。

従つて、一般的に先行技術は、(1)大きな費用を
かけて詳細な歴史的情報を保存し厳密な「最近最
少使用」置換方式を使用するか、(2)コンピユータ
時で極く最近呼出されたデータ・ブロツク（すぐ
にまた必要とされ易い）を平均して相当高価なコ
ストで、少くもしばらくの間、元の所に戻すよう
にするかのいずれかのシステムを開示している。

従つて、この発明の目的は最も最近使用された
情報ブロツク、または頁の少くも50％を全体的に
除外して置換し、同時にハードウエアまたはデー
タ処理コストの大幅な増加を避けることである。

この発明によると、大規模低速メモリーから高
速小容量メモリーに頁を置換えるに際し、「最近
最少使用」基準を実施することができる安価なシ
ステムが用意される。関連コストの高い、高速メ
モリーからの各頁、または情報ブロツクの呼出順
序の正確な追跡と維持する代りに、このシステム
は高速メモリーに「頁」のデータに関する簡単な
「Ａ」および「Ｂ」単一バイナリ・デイジツト
（またはビツト）レジスタを使用する。最初に、
各参照された（使用、または呼出された）「頁」
に関係する「Ａ」レジスタに使用表示ビツトが挿
入される。これは「Ａ」レジスタの半数が満され
るまで行なわれる。次に、「Ｂ」レジスタがクリ
ヤされ、各参照された頁に関係する「Ｂ」単一ビ
ツト・レジスタに使用表示ビツトが挿入される。
今、置換するためにある頁が選ばれなければなら
ない場合、「Ａ」および「Ｂ」レジスタが走査さ
れ、「Ａ」または「Ｂ」使用ビツトを持たない頁
が置換のために選ばれる。「Ｂ」レジスタの半数
が満たされた後で、「Ａ」レジスタはクリヤさ
れ、処理が続行される。

このシステムは置換のためにする、高速メモリ
ーの「最近最少使用」頁の厳密な選択による大部
分の利益を保証する利点を持つにも拘らず、ラン
ダム選択システムに使用されている論理回路より
も極くわずか論理回路を追加する必要があるのみ
である。特に、このシステムは、置換するために
選ばれる「頁」または情報ブロツクは最も最近使
用された頁の合計の50％からは選ばれないことを
保証するものであり、平均では高速メモリーの25
％の最近最少使用の頁から選ばれることを保証す
るものである。

より一般的な基礎に立ち、この発明は小型高速
メモリーと大規模低速メモリーとを持つ演算シス
テムを含み、少くも高速メモリーの情報の「頁」
またはブロツクの各部分については、レジスタ装
置および関連論理回路と組合わせによつて、最も
最近呼出された高速メモリーの頁の少くも50％の
中からは置換のための頁を選ばないようにし、置
換する頁は、所定の切換時点に続く時間に呼出し
がなかつたということを基準にして、残りの50％
またはそれ以下の％の中から選ぶようにしたシス
テムである。

次にこの発明の実施例を添付図面とともに詳細
に説明する。

第１図は演算システム１２と、該演算システム
１２と情報を交換する高速またはバツフア・メモ
リー、または記憶装置１４とを含むデータ処理装
置を表わす。大型またはバツク・アツプ・メモリ
ー、または記憶装置１６は該高速メモリー１４に
記憶できない程多くのデジタル情報を記憶する容
量を有する。該演算システム１２で処理される各
問題に対する情報は大型バツク・アツプ・メモリ
ー１６から高速メモリー１４へ転送される。多く
の場合、メモリー１６からの情報のあるブロツク
は演算システム１２で屡々使用されるから高速メ
モリー１４に保持される。かゝる情報の「頁」ま
たはデイジタル情報ブロツクは低速メモリー１６
から高速メモリー１４に、普通、ユニツトとして
転送される。

導入において説明したように、該演算システム
１２に最近呼出された「頁」、またはデイジタル
情報のブロツクは近い将来再び呼出されることが
多いということが確認される。従つて、転送回路
１８および連想メモリー２４はデータ処理システ
ム１２に必要な情報を提供するために、新たな情
報を高速メモリー１４に追加挿入しなければなら
ない場合、高速メモリー１４から最近使用されな
かつた情報のブロツクを選択する論理回路を含む
ものである。

ついでながら、この発明は主に転送回路１８と
連想メモリー２４に関するものである。第１図に
表わされているような全システムは異なる型の転
送回路を持ち、エヌ・シー・アール・コーポレー
シヨン（NCR Corporation）（オハイオ州デイト
ン市）から入手可能な商品名クライテリオン
（CRITERION）8550，8570として販売されてい
るデータ処理システムに含まれている。

転送回路１８、連想メモリー２４の動作態様の
詳細は第２図の概念図、第３図の論理流れ図、第
４図の詳細な論理回路図に従つて考察される。

第２図を見ると、連想メモリーはブロツク２４
で表わされ、第１図の高速メモリー１４の１６情
報アドレスまたはブロツクに対しては空白で表わ
されている。該連想メモリー２４の各１６位置に
は、高速メモリーの各部に記憶されている情報が
引出された大型メモリー１６の元のアドレスが含
まれている。連想メモリー２４に照会された各情
報ブロツクはＡ単一ビツト・レジスタ２６とＢ単
一ビツト・レジスタ２８とに接続される。Ａおよ
びＢ単一ビツト・レジスタ２６，２８は「使用」
レジスタであり、高速メモリーの情報ブロツク
（勿論、連想メモリー２４の各空白０〜15に接続
されたアドレスに対応する）に対して、コンピユ
ータまたはデータ処理装置１２による照会の追跡
を維持することに使用される。

動作に際しては、使用レジスタ２６，２８は連
続的に可能化される「Ａ」レジスタと「Ｂ」レジ
スタ２８とに分けられる。特に、スイツチ３０が
２つの列Ａ，Ｂのうちの１つを選ぶ場合、高速メ
モリーの特定の場所の照会が行なわれたことを表
わすために、各対応する単一ビツト・レジスタに
使用ビツトが挿入される。

第２図で、スイツチ３０は「Ｂ」列のレジスタ
２８の方に向けられているように表わされてい
る。この場合には16単一ビツトの「Ａ」レジスタ
２６の８ビツトに使用ビツトが負荷されていると
いうことに注意すべきである。「Ｂ」使用レジス
タ２８については３ビツトのみが負荷されてお
り、それらは０，３，４と指定されたレジスタで
ある。今、コンピユータ１２が高速メモリー１４
の情報ブロツク１０からある情報を選んで場合、
第２図の列２８の「Ｂ」レジスタの「０」は
「１」とマークされる。

今、データ処理システム１２が高速メモリー１
４には含まれておらず、大型メモリー１６にのみ
記憶されている情報を要求した場合は、該情報ブ
ロツクを高速メモリー１４に転送する必要があ
る。該高速メモリーの１６情報ブロツクが要求さ
れた新しい情報を挿入する空番地を作るために取
除かなければならない場合に問題が発生する。こ
の問題を解決するために、連想メモリー２４の空
地０〜１５に接続されている使用レジスタ２６，
２８はＡ−Ｂビツト対が０−０であるかどうかを
テストされ、またはチエツクされる。選択論理回
路は第５番目のレジスタのようにＡ−Ｂの２ビツ
トの使用レジスタが両者とも使用ビツトを持たな
い場合、第２図の３６で指定された16ラインのう
ちの第５入力ライン（第５レジスタ）を介してエ
ンコーダ３４に信号が供給されるというように配
置されている。同様にして、Ａ−Ｂの２ビツトの
０−０が含まれている使用レジスタ第９，第10，
第11，第13，第15に接続されている入力ライン３
６を介して該エンコーダ３４に信号が送られる。
エンコーダ３４は導体３８に、大型メモリー１６
からのデータが挿入されるべき高速メモリー１４
の部分を識別する４ビツト・アドレス信号を提供
する。エンコーダ３４は上に列挙された最近最少
照合（使用、呼出）レジスタの最小番号（この場
合は第５レジスタ）を任意に選出する（これら最
近最少照会レジスターのいずれに対しても等しく
有効な選択であるが）。加うるに、連想メモリー
２４の第５位置（第５レジスタ）に対応する入力
が行なわれ、使用ビツトは該連想メモリーのテー
ブル位置５に対応する列２８の「Ｂ」レジスタに
挿入される。

前述したように、第２図の列２８には３個の使
用ビツトのみが表わされており、更に「Ｂ」レジ
スタに対する第４番目の使用ビツトが第５レジス
タに追加されたことを説明した。該高速メモリー
１４の更に追加する４個のブロツクから情報の呼
出があつた後は、８個のビツトが「Ｂ」レジスタ
にセツトされたことになり、そこで回路４６を付
勢するために、回路４２から導体４４を介して該
回路４６に信号が供給される。すると、トグル・
スイツチ３０は列「Ｂ」から列「Ａ」に、または
その逆に切換えられ、矢印４８，５０で示されて
いるリセツト信号を起動して該トグル・スイツチ
が切換えられた列に接続されている16レジスタを
リセツトする。従つて、列２６の１６「Ａ」使用
レジスタにある使用ビツトのすべては、該回路４
６が付勢されたときに「０」にリセツトされる。

前述したこのサイクルはその後、「Ａ」レジス
タに８ビツトが入力されるまで使用ビツトの挿入
が繰返えされ、次いで回路４２が８ビツト挿入状
態を検出して回路４６を付勢し、再び「Ｂ」列に
切換えられる。

以上第２図で述べた動作態様は第３図のプログ
ラム形式で表わされる。「開始」に続くブロツク
６２で示された第１の工程はコンピユータの命令
ですべての表示ビツトをクリヤし、列Ｂを選択す
る工程である。開始に続き、データ処理システム
１２によるデータ要求を受信すると、６角形６４
における第１の質問は「デーブルに要求するアド
レスがあるか」である。この質問に対する答が
「ノー」であれば、新たなデータ挿入を該テーブ
ルに設けなければならないことを意味する。これ
はたゞ単に要求された情報ブロツクを大型低速メ
モリー１６から高速メモリー１４の空位置に移動
する割込サービス・ルーチンによつて達成され
る。

ブロツク８２，８４はテーブルの加入が行なわ
れなければならない場合の情況に関するものであ
る。ブロツク８２は高速メモリーの最近最少使用
情報ブロツクの１つであることを表わすＡ−Ｂレ
ジスタに「00」を持つ最初の使用レジスタを選択
することを表わしている。ブロツク８４は大形メ
モリーから高速メモリーの選択場所に情報を転送
する工程を表わす。

６４で表わされたシーケンスの部分に戻り、そ
こで「イエス」の答は要求データが高速メモリー
にあることを表わす。ブロツク６８は使用する情
報ブロツクに対して、スイツチ３０が接続されて
いるＡまたはＢのいずれかに対する適当な単一ビ
ツト・レジスタに使用ビツトをセツトする、また
は挿入する工程を表わす。次の６角形７０におけ
る質問は「選ばれている列は８ビツトになつた
か」である。その作用は答「イエス」の場合、第
２図の回路４２，４４，４６，４８，５０で実行
された。そして、これら切換およびリセツト工程
はシーケンスの図のブロツク７２，７４に挙げら
れている。ライン７６，７８，８０はデータ処理
システム１２によつて更に追加するメモリー・ア
ドレスが呼出される場合に、ブロツク６４に復帰
することを表わす。

特に第１図、第２図、第３図、およびその説明
に関して注意しなければならないことは高速メモ
リーの各データ・ブロツクは連想メモリー２４お
よび使用レジスタ２６，２８のブロツク、または
位置と連結されたものとみなされたことである。
しかし、実際の運用では高速メモリーは該連想メ
モリーおよび使用レジスタより多いブロツクを有
することができる。そのような場合、別のソフト
ウエアで維持されるテーブルが該高速メモリーの
すべてのデータ・アドレスのブロツクを含むよう
にされる。もし、呼出されたデータが連想メモリ
ー２４のブロツクの１つで表わさない場合は、大
形メモリー１４からデータを引出す前に、該高速
メモリーと結びつける別のテーブルがまずチエツ
クされ、要求するデータがある場合は、大形メモ
リーからのデータ呼出について前述したと同様な
方法で、そのデータ・アドレスが連想メモリー２
４に負荷される。

次に、第４Ａ図、第４Ｂ図の詳細なロジツク回
路図について説明する。最初に、この回路はエミ
ツタ結合ロジツクまたはECLの形式で表わされ
ているということは注意すべきである。これらの
配列で、各能動回路は抵抗に給電されなければな
らない。従つて、該回路図の各所に表わされてい
る小さいブロツクはECL回路に常用される前述
の抵抗を構成するものである。ちなみに、ECL
型回路の良い参考文献はMotorola Emitter
Coupled Logicの頭文字MECLで指定されるモト
ロラ（Motorola）社の刊行物に見ることができ
る。該論理回路のほとんどの能動回路はここに表
わされているようにインバータであり、それは従
来からあるように、「アンド」および「オア」回
路の先に小さい円を描いて表わされている。ある
場合には該小円がなく、それは反転しない場合で
ある。また、左側を囲む縦線を持つ能動回路は
「アンド」ゲートであり、また反転がある場合は
「ナンド」ゲートである。同様に左側が凹曲線で
囲まれている場合は「オア」回路である。

エミツタ結合ロジツクでは、論理「１」を「ロ
ー」電圧状態で表わし、論理「０」を「ハイ」電
圧状態で表わすのが慣用であり、このロジツクも
該慣用手段に従う。ここで特に注意すべきこと
は、第４Ａ図、第４Ｂ図の論理回路の多くの入力
は通常「ロー」（論理１）であり、論理０（ハ
イ）状態に切換えられることによつて能動となる
ということである。入力端におけるこれら入力は
線またはバーで表わされている。故に、「CLK」
入力は論理１または立下り（ロー）クロツク・パ
ルスを表わし、「」は論理０または立上り
（ハイ）クロツク・パルスを表わす。同様にし
て、「^TRANSLATE」入力は通常ローまたは論理１で
あり、翻訳動作が作作動されるときに論理０また
は（ハイ）に切換えられる。

更に、図に描かれている文字NCはいずれの信
号源にも接続されていない導体であるということ
を表わしている。信号または命令の後に、図に現
わされている数「＋１」を持つ信号または命令は
そのような数を持たずに表わされている命令の次
の最初のクロツク・サイクル中に発生するもので
あるということを表示する。

第４Ａ図，第４Ｂ図の論理回路において、ブロ
ツク２６′，２６″は「Ａ」単一ビツト・レジスタ
を構成し、ブロツク２８′，２８″は「Ｂ」単一ビ
ツト使用レジスタを表わす。これら４チツプはシ
グネテイツクス（Signetics）社から入手できる
部品番号10155である。

連想メモリー２４に記憶されているアドレスを
持つ情報ブロツクの１つに対して行なわれた照合
が成功すると（この動作は「翻訳成功」として知
られている）、導体Ｃ０〜Ｃ１５の１つはAM
（連想メモリー）加入比較回路によつて付勢され
る。ＡレジスタまたはＢレジスタのいずれかに選
択的に行なわれる使用ビツトの加入は第４Ａ図の
下部にあるフリツプ・フロツプ９２で制御され
る。それは下記されるように、Ａレジスタまたは
Ｂレジスタいずれかの端子を可能化する。該フ
リツプ・フロツプの出力はPTR，^PTRで表わされ
る。第４Ｂ図の右側にあり、Ａレジスタ２６′，
２６″およびＢレジスタ２８′，２８″に対するそ
れぞれの入力である「クロツクＡ」および「クロ
ツクＢ」信号の発生は、それぞれクロツク信号
と、フリツプ・フロツプ９２の相互に排他的な出
力であるPTRまたはのいずれかと、ナンド
回路９９からの第３の入力との３つの入力を持つ
アンド・ゲート９４，９６によつて達成される。
該ナンド回路９９は「バー」または反転信号とと
もに、その１入力である12を入力す
る。従つて、ナンド回路９９は該ナンド回路９９
の入力の１つがクロツクＡ（CLKA）またはクロ
ツクＢ（CLKB）信号の発生を可能化するよう論
理０に移動されると、アンド回路９４，９６に対
して論理１出力（エネーブル・クロツク）を提供
する。これらの信号は（CLKA，CLKB）それぞ
れＡレジスタ２６′，２６″およびＢレジスタ２
８′，２８″の（書込）入力に供給される。

該レジスタ２６′（４つの類似回路の１つ）に
対する他の２つの入力は該チツプの「Io」端子へ
の「SET RR」入力であり、「Ao」端子に対する
「Ｒ／ＷモードＡ」入力である。Io端子への入力
は該レジスタのセツト状態を確認し、該レジスタ
の最近照会（SET RR）単一ビツトをセツトす
るか、無効命令を実行したときまたはリセツト1/
２（RERET1/2）を実行したときにすべてのビツ
トを論理０状態にクリヤすることに使用される。
第４Ｂ図の右側にあるナンド・ゲート９９は
SUCCESSFUL TRANSLATION，CREATE
NEW ENTRYおよびREAD＆SET RR＋１等の
各制御入力とともに「SET RR」入力を持つと
いうことに注意すべきである。更に、「Ｒ／Ｗ
modeA」「Ｒ／Ｗ modeB」の各入力は該論理回
路の右側にあるオア・ゲート９５，９７から発生
される。

混乱を避けるために注意しなければならないの
は、各４使用レジスタ・チツプ２６′，２６″，２
８′，２８″は「Ｒ／Ｗ modeA」または「Ｒ／
Ｗ modeB」信号が供給される「Ao」入力を持
つということであり、特に注意すべきことは、各
Ｂ使用レジスタが「Ao」端子を持つということ
である。従つて、高速メモリーのブロツク４に情
報の照会が行なわれた場合ラインＣ４は付勢さ
れ、フリツプ・フロツプ９２の状態に応じて２
６′または２８′のいずれかのレジスタＹ４は論理
１状態切換えられる。勿論、フリツプ・フロツプ
９２は第２図に表わされているスイツチ３０の作
用に適応するものである。

第２図とともに前述したように、スイツチ３０
が列２６か列２８のいずれかを選び、使用レジス
タの1/2または８個が「１」状態にセツトされた
場合、該スイツチは他方のレジスタ列に切換えら
れ、この第２のレジスタ列はクリヤされる。この
対応する作用は２つのプログラマブル読出専用メ
モリーまたは「PROM」９８，１００と、アダー
１０２とによつて第４Ａ図，第４Ｂ図の論理回路
で達成される。SUCCESSFUL TRANSLATION
CREATE NEW ENTRYまたはREAD＆SET
RR命令直後のクロツク期間中、すべての「Ａ」
または「Ｂ」レジスタ（フリツプ・フロツプ９２
の状態によつて異なる）からのＹ出力（Ｃ０〜Ｃ
１５）はPROM ９８，１００に読取られ、該
RPOMは使用レジスタ２６′，２６″から読出され
たビツトの数を表わすバイナリ数出力をアダー１
０２に供給する。故に、特定の例として、レジス
タ２６′のＹ０，Ｙ１，Ｙ２がマークされている
ものと仮定すれば、PROM ９８への上部３導体
が付勢されることになる（論理１となる）。この
状態のもとではPROM ９８からの出力は10進数
３を表わすバイナリ数である0011である。更に、
レジスタ２６″の５つのレジスタ位置Ｙ２〜Ｙ６
に使用ビツトが含まれているものと仮定すると、
PROM 100に対する入力における導体Ｃ１０〜Ｃ
１４は付勢され、出力は10進数５に対応するバイ
ナリ数0101となるであろう。該アダー１０２は
PROM ９８からのバイナリ数0011と、PROM１
００からの0101とを総和して10進数８に対応する
バイナリ数1000を得る。アダー１０２からの導体
１０４の出力は能動化され（論理２）てアンド・
ゲート１０６に供給される。フリツプ・フロツプ
１５０から導体１０８を介してフリツプ・フロツ
プ９２の入力へ適当なタイミング信号が到達する
と、該フリツプ・フロツプ９２は付勢されてその
状態が反転される。従つて、使用レジスタ２
６′，２６″の組の１つから他方の使用レジスタ２
８′，２８″の組へ切換が行なわれる。

ノア・ゲート１５４は論理０クロツク・パルス
であるを発生する。該パルスはＡまた
はＢレジスタをクロツクする。この信号はフリツ
プ・フロツプ１５０をリセツトし、次いで最近照
会されたビツトがＡまたはＢレジスタにセツトさ
れた後の１クロツク・サイクルまでフリツプ・フ
ロツプ９２，１１６の反転を遅らせる。

フリツプ・フロツプ９２が切換えられた後の最
初のサイクル期間中、新しく選ばれた使用レジス
タのレジスタ群は（この実施例では「Ｂ」レジス
タ２８′，２８″）すべての入力「Ｙ」ラインを
「ロ−」または論理１状態に反転することによつ
て「０」にリセツトされ、それぞれ回路２８′２
８″のＲ／Ｗ導体１１２，１１４に書込パルスを
供給する。同時点で、Ｂレジスタタ２８′，２
８″のＩ。端子へのSET RR入力は論理０かハイ
状態である。すなわち、該チツプ２６′，２６″，
２８′，２８″のＩ。端子は選ばれたレジスタがセ
ツトされるようにするため、その状態を制御する
ものである。入力「Ｙ」導体はフリツプ・フロツ
プ１１６の動作によりすべてローに反転される。
該フリツプ・フロツプ１１６は12信号
をアンド・ゲート１１７の入力の１つに出力す
る。該12出力は、フリツプ・フロツプ
９２がその出力PTRととの間で切換えられ
る度ごとに１クロツク・サイクルの間、論理０に
セツトされる。「INHDEC」と称するアンド・ゲ
ート１１７の出力はナンド回路１１９，１２１の
入力に論理０状態を供給し、該全ナンド回路１１
９，１２１からの出力を論理１（または「ロ
ー」）状態にする。それによつて、回路２８′，２
８″のＢレジスタのすべては論理０状態にセツト
できるように可能化される。

今、データ処理システム１２（第１図）が高速
メモリー１４にない番号を要求した場合、最近最
少使用の情報ブロツクを選ばなければならない。
従つて、ＡビツトおよびＢビツトがともに「０」
に等しい最下位番号の１対のレジスタを識別しな
ければならない。この作用を完成するために、入
力導体１１８，１２０に０を挿入し、回路２
６′，２８′，２６″，２８″すべては、該全４チツ
プの「Ao」端子すべての入力１１２，１１４，
１２２，１２４をハイまたは論理０状態にセツト
することにより「アソシエイト」（associate）モ
ードにセツトされる。Ａレジスタ・チツプ２
６′，２６″またはＢレジスタ２８′，２８″への論
理０加入を伴なういかなる入力も、両レジスタ間
を接続し、各対応するＹラインを「ロー」状態に
する。エンコーダ１２６，１２８は入力ラインを
感知して、ＡおよびＢレジスタともに「０」であ
る最下位番号のラインを確認する。該エンコーダ
１２６，１２８の出力はマルチプレクサ回路１３
０で組合わされ、その結果該回路１３０からの４
デイジツト・コード出力は新たな加入が負荷され
るべき連想メモリーの位置を識別することに使用
される。該エンコーダ１２６，１２８の入力にお
けるナンド・ゲート１５２は該エンコーダへの条
件付けをする適当な信号を提供することに必要と
される。

２つのデコーダ１３２，１３４（他の回路と同
様に）は回路１３０からの符号化出力を受信す
る。この情報はＡまたはＢレジスタ（フリツプ・
フロツプ９２の状態により異なる）のいずれかに
対する適切な入力Ｙ導体を識別することに使用さ
れ、使用ビツトを適切な単一ビツト・レジスタに
挿入することにも用いられる。デコーダ１３２，
１３４はラインＣ０〜Ｃ１５の選ばれた１つに結
合されているナンド・ゲートを除き、すべてのナ
ンド・ゲート１１９，１２１に論理１信号を供給
する。アンド・ゲート１１７からの論理１ととも
に、選ばれたナンド・ゲートのみが０および１両
入力を持つことになり、選ばれたラインのみが論
理１を受信し、チツプ２６′，２６″，２８′また
は２８″の適切なレジスタに使用ビツトを挿入す
るようにローに「ドライブ」される。

入力は該システムがターン・オ
ンされ、イニシアライズ（初期設定）されたとき
に、レジスタの半分をリセツトすることに使用さ
れる。これは前述の12動作とほぼ同様
な方法で達成される。そして、12入力
とともに、アンド・ゲート１１７およびナンド・
ゲート９９への入力の挿入は特に
注目すべきものである。

ＡおよびＢ使用レジスタ２６′，２６″，２
８′，２８″の端子Ioに供給されたSET RR信号を
出力するナンド・ゲート９３の関係は注目すべき
である。前述したように、Io端子は他の導体が可
能化されたときに個々のレジスタがセツトされる
ように状態の制御を行なう。２つの直接入力(1)
CREATE NEW ENTRY（新加入の創性）、(2)
SUCCESSFUF TRANSLATION（翻訳成功）
とともに、それらの機能が発生したときに、
SET RR信号は論理１となる。リセツト状態に
対してはSET RRは論理０となるだろう。

翻訳成功前の翻訳期間中はクロツクＡ、クロツ
クＢまたはSET RR信号のいずれもが可能化さ
れておらず、従つて、ＡまたはＢレジスタ２
６′，２６″，２８′，２８″の加入、変化は起るこ
とができない。ちなみに、翻訳がみられている翻
訳期間は後に発生する前述した「SUCCESSFUL
TRANSLATION」に対する比較から
「TRANSLATE」または「TRANSLATE」入力
とマークされる。該「TRANSLATE」状態はナ
ンド・ゲート１１９，１２１の出力を論理１に
し、そのためデコーダ１３２，１３４は該アドレ
ス翻訳が試みられている間中Ｃ０〜Ｃ１５ライン
をバイアスしない。

ＡおよびＢレジスタとして使用される２６′，
２６″，２８′，２８″前述のシグネテイツクス・
パーツ番号10155に加え、更に半導体チツプの部
品番号を追加して使用部品を完全にする。特に、
エンコーダ・チツプはシグネイツクス部品番号
10162、マルチプレクサ１３０はシグネテイツク
ス部品番号10173、アダー１０２はシグネテイツ
クス部品番号10181である。

以上この発明の実施例を説明した。勿論、該
種々の論理要素に供給される信号の実際のタイミ
ングは前述したNCR Criterionのような使用する
全体の演算またはデータ処理システムと一致しな
ければならない。タイミングおよびそれと同様な
事柄は、勿論、データ処理技術における当業者間
では周知なことである。この論理回路の実施の精
密な態様はこの発明にとつては本質的なことでは
ないが、異なる種類の論理要素およびナンド・ゲ
ート、オア・ゲート、フリツプ・フロツプ、およ
び同等の作用を実行する論理回路のシステムを使
用する他の類似する論理システムによつて実施す
ることができるということは容易に理解されるも
のである。限定ではなく例として、２または３バ
イナリ・デイジツト長のシフト・レジスタを各頁
の高速メモリーと接続される各１対のＡおよびＢ
使用レジスタの場所に使用することができ、入力
レジスタが部分的に満たされた場合に、シフトが
生じるようにすることができる。同様なロジツク
の交換は該回路の他の場所でも行なうことができ
る。

以上説明したところから、この発明は所期の目
的を達成することができることが明らかとなつ
た。

【図面の簡単な説明】

第１図はこの発明が使用されるシステムを表わ
す全体的ブロツク線図、第２図はこの発明を実施
するシステムの概略ブロツク線図、第３図は第２
図のシステムの動作順次を表わす論理流れ図、第
４図はこの発明の実施例を表わす概略論理線図で
ある。１２…演算システム、１４…高速メモリー、１
６…大容量メモリー、１８…転送回路、２４…連
想メモリー、２６，２８…単一ビツト・レジス
タ、３０…スイツチ、３４…エンコーダ、４２，
４６…回路、２６′，２６″，２８′，２８″…単一
ビツト・レジスタ、９２，１１６，１５０…フリ
ツプ・フロツプ、９８，１００…PROM、９５，
９７…オア・ゲート、９４，９６…アンド・ゲー
ト、９３…ナンド・ゲート、１５４…ノア・ゲー
ト、１３２，１３４…デコーダ、１２６，１２８
…エンコーダ、１０２…アダー、１３０…マルチ
プレクサ。

Claims

【特許請求の範囲】１複数のアドレス位置を持ち、デイジタル情報
の「頁」またはブロツクを記憶する限定された容
量の高速メモリーと、低速大容量メモリーと、前記高速メモリーからの情報を受信するように
接続された高速データ処理装置と、前記高速メモリーのデイジタル情報の各頁と結
合する「Ａ」単一ビツト・レジスタと「Ｂ」単一
ビツト・レジスタとを提供する手段と、情報が連想された頁から呼出されたときに、各
「Ａ」レジスタに使用ビツトを挿入する手段と、前記「Ａ」レジスタの約50％に使用ビツトが挿
入されたことを検知して前記「Ｂ」レジスタをク
リヤし、その後は前記「Ｂ」レジスタに使用ビツ
トを挿入する手段と、前記「Ｂ」レジスタの約50％が満たされたこと
を感知して再び前記「Ａ」レジスタに切換え、該
「Ａ」レジスタをクリヤして後、該「Ａ」レジス
タに使用ビツトを挿入する手段と、前記「Ａ」レジスタと「Ｂ」レジスタに特定頁
に関連する使用ビツトがないことを検出すること
により、前記高速メモリーの置換用頁位置を選択
する手段と、前記高速メモリーの前記選ばれた頁の１つと前
記低速メモリーとの間で情報を交換する手段とか
ら成ることを特徴とするデータ置換処理システ
ム。２前記高速メモリーの位置と前記大容量メモリ
ーの対応するアドレスとを関連付けるための連想
メモリーが設けられ、前記「Ａ」および「Ｂ」レ
ジスタは前記連想メモリーの各アドレスと連結さ
れていることを特徴とする特許請求の範囲第１項
記載のデータ置換処理システム。３デイジタル・データ処理ユニツトと、限定された数の情報ブロツクを記憶し得る記憶
容量を持ち、前記デイジタル・データ処理ユニツ
トに直接使用するための高速低容量デイジタル・
メモリーと、低呼出速度の大容量デイジタル・メモリーと、前記大容量メモリーから前記高速メモリーの特
定の位置にデータを転送する手段と、前記大容量デイジタル・メモリーからの新デー
タを受信するための前記高速低容量デイジタル・
メモリー内の記憶ブロツクを、最近使用時の古い
方から50％のブロツク群の中から選択する論理回
路手段であつて、前記50％のブロツク群からの最
初の選択については前記ブロツク群内のデータの
それ以前の使用状況とは無関係に行なう論理回路
手段とから成るデイジタル処理システム。４呼出しが行なわれた前記高速メモリーのデー
タ・ブロツクに対応する使用マーカー・ビツト
を、合計ブロツク数の約50％がマークされるまで
記憶する手段と、その後、呼出の古い方から50％にあたる前記デ
ータ・ブロツクと関連する使用マーカー・ビツト
をクリヤする手段とを含むことを特徴とする特許
請求の範囲第３項記載のデイジタル処理システ
ム。５第１および第２の単一ビツト使用レジスタが
前記高速メモリーの各ブロツク記憶位置と連繋さ
れることを特徴とする特許請求の範囲第３項記載
のデイジタル処理システム。６前記ブロツクの記憶位置と連繋する前記第１
および第２の単一ビツト・レジスタのいずれかに
使用ビツトを挿入する手段を含むことを特徴とす
る特許請求の範囲第５項記載のデイジタル処理シ
ステム。７前記第１のすべてかまたは前記第２のすべて
の単一ビツト・レジスタのいずれかをクリヤする
手段を含むことを特徴とする特許請求の範囲第５
項記載のデイジタル処理システム。８前記第１および第２の使用ビツト・レジスタ
両者から使用ビツトを読取る手段と、前記連繋す
る使用レジスタ内に使用ビツトを持たない記憶位
置ブロツクを選択する手段とを含むことを特徴と
する特許請求の範囲第５項記載のデイジタル処理
システム。９デイジタル・データ処理ユニツトと、限定された数の情報ブロツクを記憶する記憶容
量を持ち、前記デイジタル・データ処理ユニツト
に直接使用するための高速低容量デイジタル・メ
モリーと、低呼出速度の大容量デイジタル・メモリーと、前記大容量メモリーから前記高速メモリーの特
定の位置にデータを転送する手段と、前記大容量メモリーからの新データを受信する
ための前記高速メモリー内の記憶ブロツクを、前
記高速メモリー内の最近使用時の古いブロツク群
の一部のグループの中から選択する論理回路手段
であつて、前記最近使用時の古い一部のブロツク
群からの最初の選択については前記ブロツク群内
のデータのそれ以前の使用状況とは無関係に行な
う論理回路手段とから成るデイジタル処理システ
ム。１０前記論理回路手段は、前記高速メモリーの各ブロツクと連繋し、該連
繋されたブロツクに対する最近の呼出しを表わす
第１の組の使用ビツトと、該連繋されたブロツク
に対する古い呼出しを表わす第２の組の使用ビツ
トとのそれぞれに少くとも１使用ビツトの記憶可
能な手段と、前記第１の組の最近使用ビツトを保持する間、
前記第２の組の古い使用ビツトのすべてをクリヤ
する手段とを含むことを特徴とする特許請求の範
囲第９項記載のデイジタル処理システム。