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

הקדמה¶

בפרק 8.1 למדנו שהצינור מבצע הוראות בסדר - הוראה 1, אחריה הוראה 2, אחריה הוראה 3. ראינו שסכנות נתונים יכולות לגרום לעיכובים (stalls) כשהוראה צריכה תוצאה שעדיין לא מוכנה. בפרק 8.3 למדנו שcache miss יכול לעלות 100-200 מחזורים. אם הוראה 1 ממתינה לנתון מהRAM, האם הוראות 2, 3, 4... חייבות גם לחכות?

התשובה במעבד מודרני: לא. מעבדים מודרניים מסוגלים לבצע הוראות שלא בסדר - out-of-order (OoO). אם הוראה 1 ממתינה לנתון, המעבד מסתכל קדימה ומבצע הוראות שלא תלויות בהוראה 1. כשהנתון מגיע, הוראה 1 מתבצעת. מבחינת המתכנת, נראה כאילו הכל רץ בסדר - אבל מתחת לפני השטח, המעבד משנה את הסדר כדי למקסם ביצועים.

למה ביצוע שלא בסדר עוזר¶

דוגמה קונקרטית:

mov eax, [addr1]    ; (1) load מזכרון - cache miss! ~200 מחזורים
add ebx, eax        ; (2) תלוי ב-(1) - חייב לחכות
mov ecx, [addr2]    ; (3) לא תלוי ב-(1) ו-(2)!
add edx, ecx        ; (4) תלוי ב-(3) בלבד
mul esi, edi         ; (5) לא תלוי בכלום שלפניו

במעבד in-order (שמבצע בסדר):
- הוראה 1 מתחילה, ממתינה 200 מחזורים לנתון מ-RAM
- הוראות 2, 3, 4, 5 ממתינות בתור - גם אם אין להן שום קשר להוראה 1
- סה"כ: 200+ מחזורים לכל 5 ההוראות

במעבד out-of-order:
- הוראה 1 מתחילה, ממתינה לנתון
- הוראה 2 ממתינה (תלויה ב-1)
- הוראה 3 מתבצעת (לא תלויה ב-1!)
- הוראה 4 מתבצעת אחרי 3
- הוראה 5 מתבצעת (לא תלויה בכלום!)
- כשהנתון מגיע, הוראה 1 מסתיימת והוראה 2 מתבצעת
- סה"כ: 200 מחזורים (כמעט), אבל הוראות 3, 4, 5 כבר סיימו

המעבד "מילא" את זמן ההמתנה בעבודה שימושית.

אלגוריתם Tomasulo ותחנות שמירה - reservation stations¶

הרעיון המרכזי פותח ע"י Robert Tomasulo ב-IBM ב-1967 ומשמש (בגרסאות מודרניות) עד היום.

העיקרון¶

במקום שהוראות יושבות בצינור ומחכות בסדר, הן נשלחות לתחנות שמירה - reservation stations. כל תחנה מחזיקה הוראה אחת ועוקבת אחרי התלויות שלה. ברגע שכל האופרנדים מוכנים - ההוראה מופנית ליחידת הביצוע.

הוראה נכנסת -> מפוענחת -> נכנסת לתחנת שמירה
                              |
                    ממתינה לאופרנדים
                              |
                    כל האופרנדים מוכנים?
                     /              \
                   כן               לא
                   |                |
             נשלחת לביצוע    ממשיכה לחכות

שידור תוצאות - Common Data Bus (CDB)¶

כשיחידת ביצוע מסיימת חישוב, התוצאה משודרת על ה-CDB (Common Data Bus) לכל תחנות השמירה. כל תחנה שממתינה לתוצאה הזו מקבלת אותה ומעדכנת את האופרנד שלה. אם עכשיו כל האופרנדים מוכנים, ההוראה יכולה לצאת לביצוע.

דוגמה מפושטת עם 3 הוראות:

תחנת שמירה 1: ADD eax, ebx    [eax=מוכן, ebx=מוכן]     -> מוכנה!
תחנת שמירה 2: SUB ecx, eax    [ecx=מוכן, eax=ממתינה]   -> ממתינה ל-eax
תחנת שמירה 3: MUL edx, esi    [edx=מוכן, esi=מוכן]     -> מוכנה!

הוראות 1 ו-3 יכולות לרוץ בו-זמנית (אם יש שתי יחידות ביצוע). כשהוראה 1 מסיימת ומשדרת את eax החדש, תחנה 2 מקבלת את הערך ומתקדמת לביצוע.

חוצץ סידור מחדש - Reorder Buffer (ROB)¶

יש בעיה: אם הוראות מתבצעות שלא בסדר, מה קורה כשיש exception? למשל, הוראה 5 מתבצעת לפני הוראה 3, והוראה 3 גורמת לsegmentation fault. ההוראה 5 כבר שינתה אוגרים - אבל מבחינה לוגית, היא אמורה לא לרוץ כלל!

הפתרון: חוצץ סידור מחדש - Reorder Buffer (ROB). ההוראות מתבצעות שלא בסדר, אבל מאושרות (committed) בסדר המקורי.

               ביצוע שלא בסדר          אישור בסדר
                    |                      |
הוראה 1: [IF][ID]...[EX]--->[ROB slot 1] --->  COMMIT
הוראה 2: [IF][ID].........[EX]->[ROB slot 2] -> COMMIT
הוראה 3: [IF][ID].[EX]-------->[ROB slot 3] --> COMMIT

כשהוראה מסיימת ביצוע, התוצאה שלה נכתבת ל-ROB (לא ישירות לאוגרים האמיתיים)
ה-ROB מנהל תור FIFO - הוראות מאושרות בסדר שנכנסו
כשהוראה בראש התור מוכנה - היא מאושרת (committed), והתוצאה נכתבת לאוגרים/זכרון
אם הוראה גורמת ל-exception - כל ההוראות שאחריה ב-ROB מבוטלות (אף פעם לא אושרו)

זה מבטיח exceptions מדויקות - precise exceptions: מנקודת המבט של התוכנה, כל ההוראות עד הexception בוצעו, וכל ההוראות אחריה לא בוצעו - בדיוק כמו במעבד in-order.

שינוי שמות אוגרים - register renaming¶

תלויות אמיתיות ותלויות כוזבות¶

לא כל תלות בין הוראות היא אמיתית. יש שלושה סוגי תלויות:

RAW - Read After Write (תלות אמיתית):

add eax, ebx    ; כותב ל-eax
sub ecx, eax    ; קורא מ-eax - חייב לחכות!

WAR - Write After Read (תלות כוזבת):

add ecx, eax    ; קורא מ-eax
mov eax, 5      ; כותב ל-eax - אבל לא באמת תלוי!

WAW - Write After Write (תלות כוזבת):

mov eax, [addr1]   ; כותב ל-eax
mov eax, [addr2]   ; כותב ל-eax שוב - אבל לא באמת תלוי!

תלויות WAR ו-WAW הן כוזבות - הן נוצרות רק כי שתי הוראות שונות משתמשות באותו שם אוגר, לא כי יש תלות אמיתית בנתונים.

הפתרון: שינוי שמות¶

למעבד x86-64 יש 16 אוגרים כלליים (rax, rbx, rcx, ...). אבל בתוך המעבד יש הרבה יותר אוגרים פיזיים - 180 ומעלה במעבדי Intel מודרניים.

כשהוראה נכנסת למעבד, כל כתיבה לאוגר מקבלת אוגר פיזי חדש. כך שתי הוראות שכותבות ל-"eax" בעצם כותבות לאוגרים פיזיים שונים.

דוגמה:

; קוד מקורי:          ; אחרי register renaming:
mov eax, [addr1]       ; mov P1, [addr1]    (eax -> P1)
add eax, 1             ; add P2, P1, 1      (eax -> P2)
mov eax, [addr2]       ; mov P3, [addr2]    (eax -> P3)  -- לא תלוי ב-P1/P2!
add eax, 2             ; add P4, P3, 2      (eax -> P4)

