לדלג לתוכן

8.2 חיזוי הסתעפויות פתרון

פתרון תרגול - חיזוי הסתעפויות

1. חיזוי התנהגות של חזאי 2-ביט

מזכירים את המצבים ואת המעברים:
- 00 (SN): ניחוש N. אם T -> עבור ל-01. אם N -> נשאר 00.
- 01 (WN): ניחוש N. אם T -> עבור ל-10. אם N -> עבור ל-00.
- 10 (WT): ניחוש T. אם T -> עבור ל-11. אם N -> עבור ל-01.
- 11 (ST): ניחוש T. אם T -> נשאר 11. אם N -> עבור ל-10.

הטבלה:

צעד תוצאה מצב לפני ניחוש נכון/טעות מצב אחרי
1 T 00 (SN) N טעות 01 (WN)
2 T 01 (WN) N טעות 10 (WT)
3 T 10 (WT) T נכון 11 (ST)
4 T 11 (ST) T נכון 11 (ST)
5 T 11 (ST) T נכון 11 (ST)
6 T 11 (ST) T נכון 11 (ST)
7 N 11 (ST) T טעות 10 (WT)
8 T 10 (WT) T נכון 11 (ST)
9 T 11 (ST) T נכון 11 (ST)
10 T 11 (ST) T נכון 11 (ST)
11 N 11 (ST) T טעות 10 (WT)
12 N 10 (WT) T טעות 01 (WN)
13 N 01 (WN) N נכון 00 (SN)
14 T 00 (SN) N טעות 01 (WN)
15 T 01 (WN) N טעות 10 (WT)
16 T 10 (WT) T נכון 11 (ST)

סה"כ: 7 טעויות מתוך 16 = 56.25% דיוק (43.75% טעויות).

הדיוק הנמוך נובע מכך שהרצף מתחיל עם שתי טעויות "קרות" (cold start), ויש שינויי כיוון תכופים.

חזאי 1-ביט:

צעד תוצאה מצב ניחוש נכון/טעות מצב אחרי
1 T N N טעות T
2 T T T נכון T
3 T T T נכון T
4 T T T נכון T
5 T T T נכון T
6 T T T נכון T
7 N T T טעות N
8 T N N טעות T
9 T T T נכון T
10 T T T נכון T
11 N T T טעות N
12 N N N נכון N
13 N N N נכון N
14 T N N טעות T
15 T T T נכון T
16 T T T נכון T

חזאי 1-ביט: 5 טעויות מתוך 16 = 68.75% דיוק. במקרה הזה, חזאי 1-ביט דווקא טוב יותר! זה בגלל שהרצף מכיל שינויי כיוון בודדים - חזאי 2-ביט "מגיב לאט" אבל כאן המהירות דווקא עוזרת.

עם זאת, עבור לולאות ארוכות ויציבות, חזאי 2-ביט כמעט תמיד עדיף.

2. ניתוח ביצועים: ממוין מול לא ממוין

סעיף 1: תוצאות טיפוסיות:

unsorted: 1.200 sec
sorted:   0.350 sec
ratio:    3.43x

היחס המדויק תלוי במעבד ובקומפיילר, אבל בדרך כלל בין 2x ל-6x.

סעיף 2: הסבר:
- מערך ממוין: ההסתעפות if (arr[i] >= 128) יוצרת דפוס צפוי. ברצף התחתון של המערך (ערכים 0-127), ההסתעפות תמיד לא נלקחת. ברצף העליון (128-255), תמיד נלקחת. החזאי לומד את הדפוס ומנחש נכון כמעט תמיד. הטעות היחידה היא בנקודת המעבר (פעם אחת מתוך 100,000 איטרציות).
- מערך לא ממוין: הערכים מעורבבים אקראית. ההסתעפות נלקחת בערך 50% מהפעמים בצורה אקראית. שום חזאי לא יכול לחזות רצף אקראי - הטעות היא כ-50%.

סעיף 3: עם >= 1:
כמעט כל האיברים (255 מתוך 256) עוברים את התנאי. ההסתעפות כמעט תמיד נלקחת - גם במערך הלא ממוין. החזאי מנחש "נלקח" ולמעד רק לעתים נדירות. היחס בין הזמנים קרוב ל-1 (כמעט אין הבדל).

