8.3 זכרון מטמון הרצאה

הקדמה¶

בפרק 0.2 למדנו שיש אוגרים (מהירים, קטנים) ויש RAM (איטי, גדול). אבל יש פער ענק ביניהם - האוגרים מגיבים תוך פחות ממחזור שעון אחד, בזמן שגישה ל-RAM לוקחת כ-100 מחזורים. אם המעבד היה צריך לגשת ל-RAM בכל פעם שהוא צריך נתון, הוא היה מבזבז רוב הזמן בהמתנה.

הפתרון: זכרון מטמון - cache memory - שכבות של זכרון קטן ומהיר שיושבות בין המעבד ל-RAM ומחזיקות עותקים של הנתונים הנפוצים ביותר.

היררכיית הזכרון - memory hierarchy¶

              מהירות       גודל טיפוסי      זמן גישה
              --------     -------------    ----------
אוגרים        הכי מהיר     כמה מאות בתים    < 1ns
    |
L1 cache      מהיר מאוד    32-64 KB         ~1 ns  (4 מחזורים)
    |
L2 cache      מהיר         256 KB - 1 MB    ~5 ns  (12 מחזורים)
    |
L3 cache      בינוני       8-64 MB          ~15 ns (40 מחזורים)
    |
RAM           איטי         8-128 GB         ~100 ns (200+ מחזורים)
    |
דיסק (SSD)    איטי מאוד    256 GB - 4 TB    ~100,000 ns (0.1ms)
    |
דיסק (HDD)    הכי איטי     1-20 TB          ~10,000,000 ns (10ms)

כמה נקודות חשובות:
- L1 מפוצל: יש L1 נפרד להוראות (L1I) ו-L1 נפרד לנתונים (L1D). זה פותר את סכנת המבנה שלמדנו בפרק 8.1 - שלב IF קורא מ-L1I ושלב MEM קורא/כותב ל-L1D בו-זמנית.
- L1 ו-L2 לכל ליבה: בעידן הרב-ליבתי, כל ליבה במעבד יש לה L1 ו-L2 פרטיים.
- L3 משותף: מטמון L3 משותף לכל הליבות. הוא גדול יותר אבל איטי יותר.
- הפרש פי 100: הפער בין L1 (1ns) ל-RAM (100ns) הוא פי 100. זה כאילו ההבדל בין לשלוף ספר מהמדף ליד (L1) לבין לנסוע לספרייה העירונית (RAM).

למה מטמון עובד - עקרונות מקומיות - locality principles¶

מטמון הוא קטן - 64KB של L1 מול 16GB של RAM. איך מטמון כל כך קטן יכול להיות יעיל? בגלל שתוכנות לא ניגשות לזכרון באופן אקראי. יש שני דפוסים חזקים:

מקומיות זמנית - temporal locality¶

אם ניגשת לכתובת מסוימת, סביר שתיגש אליה שוב בקרוב.

דוגמאות: משתנה counter בלולאה, מצביע ההוראה (IP) שרץ על אותו קוד שוב ושוב בלולאה, הראש של רשימה מקושרת שניגשים אליו בכל צעד.

מקומיות מרחבית - spatial locality¶

אם ניגשת לכתובת מסוימת, סביר שתיגש לכתובות סמוכות בקרוב.

דוגמאות: סריקה של מערך (כתובת i, אחריה כתובת i+1, אחריה i+2...), ביצוע קוד רצף (הוראה אחרי הוראה), גישה לשדות של struct (שדה אחד ליד השני בזכרון).

המטמון מנצל את שני הדפוסים: כשניגשים לכתובת, הוא טוען אותה ואת הסביבה שלה (מקומיות מרחבית), ושומר אותה לגישה חוזרת (מקומיות זמנית).

מבנה המטמון - cache structure¶

שורת מטמון - cache line¶

שורת המטמון היא יחידת המטמון הבסיסית. ברוב מעבדי x86, שורת מטמון היא 64 בתים.

