8.3 - זכרון מטמון - הרצאה
הקדמה¶
בפרק 0.2 למדנו שיש אוגרים (מהירים, קטנים) ויש RAM (איטי, גדול). אבל יש פער ענק ביניהם - האוגרים מגיבים תוך פחות ממחזור שעון אחד, בזמן שגישה ל-RAM לוקחת כ-100 מחזורים. אם המעבד היה צריך לגשת ל-RAM בכל פעם שהוא צריך נתון, הוא היה מבזבז רוב הזמן בהמתנה.
הפתרון: זכרון מטמון - cache memory - שכבות של זכרון קטן ומהיר שיושבות בין המעבד ל-RAM ומחזיקות עותקים של הנתונים הנפוצים ביותר.
היררכיית הזכרון - memory hierarchy¶
Speed Typical size Access time
-------- ------------- ----------
Registers Fastest a few hundred B < 1ns
|
L1 cache Very fast 32-64 KB ~1 ns (4 cycles)
|
L2 cache Fast 256 KB - 1 MB ~5 ns (12 cycles)
|
L3 cache Medium 8-64 MB ~15 ns (40 cycles)
|
RAM Slow 8-128 GB ~100 ns (200+ cycles)
|
Disk (SSD) Very slow 256 GB - 4 TB ~100,000 ns (0.1ms)
|
Disk (HDD) Slowest 1-20 TB ~10,000,000 ns (10ms)
כמה נקודות חשובות:
- L1 מפוצל: יש L1 נפרד להוראות (L1I) ו-L1 נפרד לנתונים (L1D). זה פותר את סכנת המבנה שלמדנו בפרק 8.1 - שלב IF קורא מ-L1I ושלב MEM קורא/כותב ל-L1D בו-זמנית.
- L1 ו-L2 לכל ליבה: בעידן הרב-ליבתי, כל ליבה במעבד יש לה L1 ו-L2 פרטיים.
- L3 משותף: הcache L3 משותף לכל הליבות. הוא גדול יותר אבל איטי יותר.
- הפרש פי 100: הפער בין L1 (1ns) ל-RAM (100ns) הוא פי 100. זה כאילו ההבדל בין לשלוף ספר מהמדף ליד (L1) לבין לנסוע לספרייה העירונית (RAM).
למה cache עובד - עקרונות מקומיות - locality principles¶
הcache הוא קטן - 64KB של L1 מול 16GB של RAM. איך cache כל כך קטן יכול להיות יעיל? בגלל שתוכנות לא ניגשות לזכרון באופן אקראי. יש שני דפוסים חזקים:
מקומיות זמנית - temporal locality¶
אם ניגשת לכתובת מסוימת, סביר שתיגש אליה שוב בקרוב.
דוגמאות: משתנה counter בלולאה, מצביע ההוראה (IP) שרץ על אותו קוד שוב ושוב בלולאה, הראש של רשימה מקושרת שניגשים אליו בכל צעד.
מקומיות מרחבית - spatial locality¶
אם ניגשת לכתובת מסוימת, סביר שתיגש לכתובות סמוכות בקרוב.
דוגמאות: סריקה של מערך (כתובת i, אחריה כתובת i+1, אחריה i+2...), ביצוע קוד רצף (הוראה אחרי הוראה), גישה לשדות של struct (שדה אחד ליד השני בזכרון).
הcache מנצל את שני הדפוסים: כשניגשים לכתובת, הוא טוען אותה ואת הסביבה שלה (מקומיות מרחבית), ושומר אותה לגישה חוזרת (מקומיות זמנית).
מבנה המטמון - cache structure¶
שורת מטמון - cache line¶
שורת הcache היא יחידת הcache הבסיסית. ברוב מעבדי x86, שורת cache היא 64 בתים.
כשאתם קוראים בית אחד מהזכרון וזה cache miss, המעבד לא מביא רק את הבית הזה - הוא מביא את כל שורת הcache (64 בתים) שמכילה אותו. למה? מקומיות מרחבית - סביר שתצטרכו גם את הבתים הסמוכים.
זה אומר שאם יש לכם מערך של int-ים (4 בתים כל אחד), גישה לאיבר אחד מביאה 16 איברים לcache (64 / 4 = 16). הגישה ל-15 האיברים הבאים תהיה cache hit - מהירה מאוד.
תגית, אינדקס, היסט - tag, index, offset¶
כל כתובת בזכרון מפורקת לשלושה חלקים שקובעים איפה הנתון נמצא בcache:
Address (e.g. 32 bit):
+------------------+---------+--------+
| Tag | Index | Offset |
+------------------+---------+--------+
- היסט - Offset (6 ביט עבור שורה של 64 בתים): מציין את המיקום בתוך שורת הcache. 6 ביט = 64 ערכים = 64 בתים.
- אינדקס - Index: מציין באיזו קבוצה (set) בcache לחפש.
- תגית - Tag: מזהה ייחודי - כשנמצא את הset, צריך לבדוק שהtag תואם כדי לוודא שזו באמת הכתובת שחיפשנו.
אסוציאטיביות - associativity¶
איך כתובת ממופה למקום בcache? יש שלוש גישות:
מיפוי ישיר - direct-mapped:
כל כתובת יכולה להיכנס רק למקום אחד ספציפי בcache (נקבע לפי הindex). מהיר לחיפוש (מסתכלים רק במקום אחד), אבל נוצרות הרבה התנגשויות - שתי כתובות שונות עם אותו index מתחרות על אותו מקום.
אסוציאטיבי מלא - fully associative:
כל כתובת יכולה להיכנס לכל מקום בcache. הכי גמיש, אין התנגשויות מיותרות, אבל החיפוש דורש השוואת tag מול כל הכניסות - יקר מאוד בחומרה. משתמשים רק בcaches קטנים מאוד (כמו TLB).
אסוציאטיבי קבוצתי - N-way set-associative:
הפשרה הנפוצה. הcache מחולק לsets, כל set מכיל N שורות (ways). כתובת ממופה לset ספציפי (לפי index), אבל בתוך הset יכולה להיכנס לכל אחת מ-N השורות.
Cache 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¶
הגישה הראשונה לשורת cache - הנתון מעולם לא היה בcache. זה בלתי נמנע.
החטאת קיבולת - capacity miss¶
הcache מלא והנתון נדחק החוצה כי אין מקום. קורה כשסט הנתונים גדול מהcache.
החטאת התנגשות - conflict miss¶
הנתון נדחק החוצה למרות שיש מקום פנוי בcache - כי הset הספציפי שלו מלא. קורה ב-direct-mapped ו-set-associative. לא קורה ב-fully associative.
מדיניות כתיבה - write policies¶
כשהמעבד כותב נתון, הוא כותב לcache. אבל מתי הנתון נכתב ל-RAM?
כתיבה מיידית - write-through¶
כל כתיבה לcache נכתבת מיד גם ל-RAM (או לשכבת הcache הבאה). פשוט אבל יוצר הרבה תעבורה לRAM.
כתיבה בעיכוב - write-back¶
כתיבה רק לcache. השורה מסומנת כ-"מלוכלכת" (dirty). רק כשהשורה נדחקת מהcache (eviction), היא נכתבת ל-RAM. מעבדים מודרניים משתמשים ב-write-back כי זה מפחית דרמטית את התעבורה ל-RAM.
קוהרנטיות מטמון - cache coherency¶
הבעיה¶
כזכור מפרק 6 (הקרנל), מעבדים מודרניים הם רב-ליבתיים. לכל ליבה יש L1 ו-L2 פרטיים. מה קורה כשליבה 0 כותבת ערך חדש לכתובת X (וזה נשמר רק ב-L1 של ליבה 0), וליבה 1 קוראת את כתובת X מה-L1 שלה ומקבלת את הערך הישן?
זה מצב של אי-קוהרנטיות - שתי ליבות רואות ערכים שונים לאותה כתובת.
פרוטוקול MESI¶
הפתרון: כל שורת cache מסומנת באחד מארבעה מצבים:
| מצב | שם | משמעות |
|---|---|---|
| M | Modified | השורה שונתה (dirty) ונמצאת רק בcache הזה. RAM מיושן. |
| E | Exclusive | השורה לא שונתה ונמצאת רק בcache הזה. |
| S | Shared | השורה לא שונתה ונמצאת בcaches של כמה ליבות. |
| I | Invalid | השורה לא תקפה - צריך לקרוא מחדש. |
כשליבה 0 כותבת לשורה:
1. אם השורה במצב M או E - כותבת ישירות (היא היחידה שמחזיקה את השורה)
2. אם השורה במצב S - שולחת הודעת invalidate לכל הליבות האחרות שמחזיקות את השורה. הן מסמנות את השורה שלהן כ-I (Invalid). רק אז ליבה 0 כותבת ומעבירה את השורה למצב M.
כשליבה 1 רוצה לקרוא שורה שמסומנת I - היא חייבת לבקש אותה מחדש (מליבה אחרת או מ-RAM).
שיתוף כוזב - false sharing¶
זוהי בעיית ביצועים מוכרת בתכנות מרובה threads. היא קורית כשתי ליבות כותבות למשתנים שונים שבמקרה נמצאים על אותה שורת cache.
// two adjacent variables in memory:
struct {
int counter_thread0; // thread 0 writes here
int counter_thread1; // thread 1 writes here
} shared;
שני המשתנים צמודים בזכרון ונמצאים על אותה שורת cache (64 בתים). כל פעם ש-thread 0 כותב ל-counter_thread0, השורה ב-L1 של ליבה 1 הופכת ל-Invalid. וכל פעם ש-thread 1 כותב ל-counter_thread1, השורה ב-L1 של ליבה 0 הופכת ל-Invalid. הcaches "מתרוצצים" ביניהם על השורה - למרות שכל thread כותב למשתנה שלו בלבד!
הפתרון - ריפוד - padding: להרחיק את המשתנים כך שיהיו על שורות cache שונות:
struct {
int counter_thread0;
char padding[60]; // padding - 60 bytes to complete to 64
int counter_thread1; // now on a different cache line
} shared;
עם הריפוד, כל thread כותב לשורת cache נפרדת - אין invalidations מיותרות, והביצועים משתפרים דרמטית.
למה זה חשוב למתכנתים¶
סריקת מערכים - סדר הגישה משנה¶
// sequential access - cache-friendly
for (int i = 0; i < N; i++)
sum += arr[i]; // consecutive addresses: arr[0], arr[1], arr[2]...
// random access - cache-unfriendly
for (int i = 0; i < N; i++)
sum += arr[random_index[i]]; // jumps to random locations
בגישה רציפה, cache miss קורה רק פעם אחת כל 16 int-ים (64 בתים / 4 = 16). שאר הגישות הן cache hits. בגישה אקראית, כמעט כל גישה היא cache miss.
מבנה מערכים מול מערך מבנים - SoA vs AoS¶
מערך מבנים - Array of Structures (AoS):
struct Particle {
float x, y, z; // position
float vx, vy, vz; // velocity
float mass; // mass
int type; // type
};
struct Particle particles[10000];
אם רוצים לחשב את סכום המסות:
כל 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;
עכשיו כל הmass-ים צמודים בזכרון - כל cache line מביא 16 ערכי mass (64/4). ניצולת מושלמת של הcache.
כפל מטריצות - הדוגמה הקלאסית¶
// naive version: 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 - כל גישה היא שורת cache אחרת. מטריצה 1000x1000 של double (8 בתים) = 8MB, הרבה יותר מ-L1 cache.
// adapted version: ikj (loop order changed)
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 ישירות ממוני החומרה:
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 | יחידת הcache הבסיסית (64 בתים ב-x86) |
| מקומיות זמנית - temporal locality | גישה חוזרת לאותו נתון |
| מקומיות מרחבית - spatial locality | גישה לנתונים סמוכים |
| אסוציאטיביות - associativity | כמה מקומות יכולה שורה לתפוס בset |
| החטאה ראשונית - compulsory miss | גישה ראשונה לשורה |
| החטאת קיבולת - capacity miss | הcache מלא |
| החטאת התנגשות - conflict miss | הset מלא |
| כתיבה בעיכוב - write-back | כתיבה ל-RAM רק ב-eviction |
| פרוטוקול MESI | קוהרנטיות cache בין ליבות |
| שיתוף כוזב - false sharing | ליבות שונות כותבות לאותה שורת cache |
בפרק הבא (8.4) נלמד על ביצוע שלא בסדר - איך המעבד מצליח להימנע מלחכות כשיש cache miss.