8.4 ביצוע שלא בסדר פתרון
פתרון תרגול - ביצוע שלא בסדר¶
1. זיהוי הוראות עצמאיות¶
גרף תלויות:
(1) mov eax, [rdi] (2) mov ebx, [rsi] (4) mov ecx, [rdx] (6) sub edx, 10
| | | |
+---- RAW eax ---------+ | |
| | | |
v v v |
(3) add eax, ebx (5) mul ecx, ecx |
| | |
| RAW eax +---- RAW ecx ---------+
v | |
(7) mov [r8], eax v v
(8) add ecx, edx
תלויות:
- (3) תלוי ב-(1) ו-(2): RAW על eax ו-ebx
- (5) תלוי ב-(4): RAW על ecx
- (7) תלוי ב-(3): RAW על eax
- (8) תלוי ב-(5) ו-(6): RAW על ecx ו-edx
ביצוע OoO (2 ALU + 1 Load/Store):
מחזור: 1 2 3 4 5 6 7 8 9 10
Load: (1) (2) .. .. (4) .. .. .. (7)
ALU-1: (6) .. .. (3) .. (8)
ALU-2: (5) .. ..
בואו נחשב יותר בקפידה:
- מחזור 1-4: הוראה (1) מתבצעת (load, 4 מחזורים). תוצאה מוכנה בסוף מחזור 4.
- מחזור 2-5: הוראה (2) מתחילה במחזור 2 (Load unit פנויה אחרי שליחת (1)). מוכנה בסוף מחזור 5. רגע - יש רק load unit אחת. (2) מתחילה במחזור 2 כי הload unit עובדת pipelined - (1) כבר שלחה את הבקשה.
בפועל, נניח שload unit pipelined ויכולה לקבל load חדש כל מחזור:
- מחזור 1: start load (1)
- מחזור 2: start load (2)
- מחזור 3: start load (4)
- מחזור 4: (1) ready. (6) מתבצע ב-ALU (לא תלוי בכלום, מחזור אחד)
- מחזור 5: (2) ready.
- מחזור 6: (3) = add eax, ebx - (1) ו-(2) מוכנים. מחזור אחד. + (5) = mul ecx - (4) מוכן. 3 מחזורים.
- מחזור 7: (3) ready.
- מחזור 8: (5) ready. + (7) = store - (3) מוכן.
- מחזור 9: (8) = add ecx, edx - (5) ו-(6) מוכנים. מחזור אחד.
סה"כ OoO: 9 מחזורים (מוגבל על ידי latency של loads + שרשרת (4)->(5)->(8)).
ביצוע in-order:
סה"כ in-order: 4 + 4 + 1 + 4 + 3 + 1 + 1 + 1 = 19 מחזורים
IPC:
- OoO: 8 הוראות / 9 מחזורים = 0.89 IPC
- In-order: 8 / 19 = 0.42 IPC
OoO שיפר פי 2.1 במקרה הזה.
2. שינוי שמות אוגרים¶
סעיף 1 - תלויות:
mov eax, [addr1] ; (1) כותב eax
add eax, 5 ; (2) קורא וכותב eax
mov [addr3], eax ; (3) קורא eax
mov eax, [addr2] ; (4) כותב eax
add eax, 10 ; (5) קורא וכותב eax
mov [addr4], eax ; (6) קורא eax
| תלות | מ/אל | סוג | אוגר |
|---|---|---|---|
| (1) -> (2) | 1 -> 2 | RAW | eax |
| (2) -> (3) | 2 -> 3 | RAW | eax |
| (2) -> (4) | 2 -> 4 | WAW | eax (שניהם כותבים) |
| (3) -> (4) | 3 -> 4 | WAR | eax (3 קורא, 4 כותב) |
| (4) -> (5) | 4 -> 5 | RAW | eax |
| (5) -> (6) | 5 -> 6 | RAW | eax |
| (1) -> (4) | 1 -> 4 | WAW | eax (שניהם כותבים) |
סעיף 2 - אחרי register renaming:
mov P1, [addr1] ; (1) eax -> P1
add P2, P1, 5 ; (2) קורא P1, כותב P2
mov [addr3], P2 ; (3) קורא P2
mov P3, [addr2] ; (4) eax -> P3 (שם חדש!)
add P4, P3, 10 ; (5) קורא P3, כותב P4
mov [addr4], P4 ; (6) קורא P4
סעיף 3 - תלויות שנשארו ונעלמו:
נשארו (RAW אמיתיות):
- (1) -> (2): P1
- (2) -> (3): P2
- (4) -> (5): P3
- (5) -> (6): P4
נעלמו (תלויות כוזבות):
- (2) -> (4) WAW: נעלם! P2 ו-P3 הם אוגרים שונים
- (3) -> (4) WAR: נעלם! (3) קורא P2, (4) כותב P3 - אין קונפליקט
- (1) -> (4) WAW: נעלם! P1 ו-P3 הם אוגרים שונים
סעיף 4 - גרף תלויות אחרי renaming:
שתי שרשראות עצמאיות לחלוטין! יכולות לרוץ במקביל.
בהנחת load = 4 מחזורים, add = 1, store = 1:
שרשרת A: (1)[4cyc] -> (2)[1cyc] -> (3)[1cyc] = 6 מחזורים
שרשרת B: (4)[4cyc] -> (5)[1cyc] -> (6)[1cyc] = 6 מחזורים
רצות במקביל!
זמן ביצוע מינימלי עם OoO: 6 מחזורים (שתי השרשראות רצות במקביל).
בלי renaming, שרשרת B חייבת לחכות לשרשרת A (בגלל WAW/WAR על eax): 12 מחזורים.
שיפור פי 2!
3. חיזוי IPC¶
קטע A - חישוב עצמאי:
כל איטרציה: 2 loads + 1 add + 1 store = 4 uops. הכל ב-cache.
כל איטרציה עצמאית - המעבד יכול לעבוד על כמה איטרציות במקביל.
עם 4-wide superscalar: IPC קרוב ל-3-4 (כמעט מקסימום, מוגבל על ידי רוחב הband של loads/stores).
קטע B - שרשרת תלויות:
כל איטרציה: 1 load + 1 add. אבל הadd תלוי ב-sum מהאיטרציה הקודמת!
הadd לוקח 1 מחזור, אז כל איטרציה לוקחת לפחות 1 מחזור (latency של add). ה-load יכול לרוץ מוקדם (בזכות OoO), אבל ה-add חייב לחכות לקודם.
IPC: כ-1-2. שרשרת התלויות על sum מגבילה. ה-load רץ במקביל, אבל ה-add הוא הcritical path.
קטע C - סריקת רשימה מקושרת:
הבעיה הקשה ביותר - pointer chasing: כתובת הload הבא תלויה בתוצאת הload הנוכחי.
אם הנתונים לא ב-cache, כל load הוא cache miss (~100-200 מחזורים). OoO לא יכול לעזור כי אי אפשר להתחיל את הload הבא בלי לדעת את הכתובת שלו.
IPC: כ-0.01-0.1. המעבד מבזבז רוב הזמן בהמתנה ל-RAM. זה אחד המקרים הגרועים ביותר לביצועי מעבד מודרני.
מסקנה: מבנה נתונים מבוסס מערכים (שמנצל spatial locality) כמעט תמיד מהיר יותר מרשימות מקושרות, למרות שהcomplexity התיאורטית זהה.
4. הבנת Spectre¶
סעיף 1: כש-x חוקי (למשל x=5):
- בדיקת x < array_size -> true (5 < 16)
- קוראים secret_data[5] - נניח שהערך הוא 42
- ניגשים ל-probe_array[42 * 256] = probe_array[10752]
- מחזירים את הערך שבכתובת הזו
- בתור תופעת לוואי, שורת המטמון של probe_array[10752] נטענה לcache
סעיף 2: כש-x=200 (מחוץ לגבולות):
- בדיקת 200 < 16 -> false
- נכנסים ל-else ומחזירים 0
- לא קוראים מ-secret_data ולא ניגשים ל-probe_array
סעיף 3: עם ביצוע ספקולטיבי:
- המעבד מגיע ל-
if (x < array_size). הערך array_size לא ב-cache - צריך לחכות 200 מחזורים. - חזאי ההסתעפויות (שאומן עם x חוקי) מנחש: "התנאי מתקיים" (taken).
- המעבד ספקולטיבית מבצע את הגוף של הif:
- קורא
secret_data[200]- נניח הערך הוא 87 - חישוב
87 * 256 = 22272 - קורא
probe_array[22272]- שורת מטמון של probe_array[22272] נטענת לcache - אחרי 200 מחזורים, array_size מגיע מ-RAM. המעבד מגלה ש-200 >= 16 - הניחוש שגוי!
- ROB flush - כל התוצאות הספקולטיביות מבוטלות. הערך 87 לא נכתב לשום מקום גלוי.
אבל - שורת המטמון של probe_array[22272] עדיין ב-cache!
סעיף 4: התוקף מודד עיתויי גישה:
for (int guess = 0; guess < 256; guess++) {
start = rdtsc();
volatile char dummy = probe_array[guess * 256];
time = rdtsc() - start;
if (time < THRESHOLD) // גישה מהירה = cache hit!
printf("secret byte = %d\n", guess);
}
probe_array[87 * 256]= cache hit (כ-5ns) כי נטען ספקולטיבית- כל שאר
probe_array[X * 256]= cache miss (כ-100ns) - הגישה המהירה ביותר חושפת ש-
secret_data[200] = 87
סעיף 5: למה הROB לא מגן:
הROB מבטל את כל התוצאות הארכיטקטוניות - ערכים באוגרים וכתיבות לזכרון. מנקודת מבט לוגית, ההוראות הספקולטיביות "מעולם לא רצו".
אבל הROB לא מבטל תופעות לוואי מיקרו-ארכיטקטוניות - שינויים במטמון. שורת המטמון שנטענה ספקולטיבית נשארת ב-cache כי:
- ביטול שורות מטמון על כל misprediction יהיה יקר מדי בביצועים
- מתכנני המעבד לא חשבו שמצב הcache יכול להדליף מידע
זהו הפער בין המודל הלוגי (הכל מבוטל) למציאות הפיזית (cache state נשאר) - וזה בדיוק מה ש-Spectre מנצלת.