כשאתם קוראים בית אחד מהזכרון וזה cache miss, המעבד לא מביא רק את הבית הזה - הוא מביא את כל שורת המטמון (64 בתים) שמכילה אותו. למה? מקומיות מרחבית - סביר שתצטרכו גם את הבתים הסמוכים.

זה אומר שאם יש לכם מערך של int-ים (4 בתים כל אחד), גישה לאיבר אחד מביאה 16 איברים למטמון (64 / 4 = 16). הגישה ל-15 האיברים הבאים תהיה cache hit - מהירה מאוד.

תגית, אינדקס, היסט - tag, index, offset¶

כל כתובת בזכרון מפורקת לשלושה חלקים שקובעים איפה הנתון נמצא במטמון:

כתובת (למשל 32 ביט):
+------------------+---------+--------+
|      Tag         |  Index  | Offset |
+------------------+---------+--------+

היסט - Offset (6 ביט עבור שורה של 64 בתים): מציין את המיקום בתוך שורת המטמון. 6 ביט = 64 ערכים = 64 בתים.
אינדקס - Index: מציין באיזו קבוצה (set) במטמון לחפש.
תגית - Tag: מזהה ייחודי - כשנמצא את הset, צריך לבדוק שהtag תואם כדי לוודא שזו באמת הכתובת שחיפשנו.

אסוציאטיביות - associativity¶

איך כתובת ממופה למקום במטמון? יש שלוש גישות:

מיפוי ישיר - direct-mapped:
כל כתובת יכולה להיכנס רק למקום אחד ספציפי במטמון (נקבע לפי הindex). מהיר לחיפוש (מסתכלים רק במקום אחד), אבל נוצרות הרבה התנגשויות - שתי כתובות שונות עם אותו index מתחרות על אותו מקום.

כתובת A -> יכולה רק בset 3
כתובת B -> יכולה רק בset 3  (התנגשות!)

אסוציאטיבי מלא - fully associative:
כל כתובת יכולה להיכנס לכל מקום במטמון. הכי גמיש, אין התנגשויות מיותרות, אבל החיפוש דורש השוואת tag מול כל הכניסות - יקר מאוד בחומרה. משתמשים רק במטמונים קטנים מאוד (כמו TLB).

אסוציאטיבי קבוצתי - N-way set-associative:
הפשרה הנפוצה. המטמון מחולק לsets, כל set מכיל N שורות (ways). כתובת ממופה לset ספציפי (לפי index), אבל בתוך הset יכולה להיכנס לכל אחת מ-N השורות.

מטמון 4-way set-associative:

Set 0:  [way 0] [way 1] [way 2] [way 3]
Set 1:  [way 0] [way 1] [way 2] [way 3]
Set 2:  [way 0] [way 1] [way 2] [way 3]
...
Set 63: [way 0] [way 1] [way 2] [way 3]

דוגמה: L1D במעבדי Intel מודרניים הוא בדרך כלל 8-way set-associative, 64 sets, 64B lines:
- גודל = 64 sets x 8 ways x 64 bytes = 32 KB
- כל כתובת ממופה ל-1 מתוך 64 sets (6 ביט index), ובתוך הset בודקים 8 tags

החטאות מטמון - cache misses¶

יש שלושה סוגי cache miss:

החטאה ראשונית - compulsory (cold) miss¶

הגישה הראשונה לשורת מטמון - הנתון מעולם לא היה במטמון. זה בלתי נמנע.

החטאת קיבולת - capacity miss¶

המטמון מלא והנתון נדחק החוצה כי אין מקום. קורה כשסט הנתונים גדול מהמטמון.

החטאת התנגשות - conflict miss¶

הנתון נדחק החוצה למרות שיש מקום פנוי במטמון - כי הset הספציפי שלו מלא. קורה ב-direct-mapped ו-set-associative. לא קורה ב-fully associative.

מדיניות כתיבה - write policies¶

כשהמעבד כותב נתון, הוא כותב למטמון. אבל מתי הנתון נכתב ל-RAM?

כתיבה מיידית - write-through¶

כל כתיבה למטמון נכתבת מיד גם ל-RAM (או לשכבת המטמון הבאה). פשוט אבל יוצר הרבה תעבורה לRAM.

