8.2 חיזוי הסתעפויות הרצאה

הקדמה

בפרק 8.1 ראינו שסכנות בקרה (control hazards) הן אחת הבעיות המרכזיות בצינור ההוראות. כשהמעבד מגיע להוראת הסתעפות מותנית (כמו jz, jne, jg שלמדנו בפרקים 1.3 ו-2), הוא לא יודע לאן לקפוץ עד ששלב EX מחשב את התנאי. אבל הצינור לא יכול לחכות - הוא צריך להמשיך לטעון הוראות עכשיו.

הפתרון: חיזוי הסתעפויות - branch prediction. המעבד מנחש לאן ההסתעפות תלך, וממשיך לעבוד על סמך הניחוש. אם ניחש נכון - מעולה, אין שום עיכוב. אם ניחש לא נכון - שטיפת צינור (pipeline flush) ותחילה מחדש.

---

המחיר של טעות - branch misprediction penalty

כשהמעבד מנחש לא נכון, כל ההוראות שנכנסו לצינור על סמך הניחוש השגוי צריכות להיזרק. ההוראות האלה כבר עברו שלבי IF, ID, ואולי אפילו EX - כל העבודה הזו הולכת לאיבוד.

המחיר תלוי ישירות בעומק הצינור:

ארכיטקטורה	עומק צינור	מחיר טעות (מחזורים)
צינור קלאסי 5 שלבים	5	2-3
Intel Core (Skylake)	14-19	15-20
Intel Pentium 4 (Prescott)	31	כ-30

במעבד מודרני עם תדר של 4 GHz, כל מחזור הוא 0.25 ננושניות. שטיפת צינור של 15 מחזורים זה 3.75 ננושניות - זמן שבו המעבד יכול היה לבצע 60-90 uops (מיקרו-פעולות). זה הרבה עבודה מבוזבזת.

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

---

חיזוי סטטי - static prediction

השיטות הפשוטות ביותר לא דורשות זכרון ולא לומדות מהעבר:

שיטה 1 - תמיד לא נלקח (always predict not-taken):
המעבד תמיד מניח שהסתעפות לא תתקיים, וממשיך לטעון את ההוראה הבאה ברצף. שיטה פשוטה, אבל מפספסת בערך 60% מההסתעפויות בקוד אמיתי (כי רוב הלולאות כן קופצות חזרה).

שיטה 2 - הכלל של אחורה/קדימה (BTFN - Backward Taken, Forward Not-taken):
- הסתעפות אחורה (לכתובת נמוכה יותר) - מנחשים שכן תתקיים. למה? כי הסתעפות אחורה היא בדרך כלל סגירת לולאה, ולולאות מתבצעות הרבה פעמים.
- הסתעפות קדימה (לכתובת גבוהה יותר) - מנחשים שלא תתקיים. הסתעפות קדימה היא בדרך כלל תנאי if שלעתים קרובות לא מתקיים.

שיטה 2 טובה יותר - בערך 65% דיוק. אבל 65% זה רחוק מלהספיק למעבד מודרני.

---

חיזוי דינמי - dynamic prediction

חיזוי דינמי לומד מההיסטוריה - הוא זוכר מה ההסתעפות עשתה בעבר ומנחש שהיא תעשה את אותו הדבר שוב.

טבלת היסטוריית הסתעפויות - Branch History Table (BHT)

הBHT היא טבלה שמחזיקה מידע על הסתעפויות שהמעבד כבר ראה. כל כניסה בטבלה מזוהה לפי (חלק מ)כתובת ההסתעפות, ומכילה מידע על התנהגותה בעבר.

חזאי 1-ביט - 1-bit predictor

השיטה הפשוטה ביותר: זכור מה ההסתעפות עשתה בפעם האחרונה, ונחש את אותו הדבר.

מצב 0: "לא נלקח" --> ניחוש: לא נלקח
מצב 1: "נלקח"     --> ניחוש: נלקח

אם ההסתעפות נלקחה - עבור למצב 1.
אם לא נלקחה - עבור למצב 0.

הבעיה עם חזאי 1-ביט: חשבו על לולאה שרצה 10 פעמים:

הסתעפות: נלקח, נלקח, נלקח, ..., נלקח, לא-נלקח, נלקח, נלקח, ...
ניחוש:   ???,    נלקח, נלקח, ..., נלקח, נלקח,    לא-נלקח, נלקח, ...
נכון:    ???,    V,     V,    ..., V,     X,        X,       V, ...

החזאי טועה פעמיים - פעם אחת כשהלולאה מסתיימת (ניחש נלקח, אבל יצאנו מהלולאה), ופעם שניה כשהלולאה מתחילה שוב (ניחש לא-נלקח, אבל חזרנו ללולאה). לולאה שרצה 10 פעמים: 2 טעויות מתוך 10 = 80% דיוק.

חזאי 2-ביט - 2-bit predictor (saturating counter)

הפתרון: לא לשנות את הניחוש אחרי טעות אחת - לדרוש שתי טעויות רצופות לפני שמשנים כיוון.

מכונת המצבים:

     נלקח          נלקח          לא-נלקח      לא-נלקח
  +--------+    +--------+    +--------+    +--------+
  |  חזק   | -> |  חלש   | -> |  חלש   | -> |  חזק   |
  | נלקח   |    | נלקח   |    |לא-נלקח|    |לא-נלקח|
  |  (11)  |    |  (10)  |    |  (01)  |    |  (00)  |
  +--------+    +--------+    +--------+    +--------+
   לא-נלקח:      לא-נלקח:     נלקח:         נלקח:
   עבור ל-10     עבור ל-01    עבור ל-10     עבור ל-01

ארבעת המצבים:
- חזק נלקח - Strongly Taken (11): ניחוש: נלקח. אם טעינו, עוברים לחלש נלקח (10).
- חלש נלקח - Weakly Taken (10): ניחוש: נלקח. אם טעינו, עוברים לחלש לא-נלקח (01).
- חלש לא-נלקח - Weakly Not Taken (01): ניחוש: לא נלקח. אם טעינו, עוברים לחלש נלקח (10).
- חזק לא-נלקח - Strongly Not Taken (00): ניחוש: לא נלקח. אם טעינו, עוברים לחלש לא-נלקח (01).

עכשיו בלולאה שרצה 10 פעמים: החזאי טועה רק פעם אחת - כשהלולאה מסתיימת. כשהיא מתחילה שוב, החזאי עדיין במצב "חלש נלקח" (10) ומנחש נכון. הדיוק עולה ל-90%.

---

חוצץ מטרת הסתעפות - Branch Target Buffer (BTB)

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

הBTB הוא מטמון (cache) שמחזיק את כתובת היעד של הסתעפויות שכבר נראו. המפתח הוא כתובת הוראת ההסתעפות, והערך הוא כתובת היעד.

BTB:
+--------------------+--------------------+
| כתובת הסתעפות      | כתובת יעד          |
+--------------------+--------------------+
| 0x004010A0         | 0x00401020         |
| 0x004011B4         | 0x004011E0         |
| 0x00401200         | 0x00401150         |
+--------------------+--------------------+

התהליך המלא:
1. שלב IF מקבל את כתובת ההוראה הנוכחית
2. במקביל לקריאת ההוראה, הכתובת נבדקת בBTB
3. אם יש hit בBTB וגם החזאי (BHT) אומר "נלקח" - שלב IF מתחיל מיד לטעון הוראות מכתובת היעד
4. כל זה קורה לפני שההוראה בכלל פוענחה! המעבד עדיין לא יודע שזו הסתעפות - הוא פשוט מזהה את הכתובת

בזכות הBTB, גם הוראות call ו-ret (קריאה לפונקציה וחזרה ממנה) יכולות להתחזות ביעילות. למעשה, מעבדים מודרניים מחזיקים גם מחסנית חזרות - Return Stack Buffer (RSB) שחוזה את כתובת החזרה מפונקציות.

---

חזאים מודרניים

המציאות הרבה יותר מורכבת מחזאי 2-ביט פשוט. מעבדים מודרניים משתמשים בשיטות מתקדמות:

חזאי היסטוריה גלובלית - global history predictor

