JPH04233641A - データプレフェッチの方法およびその装置 - Google Patents

データプレフェッチの方法およびその装置

Info

Publication number
JPH04233641A
JPH04233641A JP3216621A JP21662191A JPH04233641A JP H04233641 A JPH04233641 A JP H04233641A JP 3216621 A JP3216621 A JP 3216621A JP 21662191 A JP21662191 A JP 21662191A JP H04233641 A JPH04233641 A JP H04233641A
Authority
JP
Japan
Prior art keywords
memory
cache
data
bus
address
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP3216621A
Other languages
English (en)
Other versions
JP3323212B2 (ja
Inventor
Pirmin L Weisser
ピルミン　エル．　ヴァイサ
Fulps V Vermeer
フールプス　ヴィ．　ヴァーミア
Edward C King
エドワード　シー．　キング
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NCR Voyix Corp
Original Assignee
NCR Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NCR Corp filed Critical NCR Corp
Publication of JPH04233641A publication Critical patent/JPH04233641A/ja
Application granted granted Critical
Publication of JP3323212B2 publication Critical patent/JP3323212B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3802—Instruction prefetching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0862—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with prefetch
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/60—Details of cache memory
    • G06F2212/6022—Using a prefetch buffer or dedicated prefetch cache

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Bus Control (AREA)

Abstract

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

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はコンピューターメモリシ
ステムに関し、特にコンピューターメモリシステムから
のデータのプレフェッチを行なうための方法と装置に関
する。
【０００２】
【従来の技術】コンピュータの性能はメモリの階層を使
用することによって強化できる。例えば、三段のメモリ
は低速、中速、および高速メモリで構成できる。低速メ
モリは廉価で多量のデータ格納のための磁気ディスクで
よい。中速メモリはコンピュータの主メモリとして使用
するＤＲＡＭで構成できる。高速メモリはプロセッサキ
ャッシュメモリとして使用できるＳＲＡＭが使用できる
。メモリの階層を利用するのは、最高速メモリ内でシス
テムプロセッサにより実行されるコード（命令）および
他のデータをグループ化するためである。そのような高
速メモリは通例、入手できる最も高価なメモリが使用さ
れるので、経済性を考慮して比較的小さい。ＤＲＡＭか
ら構成される主メモリは、ＳＲＡＭを用いたキャッシュ
メモリよりもより高密度かつより廉価であり、従ってキ
ャッシュメモリよりも著しく大きい。
【０００３】作動期間中、システムプロセッサが現に実
行中の変数に迅速にアクセスできるようにするため、命
令その他のデータはシステムメモリからキャッシュメモ
リに転送される。キャッシュにない追加的データが必要
とされるときは、そのデータをメモリから転送し、これ
でキャッシュ内の選択したデータを置換する。いずれの
データを置換するかを決定するにはいろいろのアルゴリ
ズムが使用される。
【０００４】定義により、高効率動作キャッシュのアー
キテクチャーは高い「ヒット（当たり）」率持つもので
ある。「ヒット」はキャッシュ内に要求されたデータが
あるときに起こる。ヒット率には多数の要因が影響する
。主な因子は実行されるコードの引合いの局所性である
。言い換えると、もしも当該コードがメモリ内で近接し
た物理的ロケーションにあると、メモリ内に広く当該コ
ードが分散しているときよりヒット率は高くなる。キャ
ッシュのヒット率に影響するもう一つの因子はそのメモ
リにアクセスするデバイスの数である。もしも唯一つの
バス主、例えばシステムプロセッサ、がメモリにアクセ
スするのであれば、ヒット率がかなり高くなるようにキ
ャッシュに格納されるデータを制御できる。しかしなが
ら、同一のキャッシュを通して当該メモリに一つ以上の
バス主がアクセスするときは、キャッシュはこれらバス
主からの要求の間を何度も往復することがありうる。 その結果ヒット率は大きく低下する。換言すると、キャ
ッシュは非差別的なものであって、システムプロセッサ
および他のバス主の要求がキャッシュに等しく影響する
。一つのオペレーションがキャッシュのデータ編成に著
しく影響を与えることがありうる。例えば、非ホストＣ
ＰＵバス主からのメモリアクセス要求に応答してキャッ
シュに入れられたデータはホストプロセッサが必要とす
るデータを上書きしてしまう。
【０００５】ヒット率に影響するもう一つの因子はコー
ドデータおよび非コードデータの両方がキャッシュ化さ
れるという事情に関係する。システムメモリ内のデータ
ブロックはキャッシュ内でいろいろの物理的ロケーショ
ンに転写（ｍａｐｐｉｎｎｇ）される。もしもシステム
メモリ内の各データブロックが単一のロケーションに転
写されるのであれば、キャッシュは直接転写キャッシュ
（ｄｉｒｅｃｔ　ｍａｐｐｅｄ　ｃａｃｈｅ）と言われ
る。これに対してセット関連転写キャッシュと呼ばれる
ものは各データブロックが複数のロケーションに転写さ
れるものである。例えば、もしも各データブロックが二
つのロケーションのいずれかに転写されるとき、これは
二通り−セット関連転写（ｔｗｏ−ｗａｙ　ｓｅｔ　ａ
ｓｓｏｃｉａｔｉｖｅ　ｍａｐｐｉｎｇ）と呼ばれてい
る。システムメモリブロックが利用できるロケーション
の数に関係なく、コードデータおよび非コードデータの
両方がキャッシュ化されるときはそれぞれの転写が重複
することになる。従って、コードデータおよび非コード
データの両方がキャッシュ化されるときは、メモリへの
アクセスに応答してデータが置換されるにともない著し
いスラッシング（ｔｈｒａｓｈｉｎｇ、データ処理の低
下）が起こりえる。
【０００６】ヒット率に影響を及ぼしてシステム性能を
改善できる技術の一つはプレフェッチキューを使用する
ことである。プレフェッチキューとは、プレフェッチア
ルゴリズムに基づいて選択される高速メモリ内のデータ
エレメントの集合である。例えば、システムプロセッサ
が使用することを予測してシステムメモリからコードデ
ータエレメントをプレフェッチ（予めの取り寄せ）を行
なうことができる。従来、このようなプレフェッチキュ
ーはシステムプロセッサに密接に関連していた。複数の
バス主を有するシステムにおいてはシステムプロセッサ
からデータを求めるためのプレフェッチ要求は他のバス
主とメモリアクセスに関して競争することが必要であっ
た。もしもそのプレフェッチ要求が優先されると他のメ
モリ要求は遅延されることになる。これは他のバス主に
待機状態を強いることから、システムの性能に幾分かの
影響を及ぼす。さらに、このプレフェッチ要求は単なる
予測であるので、プレフェッチデータの一部またはほと
んどがプロセッサにより使用されないことがある。その
ようなデータエレメントの不使用が他のバス主のメモリ
アクセス要求を遅延させることにより、さらにシステム
性能が劣化する。
【０００７】
【発明が解決しようとする課題】従って本発明はシステ
ムメモリからのデータのプレフェッチを行なうための新
規かつ改良された方法を与えることを課題とする。
【０００８】本発明のもう一つの課題はメモリシステム
の応答時間を改善する方法を与えることである。
【０００９】本発明のさらに別の課題はコンピューター
システムの性能を改善する方法を与えることである。
【００１０】本発明のさらに別の課題は新規かつ改良さ
れたメモリシステムを与えることである。
【００１１】本発明のさらに別の課題は一層効率的なプ
レフェッチキューを与えることである。
【００１２】本発明のさらに別の課題はコンピューター
メモリシステム内のコードデータをアクセスするための
方法とシステムを与えることである。
【００１３】
【課題を解決するための手段】本発明はメモリシステム
におけるデータエレメント管理方法を与える。このメモ
リシステムはバスで当該システムに接続された複数のバ
ス主がアクセスできる。読み取るべきコードデータエレ
メントが予測される。データを求める該バス主のメモリ
アクセス要求を遅延することなく、この予測されたコー
ドデータエレメントは次いで該メモリシステム内で低速
メモリから高速メモリへ転送される。
【００１４】本発明はまた、バスによって複数のバス主
に接続可能なメモリシステムを与える。このシステムに
はシステムメモリと、キャッシュと、予測装置と、転送
装置とを含む。このメモリおよびキャッシュは該バスに
接続される。この予測装置はバス主が読み取るデータエ
レメントを予測する。転送装置は該バス主が要求するメ
モリアクセスを遅延させることなく、該予測されたデー
タエレメントをメモリからキャッシュへ転送する。
【００１５】
【実施例】図１はコンピューターメモリシステム１０の
ブロック線図を示す。メモリシステム１０はシステムメ
モリ１２を含む。メモリ１２は好ましい実施例では動的
ランダムアクセスメモリ（ＤＲＡＭ）チップからなる。 メモリ１２に格納されるデータは一般にコードデータ（
命令）と非コードデータとに分割することができる。 ここに使用する「データ」という用語は情報を指し、コ
ードデータ（命令）および非コードデータを含む。メモ
リ１２はバス１４でコンピューターシステム（図示して
なし）の他の部分に接続されている。メモリシステム１
０は二つ以上のバス主に使用できるように設計されてい
るが、単一のバス主に使うこともできる。特にメモリシ
ステム１０は他のバス主またはメモリシステム１０への
アクセスに関してホストプロセッサと競合する装置と組
み合わせたインテル社のホストプロセッサ３８６、３８
６ｓｘ、４８６等に使用することができるように設計さ
れている。メモリ１２へのアクセスはバス１４内に設け
られたＤＲＡＭ制御装置２２で制御される。
【００１６】システム１０はまたバス１４にそれぞれ接
続された内部キャッシュ１６、プレフェッチキャッシュ
１８、および書き込みバッファキャッシュ２０を含む。 好ましい実施例では内部キャッシュ１６は４Ｋバイトの
４通り−セット関連キャッシュで、プレフェッチキャッ
シュ１８は１２８バイトの直接転写キャッシュで、書き
込みバッファキャッシュ２０は１２８バイトの２通り−
セット関連キャッシュである。
【００１７】本キャッシュの特徴は使用されるホストプ
ロセッサの形式（３８６、３８６ｓｘ、４８６）に応じ
てこれらキャッシュの機能が変更できることである。し
かし、キャッシュのいくつかの特徴は変更できない。例
えば内部キャッシュ１６はホストプロセッサによるメモ
リアクセスに基づいてのみ選択できるデータを保持する
。言い換えると、内部キャッシュ１６はホストプロセッ
サ専用であり、他のバス主によるメモリアクセスによっ
て影響されない。任意のバス主が各キャッシュを読み取
りできることを認識されたい。従って内部キャッシュ１
６はその中にシステムプロセッサ以外の他のプロセッサ
によるメモリアクセスに基づくデータ書き込みは許さな
いが、他のバス主も、要求しているデータがその中にあ
る限りデータの読み取りはできる。各キャッシュは検分
（記録内容を検分すること）でヒットした記録内容を無
効にするため、当該キャッシュで意図されていないデー
タ書き込みもすべて検分し、これによって動作の一貫性
を確保することを認識されたい。
【００１８】キャッシュに関し不変な特徴の一つは、プ
レフェッチキャッシュ１８がＤＲＡＭ１２から取り寄せ
たコードデータのみを収容することである。後で詳述す
るように、プレフェッチキャッシュ１８はホストプロセ
ッサのメモリアクセスに基づくコードのみを取り寄せる
。動作上、システムプロセッサがプレフェッチキャシュ
内に用意されていないコードデータを要求するときは、
次のコード要求を予期して次順の１２８バイトコードが
プレフェッチキャッシュ１８内に予め取り寄せ（プレフ
ェッチ）される。
【００１９】書き込みバッファキャッシュ２０はＤＲＡ
Ｍ１２内に書き込まれるデータのバッファのみを行なう
。このキャッシュは単に書き込みバッファを行なうのみ
ならず、上述したように任意のバス主による読み取りも
許すキャッシュである。しかしこのバッファはＤＲＡＭ
１２からのデータのキャッシュはしない。
【００２０】各キャッシュの機能が分離されていること
、およびプロセッサの形式に基づいてこれらの機能を選
択的に定義できることは本キャッシュの重要な特徴であ
る。この性能により、本システムはキャッシュを総和的
に使用するものよりも何倍も大きなキャッシュを使用す
るシステムの性能を達成し、またはこれをしのぐことが
できる。プロセッサの形式に基づいて選択的に機能を定
義できる点に関していうと、４８６プロセッサを使用す
るシステムの場合、書き込みバッファキャッシュ２０は
システム以外のすべてのバス主が行なうデータ書き込み
のバッファを行なう。３８６、３８６ｓｘシステムプロ
セッサを使用するシステムの場合、内部キャッシュ１６
はコードデータのみを保持し、システムプロセッサのた
めの読み取り専用キャッシュであり、書き込みバッファ
キャッシュ２０はシステムプロセッサを含めた任意のバ
ス主によるデータ書き込みのバッファを行なう。これら
キャッシュの動作特性は、存在するホストプロセッサの
形式情報に基づいて、電力投入時の自己形成条件に従っ
て定義される。
【００２１】ＤＲＡＭ制御装置２２はＤＲＡＭ１２への
アクセスのための高速ページモードを支持する。高速ペ
ージモードはメモリページ内の行ラインをアクティブと
した後、列ラインを順次ストロボ作動させてデータをＤ
ＲＡＭの中にまたはＤＲＡＭの外に転送することにより
ＤＲＡＭへのアクセスを高速化する良く知られた方法で
ある。加えて、ＤＲＡＭ１２はコードデータか非コード
データのいずれかを含むページに分割されている。ＤＲ
ＡＭ１２に関連されたレジスタはＤＲＡＭ１２内または
ＤＲＡＭ制御装置２２内に配置され、最も最近にアクセ
スされたページのページアドレスを保持する。実際、本
システムは本システムに接続されたプロセッサの形式に
応じてコードページまたは非コードページに指向するバ
イアスを与える。例えばもしもシステムプロセッサが４
８６であると、もっとも最近にアクセスされたコードア
ドレスページのアドレスがレジスタ内に保持される。動
作上、ＤＲＡＭ１２内のコードデータページおよび非コ
ードデータページは共にランダムアクセスができる。も
しもコードページがある一サイクルでアクセスされ、次
のサイクルで非コードページがアクセスされると、非コ
ードページがアクセスされる間、コードページのアドレ
スはレジスタ内に保持される。非コードページがアクセ
スされた直後、再びコードページを開くのにレジスタ内
のそのアドレスが使用される。これと対照的に、もしも
システムプロセッサが３８６または３８６ｓｘであると
、最も最近にアクセスされた非コードアドレスページの
アドレスがレジスタ内に保持される。オープンページバ
イアス、高速ページモードアクセスおよび多重キャッシ
ュを選択的になしうるこの組み合わせがシステム性能を
高める。
【００２２】書き込みバッファキャッシュ２０は２通り
−セット関連キャッシュである。メモリの非コードデー
タ領域は、リスト、ヒープ（ｈｅａｐ）、およびスタッ
ク（ｓｔａｃｋ）として知られる三つの領域に分割でき
る。メモリ内のデータブロックはリスト、ヒープ、およ
びスタックように準備され、それぞれ、各自の組織と目
的を有する。例えばスタックは一組のデータエレメント
で、その内の一エレメントのみが一度にアクセスできる
。リストデータは主として読み取り用であり、一般的に
書き込み用ではない。構造を有するプログラムではスタ
ックへの書き込みが高い頻度で起こり、次に頻度の高い
書き込みはヒープに対して起きる。ＤＲＡＭ内にヒープ
用のデータブロックとスタック用のデータブロックを適
切に指定し、かつこれらブロックを２通り−セット関連
キャッシュ内の対向するセットに転写することにより、
動作効率を高めることができる。さらに非コードデータ
に対するＤＲＡＭ内のオープンページバイアスは実効上
、リストデータに対するオープンページバイアスとなる
。このようにして動作特性がさらに高められる。
【００２３】図２および図３は本発明の一形態であるプ
レフェッチキューキャッシュ１８の線図である。キャッ
シュ１８はシステムメモリ１２からコードデータエレメ
ント（ダブル語）を受信し、外部バス主は読み取りのみ
が可能であり、書き込みはできない。キャッシュ１８は
アドレスラインおよびデータラインの両方を含むトラン
ザクションバス１４に接続されている。キャッシュ１８
は両者あいまって最大３２個のダブル語（３２ｘ４バイ
ト）を保持するコードデータＲＡＭ２０２および２０４
、ＲＡＭ２０２、２０４、タグＲＡＭ２０６、妥当性ア
レー２０８、および関連制御論理回路を含む。キャッシ
ュ１８は直接転写キャッシュで、ＲＡＭ２０６内のアド
レスタグがデータＲＡＭ２０２、２０４内の４個のダブ
ル語の各ラインに対応する。キャッシュヒットは、（前
進アドレスバス２１０またはトランザクションバス１４
の何れかからの）現アドレスに対して選択されたビット
をタグＲＡＭ２０６からのアドレスに比較することによ
り決定される。この比較はもしも現データがキャッシュ
１８内にあれば「ヒット」信号を発生するヒット検出論
理回路２１４でなされる。
【００２４】図４はキャッシュ１８内の格納スペースの
利用可能性を示唆する「推定」信号を与えるための、キ
ャッシュ１８に密接に関連した構造体の線図である。プ
レフェッチポインタ２１６はキャッシュ１８に転送され
た最も最近のデータエレメントのアドレスを格納するレ
ジスタである。現アドレスポインタ２１８はキャッシュ
１８から読み込まれた最も最近のデータエレメントのア
ドレスを格納するレジスタである。これら各レジスタに
格納されるアドレスはそれぞれのデータエレメントの完
全なアドレスの本の一部である。現アドレスポインタに
体して選択されたビット数はタグ２０６内に用意される
ロケーション数に依存する。例えばもしも各データエレ
メントにタグアドレスがあり、また３２個のデータエレ
メントがあるなら、現アドレスビット数は５（３２５の
５）。図示した実施例では各データラインにタグアドレ
スがあり、各データラインは複数のデータエレメント（
４ｘ３２ビット、すなわち４個のダブル語）を保持する
。従って、現アドレスポインタ２１８は８本のラインの
一つを指すアドレスビット４、５、および６を含む。 ｐレフェッチポインタ２１６はキャッシュ１８尚の３２
個のデータエレメントの一つを指すアドレスビット２、
３、４、５、および６を保持する。プレフェッチポイン
タ２１６は、プレフェッチポインタ２１６のアドレスを
１だけ増大させる加算器２２０に接続されている。加算
器２２０および現アドレスポインタ２１８のの出力は比
較器２２２の入力として接続される。比較器２２２の出
力は、二つの値が等しくない限りアクティブな推定信号
となる。しかし、プレフェッチポインタ２１６内のアド
レスが現アドレスポインタ２１８内のアドレスよりも１
少ないときは、「推定」は無効にされる。
【００２５】各データエレメントに対してタグアドレス
があり、現アドレスポインタ２１８が個々のエレメント
を特定するなら、プレフェッチポインタ２１６内の当該
アドレスは現アドレスポインタ２１８のｍ番目毎のアド
レスの値よりも１だけ小さくなる。ここにｍはプレフェ
ッチキャッシュ１８内のデータエレメント（ダブル語）
の数である。推定信号は、プレフェッチポインタ２１６
が現アドレスポインタ２１８より一アドレスだけ後でな
いときは必ずキャッシュ１８内の格納スペースが利用可
能であるか否かを示す。もしも各データラインに対して
タグアドレスがあり、現アドレスポインタ２１８が個々
のラインを特定するなら、プレフェッチポインタ２１６
内のアドレスは現アドレスポインタ２１８のｎ番目毎の
アドレスの値よりも１だけ小さくなる。ここにｎはプレ
フェッチキャッシュ１８内のデータライン数である。以
下の議論では各データラインに対してタグアドレスがあ
り、現アドレスポインタ２１８が個々のラインを特定す
ることを仮定している。しかし当業者は図４に示すよう
なポインタ構成にもこの議論が適用できることが了解で
きよう。
【００２６】プレフェッチポインタ２１６はＤＲＡＭ１
２から転送される各データエレメントのアドレスが入力
される。現アドレスポインタ２１８はキャッシュ１８か
ら読み込まれるデータエレメント各々のアドレスが入力
される。もしもキャッシュ１８が完全に予測されたデー
タエレメントで一杯であると、推定信号は無効にされる
。もしもバス主により読み込まれた次のコードデータエ
レメントが前に読み込まれたアドレスの次順のアドレス
であると、現アドレスポインタ２１８はその次のアドレ
スが入れられる。プレフェッチポインタ２１６は次いで
現アドレスポインタ２１８を二つだけ遅らせ、キャッシ
ュ１８から読み見込まれたばかりのデータエレメントを
新しいデータエレメントで置換することを要求するため
、推定信号が再び発せられる。従って、キャッシュ１８
は循環キューメモリである。言い換えると、バス主が要
求したコードデータエレメントに対してキャッシュ１８
内でヒットがある限り、キャッシュ１８は連続的に再入
力される。
【００２７】作動上、本発明の方法は大きく二つに分け
られる。第一に、読み込まれるべきコードデータエレメ
ントが予測される。第二に、該予測されたコードデータ
エレメントが、いかなるバス主のデータに対するメモリ
アクセス要求をも遅延することなくシステムメモリ１２
からキャッシュ１８へ転送される。しかしながら、以下
の説明から了解されようが、これら二つのステップは幾
分重複しており、一般的に言うと、本コンピューターシ
ステムがバス主からの各後続のコードデータ読み取り要
求を処理する期間中、反復される。
【００２８】初めに、プレフェッチポインタ２１６およ
び現アドレスポインタ２１８はアクティブ推定信号を与
える値を入力される。バス主の一つ、好ましくはホスト
プロセッサは、メモリシステムからコードデータエレメ
ントの読み取りを要求する。キャッシュヒットは起こら
ないので、要求されたデータエレメントはＤＲＡＭ１２
から読み込まれる。次順のデータエレメントを同定する
ために、要求されたデータエレメントのアドレスはＤＲ
ＡＭ制御装置２２内のレジスタに格納される。ＤＲＡＭ
制御装置２２はここで推定信号を受信し、格納されてい
たアドレスを次順のデータエレメントのアドレスに増大
する。トランザクションバス１４が自由であるときは常
に、この次順のデータエレメントはキャッシュ１８へ転
送される。
【００２９】ＤＲＡＭ制御装置２２がバス１４を検分し
、自由サイクルすなわちオープンサイクル時に次のデー
タエレメントを送信するのに使用されるいろいろの技術
がある。好ましい実施例では本メモリシステムはクロッ
クサイクルに同期されている。最も高速のデータ読み取
りは２サイクルかかる（キャッシュヒットがあった場合
）。バスインタフェースに要求が到来すると、メモリア
クセスを開始するため前進アドレスバス２１０を介して
予定のアドレスビットがキャッシュに直接に送られる。 これはトランザクションバス１４がアイドル状態になる
最初の期間に起こる。もしもキャッシュヒットがあると
、当該データエレメントは第二サイクルの間、トランザ
クションバス１４上に置かれる。第一サイクル期間中は
バス１４が開かれている（不使用となる）ので、このコ
ードデータエレメントは第一サイクル期間内にキャッシ
ュ１８に転送される。オープンサイクル期間にＤＲＡＭ
１２からキャッシュ１８へ予測されたデータエレメント
を転送することにより、バス主のメモリアクセス要求は
遅延されない。このことは本発明の重要な特徴である。 その理由はキャッシュ１８内のすべてのデータエレメン
トは単に推定されたものに過ぎず、もしもサイクル時間
がデータエレメントをキャッシュ化するのに失われるな
ら、キャッシュ中にコードデータをプレフェッチしてお
くことによる性能の向上は一部的なものであるからであ
る。
【００３０】ＤＲＡＭ制御装置内のアドレスを次順のデ
ータエレメントのアドレスに増大させる先行プロセス、
推定信号の観察、バス１４の監視、およびＤＲＡＭ１２
からキャッシュ１８へのデータエレメントの転送はキャ
ッシュ１８内に空きがあるかぎり反復される。キャッシ
ュ１８内の利用可能な空きとは、キャッシュ１８内にｍ
個より少ない予測データエレメントがあることを言う。 ここにｍはキャッシュ１８のデータエレメント容量であ
る。エレメントはもしもそれが読み取られることが予期
されるデータエレメントの集合内にあると、特定の時点
に「予測できる」。例えばもしもキャッシュ１８が先行
の読み取り時に次のｍ個の順次的データエレメントで一
杯であることが解かると、空きは全くない。もしも次の
読み取り要求がキャッシュ１８内にないコードデータエ
レメントを求めるものであればキャッシュ１８内のｍ個
のデータエレメントはその場合「予測される」ものでは
ないので、キャッシュ１８内のすべての空間が空きであ
り、「利用可能」である。コードデータエレメントがキ
ャッシュ１８内にあると否とにかかわらずバス主により
読み取られるときは、キャッシュ１８内の各データエレ
メントに対してタグアドレスがある限り、常に予測され
る順次的コードデータエレメントが一つ以上あり、これ
らデータエレメントがＤＲＡＭ１２からキャッシュ１８
中に転送される。しかし現アドレスポインタ２１８が同
一のラインアドレスで満たされていると、各データライ
ンに対するタグアドレスがあってもバス主のコード読み
取りによってはＤＲＡＭ１２からの転送が起こらない。
【００３１】本発明の詳細な設計は高度ハードウェア記
述言語であるＣＤＬで行なわれる。ＣＤＬはデジタル論
理システム用のハードウェアを曖昧さなしに定義するソ
フトウェアツールである。ＣＤＬリストは完全にシステ
ム１０の好ましい実施例を確定する。このリストはこれ
をコンパイルすると「Ｃ」ソースコードを与え、このソ
ースコードは次いでＣコンパイラでコンパイルされて標
準化されたＣオブジェクトファイルフォーマット（ＣＯ
ＦＦ）を与える。次いでこのＣオブジェクトファイルフ
ォーマットを論理合成プログラムに入力すると詳細な論
理構造体が得られる。この目的に使用される論理合成プ
ログラムはカルフォルニア州マウンテンビュー市のシノ
プシス社から販売されているＳＹＮＯＰＳＹＳである。
【００３２】図５は本発明のモジュール間の関係を示す
。
【００３３】
【図面の簡単な説明】
【図１】図１は高性能コンピューターメモリシステムの
ブロック線図である。
【図２】図２は本発明に基づくプレフェッチキューの一
部の線図である
【図３】図３は図２に続く残りの線図である。
【図４】図４は図２、および図３のプレフェッチキュー
に使用する推定信号発生装置の線図である。
【図５】図５は本メモリシステムのモジュール間の関係
を示すブロック線図である。
【符号の説明】
１０　　コンピューターメモリシステム１４　　バス １８　　プレフェッチキャッシュ

Claims (3)

    【特許請求の範囲】
  1. 【請求項１】メモリシステムにバスで接続された複数の
    バス主がアクセスできる該メモリシステムにおけるデー
    タエレメント管理方法であって、読み取るべきコードデ
    ータエレメントを予測することと、該メモリシステム内
    の該予測されたコードデータエレメントを、データを求
    める該バス主のメモリアクセス要求を遅延することなく
    該メモリシステム内で低速メモリから高速メモリへ転送
    することとを含むデータエレメント管理方法。
  2. 【請求項２】複数のデバイスがアクセスできるメモリシ
    ステムにおけるデータエレメント管理方法であって、読
    み取るべきコードデータエレメントを予測することと、
    該メモリシステム内の該予測されたコードデータエレメ
    ントを、データを求める該バス主のメモリアクセス要求
    を遅延することなく該メモリシステム内で低速メモリか
    ら循環キュー高速メモリへ転送することとを含むデータ
    エレメント管理方法。
  3. 【請求項３】バスによって複数のバス主に接続可能なメ
    モリシステムであって、該バスに接続されたシステムメ
    モリと、該バスに接続されたキャッシュと、バス主が読
    み取るデータエレメントを予測するための手段と、該メ
    モリシステム内の該予測されたコードデータエレメント
    を、データを求める該バス主のメモリアクセス要求を遅
    延することなく該メモリから該キャッシュへ転送する装
    置とを含むメモリシステム。
JP21662191A 1990-08-06 1991-08-02 データプレフェッチの方法およびその装置 Expired - Lifetime JP3323212B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/563,215 US5530941A (en) 1990-08-06 1990-08-06 System and method for prefetching data from a main computer memory into a cache memory
US563215 1990-08-06

Publications (2)

Publication Number Publication Date
JPH04233641A true JPH04233641A (ja) 1992-08-21
JP3323212B2 JP3323212B2 (ja) 2002-09-09

Family

ID=24249573

Family Applications (1)

Application Number Title Priority Date Filing Date
JP21662191A Expired - Lifetime JP3323212B2 (ja) 1990-08-06 1991-08-02 データプレフェッチの方法およびその装置

Country Status (4)

Country Link
US (2) US5530941A (ja)
EP (1) EP0470734B1 (ja)
JP (1) JP3323212B2 (ja)
DE (1) DE69132186T2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009537921A (ja) * 2006-05-22 2009-10-29 インターナショナル・ビジネス・マシーンズ・コーポレーション リモート・プリフェッチ・バッファを提供するためのシステム及び方法

Families Citing this family (60)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2247546B (en) * 1990-08-31 1995-03-01 Sun Microsystems Inc Method and apparatus for predictive caching
JP3451099B2 (ja) * 1991-12-06 2003-09-29 株式会社日立製作所 外部記憶サブシステム
DE69327981T2 (de) * 1993-01-21 2000-10-05 Advanced Micro Devices, Inc. Kombinierte Speicheranordnung mit einem Vorausholungspuffer und einem Cachespeicher und Verfahren zur Befehlenversorgung für eine Prozessoreinheit, das diese Anordnung benutzt.
TW228580B (en) * 1993-10-01 1994-08-21 Ibm Information processing system and method of operation
US5778436A (en) * 1995-03-06 1998-07-07 Duke University Predictive caching system and method based on memory access which previously followed a cache miss
US5680640A (en) * 1995-09-01 1997-10-21 Emc Corporation System for migrating data by selecting a first or second transfer means based on the status of a data element map initialized to a predetermined state
US6385710B1 (en) * 1996-02-23 2002-05-07 Sun Microsystems, Inc. Multiple-mode external cache subsystem
US5781916A (en) * 1996-03-25 1998-07-14 Motorola, Inc. Cache control circuitry and method therefor
US6446149B1 (en) * 1998-03-03 2002-09-03 Compaq Information Technologies Group, L.P. Self-modifying synchronization memory address space and protocol for communication between multiple busmasters of a computer system
US6295583B1 (en) * 1998-06-18 2001-09-25 Compaq Information Technologies Group, L.P. Method and apparatus for resolving probes in multi-processor systems which do not use external duplicate tags for probe filtering
US6449697B1 (en) 1999-04-23 2002-09-10 International Business Machines Corporation Prestaging data into cache in preparation for data transfer operations
US6421763B1 (en) 1999-06-30 2002-07-16 International Business Machines Corporation Method for instruction extensions for a tightly coupled speculative request unit
US6510494B1 (en) 1999-06-30 2003-01-21 International Business Machines Corporation Time based mechanism for cached speculative data deallocation
US6360299B1 (en) * 1999-06-30 2002-03-19 International Business Machines Corporation Extended cache state with prefetched stream ID information
US6532521B1 (en) 1999-06-30 2003-03-11 International Business Machines Corporation Mechanism for high performance transfer of speculative request data between levels of cache hierarchy
US6393528B1 (en) * 1999-06-30 2002-05-21 International Business Machines Corporation Optimized cache allocation algorithm for multiple speculative requests
US6496921B1 (en) 1999-06-30 2002-12-17 International Business Machines Corporation Layered speculative request unit with instruction optimized and storage hierarchy optimized partitions
US6421762B1 (en) 1999-06-30 2002-07-16 International Business Machines Corporation Cache allocation policy based on speculative request history
US6754779B1 (en) * 1999-08-23 2004-06-22 Advanced Micro Devices SDRAM read prefetch from multiple master devices
US6658505B2 (en) * 2001-06-05 2003-12-02 Hewlett-Packard Development Company, L.P. System and method for checking bits in a buffer with multiple entries
US6970978B1 (en) * 2002-04-03 2005-11-29 Advanced Micro Devices, Inc. System and method for providing a pre-fetch memory controller
US7055005B2 (en) * 2003-04-07 2006-05-30 Hewlett-Packard Development Company, L.P. Methods and apparatus used to retrieve data from memory into a RAM controller before such data is requested
US7051162B2 (en) * 2003-04-07 2006-05-23 Hewlett-Packard Development Company, L.P. Methods and apparatus used to retrieve data from memory before such data is requested
US7370125B2 (en) * 2003-11-25 2008-05-06 Intel Corporation Stream under-run/over-run recovery
US20050143843A1 (en) * 2003-11-25 2005-06-30 Zohar Bogin Command pacing
US7346716B2 (en) 2003-11-25 2008-03-18 Intel Corporation Tracking progress of data streamer
US7238218B2 (en) * 2004-04-06 2007-07-03 International Business Machines Corporation Memory prefetch method and system
US20050246500A1 (en) * 2004-04-28 2005-11-03 Ravishankar Iyer Method, apparatus and system for an application-aware cache push agent
US7296129B2 (en) 2004-07-30 2007-11-13 International Business Machines Corporation System, method and storage medium for providing a serialized memory interface with a bus repeater
US7389375B2 (en) 2004-07-30 2008-06-17 International Business Machines Corporation System, method and storage medium for a multi-mode memory buffer device
US7539800B2 (en) 2004-07-30 2009-05-26 International Business Machines Corporation System, method and storage medium for providing segment level sparing
US7512762B2 (en) 2004-10-29 2009-03-31 International Business Machines Corporation System, method and storage medium for a memory subsystem with positional read data latency
US7305574B2 (en) 2004-10-29 2007-12-04 International Business Machines Corporation System, method and storage medium for bus calibration in a memory subsystem
US7395476B2 (en) 2004-10-29 2008-07-01 International Business Machines Corporation System, method and storage medium for providing a high speed test interface to a memory subsystem
US7299313B2 (en) 2004-10-29 2007-11-20 International Business Machines Corporation System, method and storage medium for a memory subsystem command interface
US7441060B2 (en) 2004-10-29 2008-10-21 International Business Machines Corporation System, method and storage medium for providing a service interface to a memory system
US7356737B2 (en) 2004-10-29 2008-04-08 International Business Machines Corporation System, method and storage medium for testing a memory module
US7277988B2 (en) 2004-10-29 2007-10-02 International Business Machines Corporation System, method and storage medium for providing data caching and data compression in a memory subsystem
US7331010B2 (en) 2004-10-29 2008-02-12 International Business Machines Corporation System, method and storage medium for providing fault detection and correction in a memory subsystem
US7610497B2 (en) * 2005-02-01 2009-10-27 Via Technologies, Inc. Power management system with a bridge logic having analyzers for monitoring data quantity to modify operating clock and voltage of the processor and main memory
US7478259B2 (en) 2005-10-31 2009-01-13 International Business Machines Corporation System, method and storage medium for deriving clocks in a memory system
US7685392B2 (en) 2005-11-28 2010-03-23 International Business Machines Corporation Providing indeterminate read data latency in a memory system
US7594055B2 (en) 2006-05-24 2009-09-22 International Business Machines Corporation Systems and methods for providing distributed technology independent memory controllers
US7640386B2 (en) 2006-05-24 2009-12-29 International Business Machines Corporation Systems and methods for providing memory modules with multiple hub devices
US7584336B2 (en) 2006-06-08 2009-09-01 International Business Machines Corporation Systems and methods for providing data modification operations in memory subsystems
US8720447B2 (en) * 2006-07-28 2014-05-13 Family Concepts Tjh, Llc Suspended back pillow for sustaining a side sleeping position
US7874032B2 (en) * 2008-06-24 2011-01-25 Vaughn North Method and device for maintaining a side sleeping position
US7493439B2 (en) 2006-08-01 2009-02-17 International Business Machines Corporation Systems and methods for providing performance monitoring in a memory system
US7669086B2 (en) 2006-08-02 2010-02-23 International Business Machines Corporation Systems and methods for providing collision detection in a memory system
US7581073B2 (en) 2006-08-09 2009-08-25 International Business Machines Corporation Systems and methods for providing distributed autonomous power management in a memory system
US7587559B2 (en) 2006-08-10 2009-09-08 International Business Machines Corporation Systems and methods for memory module power management
US7539842B2 (en) 2006-08-15 2009-05-26 International Business Machines Corporation Computer memory system for selecting memory buses according to physical memory organization information stored in virtual address translation tables
US7490217B2 (en) 2006-08-15 2009-02-10 International Business Machines Corporation Design structure for selecting memory busses according to physical memory organization information stored in virtual address translation tables
US7477522B2 (en) 2006-10-23 2009-01-13 International Business Machines Corporation High density high reliability memory module with a fault tolerant address and command bus
US7870459B2 (en) 2006-10-23 2011-01-11 International Business Machines Corporation High density high reliability memory module with power gating and a fault tolerant address and command bus
US7721140B2 (en) 2007-01-02 2010-05-18 International Business Machines Corporation Systems and methods for improving serviceability of a memory system
US7606988B2 (en) 2007-01-29 2009-10-20 International Business Machines Corporation Systems and methods for providing a dynamic memory bank page policy
US7603526B2 (en) 2007-01-29 2009-10-13 International Business Machines Corporation Systems and methods for providing dynamic memory pre-fetch
US8429775B2 (en) * 2009-06-23 2013-04-30 Vaughn W. North Suspended back pillow for sustaining a side sleeping position
WO2014011181A1 (en) * 2012-07-12 2014-01-16 Hewlett-Packard Development Company, L.P. Providing data to be retrieved

Family Cites Families (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB1354827A (en) * 1971-08-25 1974-06-05 Ibm Data processing systems
US4527237A (en) * 1979-10-11 1985-07-02 Nanodata Computer Corporation Data processing system
US4442488A (en) * 1980-05-05 1984-04-10 Floating Point Systems, Inc. Instruction cache memory system
US4442484A (en) * 1980-10-14 1984-04-10 Intel Corporation Microprocessor memory management and protection mechanism
US4490782A (en) * 1981-06-05 1984-12-25 International Business Machines Corporation I/O Storage controller cache system with prefetch determined by requested record's position within data block
DE3382350D1 (de) * 1982-11-17 1991-08-29 Nec Corp Anordnung zum vorabholen von befehlen mit vorhersage einer verzweigungszieladresse.
US4719568A (en) * 1982-12-30 1988-01-12 International Business Machines Corporation Hierarchical memory system including separate cache memories for storing data and instructions
US4622631B1 (en) * 1983-12-30 1996-04-09 Recognition Int Inc Data processing system having a data coherence solution
US4823259A (en) * 1984-06-29 1989-04-18 International Business Machines Corporation High speed buffer store arrangement for quick wide transfer of data
US4884197A (en) * 1985-02-22 1989-11-28 Intergraph Corporation Method and apparatus for addressing a cache memory
WO1987005417A1 (en) * 1986-02-28 1987-09-11 Nec Corporation Instruction prefetch control apparatus
US4991080A (en) * 1986-03-13 1991-02-05 International Business Machines Corporation Pipeline processing apparatus for executing instructions in three streams, including branch stream pre-execution processor for pre-executing conditional branch instructions
US4914577A (en) * 1987-07-16 1990-04-03 Icon International, Inc. Dynamic memory management system and method
US4926317A (en) * 1987-07-24 1990-05-15 Convex Computer Corporation Hierarchical memory system with logical cache, physical cache, and address translation unit for generating a sequence of physical addresses
US5055999A (en) * 1987-12-22 1991-10-08 Kendall Square Research Corporation Multiprocessor digital data processing system
US5025366A (en) * 1988-01-20 1991-06-18 Advanced Micro Devices, Inc. Organization of an integrated cache unit for flexible usage in cache system design
US5023776A (en) * 1988-02-22 1991-06-11 International Business Machines Corp. Store queue for a tightly coupled multiple processor configuration with two-level cache buffer storage
US5247649A (en) * 1988-05-06 1993-09-21 Hitachi, Ltd. Multi-processor system having a multi-port cache memory
US4987529A (en) * 1988-08-11 1991-01-22 Ast Research, Inc. Shared memory bus system for arbitrating access control among contending memory refresh circuits, peripheral controllers, and bus masters
US5113515A (en) * 1989-02-03 1992-05-12 Digital Equipment Corporation Virtual instruction cache system using length responsive decoded instruction shifting and merging with prefetch buffer outputs to fill instruction buffer
US5136697A (en) * 1989-06-06 1992-08-04 Advanced Micro Devices, Inc. System for reducing delay for execution subsequent to correctly predicted branch instruction using fetch information stored with each block of instructions in cache
US5230068A (en) * 1990-02-26 1993-07-20 Nexgen Microsystems Cache memory system for dynamically altering single cache memory line as either branch target entry or pre-fetch instruction queue based upon instruction sequence
US5226130A (en) * 1990-02-26 1993-07-06 Nexgen Microsystems Method and apparatus for store-into-instruction-stream detection and maintaining branch prediction cache consistency
US5283873A (en) * 1990-06-29 1994-02-01 Digital Equipment Corporation Next line prediction apparatus for a pipelined computed system

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009537921A (ja) * 2006-05-22 2009-10-29 インターナショナル・ビジネス・マシーンズ・コーポレーション リモート・プリフェッチ・バッファを提供するためのシステム及び方法

Also Published As

Publication number Publication date
US5751994A (en) 1998-05-12
EP0470734A1 (en) 1992-02-12
DE69132186T2 (de) 2001-01-18
US5530941A (en) 1996-06-25
JP3323212B2 (ja) 2002-09-09
DE69132186D1 (de) 2000-06-15
EP0470734B1 (en) 2000-05-10

Similar Documents

Publication Publication Date Title
JP3323212B2 (ja) データプレフェッチの方法およびその装置
US5586294A (en) Method for increased performance from a memory stream buffer by eliminating read-modify-write streams from history buffer
US5659713A (en) Memory stream buffer with variable-size prefetch depending on memory interleaving configuration
US5371870A (en) Stream buffer memory having a multiple-entry address history buffer for detecting sequential reads to initiate prefetching
US5490113A (en) Memory stream buffer
US5388247A (en) History buffer control to reduce unnecessary allocations in a memory stream buffer
US5958040A (en) Adaptive stream buffers
US8725987B2 (en) Cache memory system including selectively accessible pre-fetch memory for pre-fetch of variable size data
US6321296B1 (en) SDRAM L3 cache using speculative loads with command aborts to lower latency
US5781926A (en) Method and apparatus for sub cache line access and storage allowing access to sub cache lines before completion of line fill
US5420994A (en) Method for reading a multiple byte data element in a memory system with at least one cache and a main memory
US5287512A (en) Computer memory system and method for cleaning data elements
US5452418A (en) Method of using stream buffer to perform operation under normal operation mode and selectively switching to test mode to check data integrity during system operation
US5367657A (en) Method and apparatus for efficient read prefetching of instruction code data in computer memory subsystems
US6240487B1 (en) Integrated cache buffers
US6801982B2 (en) Read prediction algorithm to provide low latency reads with SDRAM cache
US5835945A (en) Memory system with write buffer, prefetch and internal caches
US5434990A (en) Method for serially or concurrently addressing n individually addressable memories each having an address latch and data latch
EP0535701A1 (en) Architecture and method for combining static cache memory and dynamic main memory on the same chip (CDRAM)
US5953740A (en) Computer memory system having programmable operational characteristics based on characteristics of a central processor
JP3187465B2 (ja) コンピューターメモリオープンページバイアス法とその装置
US20010034808A1 (en) Cache memory device and information processing system
US20070050553A1 (en) Processing modules with multilevel cache architecture
GB2454811A (en) Cache memory which pre-fetches data when an address register is written
JPH04253238A (ja) コンピューターメモリシステムおよびキャッシュ・オーバーフローに関わる性能の強化法

Legal Events

Date Code Title Description
R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20080628

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090628

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090628

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100628

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100628

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110628

Year of fee payment: 9

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120628

Year of fee payment: 10

EXPY Cancellation because of completion of term
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120628

Year of fee payment: 10