(57)【特許請求の範囲】
【請求項１】
実行パイプラインと、
前記実行パイプラインに結合されたキャッシュと、
ロード命令がキャッシュミスする毎に、当該ロード命令に係る１エントリを登録してデータを当該エントリ内のデータフィールドに記憶し、続いてブロックインされた前記データを、当該データを必要とする他の全てのエントリの中のデータフィールドに一度に充足する待ち行列構造と
を有し、前記待ち行列構造は、目標レジスタへのデータのロード命令に対して、前記データがキャッシュにない場合、前記データおよび前記データの目標レジスタのＩＤを前記実行パイプラインに送り、さらに可観測性ビットの記憶域を含み、該可観測性ビットは、未処理の記憶命令が該記憶命令以前のメモリデータの要求の完了を待っているときに、前記要求されたメモリデータが待ち行列構造にまだ存在しない場合であっても、未処理の記憶命令が実行されるようにメモリデータの要求が十分に完了していることを示す、コンピュータシステム。
【請求項２】
前記待ち行列構造は、複数のデータエントリを記憶するのに十分な容量を有し、前記エントリを前記実行パイプラインに任意の順序で送るように適合されている、請求項１に記載のコンピュータシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータシステムに係り、とりわけ、コンピュータのランダムアクセスメモリシステムに関し、さらに詳細にはキャッシュミスの後、要求された項目をプロセッサに供給するのに要する時間の短縮に関する。
【０００２】
【従来の技術】
多くのコンピュータシステムにメモリシステムの多レベル階層構造が採用されており、比較的高速、高コスト、容量の限られたメモリが階層構造の最上位にあり、階層構造の最下位に向かってより低速、低コスト、大容量になっていく。メモリ階層構造の目的は平均メモリアクセス時間の短縮である。通常、階層構造は、速度を上げるためにプロセッサ集積回路に物理的に集積されるか、プロセッサに物理的に近接して取り付けられたキャッシュと呼ばれる小型の高速メモリを含む。メモリ階層構造は、メモリに対して要求される項目がその要求時に高いパーセンテージで階層構造の最上位（待ち時間の最も短いレベル）に存在する場合に、費用効率が高くなる。プロセッサがある項目を要求し、その項目がキャッシュにある場合、この事象をキャッシュヒットと呼ぶ。プロセッサがある項目を要求し、その項目がキャッシュにない場合、この事象をキャッシュミスと呼ぶ。キャッシュミスが発生すると、要求された項目はメモリ階層構造のより低レベル（待ち時間の長いレベル）から検索される。これによって性能に重大な影響が生じる可能性がある。一般的に、プロセッサの速度はメモリの速度を上回る速さで増大しており、したがってキャッシュミスの相対的性能ペナルティも時間を追って大きくなっている。
【０００３】
平均メモリアクセス時間はキャッシュヒット／ミス比を改善し、キャッシュミスによる時間ペナルティを低減し、キャッシュヒットに要する時間を短縮することによって短縮することができる。本発明は、主としてキャッシュミスの時間ペナルティの低減に関する。
【０００４】
【発明が解決しようとする課題】
多くのコンピュータシステムにおいて、パイプライニング（pipelining）と呼ばれる技術での実行時には複数の命令が重複する。パイプライニングにおいては、命令の実行は段階あるいはフェーズと呼ばれる小さな部分に分割され、段階あるいはフェーズは１つの命令全体の完了のためには、総時間内の一部の時間を要する。第１の命令が第１段階すなわちフェーズを完了して、第２段階すなわちフェーズに移行すると、第１段階では第２の命令が開始される。任意の時間において、各異なるフェーズでは、ある多数の命令の実行が重複する可能性がある。この場合、それらの命令がパイプラインを出る速度が有効命令速度となる。あるいは、コンピュータシステムが同時に複数の命令を出す場合がある。かかるシステムはスーパースカラマシンと呼ばれる。その１つのバリエーションとして、１つの命令が複数の演算を含む超長命令語マシーンがある。最後に、メモリを共用することのできる複数のプロセッサを有するシステムが存在する。これら全てを組み合わせたものが存在するのはいうまでもなく、また特にスーパースカラパイプライン処理マシーンも存在する。同時実行および重複実行は、独立命令すなわち演算を前提としている。これに対して、１つの演算に他の演算の計算結果が必要である場合、２つの演算は順次実行しなければならない。通常、これによる負荷は独立演算をハードウェアに供給するコンパイラにかかってくる。同時重複命令実行の環境において、キャッシュミスは多数の命令の中断といった重大な問題を引き起こす可能性がある。
【０００５】
キャッシュの内外に転送可能なメモリの最小量を行、あるいは場合によってはブロックと称する。通常、メモリはワード（例えば、３２ビット／ワード）に構成され、行は通常複数のワード（例えば、１６ワード／行）である。また、メモリを１つにつき多数の行を有するページに分割することもある。
【０００６】
キャッシュミスの影響を最小限にするには、さまざまな方法を用いることができる。例えば、キャッシュと他の低レベルメモリとの間にバッファを設ける場合がある。かかるバッファは、通常、ミスアドレスの直後のアドレスも必要であるとの仮定のもとに、ミスアドレスを含む順次アドレスのブロックすなわち行を取り込む。米国特許第５，３１７，７１８号（Jouppi氏）においては、ストリームバッファと称するバッファをキャッシュと低レベルメモリとの間に設ける。Jouppi氏の特許においては、項目は他のキャッシュミスがある場合、それが生じるまでこのバッファに記憶され、その後かかる項目はバッファから直接プロセッサに行く代わりにキャッシュに入れられる。Jouppi氏の特許で説明するストリームバッファは、キャッシュミスとなった特定の要求に加えてプロセッサが必要とする可能性の高い項目のブロックを高速にロードすることによって、キャッシュミスの影響を低減するものである。実際には、ストリームバッファはブロックサイズを増大させる。インターリーブ処理については、Jouppi氏はそれぞれが異なる開始アドレスを有する複数のストリームバッファを最低使用頻度に基づいて置き換えることを提案している。米国特許第５，４２３，０１６号（Tsuchiya氏他）においては、１つのデータブロックを保持するバッファが設けられる。Tsuchiya氏の特許では、バッファ内のこの１つのデータブロック内の項目はキャッシュに入れることなく、プロセッサがバッファから直接利用することができる。このデータブロックがキャッシュへの転送の前に再度アクセスされる場合、そのアクセス要求はブロックバッファから直接サービスされる。１つのブロックについていえば、Tsuchiya氏の特許に説明するバッファは、バッファ内の項目をまずキャッシュに入れることなく直接プロセッサに入手可能とすることによって、Jouppi氏の特許に比べて性能の改善は大きい。
【０００７】
キャッシュミスペナルティのさらなる低減、特に、異常実行を伴なう複数のミスや同じ行への複数のミスに対するペナルティの低減が必要とされている。
【０００８】
【課題を解決するための手段】
未処理アクセス待ち行列（ＰＡＱ）と呼ばれる内容参照可能メモリは、キャッシュミスの生じた、レジスタ指定（レジスタロード命令）付きのプロセッサによる複数のアクセスを保持するのに用いられる。ＰＡＱは低レベルから着信するデータが利用可能となり次第これを捕獲する。
【０００９】
各ＰＡＱエントリは、あるレジスタ宛先に供給すべき最大のデータ項目に対する十分なデータ（ダブルワード）を保持する。さらに、各ＰＡＱエントリは要求側装置への返却を支援し、また要求順序付けを支援するのに必要な全ての関連情報を保持する。特に、アドレスに加えて、各ＰＡＱエントリは、宛先レジスタおよび行中の注目されるデータフィールドのＩＤを保持する。１つの行に対するアクセスが２つ以上ある場合、それぞれの個別のアクセスには待ち行列中の別々のエントリが与えられ、１つの行のこのようなエントリの全てにその行が利用可能になり次第その行の適当な部分が供給される。最後に、この未処理アクセス待ち行列は、処理可能な状態のデータを有する複数のエントリの戻りパスの調停を行なう。
【００１０】
１つのメモリ行に対する複数のミスのエントリを設けることは、手続き（プロシージャ）の入口および出口境界等のメモリの順次の領域にアクセスする命令に対して特に有効である。このことにおいては、通常いくつかのレジスタが順次保存あるいは復元され、メモリアドレスは順次である。
【００１１】
ＰＡＱには以下の利点がある。
（ａ）データははじめにそれをキャッシュに入れることなく、待ち行列から直接入手可能である。
（ｂ）１つの行に対する別個の要求のそれぞれに別個のエントリが与えられ、各エントリにはその行が利用可能になり次第その行の適当な部分が供給される。（ｃ）この待ち行列は要求側装置に対して要求された任意の順序で結果を供給してアウトオブオーダ（out-of-order）キャッシュ戻りを支援し、複数のソースが処理可能な状態のデータを有する場合の調停を行なう。
【００１２】
【発明の実施の形態】
図１は、本発明に係るコンピュータシステムの一実施形態を示す概略ブロック図である。同図は、パイプライン処理されたシステムの１つのプロセッサの一部を示す。各プロセッサは主（Ｌ１）キャッシュ１００を含む。各プロセッサはより低レベルの（Ｌ２）キャッシュ１０２を有していてもよい。レジスタ宛先を有するメモリアクセスがＬ１キャッシュをミスした場合（Ｌ２キャッシュがある場合には両方のキャッシュをミスした場合）、対応するＰＡＱ１０４にアドレス、サイズ、宛先レジスタおよび他の情報が入力される。各ＰＡＱは複数のミスのための複数のエントリを有する。ミスした行は、それぞれのメモリ階層構造のより低いレベルから順次検索される。このより低いレベルとは、システムバス（以下、バスと称す）１０６を介して接続された共用ランダムアクセスメモリとすることができ、また、ディスク等の周辺装置とすることもできる。メモリ階層構造の低いレベルからの完全な行がバッファされる（１０８）。バッファに行が利用可能になり次第、対応するＰＡＱエントリは、未処理アクセスを満足するのに必要なその行内の適当なデータフィールド（ワードあるいはダブルワード）を受け取る。未処理アクセスはＬ１キャッシュではなくＰＡＱによって直接満足される。同じ行に対して複数の未処理アクセスがある場合、ＰＡＱ内の対応するそれぞれのエントリは、フィルバッファ１０８をバイパスしてバスから直接必要なデータフィールドを受け取る。実行パイプライン１１２に入力すべきデータについては、マルチプレクサ１１０がＰＡＱあるいはＬ１キャッシュのいずれかからのバイパスデータを選択する。
【００１３】
データの取り込みを要求するパイプライン処理された命令は、キャッシュ待ち行列１１４に入れられる。データがＬ１キャッシュあるいはＬ２キャッシュにある場合、データはキャッシュからマルチプレクサ１１０を介して供給される。両方のキャッシュでキャッシュミスが生じた場合、データアドレス、サイズ、宛先レジスタおよび他の情報がＰＡＱに入力され、その後ＰＡＱによってこの要求はＰＡＱによって満足される。
【００１４】
ＰＡＱは内容参照可能メモリ（ＣＡＭ：Content addressable memory）および追加のランダムアクセスメモリ（ＲＡＭ）あるいはデータレジスタセルを含む。ＰＡＱ内のフィールドは以下の通りである。
（ａ）物理アドレス
（ｂ）アクセスタイプ（ロード／記憶／ボス（both）／セマフォ／ナイザー（neither）／先取り）
（ｃ）アクセスサイズ（バイト）
（ｄ）目標レジスタ
（ｅ）データ
（ｆ）可観測性ビット（オプション）
【００１５】
物理アドレスはＣＡＭに記憶される。残りの項目は、別のＲＡＭあるいはデータレジスタセルに記憶される。データ取り出し命令がＰＡＱに入力されるとき、データフィールドを除く全てのフィールドが入力される。
【００１６】
次の表１は、代表的なパイプライン処理プロセッサのさまざまな段階を示す。プロセッサごとにかかる段階はさまざまに異なる。さらに、各段階ごとに複数のクロック位相がある場合があり、異なる段階で発生するものとして示す動作の一部は、実際には１つの段階の異なる位相で発生する。しかし、表１は限定的に解釈すべきものではなく、全体的な流れを示すことを意図したものである。第１段階では、命令アドレスが生成される。次に、命令キャッシュがアクセスされる。命令がキャッシュヒットした場合、その命令がキャッシュから取り出され、復号される。レジスタのみに関係する整数算術命令の場合、この算術演算は次の段階（段階４）で完了する場合がある。あるいは、ロードおよび記憶命令等のメモリ参照の場合、目標アドレスは段階４で生成される。続いて、データキャッシュアドレスが復号される。キャッシュヒットした場合、このデータは段階６でキャッシュから入手可能になるかあるいはキャッシュに入手可能となる。最後に、レジスタロード命令の場合、データは段階７でレジスタに書き込まれる。
【００１７】
【表１】
0003800383.tif 000002
【００１８】
本発明は、主としてレジスタロード命令に関する。表１に示すパイプライン段階においては、分岐命令や算術演算等の一部の命令は段階４の最後に終了する。このパイプラインに段階６の前に完了する命令があり、そのデータが前のキャッシュミスからのＰＡＱ内で入手可能である場合、そのキャッシュをバイパスして、パイプラインの始点で対応するレジスタロード命令を再起動することなくそのデータを段階７でこのパイプラインに「注入する」機会がある。ＰＡＱはデータに加えて目標レジスタＩＤを記憶して、データをパイプラインの中間的段階で注入することを可能にする。データがＰＡＱで入手可能であり、パイプラインの「レジスタ書き込み」段階が空き状態である場合、マルチプレクサ１１０はＰＡＱからデータおよび目標レジスタ情報を供給する。
【００１９】
また、ＰＡＱは複数のエントリからの選択を可能とする。例えば、単純で高性能なアルゴリズムとしては、２レベルの先入れ先出しを用いるアルゴリズムがある。第１のレベルはＰＡＱが行を受け取る順序であり、第２のレベルは行エントリが要求された順序である。すなわち、ＰＡＱは最初に検索された行をまず供給する。同じ行に複数のエントリがある場合、ＰＡＱは最初の要求をまず供給する。したがって、ＰＡＱは命令の順序に関わりなくデータが入手可能になり次第供給する。
【００２０】
本発明に係るキャッシュは非閉塞型である。すなわち、キャッシュミスの場合、プロセッサは他のメモリアクセスを実行することができる。メモリアクセス命令の中には、ソフトウェアが違いを認識できない限り任意の順序で実行可能なものがある。しかし、２つの特殊なカテゴリは次のように順次実行しなければならない。獲得（強いロードとも呼ぶ）はフォワードルッキングであり、後続のデータアクセス命令の完了前に獲得命令が十分完了していなければならない（データがシステムの指定された部分になければならない）。解放（強い記憶とも呼ぶ）はバックワードルッキングであり、解放命令が完了する前にそれ以前のメモリアクセスが十分完了していなければならない。一般的に、解放アクセスは実際にはデータを必要とせず、単にアクセスの開始のために前の命令が十分に完了していればよいことを指摘しておく。システムの複数の部分が獲得および解放が十分完了しているかどうかを見るためにモニターすることのできるビット（大域可観測性ビットと呼ぶ）を含む。特に、階層構造（１１６）の下位にあるメモリにはデータが検索されたことを示す信号を発する論理構造（可観測性論理１１８）を含むことがあり、このような信号はデータがバス１０６に供給され、ＰＡＱに入れられる前に利用可能となる。
【００２１】
最も性能の低いものでは、ＰＡＱ内のデータの存在が可観測性を示す。さらに、性能を向上させるために、ＰＡＱに低レベルキャッシュ、メモリあるいはバス１０６に関係付けられた論理構造によって設定可能な可観測性ビットを含めることができる。ＰＡＱの可観測性ビットは複雑性を増大させるが、性能を向上させる。ＰＡＱが可観測性ビットを有しない場合、解放は全ての従属アクセスのデータがＰＡＱ内に入るまで待って完了しなければならない。ＰＡＱが可観測性ビットを有しない場合、解放アクセスは可観測性ビットが設定され次第実行可能であり、これは一般的にはデータがＰＡＱに到達する前である。いずれの場合にも、解放の処理には少なくとも３つの設計上の選択肢がある。第一に、ＰＡＱが可観測性ビットを有しないものと仮定する。解放にはデータは不要であるがデータが存在することを知っていなければならないことに注意しなければならない。設計上の選択肢の１つは、単に必要なデータがＰＡＱに入るまでパイプラインを停止することである。これは性能の点からは最も望ましくない選択肢である。第二の選択肢は、必要なデータがＰＡＱに入るまで解放を実行パイプランに入力しないことである。あるクラスにおけるアプリケーションのためのコンピュータにはこれが好適な選択肢となるが、一般的には、これは最良の性能が得られる選択肢ではない。第三の設計上の選択肢は、ＰＡＱが必要なデータを有するようになるまで未処理の解放をキャッシュ待ち行列１１４に保持することである。この第三の選択肢は３つの中で最良の性能を提供する。これは、解放によってパイプラインの一部のフェーズが完了しており、また他のキャッシュアクセスが解放アクセスをパスすることができるためである。
【００２２】
ここで、ＰＡＱ内の可観測性ビットを有する上の３つの選択肢について考察する。ＰＡＱ可観測性ビットはバス１０６あるいはランダムアクセスメモリに付随するハードウェアによって、可観測性ビットをデータがＰＡＱに入手可能となる前に設定することができる。これは、３つの設計上の選択肢のそれぞれにおいて、未処理の解放アクセスは、ＰＡＱに実際にデータが入るのを待つ代わりにＰＡＱに可観測性ビットが設定され次第開始することが可能であることを意味する。最大限の性能を得るためには、ＰＡＱは可観測性ビットを含み、未処理の部分的に実行された解放はキャッシュ待ち行列に保持されねばならない。
【００２３】
多プロセッサシステムには、メモリを共用する多数のプロセッサが含まれる場合がある。ある特定のアドレスのデータがキャッシュおよびバッファ、そして本発明の場合にはＰＡＱを含む異なるいくつかの場所に存在することがある。一般的に、ある特定のアドレスのデータが１つの場所で変更され、続いて他のプロセッサがそれを要求する場合、最後に変更されたデータを同定しなければならない。これをコヒーレンシーと呼ぶ。コヒーレンシーを確保する方法の１つに、データの存在する可能性のある全ての場所にアドレス（スヌープアドレスと呼ぶ）を送る方法がある。一致するたびにスヌープヒットが発生し、コヒーレンシーを維持するために修正動作が必要になることがある。詳細については例えば米国特許第５，６５２，８５９号を参照されたい。一般的に、ＰＡＱはスヌープ要求に参加する他のハードウェア構造によって満足されるデータ参照を含み、ＰＡＱがスヌープ要求に参加する必要はない。
【００２４】
ＰＡＱは以下のような他の性能改善に用いることができる。キャッシュ待ち行列１１４を、上では未処理データの取り出しに用いるものとして説明した。キャッシュ待ち行列１１４（あるいは同様な別個の記憶待ち行列）を未処理の記憶命令に用いることができる。記憶命令のミスが発生すると、記憶をキャッシュ待ち行列あるいは記憶待ち行列に残しておく代わりにＰＡＱに移動することができる。記憶命令の場合、データはＰＡＱの残りのフィールドの入力時にＰＡＱに入力されることに注意しなければならない。次に、ある行への記憶データをＰＡＱによってより低レベルのキャッシュあるいはメモリから取り出されている行データとマージすることができる。これを図１の破線で示す経路１２０および１２２（２つの経路の内１つだけが必要である）で示す。性能改善のために、ＰＡＱ内の記憶エントリの行データがフィルバッファ１０８およびオプションの低レベルキャッシュ１０２をバイパスするようにすることができる。さらに、記憶命令のためのＰＡＱ内の可観測性ビットによって従属命令の実行が可能になる場合がある。
【００２５】
ＰＡＱには以下の性能上の利点がある。まず、データを最初にキャッシュに入れることなく、ＰＡＱから直接入手可能である。第二に、各ＰＡＱエントリは宛先レジスタ情報を含むため、データをパイプラインの中間段階に注入することができ、パイプラインへの命令の入力あるいは再入力を待つことが不要になる。第三に、１つの行に対するそれぞれの個別の要求に個別のエントリが供給され、各エントリにはその行が利用可能になり次第その行の適当な部分が供給され、それによって１つの行に対する複数のミスのデータが高速に供給される。第四に、ＰＡＱは要求元の装置に結果を必要な任意の順序で供給してアウトオブオーダキャッシュ戻りを可能とし、複数のソースが処理可能な状態のデータを有する場合には調停を実行する。最後に、ＰＡＱに可観測性ビットを設けることによって、未処理の解放アクセスの実行が従属ロードアクセスのＰＡＱ内にデータが入る前に完了するようにすることができる。
【００２６】
ＰＡＱを特定のキャッシュ設計に基づいて説明したが、ＰＡＱはこの特定のキャッシュ設計には限定されない。ＰＡＱを他のキャッシュ設計およびキャッシュ階層構造に用いて同じ機能を得ることができる。ＰＡＱ内のエントリの数はシステムごとに異なるが、ある特定の実施形態では、ＰＡＱは１６から３２の未処理レジスタ目標を支援するものと考えられる。
【００２７】
以上の説明は本発明を例示するために行なったものである。以上の説明は本発明をここに開示した形態によって網羅しようとするものでもまたかかる形態に厳密に限定しようとするものでもなく、以上の原理に照らした他の改変が可能である。以上の実施形態は本発明の原理とその実際の応用に関する最良の説明を加え、それによって当業者がその考案する具体的用途に適した実施形態および各種の変更態様で本発明を最もよく活用しうるように選択および説明したものである。特許請求の範囲は従来技術によって限定されるものを除く本発明の他の代替実施形態を含むものと解すべきものである。
【００２８】
以下に本発明に実施の形態を要約する。
１．  実行パイプライン（１１２）と、
前記実行パイプラインに結合されたキャッシュ（１００）と、
前記実行パイプラインに結合された待ち行列構造（１０４）と、を有し、
前記待ち行列構造は目標レジスタへのデータのロード命令に対して、前記データが前記キャッシュにない場合、前記データおよび前記データの目標レジスタのＩＤを前記実行パイプラインに送るコンピュータシステム。
【００２９】
２．  前記待ち行列構造は複数のデータエントリを記憶するのに十分な容量を有し、前記エントリを前記実行パイプラインに任意の順序で送るように適合されている上記１記載のコンピュータシステム。
【００３０】
３．  前記待ち行列構造は１行に複数の参照を記憶するのに十分な容量を有し、前記１行をメモリから１度検索することによって前記１行の全てのエントリを記憶するように適合されている上記１記載のコンピュータシステム。
【００３１】
４．  前記待ち行列構造は可観測性ビットの記憶域を含み、それによって未処理の解放により待たされているデータが前記待ち行列構造に入る前に前記未処理の解放の実行を完了することを可能とする上記１記載のコンピュータシステム。
【００３２】
【発明の効果】
上述のように、本発明によれば、キャッシュミスペナルティのさらなる低減、特に、異常実行を伴なう複数のミスや同じ行への複数のミスに対するペナルティの低減を実現可能とするコンピュータシステムを提供できる効果がある。
【図面の簡単な説明】
【図１】本発明に一実施形態に係る未処理アクセス待ち行列を含むコンピュータシステムを示すブロック図である。
【符号の説明】
１００  主（Ｌ１）キャッシュ
１０２  低レベル（Ｌ２）キャッシュ
１０４  ＰＡＱ
１０６  システムバス
１０８  フィルバッファ
１１０  マルチプレクサ
１１２  実行パイプライン
１１４  キャッシュ待ち行列
１１６  階層構造
１１８  可観測性論理
１２０、１２２  経路
【図１】
0003800383.tif 000003