במקום להסתכל רק על ההיסטוריה של הסתעפות אחת, החזאי מסתכל על ההיסטוריה של כל ההסתעפויות האחרונות. למה? כי לפעמים הסתעפות אחת תלויה בתוצאה של הסתעפות קודמת.

לדוגמה:

if (x > 0) {
    if (x < 100) {
        // אם הגענו לכאן, x בטווח 1-99
    }
}

אם ההסתעפות הראשונה נלקחה (x > 0), יש סיכוי גבוה שגם השנייה תילקח. חזאי גלובלי לומד קורלציות כאלה.

TAGE - Tagged Geometric History Length

זהו החזאי המתקדם ביותר שבשימוש נפוץ (משמש במעבדי Intel ו-AMD). הוא משתמש בכמה טבלאות, כל אחת עם אורך היסטוריה שונה - 4, 8, 16, 32, 64, 128... הסתעפויות אחרונות. כשצריך לחזות, החזאי משתמש בטבלה עם ההיסטוריה הארוכה ביותר שיש לה match.

חזאים עצביים - neural predictors

שיטות שמבוססות על perceptrons (רשתות נוירונים פשוטות) לחיזוי הסתעפויות. Samsung השתמשו בגישה כזו במעבדי Exynos.

הדיוק בפועל

מעבדים מודרניים של Intel ו-AMD מגיעים ל-97% ומעלה דיוק חיזוי על קוד אמיתי. זה אומר שמתוך 100 הסתעפויות, רק 3 גורמות ל-pipeline flush. בלי חיזוי הסתעפויות, הביצועים היו צונחים פי 3-5.

---

למה זה חשוב למתכנתים

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

מערך ממוין מול מערך לא ממוין

זו אחת הדוגמאות המפורסמות ביותר במדעי המחשב (השאלה המפורסמת ב-StackOverflow עם יותר מ-30,000 upvotes):

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

#define N 100000

