الدرس 20: الاختزال المتوازي: الجمع القائم على الشجرة

الاختزال يقلّص مصفوفة كاملة إلى قيمة واحدة — مثلاً مجموع كل العناصر. على الـ CPU تقوم بذلك في حلقة تسلسلية: مُراكِم واحد يمرّ على العناصر الـ n في n خطوة. لكن هذا يهدر الـ GPU: thread واحد يعمل بينما آلاف غيره خاملة. الحل المتوازي هو الاختزال الشجري (tree reduction). تُحمِّل البيانات إلى shared memo

تخيّل 8 أشخاص عليهم جمع 8 أرقام. بدلاً من أن يجمعها شخص واحد وحده، يجمع كل زوج في الوقت نفسه: 8 يصبحون 4، ثم 2، ثم نتيجة واحدة. ثلاث جولات بدل سبع — تلك هي قوة الشجرة.

الاختزال (reduction): تقليص مصفوفة إلى قيمة واحدة عبر عملية تجميعية (مجموع، أقصى قيمة، إلخ). على الـ GPU يتم ذلك على شكل شجرة.
الاختزال الشجري (tree reduction): في كل خطوة يجمع نصف الـ threads أزواجاً؛ العمق هو log2(n) خطوة بدلاً من n.
stride: المسافة بين العنصرين اللذين يُجمعان في خطوة معيّنة. يبدأ كبيراً ويتناصف في كل خطوة حتى يصل إلى 1.
التزامن بين الخطوات: __syncthreads() بعد كل خطوة يضمن أن جميع عمليات الكتابة انتهت قبل أن تقرأها الخطوة التالية — بدونه تحدث حالة تسابق (race condition).