כתיבה בעיכוב - write-back¶

כתיבה רק למטמון. השורה מסומנת כ-"מלוכלכת" (dirty). רק כשהשורה נדחקת מהמטמון (eviction), היא נכתבת ל-RAM. מעבדים מודרניים משתמשים ב-write-back כי זה מפחית דרמטית את התעבורה ל-RAM.

קוהרנטיות מטמון - cache coherency¶

הבעיה¶

כזכור מפרק 6 (הקרנל), מעבדים מודרניים הם רב-ליבתיים. לכל ליבה יש L1 ו-L2 פרטיים. מה קורה כשליבה 0 כותבת ערך חדש לכתובת X (וזה נשמר רק ב-L1 של ליבה 0), וליבה 1 קוראת את כתובת X מה-L1 שלה ומקבלת את הערך הישן?

ליבה 0:                    ליבה 1:
L1: X = 42 (חדש)           L1: X = 17 (ישן!)
                              ^
                              | ליבה 1 לא יודעת שX השתנה!

זה מצב של אי-קוהרנטיות - שתי ליבות רואות ערכים שונים לאותה כתובת.

פרוטוקול MESI¶

הפתרון: כל שורת מטמון מסומנת באחד מארבעה מצבים:

מצב	שם	משמעות
M	Modified	השורה שונתה (dirty) ונמצאת רק במטמון הזה. RAM מיושן.
E	Exclusive	השורה לא שונתה ונמצאת רק במטמון הזה.
S	Shared	השורה לא שונתה ונמצאת במטמונים של כמה ליבות.
I	Invalid	השורה לא תקפה - צריך לקרוא מחדש.

כשליבה 0 כותבת לשורה:
1. אם השורה במצב M או E - כותבת ישירות (היא היחידה שמחזיקה את השורה)
2. אם השורה במצב S - שולחת הודעת invalidate לכל הליבות האחרות שמחזיקות את השורה. הן מסמנות את השורה שלהן כ-I (Invalid). רק אז ליבה 0 כותבת ומעבירה את השורה למצב M.

כשליבה 1 רוצה לקרוא שורה שמסומנת I - היא חייבת לבקש אותה מחדש (מליבה אחרת או מ-RAM).

זוהי בעיית ביצועים מוכרת בתכנות מרובה threads. היא קורית כשתי ליבות כותבות למשתנים שונים שבמקרה נמצאים על אותה שורת מטמון.

// שני משתנים צמודים בזכרון:
struct {
    int counter_thread0;   // thread 0 כותב לכאן
    int counter_thread1;   // thread 1 כותב לכאן
} shared;

שני המשתנים צמודים בזכרון ונמצאים על אותה שורת מטמון (64 בתים). כל פעם ש-thread 0 כותב ל-counter_thread0, השורה ב-L1 של ליבה 1 הופכת ל-Invalid. וכל פעם ש-thread 1 כותב ל-counter_thread1, השורה ב-L1 של ליבה 0 הופכת ל-Invalid. המטמונים "מתרוצצים" ביניהם על השורה - למרות שכל thread כותב למשתנה שלו בלבד!

הפתרון - ריפוד - padding: להרחיק את המשתנים כך שיהיו על שורות מטמון שונות:

struct {
    int counter_thread0;
    char padding[60];      // ריפוד - 60 בתים כדי להשלים ל-64
    int counter_thread1;   // עכשיו על שורת מטמון אחרת
} shared;

עם הריפוד, כל thread כותב לשורת מטמון נפרדת - אין invalidations מיותרות, והביצועים משתפרים דרמטית.

למה זה חשוב למתכנתים¶

סריקת מערכים - סדר הגישה משנה¶

// גישה רציפה - cache-friendly
for (int i = 0; i < N; i++)
    sum += arr[i];       // כתובות עוקבות: arr[0], arr[1], arr[2]...

// גישה אקראית - cache-unfriendly
for (int i = 0; i < N; i++)
    sum += arr[random_index[i]];  // קופץ למקומות רנדומליים

