のLinuxスラブ・アロケータとキャッシュパフォーマンス

Question

ガイド 理解Linuxカーネル第3版、章8.2.10から

、スラブは、同じハードウェア・キャッシュ・ラインは、多くの異なるブロックをマップすることを私たちは、第2章から知っている

を絵画やRAM。この の章では、同じサイズのオブジェクトがキャッシュ内の同じオフセットに格納されることもわかりました。 異なるスラブ内で同じオフセットを持つオブジェクトは、比較的高い確率で、同じキャッシュ行に にマップされます。したがって、キャッシュハードウェアは、2つのオブジェクト を同じキャッシュラインから異なるRAMロケーションに前後に転送し、他のキャッシュラインは十分に活用されないメモリサイクルを浪費することがあります。 スラブアロケータは、スラブカラーリングと呼ばれるポリシーによって、この不快なキャッシュ動作を減らそうとします。different スラブには、色と呼ばれる任意の値が割り当てられます。

（1）私はスラブ着色が解決しようとする問題を理解することができません。通常のプロセスがデータにアクセスするときに、データがキャッシュになく、キャッシュミスが発生した場合、データは、パフォーマンスを向上させるためにプロセスがアクセスしようとするデータの周辺アドレスからのデータと共にキャッシュにフェッチされます。どのように同じ特定のキャッシュラインがスワップし続けるような状況が発生する可能性がありますか？プロセスが2つの異なるメモリ領域のメモリ領域内の同じオフセットで2つの異なるデータアドレスにアクセスする確率は非常に低い。キャッシュポリシーは、通常、LRU、ランダムなどのいくつかのアジェンダに従ってスワップされるラインを選択します。アクセスされるアドレスの最下位ビットのマッチに応じてラインを追い出すようなポリシーはありません。

（2）私が先頭と最初のオブジェクトの異なるオフセットと異なるスラブでの結果とスラブの端から空きバイトを取るスラブ着色は、キャッシュスワッピング問題を解決する方法を理解することができませんか。 [SOLVED]

小さな調査の後は、私は私の質問への答えを見つけたと信じています。回答が投稿されました。

Answer 1

私はそれを持っていると思う、答えはに関連しています。。

キャッシュは特定のセットに分割することができ、各セットは特定のメモリブロックタイプのみをキャッシュすることができます。たとえば、set0には8の倍数のアドレスを持つメモリブロックが含まれ、set1には12の倍数のアドレスを持つメモリブロックが含まれます。これは、キャッシュのパフォーマンスを向上させ、キャッシュ全体からすべてのアドレスを検索することを避けるためです。この方法では、キャッシュの特定のセットのみを検索する必要があります。

さて、リンクからUnderstanding CPU Caching and performance Henesseyとパターソンのページ377から

は、キャッシュの配置式は次のとおりです。 （ブロックアドレス）MOD（キャッシュ内セット数）

メモリブロックアドレス0x10000008（スラブXの色C）とメモリブロックアドレス0x20000009（スラブYの色Z）。大部分のN（キャッシュ内のセット数）の場合、の計算では異なる値が得られ、データをキャッシュするための別のセットが生成されます。アドレスが同じ最下位ビット値（例えば、0x10000008および0x20000008）であった場合、Nの大半について、計算は同じ値をもたらすので、ブロックはと同じキャッシュセットにを衝突させます。

だからは、異なるスラブ内のオブジェクトの異なるオフセット（色）を維持することによって、スラブオブジェクトは、潜在的にキャッシュ内の異なるセットに到達するとが同じセットにを衝突、および全体的なキャッシュのパフォーマンスはありません増加した。

EDIT：キャッシュは直接マッピングされたものであればははまた、後ウィキペディア、CPU Cache、ノーキャッシュ置換ポリシーに従って存在しmodulu計算は、メモリブロックが格納されるキャッシュブロックが得られます。このキャッシュの組織では

ダイレクトマップキャッシュ 、メインメモリ内の各位置は、キャッシュに一つだけのエントリに行くことができます。したがって、ダイレクトマップキャッシュは、「一方向セットアソシアティブ」キャッシュとも呼ばれます。追放するキャッシュエントリの内容を選択することができないため、そのような代替ポリシーはありません。つまり、2つの場所が同じエントリにマップされていると、連続して相手をノックアウトする可能性があります。より簡単ではあるが、ダイレクト・マップ・キャッシュは、匹敵するパフォーマンスを提供するために、アソシエーテッド・キャッシュよりもはるかに大きくする必要があり、予測がより困難です。 xをキャッシュ内のブロック番号、yをメモリのブロック番号、nbeをキャッシュ内のブロック数とすると、マッピングはx = y mod nの式で行います。

Answer 2

あなたは256KBのキャッシュを持っていて、キャッシュライン=（実アドレスと0x3FFFFF）を行う超簡単なアルゴリズムを使用しているとします。

ここで、各メガバイト境界からスラブを開始すると、スラブ1のアイテム20は、同じキャッシュラインタグを使用するため、スラブ2のアイテム20をキャッシュから追い出します。

スラブをオフセットすることによって、異なるスラブが同じキャッシュラインタグを共有する可能性が低くなります。スラブ1とスラブ2の両方が32バイトのオブジェクトを保持し、スラブ2がオフセット8バイトである場合、そのキャッシュタグはスラブ1と決して等しくはありません。

私はいくつかの詳細が間違っていると確信していますが、それは価値があるためにそれを取る。