فكرة شجرة الاختزال
خفّض عدد الخيوط النشطة إلى النصف في كل خطوة.
فكرة شجرة الاختزال درس مجاني في CUDA Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في CUDA Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة CUDA Academy 4 دروس في المجموع.
ما المقصود بالاختزال
يحوّل الاختزال مصفوفة كاملة إلى قيمة واحدة، مثل جمع كل العناصر في مجموع واحد. وهو أحد أكثر الأنماط شيوعًا في GPU. 🌳
الطريقة التسلسلية بطيئة
في CPU، تجمع العناصر واحدًا تلو الآخر. وهذا يعني O(n) من الخطوات التسلسلية، لذا يتطلب مليون رقم مليون عملية جمع متعاقبة ومترابطة.
الجمع تجميعي
الفكرة أن الجمع تجميعي: (a+b)+c يساوي a+(b+c). لذلك يمكنك جمع الأزواج بأي تجميع تريده.
جمع الأزواج بالتوازي
بما أن التجميع حر، يمكنك جمع العديد من الأزواج المستقلة في الوقت نفسه. ويتولى كل خيط زوجًا واحدًا، وكل ذلك في خطوة متوازية واحدة.
التنصيف في كل خطوة
بعد مرور واحد، يختفي نصف العناصر. كرر العملية، وسيستمر العدد النشط في التنصيف: من 8 إلى 4 ثم إلى 2 ثم إلى 1.
العمق اللوغاريتمي
يعني التنصيف أنك تنتهي خلال log2(n) من الخطوات بدلًا من n. فتختزل مليون خانة في نحو 20 خطوة، لا مليون خطوة.
تصوّر الشجرة
يُظهر رسم الأزواج شجرة ثنائية. وتمثل الأوراق المدخلات، ويُنصّف كل مستوى عدد العقد، بينما يمثل الجذر مجموعك النهائي.
يتضاعف الفاصل في كل مرور
إحدى طرق كتابة ذلك برمجيًا هي أن يضيف الخيط في كل خطوة جاره الذي يبعد مسافة stride، ويتضاعف هذا الفاصل في كل مرور على البيانات.
for (int s = 1; s < blockDim.x; s *= 2) {
if (tid % (2 * s) == 0)
data[tid] += data[tid + s];
__syncthreads();
}المزامنة بين الخطوات
يعتمد كل مستوى على انتهاء المستوى السابق، لذلك يجب أن تنتظر الخيوط عند حاجز قبل قراءة نتيجة شريكها.
العمل مقابل الامتداد
يبقى إجمالي عمليات الجمع قريبًا من n، وهذا هو العمل. لكن أطول سلسلة من الاعتماديات، أي الامتداد، تنخفض إلى log2(n). العمل نفسه، ولكن انتظار أقل بكثير.
ليس الجمع وحده
تعمل الشجرة نفسها مع أي عملية تجميعية: القيمة العظمى أو الصغرى أو الضرب أو AND المنطقي. غيّر العامل، ويبقى الهيكل كما هو.
اختبار سريع
فكّر في عدد الخطوات المتوازية التي يحتاج إليها اختزال الشجرة.
مراجعة
تعلمت شجرة الاختزال: جمع الأزواج بالتوازي، والتنصيف في كل خطوة، والانتهاء خلال log2(n). وهي تعمل مع أي عامل تجميعي. والآن، حافظ على انشغال warps! 🎉
تعلم C++ مع معلم ذكاء اصطناعي — مجانًا
اكتب وقم بتشغيل أكوادك الفعلية في المتصفح، واحصل على مساعدة فورية من معلم ذكاء اصطناعي متاح 24/7، واستمر من حيث توقفت على الويب أو في التطبيق.
- الدورات
- 30
- الدروس
- 120
الأسئلة الشائعة
هل درس «فكرة شجرة الاختزال» مجاني؟
نعم — نص درس «فكرة شجرة الاختزال» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة CUDA Academy، انتقل إلى CoddyKit PRO. تتضمن دورة CUDA Academy 4 دروس في المجموع.
ماذا ستتعلم في «فكرة شجرة الاختزال»؟
خفّض عدد الخيوط النشطة إلى النصف في كل خطوة. تتمرن على CUDA Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ CUDA Academy؟
لا تُشترط خبرة سابقة. CUDA Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «فكرة شجرة الاختزال»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس CUDA Academy هذا؟
نعم. كل درس في CUDA Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- فكرة شجرة الاختزال
- القضاء على تفرّع Warp
- العنونة التسلسلية
- الاختزال النهائي متعدد الكتل