במחשבים, בטלפונים ובמכשירים נוספים קיימים מעבדים. המעבדים הללו קוראים פקודות מהזיכרון ומבצעים אותן בדרך כלל לפי הסדר, אולם לעתים מבצעים פקודה מיוחדת הנקראת "קפיצה מותנית" - Conditional Branch, היכולה בתנאים מסוימים לגרום להם לעבור ולבצע פקודות ממקום שונה בזיכרון. למשל, לפני ביצוע פעולת חילוק, המחשב יבדוק אם המחלק הוא אפס, ואם כן יקפוץ לבצע פקודות שיפיקו הודעת שגיאה. כדי לשפר את ביצועיו צריך המעבד לנחש מוקדם ככל האפשר אם הקפיצה עומדת להתבצע, ולשם כך מתכננים בוני המחשבים מנגנוני חומרה מתוחכמים [1].

הפוסט נכתב בשיתוף רוני רונן, ידיד העמותה.

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

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

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

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

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

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

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

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

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

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

 יש עוד שלל שיטות חיזוי הממומשות בחומרה. בכל דור של מעבדים מנסים לעשות שיפורים נוספים, ויכולת החיזוי שהייתה בערך 80% לפני 25 שנים עלתה ל-95% ואף יותר בימינו. אולם אין זה מספיק, כיוון שהמעבדים נהיו מאוד מהירים. למשל, נניח שהמטיילים עברו לטיול  אופנועים, ומהירותם  גדלה פי חמישה, אבל זמן הגילוי וההתמודדות עם טעויות בניווט נשאר כדקה. במצב זה נקבל שחיזוי מושלם מקצר בחצי את זמן הביצוע יחסית למצב ללא חיזוי!  

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

הערה:

[1] חיזוי קפיצות