int main() {
    int arr[N];
    srand(42);
    for (int i = 0; i < N; i++)
        arr[i] = rand() % 256;

    // --- ניסוי 1: מערך לא ממוין ---
    long long sum = 0;
    clock_t start = clock();
    for (int repeat = 0; repeat < 1000; repeat++) {
        for (int i = 0; i < N; i++) {
            if (arr[i] > 128)   // הסתעפות לא צפויה!
                sum += arr[i];
        }
    }
    clock_t end = clock();
    printf("unsorted: %f sec\n",
           (double)(end - start) / CLOCKS_PER_SEC);

    // --- מיון המערך ---
    // (נניח שמיינו כאן)

    // --- ניסוי 2: מערך ממוין ---
    sum = 0;
    start = clock();
    for (int repeat = 0; repeat < 1000; repeat++) {
        for (int i = 0; i < N; i++) {
            if (arr[i] > 128)   // הסתעפות צפויה!
                sum += arr[i];
        }
    }
    end = clock();
    printf("sorted: %f sec\n",
           (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

במערך ממוין, כל הערכים הקטנים מ-128 באים ראשונים (ההסתעפות תמיד "לא נלקחת"), ואז כל הערכים הגדולים מ-128 (ההסתעפות תמיד "נלקחת"). החזאי לומד את הדפוס ומנחש נכון כמעט תמיד.

במערך לא ממוין, הערכים מעורבבים אקראית - ההסתעפות לפעמים נלקחת ולפעמים לא, ללא דפוס. החזאי לא יכול ללמוד שום דבר, ומפספס בערך 50% מהזמן.

התוצאה: המערך הממוין מעובד מהר פי 2-6 מהלא ממוין, למרות שהקוד זהה! ההבדל היחיד הוא סדר הנתונים.

רמזים לקומפיילר - likely ו-unlikely

בקרנל לינוקס (שלמדנו בפרק 6) משתמשים הרבה במאקרואים likely() ו-unlikely():

// מתוך הקרנל של לינוקס:
if (unlikely(error)) {
    handle_error();
}

המאקרואים האלה אומרים לקומפיילר: "הcondition הזה כמעט אף פעם לא מתקיים" (unlikely) או "הcondition הזה כמעט תמיד מתקיים" (likely). הקומפיילר משתמש במידע הזה כדי לסדר את הקוד כך שהמקרה הנפוץ יהיה בזרימה הישירה (בלי קפיצה), מה שעוזר לחזאי.

ב-GCC ו-Clang אפשר להשתמש ב-__builtin_expect:

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

אופטימיזציה מונחית פרופיל - Profile-Guided Optimization (PGO)

שיטה עוד יותר טובה: מריצים את התוכנית עם נתונים אמיתיים, אוספים סטטיסטיקה על כל הסתעפות (כמה אחוז מהפעמים נלקחה), ואז מקמפלים שוב עם המידע הזה. הקומפיילר יודע בדיוק איזה branches נפוצים ומסדר את הקוד בהתאם.

# שלב 1: קומפילציה עם instrumentation
gcc -fprofile-generate -o program program.c

# שלב 2: הרצה עם נתונים אמיתיים (נוצרים קבצי .gcda)
./program < real_input.txt

# שלב 3: קומפילציה מחדש עם הנתונים שנאספו
gcc -fprofile-use -o program_optimized program.c

תכנות ללא הסתעפויות - branchless programming

הדרך הקיצונית ביותר להימנע מ-branch mispredictions: לא להשתמש בהסתעפויות בכלל.

דוגמה - חישוב מקסימום:

// גרסה עם branch:
int max_branch(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

// גרסה בלי branch (באסמבלי - עם cmov):
// cmp eax, ebx
// cmovl eax, ebx   ; אם eax < ebx, העתק ebx ל-eax

הוראת cmov (conditional move) שלמדנו באסמבלי מבצעת העתקה מותנית בלי הסתעפות - המעבד תמיד מבצע אותה, רק בוחר אם לשמור את התוצאה. אין branch, אין misprediction.

דוגמה נוספת - סיכום מותנה בלי branch:

// עם branch:
if (arr[i] > 128)
    sum += arr[i];

// בלי branch (טריק אריתמטי):
int mask = -(arr[i] > 128);  // מייצר 0xFFFFFFFF או 0x00000000
sum += arr[i] & mask;

---

ביצוע ספקולטיבי ופגיעות Spectre

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

אם הניחוש נכון - התוצאות מאושרות (committed). אם שגוי - התוצאות נזרקות (rolled back). מבחינה לוגית, זה כאילו ההוראות מעולם לא רצו.

אבל - ב-2018 חוקרי אבטחה גילו משהו מדאיג: למרות שהתוצאות ה"לוגיות" נזרקות, ביצוע ספקולטיבי משאיר עקבות במטמון. אם הוראה ספקולטיבית טענה נתון מזכרון לcache, הנתון נשאר שם גם אחרי ה-rollback.

זו הבסיס לפגיעות Spectre: תוקף יכול לגרום למעבד לבצע ספקולטיבית קוד שניגש לזכרון שלא צריך - למשל, זכרון של תהליך אחר או של הקרנל (שלמדנו עליו בפרק 6). למרות שהתוצאה הלוגית נזרקת, התוקף יכול למדוד עיתויי גישה למטמון (cache timing) כדי לגלות מה הנתון היה.

נרחיב על Spectre ועל מיטיגציות (כמו retpoline ו-KPTI) בפרק 8.4 כשנדבר על ביצוע שלא בסדר.

---

סיכום

מושג	הסבר
חיזוי הסתעפויות - branch prediction	ניחוש לאן הסתעפות תלך
מחיר טעות - misprediction penalty	מחזורים מבוזבזים בשטיפת צינור
חזאי 1-ביט	זוכר את הפעם האחרונה
חזאי 2-ביט (saturating counter)	דורש שתי טעויות לשינוי כיוון
טבלת היסטוריה - BHT	טבלה שמחזיקה מצב חזאי לכל הסתעפות
חוצץ מטרות - BTB	מטמון של כתובות יעד
חזאי TAGE	חזאי מודרני עם טבלאות היסטוריה בגדלים שונים
ביצוע ספקולטיבי - speculative execution	ביצוע הוראות לפני שידוע אם הניחוש נכון
תכנות ללא הסתעפויות - branchless programming	שימוש ב-cmov וטריקים אריתמטיים

בפרק הבא (8.3) נלמד על זכרון מטמון - הרכיב שהופך את כל ההבדל בין זכרון מהיר לאיטי.