CPU cache ဆိုတာ ဘာလဲ။

Cache ဆိုတာ မြန်မာလို ပြောရရင်တော့ ခေတ္တယာယီနေရာပါ။

CPU မှာ L1, L2 နဲ့ L3 cache တွေရှိပါတယ်။ L1 နဲ့ L2 cache တွေက Core တိုင်းမှာ ပါပြီး L3 ကတော့ shared cache ပါ။ CPU ဟာ instruction တစ်ခုကို ဖတ်ရင် L1(32KB) မှာ အရင်ဖတ်တယ်။ L1 ကို အနီးဆုံး cache လို့ သဘောထားလို့ရပါတယ်။ သူ့ဆီက Data ယူရဖို့ ဆိုရင် CPU က 3-5 cycles လောက်နဲ့ ယူနိုင်ပါတယ်။ အလွန်မြန်တာပါ။ L1 မှာ instruction ကို မတွေ့ရင်တော့ CPU ဟာ L2 cache(256KB) မှာ ထပ်ရှာပါတယ်။ သူကတော့ 10-15 cycles လောက် CPU ကနေသွားရပါတယ်။ နောက်ဆုံး cache က L3 ပါ။ L3 ကိုရောက်ဖို့ကတော့ 50-100 cycles လောက်ကို CPU ကနေသွားရပါတယ်။ C++ မှာ Cache friendly ဖြစ်တဲ့ code အရှင်းဆုံးပုစ္ဆာက row major access လို့ခေါ်ပါတယ်။

အောက်ဖေါ်ပြပါcode က cache မဖြစ်တဲ့ code ပါ။

    for (int col = 0; col < N; col++) {
        for (int row = 0; row < N; row++) {
            sum += matrix[row][col];
        }
    }

ဟောသည် code ကတော့ cache efficent ဖြစ်ပါတယ်။ ဒါကို row major access လုပ်တယ်လို့ ခေါ်ပါတယ်။

    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            sum += matrix[row][col];
        }
    }

ဘာဖြစ်လို့ Row major access က cache friendly ဖြစ်တာလဲ။ကြည့်ကြရအောင်။ အောက်ပါ 2 dimentional array ကိုကြည့်ပါ။

int matrix[4][4] = {
    { 1,  2,  3,  4},  // row 0
    { 5,  6,  7,  8},  // row 1
    { 9, 10, 11, 12},  // row 2
    {13, 14, 15, 16}   // row 3
};

အဲဒီ array ဟာ memory ပေါ်မှာ နေရာယူရင် အောက်ပါအတိုင်းယူပါတယ်။

    matrix[0][0]  (1)  - 0x1000
    matrix[0][1]  (2)  - 0x1004
    matrix[0][2]  (3)  - 0x1008
    matrix[0][3]  (4)  - 0x100C
    matrix[1][0]  (5)  - 0x1010 
    matrix[1][1]  (6)  - 0x1014
    matrix[1][2]  (7)  - 0x1018
    matrix[1][3]  (8)  - 0x101C
    matrix[2][0]  (9)  - 0x1020
    matrix[2][1]  (10) - 0x1024
    matrix[2][2]  (11) - 0x1028
    matrix[2][3]  (12) - 0x102C
    matrix[3][0]  (13) - 0x1030
    matrix[3][1]  (14) - 0x1034
    matrix[3][2]  (15) - 0x1038
    matrix[3][3]  (16) - 0x103C

ဒီတော့ CPU က စ အလုပ်လုပ်တဲ့ အချိန်မှာ ဘာကိုသွားကြည့်လဲဆိုတော့ matrix[0][0] ရဲ့ address ကိုသွားကြည့်ပါတယ်။ L1, L2 နဲ့ L3 မှာ အဲဒီ address ရှိမရှိကြည့်တယ်။ မရှိတော့ 64 byte တိတိ Cache ထဲကို ထည့်လိုက်ပါတယ်။ ဒီနေရာမှာ တစ်ခုပြောစရာရှိတာက int တစ်လုံး က 4 byte ယူပါတယ်။

    matrix[0][0]  (1)  - 0x1000
    matrix[0][1]  (2)  - 0x1004

Cache ပေါ်မှာ 64 byte ရောက်သွားတယ်ဆိုတာ ခုဏကပြောတဲ့ 2 dimensional array တစ်ခုလုံး Cache ပေါ်ရောက်သွားတာပါ။ ဒါကြောင့် matrix[0][1] , matrix[0][2] အစရှိသဖြင့် loop ထဲကခေါ်သမျှဟာ Cache ထဲကနေ CPU က အသင့် memory address ကို 4 bytes စီတိုးပြီး ခေါ်သွားရုံမို့လို့ အများကြီး မြန်သွားပါတော့တယ်။