סעיף 4: עם >= 255:
כמעט אף איבר לא עובר את התנאי (רק 1 מתוך 256). ההסתעפות כמעט אף פעם לא נלקחת. שוב, החזאי מנחש נכון כמעט תמיד. היחס קרוב ל-1.

המסקנה: הבעיה לחזאי היא לא branches שנלקחים תמיד או אף פעם - אלה קלים לחזות. הבעיה היא branches שמתנהגים אקראית (כמו 50/50 ללא דפוס). אלה גורמים ל-50% mispredictions.

3. תכנון מכונת מצבים

סעיף 1 - מכונת מצבים של חזאי 2-ביט:

          T              T              T
  SN(00) ----> WN(01) ----> WT(10) ----> ST(11)
  <----        <----        <----        |
    N            N            N          | T (נשאר)
                                         |
  ניחוש: N     ניחוש: N     ניחוש: T     ניחוש: T
מצב ניחוש אם T אם N
SN (00) N WN (01) SN (00)
WN (01) N WT (10) SN (00)
WT (10) T ST (11) WN (01)
ST (11) T ST (11) WT (10)

סעיף 2 - דפוס T,T,T,N חוזר:

חזאי 2-ביט מתחיל ב-ST (11):

צעד תוצאה מצב ניחוש נכון? מצב אחרי
1 T ST T V ST
2 T ST T V ST
3 T ST T V ST
4 N ST T X WT
5 T WT T V ST
6 T ST T V ST
7 T ST T V ST
8 N ST T X WT
9 T WT T V ST
10 T ST T V ST
11 T ST T V ST
12 N ST T X WT

2-ביט: 3 טעויות מתוך 12 = 75% דיוק (טעות אחת בכל 4 - כשהלולאה יוצאת).

חזאי 1-ביט:

צעד תוצאה מצב ניחוש נכון? מצב אחרי
1 T T T V T
2 T T T V T
3 T T T V T
4 N T T X N
5 T N N X T
6 T T T V T
7 T T T V T
8 N T T X N
9 T N N X T
10 T T T V T
11 T T T V T
12 N T T X N

1-ביט: 6 טעויות מתוך 12 = 50% דיוק. חזאי 2-ביט עדיף פי 2 בדפוס הזה!

סעיף 3 - חזאי 3-ביט:

8 מצבים (000 עד 111):

מצב ניחוש אם T אם N
000 (S3N) N 001 000
001 (S2N) N 010 000
010 (S1N) N 011 000
011 (W_T) T 100 010
100 (S1T) T 101 011
101 (S2T) T 110 100
110 (S3T) T 111 101
111 (S4T) T 111 110

עבור דפוס T,T,T,N - חזאי 3-ביט יתנהג בדיוק כמו 2-ביט (טעות אחת בכל 4) כי שתי טעויות רצופות כבר מספיקות לחזור ל"נלקח" אחרי ה-N הבודד. 3-ביט לא עדיף על 2-ביט עבור הדפוס הזה.

מקרה שבו 2-ביט עדיף על 3-ביט: דפוס עם שינויי כיוון תכופים, כמו T,T,N,N,T,T,N,N. חזאי 3-ביט "מגיב לאט" ויפספס יותר בהתחלה של כל קבוצה. כלל אצבע: ככל שיש יותר ביטים, החזאי יציב יותר אבל איטי יותר להסתגל.

4. גרסה ללא הסתעפויות

סעיף 1 - קוד branchless:

int sum_positive_branchless(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int mask = -(arr[i] > 0);
        // arr[i] > 0 מחזיר 1, הנגטיב שלו הוא 0xFFFFFFFF
        // arr[i] <= 0 מחזיר 0, הנגטיב שלו הוא 0x00000000
        sum += arr[i] & mask;
    }
    return sum;
}

סעיף 2 - תוכנית השוואה:

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

#define N 1000000
#define REPS 200

int sum_branch(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0)
            sum += arr[i];
    }
    return sum;
}

