מה זה Coalescing ו-Bank Conflicts - איך threads שכנים משפיעים אחד על השני

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

Coalescing - כשגישות מתמזגות לעסקה אחת

כשdiברנו על זיכרון גלובלי, הזכרנו שהגישה אליו איטית יחסית. אבל יש דרך לצמצם משמעותית את העלות הזו - כאשר כל ה-threads בתוך אותו warp ניגשים לכתובות זיכרון סמוכות ורציפות, החומרה יכולה לאחד את כל 32 הבקשות לעסקת זיכרון אחת גדולה, במקום לבצע 32 עסקאות נפרדות. זה נקרא memory coalescing, ומחסך פי כמה מזמן הגישה לזיכרון.

הדוגמה הפשוטה ביותר - thread מספר 0 ניגש לאיבר מספר 0 במערך, thread מספר 1 לאיבר מספר 1, וכן הלאה. זה הדפוס האידיאלי - כל הכתובות רציפות ומסודרות בדיוק לפי סדר ה-threads. החומרה מזהה את זה ומבצעת עסקה אחת יעילה שמכסה את כל ה-warp.

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

דוגמה קלאסית - מטריצה בשורות מול עמודות

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

Bank Conflicts - הבעיה המקבילה בziכרון המשותף

shared memory, שדיברנו עליו בהרחבה בפוסט על tiling, סובל מבעיה דומה במהות אך שונה בפרטים, שנקראת bank conflict. זיכרון משותף מחולק פיזית למספר קבוע של "בנקים", ובניית חומרה מאפשרת גישה מקבילה לבנקים שונים בו זמנית. הבעיה מתעוררת כאשר כמה threads באותו warp מנסים לגשת בו זמנית לכתובות שונות שנמצאות באותו בנק בדיוק. במקרה כזה, החומרה לא יכולה לשרת את כל הבקשות במקביל, והיא נאלצת לבצע אותן ברצף, אחת אחרי השנייה, מה שמבטל את היתרון המרכזי של shared memory.

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

איך נמנעים משתי הבעיות

הפתרון הכללי לשתיהן דומה במהות - לתכנן את דפוס הגישה כך שיתאים למבנה החומרה. עבור coalescing, זה אומר לוודא שthreads שכנים ניגשים לכתובות רציפות בזיכרון הגלובלי. עבור bank conflicts, לפעמים מספיק שינוי קטן, כמו הוספת "ריפוד" מלאכותי למבנה הנתונים בshared memory, כדי לפרק תבנית גישה שהייתה גורמת להתנגשות.

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

לסיכום

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

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

הצטרפו לקהילה בדיסקורד