אחרי שינוי השמות, ברור שההוראות 1-2 והוראות 3-4 הן עצמאיות לחלוטין ויכולות לרוץ במקביל! בלי שינוי שמות, הוראה 3 "תלויה" בהוראה 2 (שתיהן כותבות ל-eax) - WAW כוזב.

ביצוע על-סקלרי - superscalar execution¶

מעבדים מודרניים לא רק מבצעים הוראות שלא בסדר - הם מבצעים כמה הוראות בו-זמנית בכל מחזור שעון. זה נקרא ביצוע על-סקלרי.

מעבד Intel או AMD מודרני יכול להנפיק (issue) 4-6 uops למחזור, ולהריץ אותם על יחידות ביצוע מרובות:

יחידות ביצוע טיפוסיות במעבד מודרני:

Port 0: ALU, כפל שלמים, FP mul, branch
Port 1: ALU, כפל שלמים, FP add
Port 2: Load (קריאה מזכרון)
Port 3: Load (קריאה מזכרון)
Port 4: Store data (כתיבת נתון)
Port 5: ALU, shuffle, vector
Port 6: ALU, branch
Port 7: Store address (חישוב כתובת כתיבה)

בכל מחזור שעון, המעבד יכול לשלוח uop לכל port - עד 8 פעולות בו-זמנית!

הוראות למחזור - IPC (Instructions Per Cycle)¶

ה-IPC מודד כמה הוראות (בפועל, uops) מסתיימות בממוצע כל מחזור:
- מקסימום תיאורטי: 4-6 (תלוי בארכיטקטורה)
- קוד אמיתי טיפוסי: 2-3 IPC
- קוד עם הרבה cache misses: יכול לרדת ל-0.5 IPC ומטה

למה IPC בפועל נמוך מהמקסימום? בגלל:
- תלויות בין הוראות (גם אחרי renaming)
- cache misses שגורמים להמתנה
- branch mispredictions שגורמים לflush
- שרשראות תלויות ארוכות (כמו linked list traversal)

סדר הזכרון - memory ordering¶

ביצוע שלא בסדר מסבך את הגישה לזכרון. מה קורה כשהוראת load (קריאה) ו-store (כתיבה) מתבצעות שלא בסדר?

המעבד מרשה חלק מהסידורים מחדש¶

ב-x86, המעבד מבטיח:
- Loads לא עוברות loads: אם קריאה A לפני קריאה B בקוד, A תסתיים לפני B
- Stores לא עוברות stores: כתיבות מתבצעות בסדר המקורי
- Stores לא עוברות loads: כתיבה לא תסתיים לפני קריאה שלפניה

אבל: Loads יכולות לעבור stores (לכתובות שונות)! המעבד יכול לקרוא מכתובת Y לפני שכתב לכתובת X, גם אם הכתיבה ל-X הייתה קודם בקוד.

מחסומי זכרון - memory fences¶

כשצריך לאכוף סדר מסוים (למשל, בתכנות מקבילי), משתמשים בהוראות מיוחדות:

mfence (memory fence): מחכה שכל הloads והstores שלפניה יסתיימו לפני שממשיכים
lfence (load fence): מחכה שכל הloads שלפניה יסתיימו
sfence (store fence): מחכה שכל הstores שלפניה יסתיימו

בתכנות מקבילי (כמו שלמדנו בפרק 5.8 על threads ובפרק 6.10 על סנכרון בקרנל), סדר הזכרון הוא קריטי. אם thread אחד כותב נתון ואז כותב דגל "ready", thread אחר יכול לראות את הדגל לפני הנתון - בגלל memory reordering! מחסומי זכרון מונעים את זה.

ביצוע ספקולטיבי ו-Spectre/Meltdown¶

בפרק 8.2 הזכרנו בקצרה שביצוע ספקולטיבי עלול להשאיר עקבות במטמון. עכשיו שאנחנו מבינים OoO, ROB, ומטמון, נוכל להבין את Spectre ו-Meltdown לעומק.

