לדלג לתוכן

8.3 זכרון מטמון פתרון

פתרון תרגול - זכרון מטמון

1. חישוב פרמטרי מטמון

סעיף 1:

  • שורות מטמון בסה"כ = גודל כולל / גודל שורה = 32 KB / 64 B = 32,768 / 64 = 512 שורות
  • מספר sets = שורות / associativity = 512 / 8 = 64 sets
  • ביטים ל-offset = log2(64) = 6 ביטים (כי שורה = 64 בתים)
  • ביטים ל-index = log2(64) = 6 ביטים (כי 64 sets)
  • ביטים ל-tag = 48 - 6 - 6 = 36 ביטים
כתובת 48 ביט:
[  tag: 36 ביט  |  index: 6 ביט  |  offset: 6 ביט  ]

סעיף 2:

הכתובת 0x00007F1234ABCD40 בבינארי (48 ביט):

0000 0000 0000 0111 1111 0001 0010 0011 0100 1010 1011 1100 1101 0100 0000

נפצל מימין:
- Offset (6 ביט): 000000 = 0
- Index (6 ביט): 010100 = 20 (set מספר 20)
- Tag (36 ביט): שאר הביטים = 0x00007F1234AB3 (כל מה שנשאר)

ליתר דיוק, נחשב מההקסדצימלי:
- 0x40 = 0100 0000 -> offset = 6 ביט תחתונים = 000000 = 0, הביט ה-7 (01) שייך ל-index
- 0xD40 = 1101 0100 0000 -> offset (6 LSB) = 000000, index (6 ביט הבאים) = 010100 = 20

סעיף 3:

0x0000000000001000 -> offset = 000000 (0), index = bits 6-11 של 0x1000
0x1000 = 0001 0000 0000 0000
ביטים 6-11: 000000 = set 0

0x2000 = 0010 0000 0000 0000
ביטים 6-11: 000000 = set 0

כן, שתי הכתובות ממופות לאותו set (set 0). בשתי הכתובות ביטי הindex הם 0 כי ההבדל ביניהן (0x1000 = 4096 בתים) נמצא בביטים הגבוהים (tag). הכתובות שונות רק ב-tag, אז הן "מתחרות" על אותו set. ב-8-way set-associative שתיהן יכולות להתקיים יחד (יש 8 מקומות ב-set). ב-direct-mapped היתה התנגשות.

2. חיזוי התנהגות מטמון

מטמון: 4 sets, direct-mapped, שורה 16B.
כתובת 16 ביט: tag(8) | index(2) | offset(4)

חישוב index = (כתובת >> 4) % 4 = (כתובת / 16) % 4

כתובת כתובת/16 index tag
0 0 0 0x00
16 1 1 0x00
32 2 2 0x00
48 3 3 0x00
64 4 0 0x01

טבלת גישות:

גישה כתובת tag index Hit/Miss תוכן set אחרי
1 0 0x00 0 Miss set0=tag:00
2 16 0x00 1 Miss set1=tag:00
3 32 0x00 2 Miss set2=tag:00
4 48 0x00 3 Miss set3=tag:00
5 0 0x00 0 Hit set0=tag:00 (כבר שם)
6 64 0x01 0 Miss set0=tag:01 (דחק את tag:00!)
7 0 0x00 0 Miss set0=tag:00 (דחק את tag:01!)
8 16 0x00 1 Hit set1=tag:00 (כבר שם)

סה"כ: 6 misses, 2 hits.

סעיף 3: כתובות 0 ו-64 ממופות לאותו set (set 0) אבל עם tag שונה. בdirect-mapped, כל גישה לאחת דוחקת את השנייה - זו conflict miss. ב-2-way set-associative, שתיהן יכולות להתקיים יחד ב-set 0 (שני "ways"), וגישה 7 הייתה hit במקום miss.

3. אופטימיזציה לcache

סעיף 1: סדר הגישה בזכרון:

גרסה A (row-major):

matrix[0][0], matrix[0][1], matrix[0][2], ..., matrix[0][1023],
matrix[1][0], matrix[1][1], ..., matrix[1][1023],
...

גישה רציפה בזכרון.

גרסה B (column-major):

matrix[0][0], matrix[1][0], matrix[2][0], ..., matrix[1023][0],
matrix[0][1], matrix[1][1], ..., matrix[1023][1],
...

