(57)【特許請求の範囲】
【請求項１】
複数のクライアントによってアクセス可能なキャッシュメモリシステムと、前記キャッシュメモリシステムは複数のキャッシュメモリバンクを含み、前記複数のキャッシュメモリバンクの各々のキャッシュメモリバンクは、
キャッシュメモリと、
前記複数のクライアントのうちの或るクライアントからのデータの要求が、前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによる要求の状態にかかわらず、前記キャッシュメモリによって満たされうるか否かを判断するように構成されたタグチェックユニットと、
を含み、
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数のペンディングバッファと、前記ペンディングバッファは、データの要求を前記複数のクライアントのうちの関連クライアントからの受信の順序にて記憶し、前記データの要求が前記キャッシュメモリによって満たされうるか否かの判断を保留するように構成され、
前記複数のクライアントに関連付けられた複数のデッドロック保護ユニットと、前記デッドロック保護ユニットは、前記ペンディングバッファ内の前記関連クライアントのための前記キャッシュメモリバンクに関するペンディングバッファが、前記関連クライアントによるすべての順序の狂ったデータの要求のデータサイズの合計を、同じキャッシュメモリバンク内の読み出しデータバッファのサイズと比較することに少なくとも部分的に基づいて、前記関連クライアントからの追加のデータの要求を受け付けることができるか否かを判断するように構成され、前記デッドロック保護ユニットは、前記ペンディングバッファが前記追加のデータの要求を受け付けることができるか否かの前記判断に少なくとも部分的に基づいて、前記追加の要求を受け付けることが前記複数のキャッシュメモリバンクの間にデッドロックの状況を引き起こす場合に、前記ペンディングバッファが前記追加の要求を受け付けることを阻止するようにさらに構成され、
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数の読み出しデータバッファと、前記読み出しデータバッファは、前記関連クライアントによって要求された前記キャッシュメモリからのデータを、前記ペンディングバッファ内の前記関連クライアントに関連付けられたペンディングバッファによる受信の前記順序に従って記憶するように構成され、
を備える、システム。
【請求項２】
前記複数のキャッシュメモリバンクの各々は、
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数のリターンバッファ、前記リターンバッファは、前記タグチェックユニットが、前記データの要求が前記キャッシュメモリによって満たされうるか否かを判断した後で、前記複数のクライアントのうちの前記関連クライアントからの前記データの要求を記憶するように構成され、
をさらに含む、請求項１に記載のシステム。
【請求項３】
前記関連クライアントのための前記ペンディングバッファは、前記関連クライアントによるすべての順序の狂ったデータの要求のデータサイズの前記合計が、同じキャッシュメモリバンク内の前記読み出しデータバッファの前記サイズよりも小さい場合に、前記関連クライアントからの前記追加のデータの要求を受け付けることができる、請求項１に記載のシステム。
【請求項４】
前記複数のデッドロック保護ユニットの各々は、前記関連クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファを含む、請求項３に記載のシステム。
【請求項５】
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数の書き込みデータバッファ、前記書き込みデータバッファは、前記キャッシュメモリにデータを書き込むために前記関連クライアントからの書き込み要求を受信するように構成され、
をさらに備える、請求項１に記載のシステム。
【請求項６】
前記キャッシュメモリは、前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記複数のバッファに記憶された前記データの要求をサービスするように構成されている、請求項２に記載のシステム。
【請求項７】
クライアントからのデータの要求を、第１のキャッシュメモリバンクに関する前記クライアントに関連付けられたペンディングバッファに記憶することと、
前記データの要求の各々が、第２のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記第１のキャッシュメモリバンク内のキャッシュメモリによって満たされうるか否かを判断することと、
前記クライアントによるすべての順序の狂ったデータの要求のデータサイズの合計を、前記第１のキャッシュメモリバンク内の読み出しデータバッファのサイズと比較することに少なくとも部分的に基づいて、前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断することと、
前記ペンディングバッファが前記追加のデータの要求を受け付けることができるか否かの前記判断に少なくとも部分的に基づいて、前記追加の要求を受け付けることが前記第１のキャッシュメモリバンクと前記第２のキャッシュメモリバンクとの間にデッドロックの状況を引き起こす場合に、前記ペンディングバッファが前記追加の要求を受け付けることを阻止することと、
前記クライアントによって要求された前記キャッシュメモリからのデータを、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられた前記読み出しデータバッファによって、前記ペンディングバッファにおける前記データの要求の受信の順序に従って記憶することと
を備える、方法。
【請求項８】
前記データの要求の各々が前記キャッシュメモリによって満たされうるか否かを判断した後に、前記クライアントからの前記データの要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられたリターンバッファによって記憶すること
をさらに備える、請求項７に記載の方法。
【請求項９】
前記第１のキャッシュメモリバンクによって前記クライアントから受信されたすべての順序の狂ったデータの要求のデータサイズの前記合計が、前記読み出しデータバッファの前記サイズよりも小さい場合に、前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができると判断すること
をさらに備える、請求項７に記載の方法。
【請求項１０】
前記ペンディングバッファが追加の要求を受け付けることができると判断することは、前記クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファに少なくとも部分的に基づく、請求項９に記載の方法。
【請求項１１】
前記キャッシュメモリにデータを書き込むために前記クライアントからの書き込み要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられた書き込みデータバッファによって受信すること
をさらに備える、請求項７に記載の方法。
【請求項１２】
前記第１および第２のキャッシュメモリバンクの内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記リターンバッファに記憶された前記データの要求を前記キャッシュメモリによってサービスすること
をさらに備える、請求項８に記載の方法。
【請求項１３】
第１のキャッシュメモリバンクに関するクライアントからのデータの要求を記憶するための手段と、
前記データの要求の各々が、第２のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断するための手段と、
前記データの要求を記憶するための手段が、前記クライアントによるすべての順序の狂ったデータの要求のデータサイズの合計を、前記第１のキャッシュメモリバンク内の読み出しデータバッファのサイズと比較することに少なくとも部分的に基づいて、前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断するための手段と、
前記データの要求を記憶するための手段が前記追加のデータの要求を受け付けることができるか否かの前記判断に少なくとも部分的に基づいて、前記追加の要求を受け付けることが前記第１のキャッシュメモリバンクと前記第２のキャッシュメモリバンクとの間にデッドロックの状況を引き起こす場合に、前記データの要求を記憶するための手段が前記追加の要求を受け付けることを阻止するための手段と、
前記第１のキャッシュメモリバンクに関する前記クライアントによって要求された前記キャッシュメモリからのデータを記憶するための手段と、前記クライアントによって要求された前記キャッシュメモリからのデータを記憶するための手段は、前記読み出しデータバッファであり、
を備える、装置。
【請求項１４】
前記クライアントからの、前記キャッシュメモリによって満たされ得なかったデータの要求を記憶するための手段
をさらに備える、請求項１３に記載の装置。
【請求項１５】
前記データの要求を記憶するための手段が前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断するための前記手段は、
前記クライアントによるすべての順序の狂ったデータの要求のデータサイズの前記合計が、前記要求された前記キャッシュメモリからのデータを記憶するための手段の前記サイズよりも小さい場合に、前記データの要求を記憶するための手段が前記クライアントからの追加のデータの要求を受け付けることができると判断するための手段
を備える、請求項１３に記載の装置。
【請求項１６】
前記データの要求を受信するための手段が前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断するための前記手段は、
前記クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファ
を含む、請求項１５に記載の装置。
【請求項１７】
前記キャッシュメモリにデータを書き込むための前記クライアントからの書き込み要求を受信するための手段
をさらに備える、請求項１３に記載の装置。
【請求項１８】
前記第１および第２のキャッシュメモリバンクの内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記クライアントからの、前記キャッシュメモリによって満たされ得なかったデータの要求を記憶するための手段に記憶された前記データの要求を、前記キャッシュメモリによってサービスするための手段
をさらに備える、請求項１４に記載の装置。
【請求項１９】
メモリと、
前記メモリに接続され、
第１のキャッシュメモリバンクに関するクライアントからのデータの要求を記憶し、
前記データの要求の各々が、第２のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断し、
前記クライアントによるすべての順序の狂ったデータの要求のデータサイズの合計を、前記第１のキャッシュメモリバンク内の読み出しデータバッファのサイズと比較することに少なくとも部分的に基づいて、前記クライアントからの前記データの要求を記憶するペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断し、
前記ペンディングバッファが前記追加のデータの要求を受け付けることができるか否かの前記判断に少なくとも部分的に基づいて、前記追加の要求を受け付けることが前記第１のキャッシュメモリバンクと前記第２のキャッシュメモリバンクとの間にデッドロックの状況を引き起こす場合に、前記ペンディングバッファが前記追加の要求を受け付けることを阻止し、
前記第１のキャッシュメモリバンクに関する前記クライアントによって要求された前記キャッシュメモリからのデータを記憶する
ように構成された１つ以上のプロセッサと、
を備える、装置。
【請求項２０】
前記１つ以上のプロセッサは、
前記データの要求の各々が前記キャッシュメモリによって満たされうるか否かを判断した後で、前記クライアントからの前記データの要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられたリターンバッファに記憶する
ようにさらに構成されている、請求項１９に記載の装置。
【請求項２１】
前記１つ以上のプロセッサは、
前記第１のキャッシュメモリバンクによって前記クライアントから受信されるすべての順序の狂ったデータの要求のデータサイズの前記合計が、前記読み出しデータバッファの前記サイズよりも小さい場合に、前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができると判断する
ようにさらに構成されている、請求項１９に記載の装置。
【請求項２２】
前記ペンディングバッファが追加の要求を受け付けることができると判断することは、前記クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファに少なくとも部分的に基づく、請求項２１に記載の装置。
【請求項２３】
前記１つ以上のプロセッサは、
前記キャッシュメモリにデータを書き込むために前記クライアントからの書き込み要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられた書き込みデータバッファによって受信する
ようにさらに構成されている、請求項１９に記載の装置。
【請求項２４】
前記１つ以上のプロセッサは、
前記第１および第２のキャッシュメモリバンクの内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記リターンバッファに記憶された前記データの要求を、前記キャッシュメモリによってサービスする
ようにさらに構成されている、請求項２０に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本開示は、概して、コンピュータシステムに関し、さらに詳しくは、キャッシュメモリシステムに関する。
【背景技術】
【０００２】
[0002]コンピュータシステムにおけるキャッシュメモリシステムは、典型的には、比較的小さいかつ低いレイテンシ（latency）メモリを提供する。このようなキャッシュメモリは、データへのアクセスの平均時間を減らすために、メインメモリに記憶されたデータのサブセット（subset）のコピーを記憶する。複数のクライアントが同時にキャッシュメモリシステムへのアクセスを試みるとき、コンフリクト（conflicts）が生じる可能性がある。
【０００３】
[0003]複数のクライアント間のコンフリクトを減らすための１つの技法は、複数のクライアントがそれぞれ同時にキャッシュメモリシステム内の異なるキャッシュメモリバンクにアクセスされうるように、キャッシュメモリシステムを、各々がキャッシュメモリシステム内のデータの一部を含む複数のキャッシュメモリバンクに分割することを含むことができ、それによってクライアント間のコンフリクトを減らし、キャッシュメモリシステムのスループットを向上させる。しかしながら、依然としてコンフリクトが高い割合で生じ得、それによってキャッシュメモリシステムのスループットを低下させる。
【発明の概要】
【０００４】
[0004]一般に、本開示は、複数のクライアントによってアクセス可能なマルチバンクキャッシュメモリシステム（multi-bank cache memory systems）のスループットを向上させるための技法を説明する。各々のメモリバンクにおいて各々のクライアントに関するバッファのセットを使用することにより、本開示の技法は、複数のクライアントが同時にキャッシュメモリシステムの同じメモリバンクに要求を送る（dispatch）ことを可能にでき、それによってクライアント間のコンフリクトを減らすことができる。さらに、本開示の技法は、クライアントによって送られたデータの要求が、キャッシュシステムのメモリバンク間で順序どおりでなく（out of order）サービスされる（be serviced）ことを可能にし、それによってメモリバンク間のバンクコンフリクトを減らし、マルチバンクキャッシュメモリシステムのスループットを向上させる。
【０００５】
[0005]一例においては、方法が、クライアントからのデータの要求を、第１のキャッシュメモリバンクのためにクライアントに関連付けられたペンディングバッファ（pending buffer）に記憶することを含むことができる。本方法は、データの要求の各々が、第２のキャッシュメモリバンクにおけるクライアントによるデータの要求の状態にかかわらず、第１のキャッシュメモリバンク内のキャッシュメモリによって満たされうるか否かを、判断することをさらに含むことができる。本方法は、クライアントによって要求されたキャッシュメモリからのデータを、第１のキャッシュメモリバンクのためにクライアントに関連付けられた読み出しデータバッファによって、ペンディングバッファにおけるデータの要求の受信の順序に従って記憶することをさらに含むことができる。
【０００６】
[0006]別の例では、システムが、複数のクライアントによってアクセス可能なキャッシュメモリシステムを含むことができ、このキャッシュメモリシステムは、複数のキャッシュメモリバンクを含み、これら複数のキャッシュメモリバンクの各々は、キャッシュメモリと、複数のクライアントのうちの或るクライアントからのデータの要求が、複数のキャッシュメモリバンクのうちの別のキャッシュメモリバンクにおけるクライアントによる要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断するように構成されたタグチェックユニットと、を含む。本システムは、複数のキャッシュメモリバンクのための複数のクライアントに関連付けられた複数のペンディングバッファをさらに含むことができ、これらペンディングバッファは、データの要求を複数のクライアントのうちの関連クライアントからの受信の順序にて記憶し、データの要求がキャッシュメモリによって満たされうるか否かの判断を保留する（pending）ように構成される。本システムは、複数のキャッシュメモリバンクのために複数のクライアントに関連付けられた複数の読み出しデータバッファをさらに含むことができ、これら読み出しデータバッファは、関連クライアントによって要求されたキャッシュメモリからのデータを、ペンディングバッファ内の関連クライアントに関連付けられたペンディングバッファによる受信の順序に従って記憶するように構成される。
【０００７】
[0007]別の例では、装置が、第１のキャッシュメモリバンクに関するクライアントからのデータの要求を記憶するための手段を含むことができる。本装置は、データの要求の各々が、第２のキャッシュメモリバンクにおけるクライアントによるデータの要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断するための手段をさらに含むことができる。本装置は、第１のメモリバンクのためのクライアントによって要求されたキャッシュメモリからのデータを記憶するための手段をさらに含むことができる。
【０００８】
[0008]別の例では、装置が、１つ以上のプロセッサを含むことができる。この１つ以上のプロセッサは、第１のキャッシュメモリバンクに関するクライアントからのデータの要求を記憶するように構成されうる。この１つ以上のプロセッサは、データの要求の各々が、第２のキャッシュメモリバンクにおけるクライアントによるデータの要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断するようにさらに構成されうる。この１つ以上のプロセッサは、第１のメモリバンクに関するクライアントによって要求されたキャッシュメモリからのデータを記憶するようにさらに構成されうる。
【０００９】
[0009]１または複数の例の詳細が、添付図面および以下の説明において述べられる。他の特徴、目的、および利点が、説明と図面から、および特許請求の範囲から明らかになるだろう。
【図面の簡単な説明】
【００１０】
【図１】[0010]図１は、本開示のいくつかの態様による、例示的なプロセッサと、例示的なキャッシュメモリシステムと、例示的なメインメモリとを含む例示的なコンピュータシステムを示すブロック図である。
【図２】[0011]図２は、本開示のいくつかの態様による、例示的なクライアントと、例示的なキャッシュメモリシステムとを含む例示的なコンピュータシステムを示すブロック図である。
【図３】[0012]図３は、本開示のいくつかの態様による、例示的なキャッシュメモリシステムにおけるデッドロックを解消するための例示的な技法を示すブロック図である。
【図４】[0013]図４は、本開示のいくつかの態様による、例示的なキャッシュメモリシステムにおいてデッドロックを解消するために使用される例示的なデータ構造を示す概念図である。
【図５】[0014]図５は、本開示のいくつかの態様による、複数のクライアントによってアクセス可能なマルチバンクキャッシュメモリシステムのスループットを向上させるための例示的な方法を示すフロー図である。
【発明を実施するための形態】
【００１１】
[0015]一般に、本開示は、複数のクライアントによってアクセス可能なマルチバンクキャッシュメモリシステムのスループットを向上させるための技法を説明する。マルチバンクキャッシュメモリシステムは、クライアントが同時にキャッシュメモリシステムの異なるキャッシュメモリバンクにアクセスできるようにすることで、キャッシュメモリシステムのクライアント間のコンフリクトを減らすことができるが、複数のクライアントが同時にキャッシュメモリシステムの同じキャッシュメモリバンクにアクセスしようと試みる場合に、クライアント間のコンフリクトが依然として生じうる。
【００１２】
[0016]各々のメモリバンクに関する各々のクライアントにバッファのセットを関連付けることによって、本開示の技法は、マルチバンクメモリバンクシステムの単一のメモリバンクが同時に複数のクライアントから要求を受け付けることを可能にし得、それによってクライアント間のコンフリクトを減らすことができる。さらに、本開示の技法は、クライアントによって送信されたデータの要求が、キャッシュシステムのメモリバンク間で順序どおりでなくサービスされることを可能することで、メモリバンク間のバンクコンフリクトを減らし、マルチバンクキャッシュメモリシステムのスループットを向上させることができる。シミュレーションにおいて、４つのキャッシュメモリバンクを含み、４つのクライアントをサービスするマルチバンクキャッシュメモリシステムは、本開示の技法を使用することによって、キャッシュメモリスループットをランダムアクセスにおいて４３％から９７％へと改善することができる。
【００１３】
[0017]マルチバンクキャッシュメモリシステムにアクセスするクライアントはそれぞれ、キャッシュメモリシステムの各々のキャッシュメモリバンクのためのペンディングバッファに関連付けられうる。キャッシュメモリシステム内の特定のキャッシュメモリバンクへとクライアントによって送られる要求は、この特定のキャッシュメモリバンクに関するクライアントに関連付けられたペンディングバッファに記憶されうる。複数のクライアントから同じキャッシュメモリバンクに送られた要求は、このキャッシュメモリバンクに関する各々のクライアントに関連付けられた別々のペンディングバッファに記憶されうる。
【００１４】
[0018]クライアントから単一のキャッシュメモリバンクに送られた要求は、クライアントからの受信の順序で処理されうる。要求を処理することは、リクエストをタグチェックすることを含むことができ、あるいはキャッシュメモリバンク内のキャッシュメモリが要求を満たすことができるか否かを他の方法で判断することを含むことができる。しかしながら、キャッシュシステムへとクライアントによって送られた要求は、全体としては、受信の順序に対して狂った順序で（out of order）処理されうる。例えば、クライアントは、第１のキャッシュメモリバンクへと第１の要求および第２の要求を順に送ることができ、その後に第２のキャッシュメモリバンクに第３の要求を送ることができる。第１のキャッシュメモリバンクにおいて第１の要求が第２の要求の前に処理されうるように、要求は単一のキャッシュメモリバンク内で順に処理されうるが、全体としては、第１の要求または第２の要求が第１のキャッシュメモリバンク内で処理される前に、第３の要求が第２のキャッシュメモリバンク内で処理されるように、要求が狂った順序で処理される可能性がある。
【００１５】
[0019]さらに、マルチバンクキャッシュメモリシステムにアクセスするクライアントはそれぞれ、キャッシュメモリシステムの各々のキャッシュメモリバンクのための読み出しデータバッファに関連付けられうる。クライアントによって要求されたデータは読み出され得、特定のキャッシュメモリバンクに関するクライアントに関連付けられた読み出しデータバッファに記憶されうる。複数のクライアントによって要求された同じキャッシュメモリバンク内のデータは、このキャッシュメモリバンクに関する各々のクライアントに関連付けられた別々の読み出しデータバッファに記憶されうる。
【００１６】
[0020]クライアントは、要求されたデータを読み出すために、キャッシュメモリバンクのための自身に関連する読み出しデータバッファを読み出すことができる。クライアントは、キャッシュメモリバンクの各々に要求が送られた順序のトラック（track）を保持することができ、この順序に基づいて、クライアントが、要求されたデータを、データに対応する要求が送られたのと同じ順序で受信することができるように、キャッシュメモリバンクの各々のための読み出しデータバッファから読み出しを行うことができる。
【００１７】
[0021]図１は、本開示のいくつかの態様による、例示的なプロセッサと、例示的なキャッシュメモリシステムと、例示的なメインメモリとを含む例示的なコンピュータシステムを示すブロック図である。図１に示されるとおり、コンピュータシステム１００は、プロセッサ１１６と、キャッシュメモリシステム１０２と、メインメモリ１０８とを含むことができ、これらはすべて互いに動作可能に接続されうる。
【００１８】
[0022]プロセッサ１１６は、機能を実装し、さらに／あるいはコンピュータシステム１００内で実行のための命令を処理するように、構成されてよい。プロセッサ１１６は、いくつかの例では、中央演算処理装置、グラフィックス処理システム内のグラフィックス処理ユニット、などのマイクロプロセッサであってよい。プロセッサ１１６は、クライアント１０６Ａ〜１０６Ｎ（「クライアント１０６」）を含むことができる。クライアント１０６は、キャッシュメモリシステム１０２からデータを要求し、キャッシュメモリシステム１０２にデータを書き込み、キャッシュメモリシステム１０２からデータを受信するように構成されたプロセッサ１１６の任意のモジュールまたはコンポーネントを含むことができる。例えば、クライアント１０６は、グラフィックス処理ユニットのレンダリングパイプライン（rendering pipelines）または中央演算処理装置のインストラクションパイプライン（instruction pipelines）など、プロセッサ１１６のパイプラインを含むことができる。クライアント１０６は、いくつかの例では、プロセッサ１１６上で実行するように動作可能であるアプリケーションなどのソフトウェアであってもよい。いくつかの例では、コンピュータシステム１００内の１つ以上のプロセッサ（プロセッサ１１６など）が、クライアント１０６およびキャッシュメモリシステム１０２のサブコンポーネント（sub-components）を含むクライアント１０６およびキャッシュメモリシステム１０２の動作を指揮（direct）および制御するように構成されてよい。
【００１９】
[0023]キャッシュメモリシステム１０２は、動作中にコンピュータシステム１００内に情報を記憶でき、メインメモリ１０８のためのデータをキャッシュするように構成されてよく、キャッシュメモリシステム１０２が、メインメモリ１０８と比べてより高速なデータへのアクセスをクライアント１０６に提供できるように、メモリの階層（memory hierarchy）においてメインメモリ１０８よりもクライアント１０６に近くてよい。キャッシュメモリシステム１０２は、クライアント１０６にとってキャッシュメモリシステム１０２からのデータの読み出しがメインメモリ１０８と比べてより高速になりうるように、通常はメインメモリ１０８と比べてより高速なアクセス時間およびより低いレイテンシを有することができる。
【００２０】
[0024]キャッシュメモリシステム１０２は、キャッシュメモリバンク１０４Ａ〜１０４Ｎ（「キャッシュメモリバンク１０４」）を含むことができる。キャッシュメモリバンク１０４は、スタティックランダムアクセスメモリ（static random access memory）（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（dynamic random access memory）（ＤＲＡＭ）、ＳＲＡＭとＤＲＡＭとの組み合わせ、あるいは任意の他の適切なランダムアクセスメモリを含むことができる。キャッシュメモリバンク１０４の各々は、メインメモリ１０８内の各アドレスが、キャッシュメモリバンク１０４のうちの１つに関連付けられうるように、メインメモリ１０８内のアドレスの一部のためのキャッシュとして機能（act）しうる。キャッシュメモリシステム１０２を複数のキャッシュメモリバンク１０４に分割することによって、クライアント１０６のうちの複数のクライアントが、並行してキャッシュメモリシステム１０２にアクセスすることができる。
【００２１】
[0025]キャッシュメモリバンク１０４の各々が、ペンディングバッファ１１０Ａ〜１１０Ｎ（「ペンディングバッファ１１０」）を含むことができる。キャッシュメモリバンク１０４のうちの１つのキャッシュメモリバンク内のペンディングバッファ１１０の各々が、クライアント１０６のうちの各クライアントに関連付けられうるように、クライアント１０６のうちの各々のクライアントが、キャッシュメモリバンク１０４の各々の内のペンディングバッファ１１０のうちの或るペンディングバッファに関連付けられてよい。
【００２２】
[0026]キャッシュメモリバンク１０４の各々のキャッシュメモリバンクは、キャッシュメモリ１１２および読み出しデータバッファ１１４Ａ〜１１４Ｎ（「読み出しデータバッファ１１４」）をさらに含むことができる。キャッシュメモリバンク１０４のうちの１つのキャッシュメモリバンク内の読み出しデータバッファ１１４の各々が、やはりクライアント１０６のうちの各々のクライアントに関連付けられうるように、クライアント１０６のうちの各クライアントが、キャッシュメモリバンク１０４の各々のための読み出しデータバッファ１１４のうちの或る読み出しデータバッファに関連付けられうる。
【００２３】
[0027]クライアント１０６のうちの或るクライアントが、キャッシュメモリバンク１０４のうちの１つに、データの要求を送信することができる。一例においては、データの要求はそれぞれ、メインメモリ１０８内のデータの位置を示すメモリアドレスを含むことができる。データの要求は、データの要求が満たされうるまで、ペンディングバッファ１１０のうちのクライアントに関連付けられたペンディングバッファにおいて待ち行列に入れられうる（be queued）。クライアント１０６は、キャッシュメモリ１１２がデータの要求を満たすことができるかどうかを判断すべくキャッシュメモリ１１２にアクセスするために、互いに調停を行う（arbitrate）ことができる。いくつかの例では、キャッシュメモリ１１２は、キャッシュメモリ１１２が要求されたデータを含む場合に、データの要求を満たしうる。キャッシュメモリ１１２がデータの要求を満たすことができない場合、データはメインメモリ１０８から読み出され得、キャッシュメモリ１１２内に記憶されうる。データの要求がキャッシュメモリ１１２またはメインメモリ１０８のいずれかによって満たされた後で、要求されたデータがクライアントに戻される準備ができるまで、キャッシュメモリバンクによってデータの要求が受信されたのと同じ順序で、読み出しデータバッファ１１４のうちのクライアントに関連付けられた読み出しデータバッファにおいて待ち行列に入れられうる。要求されたデータは、クライアントによってキャッシュメモリバンク１０４へデータの要求が送られたのと同じ順序で、キャッシュメモリバンク１０４によってクライアントに戻されうる。
【００２４】
[0028]図２は、本開示のいくつかの態様による、例示的なクライアント（図１に示したクライアント１０６のうちの１つなど）と、例示的なキャッシュメモリシステム（図１に示したキャッシュメモリシステム１０２など）とを含む例示的なコンピュータシステム（図１に示したコンピュータシステム１００など）を説明するブロック図である。図２に示されるとおり、コンピュータシステム２００は、クライアント２２０と、キャッシュメモリシステム２０２とを含むことができる。コンピュータシステム２００は、グラフィックス処理システムを備えることができ、クライアント２２０は、グラフィックス処理システムのレンダリングパイプラインであってよい。
【００２５】
[0029]キャッシュメモリシステム２０２は、キャッシュメモリバンク２０４Ａおよび２０４Ｂを含むことができる。キャッシュメモリシステム２０２が、２つのキャッシュメモリバンク２０４Ａおよび２０４Ｂを含むものとして示されているが、本開示の技法は、任意の数のキャッシュメモリバンクを含むキャッシュメモリシステムを実装するために使用されうる。
【００２６】
[0030]クライアント２２０は、キャッシュメモリシステム２０２内の各々のキャッシュメモリバンクのための書き込みデータバッファに関連付けられうる。図示の例では、クライアント２２０は、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれてよい書き込みデータバッファ２１２Ａおよび２１２Ｂに関連付けられうる。いくつかの例では、書き込みデータバッファ２１２Ａおよび２１２Ｂが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれなくてよいが、代わりにクライアント２２０またはコンピュータシステム２００のどこかに含まれてよい。図２によって説明される例は、キャッシュメモリバンク２０４Ａのための単一の書き込みデータバッファ２１２Ａおよびキャッシュメモリバンク２０４Ｂのための単一の書き込みデータバッファ２１２Ｂを含むが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂはそれぞれ、キャッシュメモリシステム２０２にアクセスする各々のクライアントに関する書き込みデータバッファを含んでもよく、あるいはキャッシュメモリシステム２０２にアクセスする各々のクライアントに関する書き込みデータバッファに関連付けられてもよい。
【００２７】
[0031]書き込みデータバッファ２１２Ａおよび２１２Ｂはそれぞれ、クライアント２２０からそれぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに送られた書き込み要求を、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂへ送られた順序にて記憶して待ち行列に入れるように構成されうる。書き込み要求は、メモリ位置（memory location）の表示（indication）およびデータを含むことができ、書き込み要求に含まれるデータが書き込み要求に含まれるメモリ位置の表示に対応するキャッシュメモリ位置にてそれぞれのキャッシュメモリ２１０Ａおよび２１０Ｂに書き込まれるまで、書き込みデータバッファ２１２Ａおよび２１２Ｂによって記憶されてよい。
【００２８】
[0032]クライアント２２０は、キャッシュメモリシステム２０２内の各々のキャッシュメモリバンクのペンディングバッファに関連付けられうる。図示の例では、クライアント２２０は、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれてよいペンディングバッファ２０６Ａおよび２０６Ｂに関連付けられうる。いくつかの例では、ペンディングバッファ２０６Ａおよび２０６Ｂが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれなくてよいが、代わりにクライアント２２０またはコンピュータシステム２００のどこかに含まれてよい。図２によって説明される例は、キャッシュメモリバンク２０４Ａのための単一のペンディングバッファ２０６Ａおよびキャッシュメモリバンク２０４Ｂのための単一のペンディングバッファ２０６Ｂを含むが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂはそれぞれ、キャッシュメモリシステム２０２にアクセスする各々のクライアントに関するペンディングバッファを含んでもよく、あるいはキャッシュメモリシステム２０２にアクセスする各々のクライアントに関するペンディングバッファに関連付けられてもよい。
【００２９】
[0033]ペンディングバッファ２０６Ａおよび２０６Ｂはそれぞれ、クライアント２２０からそれぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに送られたデータの要求を、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂにおける受信の順序にて記憶して待ち行列に入れるように構成されうる。データの要求は、ペンディングバッファ２０６Ａおよび２０６Ｂによって記憶され得、ペンディングバッファ２０６Ａおよび２０６Ｂによって記憶されたデータの要求の各々がキャッシュメモリ２１０Ａおよびキャッシュメモリ２１０Ｂによってそれぞれ満たされうるか否かの判断を保留する。いくつかの例では、要求されたデータがそれぞれのキャッシュメモリ２１０Ａおよびキャッシュメモリ２１０Ｂ内に記憶されている場合に、キャッシュメモリ２１０Ａおよびキャッシュメモリ２１０Ｂが、データの要求を満たしうる。
【００３０】
[0034]クライアント２２０は、デッドロック保護ユニット２４２にも関連付けられうる。デッドロック保護ユニット２４２は、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアとの組み合わせによって実装され得、クライアント２２０に関連付けられたペンディングバッファ２０６Ａおよび２０６Ｂの各々がクライアント２２０から追加のデータの要求を受け付けることができるか否かを、追加の要求を受け付けることがキャッシュメモリバンク２０４Ａおよび２０４Ｂの間にデッドロックの状況を引き起こしうるか否かに少なくとも部分的に基づいて、判断するように構成されうる。デッドロック保護ユニット２４２などのデッドロック保護ユニットの詳細は、図３および図４に関してさらに詳しく後述される。
【００３１】
[0035]キャッシュメモリバンク２０４Ａおよび２０４Ｂは、それぞれのタグチェックユニット２０８Ａおよび２０８Ｂを含むことができる。タグチェックユニット２０８Ａおよび２０８Ｂは、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアとの組み合わせによって実装され得、それぞれのペンディングバッファ２０６Ａおよび２０６Ｂ内のデータの要求の各々がそれぞれのキャッシュメモリ２１０Ａおよび２１０Ｂによって満たされうるか否かを判断するように構成されうる。典型的には、キャッシュ内の各々のキャッシュブロックは、タグによってラベル付けされ（be labeled）得、タグは、通常は、キャッシュブロックに対応する、メインメモリ内のアドレスのうちの部分を含むことができる。タグチェックユニット２０８Ａおよび２０８Ｂは、メモリアドレスの少なくとも一部がそれぞれのキャッシュメモリ２１０Ａおよび２１０Ｂ内のキャッシュブロックのタグと一致するかどうかを判断するために、データの要求に含まれるメモリアドレスの少なくとも一部を、それぞれのキャッシュメモリ２１０Ａおよび２１０Ｂ内のキャッシュブロックのタグと比較しうる。メモリアドレスの少なくとも一部がキャッシュブロックのタグに一致する場合、要求されたデータは、キャッシュメモリのキャッシュブロックに位置付けられ（be located）うる。データの要求は、関連キャッシュメモリバンク内のキャッシュメモリによって満たされ得ない場合、キャッシュメモリは、要求されたデータをメインメモリ（図示されていない）に照会し（query）得、要求されたデータで自身を更新することができる。キャッシュメモリ２１０Ａおよび２１０Ｂは、インストラクションキャッシュ、データキャッシュ、あるいはメインメモリ（図示されていない）と比べてより高速なデータへのアクセスをクライアント２２０に提供するためにアクセスの局所性（locality）を利用するように管理される（managed）任意の他のメモリまたは記憶装置であってよい。
【００３２】
[0036]それぞれのペンディングバッファ２０６Ａおよび２０６Ｂ内に記憶されたデータの要求は、それぞれのタグチェックユニット２０８Ａおよび２０８Ｂによって、単一のキャッシュメモリバンク内の要求が順にタグチェックされるように、先入れ先出しの方法で（in a first-in-first-out fashion）タグチェックされうる。単一のキャッシュメモリバンク内の要求は順にタグチェックされうるが、いくつかのキャッシュメモリバンク内で要求がタグチェックされる順序は、クライアント２２０によるキャッシュメモリシステム２０２への要求が送信される順序に対して、順序が狂う（out of order）可能性がある。例えば、クライアント２２０は、第１のデータの要求をキャッシュメモリバンク２０４Ａに送ることができ、次いで第２のデータの要求をキャッシュメモリバンク２０４Ｂに送ることができる。しかしながら、キャッシュメモリバンク２０４Ｂ内のタグチェックユニット２０８Ｂが、タグチェックユニット２０８Ａが第１のデータの要求をタグチェックすることができるよりも前に、第２のデータの要求をタグチェックすることができるかもしれない。このように、キャッシュメモリバンク２０４Ａおよび２０４Ｂは、単一のキャッシュメモリバンクにおいては、クライアント２００から送られた要求を受信の順序でタグチェックすることができるが、他のキャッシュメモリバンクにおけるクライアント２００からの要求の状態にかかわらず、要求をキャッシュメモリシステム２０２内の他のキャッシュメモリバンクと比べて狂った順序でタグチェックする可能性がある。
【００３３】
[0037]クライアント２２０は、キャッシュメモリシステム２０２内の各々のキャッシュメモリバンクのリターンバッファにさらに関連付けられうる。いくつかの例では、リターンバッファが、キャッシュメモリによって満たされ得なかったデータの要求を、要求されたデータがメインメモリから取り出される（fetched）のを待つことができるように、バッファするために有用であってよい。図２によって示される例は、キャッシュメモリバンク２０４Ａについて単一のリターンバッファ２１４Ａおよびキャッシュメモリバンク２０４Ｂについて単一のリターンバッファ２１４Ｂを含むが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂはそれぞれ、キャッシュメモリシステム２０２にアクセスする各々のクライアントについてリターンバッファを含んでもよく、あるいはキャッシュメモリシステム２０２にアクセスする各々のクライアントについてリターンバッファに関連付けられてもよい。
【００３４】
[0038]図示の例では、クライアントは、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれてよいリターンバッファ２１４Ａおよび２１４Ｂに関連付けられうる。リターンバッファ２１４Ａおよび２１４Ｂはそれぞれ、クライアント２２０からのデータの要求を、それぞれのタグチェックユニット２０８Ａおよび２０８Ｂがデータの要求がそれぞれのキャッシュメモリ２１０Ａおよび２１０Ｂによって満たされうるか否かを判断した後で、記憶するように構成されうる。リターンバッファ２１４Ａおよび２１４Ｂは、データの要求を、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂによって受信されるのと同じ順序にて記憶して待ち行列に入れることができる。データの要求は、要求されたデータがキャッシュメモリ２１０Ａおよび２１０Ｂからアクセスされうるまで、リターンバッファ２１４Ａおよび２１４Ｂ内に残ることができる。
【００３５】
[0039]それぞれのリターンバッファ２１４Ａおよび２１４Ｂ内に記憶されたデータの要求は、単一のキャッシュメモリバンクにおける要求が順にサービスされるように先入れ先出しの方法で、それぞれのキャッシュメモリ２１０Ａおよび２１０Ｂによってサービスされうる。単一のキャッシュメモリバンク内の要求は順にサービスされうるが、いくつかのキャッシュメモリバンク内で要求がサービスされる順序は、クライアント２２０によってキャッシュメモリシステム２０２へ要求が送信された順序に対して、順序が狂う可能性がある。例えば、クライアント２２０は、第１のデータの要求をキャッシュメモリバンク２０４Ａに送信することができ、次いで第２のデータの要求をキャッシュメモリバンク２０４Ｂに送信することができる。タグチェックユニット２０８Ａが、第１のデータの要求がキャッシュメモリ２１０Ａによって現時点において満たされ得ない旨を知らせることができる一方で、タグチェックユニット２０８Ｂが、第１のデータの要求がキャッシュメモリ２１０Ｂによって満たされうる旨を知らせることができる。この例では、キャッシュメモリバンク２０４Ａが、第１のデータの要求によって要求されたデータがメインメモリから読み出されてキャッシュメモリ２１０Ａに記憶されるまで数サイクルを待たなければならないと考えられるがゆえに、キャッシュメモリバンク２０４Ｂが、キャッシュメモリバンク２０４Ａが第１の要求をサービスできるよりも前に、第２の要求をサービスできると考えられる。したがって、キャッシュメモリバンク２０４Ａおよび２０４Ｂは、単一のキャッシュメモリバンク内では、クライアント２００から送信された要求を受信の順序でサービスすることができるが、他のキャッシュメモリバンクにおけるクライアント２００からの要求の状態にかかわらず、キャッシュメモリシステム２０２内の他のキャッシュメモリバンクと比べて狂った順序で要求をサービスする可能性がある。
【００３６】
[0040]キャッシュメモリシステム２０２にアクセスするクライアントはそれぞれ、キャッシュメモリシステム２０２内の各々のキャッシュメモリバンクのための読み出しデータバッファに関連付けられうる。図２によって示される例は、キャッシュメモリバンク２０４Ａのための単一の読み出しデータバッファ２１８Ａおよびキャッシュメモリバンク２０４Ｂのための単一の読み出しデータバッファ２１８Ｂを含むが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂはそれぞれ、キャッシュメモリシステム２０２にアクセスする各々のクライアントについて読み出しデータバッファを含んでもよく、あるいはキャッシュメモリシステム２０２にアクセスする各々のクライアントについて読み出しデータバッファに関連付けられてもよい。
【００３７】
[0041]図示の例では、クライアント２２０は、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれてよい読み出しデータバッファ２１８Ａおよび２１８Ｂに関連付けられうる。いくつかの例では、読み出しデータバッファ２１８Ａおよび２１８Ｂが、それぞれのキャッシュメモリバンク２０４Ａおよび２０４Ｂに含まれなくてもよいが、代わりにクライアント２２０またはコンピュータシステム２００のどこかに含まれてよい。読み出しデータバッファ２１８Ａおよび２１８Ｂはそれぞれ、それぞれのキャッシュメモリ２１０Ａおよび２１０Ｂからのデータの要求によって要求されたデータを、それぞれのペンディングバッファ２０６Ａおよび２０６Ｂによるデータの要求の受信の順序に従って記憶して待ち行列に入れるように構成されうる。読み出しデータバッファ２１８Ａおよび２１８Ｂ内に記憶されたデータは、クライアント２２０によってキャッシュメモリシステム２０２へデータの要求が送信されたのと同じ順序で、クライアント２２０に返されうる。
【００３８】
[0042]読み出しデータバッファ２１８Ａおよび２１８Ｂは、クライアント２００によって送信されたデータの要求によって要求されたデータをバッファすることにより、デッドロック保護ユニット２４２との協働においてデッドロック保護を提供することもできる。読み出しデータバッファ２１８Ａおよび２１８Ｂなどの読み出しデータバッファによるデッドロック保護の詳細は、図３に関してさらに詳しく後述される。
【００３９】
[0043]クライアント２２０は、図１に示したクライアント１０６のうちの１つであってよい。クライアント２２０は、書き込み制御ユニット２２２、要求制御ユニット２２４、および読み出し制御ユニット２２６を含むことができる。書き込み制御ユニット２２２、要求制御ユニット２２４、および読み出し制御ユニット２２６の構成要素は、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアとの組み合わせを使用して実装されうる。図２によって示される例は、単一のクライアント２２０だけしか含んでいないが、コンピュータシステム２００は、１つ以上のクライアントを含むことができ、キャッシュメモリシステム２０２は、１つ以上のクライアントによってアクセスされうる。
【００４０】
[0044]要求制御ユニット２２４は、要求バッファ２３２およびデマルチプレクサ２３４を含むことができ、キャッシュメモリシステム２０２にデータの要求を送信するように構成されてよい。要求バッファ２３２は、データの要求を記憶して待ち行列に入れることができ、要求バッファ２３２は、データの要求ならびにキャッシュメモリバンクの表示（メモリアドレスまたはバンクＩＤなど）を、デマルチプレクサ２３４に送信することができる。キャッシュメモリバンクの表示（indication）に基づき、デマルチプレクサ２３４は、データの要求を適切なキャッシュメモリバンクに送信することができる。さらに、要求バッファ２３２は、読み出し制御ユニット２２６に送信されるすべての要求についてキャッシュメモリバンクの表示を送信することができる。
【００４１】
[0045]書き込み制御ユニット２２２は、キャッシュメモリシステム２０２に書き込み要求を送信するように構成されうる。書き込み制御ユニット２２２は、書き込み指令バッファ２２８およびデマルチプレクサ２３０を含むことができる。書き込み指令バッファ２２８は、書き込み要求を受信の順序にて記憶して待ち行列に入れることができ、書き込み要求ならびにキャッシュメモリバンクの表示（メモリアドレスまたはバンクＩＤなど）を、デマルチプレクサ２３０に送信することができる。キャッシュメモリバンクの表示に基づき、デマルチプレクサ２３０は、書き込み要求を適切なキャッシュメモリバンクに送信することができる。
【００４２】
[0046]読み出し制御ユニット２２６は、クライアント２２０によって要求されたデータをキャッシュシステム２０２から読み出すように構成されうる。読み出し制御ユニット２２６は、読み出し指令バッファ２３６、整列ユニット（alignment unit）２３８、およびマルチプレクサ２４０を含むことができる。読み出し指令バッファ２３６は、クライアント２２０の要求制御ユニット２２４によって発せられるデータの要求の各々について、データの要求が送られるキャッシュメモリバンクの表示（メモリアドレスまたはバンクＩＤなど）を受信して待ち行列に入れることができる。表示に基づき、マルチプレクサ２４０が、要求されたデータがクライアント２２０によってデータの要求が送信されたのと同じ順序でクライアント２２０によって受信されるように、適切なキャッシュメモリバンクから読み出しを行うことができる。
【００４３】
[0047]コンピュータシステム２００は、いくつかの例では、図１のプロセッサ１１６などの１つ以上のプロセッサを備えることができる。コンピュータシステム２００における１つ以上のプロセッサは、クライアント２２０およびキャッシュメモリシステム２０２の動作を指揮および制御するように構成されうる。したがって、コンピュータシステム２２０における１つ以上のプロセッサは、書き込み制御ユニット２２２、要求制御ユニット２２４、読み出し制御ユニット２２６、メモリバンク２０４Ａおよび２０４Ｂ、ペンディングバッファ２０６Ａおよび２０６Ｂ、タグチェックユニット２０８Ａおよび２０８Ｂ、キャッシュメモリ２１０Ａおよび２１０Ｂ、書き込みデータバッファ２１２Ａおよび２１２Ｂ、リターンバッファ２１４Ａおよび２１４Ｂ、ならびに読み出しデータバッファ２１８Ａおよび２１８Ｂの動作を指揮および制御するように構成されうる。
【００４４】
[0048]図３が、例示的なキャッシュメモリシステムにおいてデッドロックを解消するための例示的な技術を説明するブロック図である。図３に示されるとおりのデッドロックを解消するための例示的な技法は、図１に示したコンピュータシステム１００および図２に示したコンピュータシステム２００における使用のために適用可能であってよい。図３に示されるとおり、コンピュータシステム３００が、クライアント３０２Ａおよび３０２Ｂ、ならびにキャッシュメモリシステム３０４を含むことができる。コンピュータシステム３００は、グラフィックス処理システムを含むことができ、クライアント３０２Ａおよび３０４Ｂは、グラフィックス処理システムのためのレンダリングパイプラインであってよい。いくつかの例では、コンピュータシステム３００が、デッドロックの解消のための後述される例示的な技法を指揮および制御するように構成された１つ以上のプロセッサを含むことができる。
【００４５】
[0049]クライアント３０２Ａが、要求３２０Ａ、３２２Ａ、３２４Ａ、および３２６Ａをこの順番でキャッシュメモリシステム３０４に順に送信することができ、クライアント３０４Ｂが、要求３２０Ｂ、３２２Ｂ、３２４Ｂ、および３２６Ｂをこの順番でキャッシュメモリシステム３０４に順に送信することができる。要求３２２Ａおよび３２４Ａは、クライアント３０２Ａによってキャッシュメモリバンク３０６Ａに送信されてよく、ペンディングバッファ３０８Ａに記憶されてよい。要求３２０Ａおよび３２６Ａは、クライアント３０２Ａによってキャッシュメモリバンク３０６Ｂに送信されてよく、ペンディングバッファ３０８Ｂに記憶されてよい。要求３２０Ｂおよび３２６Ｂは、クライアント３０２Ｂによってキャッシュメモリバンク３０６Ａに送信されてよく、ペンディングバッファ３１０Ａに記憶されてよい。要求３２２Ｂおよび３２４Ｂは、クライアント３０２Ｂによってキャッシュメモリバンク３０６Ｂに送信されてよく、ペンディングバッファ３１０Ｂに記憶されてよい。
【００４６】
[0050]図３に示した例においては、クライアント３０２Ａおよび３０２Ｂによって送信される要求３２０Ａ、３２０Ｂ、３２２Ａ、３２２Ｂ、３２４Ａ、３２４Ｂ、３２６Ａ、および３２６Ｂの各々が、読み出し要求であってよく、キャッシュメモリ３１２Ａおよび３１２Ｂの同じセットインデックスを対象とする（target）ことができる。キャッシュメモリ３１２Ａおよび３１２Ｂはそれぞれ、２つのキャッシュラインスロットを含む２ウェイアソシアティブキャッシュ（two-way associative cache）であってよい。図３に示されるとおり、キャッシュメモリバンク３０６Ａ内のキャッシュメモリ３１２Ａが、クライアント３０２Ａによって送信された要求３２４Ａおよび３２２Ａをサービスすることができ、キャッシュメモリ３０６Ｂ内のキャッシュメモリ３１２Ｂが、クライアント３０４Ｂによって送信された要求３２２Ｂおよび３２４Ｂをサービスすることができる。ペンディングバッファ３０８Ａ、３１０Ａ内に記憶された要求は、要求３２４Ａおよび３２２Ａがキャッシュメモリ３１２Ａのキャッシュラインスロットをもはや占めなくなるまで、キャッシュメモリ３１２Ａによってサービスされなくてもよい。同様に、ペンディングバッファ３０８Ｂおよび３１０Ｂ内に記憶された要求も、要求３２２Ｂおよび３２４Ｂがキャッシュメモリ３１２Ｂのキャッシュラインスロットをもはや占めなくなるまで、キャッシュメモリ３１２Ｂによってサービスされなくてもよい。
【００４７】
[0051]キャッシュメモリ３１２Ａのキャッシュラインスロットを占めている要求３２４Ａおよび３２２Ａによって要求されたデータは、クライアント３０２Ａに戻され得ない。なぜならば、要求３２２Ａおよび３２４Ａは、クライアント３０２Ａによって要求３２０Ａの後に送信されており、要求３２０Ａによって要求されたデータが、未だクライアント３０２Ａに戻されていないからである。さらに、キャッシュメモリ３１２Ｂのキャッシュラインスロットを占めている要求３２４Ｂおよび３２２Ｂによって要求されたデータは、クライアント３０２Ｂに戻され得ない。なぜならば、要求３２２Ｂおよび３２４Ｂは、クライアント３０２Ｂによって要求３２０Ｂの後に送信されており、要求３２０Ｂによって要求されたデータが、未だクライアント３０２Ａに戻されていないからである。しかしながら、要求３２０Ａは、要求３２２Ｂおよび３２４Ｂがキャッシュメモリ３１２Ｂのキャッシュラインスロットを占めているため、依然としてペンディングバッファ３０８Ｂにあり、キャッシュメモリ３１２Ｂによってサービスされるのを待っており、要求３２０Ｂは、要求３２２Ａおよび３２４Ａがキャッシュメモリ３１２Ａのキャッシュラインスロットを占めているため、依然としてペンディングバッファ３１０Ａにありうる。したがって、キャッシュメモリバンク３０６Ａおよび３０６Ｂが、デッドロックの状態になりうる。
【００４８】
[0052]図２に示した読み出しデータバッファ２１８Ａおよび２１８Ｂと同様の読み出しデータバッファ３１４Ａ、３１６Ａ、３１４Ｂ、および３１６Ｂは、キャッシュメモリ３１２Ａおよび３１２Ｂのキャッシュラインスロットを解放する（free up）ためのデータバッファとして働くことによって、上述のデッドロックの状況に対して保護するように実装されうる。図３に示されるとおり、読み出しデータバッファ３１４Ａおよび３１４Ｂは、クライアント３０２Ａに関連付けられ得、読み出しデータバッファ３１６Ａおよび３１６Ｂは、クライアント３０２Ｂに関連付けられうる。要求３２２Ａおよび３２４Ａによって要求されたデータは、要求３２０Ａによって要求されたデータがクライアント３０２Ａに戻されるまで、キャッシュメモリ３１２Ａから読み出され得、読み出しデータバッファ３１４Ａ内に記憶され得、要求３２２Ｂおよび３２４Ｂによって要求されたデータは、要求３２０Ｂによって要求されたデータがクライアント３０２Ｂに戻されるまで、キャッシュメモリ３１２Ｂから読み出され得、読み出しデータバッファ３１６Ｂ内に記憶されうる。この方法で、キャッシュメモリ３１２Ａおよび３１２Ｂが、要求３２０Ａ、３２０Ｂ、３２６Ａ、および３２６Ｂをサービスし続けることができ、要求は、それらがそれぞれのクライアント３０２Ａおよび３０２Ｂによって送信された順序でそれぞれのクライアント３０２Ａおよび３０２Ｂに戻されうる。
【００４９】
[0053]図２のデッドロック保護ユニット２４２と同じように動作するデッドロック保護ユニット３１８Ａおよび３１８Ｂは、それぞれのクライアント３０２Ａおよび３０２Ｂに関連付けられうる。クライアント３０２Ａに関連付けられたデッドロック保護ユニット３１８Ａが、クライアント３０２Ａに関連付けられたペンディングバッファ３０８Ａおよび３０８Ｂがクライアント３０２Ａから追加のデータの要求を受け付けることができるか否かを判断することができる。クライアント３０２Ｂに関連付けられたデッドロック保護ユニット３１８Ｂが、ペンディングバッファ３１０Ａおよび３１０Ｂがクライアント３０２Ｂから追加のデータの要求を受け付けることができるか否かを判断することができる。
【００５０】
[0054]いくつかの例では、デッドロック保護ユニット３１８Ａが、クライアント３０２によってキャッシュメモリバンク３０６Ａに送信された順序の狂った要求のデータサイズの合計と、読み出しデータバッファ３１４Ａのサイズとの比較に基づいて、ペンディングバッファ３０８Ａがクライアント３０２から追加のデータの要求を受け付けることができるか否かを判断することができる。クライアント３０２によってキャッシュメモリバンク３０６Ａに送信された順序の狂った要求は、クライアント３０２によってキャッシュメモリバンク３０６Ａに送信された要求であって、先にクライアント３０２によって別のキャッシュメモリバンク（キャッシュメモリバンク３０６Ｂなど）に送信された要求と比べて異なる順序で処理される要求であってよい。
【００５１】
[0055]クライアント３０２によってキャッシュメモリバンク３０６Ａに行われる要求は、クライアント３０２によってキャッシュメモリシステム３０４に送信されたいずれかの先行の要求がいずれかのメモリバンクにおけるタグチェックに合格していない場合に、順序の狂った要求であってよい。順序の狂った要求は、それ自身は、タグチェックに合格していても、合格していなくてもよい。クライアント３０２によってキャッシュメモリバンク３０６Ａに行われたすべての順序の狂った要求のデータサイズの合計が、読み出しデータバッファ３１４Ａのサイズ以上である場合、デッドロック保護ユニット３１８Ａが、クライアント３０２によってキャッシュメモリバンク３０６Ａに行われたすべての順序の狂った要求のデータサイズの合計が読み出しデータバッファ３１４Ａのサイズよりも小さくなるまで、キャッシュメモリバンク３０６Ａによるクライアント３０２から追加のデータの要求の受け付けを、阻止することができる。
【００５２】
[0056]図４が、本開示のいくつかの態様による例示的なキャッシュメモリシステムにおいてデッドロックの解消に使用される例示的なデータ構造を説明するブロック図である。図４に示されるとおり、データ構造４００は、図３に示したデッドロック保護ユニット３１８Ａおよび３１８Ｂなどのデッドロック保護ユニットによって、キャッシュメモリバンクが関連クライアントから追加のデータの要求を受け付けることができるか否かを判断するために使用されうる。データ構造４００は、リングバッファ（ring buffer）であってよく、有効フラグ（valid flag）、キャッシュメモリバンクＩＤ、およびクライアントからの要求のデータサイズを順に記憶することができる。要求の有効フラグは、最初に要求がキャッシュメモリに送られたときに１に設定され得、ひとたび要求がタグチェックに合格したならばゼロに設定されうる。キャッシュメモリバンクＩＤは、要求が向けられるキャッシュメモリバンクを示すことができる。データサイズは、要求によって要求されるデータのサイズを示すことができる。
【００５３】
[0057]書き込みポインタおよび第１の有効ポインタはそれぞれ、データ構造４００内の要求を指し示す。書き込みポインタは、クライアントによって新たな要求が送信されたときに上書きされる要求を指し示すことができる。典型的には、書き込みポインタは、リングバッファ４００における最も古い項目を指し示すことができる。第１の有効ポインタは、１に設定された有効フラグを依然として有しており、すなわちタグチェックを依然として待っているリングバッファ４００における最も古い要求を指すことができる。第１の有効ポインタは、１に設定された有効フラグを有する要求に遭遇するまでリングバッファ４００を書き込みポインタから右側へと横切る（リングバッファ４００内の最後の項目からリングバッファ４００内の最初の項目への巡回（circling）を含む）ことによって発見されうる。
【００５４】
[0058]第１の有効ポインタによって指し示された要求と、書き込みポインタによって指し示された要求との間の要求（第１の有効ポインタによって指し示された要求を含む）は、順序の狂った要求と考えられうる。この例では、リングバッファ４００のアドレス１〜６に含まれる要求は、順序の狂った要求と考えられうる。
【００５５】
[0059]クライアントによってキャッシュメモリバンクに送信されたすべての順序の狂った要求のデータサイズは、キャッシュメモリバンクがクライアントから追加の要求を受け付けることができるか否かを判断するために、合計されうる。図４に示されている例では、キャッシュメモリバンク０におけるすべての順序の狂った要求のデータサイズは、アドレス１の要求のデータサイズとアドレス５の要求のデータサイズとを足し合わせ、両者の合計のデータサイズを生成することによって計算されうる。したがって、キャッシュメモリバンク０においてクライアントに関連付けられた読み出しデータバッファのデータサイズが５よりも大きい場合、キャッシュメモリバンク０は、クライアントから追加の要求を受け付けることができる。
【００５６】
[0060]同様に、キャッシュメモリバンク１におけるすべての順序の狂った要求のデータサイズは、アドレス２、３、４、および６の要求のデータサイズを足し合わせ、８という合計のデータサイズを生成することによって計算されうる。したがって、キャッシュメモリバンク１においてクライアントに関連付けられた読み出しデータバッファのデータサイズが８よりも大きい場合、キャッシュメモリバンク１は、クライアントから追加の要求を受け付けることができる。
【００５７】
[0061]図５は、本開示のいくつかの態様による複数のクライアントによってアクセス可能なマルチバンクキャッシュメモリシステムのスループットを向上させるための例示的な方法を示すフロー図である。いくつかの例では、マルチバンクキャッシュメモリシステムが、図５に示した方法の動作を指揮および制御するように構成された１つ以上のプロセッサを含むことができる。いくつかの例では、本方法は、グラフィックス処理システムにおいて実行することができる。図５に示されるとおり、本方法は、クライアントからのデータの要求を、第１のキャッシュメモリバンクに関するクライアントに関連付けられたペンディングバッファに記憶することを含むことができる（５０２）。
【００５８】
[0062]本方法は、データの要求の各々が、クライアントによる第２のキャッシュメモリバンクにおけるデータの要求の状態にかかわらず、第１のキャッシュメモリバンク内でキャッシュメモリによって満たされうるか否かを、判断することをさらに含むことができる（５０４）。
【００５９】
[0063]本方法は、判断の後で、第１のキャッシュメモリバンクに関するクライアントに関連付けられたリターンバッファによって、クライアントからのデータの要求を記憶することをさらに含むことができる（５０６）。
【００６０】
[0064]本方法は、第１のキャッシュメモリバンクに関するクライアントに関連付けられた読み出しデータバッファによって、クライアントによって要求されたキャッシュメモリからのデータを、ペンディングバッファにおけるデータの要求の受信の順序に従って記憶することをさらに含むことができる（５０８）。
【００６１】
[0065]本方法は、第１のキャッシュメモリバンクに関するクライアントに関連付けられた書き込みデータバッファによって、キャッシュメモリにデータを書き込むためのクライアントからの書き込み要求を受信することをさらに含むことができる（５１０）。
【００６２】
[0066]本方法は、ペンディングバッファがクライアントから追加のデータの要求を受け付けることができるか否かを、追加の要求を受け付けることが第１のキャッシュメモリバンクと第２のメモリバンクとの間にデッドロックの状況を引き起こすか否かに少なくとも部分的に基づいて判断することをさらに含むことができる（５１２）。
【００６３】
[0067]本方法は、第１のキャッシュメモリバンクによって関連クライアントから受信されるすべての順序の狂ったデータの要求のデータサイズの合計が、読み出しデータバッファのサイズよりも小さい場合に、ペンディングバッファがクライアントから追加のデータの要求を受け付けることができると判断することをさらに含むことができる（５１４）。ペンディングバッファが追加のデータの要求を受け付けることができると判断することは、関連クライアントの要求ごとに有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファに、少なくとも部分的に基づく。
【００６４】
[0068]１つ以上の例では、上述の機能は、グラフィックス処理システムにおいて実装されうる。１つ以上の例では、上述の機能は、ハードウェア、ソフトウェア、ファームウェア、またはこれらの任意の組み合わせにおいて実装されうる。ソフトウェアで実装される場合、これらの機能は、コンピュータ読取可能な媒体において、１つ以上の命令またはコードとして記憶または伝送されうる。コンピュータ読取可能な媒体は、或る場所から他の場所へのコンピュータプログラムの移動を容易にする任意の媒体を含むコンピュータデータ記憶媒体または通信媒体を含むことができる。データ記憶媒体は、本開示において記述された技法を実装するための命令群、コード、および／または、データ構造を取得するために１または複数のコンピュータまたは１または複数のプロセッサによってアクセスされうる任意の利用可能な媒体でありうる。これらに限られるわけではないが、例として、このようなコンピュータ読取可能な媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたは他の光ディスク記憶装置、磁気ディスク記憶装置または他の磁気記憶装置、あるいは所望のプログラムコードを命令またはデータ構造の形態で運ぶまたは記憶するために使用され得、コンピュータによってアクセスされうる任意の他の媒体を備えることができる。また、何らかの接続も、コンピュータ読取可能な媒体と称することが妥当である。例えば、ソフトウェアが、ウェブサイト、サーバ、または他のリモートソース（remote source）から、同軸ケーブル、光ファイバケーブル、ツイストペア、デジタル加入者線（ＤＳＬ）、あるいは赤外線、無線、およびマイクロ波などの無線技術を使用して伝送される場合、同軸ケーブル、光ファイバケーブル、ツイストペア、ＤＳＬ、あるいは赤外線、無線、およびマイクロ波などの無線技術は、媒体の定義に含まれる。本明細書において使用されるとき、ディスク（ｄｉｓｋおよびｄｉｓｃ）は、コンパクトディスク（ＣＤ）、レーザディスク（登録商標）、光ディスク、デジタル多用途ディスク（ＤＶＤ）、フロッピー（登録商標）ディスク、およびＢｌｕ−ｒａｙ（登録商標）ディスクを含み、ここでディスク（ｄｉｓｋ）が、通常はデータを磁気的に再生する一方で、ディスク（ｄｉｓｃ）は、データをレーザで光学的に再生する。上記の組み合わせもまた、コンピュータ読取可能な媒体の範囲内に含まれるべきである。
【００６５】
[0069]コードは、１つ以上のデジタルシグナルプロセッサ（ＤＳＰ）、汎用マイクロプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルロジックアレイ（ＦＰＧＡ）、あるいは他の同等の集積または個別論理回路、などの１つ以上のプロセッサによって実行されてよい。したがって、用語「プロセッサ」は、本明細書において使用されるとき、上述の構造のいずれか、または本明細書に記載の技法の実装に適した任意の他の構造を指すことができる。さらに、いくつかの態様においては、本明細書に記載の機能が、エンコーディングおよびデコーディングのために構成され、あるいは一体型のコーデックに組み込まれた専用のハードウェアおよび／またはソフトウェアモジュール内で提供されてもよい。さらに、これら技法は、１または複数の回路または論理要素で完全に実装されうる。
【００６６】
[0070]本開示の技法は、ワイヤレスハンドセット（wireless handset）、集積回路（ＩＣ）、またはＩＣのセット（すなわち、チップセット）を含む幅広くさまざまなデバイスまたは装置において実装されてよい。さまざまな構成要素、モジュール、またはユニットが、この開示において、開示の技法を実行するように構成されたデバイスの機能的な側面を強調するために説明されたが、必ずしも異なるハードウェア・ユニットによる実現が必要なわけではない。むしろ、前述されたように、さまざまなユニットは、適切なソフトウェアおよび／またはファームウェアと連携する、前述されたような１または複数のプロセッサを含む共通のハードウェア・ユニットの集合によって提供されうるか、コーデック・ハードウェア・ユニットに結合されうる。
【００６７】
[0071]さまざまな例が記載された。これらの例およびその他の例は、以下の特許請求の範囲の範囲内である。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［１］複数のクライアントによってアクセス可能なキャッシュメモリシステムであって、前記キャッシュメモリシステムが複数のキャッシュメモリバンクを含む、キャッシュメモリシステムと、
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数のペンディングバッファと、
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数の読み出しデータバッファと、
を備え、
前記複数のキャッシュメモリバンクの各々は、
キャッシュメモリと、
前記複数のクライアントのうちの或るクライアントからのデータの要求が、前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによる要求の状態にかかわらず、前記キャッシュメモリによって満たされうるか否かを判断するように構成されたタグチェックユニットと、
を含み、
前記ペンディングバッファは、データの要求を前記複数のクライアントのうちの関連クライアントからの受信の順序にて記憶し、前記データの要求が前記キャッシュメモリによって満たされうるか否かの判断を保留するように構成され、
前記読み出しデータバッファは、前記関連クライアントによって要求された前記キャッシュメモリからのデータを、前記ペンディングバッファ内の前記関連クライアントに関連付けられたペンディングバッファによる受信の前記順序に従って記憶するように構成されている、システム。
［２］前記複数のキャッシュメモリバンクの各々は、
前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数のバッファ
をさらに含み、
前記リターンバッファは、前記タグチェックユニットが、前記データの要求が前記キャッシュメモリによって満たされうるか否かを判断した後で、前記複数のクライアントのうちの関連クライアントからの前記データの要求を記憶するように構成されている、［１］に記載のシステム。
［３］前記複数のクライアントに関連付けられた複数のデッドロック保護ユニット
をさらに含み、
前記デッドロック保護ユニットは、前記ペンディングバッファ内の前記関連クライアントのためのペンディングバッファが前記関連クライアントからの追加のデータの要求を受け付けることができるか否かを、前記追加の要求を受け付けることが前記複数のキャッシュメモリバンクの間にデッドロックの状況を引き起こすか否かに少なくとも部分的に基づいて、判断するように構成されている、［１］に記載のシステム。
［４］前記関連クライアントのための前記ペンディングバッファは、前記関連クライアントによるすべての順序の狂ったデータの要求のデータサイズの合計が、同じキャッシュメモリバンク内の前記読み出しデータバッファのサイズよりも小さい場合に、前記関連クライアントからの前記追加のデータの要求を受け付けることができる、［３］に記載のシステム。
［５］前記複数のデッドロック保護ユニットの各々は、前記関連クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファを含む、［４］に記載のシステム。
［６］前記複数のキャッシュメモリバンクに関する前記複数のクライアントに関連付けられた複数の書き込みデータバッファ
をさらに備え、
前記書き込みデータバッファは、前記キャッシュメモリにデータを書き込むために前記関連クライアントからの書き込み要求を受信するように構成されている、［１］に記載のシステム。
［７］前記キャッシュメモリは、前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記複数のバッファに記憶された前記データの要求をサービスするように構成されている、［２］に記載のシステム。
［８］クライアントからのデータの要求を、第１のキャッシュメモリバンクに関する前記クライアントに関連付けられたペンディングバッファに記憶することと、
前記データの要求の各々が、第２のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記第１のキャッシュメモリバンク内のキャッシュメモリによって満たされうるか否かを判断することと、
前記クライアントによって要求された前記キャッシュメモリからのデータを、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられた読み出しデータバッファによって、前記ペンディングバッファにおける前記データの要求の受信の順序に従って記憶することと
を備える、方法。
［９］前記判断の後に、前記クライアントからの前記データの要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられたリターンバッファによって記憶すること
をさらに備える、［８］に記載の方法。
［１０］前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができるか否かを、前記追加の要求を受け付けることが前記第１のキャッシュメモリバンクと前記第２のキャッシュメモリバンクとの間にデッドロックの状況を引き起こすか否かに少なくとも部分的に基づいて判断すること
をさらに備える、［８］に記載の方法。
［１１］前記第１のキャッシュメモリバンクによって前記クライアントから受信されたすべての順序の狂ったデータの要求のデータサイズの合計が、前記読み出しデータバッファのサイズよりも小さい場合に、前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができると判断すること
をさらに備える、［１０］に記載の方法。
［１２］前記ペンディングバッファが追加の要求を受け付けることができると判断することは、前記クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファに少なくとも部分的に基づく、［１１］に記載の方法。
［１３］前記キャッシュメモリにデータを書き込むために前記クライアントからの書き込み要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられた書き込みデータバッファによって受信すること
をさらに備える、［８］に記載の方法。
［１４］前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記リターンバッファに記憶された前記データの要求を前記キャッシュメモリによってサービスすること
をさらに備える、［９］に記載の方法。
［１５］第１のキャッシュメモリバンクに関するクライアントからのデータの要求を記憶するための手段と、
前記データの要求の各々が、第２のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断するための手段と、
前記第１のメモリバンクに関する前記クライアントによって要求された前記キャッシュメモリからのデータを記憶するための手段と
を備える、装置。
［１６］前記クライアントからの重要なデータの要求を記憶するための手段
をさらに備える、［１５］に記載の装置。
［１７］前記データの要求を受信するための手段が前記クライアントからの追加のデータの要求を受け付けることができるか否かを、前記追加の要求を受け付けることが前記第１のキャッシュメモリバンクと前記第２のキャッシュメモリバンクとの間にデッドロックの状況を引き起こすか否かに少なくとも部分的に基づいて判断するための手段
をさらに備える、［１５］に記載の装置。
［１８］前記データの要求を受信するための手段が前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断するための前記手段は、
前記クライアントによるすべての順序の狂ったデータの要求のデータサイズの合計が、前記要求されたキャッシュメモリからのデータを記憶するための手段のサイズよりも小さい場合に、前記データの要求を受信するための手段が前記クライアントからの追加のデータの要求を受け付けることができると判断するための手段
を備える、［１７］に記載の装置。
［１９］前記データの要求を受信するための手段が前記クライアントからの追加のデータの要求を受け付けることができるか否かを判断するための前記手段は、
前記クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファ
を含む、［１８］に記載の装置。
［２０］前記キャッシュメモリにデータを書き込むための前記クライアントからの書き込み要求を受信するための手段
をさらに備える、［１５］に記載の装置。
［２１］前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記重要な要求を記憶するための手段に記憶された前記データの要求を、前記キャッシュメモリによってサービスするための手段
をさらに備える、［１６］に記載の装置。
［２２］第１のキャッシュメモリバンクに関するクライアントからのデータの要求を記憶し、
前記データの要求の各々が、第２のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、キャッシュメモリによって満たされうるか否かを判断し、
前記第１のメモリバンクに関する前記クライアントによって要求された前記キャッシュメモリからのデータを記憶する
ように構成された１つ以上のプロセッサを備える、装置。
［２３］前記１つ以上のプロセッサは、
前記判断することの後で、前記クライアントからの前記データの要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられたリターンバッファに記憶する
ようにさらに構成されている、［２２］に記載の装置。
［２４］前記１つ以上のプロセッサは、
前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができるか否かを、前記追加の要求を受け付けることが前記第１のキャッシュメモリバンクと前記第２のキャッシュメモリバンクとの間にデッドロックの状況を引き起こすか否かに少なくとも部分的に基づいて判断する
ようにさらに構成されている、［２２］に記載の装置。
［２５］前記１つ以上のプロセッサは、
前記第１のキャッシュメモリバンクによって前記クライアントから受信されるすべての順序の狂ったデータの要求のデータサイズの合計が、前記読み出しデータバッファのサイズよりも小さい場合に、前記ペンディングバッファが前記クライアントからの追加のデータの要求を受け付けることができると判断する
ようにさらに構成されている、［２４］に記載の装置。
［２６］前記ペンディングバッファが追加の要求を受け付けることができると判断することが、前記クライアントの要求について、有効フラグ、バンクＩＤ、およびデータサイズのうちの１つ以上を記憶するバッファに少なくとも部分的に基づく、［２５］に記載の装置。
［２７］前記１つ以上のプロセッサは、
前記キャッシュメモリにデータを書き込むために前記クライアントからの書き込み要求を、前記第１のキャッシュメモリバンクに関する前記クライアントに関連付けられた書き込みデータバッファによって受信する
ようにさらに構成されている、［２２］に記載の装置。
［２８］前記１つ以上のプロセッサは、
前記複数のキャッシュメモリバンク内の別のキャッシュメモリバンクにおける前記クライアントによるデータの要求の状態にかかわらず、前記リターンバッファに記憶された前記データの要求を、前記キャッシュメモリがサービスする
ようにさらに構成されている、［２３］に記載の装置。
【図１】
0006022604.tif 000002
【図２】
0006022604.tif 000003
【図３】
0006022604.tif 000004
【図４】
0006022604.tif 000005
【図５】
0006022604.tif 000006