8.4 ביצוע שלא בסדר תרגול

תרגול - ביצוע שלא בסדר¶

תרגיל 1 - זיהוי הוראות עצמאיות¶

נתון קטע הקוד הבא:

mov eax, [rdi]       ; (1) load A
mov ebx, [rsi]       ; (2) load B
add eax, ebx         ; (3) eax = A + B
mov ecx, [rdx]       ; (4) load C
mul ecx, ecx         ; (5) ecx = C * C
sub edx, 10          ; (6) edx = edx - 10
mov [r8], eax        ; (7) store A+B
add ecx, edx         ; (8) ecx = C*C + (edx-10)

ציירו גרף תלויות (dependency graph) של ההוראות. לכל הוראה, ציינו מאילו הוראות היא תלויה ולמה.
בהנחה שיש 3 יחידות ביצוע (2 ALU + 1 Load/Store), ושכל פעולה לוקחת מחזור אחד (חוץ מload שלוקח 4 מחזורים, ומul שלוקח 3 מחזורים), כמו כן נניח שמבצעים load אחד בכל פעם:
מהו זמן הביצוע הקצר ביותר האפשרי עם OoO execution?
מהו זמן הביצוע ב-in-order execution?
מהו ה-IPC (Instructions Per Cycle) בכל מקרה?

תרגיל 2 - שינוי שמות אוגרים¶

נתון הקוד הבא:

mov eax, [addr1]     ; (1)
add eax, 5           ; (2)
mov [addr3], eax     ; (3)
mov eax, [addr2]     ; (4)
add eax, 10          ; (5)
mov [addr4], eax     ; (6)

זהו את כל התלויות: RAW (Read After Write), WAR (Write After Read), WAW (Write After Write). רשמו כל תלות כזוג (הוראה X -> הוראה Y, סוג, אוגר).
בצעו register renaming ידני. החליפו כל כתיבה ל-eax באוגר פיזי חדש (P1, P2, P3, ...) וכל קריאה מ-eax באוגר הפיזי האחרון שנכתב. כתבו את הקוד אחרי renaming.
אחרי הrenaming, איזה תלויות נשארו? איזה תלויות נעלמו?
ציירו גרף תלויות של הקוד אחרי renaming. כמה שרשראות עצמאיות יש? מהו זמן הביצוע המינימלי עם OoO?

תרגיל 3 - חיזוי IPC¶

נתונים שלושה קטעי קוד. עבור כל קטע, העריכו את ה-IPC (בהנחת מעבד 4-wide superscalar עם OoO). הסבירו את ההערכה.

קטע A - חישוב עצמאי:

for (int i = 0; i < N; i++) {
    a[i] = b[i] + c[i];
}

(כל איטרציה עצמאית מהאחרות. הנחה: כל הנתונים ב-cache.)

קטע B - שרשרת תלויות:

int sum = 0;
for (int i = 0; i < N; i++) {
    sum += a[i];
}

(כל איטרציה תלויה בקודמת דרך sum. הנחה: כל הנתונים ב-cache.)

קטע C - סריקת רשימה מקושרת:

struct node *p = head;
while (p != NULL) {
    sum += p->value;
    p = p->next;    // pointer chasing!
}

(כל איטרציה תלויה בקודמת דרך p->next. הנחה: הרשימה לא ב-cache.)

תרגיל 4 - הבנת Spectre¶

קראו את קטע הקוד הבא, שמציג את הרעיון הבסיסי של Spectre Variant 1:

// מערך של הקורבן
char secret_data[256] = { /* נתונים סודיים */ };
int array_size = 16;      // גודל מערך חוקי
char probe_array[256 * 256];  // מערך בדיקה

char victim_function(int x) {
    if (x < array_size) {        // בדיקת גבולות
        return probe_array[secret_data[x] * 256];
    }
    return 0;
}

הסבירו מה הפונקציה עושה כשx חוקי (למשל x=5). מה הערך שחוזר?
מה קורה כש-x = 200 (מחוץ לגבולות)? בלי ביצוע ספקולטיבי, מה היה קורה?
הסבירו צעד-צעד מה קורה עם ביצוע ספקולטיבי כשהתוקף:
שולח x=200 אחרי שגרם ל-array_size להידחק מהcache
אימן את חזאי ההסתעפויות עם ערכי x חוקיים
איך התוקף יכול לגלות את הערך של secret_data[200] על ידי מדידת עיתויי גישה ל-probe_array? הסבירו.
למה הROB (Reorder Buffer) לא מגן מפני Spectre? הרי כל התוצאות הספקולטיביות מבוטלות...