الدرس 21: تحسين الاختزال: sequential addressing
في الدرس السابق بنينا اختزالاً شجرياً في الذاكرة المشتركة: في كل خطوة يقوم نصف الـ threads بجمع زوج من القيم، فيتقلّص المجموع حتى قيمة واحدة. لكن الطريقة التي نختار بها أيّ الـ threads نشطة وأيّ المؤشرات تصل إليها تُغيّر الأداء تغييراً جذرياً. في النسخة الساذجة ذات العنونة المتداخلة (interleaved) تن
تخيّل 8 أطفال في صف عليهم أن يجمعوا أرقاماً. في الطريقة السيّئة تطلب من الطفل 0 و 2 و 4 و 6 أن يعملوا — واحد يعمل وواحد يستريح، فوضوي. في الطريقة الجيّدة تطلب من الأطفال الأربعة الأوائل فقط، كل منهم يضيف رقم الطفل المقابل له في النصف الثاني من الصف. المجموع نفسه، لكن مجموعة منظّمة واحدة تعمل بينما الأخرى تستريح — بلا فوضى.
- العنونة المتداخلة (interleaved addressing)
- أسلوب اختزال تنمو فيه الخطوة (s *= 2) ويكون الـ thread النشط هو 2*s*tid، فتكون الـ threads النشطة مبعثرة — ما يسبّب تشعّب warp وتعارضات banks.
- العنونة المتسلسلة (sequential addressing)
- أسلوب اختزال بحلقة معكوسة (s >>= 1) حيث كل thread يحقّق tid < s ينفّذ tile[tid] += tile[tid+s]، فتكون الـ threads النشطة متجاورة — بلا تشعّب، بلا تعارضات.
- تعارض banks (bank conflict)
- عندما تصل threads في نفس الـ warp إلى نفس bank في الذاكرة المشتركة، تُنفَّذ عمليات الوصول بالتسلسل بدلاً من التوازي — ما يضرّ بالأداء.
- threads نشطة
- الـ threads التي تؤدّي العمل في خطوة اختزال معيّنة. في العنونة المتسلسلة تكون تتابعاً متجاوراً 0..s-1؛ وفي المتداخلة تكون مبعثرة.
