שיעור 20: רדוקציה מקבילה: סכום במבנה עץ
רדוקציה היא צמצום של מערך שלם לערך אחד — למשל סכום כל האיברים. ב-CPU עושים זאת בלולאה סדרתית: מצבר אחד שעובר על n האיברים ב-n צעדים. אבל זה מבזבז את ה-GPU: thread אחד עובד, אלפי האחרים בטלים. הפתרון המקבילי הוא רדוקציה במבנה עץ (tree reduction). טוענים את הנתונים ל-shared memory, ואז בכל צעד מחצית מ
דמיין/י 8 אנשים שצריכים לחבר 8 מספרים. במקום שאחד יחבר את כולם לבד, כל זוג מחבר בו-זמנית: 8 הופכים ל-4, אחר כך ל-2, ובסוף לתוצאה אחת. שלושה סבבים במקום שבעה — זה הכוח של העץ.
- רדוקציה (reduction)
- צמצום מערך לערך יחיד בעזרת פעולה אסוציאטיבית (סכום, מקסימום וכו'). ב-GPU נעשה במבנה עץ.
- רדוקציית עץ (tree reduction)
- בכל צעד מחצית מה-threads מחברות זוגות; העומק הוא log2(n) צעדים במקום n.
- stride
- המרחק בין שני האיברים שמחברים בצעד מסוים. מתחיל גדול ומתחלק בשתיים בכל צעד עד 1.
- סנכרון בין צעדים
- __syncthreads() אחרי כל צעד מבטיח שכל הכתיבות הסתיימו לפני שהצעד הבא קורא אותן — בלעדיו יש תנאי מרוץ.