איך מעבד מנחש קדימה - חיזוי ענפים וביצוע מחוץ לסדר¶
בפוסט על ארכיטקטורת מעבד הסברנו את מחזור הביצוע הבסיסי - תשלוף, פענוח, ביצוע, כתיבה חוזרת, ואיך צנרת עיבוד (pipelining) מריצה כמה פקודות במקביל, כל אחת בשלב שונה. אבל הרעיון הזה נתקל בבעיה קשה ברגע שהקוד מגיע לתנאי - הוראת if. מעבד מודרני פותר את זה בדרך מפתיעה - הוא פשוט מנחש.
הבעיה - למה תנאי שובר את הצנרת¶
צנרת עיבוד עובדת מצוין כשהמעבד יודע בדיוק אילו פקודות יגיעו הלאה, ומתחיל להביא ולפענח אותן מראש בזמן שהוא עדיין מבצע פקודות קודמות. אבל מה קורה כשהוא מגיע לקוד כמו if (x > 10)? הוא לא יודע עדיין אם התוצאה תהיה נכון או לא נכון, כי החישוב עצמו עוד לא הסתיים, וכל צד של התנאי מוביל לפקודות הבאות אחרות לגמרי בזיכרון. אם המעבד היה פשוט עוצר ומחכה לתוצאה בכל פעם, כל תנאי היה עוצר את הצנרת המהירה שלו, ומבטל את רוב היתרון שלה.
הפתרון - חיזוי ענפים¶
במקום לחכות, מעבדים מודרניים מנחשים. חיזוי ענפים (branch prediction) הוא מנגנון חומרה שמחזיק היסטוריה של תוצאות תנאים קודמים, ולומד מהם דפוסים. אם לולאה רצה אלף פעמים ובכל פעם התנאי שלה יצא נכון, המעבד מזהה את הדפוס ומנחש שגם הפעם הבאה תהיה נכון - ולכן הוא ממשיך להביא ולעבד מראש את הפקודות שמתאימות לתוצאה "נכון", עוד לפני שהוא בכלל יודע בוודאות אם זה נכון. זה נשמע כמו הימור, וזה בדיוק מה שזה - אבל הימור מחושב, שמצליח ברוב המכריע של המקרים, כי קוד אמיתי נוטה לחזור על אותם דפוסים שוב ושוב.
מה קורה כשהניחוש טועה¶
כשהחיזוי מוטעה, המעבד גילה שהוא בזבז זמן על ביצוע מוקדם של פקודות שלא היו אמורות לרוץ בכלל. הוא צריך לזרוק את כל התוצאות שכבר חישב בטעות, ולהתחיל מחדש מהנקודה הנכונה - זה נקרא pipeline flush, וזה עולה כמה מחזורי שעון יקרים, ממש כמו לכתוב עמוד שלם ואז לגלות שהתחלתם עם ההנחה הלא נכונה וצריך לקרוע ולהתחיל מחדש. זו הסיבה שקוד עם הרבה תנאים בלתי צפויים, כמו נתונים אקראיים לגמרי, יכול לרוץ לאט משמעותית מקוד עם אותה כמות פעולות בדיוק אבל דפוסים צפויים יותר.
ביצוע מחוץ לסדר - לא לחכות בטלנות¶
חיזוי ענפים פותר בעיה אחת, אבל יש בעיה קשורה - לפעמים פקודה אחת פשוט מחכה למשהו, כמו תוצאה מהזיכרון שעוד לא הגיעה, בזמן שפקודות אחריה בקוד כבר מוכנות לרוץ ולא תלויות בה בכלל. מעבדים מודרניים לא מבזבזים את הזמן הזה. במנגנון שנקרא ביצוע מחוץ לסדר (out-of-order execution), המעבד בוחן קבוצת פקודות קרובות, מזהה אילו מהן תלויות זו בזו ואילו לא, ומריץ פקודות מאוחרות יותר בקוד מוקדם, אם הן מוכנות ואין להן תלות בפקודה שעדיין ממתינה. בסוף, הוא מוודא שהתוצאות "נכתבות בחזרה" בסדר המקורי שהתוכנית ציפתה לו, כך שמבחינת התוכנית, הכל נראה כאילו רץ בדיוק בסדר שנכתב, גם אם בפועל הביצוע בפנים היה שונה לגמרי.
למה שני המנגנונים האלה ביחד הם קריטיים¶
חיזוי ענפים וביצוע מחוץ לסדר יחד הם ההבדל בין מעבד שמנצל כל מחזור שעון שלו, לבין מעבד שמבזבז זמן יקר בהמתנה. הם גם הסבר לתופעה שמפתיעה מתכנתים לפעמים - שני קטעי קוד שעל הנייר עושים בדיוק אותו מספר פעולות יכולים לרוץ במהירויות שונות משמעותית, תלוי כמה קל למעבד לחזות את ההתנהגות שלהם וכמה תלויות יש בין הפקודות שלהם.
זה בדיוק סוג הידע שממשיך את ההבנה מהשלבים הבסיסיים של תשלוף-פענוח-ביצוע, לרזולוציה שבה מתכנני מעבדים באמת חושבים, וזה בדיוק הכיוון שאנחנו מעמיקים בו בקורס ליבת המחשב שלנו.
קורס ליבת המחשב נמצא כאן, חינם ובעברית, עד לנושאים מתקדמים באמת בארכיטקטורת מעבדים.
יש לכם שאלה על ביצועי קוד שמפתיעים אתכם? שאלו בדיסקורד.
לסיכום¶
מעבד מודרני לא מחכה בסבלנות לכל תוצאה - הוא מנחש תוצאות תנאים מראש בעזרת חיזוי ענפים, ומריץ פקודות מוכנות מוקדם יותר ממה שהסדר המקורי מציע, בעזרת ביצוע מחוץ לסדר. שני המנגנונים האלה הם חלק גדול מהסיבה שמעבדים היום מהירים כל כך, וגם הסבר לזה שביצועי קוד תלויים בהרבה יותר ממספר הפקודות שהוא מכיל.