cache coloringとは

プログラムの実行速度を上げるためには、CPUが持っているcacheをいかに上手に使うかが重要になってきます。

プログラムで工夫する事によって、cacheのmiss率を下げて、実行速度を上げる事ができます。

cacheのcoloringとは、cacheのmiss率を下げるためのプログラムテクニックです。

cacheの仕組み

前程

話を簡単にするために、

• cacheの方式は、direct mapped。
• cacheの1ラインのサイズは16bytes。
• cacheサイズは1KB。

とします。

cacheの構成

       <--16bytes-->
       +-----------+
index0 |           |
       +-----------+
index1 |           |
       +-----------+
index2 |           |
       +-----------+
index3 |           |
       +-----------+
index4 |           |
       +-----------+
            ...
       +-----------+
index63|           |
       +-----------+

cacheは、16bytesごとの塊xN個で構成されています。 この16bytesの塊1つを、1lineと呼びます。

lineが何個あるかは、cacheサイズをlineサイズで割れば計算できます。1KB / 16 = 64なので、このcacheには64line存在します。

あるデータは、どこのcache lineに入るか

CPUがあるアドレスにアクセスした時、どのindex番号のlineにアクセスするかは、以下の計算でわかります。

• アドレスを1KBで割った余りを計算する。
• その余りを、16で割る

つまり、アドレスのbit9からbit4がlineのindex番号になります。

bit 31                                        10 9 8 7 6 5 4 3 2 1 0
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | | | |X|X|X|X| 
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                                <--line番号->

あるメモリアドレスから、どこのcache lineに入るのかは一意に決まります。

cache coloringの概要

良く使うデータや、連続して使うデータが同じcache lineに割り当てられてしまうと、cache missが頻発してしまいます。

例えば、2つのアドレス

• 0x000000A0
• 0x000020A0

に交互にアクセスするとします。

この2つのアドレスは、どちらもbit9-6は0x0Aですので、どちらもindex10のcache lineに入ります。

そのため、アクセスするたびにcache lineの入れ換え(cache miss)が発生してしまい、効率が悪いメモリアクセスとなってしまいます。

cache coloringとは、データがcacheのどこのlineに入るかをコントロールする事で、cache missを少なくする方法の事です。

cache coloringの例(データキャッシュ)

構造体の配列(slab coloring)

大きさがちょうどcacheのサイズと同じの構造体があったとします。 名前を、struct hogeとしましょう。

struct hogeは、リンクリストを作るためのメンバnextとprevも持っています。

struct hoge {
    struct hoge *next;
    struct hoge *prev;
    ...
};

また、struct hogeの配列も用意します。

struct hoge array[30];

struct hogeのサイズは、ちょうどcacheのサイズと同じ1KBです。 つまり、array[0].nextと、array[1].next、array[n].nextは全て、同じcache lineに入る事になります。

ここで、array[]のリンクリストに、要素を追加するコードを考えてみます。 例として、A後ろに、Bを挿入してみます。

struct hoge *A,*B,*C;

C = A->next;
B->prev = A;
A->next = B;
C->prev = B;

cache missが頻発している事にお気付きでしょうか。

C = A->next; /* Aがcacheに入る */
B->prev = A; /* Bがcacheに入る */
A->next = B; /* Aがcacheに入る */
C->prev = B; /* Cがcacheに入る */

この現象を避けるには、struct hogeのよくアクセスするメンバ(この場合、prevとnext)が、同じcache lineに入らないようにする事です。

一番簡単な方法は、struct hogeにpaddingを入れて、サイズを1KBから、1KB+16bytesにしてやる事です。

Linuxのtask struct

Linuxには、プロセスの状態を管理するためのtask structという構造体があります。

以前のLinuxカーネルでは、task structが置かれるアドレスは、必ず8KBの倍数でした。つまり、異なるtask structが同じcache lineに入ってしまっていました。そのため、例えば「全てのtask structを走査する」ような事を行うと、cache missが頻発していました。

現在のLinuxカーネルでは、task structを置くアドレスを、8の倍数+αにしています。αをプロセスによっていろいろ変えてやる事で、task structが同じcache lineに入る事を防いでいます。

詳しくはこちら。

cache coloringの例(命令キャッシュ)

procedure mapping

関数A()が関数B()を頻繁に呼び出しているとします。

void A(void) 
{
    for (i = 0; i < 10000; i++) {
        B();
    }
}

この場合、A()とB()が同じcache lineに入るようなアドレスに配置されていると、

1. A()の処理中 -> cache lineにAが入る
2. B()を呼び出す -> cache lineにBが入る
3. B()からリターン -> cache lineにAが入る
4. 2.へ

となり、cache missが頻発してしまいます。

A()とB()が同じcache lineに入らないように配置するアドレスを工夫してやる事で、cache miss率を下げる事ができます。

書こうと思っていたけど、力尽きて書いてない事

• page coloring
• fully associative cache/N-way associative cache
• virtual address

---

Last Modified: 2008-06-16 Monday