כל גישה קופצת 1024 x 4 = 4096 בתים קדימה.

סעיף 2 - חישוב cache misses:

גרסה A:
שורת מטמון = 64B = 16 int-ים. בגישה רציפה, כל 16 גישות יש miss אחד (הראשון). שאר 15 הם hits.
- misses = 1,048,576 / 16 = 65,536 misses
- miss rate = 1/16 = 6.25%

גרסה B:
כל גישה קופצת 4096 בתים = 64 שורות מטמון. כל גישה היא לשורת מטמון אחרת. אם המטריצה גדולה מ-L1 (1024x1024x4 = 4MB >> 32KB), כל גישה מביאה שורה חדשה שדוחקת שורות ישנות. עד שנחזור לאותה שורה (אחרי 1024 גישות), היא כבר נדחקה.
- misses = כמעט 1,048,576 misses (כמעט כל גישה היא miss)
- miss rate = כמעט 100%

היחס: גרסה B איטית פי 16 בערך (או יותר, כי ב-100% miss rate יש גם קנסות נוספים של eviction/writeback).

סעיף 3: תוצאות טיפוסיות עם N=4096:

version A (row-major):    0.012 sec
version B (column-major): 0.150 sec
ratio: ~12.5x

סעיף 4 - בונוס:
שיטה מהירה יותר - memset:

memset(matrix, 0, sizeof(matrix));

memset מותאם ל-SIMD ויכול לאפס 64 בתים (שורת מטמון שלמה) במכה אחת עם הוראות vmovaps (AVX). בנוסף, הקומפיילר ומערכת ההפעלה יכולים להשתמש ב-non-temporal stores שעוקפים את הcache (כותבים ישירות ל-RAM) כשכותבים כמויות גדולות - כך לא ממלאים את הcache בנתוני אפסים שלא צריך לקרוא שוב.

4. ניתוח false sharing

סעיף 1: תוצאות טיפוסיות:

shared (false sharing): 1.200 sec
padded (no sharing):    0.250 sec
ratio: 4.80x

היחס נע בין 2x ל-10x תלוי במעבד ובמספר הליבות.

סעיף 2: מה קורה בניסוי 1 (בלי padding):

  • counter0 ו-counter1 הם שני long-ים (8 בתים כל אחד) צמודים בזכרון. שניהם על אותה שורת מטמון (64 בתים).
  • כש-thread 0 (רץ על ליבה 0) כותב ל-counter0:
  • הליבה 0 צריכה את השורה במצב M (Modified) לפי פרוטוקול MESI
  • היא שולחת invalidate לליבה 1
  • השורה בcache של ליבה 1 הופכת ל-I (Invalid)
  • ליבה 0 כותבת ומסמנת M
  • כש-thread 1 (רץ על ליבה 1) רוצה לכתוב ל-counter1:
  • השורה בcache שלו במצב I - חייב לבקש אותה מליבה 0
  • ליבה 0 שולחת את השורה (write-back) וחוזרת למצב I
  • ליבה 1 מקבלת את השורה, מסמנת M, כותבת
  • אם ליבה 0 רוצה שוב לכתוב ל-counter0 - חוזרים להתחלה

כל כתיבה גורמת ל-"pingpong" של שורת המטמון בין הליבות. כל transfer כזה לוקח עשרות מחזורים.

סעיף 3: עם padding, counter0 ו-counter1 נמצאים על שורות מטמון שונות (56 בתים ריפוד + 8 בתים counter0 = 64 בתים = שורה שלמה). ליבה 0 כותבת לשורה X וליבה 1 כותבת לשורה Y - אין שום קשר ביניהן. כל ליבה מחזיקה את השורה שלה במצב M בלי להפריע לשנייה.

סעיף 4: אם שני הthreads רצים על אותה ליבה (עם taskset):
- שני הthreads חולקים את אותו L1 cache
- אין תקשורת בין ליבות כי יש רק ליבה אחת
- אין invalidations כי אין ליבה שנייה שמחזיקה עותק
- ההבדל בין shared ל-padded יעלם (או יהיה זניח)

הthread-ים עדיין מתחלפים (context switch) על אותה ליבה, אבל כשthread מקבל את הליבה, השורה כבר במטמון - אין misprediction ואין invalidation.