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

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

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

נתון חזאי 2-ביט (saturating counter) שמתחיל במצב "חזק לא-נלקח" (00).

הנה רצף ההסתעפויות (T = נלקח, N = לא נלקח):

T, T, T, T, T, T, N, T, T, T, N, N, N, T, T, T

מלאו טבלה עבור כל הסתעפות ברצף:

צעד	תוצאה בפועל	מצב חזאי (לפני)	ניחוש	נכון/טעות	מצב חזאי (אחרי)
1	T	00	N	טעות	?
2	T	?	?	?	?
...

כמה טעויות היו בסה"כ? מה אחוז הדיוק?
אם היינו משתמשים בחזאי 1-ביט (שמתחיל במצב "לא נלקח"), כמה טעויות היו? השוו.

תרגיל 2 - ניתוח ביצועים: ממוין מול לא ממוין¶

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

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

#define N 100000

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

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

    // --- מערך לא ממוין ---
    long long sum1 = 0;
    clock_t start = clock();
    for (int rep = 0; rep < 500; rep++) {
        for (int i = 0; i < N; i++) {
            if (arr[i] >= 128)
                sum1 += arr[i];
        }
    }
    clock_t t_unsorted = clock() - start;

    // --- מיון ---
    qsort(arr, N, sizeof(int), compare);

    // --- מערך ממוין ---
    long long sum2 = 0;
    start = clock();
    for (int rep = 0; rep < 500; rep++) {
        for (int i = 0; i < N; i++) {
            if (arr[i] >= 128)
                sum2 += arr[i];
        }
    }
    clock_t t_sorted = clock() - start;

    printf("unsorted: %.3f sec\n",
           (double)t_unsorted / CLOCKS_PER_SEC);
    printf("sorted:   %.3f sec\n",
           (double)t_sorted / CLOCKS_PER_SEC);
    printf("ratio:    %.2fx\n",
           (double)t_unsorted / t_sorted);

    return 0;
}

קמפלו והריצו את הקוד עם gcc -O2 -o branch_test branch_test.c. מה היחס בין הזמנים?
הסבירו: למה המערך הממוין מהיר יותר? מה קורה בחזאי ההסתעפויות בכל מקרה?
שנו את התנאי מ->= 128 ל->= 1. עכשיו כמעט כל האיברים עוברים את התנאי. הריצו שוב - מה קרה ליחס בין הזמנים? למה?
שנו את התנאי ל->= 255. עכשיו כמעט אף איבר לא עובר. מה קרה? למה?

תרגיל 3 - תכנון מכונת מצבים לחזאי 2-ביט¶

ציירו את מכונת המצבים המלאה של חזאי 2-ביט (saturating counter) עם 4 מצבים: SN (00), WN (01), WT (10), ST (11). לכל מצב, ציינו:
מה הניחוש (T או N)
לאן עוברים אם התוצאה T
לאן עוברים אם התוצאה N
נניח שיש לולאה שרצה בדיוק 3 פעמים ואז יוצאת. הדפוס: T, T, T, N, T, T, T, N, T, T, T, N, ...
חשבו את הדיוק של חזאי 2-ביט שמתחיל ב-ST (11). כמה טעויות ב-12 הניחושים?
חשבו את הדיוק של חזאי 1-ביט. כמה טעויות ב-12?
תכננו חזאי 3-ביט (8 מצבים). הגדירו את מכונת המצבים: מה הניחוש בכל מצב, ולאן עוברים. החזאי צריך לדרוש 3 טעויות רצופות כדי לשנות כיוון.
האם חזאי 3-ביט טוב יותר מ-2-ביט עבור הדפוס T,T,T,N? חשבו.
האם תמיד יותר ביטים = יותר טוב? חשבו על מקרה שבו 2-ביט עדיף על 3-ביט.

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

נתון הקוד הבא שמחשב את סכום כל האיברים החיוביים במערך:

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

כתבו גרסה ללא הסתעפויות (branchless) של הפונקציה, באמצעות הטריק של mask:

int mask = -(arr[i] > 0);  // 0xFFFFFFFF אם חיובי, 0x00000000 אם לא
sum += arr[i] & mask;

כתבו תוכנית שמשווה את זמני הריצה של שתי הגרסאות על:
מערך שכל איבריו חיוביים
מערך שחצי חיוביים וחצי שליליים, מעורבבים אקראית
מערך שחצי חיוביים וחצי שליליים, ממוינים
באיזה מקרה הגרסה ללא הסתעפויות מנצחת? באיזה מקרה הגרסה עם ההסתעפות מנצחת (או שוות)? הסבירו למה.
(בונוס) אם הקומפיילר שלכם תומך, קמפלו עם -O2 ובדקו את האסמבלי שנוצר (gcc -O2 -S). האם הקומפיילר כבר הפך את ה-if ל-cmov בעצמו?