Spectre (Variant 1) - עקיפת בדיקת גבולות¶

// קוד של הקורבן:
if (x < array1_size) {           // בדיקת גבולות
    char value = array1[x];       // גישה לגיטימית
    char dummy = array2[value * 256];  // גישה תלויה בvalue
}

מה התוקף עושה:
1. מאמן את חזאי ההסתעפויות שהcondition x < array1_size תמיד מתקיים (על ידי קריאה חוזרת עם x חוקי)
2. גורם ל-array1_size להידחק מהcache (cache flush)
3. שולח x שהוא מחוץ לגבולות (למשל, x שגורם ל-array1[x] לקרוא מזכרון של הקרנל)

מה קורה:
1. הcondition x < array1_size צריך לקרוא את array1_size מ-RAM (cache miss!) - לוקח 200 מחזורים
2. החזאי מנחש "כן" (כי אומן כך) - הcondition ספקולטיבית מתקבל
3. המעבד מבצע ספקולטיבית array1[x] - קורא בית מזכרון אסור!
4. המעבד מבצע ספקולטיבית array2[value * 256] - טוען שורת מטמון שתלויה ב-value
5. הcondition מתגלה כ-false - כל התוצאות הספקולטיביות מבוטלות (ROB flush)

אבל - שורת המטמון שנטענה בצעד 4 נשארת בcache! התוקף עכשיו מודד עיתויי גישה ל-array2[0*256], array2[1*256], ..., array2[255*256]. הגישה שהכי מהירה חושפת את הvalue - כי שורת המטמון שלה כבר נטענה בצעד 4.

Meltdown - קריאת זכרון קרנל¶

דומה לSpectre, אבל מנצלת את העובדה שבמעבדי Intel (עד 2018), ביצוע ספקולטיבי לא בדק הרשאות ring (ring 0 / ring 3 שלמדנו בפרק 2). הוראת load ספקולטיבית יכלה לקרוא מזכרון הקרנל, גם אם ה-user/supervisor bit בpage table (שלמדנו בפרק 2.5) אמור למנוע את זה. הבדיקה נעשתה רק ב-commit - מאוחר מדי.

מיטיגציות¶

KPTI - Kernel Page Table Isolation: הקרנל מנתק את מיפוי הזכרון שלו מpage tables של user space. כשתוכנית user רצה, דפי הקרנל פשוט לא ממופים - אפילו ספקולטיבית אי אפשר לקרוא אותם (שלמדנו בפרק 6.4).
Retpoline: טכניקה שמחליפה indirect branches (כמו jmp [rax]) בקוד שלא ניתן לcache-based side channel.
עדכוני מיקרוקוד: Intel עדכן את הmicrocode של המעבדים כדי לאפשר ניקוי של חזאי ההסתעפויות (IBRS, IBPB).
מעבדים חדשים: מאז 2019, מעבדי Intel חדשים כוללים תיקוני חומרה שמונעים Meltdown ברמת הסיליקון.

סיכום¶

מושג	הסבר
ביצוע שלא בסדר - OoO	המעבד מבצע הוראות מוכנות בלי לחכות לקודמות
תחנות שמירה - reservation stations	תורים שמחזיקים הוראות וממתינים לאופרנדים
חוצץ סידור מחדש - ROB	מבטיח שהוראות מאושרות בסדר המקורי
שינוי שמות אוגרים - register renaming	מבטל תלויות כוזבות (WAR, WAW)
ביצוע על-סקלרי - superscalar	כמה הוראות מתבצעות בו-זמנית
הוראות למחזור - IPC	מדד לניצולת המעבד
מחסום זכרון - memory fence	אוכף סדר גישות לזכרון
ביצוע ספקולטיבי - speculative execution	ביצוע על סמך ניחוש
פגיעות Spectre	ניצול עקבות ספקולטיביות במטמון

בפרק הבא (8.5) נחזור לזכרון הוירטואלי שלמדנו בפרקים 2 ו-6, ונבין לעומק את הצד החומרתי - page table walks, TLB, ו-huge pages.