בגישה רציפה, cache miss קורה רק פעם אחת כל 16 int-ים (64 בתים / 4 = 16). שאר הגישות הן cache hits. בגישה אקראית, כמעט כל גישה היא cache miss.

מבנה מערכים מול מערך מבנים - SoA vs AoS¶

מערך מבנים - Array of Structures (AoS):

struct Particle {
    float x, y, z;      // מיקום
    float vx, vy, vz;   // מהירות
    float mass;          // מסה
    int type;            // סוג
};
struct Particle particles[10000];

אם רוצים לחשב את סכום המסות:

for (int i = 0; i < 10000; i++)
    total_mass += particles[i].mass;

כל struct הוא 32 בתים. שדה mass נמצא ב-offset 24 בתוך כל struct. כל גישה ל-mass קופצת 32 בתים - חצי מהנתונים שנכנסים לcache line לא רלוונטיים.

מבנה מערכים - Structure of Arrays (SoA):

struct ParticleArrays {
    float x[10000], y[10000], z[10000];
    float vx[10000], vy[10000], vz[10000];
    float mass[10000];
    int type[10000];
};
struct ParticleArrays particles;

for (int i = 0; i < 10000; i++)
    total_mass += particles.mass[i];

עכשיו כל הmass-ים צמודים בזכרון - כל cache line מביא 16 ערכי mass (64/4). ניצולת מושלמת של הcache.

כפל מטריצות - הדוגמה הקלאסית¶

// גרסה נאיבית: ijk
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            C[i][j] += A[i][k] * B[k][j];

הבעיה ב-B[k][j]: כש-k משתנה ו-j קבוע, אנחנו קופצים בין שורות של B - כל גישה היא שורת מטמון אחרת. מטריצה 1000x1000 של double (8 בתים) = 8MB, הרבה יותר מ-L1 cache.

// גרסה מותאמת: ikj (שינוי סדר הלולאות)
for (int i = 0; i < N; i++)
    for (int k = 0; k < N; k++)
        for (int j = 0; j < N; j++)
            C[i][j] += A[i][k] * B[k][j];

עכשיו B[k][j] נסרק עם j עוקב - גישה רציפה! וגם C[i][j] נסרק רציף. ו-A[i][k] קבוע בלולאה הפנימית. ההבדל: פי 3-10 יותר מהיר על מטריצות גדולות.

מדידה עם perf¶

הכלי perf בלינוקס מאפשר למדוד cache misses ישירות ממוני החומרה:

perf stat -e L1-dcache-load-misses,L1-dcache-loads,\
LLC-load-misses,LLC-loads ./my_program

 1,234,567  L1-dcache-load-misses  (5.12% of L1 loads)
24,115,890  L1-dcache-loads
     4,521  LLC-load-misses        (0.37% of LLC loads)
 1,234,567  LLC-loads

הפלט אומר: 5.12% מהגישות ל-L1D היו miss (נפלו ל-L2/L3), ומתוך אלה רק 0.37% היו miss גם ב-LLC (Last Level Cache, כלומר L3) ונפלו ל-RAM.

סיכום¶

מושג	הסבר
שורת מטמון - cache line	יחידת המטמון הבסיסית (64 בתים ב-x86)
מקומיות זמנית - temporal locality	גישה חוזרת לאותו נתון
מקומיות מרחבית - spatial locality	גישה לנתונים סמוכים
אסוציאטיביות - associativity	כמה מקומות יכולה שורה לתפוס בset
החטאה ראשונית - compulsory miss	גישה ראשונה לשורה
החטאת קיבולת - capacity miss	המטמון מלא
החטאת התנגשות - conflict miss	הset מלא
כתיבה בעיכוב - write-back	כתיבה ל-RAM רק ב-eviction
פרוטוקול MESI	קוהרנטיות מטמון בין ליבות
שיתוף כוזב - false sharing	ליבות שונות כותבות לאותה שורת מטמון

בפרק הבא (8.4) נלמד על ביצוע שלא בסדר - איך המעבד מצליח להימנע מלחכות כשיש cache miss.