8.3 זכרון מטמון תרגול

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

תרגיל 1 - חישוב פרמטרי מטמון

נתון מטמון L1 עם הפרמטרים הבאים:
- גודל כולל: 32 KB
- גודל שורה: 64 בתים
- אסוציאטיביות: 8-way set-associative
- כתובות של 48 ביט

1. חשבו:
2. כמה שורות מטמון יש בסה"כ?
3. כמה sets יש?
4. כמה ביטים ל-offset?
5. כמה ביטים ל-index?

6. כמה ביטים ל-tag?

7. נתונה הכתובת (בהקסדצימלי): 0x00007F1234ABCD40

8. מהו הoffset?
9. מהו הindex (מספר הset)?

10. מהו הtag?

11. נתונות שתי כתובות: 0x0000000000001000 ו-0x0000000000002000. האם הן ממופות לאותו set? הסבירו.

---

תרגיל 2 - חיזוי התנהגות מטמון

נתון מטמון direct-mapped (1-way) עם:
- 4 שורות (4 sets)
- גודל שורה: 16 בתים
- כתובות של 16 ביט

חלוקת כתובת: tag (8 ביט) | index (2 ביט) | offset (4 ביט)

נתונה סדרת גישות לכתובות (בדצימלי): 0, 16, 32, 48, 0, 64, 0, 16

1. מלאו טבלה עבור כל גישה:

גישה	כתובת	tag	index	offset	Hit/Miss	מצב הset אחרי
1	0	0x00	0	0	?	?
2	16	?	?	?	?	?
...

1. כמה hits וכמה misses?
2. שימו לב שכתובות 0 ו-64 ממופות לאותו set. מה קורה? איך מטמון 2-way set-associative היה פותר את הבעיה?

---

תרגיל 3 - אופטימיזציה לcache

נתונות שתי גרסאות של קוד שמאפס מטריצה:

גרסה A - לפי שורות:

#define N 1024
int matrix[N][N];

// גרסה A: i אחרי j (שורה-שורה)
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        matrix[i][j] = 0;

גרסה B - לפי עמודות:

// גרסה B: j אחרי i (עמודה-עמודה)
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        matrix[i][j] = 0;

1. ב-C, מטריצה int matrix[N][N] מאוחסנת ב-row-major order - כלומר matrix[0][0], matrix[0][1], ..., matrix[0][1023], matrix[1][0], matrix[1][1], ... ציירו (סכמטית) את סדר הגישה לזכרון של כל גרסה.

2. חשבו את שיעור ה-cache miss עבור L1D (32KB, שורה 64B):

3. גרסה A: כמה misses מתוך 1024x1024 = 1,048,576 גישות?

4. גרסה B: כמה misses?
   (רמז: int הוא 4 בתים, שורת מטמון 64 בתים = 16 int-ים)

5. כתבו תוכנית שמודדת את זמן הריצה של שתי הגרסאות (עם N=4096 להבדל ברור). מה היחס?

6. (בונוס) הציעו שיטה לאפס את המטריצה שהיא אפילו יותר מהירה מגרסה A.

---

תרגיל 4 - ניתוח false sharing

נתון הקוד הבא שמריץ שני threads, כל אחד סופר עד 100 מיליון:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

struct shared_data {
    long counter0;
    long counter1;
};

struct padded_data {
    long counter0;
    char pad[56];  // padding to separate cache lines
    long counter1;
};

void *increment(void *arg) {
    long *counter = (long *)arg;
    for (long i = 0; i < 100000000L; i++) {
        (*counter)++;
    }
    return NULL;
}

int main() {
    struct timespec start, end;
    pthread_t t1, t2;

    // --- ניסוי 1: בלי padding (false sharing) ---
    struct shared_data shared = {0, 0};

    clock_gettime(CLOCK_MONOTONIC, &start);
    pthread_create(&t1, NULL, increment, &shared.counter0);
    pthread_create(&t2, NULL, increment, &shared.counter1);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    clock_gettime(CLOCK_MONOTONIC, &end);

    double t_shared = (end.tv_sec - start.tv_sec)
                    + (end.tv_nsec - start.tv_nsec) / 1e9;

    // --- ניסוי 2: עם padding (בלי false sharing) ---
    struct padded_data padded = {0, .counter1 = 0};

    clock_gettime(CLOCK_MONOTONIC, &start);
    pthread_create(&t1, NULL, increment, &padded.counter0);
    pthread_create(&t2, NULL, increment, &padded.counter1);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    clock_gettime(CLOCK_MONOTONIC, &end);

    double t_padded = (end.tv_sec - start.tv_sec)
                    + (end.tv_nsec - start.tv_nsec) / 1e9;

    printf("shared (false sharing): %.3f sec\n", t_shared);
    printf("padded (no sharing):    %.3f sec\n", t_padded);
    printf("ratio: %.2fx\n", t_shared / t_padded);

    return 0;
}

1. קמפלו עם gcc -O2 -pthread -o false_sharing false_sharing.c והריצו. מה היחס?

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

3. על איזה שורת מטמון נמצאים counter0 ו-counter1?
4. מה קורה כשthread 0 כותב ל-counter0?

5. מה thread 1 צריך לעשות כדי לכתוב ל-counter1?

6. הסבירו למה ניסוי 2 (עם padding) מהיר יותר.

7. מה היה קורה אם היינו מריצים את שני הthreads על אותה ליבה (באמצעות taskset -c 0 ./false_sharing)? האם ההבדל בין shared ל-padded היה גדול? קטן? נעלם? הסבירו.