データキャッシュとメインメモリ間の一貫性の保証
プロセッサコア、複数のスレッドの各々によってアクセス可能なデータを記憶するキャッシュメモリ、複数のスレッドによってアクセス可能なデータを記憶するメインメモリ、非一貫性検出モジュール、及びメモリアービターを含み、複数のスレッドをサポートするマルチスレッドプロセッサにおいてメモリアクセスを制御するための装置を提供し、非一貫性検出モジュールは、プロセッサコアとメモリアービターの間に接続され、メモリアービターは、非一貫性検出モジュールとメインメモリの間に接続され、キャッシュメモリからメモリアービターに送信された読取及び書込要求に対する各スレッドのための個別の要求待ち行列が存在し、使用においては、非一貫性検出モジュールは、キャッシュメモリからメインメモリに送信された各書込要求に対するメモリアドレスの指示を書込アドレスメモリに記憶し、更に、キャッシュメモリから送信された各次の読取要求のアドレスを書込アドレスメモリ内の指示と比較し、次の読取要求のアドレスが指示に適合した場合に、読取要求に対応する障壁を適合指示が属するスレッドの要求待ち行列内に挿入し、メモリアービターは、対応する障壁がメモリアービターによって受信されるまで読取要求がメモリバスにアクセスしないように阻止する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、マルチスレッドプロセッサに関し、特に、マルチスレッドプロセッサにおける複数のスレッドによってアクセスされるキャッシャメモリとメインメモリ間のデータ非一貫性の問題に関する。
【背景技術】
【0002】
マルチスレッドプロセッサは、複数の異なる命令シーケンス(又はスレッド)を同時に処理することができる。スレッドの実行中に、データ及び命令は、メモリからアクセスされなくてはならない。従って、異なるスレッドは、メモリ及び時にはメモリの同じ部分に同時にアクセスする必要がある場合がある。従って、メモリアクセスに対してスレッド間に何らかのアービトレーションが必要である。
【0003】
マルチスレッドプロセッサは、典型的には、図1に示すように、最も一般的にアクセスされるデータ及び命令を収容する命令キャッシュ及びデータキャッシュを有する。要求されるデータ又は命令がキャッシュで見つからなかった場合、メモリバス上でのメモリへのアクセスを要求しなくてはならない。メモリへのアクセスは、スレッドが互いに衝突しないように制御しなくてはならない。この理由のために、命令及びデータキャッシュからの異なるスレッドからのメモリアクセスの各々は、メモリアービターモジュールまでのそれら独自の専用データ経路を有する。
【0004】
図1は、従来技術によるマルチスレッドプロセッサのメモリアクセスシステムの概略図である。プロセッサコア10で実行されるスレッドは、データ及び命令キャッシュ11、12からデータ及び命令を要求することができる。命令及びデータキャッシュの各々は、それらに関連付けられたメモリ管理ユニットを有する。要求されたデータ又は命令がキャッシュの1つになかった場合、要求は、メモリバスに通される。異なるスレッドからの要求の間を仲裁するために、要求は、最初にそのスレッドに対する要求を順序付けるスレッドアービター13、14を通して、かつ次にメモリバスへのアクセスを制御するメモリアービター15を通して経路指定される。
【0005】
メインメモリ内では、データは、典型的には、キャッシュラインと呼ばれる固定数のビットの単位で記憶され、かつアクセス可能である。従って、メモリからメモリアドレスを読み取るために、そのアドレスを収容するキャッシュライン全体をフェッチしなくてはならない。キャッシュラインの2つのタイプが存在する。一方のタイプは、特定のスレッドに対するデータを記憶するのみであるローカルキャッシュラインである。他方は、異なるスレッドによってアクセス可能なデータを記憶するグローバルキャッシュラインである。データピースが、グローバル又はローカルキャッシュラインに記憶されるか否かは、その線形アドレスに依存する。本発明は、スレッド間で共有されるメモリリソース、すなわち、グローバルキャッシュラインに関するものである。
【0006】
グローバルキャッシュラインは、キャッシュライン内の異なるワード位置に異なるスレッドによって入力されたソフトウエアローカル変数の値を記憶することができると考えられる。スレッドTxがキャッシュラインからそのローカル変数を読み取った時、その最後に書かれた値を取り戻すことが予想される。しかし、他のスレッドによる同じキャッシュライン内のそれらのローカル変数へのアクセスがスレッドTxに古い間違った値を読み取らせるという状況が、書込スルーデータキャッシュを使用した時に起こる可能性がある。これが起こった時、Txは、「データが非一貫性」になったと呼ばれる。
【0007】
図2a及び2bの各々は、スレッドT0上でデータ非一貫性を起こす異なるスレッドによるアクセスの例示的なシーケンスを示している。
【0008】
図2aを参照すると、T0は、書込要求により、最初にそのローカル変数Aにアクセスする。次に、T1は、読取要求により、そのローカル変数Bにアクセスする。A及びBの物理アドレスは、これらが同じグローバルデータキャッシュライン内でキャッシュに入れられるようなものである。最初にA及びBの両方はキャッシュにはない。
【0009】
読取要求は、典型的には、書込要求よりはメモリバスに到達するための時間がかからない。この場合、T1読取は、T0書込の前にメモリに到達する。この結果、キャッシュラインの古い値が、データキャッシュに記憶される。T0書込要求は、データキャッシュではなく、メモリバスにのみ書き込む。従って、データキャッシュからのキャッシュラインの次の読取は、T1読取の結果としてデータキャッシュに記憶されている古い値をフェッチすることになる。
【0010】
図2bを参照すると、ここでもまた、A及びBの両方が同じキャッシュラインにあり、最初はデータキャッシュにはない。T1は、最初に、読取要求によってメモリバスからBにアクセスする。Bがフェッチされる前に、すなわち、読取要求がデータキャッシュを離れた時間とBを収容するキャッシュラインがデータキャッシュに記憶された時間との間に、Aに対する書込要求がT0からメモリバスに出される。ここでもまた、T0からの書込は、データキャッシュに書き込まれず、従って、データキャッシュは、次の読取要求によってアクセスされることになるキャッシュラインの古いバージョンを保持する。
【発明の概要】
【発明が解決しようとする課題】
【0011】
図から分るように、複数のスレッドがメモリバスからグローバルキャッシュメモリにアクセスした時、データ非一貫性が、特に、書込スルーキャッシュを発生させる可能性がある。本発明は、非一貫性の障害を検出することにより、かつ読取又は書込命令がそれを行うことが安全である時にだけメモリバスから出されることを保証する機構を使用することにより、この問題に対処することを目的とする。
【課題を解決するための手段】
【0012】
本発明は、添付の独立請求項に定められている。好ましい特徴は、従属請求項に定められている。
【0013】
ここで、本発明の実施例を添付の図面に関連して以下に説明する。
【図面の簡単な説明】
【0014】
【図1】従来のマルチスレッドプロセッサコアのメモリアクセスシステムを示す図である。
【図2a】キャッシュ非一貫性をもたらすメモリアクセスのシーケンスを示す図である。
【図2b】キャッシュ非一貫性をもたらすメモリアクセスのシーケンスを示す図である。
【図3】本発明によるシステムを示す概略図である。
【図4】本発明による例示的なグローバル書込アドレスメモリの作動を示す図である。
【図5】図3のシステムで使用される非一貫性検出モジュールを示す図である。
【図6】図3のシステムで使用されるメモリアービターを示す図である。
【図7】アービターでの順序強制を示す図である。
【発明を実施するための形態】
【0015】
図2a及び2bに示すように、データ非一貫性は、異なる状況から生じる可能性があり、これは、個別に扱うことができる。図2aで示す非一貫性は、第1の機構を使用して防ぐことができ、図2bで示す非一貫性は、第2の機構を使用して防ぐことができる。
【0016】
図3は、本発明の第1の態様によるシステムの概略図である。図3は、図2aに関して説明した状況から起こる可能性があるデータ非一貫性を防ぐメモリバスからデータにアクセスするためのシステムを示している。本発明は、データ非一貫性、及び従ってデータへのアクセスに関するものであるから、メモリバスからの命令フェッチのための経路は、分かり易いように省略する。
【0017】
システムは、プロセッサコアに接続したデータキャッシュメモリ管理ユニット30、メモリ管理ユニットに接続したスレッドアービター31、32、及びスレッドアービターとメモリバス間に接続したメモリアービター33を含む。
【0018】
データキャッシュメモリ管理ユニット内に、データキャッシュそれ自体34及びアドレス変換などのための関連のメモリ管理機能、並びに非一貫性検出モジュールがある。
【0019】
図1に示すシステムのように、図2のシステムでは、プロセッサコアで実行されるスレッドが読取又は書込要求を出した時に、この要求は、データキャッシュMMU30に経路指定される。読取要求では、データがデータキャッシュ34にある場合、これは、即座にフェッチされて使用される。それがデータキャッシュにない場合、メモリバス上のメモリにアクセスしなくてはならない。書込スルーキャッシュでの書込要求では、書込要求は、常に、メモリバスにアクセスする。データキャッシュに関連付けられたメモリ管理ユニット(MMU)機能は、プロセッサで実行されるプログラムによって使用される仮想メモリアドレスをメモリバス上の物理メモリアドレスに変換することになる。
【0020】
本発明の1つの態様では、非一貫性検出モジュール35が、グローバル読取要求及びグローバル書込要求から生じる非一貫性に対処するために提供される。本明細書で使用される「グローバル書込要求」及び「グローバル読取要求」という語は、複数のスレッドによって共有されるメモリの一部分への要求を意味する。データキャッシュ34からのグローバル読取及び書込要求は、メモリアービター33及び次にメモリバスに到達する前に、最初に、非一貫性検出モジュール35を通過しなくてはならない。非一貫性検出モジュールは、図5に更に詳しく示されている。
【0021】
非一貫性検出モジュールは、3つの機能を有する。1つは、以前のグローバル書込要求の物理アドレスの記録を維持することである。別のものは、あらゆる着信グローバル読取のアドレスを以前の書込要求の記録と比較し、同じグローバルキャッシュラインへの過去の書込があるかを判断することである。最後は、メモリアービター33が非一貫性検出モジュール35によって意図されるようなメモリバスに要求を出すための順序を強制することができるように、比較情報を使用して「順序強制サイドバンド」を各要求に追加する(又は、個別の「障壁要求」を挿入する)ことである。この機構は、性能劣化を起こすと考えられるメモリアービターの前の様々なモジュールを通るデータフローの停止又は失速を生じない。
【0022】
全ての以前のグローバルキャッシュ書込の個々の物理アドレスの記録を維持することは、実施には実際的でないメモリの無限量を必要とする。代替としては、グローバル書込要求の個々のアドレスを代わりにアドレスの範囲に圧縮することである。この実施形態では、非一貫性検出モジュールは、各スレッドに対する「グローバル書込アドレスメモリ(GWAM)」を含む。各GWAMは、少数のデータ記憶スロットから構成され、各々は、重なっていないアドレス範囲を記憶する。
【0023】
図4は、本発明による例示的なGWAMがどのように作動するかを示している。図4aは、4つのメモリスロットを有するGWAMを示している。メモリスロットは、最初は空である。各メモリスロットは、4つのフィールド、すなわち、有効フラグフィールド、32ビットバイトアドレスフィールド(TAG)、上位アドレス範囲サイズマスク(MU)、及び下位アドレス範囲サイズビットマスク(ML)を有する。
【0024】
有効フラグは、記録された書込アドレスがメモリスロット内にあるかを単純に指示する。TAGフィールドは、スロットによって網羅されるメモリアドレスの範囲内のアドレスを指示する。
【0025】
MU及びMLフィールドは、スロットによって網羅されるメモリアドレス範囲を定義する。網羅されるアドレス範囲に対して、下位アドレス=TAG &&(MU & ML)であり、ここで、&&は、ビットAND演算を表し、&は、ベクトル連結を表している。上位アドレス=TAG‖!(MU & ML)であり、ここで、‖は、ビットOR演算を表している。例えば、16進表記を使用して、TAG = 0xAAAAAA34に対して、ML = 0xFFFF00、MU = 0xFF、アドレス範囲=0xAAAAAA00から0xAAAAAAFFである。
【0026】
第1の書込アドレスが記録された時、これは、GWAMのメモリスロットに割り当てられる。これは、図4bに示されている。スロットの全てがこの前に空であるので、データを圧縮する必要はない。この場合は0xB1000000である書込アドレスは、最小アドレス範囲で第1のスロットに記憶される。
【0027】
第2の書込アドレス0xA0000000がGWAMに記憶される時、これは、ここでもまた最小範囲により、第2のスロットに記憶される。これは、図4cに示されている。
【0028】
別のスロットのMUフィールドによって定義されたアドレス範囲に収まることができる第3の書込アドレスが出された時、これは、そのスロットに配置され、MLフィールドが、新しいアドレスを入れるために変更される。図4dはこれを示している。図4dでは、新しい書込要求は、アドレス0xB1000004に対してのものである。このアドレスは、MLの値を変更する(更にMUを変化させないでおく)ことによって第1のスロット内に圧縮することができるので、それは、第1のスロット内に圧縮される。
【0029】
図4e及び4fは、既存のスロット内に圧縮できない更に2つの書込要求アドレス0x80000000及び0x90000000の追加を示している。これらのアドレスの追加の後、スロットの全てが使用される。
【0030】
図4gは、新しい要求アドレス0xC0000000の次の追加を示している。このアドレスは、いずれのスロットにも圧縮できず、スロットの全てが満杯であるので、既存のスロットの全ては、第1のスロットにおいて1つの範囲内に圧縮される。こうして、着信書込要求アドレスに利用可能な3つのスロットが存在する。
【0031】
このGWAM構成は、小さなメモリに書込アドレスに関する十分な情報を記憶することを可能にする。必要がないのに挿入される一部の障壁をもたらすことがあるが、実際には、この妥協は、性能にそれ程影響を与えない。
【0032】
図5は、図3の非一貫性検出モジュールの構成要素部分を示している。スレッドTxからの要求を受信すると、非一貫性検出モジュールは、最初に、これがグローバルキャッシュラインへの読取要求又は書込要求かをブロック500で判断する。
【0033】
これがグローバル書込要求である場合、スレッドTxに対するGWAMは、図4に関して上述したように更新される。
【0034】
図5は、ブロック510において、各スレッドに対して非一貫性検出モジュールによって維持されるメモリ及びレジスタを示している。GWAMは、ブロック515として示されている。同じく含まれるのは、メモリアービターに通されるのを待っているFIFO580においてそのスレッドに対して待ち行列に入れられている要求の数の記録であるバッファカウントレジスタ520、1又は0の値を取り、更にそのスレッドに対する最後の障壁以来のそのスレッドに対するデータキャッシュからのいずれかの要求が通されたかを指示する最後の障壁バッファ空(LB_buff_empty)レジスタ525、及びFIFO580における各要求に対する識別値を提供する要求ID(req_id)である。
【0035】
これがスレッドTxからのグローバル読取要求である場合、要求は、比較器ユニット530に通される。比較器ユニット530は、グローバル読取要求のメモリアドレスが、他のスレッドのGWAMのいずれにおいてもアドレス範囲に収まるかを調べるために検査する。
【0036】
読取要求アドレスが、別のスレッドのGWAMにおけるアドレス範囲に収まらない場合、読取要求は、いずれの障壁フラグ又は障壁要求の挿入もなしにメモリアービターに通すことができる。
【0037】
しかし、読取要求アドレスが、別のスレッドのGWAMの記憶されたアドレス範囲内に収まる場合(以下では、本明細書で適合スレッドと呼ぶ)、要求は、各適合スレッドに対するLB_buff_emptyレジスタの値を判断するブロック540に通される。LB_buff_emptyレジスタが、適合スレッドに対して値0を有する場合(すなわち、最後の障壁が挿入されてからはそのスレッドに対して要求が待ち行列に入れられていない場合)、更に別の障壁を挿入する必要はない。しかし、LB_buff_emptyレジスタが、適合スレッドに対して値1を有する場合、非一貫性の問題が起こらないようにするために、そのスレッドに対して障壁を挿入すべきである。
【0038】
障壁を挿入することができる2つの方法がある。障壁は、既存の要求に添付されるサイドバンドデータとして挿入することができ、又は添付されたサイドバンドデータを有する新しい要求を含む個別の「障壁要求」として挿入することができる。問題のスレッドに対してFIFO580において待ち行列に入れられている要求が存在する場合、障壁が、サイドバンドデータとしてFIFOでの最後の要求に追加される。FIFO580でそのスレッドに対して待ち行列に入れられた要求が存在しない場合、障壁サイドバンドデータを添付するものは何もない。この場合、障壁は、添付された障壁サイドバンドデータを有する新しい障壁要求の形式を取らなくてはならない。ブロック545において、非一貫性検出モジュールは、各適合スレッドに対するバッファカウントが0に等しいかを判断する。
【0039】
バッファカウントが0に等しい場合、この障壁は、新しい障壁要求として挿入される。これは、ブロック565で指示されている。同時に、ブロック検査データと呼ばれるサイドバンドデータが、読取要求に追加され、各要求に添付されるタイムスタンプが、増分又はトグルされる。ブロック検査データは、障壁が挿入されている全ての適合スレッドのスレッドIDを含む。次に、要求は、これらがメモリアービターに出されるまでスレッド毎FIFO580において待ち行列に入れられる。「タイムスタンプ」という語は、本明細書では、変更された時に新しい期間をマーク付けする時間に関するデータピースを意味するのに使用される。好ましい実施形態では、タイムスタンプは、0又は1の値を有することができる1ビットフィールドである。
【0040】
バッファカウントが、障壁が挿入される適合スレッドに対して0に等しくない場合、障壁は、サイドバンドデータとしてFIFO580の最後の要求に添付される。しかし、障壁サイドバンドデータは、要求がFIFO580を出た後でないと追加することができない。バックエンド障壁インサートFIFO550が、従って、各スレッドに対して提供される。このFIFO550は、障壁が添付される要求のスレッドIDを対応するグローバル読取要求のIDを含む障壁データ自体と共に記憶する。
【0041】
説明した検査の全てに続いて、各スレッドに対する読取及び書込要求は、スレッド毎要求FIFO580において待ち行列に入れられる。多重化機能570が、図5に示され、要求及び障壁が適切なスレッドFIFO580に経路指定されることを示している。ブロック565からの矢印は、挿入のための障壁要求を示している。図の上部からの矢印は、マルチプレクサ570を通してスレッド毎FIFOに追加される読取及び書込要求を示している。障壁が、個別の障壁要求として挿入される場合、これは、正しいスレッド要求FIFOにおいて待ち行列に入れられ、対応する読取要求は、そのスレッド要求FIFOにおいて待ち行列に入れられる。
【0042】
バックエンド障壁インサート検査段560が、各要求FIFO580の出口に提供される。FIFO580を離れるあらゆる要求が、対応するバックエンド障壁インサートFIFO550での第1のエントリに対して検査される。適合性がある場合、サイドバンドデータが、メモリアービターに送信される前に要求に添付される。
【0043】
サイドバンドデータ又は個別の障壁要求のいずれかとしての障壁が要求待ち行列に含まれる時、そのスレッドに対するGWAMは、瞬時に消去される。これらのメモリアドレスエントリに関連付けられたいずれの非一貫性の障害もこれ以上存在しない時、GWAMにおける全てのエントリを消去することができる。
【0044】
要約すると、順序強制をサポートするために、非一貫性検出モジュールは、着信読取アドレスがGWAMアドレス範囲スロットの1つの中に収まる時に以下の段階を実行する。
1)1つを必要とするスレッドに対する障壁要求を出す。
2)適切なブロック検査サイドバンドデータを読取要求に割り当てる
3)あらゆる読取/書込に添付される内部1ビットタイムスタンプをトグルする。
4)障壁要求を出されたスレッドのGWAMを瞬時に消去する。
【0045】
図6は、この実施形態による順序強制メモリアービターの機能的ハードウエアブロックを示している。
【0046】
メモリアービターは、障壁ステータスレジスタ600及び現在のタイムスタンプレジスタ605を維持する。障壁ステータスレジスタ600は、障壁がスレッドアービター610を通して出されているか及びどのスレッドからかを指示する。障壁ステータスレジスタは、メモリアービターの内部タイムスタンプが増分又はトグルされる度にクリアされる。内部タイムスタンプは、ブロック検査サイドバンドデータを有する読取要求がスレッドアービターによって出される度に増分又はトグルされる。タイムスタンプレジスタは、単純に現在のタイムスタンプ値の記録である。
【0047】
非一貫性検出モジュールから到着した要求がブロック検査サイドバンドデータを有するグローバル読取要求であるかは、ブロック615において最初に判断される。これが、ブロック検査サイドバンドデータを有するグローバル読取要求である場合、ブロック620において、メモリアービターは、ブロック検査サイドバンドデータの障壁データを読み取り、これを障壁ステータスレジスタに対して検査し、関連の障壁が全てスレッドアービター610によって出されているかを判断する。関連の障壁の全てが出されている場合、グローバル読取要求は、スレッドアービターに公開される。関連の障壁の全てがスレッドアービターによって出されていない場合、グローバル読取要求は、メモリアービターの入力で阻止される。これらの検査は、グローバル読取要求が公開されるまで繰り返される。
【0048】
要求がグローバル読取要求ではない場合、ブロック625でのブロック検査サイドバンドデータにより、そのタイムスタンプは、現在のタイムスタンプレジスタに記憶されている内部タイムスタンプ値と比較される。タイムスタンプが適合した場合、要求は、スレッドアービターに公開される。タイムスタンプが適合しなかった場合、要求は阻止される。このタイムスタンプ検査は、タイムスタンプが適合し、要求が公開されるまで繰り返される。
【0049】
スレッドアービター610は、全てのスレッドに対する公開された要求を受信し、ラウンドロビン技術のようなアービトレーション技術を使用して、メモリバスへのアクセスのためにスレッド間を仲裁する。あらゆる望ましい計量法をスレッド間を仲裁するためにスレッドアービターにおいて使用することができる。
【0050】
障壁を含む要求(又は個別の障壁要求)及びブロック検査サイドバンドデータを有するグローバル読取要求が、スレッドアービターによって出された時、障壁ステータスレジスタ及びタイムスタンプレジスタは、上記に説明して図6に示すように更新される。要求は、ブロック630及び635において、ブロック検査サイドバンドデータを有するグローバル読取要求に対して及び障壁に対して検査される。障壁が検出された場合、障壁ステータスレジスタが、ブロック640において更新される。ブロック検査サイドバンドデータを有するグローバル読取要求が検出された場合、障壁ステータスレジスタはクリアされ、タイムスタンプレジスタにおける内部タイムスタンプがブロック645においてトグルされる。
【0051】
その全体的な効果は、その前の全てのスレッドからの全てのメモリ要求が出されるまで、問題の読取に続くいずれの要求もメモリアービターによって出されないということである。GWAMコンテンツは、将来の着信要求がそれらに追い着くことができないように強制機構が保証しているので、障壁要求を出しているスレッドに対して消去することができる。
【0052】
図2aの例示的なシーケンスを参照すると、T1_Read_to_C1が検出モジュール入力に呈示される時、GWAMからの適合性は、検出モジュールによる以下のアクションを起こすと考えられる。
−他の非要求側スレッドT0への障壁要求T0_Bar_T1を挿入する。障壁要求は、それがT1グローバル読取によって起こされた障壁要求であることを指示するスレッドID T1のサイドバンドデータを有する。
−「T0からの障壁まで待つ」ために、T1_Read_to_C1のブロック検査値を設定する。
−グローバルキャッシュ読取の後で将来の要求に対するタイムスタンプフラグを増分する。
メモリアービターは、それらの順序強制サイドバンド値を復号し、適切なアクションを取る。
−メモリバスに出された時に、障壁要求T0_Bar_T1をストールせず、障壁イシューステータスレジスタを更新する。
−T0_Bar_T1が出されたと障壁イシューステータスレジスタが指示するまで、T1_Read_to_C1を持ち続ける。アービターは、T1_Read_to_C1が出された後にそれら独自の現在のタイムスタンプレジスタを更新する。T0_Bar_T1の発行は、T1_Read_to_C1の前にT0からの問題の書込を含む全ての要求が出されたことを意味する。
−T0_Write_to_C3及びT1_Read_to_C4の「安全な」要求のために、アービターの現在のタイムスタンプレジスタをタイムスタンプ値と比較し、タイムスタンプ値が適合した時にのみ発行する。
【0053】
図7は、このような順序強制処理及びメモリアービターによる結果を示している。データキャッシュからの要求の初期ストリームは、ストリーム70として図7の上部に示されている。要求は、スレッド毎ストリームと障壁に分離され、ストリーム71及び72としてスレッドアービター73に入る図7の中心に説明して示すように、非一貫性検出モジュールによってサイドバンドデータが挿入される。図7の下部には、メモリバスに送信された要求74の順序付けされたストリームが示されている。
【0054】
図2bに示す非一貫性障害は、異なる機構を使用して対処することができる。データキャッシュは、データキャッシュのDATA RAMにキャッシュラインの物理アドレスを記憶しているTAG RAMを含む。データキャッシュが、データキャッシュで損失された読取要求を受信した時、TAG RAMからのエントリは、読取要求によってフェッチされるキャッシュラインの物理アドレス情報を記憶するように選択される。TAG RAMにおけるこの物理アドレス情報に充填フラグを追加することができ、これは、RAMのその部分が、現在フェッチされているキャッシュラインに対して除外されていることを指示するものである。充填フラグは、キャッシュラインがフェッチされている時は値1、及びフェッチされるキャッシュラインがない時は0を取る。
【0055】
他のスレッドから同じキャッシュライン内の同じか又は異なる位置への次の書込がある時、充填フラグが値1を有する間は、「汚染フラグ」と呼ばれるTAG RAMにおける別のフラグが、そのキャッシュラインに対して設定される。汚染フラグが値1を有する時、これは、1つのスレッドが、現在フェッチされているキャッシュラインを修正しており、データキャッシュに最終的に入れられているデータが最も最新のデータであるという保証がないので、潜在的な非一貫性の障害が存在することを指示する。汚染フラグが1である時、キャッシュラインは、そのデータが信頼できないので無効であると見なされる。この場合、次の読取要求は、データキャッシュにおけるデータを無視することになり、メインメモリから最新データをフェッチすることになる。
【0056】
以下のシーケンスは、図2bに示す状況に対するこの機構を示している。
【0057】
T1が、Bを読み取る。Bがデータキャッシュにないので、データキャッシュMMUは、メモリバスからBを収容するキャッシュラインをフェッチする。TAG RAMにおけるTAGフィールドが更新され、充填フラグが1に設定され、汚染フラグが0に設定される。
【0058】
T0が、データ0X10をAに書き込む。Aはキャッシュにないが、RAMにおける充填フラグは、キャッシュラインが現在満たされていることを指示する。従って、汚染フラグは、1に設定される。
【0059】
T1キャッシュラインフェッチが行われる。データキャッシュにおけるキャッシュラインは、読取要求の結果として、メインメモリからAの古い値を収容している。
【0060】
T0が、Aを読み取る。データキャッシュが、Aを含むキャッシュラインを収容しているので、TAG RAMコンテンツは、キャッシュヒットを指示するが、汚染フラグは、そのキャッシュラインに対して1に設定される。次に、ハードウエアが、この読取がキャッシュで損失したように判断し、このラインは、メモリバスから再度フェッチされる。この読取がT0書込の後に起こるので、読取は、Aの最後の値を戻し、データの一貫性が維持される。
【0061】
2つの機構、すなわち、図2aで示すようにシナリオを扱う第1の機構と図2bで示すようにシナリオを扱う第2の機構の結合は、書込スルーデータキャッシュにおけるキャッシュ損失の結果として起こるデータ非一貫性に対する解決法を提供する。
【符号の説明】
【0062】
30 データキャッシュメモリ管理ユニット
31、32 スレッドアービター
33 メモリアービター
34 データキャッシュ
35 非一貫性検出モジュール
【技術分野】
【0001】
本発明は、マルチスレッドプロセッサに関し、特に、マルチスレッドプロセッサにおける複数のスレッドによってアクセスされるキャッシャメモリとメインメモリ間のデータ非一貫性の問題に関する。
【背景技術】
【0002】
マルチスレッドプロセッサは、複数の異なる命令シーケンス(又はスレッド)を同時に処理することができる。スレッドの実行中に、データ及び命令は、メモリからアクセスされなくてはならない。従って、異なるスレッドは、メモリ及び時にはメモリの同じ部分に同時にアクセスする必要がある場合がある。従って、メモリアクセスに対してスレッド間に何らかのアービトレーションが必要である。
【0003】
マルチスレッドプロセッサは、典型的には、図1に示すように、最も一般的にアクセスされるデータ及び命令を収容する命令キャッシュ及びデータキャッシュを有する。要求されるデータ又は命令がキャッシュで見つからなかった場合、メモリバス上でのメモリへのアクセスを要求しなくてはならない。メモリへのアクセスは、スレッドが互いに衝突しないように制御しなくてはならない。この理由のために、命令及びデータキャッシュからの異なるスレッドからのメモリアクセスの各々は、メモリアービターモジュールまでのそれら独自の専用データ経路を有する。
【0004】
図1は、従来技術によるマルチスレッドプロセッサのメモリアクセスシステムの概略図である。プロセッサコア10で実行されるスレッドは、データ及び命令キャッシュ11、12からデータ及び命令を要求することができる。命令及びデータキャッシュの各々は、それらに関連付けられたメモリ管理ユニットを有する。要求されたデータ又は命令がキャッシュの1つになかった場合、要求は、メモリバスに通される。異なるスレッドからの要求の間を仲裁するために、要求は、最初にそのスレッドに対する要求を順序付けるスレッドアービター13、14を通して、かつ次にメモリバスへのアクセスを制御するメモリアービター15を通して経路指定される。
【0005】
メインメモリ内では、データは、典型的には、キャッシュラインと呼ばれる固定数のビットの単位で記憶され、かつアクセス可能である。従って、メモリからメモリアドレスを読み取るために、そのアドレスを収容するキャッシュライン全体をフェッチしなくてはならない。キャッシュラインの2つのタイプが存在する。一方のタイプは、特定のスレッドに対するデータを記憶するのみであるローカルキャッシュラインである。他方は、異なるスレッドによってアクセス可能なデータを記憶するグローバルキャッシュラインである。データピースが、グローバル又はローカルキャッシュラインに記憶されるか否かは、その線形アドレスに依存する。本発明は、スレッド間で共有されるメモリリソース、すなわち、グローバルキャッシュラインに関するものである。
【0006】
グローバルキャッシュラインは、キャッシュライン内の異なるワード位置に異なるスレッドによって入力されたソフトウエアローカル変数の値を記憶することができると考えられる。スレッドTxがキャッシュラインからそのローカル変数を読み取った時、その最後に書かれた値を取り戻すことが予想される。しかし、他のスレッドによる同じキャッシュライン内のそれらのローカル変数へのアクセスがスレッドTxに古い間違った値を読み取らせるという状況が、書込スルーデータキャッシュを使用した時に起こる可能性がある。これが起こった時、Txは、「データが非一貫性」になったと呼ばれる。
【0007】
図2a及び2bの各々は、スレッドT0上でデータ非一貫性を起こす異なるスレッドによるアクセスの例示的なシーケンスを示している。
【0008】
図2aを参照すると、T0は、書込要求により、最初にそのローカル変数Aにアクセスする。次に、T1は、読取要求により、そのローカル変数Bにアクセスする。A及びBの物理アドレスは、これらが同じグローバルデータキャッシュライン内でキャッシュに入れられるようなものである。最初にA及びBの両方はキャッシュにはない。
【0009】
読取要求は、典型的には、書込要求よりはメモリバスに到達するための時間がかからない。この場合、T1読取は、T0書込の前にメモリに到達する。この結果、キャッシュラインの古い値が、データキャッシュに記憶される。T0書込要求は、データキャッシュではなく、メモリバスにのみ書き込む。従って、データキャッシュからのキャッシュラインの次の読取は、T1読取の結果としてデータキャッシュに記憶されている古い値をフェッチすることになる。
【0010】
図2bを参照すると、ここでもまた、A及びBの両方が同じキャッシュラインにあり、最初はデータキャッシュにはない。T1は、最初に、読取要求によってメモリバスからBにアクセスする。Bがフェッチされる前に、すなわち、読取要求がデータキャッシュを離れた時間とBを収容するキャッシュラインがデータキャッシュに記憶された時間との間に、Aに対する書込要求がT0からメモリバスに出される。ここでもまた、T0からの書込は、データキャッシュに書き込まれず、従って、データキャッシュは、次の読取要求によってアクセスされることになるキャッシュラインの古いバージョンを保持する。
【発明の概要】
【発明が解決しようとする課題】
【0011】
図から分るように、複数のスレッドがメモリバスからグローバルキャッシュメモリにアクセスした時、データ非一貫性が、特に、書込スルーキャッシュを発生させる可能性がある。本発明は、非一貫性の障害を検出することにより、かつ読取又は書込命令がそれを行うことが安全である時にだけメモリバスから出されることを保証する機構を使用することにより、この問題に対処することを目的とする。
【課題を解決するための手段】
【0012】
本発明は、添付の独立請求項に定められている。好ましい特徴は、従属請求項に定められている。
【0013】
ここで、本発明の実施例を添付の図面に関連して以下に説明する。
【図面の簡単な説明】
【0014】
【図1】従来のマルチスレッドプロセッサコアのメモリアクセスシステムを示す図である。
【図2a】キャッシュ非一貫性をもたらすメモリアクセスのシーケンスを示す図である。
【図2b】キャッシュ非一貫性をもたらすメモリアクセスのシーケンスを示す図である。
【図3】本発明によるシステムを示す概略図である。
【図4】本発明による例示的なグローバル書込アドレスメモリの作動を示す図である。
【図5】図3のシステムで使用される非一貫性検出モジュールを示す図である。
【図6】図3のシステムで使用されるメモリアービターを示す図である。
【図7】アービターでの順序強制を示す図である。
【発明を実施するための形態】
【0015】
図2a及び2bに示すように、データ非一貫性は、異なる状況から生じる可能性があり、これは、個別に扱うことができる。図2aで示す非一貫性は、第1の機構を使用して防ぐことができ、図2bで示す非一貫性は、第2の機構を使用して防ぐことができる。
【0016】
図3は、本発明の第1の態様によるシステムの概略図である。図3は、図2aに関して説明した状況から起こる可能性があるデータ非一貫性を防ぐメモリバスからデータにアクセスするためのシステムを示している。本発明は、データ非一貫性、及び従ってデータへのアクセスに関するものであるから、メモリバスからの命令フェッチのための経路は、分かり易いように省略する。
【0017】
システムは、プロセッサコアに接続したデータキャッシュメモリ管理ユニット30、メモリ管理ユニットに接続したスレッドアービター31、32、及びスレッドアービターとメモリバス間に接続したメモリアービター33を含む。
【0018】
データキャッシュメモリ管理ユニット内に、データキャッシュそれ自体34及びアドレス変換などのための関連のメモリ管理機能、並びに非一貫性検出モジュールがある。
【0019】
図1に示すシステムのように、図2のシステムでは、プロセッサコアで実行されるスレッドが読取又は書込要求を出した時に、この要求は、データキャッシュMMU30に経路指定される。読取要求では、データがデータキャッシュ34にある場合、これは、即座にフェッチされて使用される。それがデータキャッシュにない場合、メモリバス上のメモリにアクセスしなくてはならない。書込スルーキャッシュでの書込要求では、書込要求は、常に、メモリバスにアクセスする。データキャッシュに関連付けられたメモリ管理ユニット(MMU)機能は、プロセッサで実行されるプログラムによって使用される仮想メモリアドレスをメモリバス上の物理メモリアドレスに変換することになる。
【0020】
本発明の1つの態様では、非一貫性検出モジュール35が、グローバル読取要求及びグローバル書込要求から生じる非一貫性に対処するために提供される。本明細書で使用される「グローバル書込要求」及び「グローバル読取要求」という語は、複数のスレッドによって共有されるメモリの一部分への要求を意味する。データキャッシュ34からのグローバル読取及び書込要求は、メモリアービター33及び次にメモリバスに到達する前に、最初に、非一貫性検出モジュール35を通過しなくてはならない。非一貫性検出モジュールは、図5に更に詳しく示されている。
【0021】
非一貫性検出モジュールは、3つの機能を有する。1つは、以前のグローバル書込要求の物理アドレスの記録を維持することである。別のものは、あらゆる着信グローバル読取のアドレスを以前の書込要求の記録と比較し、同じグローバルキャッシュラインへの過去の書込があるかを判断することである。最後は、メモリアービター33が非一貫性検出モジュール35によって意図されるようなメモリバスに要求を出すための順序を強制することができるように、比較情報を使用して「順序強制サイドバンド」を各要求に追加する(又は、個別の「障壁要求」を挿入する)ことである。この機構は、性能劣化を起こすと考えられるメモリアービターの前の様々なモジュールを通るデータフローの停止又は失速を生じない。
【0022】
全ての以前のグローバルキャッシュ書込の個々の物理アドレスの記録を維持することは、実施には実際的でないメモリの無限量を必要とする。代替としては、グローバル書込要求の個々のアドレスを代わりにアドレスの範囲に圧縮することである。この実施形態では、非一貫性検出モジュールは、各スレッドに対する「グローバル書込アドレスメモリ(GWAM)」を含む。各GWAMは、少数のデータ記憶スロットから構成され、各々は、重なっていないアドレス範囲を記憶する。
【0023】
図4は、本発明による例示的なGWAMがどのように作動するかを示している。図4aは、4つのメモリスロットを有するGWAMを示している。メモリスロットは、最初は空である。各メモリスロットは、4つのフィールド、すなわち、有効フラグフィールド、32ビットバイトアドレスフィールド(TAG)、上位アドレス範囲サイズマスク(MU)、及び下位アドレス範囲サイズビットマスク(ML)を有する。
【0024】
有効フラグは、記録された書込アドレスがメモリスロット内にあるかを単純に指示する。TAGフィールドは、スロットによって網羅されるメモリアドレスの範囲内のアドレスを指示する。
【0025】
MU及びMLフィールドは、スロットによって網羅されるメモリアドレス範囲を定義する。網羅されるアドレス範囲に対して、下位アドレス=TAG &&(MU & ML)であり、ここで、&&は、ビットAND演算を表し、&は、ベクトル連結を表している。上位アドレス=TAG‖!(MU & ML)であり、ここで、‖は、ビットOR演算を表している。例えば、16進表記を使用して、TAG = 0xAAAAAA34に対して、ML = 0xFFFF00、MU = 0xFF、アドレス範囲=0xAAAAAA00から0xAAAAAAFFである。
【0026】
第1の書込アドレスが記録された時、これは、GWAMのメモリスロットに割り当てられる。これは、図4bに示されている。スロットの全てがこの前に空であるので、データを圧縮する必要はない。この場合は0xB1000000である書込アドレスは、最小アドレス範囲で第1のスロットに記憶される。
【0027】
第2の書込アドレス0xA0000000がGWAMに記憶される時、これは、ここでもまた最小範囲により、第2のスロットに記憶される。これは、図4cに示されている。
【0028】
別のスロットのMUフィールドによって定義されたアドレス範囲に収まることができる第3の書込アドレスが出された時、これは、そのスロットに配置され、MLフィールドが、新しいアドレスを入れるために変更される。図4dはこれを示している。図4dでは、新しい書込要求は、アドレス0xB1000004に対してのものである。このアドレスは、MLの値を変更する(更にMUを変化させないでおく)ことによって第1のスロット内に圧縮することができるので、それは、第1のスロット内に圧縮される。
【0029】
図4e及び4fは、既存のスロット内に圧縮できない更に2つの書込要求アドレス0x80000000及び0x90000000の追加を示している。これらのアドレスの追加の後、スロットの全てが使用される。
【0030】
図4gは、新しい要求アドレス0xC0000000の次の追加を示している。このアドレスは、いずれのスロットにも圧縮できず、スロットの全てが満杯であるので、既存のスロットの全ては、第1のスロットにおいて1つの範囲内に圧縮される。こうして、着信書込要求アドレスに利用可能な3つのスロットが存在する。
【0031】
このGWAM構成は、小さなメモリに書込アドレスに関する十分な情報を記憶することを可能にする。必要がないのに挿入される一部の障壁をもたらすことがあるが、実際には、この妥協は、性能にそれ程影響を与えない。
【0032】
図5は、図3の非一貫性検出モジュールの構成要素部分を示している。スレッドTxからの要求を受信すると、非一貫性検出モジュールは、最初に、これがグローバルキャッシュラインへの読取要求又は書込要求かをブロック500で判断する。
【0033】
これがグローバル書込要求である場合、スレッドTxに対するGWAMは、図4に関して上述したように更新される。
【0034】
図5は、ブロック510において、各スレッドに対して非一貫性検出モジュールによって維持されるメモリ及びレジスタを示している。GWAMは、ブロック515として示されている。同じく含まれるのは、メモリアービターに通されるのを待っているFIFO580においてそのスレッドに対して待ち行列に入れられている要求の数の記録であるバッファカウントレジスタ520、1又は0の値を取り、更にそのスレッドに対する最後の障壁以来のそのスレッドに対するデータキャッシュからのいずれかの要求が通されたかを指示する最後の障壁バッファ空(LB_buff_empty)レジスタ525、及びFIFO580における各要求に対する識別値を提供する要求ID(req_id)である。
【0035】
これがスレッドTxからのグローバル読取要求である場合、要求は、比較器ユニット530に通される。比較器ユニット530は、グローバル読取要求のメモリアドレスが、他のスレッドのGWAMのいずれにおいてもアドレス範囲に収まるかを調べるために検査する。
【0036】
読取要求アドレスが、別のスレッドのGWAMにおけるアドレス範囲に収まらない場合、読取要求は、いずれの障壁フラグ又は障壁要求の挿入もなしにメモリアービターに通すことができる。
【0037】
しかし、読取要求アドレスが、別のスレッドのGWAMの記憶されたアドレス範囲内に収まる場合(以下では、本明細書で適合スレッドと呼ぶ)、要求は、各適合スレッドに対するLB_buff_emptyレジスタの値を判断するブロック540に通される。LB_buff_emptyレジスタが、適合スレッドに対して値0を有する場合(すなわち、最後の障壁が挿入されてからはそのスレッドに対して要求が待ち行列に入れられていない場合)、更に別の障壁を挿入する必要はない。しかし、LB_buff_emptyレジスタが、適合スレッドに対して値1を有する場合、非一貫性の問題が起こらないようにするために、そのスレッドに対して障壁を挿入すべきである。
【0038】
障壁を挿入することができる2つの方法がある。障壁は、既存の要求に添付されるサイドバンドデータとして挿入することができ、又は添付されたサイドバンドデータを有する新しい要求を含む個別の「障壁要求」として挿入することができる。問題のスレッドに対してFIFO580において待ち行列に入れられている要求が存在する場合、障壁が、サイドバンドデータとしてFIFOでの最後の要求に追加される。FIFO580でそのスレッドに対して待ち行列に入れられた要求が存在しない場合、障壁サイドバンドデータを添付するものは何もない。この場合、障壁は、添付された障壁サイドバンドデータを有する新しい障壁要求の形式を取らなくてはならない。ブロック545において、非一貫性検出モジュールは、各適合スレッドに対するバッファカウントが0に等しいかを判断する。
【0039】
バッファカウントが0に等しい場合、この障壁は、新しい障壁要求として挿入される。これは、ブロック565で指示されている。同時に、ブロック検査データと呼ばれるサイドバンドデータが、読取要求に追加され、各要求に添付されるタイムスタンプが、増分又はトグルされる。ブロック検査データは、障壁が挿入されている全ての適合スレッドのスレッドIDを含む。次に、要求は、これらがメモリアービターに出されるまでスレッド毎FIFO580において待ち行列に入れられる。「タイムスタンプ」という語は、本明細書では、変更された時に新しい期間をマーク付けする時間に関するデータピースを意味するのに使用される。好ましい実施形態では、タイムスタンプは、0又は1の値を有することができる1ビットフィールドである。
【0040】
バッファカウントが、障壁が挿入される適合スレッドに対して0に等しくない場合、障壁は、サイドバンドデータとしてFIFO580の最後の要求に添付される。しかし、障壁サイドバンドデータは、要求がFIFO580を出た後でないと追加することができない。バックエンド障壁インサートFIFO550が、従って、各スレッドに対して提供される。このFIFO550は、障壁が添付される要求のスレッドIDを対応するグローバル読取要求のIDを含む障壁データ自体と共に記憶する。
【0041】
説明した検査の全てに続いて、各スレッドに対する読取及び書込要求は、スレッド毎要求FIFO580において待ち行列に入れられる。多重化機能570が、図5に示され、要求及び障壁が適切なスレッドFIFO580に経路指定されることを示している。ブロック565からの矢印は、挿入のための障壁要求を示している。図の上部からの矢印は、マルチプレクサ570を通してスレッド毎FIFOに追加される読取及び書込要求を示している。障壁が、個別の障壁要求として挿入される場合、これは、正しいスレッド要求FIFOにおいて待ち行列に入れられ、対応する読取要求は、そのスレッド要求FIFOにおいて待ち行列に入れられる。
【0042】
バックエンド障壁インサート検査段560が、各要求FIFO580の出口に提供される。FIFO580を離れるあらゆる要求が、対応するバックエンド障壁インサートFIFO550での第1のエントリに対して検査される。適合性がある場合、サイドバンドデータが、メモリアービターに送信される前に要求に添付される。
【0043】
サイドバンドデータ又は個別の障壁要求のいずれかとしての障壁が要求待ち行列に含まれる時、そのスレッドに対するGWAMは、瞬時に消去される。これらのメモリアドレスエントリに関連付けられたいずれの非一貫性の障害もこれ以上存在しない時、GWAMにおける全てのエントリを消去することができる。
【0044】
要約すると、順序強制をサポートするために、非一貫性検出モジュールは、着信読取アドレスがGWAMアドレス範囲スロットの1つの中に収まる時に以下の段階を実行する。
1)1つを必要とするスレッドに対する障壁要求を出す。
2)適切なブロック検査サイドバンドデータを読取要求に割り当てる
3)あらゆる読取/書込に添付される内部1ビットタイムスタンプをトグルする。
4)障壁要求を出されたスレッドのGWAMを瞬時に消去する。
【0045】
図6は、この実施形態による順序強制メモリアービターの機能的ハードウエアブロックを示している。
【0046】
メモリアービターは、障壁ステータスレジスタ600及び現在のタイムスタンプレジスタ605を維持する。障壁ステータスレジスタ600は、障壁がスレッドアービター610を通して出されているか及びどのスレッドからかを指示する。障壁ステータスレジスタは、メモリアービターの内部タイムスタンプが増分又はトグルされる度にクリアされる。内部タイムスタンプは、ブロック検査サイドバンドデータを有する読取要求がスレッドアービターによって出される度に増分又はトグルされる。タイムスタンプレジスタは、単純に現在のタイムスタンプ値の記録である。
【0047】
非一貫性検出モジュールから到着した要求がブロック検査サイドバンドデータを有するグローバル読取要求であるかは、ブロック615において最初に判断される。これが、ブロック検査サイドバンドデータを有するグローバル読取要求である場合、ブロック620において、メモリアービターは、ブロック検査サイドバンドデータの障壁データを読み取り、これを障壁ステータスレジスタに対して検査し、関連の障壁が全てスレッドアービター610によって出されているかを判断する。関連の障壁の全てが出されている場合、グローバル読取要求は、スレッドアービターに公開される。関連の障壁の全てがスレッドアービターによって出されていない場合、グローバル読取要求は、メモリアービターの入力で阻止される。これらの検査は、グローバル読取要求が公開されるまで繰り返される。
【0048】
要求がグローバル読取要求ではない場合、ブロック625でのブロック検査サイドバンドデータにより、そのタイムスタンプは、現在のタイムスタンプレジスタに記憶されている内部タイムスタンプ値と比較される。タイムスタンプが適合した場合、要求は、スレッドアービターに公開される。タイムスタンプが適合しなかった場合、要求は阻止される。このタイムスタンプ検査は、タイムスタンプが適合し、要求が公開されるまで繰り返される。
【0049】
スレッドアービター610は、全てのスレッドに対する公開された要求を受信し、ラウンドロビン技術のようなアービトレーション技術を使用して、メモリバスへのアクセスのためにスレッド間を仲裁する。あらゆる望ましい計量法をスレッド間を仲裁するためにスレッドアービターにおいて使用することができる。
【0050】
障壁を含む要求(又は個別の障壁要求)及びブロック検査サイドバンドデータを有するグローバル読取要求が、スレッドアービターによって出された時、障壁ステータスレジスタ及びタイムスタンプレジスタは、上記に説明して図6に示すように更新される。要求は、ブロック630及び635において、ブロック検査サイドバンドデータを有するグローバル読取要求に対して及び障壁に対して検査される。障壁が検出された場合、障壁ステータスレジスタが、ブロック640において更新される。ブロック検査サイドバンドデータを有するグローバル読取要求が検出された場合、障壁ステータスレジスタはクリアされ、タイムスタンプレジスタにおける内部タイムスタンプがブロック645においてトグルされる。
【0051】
その全体的な効果は、その前の全てのスレッドからの全てのメモリ要求が出されるまで、問題の読取に続くいずれの要求もメモリアービターによって出されないということである。GWAMコンテンツは、将来の着信要求がそれらに追い着くことができないように強制機構が保証しているので、障壁要求を出しているスレッドに対して消去することができる。
【0052】
図2aの例示的なシーケンスを参照すると、T1_Read_to_C1が検出モジュール入力に呈示される時、GWAMからの適合性は、検出モジュールによる以下のアクションを起こすと考えられる。
−他の非要求側スレッドT0への障壁要求T0_Bar_T1を挿入する。障壁要求は、それがT1グローバル読取によって起こされた障壁要求であることを指示するスレッドID T1のサイドバンドデータを有する。
−「T0からの障壁まで待つ」ために、T1_Read_to_C1のブロック検査値を設定する。
−グローバルキャッシュ読取の後で将来の要求に対するタイムスタンプフラグを増分する。
メモリアービターは、それらの順序強制サイドバンド値を復号し、適切なアクションを取る。
−メモリバスに出された時に、障壁要求T0_Bar_T1をストールせず、障壁イシューステータスレジスタを更新する。
−T0_Bar_T1が出されたと障壁イシューステータスレジスタが指示するまで、T1_Read_to_C1を持ち続ける。アービターは、T1_Read_to_C1が出された後にそれら独自の現在のタイムスタンプレジスタを更新する。T0_Bar_T1の発行は、T1_Read_to_C1の前にT0からの問題の書込を含む全ての要求が出されたことを意味する。
−T0_Write_to_C3及びT1_Read_to_C4の「安全な」要求のために、アービターの現在のタイムスタンプレジスタをタイムスタンプ値と比較し、タイムスタンプ値が適合した時にのみ発行する。
【0053】
図7は、このような順序強制処理及びメモリアービターによる結果を示している。データキャッシュからの要求の初期ストリームは、ストリーム70として図7の上部に示されている。要求は、スレッド毎ストリームと障壁に分離され、ストリーム71及び72としてスレッドアービター73に入る図7の中心に説明して示すように、非一貫性検出モジュールによってサイドバンドデータが挿入される。図7の下部には、メモリバスに送信された要求74の順序付けされたストリームが示されている。
【0054】
図2bに示す非一貫性障害は、異なる機構を使用して対処することができる。データキャッシュは、データキャッシュのDATA RAMにキャッシュラインの物理アドレスを記憶しているTAG RAMを含む。データキャッシュが、データキャッシュで損失された読取要求を受信した時、TAG RAMからのエントリは、読取要求によってフェッチされるキャッシュラインの物理アドレス情報を記憶するように選択される。TAG RAMにおけるこの物理アドレス情報に充填フラグを追加することができ、これは、RAMのその部分が、現在フェッチされているキャッシュラインに対して除外されていることを指示するものである。充填フラグは、キャッシュラインがフェッチされている時は値1、及びフェッチされるキャッシュラインがない時は0を取る。
【0055】
他のスレッドから同じキャッシュライン内の同じか又は異なる位置への次の書込がある時、充填フラグが値1を有する間は、「汚染フラグ」と呼ばれるTAG RAMにおける別のフラグが、そのキャッシュラインに対して設定される。汚染フラグが値1を有する時、これは、1つのスレッドが、現在フェッチされているキャッシュラインを修正しており、データキャッシュに最終的に入れられているデータが最も最新のデータであるという保証がないので、潜在的な非一貫性の障害が存在することを指示する。汚染フラグが1である時、キャッシュラインは、そのデータが信頼できないので無効であると見なされる。この場合、次の読取要求は、データキャッシュにおけるデータを無視することになり、メインメモリから最新データをフェッチすることになる。
【0056】
以下のシーケンスは、図2bに示す状況に対するこの機構を示している。
【0057】
T1が、Bを読み取る。Bがデータキャッシュにないので、データキャッシュMMUは、メモリバスからBを収容するキャッシュラインをフェッチする。TAG RAMにおけるTAGフィールドが更新され、充填フラグが1に設定され、汚染フラグが0に設定される。
【0058】
T0が、データ0X10をAに書き込む。Aはキャッシュにないが、RAMにおける充填フラグは、キャッシュラインが現在満たされていることを指示する。従って、汚染フラグは、1に設定される。
【0059】
T1キャッシュラインフェッチが行われる。データキャッシュにおけるキャッシュラインは、読取要求の結果として、メインメモリからAの古い値を収容している。
【0060】
T0が、Aを読み取る。データキャッシュが、Aを含むキャッシュラインを収容しているので、TAG RAMコンテンツは、キャッシュヒットを指示するが、汚染フラグは、そのキャッシュラインに対して1に設定される。次に、ハードウエアが、この読取がキャッシュで損失したように判断し、このラインは、メモリバスから再度フェッチされる。この読取がT0書込の後に起こるので、読取は、Aの最後の値を戻し、データの一貫性が維持される。
【0061】
2つの機構、すなわち、図2aで示すようにシナリオを扱う第1の機構と図2bで示すようにシナリオを扱う第2の機構の結合は、書込スルーデータキャッシュにおけるキャッシュ損失の結果として起こるデータ非一貫性に対する解決法を提供する。
【符号の説明】
【0062】
30 データキャッシュメモリ管理ユニット
31、32 スレッドアービター
33 メモリアービター
34 データキャッシュ
35 非一貫性検出モジュール
【特許請求の範囲】
【請求項1】
複数のスレッドをサポートするマルチスレッドプロセッサによるメモリアクセスを制御するためのシステムであって、
プロセッサコアと、
複数のスレッドの各々によってアクセス可能なデータを記憶するキャッシュメモリと、
前記複数のスレッドによってアクセス可能なデータを記憶するメインメモリと、
非一貫性検出モジュールと、
メモリアービターであって、前記非一貫性検出モジュールが、前記プロセッサコアと該メモリアービターの間に接続され、該メモリアービターが、該非一貫性検出モジュールと前記メインメモリの間に接続され、前記キャッシュメモリから該メモリアービターに送信された読取及び書込要求のための各スレッドに対して個別の要求待ち行列が存在するメモリアービターと、
を含み、
使用において、前記一貫性検出モジュールは、前記キャッシュメモリから前記メインメモリに送信された各書込要求に対するメモリアドレスの指示を書込アドレスメモリに記憶し、かつ該キャッシュメモリから該メインメモリに送信された各次の読取要求のアドレスを該書込アドレスメモリ内の指示と比較し、該次の読取要求のアドレスが指示に適合する場合に、該読取要求に対応する障壁を該適合指示が属する前記スレッドの前記要求待ち行列内に挿入し、前記メモリアービターは、前記対応する障壁が該メモリアービターによって受信されるまで、前記次の読取要求が前記メインメモリにアクセスすることを阻止する、
ことを特徴とするシステム。
【請求項2】
前記非一貫性検出モジュールは、サイドバンドデータを前記次の読取要求に添付することを特徴とする請求項1に記載のシステム。
【請求項3】
前記サイドバンドデータは、対応する障壁が挿入された前記要求待ち行列内にこれらのスレッドのリストを含め、
前記次の読取要求は、前記対応する障壁の全てが前記メモリアービターによって受信されるまで、前記メインメモリへのアクセスを阻止される、
ことを特徴とする請求項2に記載のシステム。
【請求項4】
前記非一貫性検出モジュールは、現在のタイムスタンプを各要求に添付することを特徴とする請求項1から請求項3のいずれか1項に記載のシステム。
【請求項5】
前記非一貫性検出モジュールは、読取要求の前記アドレスが前記書込アドレスメモリ内の1つ又はそれよりも多くの指示に適合する毎に前記現在のタイムスタンプを更新することを特徴とする請求項4に記載のシステム。
【請求項6】
前記メモリアービターは、内部タイムスタンプカウンタを含み、かつサイドバンドデータが添付された読取要求以外の要求が、その要求に添付されたタイムスタンプが該内部タイムスタンプカウンタに適合する時にのみ前記メインメモリにアクセスすることを許可することになり、
前記内部タイムスタンプカウンタは、サイドバンドデータが添付された読取要求が前記メモリアービターを通過する毎に更新される、
ことを特徴とする請求項2又は請求項3に従属する時の請求項4又は請求項5のいずれか1項に記載のシステム。
【請求項7】
前記非一貫性検出モジュールは、前記書込要求の前記メモリアドレスが属するアドレス範囲を該書込アドレスメモリに記憶することにより、該書込要求のメモリアドレスの指示を記憶することを特徴とする請求項1から請求項6のいずれか1項に記載のシステム。
【請求項8】
前記非一貫性検出モジュールは、単一アドレス範囲エントリにおける複数のアドレスを前記書込アドレスメモリに記憶し、
前記アドレス範囲のサイズは、動的に変更することができる、
ことを特徴とする請求項7に記載のシステム。
【請求項9】
前記プロセッサコアから前記メモリバスに送信された各書込要求に対するメモリアドレスの前記指示は、前記非一貫性モジュールにおけるスレッド特定の書込アドレスメモリに記憶され、該非一貫性検出モジュールは、前記次の読取要求の前記アドレスを他のスレッドの各々の該書込アドレスメモリ内の指示と比較することを特徴とする請求項1から請求項8のいずれか1項に記載のシステム。
【請求項10】
各スレッドが、特定の書込アドレスメモリを有し、
スレッドに対する書込アドレスメモリ内の全てのエントリが、障壁がそのスレッドに対する前記要求待ち行列に追加された時に削除される、
ことを特徴とする請求項1から請求項9のいずれか1項に記載のシステム。
【請求項11】
前記障壁は、前記対応する読取要求が属する前記スレッドを識別するデータを含むことを特徴とする請求項1から請求項10のいずれか1項に記載のシステム。
【請求項12】
前記障壁は、前記適合指示が属する前記スレッドの前記要求待ち行列における既存の要求に添付された障壁サイドバンドデータを含むことを特徴とする請求項1から請求項11のいずれか1項に記載のシステム。
【請求項13】
前記適合指示が属する前記スレッドの前記要求待ち行列に要求が存在しない時に、前記障壁は、該要求待ち行列内に挿入された新しい要求に添付された障壁サイドバンドデータを含むことを特徴とする請求項1から請求項11のいずれか1項に記載のシステム。
【請求項14】
前記非一貫性検出モジュールは、前記適合指示が属する前記スレッドの前記要求待ち行列内に障壁を以前の障壁がそのスレッドに対して挿入されてからそのスレッドからの前記キャッシュメモリから要求が送信されていた場合にのみ挿入することを特徴とする請求項1から請求項13のいずれか1項に記載のシステム。
【請求項15】
プロセッサコア、複数のスレッドの各々によってアクセス可能なデータを記憶するキャッシュメモリ、該複数のスレッドによってアクセス可能なデータを記憶するメインメモリに接続されたメモリバス、及び各スレッドに対する書込アドレスメモリを含むマルチスレッドプロセッサにおけるスレッドによるグローバルメモリへのアクセスを制御する方法であって、
(a)各スレッドに対して、前記メインメモリへの各書込要求のメモリアドレスの指示を対応する書込アドレスメモリに記憶する段階、
(b)次の読取要求のメモリアドレスを他のスレッドの前記書込アドレスメモリのコンテンツと比較する段階、及び
(c)前記読取要求の前記メモリアドレスが書込アドレスメモリ内の指示に対応する場合に、前記対応する書込要求が属する前記スレッドの要求待ち行列内に障壁を挿入し、かつ対応する障壁が前記メインメモリによって受信されるまで、該読取要求が該メインメモリにアクセスすることを阻止する段階、
を含むことを特徴とする方法。
【請求項16】
スレッドに対する書込アドレスメモリ内の全てのエントリを障壁がそのスレッドの前記要求待ち行列に追加された時に削除する段階を更に含むことを特徴とする請求項15に記載の方法。
【請求項17】
前記障壁は、対応する読取要求が属するスレッドを識別するデータを含むことを特徴とする請求項15又は請求項16に記載の方法。
【請求項18】
前記障壁は、前記要求待ち行列における既存の要求に添付されたサイドバンドデータを含むことを特徴とする請求項15、請求項16、又は請求項17に記載の方法。
【請求項19】
適合指示が属するスレッドの前記要求待ち行列に要求がない時に、前記障壁は、該要求待ち行列内に挿入された新しい要求に添付された障壁サイドバンドデータを含むことを特徴とする請求項15から請求項18のいずれか1項に記載の方法。
【請求項20】
障壁をスレッドの要求待ち行列内に挿入する前記段階は、以前の障壁がそのスレッドに対して挿入されてからそのスレッドに対する前記キャッシュメモリから送信された要求が存在する場合にのみ実行されることを特徴とする請求項15から請求項19のいずれか1項に記載の方法。
【請求項21】
現在のタイムスタンプをどの要求にも添付する段階を更に含むことを特徴とする請求項15から請求項20のいずれか1項に記載の方法。
【請求項22】
読取要求の前記メモリアドレスが前記書込アドレスメモリ内の1つ又はそれよりも多くの指示に対応する毎に添付される前記タイムスタンプを更新する段階を更に含むことを特徴とする請求項21に記載の方法。
【請求項23】
サイドバンドデータを前記次の読取要求に添付する段階を更に含むことを特徴とする請求項15から請求項22のいずれか1項に記載の方法。
【請求項24】
前記サイドバンドデータは、それらのスレッドのリストを対応する障壁が挿入された前記要求待ち行列内に含め、
前記読取要求は、前記対応する障壁の全てがメモリアービターを通過した後にのみ前記メインメモリに通される、
ことを特徴とする請求項23に記載の方法。
【請求項25】
段階(c)は、サイドバンドデータが添付された読取要求以外の要求が、その要求に添付されたタイムスタンプが内部タイムスタンプカウンタに適合するまで前記メインメモリにアクセスすることを阻止する段階を更に含み、
添付されたサイドバンドデータを有する読取要求がメモリアービターを通過する度に前記内部タイムスタンプカウンタを更新する段階、
を更に含むことを特徴とする請求項23又は請求項24に記載の方法。
【請求項26】
段階(a)は、前記書込要求が属するアドレス範囲を前記書込アドレスメモリに記憶することによって各書込要求の前記メモリアドレスの指示を記憶する段階を含むことを特徴とする請求項15から請求項25のいずれか1項に記載の方法。
【請求項27】
段階(a)は、複数のアドレスを単一アドレス範囲として記憶する段階を含むことを特徴とする請求項26に記載の方法。
【請求項1】
複数のスレッドをサポートするマルチスレッドプロセッサによるメモリアクセスを制御するためのシステムであって、
プロセッサコアと、
複数のスレッドの各々によってアクセス可能なデータを記憶するキャッシュメモリと、
前記複数のスレッドによってアクセス可能なデータを記憶するメインメモリと、
非一貫性検出モジュールと、
メモリアービターであって、前記非一貫性検出モジュールが、前記プロセッサコアと該メモリアービターの間に接続され、該メモリアービターが、該非一貫性検出モジュールと前記メインメモリの間に接続され、前記キャッシュメモリから該メモリアービターに送信された読取及び書込要求のための各スレッドに対して個別の要求待ち行列が存在するメモリアービターと、
を含み、
使用において、前記一貫性検出モジュールは、前記キャッシュメモリから前記メインメモリに送信された各書込要求に対するメモリアドレスの指示を書込アドレスメモリに記憶し、かつ該キャッシュメモリから該メインメモリに送信された各次の読取要求のアドレスを該書込アドレスメモリ内の指示と比較し、該次の読取要求のアドレスが指示に適合する場合に、該読取要求に対応する障壁を該適合指示が属する前記スレッドの前記要求待ち行列内に挿入し、前記メモリアービターは、前記対応する障壁が該メモリアービターによって受信されるまで、前記次の読取要求が前記メインメモリにアクセスすることを阻止する、
ことを特徴とするシステム。
【請求項2】
前記非一貫性検出モジュールは、サイドバンドデータを前記次の読取要求に添付することを特徴とする請求項1に記載のシステム。
【請求項3】
前記サイドバンドデータは、対応する障壁が挿入された前記要求待ち行列内にこれらのスレッドのリストを含め、
前記次の読取要求は、前記対応する障壁の全てが前記メモリアービターによって受信されるまで、前記メインメモリへのアクセスを阻止される、
ことを特徴とする請求項2に記載のシステム。
【請求項4】
前記非一貫性検出モジュールは、現在のタイムスタンプを各要求に添付することを特徴とする請求項1から請求項3のいずれか1項に記載のシステム。
【請求項5】
前記非一貫性検出モジュールは、読取要求の前記アドレスが前記書込アドレスメモリ内の1つ又はそれよりも多くの指示に適合する毎に前記現在のタイムスタンプを更新することを特徴とする請求項4に記載のシステム。
【請求項6】
前記メモリアービターは、内部タイムスタンプカウンタを含み、かつサイドバンドデータが添付された読取要求以外の要求が、その要求に添付されたタイムスタンプが該内部タイムスタンプカウンタに適合する時にのみ前記メインメモリにアクセスすることを許可することになり、
前記内部タイムスタンプカウンタは、サイドバンドデータが添付された読取要求が前記メモリアービターを通過する毎に更新される、
ことを特徴とする請求項2又は請求項3に従属する時の請求項4又は請求項5のいずれか1項に記載のシステム。
【請求項7】
前記非一貫性検出モジュールは、前記書込要求の前記メモリアドレスが属するアドレス範囲を該書込アドレスメモリに記憶することにより、該書込要求のメモリアドレスの指示を記憶することを特徴とする請求項1から請求項6のいずれか1項に記載のシステム。
【請求項8】
前記非一貫性検出モジュールは、単一アドレス範囲エントリにおける複数のアドレスを前記書込アドレスメモリに記憶し、
前記アドレス範囲のサイズは、動的に変更することができる、
ことを特徴とする請求項7に記載のシステム。
【請求項9】
前記プロセッサコアから前記メモリバスに送信された各書込要求に対するメモリアドレスの前記指示は、前記非一貫性モジュールにおけるスレッド特定の書込アドレスメモリに記憶され、該非一貫性検出モジュールは、前記次の読取要求の前記アドレスを他のスレッドの各々の該書込アドレスメモリ内の指示と比較することを特徴とする請求項1から請求項8のいずれか1項に記載のシステム。
【請求項10】
各スレッドが、特定の書込アドレスメモリを有し、
スレッドに対する書込アドレスメモリ内の全てのエントリが、障壁がそのスレッドに対する前記要求待ち行列に追加された時に削除される、
ことを特徴とする請求項1から請求項9のいずれか1項に記載のシステム。
【請求項11】
前記障壁は、前記対応する読取要求が属する前記スレッドを識別するデータを含むことを特徴とする請求項1から請求項10のいずれか1項に記載のシステム。
【請求項12】
前記障壁は、前記適合指示が属する前記スレッドの前記要求待ち行列における既存の要求に添付された障壁サイドバンドデータを含むことを特徴とする請求項1から請求項11のいずれか1項に記載のシステム。
【請求項13】
前記適合指示が属する前記スレッドの前記要求待ち行列に要求が存在しない時に、前記障壁は、該要求待ち行列内に挿入された新しい要求に添付された障壁サイドバンドデータを含むことを特徴とする請求項1から請求項11のいずれか1項に記載のシステム。
【請求項14】
前記非一貫性検出モジュールは、前記適合指示が属する前記スレッドの前記要求待ち行列内に障壁を以前の障壁がそのスレッドに対して挿入されてからそのスレッドからの前記キャッシュメモリから要求が送信されていた場合にのみ挿入することを特徴とする請求項1から請求項13のいずれか1項に記載のシステム。
【請求項15】
プロセッサコア、複数のスレッドの各々によってアクセス可能なデータを記憶するキャッシュメモリ、該複数のスレッドによってアクセス可能なデータを記憶するメインメモリに接続されたメモリバス、及び各スレッドに対する書込アドレスメモリを含むマルチスレッドプロセッサにおけるスレッドによるグローバルメモリへのアクセスを制御する方法であって、
(a)各スレッドに対して、前記メインメモリへの各書込要求のメモリアドレスの指示を対応する書込アドレスメモリに記憶する段階、
(b)次の読取要求のメモリアドレスを他のスレッドの前記書込アドレスメモリのコンテンツと比較する段階、及び
(c)前記読取要求の前記メモリアドレスが書込アドレスメモリ内の指示に対応する場合に、前記対応する書込要求が属する前記スレッドの要求待ち行列内に障壁を挿入し、かつ対応する障壁が前記メインメモリによって受信されるまで、該読取要求が該メインメモリにアクセスすることを阻止する段階、
を含むことを特徴とする方法。
【請求項16】
スレッドに対する書込アドレスメモリ内の全てのエントリを障壁がそのスレッドの前記要求待ち行列に追加された時に削除する段階を更に含むことを特徴とする請求項15に記載の方法。
【請求項17】
前記障壁は、対応する読取要求が属するスレッドを識別するデータを含むことを特徴とする請求項15又は請求項16に記載の方法。
【請求項18】
前記障壁は、前記要求待ち行列における既存の要求に添付されたサイドバンドデータを含むことを特徴とする請求項15、請求項16、又は請求項17に記載の方法。
【請求項19】
適合指示が属するスレッドの前記要求待ち行列に要求がない時に、前記障壁は、該要求待ち行列内に挿入された新しい要求に添付された障壁サイドバンドデータを含むことを特徴とする請求項15から請求項18のいずれか1項に記載の方法。
【請求項20】
障壁をスレッドの要求待ち行列内に挿入する前記段階は、以前の障壁がそのスレッドに対して挿入されてからそのスレッドに対する前記キャッシュメモリから送信された要求が存在する場合にのみ実行されることを特徴とする請求項15から請求項19のいずれか1項に記載の方法。
【請求項21】
現在のタイムスタンプをどの要求にも添付する段階を更に含むことを特徴とする請求項15から請求項20のいずれか1項に記載の方法。
【請求項22】
読取要求の前記メモリアドレスが前記書込アドレスメモリ内の1つ又はそれよりも多くの指示に対応する毎に添付される前記タイムスタンプを更新する段階を更に含むことを特徴とする請求項21に記載の方法。
【請求項23】
サイドバンドデータを前記次の読取要求に添付する段階を更に含むことを特徴とする請求項15から請求項22のいずれか1項に記載の方法。
【請求項24】
前記サイドバンドデータは、それらのスレッドのリストを対応する障壁が挿入された前記要求待ち行列内に含め、
前記読取要求は、前記対応する障壁の全てがメモリアービターを通過した後にのみ前記メインメモリに通される、
ことを特徴とする請求項23に記載の方法。
【請求項25】
段階(c)は、サイドバンドデータが添付された読取要求以外の要求が、その要求に添付されたタイムスタンプが内部タイムスタンプカウンタに適合するまで前記メインメモリにアクセスすることを阻止する段階を更に含み、
添付されたサイドバンドデータを有する読取要求がメモリアービターを通過する度に前記内部タイムスタンプカウンタを更新する段階、
を更に含むことを特徴とする請求項23又は請求項24に記載の方法。
【請求項26】
段階(a)は、前記書込要求が属するアドレス範囲を前記書込アドレスメモリに記憶することによって各書込要求の前記メモリアドレスの指示を記憶する段階を含むことを特徴とする請求項15から請求項25のいずれか1項に記載の方法。
【請求項27】
段階(a)は、複数のアドレスを単一アドレス範囲として記憶する段階を含むことを特徴とする請求項26に記載の方法。
【図1】
【図2a】
【図2b】
【図3】
【図4a】
【図4b】
【図4c】
【図4d】
【図4e】
【図4f】
【図4g】
【図5】
【図6】
【図7】
【図2a】
【図2b】
【図3】
【図4a】
【図4b】
【図4c】
【図4d】
【図4e】
【図4f】
【図4g】
【図5】
【図6】
【図7】
【公表番号】特表2012−523055(P2012−523055A)
【公表日】平成24年9月27日(2012.9.27)
【国際特許分類】
【出願番号】特願2012−504076(P2012−504076)
【出願日】平成22年4月7日(2010.4.7)
【国際出願番号】PCT/GB2010/000727
【国際公開番号】WO2010/116151
【国際公開日】平成22年10月14日(2010.10.14)
【出願人】(501176037)イマジネイション テクノロジーズ リミテッド (59)
【Fターム(参考)】
【公表日】平成24年9月27日(2012.9.27)
【国際特許分類】
【出願日】平成22年4月7日(2010.4.7)
【国際出願番号】PCT/GB2010/000727
【国際公開番号】WO2010/116151
【国際公開日】平成22年10月14日(2010.10.14)
【出願人】(501176037)イマジネイション テクノロジーズ リミテッド (59)
【Fターム(参考)】
[ Back to top ]