שיעור 21: אופטימיזציית רדוקציה: sequential addressing

בשיעור הקודם בנינו רדוקציית עץ בזיכרון משותף: בכל צעד מחצית מה-threads מחברות זוג ערכים, וכך הסכום מצטמצם עד לערך אחד. אבל הדרך שבה בוחרים אילו threads פעילים ואיזה אינדקסים הם ניגשים אליהם משנה דרמטית את הביצועים. בגרסה התמימה, המרווחת (interleaved addressing), הצעד s גדל (s *= 2) וה-thread הפעיל מ

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

מיעון מרווח (interleaved addressing): שיטת רדוקציה שבה הצעד גדל (s *= 2) וה-thread הפעיל הוא 2*s*tid, כך שהפעילים מפוזרים — גורם להתפצלות warp ולהתנגשויות banks.
מיעון רציף (sequential addressing): שיטת רדוקציה עם לולאה הפוכה (s >>= 1) שבה כל thread עם tid < s מחבר tile[tid] += tile[tid+s], כך שהפעילים הם רצף — בלי התפצלות ובלי התנגשויות.
התנגשות banks (bank conflict): כש-threads באותו warp ניגשים לאותו bank בזיכרון המשותף, הגישות מתבצעות ברצף במקום במקביל — ביצועים נפגעים.
threads פעילים: ה-threads שמבצעים עבודה בצעד נתון של הרדוקציה. במיעון רציף הם רצף 0..s-1; במרווח הם מפוזרים.