Shared Memory ו-Tiling מוסבר - הטכניקה שמאיצה כפל מטריצות פי כמה

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

הבעיה שtiling פותר

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

זו בדיוק הבעיה שגורמת לקוד GPU נאיבי להיות הרבה יותר איטי ממה שהחומרה מסוגלת לספק בפועל.

הרעיון של tiling

הפתרון הוא לחלק את המטריצות לריבועים קטנים, tiles, ולעבד את החישוב tile אחרי tile במקום שורה שלמה בבת אחת. כל block של threads אחראי על tile אחד בתוצאה, וכל ה-threads בתוך אותו block עובדים יחד כדי לטעון tile מתאים ממטריצה A ו-tile מתאים ממטריצה B אל תוך shared memory, פעם אחת בלבד.

ברגע שה-tile יושב ב-shared memory, שהוא מהיר בהרבה מהזיכרון הגלובלי, כל ה-threads בתוך ה-block יכולים לגשת אליו שוב ושוב בלי לחזור לזיכרון האיטי. כל thread מחשב את התרומה החלקית שלו מהזוג הזה של tiles, מצטבר עם תוצאות מ-tiles קודמים, וממשיך הלאה ל-tile הבא, עד שכל השורה והעמודה כוסו.

למה זה עובד כל כך טוב

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

הצורך ב-synchronization

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

מה קובע את גודל ה-tile

גודל ה-tile הוא עוד פרמטר שדורש איזון. tile גדול חוסך יותר גישות לזיכרון הגלובלי, אבל צורך יותר shared memory לכל block, מה שמגביל כמה blocks יכולים לרוץ במקביל על אותו SM, בדיוק כמו שראינו בפוסט על occupancy. tile קטן מדי לא מנצל את הפוטנציאל של הטכניקה. המספר הנכון תלוי בחומרה הספציפית ובגודל המטריצות, ובדרך כלל מוצאים אותו דרך ניסוי ובדיקה עם כלי פרופיילינג.

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

לסיכום

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

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

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