שיעור 20: רדוקציה מקבילה: סכום במבנה עץ

רדוקציה היא צמצום של מערך שלם לערך אחד — למשל סכום כל האיברים. ב-CPU עושים זאת בלולאה סדרתית: מצבר אחד שעובר על n האיברים ב-n צעדים. אבל זה מבזבז את ה-GPU: thread אחד עובד, אלפי האחרים בטלים. הפתרון המקבילי הוא רדוקציה במבנה עץ (tree reduction). טוענים את הנתונים ל-shared memory, ואז בכל צעד מחצית מ

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

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