int sum_branchless(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int mask = -(arr[i] > 0);
        sum += arr[i] & mask;
    }
    return sum;
}

int main() {
    int *arr = malloc(N * sizeof(int));
    srand(42);

    // --- מקרה 1: הכל חיובי ---
    for (int i = 0; i < N; i++) arr[i] = rand() % 100 + 1;

    clock_t start = clock();
    volatile int s = 0;
    for (int r = 0; r < REPS; r++) s = sum_branch(arr, N);
    double t1_branch = (double)(clock() - start) / CLOCKS_PER_SEC;

    start = clock();
    for (int r = 0; r < REPS; r++) s = sum_branchless(arr, N);
    double t1_nobranch = (double)(clock() - start) / CLOCKS_PER_SEC;

    printf("all positive:   branch=%.3f  branchless=%.3f\n",
           t1_branch, t1_nobranch);

    // --- מקרה 2: חצי/חצי מעורבב ---
    for (int i = 0; i < N; i++)
        arr[i] = (rand() % 200) - 100;  // -100 עד 99

    start = clock();
    for (int r = 0; r < REPS; r++) s = sum_branch(arr, N);
    double t2_branch = (double)(clock() - start) / CLOCKS_PER_SEC;

    start = clock();
    for (int r = 0; r < REPS; r++) s = sum_branchless(arr, N);
    double t2_nobranch = (double)(clock() - start) / CLOCKS_PER_SEC;

    printf("mixed random:   branch=%.3f  branchless=%.3f\n",
           t2_branch, t2_nobranch);

    // --- מקרה 3: חצי/חצי ממוין ---
    // (כבר מעורבב מהמקרה הקודם, צריך למיין)
    int compare(const void *a, const void *b) {
        return *(int *)a - *(int *)b;
    }
    qsort(arr, N, sizeof(int), compare);

    start = clock();
    for (int r = 0; r < REPS; r++) s = sum_branch(arr, N);
    double t3_branch = (double)(clock() - start) / CLOCKS_PER_SEC;

    start = clock();
    for (int r = 0; r < REPS; r++) s = sum_branchless(arr, N);
    double t3_nobranch = (double)(clock() - start) / CLOCKS_PER_SEC;

    printf("mixed sorted:   branch=%.3f  branchless=%.3f\n",
           t3_branch, t3_nobranch);

    free(arr);
    return 0;
}

סעיף 3 - ניתוח תוצאות צפויות:

מקרה branch branchless מנצח
הכל חיובי מהיר מהיר שווה (או branch קצת יותר מהיר)
חצי/חצי מעורבב איטי מהיר branchless
חצי/חצי ממוין מהיר מהיר שווה (או branch קצת יותר מהיר)

הסבר:
- הכל חיובי: ההסתעפות תמיד נלקחת - החזאי מנחש נכון 100%. אין mispredictions, אז הגרסה עם branch יעילה. הגרסה branchless עושה עבודה נוספת (mask, AND) שהגרסה branch לא צריכה.
- חצי/חצי מעורבב: ההסתעפות אקראית - 50% mispredictions. כל misprediction עולה 15+ מחזורים. הגרסה branchless לא מושפעת כי אין branch כלל.
- חצי/חצי ממוין: כל השליליים ראשונים, אחריהם כל החיוביים. החזאי לומד את הדפוס - כמעט 100% דיוק. שוב אין mispredictions, והגרסה branch חוזרת להיות יעילה.

מסקנה: תכנות branchless משתלם רק כשההסתעפות לא ניתנת לחיזוי. כשהחזאי מצליח, branch הוא הגישה הטובה יותר.

סעיף 4 - בונוס:
עם -O2, GCC לעתים קרובות כבר ממיר if פשוט ל-cmov בעצמו. בדקו באסמבלי שנוצר:

gcc -O2 -S -o branch_test.s branch_test.c

חפשו את המילה cmov בקובץ. אם הקומפיילר כבר עשה branchless, שתי הגרסאות ייתנו ביצועים זהים. במקרה כזה, קמפלו עם -O1 או -O0 כדי לראות את ההבדל.