(57)【特許請求の範囲】
【請求項１】
プロセッサと、
第１の種類のトランザクション待ち行列および第２の種類のトランザクション待ち行列を有するメモリ・コントローラと、
前記メモリ・コントローラに結合されたメモリと
を含み、前記メモリ・コントローラに、
トランザクションを受け取らせる手段と、
前記トランザクションが、第１の種類のトランザクションであるか第２の種類のトランザクションであるかを判定させる手段と、
前記トランザクションが前記第１の種類のトランザクションである場合に、前記トランザクションのアドレスを、前記第２のトランザクション待ち行列に格納されている第２の種類のトランザクションのアドレスと比較させる手段と、
前記トランザクションが前記第２の種類のトランザクションである場合に、前記トランザクションのアドレスを、前記第１の種類のトランザクション待ち行列に格納されている第１の種類のトランザクションのアドレスと比較させる手段と、
前記第１の種類のトランザクションのアドレスが前記第２の種類のトランザクションのアドレスと一致しない場合に、前記トランザクションを最適な方法で処理させる手段と、
前記第１の種類のトランザクションのアドレスが前記第２の種類のトランザクションのアドレスと一致する場合、前記トランザクションを、前記トランザクションが受け取られた順序で処理させる手段と
を実行させる
トランザクションに優先順位を付けさせるためのコンピュータ・システム。
【請求項２】
前記最適な方法が、最初に前記第１および第２の種類のトランザクションのうち最適化のために優先される方のすべてを処理させる手段と、次に前記第１および第２の種類のトランザクションのうちの他方のすべてを処理させる手段とを含む、請求項１に記載のコンピュータ・システム。
【請求項３】
プロセッサと、
読取トランザクション待ち行列、書込トランザクション待ち行列、順序バッファおよび優先順位付け論理を含む、前記プロセッサに接続されたキャッシュと
を含み、前記優先順位付け論理に、
１つまたは複数のトランザクションを受け取らせる手段と、
各トランザクションの生起を前記順序バッファにログ記録させる手段と、
受け取ったトランザクションが読取トランザクションである場合に、該読取トランザクションのアドレスを、前記書込トランザクション待ち行列内の書込トランザクションのアドレスと比較させる手段と、
前記読取トランザクションの前記アドレスが、前記書込トランザクション待ち行列内に格納された書込トランザクションの前記アドレスと一致する場合に、前記読取トランザクションを前記読取トランザクション待ち行列に格納し、前記書込トランザクションと一致する前記アドレスを、前記書込トランザクション待ち行列内で衝突として識別させる手段と、
前記受け取ったトランザクションが書込トランザクションである場合に、該書込トランザクションのアドレスを、前記読取トランザクション待ち行列内の読取トランザクションのアドレスと比較させる手段と、
前記書込トランザクションの前記アドレスが、前記読取トランザクション待ち行列内の読取トランザクションの前記アドレスと一致する場合に、前記書込トランザクションを前記書込トランザクション待ち行列に格納し、読取トランザクションと一致する前記アドレスを、前記読取トランザクション待ち行列内で衝突として識別させる手段と、
衝突について各トランザクション待ち行列を検査させる手段と、
いずれかのトランザクション待ち行列に衝突が存在する場合に、衝突としてマークされたトランザクションが処理されるまで、前記順序バッファ内に記録された順序に従ってトランザクションを処理させる手段と、
トランザクション待ち行列のいずれにも衝突トランザクションが存在しない場合に、前記書込トランザクション待ち行列内の前記書込トランザクションを処理する前に、前記読取トランザクション待ち行列に存在する前記読取トランザクションを処理させる手段と
を実行させる
メモリ内の読取トランザクションおよび書込トランザクションに優先順位を付けさせるための装置。
【請求項４】
前記優先順位付け論理に、さらに、
前記読取トランザクション待ち行列が空である場合に、前記書込トランザクション待ち行列内に存在する前記書込トランザクションを処理させる手段
を含む、請求項３に記載の装置。
【請求項５】
第１の種類のトランザクションが格納される第１の種類のトランザクション待ち行列、第２の種類のトランザクションが格納される第２の種類のトランザクション待ち行列、およびトランザクションの受取順序を示す順序バッファを有するメモリを含むコンピュータ・システムにおいて、
トランザクションを受け取るステップと、
特定のトランザクションを受け取ったことを示す情報を前記順序バッファに格納するステップと、
前記トランザクションが、第１の種類のトランザクションであるか第２の種類のトランザクションであるかを判定するステップと、
前記トランザクションが前記第１の種類のトランザクションである場合に、前記トランザクションのアドレスを、前記第２の種類のトランザクション待ち行列に格納されている第２の種類のトランザクションのアドレスと比較するステップと、
前記トランザクションが前記第２の種類のトランザクションである場合に、前記トランザクションのアドレスを、前記第１の種類のトランザクション待ち行列に格納されている第１の種類のトランザクションのアドレスと比較するステップと、
どちらの比較も一致をもたらさない場合に、前記トランザクションを最適の方法で処理するステップと、
どちらかの比較が一致をもたらす場合に、前記トランザクションを、前記順序バッファに格納された順序で処理するステップと
を含む、トランザクションに優先順位を付ける方法。
【請求項６】
最適の方法で前記トランザクションを処理する前記ステップが、一方の種類のトランザクションのいずれかを処理する前に、他方の種類のトランザクションのすべてを処理するステップを含む、請求項５に記載の方法。
【請求項７】
前記読取トランザクションまたは前記書込トランザクションの処理の際に、前記順序バッファから対応する情報を除去するステップと、
前記順序バッファ内で残りの情報の隙間を詰めるステップと
をさらに含む、請求項５に記載の方法。
【請求項８】
プロセッサと、順序バッファと、書込待ち行列と、読取待ち行列とを有するコンピュータ・システムにおいて、
前記プロセッサからのトランザクションを受け取るステップと、
前記トランザクションが、読取トランザクションであるか書込トランザクションであるかを判定するステップと、
前記トランザクションの生起を前記順序バッファにログ記録するステップと、
前記トランザクションが読取トランザクションである場合に、前記読取トランザクションのアドレスを、前記書込待ち行列内の書込トランザクションのアドレスと比較するステップと、
前記読取トランザクションのアドレスが、前記書込待ち行列内の書込トランザクションのアドレスと一致する場合に、前記読取トランザクションを前記読取待ち行列に格納し、前記一致する書込トランザクションを衝突として識別するステップと、
受け取ったトランザクションが書込トランザクションである場合に、前記書込トランザクションのアドレスを、読取待ち行列内の読取トランザクションのアドレスと比較するステップと、
前記受け取った書込トランザクションの前記アドレスが、前記読取待ち行列内の読取トランザクションの前記アドレスと一致する場合に、前記書込トランザクションを前記書込待ち行列に格納し、前記一致する読取トランザクションを衝突として識別するステップと、
前記読取待ち行列または前記書込待ち行列のいずれかに衝突が存在する場合に、衝突としてマークされたトランザクションが処理されるまで、前記順序バッファに入力された順序に従ってトランザクションを処理するステップと、
前記読取待ち行列および前記書込待ち行列のいずれにも衝突トランザクションが存在しない場合に、前記書込待ち行列内の前記書込トランザクションを処理する前に、前記読取待ち行列内に存在する前記読取トランザクションを処理するステップと
を含む、トランザクションに優先順位を付ける方法。
【請求項９】
前記読取トランザクションまたは前記書込トランザクション処理の際に、前記順序バッファから対応する記録を除去するステップと、
前記順序バッファ内の残りの記録の間の隙間を詰めるステップと
をさらに含む、請求項８に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
開示される発明は、読取／書込コヒーレンスを維持しながらバス利用度を最適化することに関する。バス最適化は、できる限り多数の読み取りが連続して発生するように、書込トランザクションより読取トランザクションを優先させることによって達成される。
【０００２】
【従来の技術】
コンピュータ産業の技術が進歩するにつれて、情報が処理され、アクセスされる速度が高まる。いくつかの命令は、プロセッサによる内部動作だけを必要とし、この状況ではプロセッサ速度によってコンピュータ・システムの速度が左右される。しかし、プロセッサによって開始される他の命令は、外部トランザクションを必要とし、この外部トランザクションは、周辺装置がプロセッサと相互作用する速度によって速度が決められる。したがって、最適化は、周辺装置にトランザクションの処理を要求するバス・インターフェース上でのトランザクションの提示の前にトランザクションを処理することによって得ることができる。しかし、データ・コヒーレンスに関する問題が生じる可能性がある。特定の位置に対するデータが、継続的に更新され、読み取られる場合、この位置との間のトランザクションは、プロセッサがトランザクションを生成した順序で処理されなければならない。したがって、キャッシュ・メモリを扱う時には、キャッシュ・メモリ内の特定の位置に対する書込要求を、その後の、メモリ内の同一位置からの読取の要求の前に完了しなければならない。逆に、キャッシュ・メモリ内の特定の位置に対する読取要求は、その後の、メモリ内の同一位置に対する書込の要求の前に完了しなければならない。
【０００３】
従来技術には、少なくとも２つの方式が含まれる。一方の方式では、トランザクションの完全な順序通り（イン・オーダー）の処理が可能になる。順序通りの実施形態では、プロセッサの読取または書込のトランザクションを、プロセッサが各トランザクションを要求した順序で実行することが必要になる。この処理によって、読取／書込コヒーレンスが保証されるが、バス利用度の最適化は全く行われない。
【０００４】
もう一つの従来技術の方式では、キャッシュ・メモリに対する読取および書込のトランザクションに優先順位を付けてバス利用度を最適化することができるように、トランザクションの順序はずれ（アウト・オブ・オーダー）処理を可能にする。読取トランザクションが、未完了の書込トランザクションと衝突する場合には、読取データは、書込待ち行列項目から転送される。これによって、書込トランザクションの完了に依存せずに、読取トランザクションを実行できるようになる。しかし、これには、プロセッサ・チップまたはチップ・セットでのハードウェアおよび複雑さの望ましくない増大が必要である。
【０００５】
【発明が解決しようとする課題】
読取／書込コヒーレンスを維持しながらバス利用度を最適化する能力の進歩は、有益になるはずである。したがって、本発明の目的は、読取／書込コヒーレンスを維持しながら高められたバス利用度を提供することである。
【０００６】
【課題を解決するための手段】
本発明は、読取および書込のコヒーレンスを維持しながらバス利用度を最適化するための方法および装置を提供する。具体的に言うと、本発明は、衝突保留がない時に最適の優先順位付け機構を可能にすることによるバス利用度最適化を提供する。衝突保留が判定される時には、読取トランザクションおよび書込トランザクションは、データ・コヒーレンシを考慮して、トランザクションの年齢に従って処理される。
【０００７】
【発明の実施の形態】
以下の説明では、同様の部品に、明細書および図面を通じてそれぞれ同一の符号を付す。図面は、必ずしも原寸通りではなく、一部の図面は、明瞭さと簡潔さのために誇張した形または一般的な形で示される場合がある。
【０００８】
図１に関して、開示される発明によるコンピュータ・システムが図示されている。マイクロプロセッサ１００が図示されている。マイクロプロセッサ１００には、ＣＰＵコア１０２、Ｌ３キャッシュ・タグ１０４ａおよびＬ３キャッシュ・コントローラ１０６が含まれる。ＣＰＵコア１０２は、内部バス１０５を介してＬ３キャッシュ・コントローラ１０６に接続される。Ｌ３キャッシュ・タグ１０４ａは、第２の内部バス１０７を介してＬ３キャッシュ・コントローラ１０６に接続される。Ｌ３キャッシュ・タグ１０４ａ、Ｌ３キャッシュ・コントローラ１０６およびＬ３キャッシュ・データ・メモリ１０４ｂは、Ｌ３キャッシュ・システムを構成する。Ｌ３キャッシュ・データ・メモリ１０４ｂは、マイクロプロセッサ１００、具体的にはＬ３キャッシュ・コントローラ１０６に、外部Ｌ３バス１０８を介して接続される。
【０００９】
マイクロプロセッサ１００は、システム・バス１１２に接続される。大容量記憶装置１１４、ビデオ・コントローラ１１６、主記憶１１０および入出力装置１２０も、システム・バス１１２に接続される。ビデオ・コントローラ１１６は、モニタ１１８に接続される。大容量記憶装置１１４は、開示される実施例では、ハード・ディスク装置である。しかし、本発明の趣旨から逸脱せずに、さまざまな大容量記憶装置を使用することができる。他の大容量記憶装置の例が、テープ駆動装置とコンパクト・ディスク駆動装置である。入出力装置１２０は、開示される実施例では、キーボードまたはマウスもしくはその両方である。ビデオ・コントローラとモニタは、コンピュータ・システムの一般的な要素であり、したがって、当技術分野で周知である。
【００１０】
ここで図２を参照すると、開示される発明による、Ｌ３キャッシュ・コントローラ１０６の内部の待ち行列化および制御の図が示されている。Ｌ３キャッシュ・コントローラ１０６の待ち行列化および制御に含まれるのが、待ち行列化論理２００である。待ち行列化論理２００内には、外部Ｌ３バス１０８行きの一連のトランザクションが図示されている。トランザクションは、読取待ち行列バス２２６を介して読取待ち行列２０２に経路指定され、書込待ち行列バス２２８を介して書込待ち行列２０４に経路指定される。読取待ち行列２０２および書込待ち行列２０４と共に、順序バッファ２０６が図示されている。開示される実施例の順序バッファ２０６は、ＦＩＦＯ（先入れ先出し）バッファである。トランザクションは、外部Ｌ３バス１０８に向けられるとき、まず待ち行列化論理２００に入力され、待ち行列化論理が受け取ったトランザクションの種類が、順序バッファ２０６に格納される。順序バッファ２０６は、読取待ち行列２０２および書込待ち行列２０４に格納されたトランザクションのすべてを識別するのに十分な項目を収容するように設計された１ビット幅のバッファである。順序バッファ内の読取待ち行列項目は、「１」として示され、書込待ち行列項目は、「０」として示される。読取待ち行列２０２は、０から１５までの合計１６個の項目を有する。書込待ち行列２０４は、０から７までの合計８個の項目を有する。したがって、順序バッファ２０６は、０から２３までの合計２４個の１ビット幅の項目を有する。トランザクションは、待ち行列化論理２００に入る時に、読取トランザクションまたは書込トランザクションとして識別される。トランザクションが読取トランザクションである場合には、そのトランザクションは、読取待ち行列２０２の次のトランザクションとして格納される。トランザクションが書込トランザクションである場合には、書込待ち行列２０４に格納される。トランザクションが書込待ち行列２０４または読取待ち行列２０２にロードされる時に、順序バッファ２０６の対応するビットがセットされて、格納トランザクションの年齢が記録される。トランザクションが、読取トランザクションまたは書込トランザクションとして判定されると、実質的にそれと同時に、待ち行列化論理２００が、そのトランザクションが衝突を引き起こすかどうかを判定する。
【００１１】
衝突は、新しいトランザクションのアドレスを、反対の待ち行列のすべての有効な項目と比較することによって判定される。たとえば、読取トランザクションが外部Ｌ３バス１０８行きである場合、その読取トランザクションは、読取待ち行列２０２に格納される。しかし、その読取トランザクションを読取待ち行列２０２に格納する前に、入力読取トランザクションのアドレスが、書込待ち行列に格納された残余の有効な書込トランザクションのすべてのアドレスと比較される。アドレスが一致する場合には、衝突が発生する。待ち行列化論理２００は、書込待ち行列２０４の一致する項目内の衝突ビットをセットし、衝突があることを、Ｌ３調停論理２１６に知らせる。待ち行列化論理２００は、図３および４に関連して詳細に説明する。書込待ち行列２０４からは、信号線２０８を介して書込待ち行列要求信号が、また、信号線２１０を介して書込待ち行列衝突信号が、Ｌ３調停論理２１６に送られる。最古項目待ち行列ポインタ２３２は、順序バッファ２０６内から発し、Ｌ３調停論理２１６に対して、最古の有効なトランザクションを含む待ち行列を示す。読取待ち行列２０２から、信号線２１２を介して読取待ち行列要求信号が、また、信号線２１４を介して読取待ち行列衝突信号が、Ｌ３調停論理２１６に送られる。読取待ち行列のトランザクションは、信号線２２２を介してマルチプレクサ２２０に送られ、書込待ち行列のトランザクションは、信号線２２４を介してマルチプレクサ２２０に送られる。マルチプレクサ２２０は、Ｌ３調停論理２１６からの出力である信号線２１８によって制御される。Ｌ３調停論理は、待ち行列に残っているどのトランザクションを次に処理し、外部Ｌ３バス１０８に送るかを決定する。開示される実施例では、衝突が存在しない場合に、読取待ち行列２０２が優先権を有する。衝突が存在しない場合、読取待ち行列２０２に格納された読取トランザクションが、書込待ち行列２０４に格納されたどの書込トランザクションの処理よりも前に処理される。しかし、衝突が存在する場合には、読取待ち行列２０２に格納された読取トランザクションと書込待ち行列２０４に格納された書込トランザクションが、順序バッファ２０６内の項目に従って処理される。他の調停方式も可能であり、状況によってはそちらの方が好ましくなる可能性がある。さらに、広範囲の調停機構を、本発明の範囲および趣旨から逸脱せずに実施することができる。
【００１２】
ここで図３および４を参照すると、開示される発明によるキャッシュ・コントローラの待ち行列化論理の詳細な図が示されている。外部Ｌ３バス行きのトランザクションは、読取待ち行列バス２２６または書込待ち行列バス２２８のいずれかを通過する。読取トランザクションは、読取待ち行列２０２に入る前にレジスタ３００に登録される。待ち行列化論理２００は、レジスタ３００のトランザクションのアドレスが、書込待ち行列２０４に格納された有効な書込トランザクションのアドレスと同等であるかどうかを判定する。レジスタ３００の読取トランザクションのアドレスは、書込待ち行列２０４との比較のためにバス３０４を介して送られる。書込待ち行列２０４は、０乃至７個のトランザクションを含む。これらのトランザクションは、項目０  ３８２ないし項目Ｍ３６０によって示される。項目Ｍ３６０および項目０  ３８２に示すように、各項目は同一の構造である。比較器３５４が、書込待ち行列２０４内に存在する。レジスタ３００の読取トランザクションのアドレスが、比較器３５４に送られる。比較器をイネーブルするために、項目有効ビット３６４が、ハイに接続された１ビット３５２と比較される。比較器３５４は、レジスタ３００のトランザクションのアドレスを項目Ｍ３６０のアドレス３６２と比較する。その出力は、その項目の衝突インジケータ３６８として登録される。衝突インジケータ３６８の出力は、信号線３７０を介してＯＲゲート３７２に送られる。書込待ち行列２０４のすべての衝突出力が、ＯＲゲート３７２を介して論理和をとられる。ＯＲゲート３７２の出力は、信号線２１０の書込待ち行列衝突を示す信号として送られる。これと同一の処理が、書込待ち行列２０４のすべての項目について行われる。
【００１３】
レジスタ３００の読取トランザクションのアドレスは、バス３０４を介して比較器３７８に渡される。やはり、比較器の１ビット入力３７６は、ハイに結合されて、項目０  ３８２の有効ビット３９４と比較される。項目０  ３８２は、アドレス３８４を有する。アドレス３８４は、バス３８０を介して比較器３７８に送られる。有効ビット３９４は、信号線３９２を介して比較器３７８に送られる。比較器は、読取待ち行列２０２行きのレジスタ３００のトランザクションのアドレスと、項目０  ３８２のアドレス３８４を、有効ビット３９４と１ビット入力３７６との比較と共に比較する。この比較の出力は、衝突ビット３９６に送られる。その出力は、信号線３９７を介してＯＲゲート３７２に送られる。すべての衝突ビットのすべての出力が、ＯＲゲート３７２に送られ、その出力が、書込待ち行列衝突を示す信号線２１０を介してＬ３調停論理２１６に送られる。書込待ち行列２０４の項目のすべての有効ビットが、ＯＲゲート３７４で互いに論理和をとられ、その出力が、書込待ち行列要求を示す信号線２０８を介してＬ３調停論理２１６に送られる。書込待ち行列２０４に格納されているトランザクションのアドレスは、バス３８６および３８８に渡され、バス２２４を介してマルチプレクサ２２０に送られる。
【００１４】
外部Ｌ３バス行きのトランザクションが、書込トランザクションであると判定された場合、そのトランザクションは、レジスタ３０２に登録される。書込トランザクション・レジスタ３０２にあるアドレスは、バス３０６を介して送られ、読取待ち行列２０２に格納されたすべてのトランザクションと比較される。読取待ち行列２０２は、開示される実施例では項目０  ３１０ないし項目Ｎ３０８を有する。読取待ち行列２０２は１６個の項目、書込待ち行列は８個の項目を含む。レジスタ３０２の書込トランザクションのアドレスは、バス３０６を介して比較器３４０に送られる。項目Ｎ３０８には、アドレス３１２が含まれる。このアドレス３１２は、バス３１６を介して比較器３４０に送られる。また、このアドレス３１２は、バス３５０を介してマルチプレクサ３４８に送られ、その後、項目Ｎ３０８が読取待ち行列２０２内で最古の項目である時には、バス２２２から最終的にマルチプレクサ２２０に送られる。項目Ｎ３０８には、有効ビット３１８が含まれる。有効ビット３１８は、信号線３１４を介して比較器３４０に送られる。比較器３４０の出力は、判定され、衝突ビット３４１に送られる。衝突ビット３４１の出力は、信号線３２２を介してＯＲゲート３２４に送られる。有効ビット３１８は、信号線３２０を介して第２のＯＲゲート３２６に転送される。レジスタ３０２の書込トランザクションのアドレスは、読取待ち行列２０２内にあるすべての項目と比較される。たとえば、項目０  ３１０との比較を次に示す。バス３０６を介して送られたアドレスは、比較器３４６に入力される。比較器３４６をイネーブルするために、項目の有効ビット３３４が、「１」３４４と比較される。項目０  ３１０は、アドレス３２８を有する。そのアドレス３２８は、バス３３０を介して比較器３４６に送られて、バス３０６を介して送られたアドレスと比較される。有効ビット３３４は、信号線３３２を介して比較器３４６に送られる。比較器の結果が、衝突ビット３４７への入力をもたらす。衝突ビット３４７は、信号線３３８を介してＯＲゲート３２４に送られる。ＯＲゲート３２４は、読取待ち行列２０２の各項目の衝突ビットを受け入れ、その出力は、Ｌ３調停論理２１６に送られ、読取待ち行列衝突を示す。有効ビット３１８は信号線３２０を介して、有効ビット３３４は信号線３３６を介して、それぞれＯＲゲート３２６に送られる。このＯＲゲート３２６の出力は、信号線２１２を介してＬ３調停論理２１６に送られ、読取待ち行列要求を示す。
【００１５】
次に、図５を参照すると、順序バッファの処理が示されている。順序バッファ２０６は、読取待ち行列２０２または書込待ち行列２０４に入力されるトランザクションの受取をログ記録するバッファである。レジスタ３００の読取トランザクションのそれぞれは、ハイのビットすなわち「１」を用いて表され、書込トランザクションのそれぞれは、ローのビットすなわち「０」を用いて表される。順序バッファ２０６は、読取待ち行列２０２および書込待ち行列２０４に格納されるすべてのトランザクションを表す項目を収容するように設計される。Ｌ３キャッシュ・コントローラ１０６が処理されるトランザクションを表すビットを除去する処理について説明する。たとえば、図５の一番左の列４０４の最下部から始めると、順序バッファ２０６には、００１１００１０１…０というビット列が含まれる。Ｌ３キャッシュ・コントローラ１０６が、読取トランザクションを処理する４００。順序バッファ２０６の最も下の（最も古い）「１」が、順序バッファ２０６から除去される。これは、中央の列４０６に示されている。最も下の「１」が除去され、その代わりに破線が存在する。次に、順序バッファ２０６の残りの項目の隙間が詰められ、次のトランザクションの出現をバッファの最上部に配置できるようにする。これは右の列４０８に示されている。図からわかるように、最下部の２つの「０」インジケータは同一のままである。しかし、除去された最初の「１」の上の残りの桁は、圧縮されており、したがって、項目の間に空の空間はない。このようにして、各トランザクションが処理される際に、当該トランザクションを示す最も下の項目（読取トランザクションは「１」、書込トランザクションは「０」）が除去され、順序バッファの残りの項目の隙間が詰められる。
【００１６】
ここで図６を参照すると、開示される発明による読取待ち行列項目および書込待ち行列項目の信号記述が示されている。読取トランザクション５００には、アドレス・フィールド５０２、有効ビット５０４および衝突保留ビット５０６が含まれる。アドレス・フィールド５０２は、１８ビット幅である。したがって、読取トランザクション５００は、２０ビット幅である。書込トランザクション５２０は、アドレス・フィールド５２２、有効ビット５２４、衝突保留ビット５２６、高優先順位ビット５３０およびデータ・フィールド５２８からなる。アドレス・フィールド５２２は、やはり１８ビット幅である。この書込トランザクション５２０に関連するデータ・フィールド５２８は、３２バイト幅である。
【００１７】
ここで図７を参照すると、開示される発明による調停処理の流れ図が示されている。この処理は、ステップ５７０から始まる。ステップ５７２で、トランザクションを受け取る。そのトランザクションが別のトランザクションと衝突するかどうかを、ステップ５７４で判定する。衝突がない場合、ステップ５７６で、待ち行列化されたトランザクションを、最適な方法で処理する。衝突がある場合には、ステップ５７８で、待ち行列化されたトランザクションを、順序バッファ２０６に格納された受け取り順序に従って処理する。トランザクションを処理した後に、ステップ５８０で、まだトランザクションが存在するかどうかを判定する。まだトランザクションが存在する場合、処理はステップ５７４に戻り、衝突状態がまだ存在するかどうかを判定する。トランザクションが存在しない場合、処理はステップ５８２で終了する。開示される実施例では、この処理は、Ｌ３キャッシュ・コントローラ１０６の読取トランザクションおよび書込トランザクションを介して実施される。しかし、広範囲のハードウェア・システムで、本発明の趣旨からそれずに、開示される発明を使用することができる。
【００１８】
次に、図８に、開示される発明による、待ち行列項目のローディングの処理が示されている。この処理は、ステップ６００の「開始」から始まる。ステップ６０２で、トランザクションを受け取る。次に、ステップ６０４で、トランザクションが読取トランザクションと書込トランザクションのどちらであるかを判定する。ステップ６０６で、受け取ったトランザクションの種類を、順序バッファにログ記録する。ステップ６０８の判定で、トランザクションが読取トランザクションである場合には、ステップ６１０で、読取トランザクションのアドレスを、すべての有効な書込待ち行列項目アドレスと比較する。ステップ６１２で、アドレスの一致が存在しない場合には、ステップ６３２で、読取トランザクションを読取待ち行列に格納し、その後、ステップ６２６で処理を終了する。しかし、ステップ６１２でアドレスの一致が存在する場合には、ステップ６１４で、読取トランザクションを読取待ち行列に格納し、ステップ６１６で、一致する有効な書込トランザクションの衝突ビットをセットして、それが読取待ち行列のトランザクションと衝突していることをマークする。その後、ステップ６２６で処理が終了する。
【００１９】
ステップ６０８で、トランザクションが書き込みトランザクションであると判定される場合、ステップ６１８で、書込トランザクションのアドレスを、すべての有効な読取待ち行列項目のアドレスと比較する。ステップ６２０で、一致が存在する場合には、ステップ６２２で、書込トランザクションを書込待ち行列に格納し、ステップ６２４で、一致する有効な読取トランザクションの衝突ビットをセットして、衝突が発生していることを示す。この処理は、その後、ステップ６２６で終了する。ステップ６２０で一致が存在しない場合には、ステップ６３０で書込トランザクションを書込待ち行列に格納し、処理はステップ６２６で終了する。
【００２０】
ここで図９を参照すると、開示される発明による調停処理の流れ図が示されている。この処理は、ステップ７００の「開始」から始まる。次に、ステップ７０２で、衝突が存在するかどうかを判定する。衝突がある場合には、ステップ７０４で、順序バッファを使用して優先順位を判定して、次のトランザクションの処理を実行する。順序バッファによる優先順位の決定に基づいてトランザクションを処理した後に、ステップ７０６で、衝突がまだ保留中であるかどうかを判定する。衝突がまだ保留中である場合には、この処理はステップ７０４に戻り、順序バッファを使用して優先順位を判定して次のトランザクションを処理する。衝突が保留中でなくなった場合には、処理はステップ７０８に進む。ステップ７０２で衝突ビットがセットされていなかった場合にも、処理はステップ７０８に進む。ステップ７０８で、読取待ち行列が空であるかどうかを判定する。読取待ち行列が空でない場合には、ステップ７１０で次の読取トランザクションを処理した後に、ステップ７０２に戻って、保留中の衝突があるかどうかを判定する。読取待ち行列が空の場合には、処理はステップ７１２に進む。ステップ７１２の判定で、書込待ち行列が空の場合には、この処理はステップ７１６で終了する。しかし、書込待ち行列が空でない場合には、ステップ７１４で次の書込トランザクションを処理した後に、この処理はステップ７０２に戻る。その後、衝突ビットがセットされているかどうかを判定した後に、次のトランザクションを処理する。
【００２１】
この処理では、衝突が保留中でない場合に、書込待ち行列のトランザクションの前に、読取待ち行列のすべての読取トランザクションを処理することができる。衝突が存在するならば、読取待ち行列２０２および書込待ち行列２０４は、有効な項目がロードされた順序を示す順序バッファ２０６の項目に従って処理される。しかし、読取待ち行列または書込待ち行列の、衝突を含む項目が処理された後は、衝突ビットがリセットされ、書込トランザクションの前に読取トランザクションを処理することに基づく優先順位付けが再開される。しかし、書込トランザクションより優先して読取トランザクションを処理すること以外の最適化方式を、開示される発明に従って使用することができる。その代わりに、衝突がないことの検出に応答して処理するための最適の方法には、１）最後の動作が書込動作であった場合には読取動作より書込動作を優先して実行し、最後の動作が読取動作であった場合には書込動作より読取動作を優先して実行すること、２）最後にアクセスされたページに対応するメモリ・ページにアクセスするメモリ・アクセス動作を優先して実行すること、３）読取動作の前に書込動作を実行すること、または４）ラウンド・ロビン・シーケンスで読取動作と書込動作を実行することが含まれる。開示される発明では、本明細書に開示された順序バッファを実施することによって、衝突が保留中の時にデータ・コヒーレンシを維持することができる。しかし、衝突が保留中でない時には、どのような最適化方法でも使用することができる。本明細書に開示された読取優先の最適化方式は、１つの実施形態であるが、本発明の趣旨からそれずに、さまざまな最適化方式を使用することができる。
【００２２】
前述の本発明の開示および説明は、その図示および例示であり、さまざまな寸法、形状、素材および構成要素を、本発明の主旨から逸脱せずに作ることができる。
【００２３】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００２４】
（１）プロセッサと、
第１の種類のトランザクション待ち行列および第２の種類のトランザクション待ち行列を有するメモリ・コントローラと
前記メモリ・コントローラに結合されたメモリと
を含み、前記メモリ・コントローラが、
トランザクションを受け取るステップと、
前記トランザクションが、第１の種類のトランザクションであるか第２の種類のトランザクションであるかを判定するステップと、
前記トランザクションが前記第１の種類のトランザクションである場合に、前記トランザクションを、前記第２の種類のトランザクション待ち行列に格納されている第２の種類のトランザクションと比較するステップと、
前記トランザクションが前記第２の種類のトランザクションである場合に、前記トランザクションを、前記第１の種類のトランザクション待ち行列に格納されている第１の種類のトランザクションと比較するステップと、
第１の種類のトランザクションが第２の種類のトランザクションと一致しない場合に、前記トランザクションを最適な方法で処理するステップと、
第１の種類のトランザクションが第２の種類のトランザクションと一致する場合に、前記トランザクションを、前記トランザクションが受け取られた順序で処理するステップと
を実行する
トランザクションに優先順位を付けるためのコンピュータ・システム。
（２）前記最適の方法が、最初に前記第１および第２の種類のトランザクションのうちの早い方のすべてを処理するステップと、次に前記第１および第２の種類のトランザクションのうちの遅い方のすべてを処理するステップとを含む、上記（１）に記載のコンピュータ・システム。
（３）プロセッサと、
読取トランザクション待ち行列、書込トランザクション待ち行列、順序バッファおよび優先順位付け論理を含む、前記プロセッサに接続されたキャッシュと
を含み、前記優先順位付け論理が、
１つまたは複数のトランザクションを受け取るステップと、
各トランザクションの生起を前記順序バッファにログ記録するステップと、
受け取ったトランザクションが読取トランザクションである場合に、該読取トランザクションのアドレスを、前記書込トランザクション待ち行列内の書込トランザクションのアドレスと比較するステップと、
前記読取トランザクションの前記アドレスが、前記書込トランザクション待ち行列内に格納された書込トランザクションの前記アドレスと一致する場合に、前記読取トランザクションを前記読取トランザクション待ち行列に格納し、前記書込トランザクションと一致する前記アドレスを、前記書込トランザクション待ち行列内で衝突として識別するステップと、
前記受け取ったトランザクションが書込トランザクションである場合に、該書込トランザクションのアドレスを、前記読取トランザクション待ち行列内の読取トランザクションのアドレスと比較するステップと、
前記書込トランザクションの前記アドレスが、前記読取トランザクション待ち行列内の読取トランザクションの前記アドレスと一致する場合に、前記書込トランザクションを前記書込トランザクション待ち行列に格納し、読取トランザクションと一致する前記アドレスを、前記読取トランザクション待ち行列内で衝突として識別するステップと、
衝突について各トランザクション待ち行列を検査するステップと、
いずれかのトランザクション待ち行列に衝突が存在する場合に、衝突としてマークされたトランザクションが処理されるまで、前記順序バッファ内に記録された順序に従ってトランザクションを処理するステップと、
トランザクション待ち行列のいずれにも衝突トランザクションが存在しない場合に、前記書込トランザクション待ち行列内の前記書込トランザクションを処理する前に、前記読取トランザクション待ち行列に存在する前記読取トランザクションを処理するステップと
を実行する
メモリ内の読取トランザクションおよび書込トランザクションに優先順位を付けるための装置。
（４）前記優先順位付け論理が、さらに、
前記読取トランザクション待ち行列が空である場合に、前記書込トランザクション待ち行列内に存在する前記書込トランザクションを処理するステップ
を含む、上記（３）に記載の装置。
（５）第１の種類のトランザクションが格納される第１の種類のトランザクション待ち行列、第２の種類のトランザクションが格納される第２の種類のトランザクション待ち行列、およびトランザクションの受取順序を示す順序バッファを有するメモリを含むコンピュータ・システムにおいて、
トランザクションを受け取るステップと、
特定のトランザクションを受け取ったことを示す情報を前記順序バッファに格納するステップと、
前記トランザクションが、第１の種類のトランザクションであるか第２の種類のトランザクションであるかを判定するステップと、
前記トランザクションが前記第１の種類のトランザクションである場合に、前記トランザクションを、前記第２の種類のトランザクション待ち行列に格納されている第２の種類のトランザクションと比較するステップと、
前記トランザクションが前記第２の種類のトランザクションである場合に、前記トランザクションを、前記第１の種類のトランザクション待ち行列に格納されている第１の種類のトランザクションと比較するステップと、
どちらの比較も一致をもたらさない場合に、前記トランザクションを最適の方法で処理するステップと、
どちらかの比較が一致をもたらす場合に、前記トランザクションを、前記順序バッファに格納された順序で処理するステップと
を含む、トランザクションに優先順位を付ける方法。
（６）各トランザクションが、アドレスを含み、前記第１の種類のトランザクションを第２の種類のトランザクションと比較する前記ステップが、前記第１の種類のトランザクションの前記アドレスを、前記第２の種類のトランザクションの前記アドレスと比較するステップを含む、上記（５）に記載の方法。
（７）各トランザクションが、アドレスを含み、前記第２の種類のトランザクションを第１の種類のトランザクションと比較する前記ステップが、前記第２の種類のトランザクションの前記アドレスを、前記第１の種類のトランザクションの前記アドレスと比較するステップを含む、上記（５）に記載の方法。
（８）最適の方法で前記トランザクションを処理する前記ステップが、一方の種類のトランザクションのいずれかを処理する前に、他方の種類のトランザクションのすべてを処理するステップを含む、上記（５）に記載の方法。
（９）前記読取トランザクションまたは前記書込トランザクションの処理の際に、前記順序バッファから対応する情報を除去するステップと、
前記順序バッファ内で残りの情報の隙間を詰めるステップと
をさらに含む、上記（５）に記載の方法。
（１０）プロセッサと、順序バッファと、書込待ち行列と、読取待ち行列とを有するコンピュータ・システムにおいて、
前記プロセッサからのトランザクションを受け取るステップと、
前記トランザクションが、読取トランザクションであるか書込トランザクションであるかを判定するステップと、
前記トランザクションの生起を前記順序バッファにログ記録するステップと、
前記トランザクションが読取トランザクションである場合に、前記読取トランザクションの少なくとも一部を、前記書込待ち行列内の書込トランザクションの少なくとも一部と比較するステップと、
前記読取トランザクションの前記一部が、前記書込待ち行列内の書込トランザクションの前記一部と一致する場合に、前記読取トランザクションを前記読取待ち行列に格納し、前記一致する書込トランザクションを衝突として識別するステップと、
受け取ったトランザクションが書込トランザクションである場合に、前記書込トランザクションの少なくとも一部を、読取待ち行列内の読取トランザクションの少なくとも一部と比較するステップと、
前記受け取った書込トランザクションの前記一部が、前記読取待ち行列内の読取トランザクションの前記一部と一致する場合に、前記書込トランザクションを前記書込待ち行列に格納し、前記一致する読取トランザクションを衝突として識別するステップと、
前記読取待ち行列または前記書込待ち行列のいずれかに衝突が存在する場合に、衝突としてマークされたトランザクションが処理されるまで、前記順序バッファに入力された順序に従ってトランザクションを処理するステップと、
前記読取待ち行列および前記書込待ち行列のいずれにも衝突トランザクションが存在しない場合に、前記書込待ち行列内の前記書込トランザクションを処理する前に、前記読取待ち行列内に存在する前記読取トランザクションを処理するステップと
を含む、トランザクションに優先順位を付ける方法。
（１１）前記読取トランザクションまたは前記書込トランザクションの処理の際に、前記順序バッファから対応する記録を除去するステップと、
前記順序バッファ内の残りの記録の間の隙間を詰めるステップと
をさらに含む、上記（１０）に記載の方法。
【図面の簡単な説明】
【図１】開示される発明によるコンピュータ・システムのブロック図である。
【図２】開示される発明による、Ｌ３キャッシュ外部バスのための待ち行列化と制御のブロック図である。
【図３】開示される発明による比較論理を含む、Ｌ３キャッシュ外部バスのための待ち行列化の詳細なブロック図である。
【図４】開示される発明による比較論理を含む、Ｌ３キャッシュ外部バスのための待ち行列化の詳細なブロック図である。
【図５】開示される発明による順序バッファの図である。
【図６】読取トランザクションおよび書込トランザクションの待ち行列項目のビット定義を示す図である。
【図７】開示される発明による待ち行列の間の調停の流れ図である。
【図８】開示される発明による待ち行列項目のローディングの流れ図である。
【図９】開示される発明による調停処理の流れ図である。
【符号の説明】
１０６  Ｌ３キャッシュ・コントローラ
１０８  外部Ｌ３バス
２００  待ち行列化論理
２０２  読取待ち行列
２０４  書込待ち行列
２０６  順序バッファ
２０８  信号線
２１０  信号線
２１２  信号線
２１４  信号線
２１６  Ｌ３調停論理
２１８  信号線
２２０  マルチプレクサ
２２２  バス、信号線
２２４  バス、信号線
２２６  読取待ち行列バス
２２８  書込待ち行列バス
２３２  最古項目待ち行列ポインタ
【図１】
0003644588.tif 000002
【図２】
0003644588.tif 000003
【図３】
0003644588.tif 000004
【図４】
0003644588.tif 000005
【図５】
0003644588.tif 000006
【図６】
0003644588.tif 000007
【図７】
0003644588.tif 000008
【図８】
0003644588.tif 000009
【図９】
0003644588.tif 000010