خوارزمية تتبع GPU جديدة: تتبع مسار واجهة الموجة

في هذه المقالة ، نستكشف المفهوم المهم المستخدم في منصة Lighthouse 2. التي تم إصدارها مؤخرًا ، حيث إن تتبع مسار واجهة الموجة ، كما يطلق عليه Lane و Karras و Aila من NVIDIA ، أو تتبع مسار التدفق ، كما كان يطلق عليه في الأصل في أطروحة الماجستير في Van Antwerp ، يلعب دورًا مهمًا في تطوير تتبع مسار فعال على وحدة معالجة الرسومات ، ومسارات تتبع محتملة على وحدة المعالجة المركزية. ومع ذلك ، من غير المنطقي تمامًا ، لذلك ، من الضروري إعادة التفكير في خوارزميات تتبع الأشعة.

الإشغال

خوارزمية تتبع المسار بسيطة بشكل مدهش ويمكن وصفها في بضعة أسطر من الكود الكاذب:

vec3 Trace( vec3 O, vec3 D ) IntersectionData i = Scene::Intersect( O, D ) if (i == NoHit) return vec3( 0 ) // ray left the scene if (i == Light) return i.material.color // lights do not reflect vec3 R, pdf = RandomDirectionOnHemisphere( i.normal ), 1 / 2PI return Trace( i.position, R ) * i.BRDF * dot( i.normal, R ) / pdf 

المدخلات هي الأشعة الأساسية التي تمر من الكاميرا عبر بكسل الشاشة. بالنسبة إلى هذه الحزمة ، نحدد أقرب تقاطع مع المشهد البدائي. إذا لم تكن هناك التقاطعات ، فإن الشعاع يختفي في الفراغ. خلاف ذلك ، إذا وصلت الحزمة إلى مصدر الضوء ، فقد وجدنا مسار الضوء بين المصدر والكاميرا. إذا وجدنا شيئًا آخر ، فنحن نؤدي التفكير والتكرار ، على أمل أن الشعاع المنعكس سيظل مصدر الإضاءة. لاحظ أن هذه العملية تشبه المسار (العائد) للفوتون الذي ينعكس على سطح المشهد.

تم تصميم وحدات معالجة الرسومات لتنفيذ هذه المهمة في وضع متعدد الخيوط. في البداية قد يبدو أن تتبع الشعاع مثالي لهذا الغرض. لذلك ، نحن نستخدم OpenCL أو CUDA لإنشاء دفق للبكسل ، حيث يقوم كل دفق خوارزمية تعمل فعليًا كما هو مخطط لها ، وهي سريعة جدًا: انظر فقط إلى بعض الأمثلة مع ShaderToy لفهم مدى سرعة تتبع الأشعة على GPU. ولكن ، ما كان الأمر كذلك ، فإن السؤال مختلف: هل أجهزة تتبع الأشعة هذه في أسرع وقت ممكن ؟


هذه الخوارزمية لديها مشكلة. يمكن أن يجد الشعاع الأساسي مصدر الضوء على الفور ، أو بعد انعكاس عشوائي واحد ، أو بعد 50 انعكاسًا. سوف يلاحظ المبرمج لوحدة المعالجة المركزية تجاوز سعة مكدس محتمل هنا؛ يجب أن يرى مبرمج GPU مشكلة الإشغال . سبب المشكلة هو تكرار الذيل الشرطي: قد ينتهي المسار عند مصدر الضوء أو يستمر. دعنا ننقل هذا إلى العديد من مؤشرات الترابط: ستتوقف بعض مؤشرات الترابط ، وسيستمر الجزء الآخر في العمل. بعد انعكاسات قليلة ، سيكون لدينا العديد من مؤشرات الترابط التي تحتاج إلى مواصلة الحوسبة ، وستنتظر معظم مؤشرات الترابط انتهاء مؤشرات الترابط الأخيرة هذه من العمل. العمالة هي مقياس لجزء مؤشرات ترابط GPU التي تؤدي عملاً مفيدًا.

تنطبق مشكلة التوظيف على نموذج التنفيذ لأجهزة SIMT GPU. يتم تنظيم التدفقات إلى مجموعات ، على سبيل المثال ، يتم دمج مؤشرات الترابط 32 Pascal GPU (NVidia equipment class 10xx) 32 في التفاف . مؤشرات الترابط في الاعوجاج تحتوي على عداد برنامج شائع: يتم تنفيذها بخطوة ثابتة ، بحيث يتم تنفيذ كل تعليمة برنامج من خلال 32 مؤشر ترابط في وقت واحد. يرمز SIMT إلى مؤشر ترابط واحد متعدد التعليمات ، والذي يصف المفهوم جيدًا. بالنسبة لمعالج SIMT ، تكون الشفرة ذات الشروط معقدة. يظهر هذا بوضوح في وثائق Volta الرسمية:


تنفيذ التعليمات البرمجية مع الشروط في SIMT.

عندما يكون هناك شرط معين صحيح لبعض مؤشرات الترابط في الاعوجاج ، يتم إجراء تسلسل لفروع عبارة if . بديل لنهج "كافة مؤشرات الترابط تفعل الشيء نفسه" هو "يتم تعطيل بعض مؤشرات الترابط." في كتلة if-then-else ، سيكون متوسط ​​احتلال الاعوجاج 50٪ ، ما لم يكن لجميع الخيوط الاتساق فيما يتعلق بالشرط.

لسوء الحظ ، رمز مع شروط في تتبع الأشعة ليست نادرة جدا. تنبعث أشعة الظلال فقط إذا كان مصدر الضوء لا يقع خلف نقطة التظليل ، فقد تتصادم مسارات مختلفة مع مواد مختلفة ، ويمكن للتكامل مع طريقة الروليت الروسية أن تدمر المسار أو تتركه على قيد الحياة ، وهكذا. اتضح أن الإشغال أصبح المصدر الرئيسي لعدم الكفاءة ، وليس من السهل منعه دون اتخاذ تدابير طارئة.

تتبع مسار التدفق

تم تصميم خوارزمية تتبع مسار التدفق لمعالجة السبب الجذري للمشكلة المزدحمة. تتبع مسار التدفق يقسم خوارزمية تتبع المسار إلى أربع خطوات:

1. توليد
2. مد
3. ظل
4. انضم

يتم تنفيذ كل مرحلة كبرنامج منفصل. لذلك ، بدلاً من تنفيذ تتبع مسار كامل كبرنامج GPU واحد ("kernel" ، kernel) ، سيتعين علينا العمل مع أربعة مراكز. بالإضافة إلى ذلك ، كما سنرى قريبًا ، يتم تنفيذها في حلقة.

المرحلة 1 ("توليد") هي المسؤولة عن توليد الأشعة الأولية. هذا هو جوهر بسيط يقوم بإنشاء نقاط البداية واتجاهات الأشعة بمبلغ يساوي عدد البكسل. مخرجات هذه المرحلة عبارة عن مخزن مؤقت كبير للأشعة وعداد لإعلام المرحلة التالية بعدد الأشعة التي تحتاج إلى معالجة. بالنسبة للأشعة الأساسية ، تساوي هذه القيمة عرض الشاشة مرات ارتفاع الشاشة .

المرحلة 2 ("التجديد") هي اللب الثاني. يتم تنفيذه فقط بعد اكتمال المرحلة 1 لجميع وحدات البكسل. تقرأ النواة المخزن المؤقت الذي تم إنشاؤه في الخطوة 1 وتعبر كل شعاع مع المشهد. إخراج هذه المرحلة هو نتيجة تقاطع لكل شعاع المخزنة في المخزن المؤقت.

يتم تنفيذ المرحلة 3 ("الظل") بعد الانتهاء من المرحلة 2. وتتلقى نتيجة التقاطع من المرحلة 2 وتحسب نموذج التظليل لكل مسار. هذه العملية قد تنشئ أو لا تنشئ أشعة جديدة ، اعتمادًا على ما إذا كان المسار قد اكتمل. المسارات التي تولد الشعاع الجديد (المسار "يمتد") تكتب الشعاع الجديد ("مقطع المسار") إلى المخزن المؤقت. المسارات التي تقوم مباشرة باختبار مصادر الإضاءة ("عينة الإضاءة بوضوح" أو "حساب الحدث التالي") تكتب شعاع الظل إلى مخزن مؤقت ثانٍ.

تتتبع المرحلة 4 ("Connect") أشعة الظل التي تم إنشاؤها في المرحلة 3. وهذا يشبه المرحلة 2 ، ولكن مع وجود اختلاف مهم: تحتاج أشعة الظل إلى العثور على أي تقاطع ، بينما تحتاج الأشعة الممتدة إلى العثور على أقرب تقاطع. لذلك ، تم إنشاء نواة منفصلة لهذا الغرض.

بعد الانتهاء من الخطوة 4 ، نحصل على مخزن مؤقت يحتوي على الأشعة التي تمدد المسار. بعد أخذ هذه الأشعة ، ننتقل إلى المرحلة 2. نواصل القيام بذلك حتى لا توجد أشعة تمديد أو حتى نصل إلى الحد الأقصى لعدد التكرارات.

مصادر عدم الكفاءة

سيرى المبرمج المعني بالأداء الكثير من اللحظات الخطيرة في مثل هذا المخطط من خوارزميات تتبع مسار التدفق:

• بدلاً من استدعاء kernel واحد ، لدينا الآن ثلاث مكالمات لكل تكرار ، بالإضافة إلى kernel من الجيل. النوى الصعبة تعني زيادة معينة في الحمل ، لذلك هذا أمر سيء.
• كل نواة يقرأ مخزنًا ضخمًا كبيرًا ويكتب مخزنًا كبيرًا ضخمًا.
• تحتاج وحدة المعالجة المركزية إلى معرفة عدد مؤشرات الترابط التي سيتم إنشاؤها لكل نواة ، لذلك يجب أن تخبر وحدة معالجة الرسومات وحدة المعالجة المركزية عدد الأشعة التي تم إنشاؤها في الخطوة 3. نقل المعلومات من وحدة معالجة الرسومات إلى وحدة المعالجة المركزية فكرة سيئة ، ويجب القيام بذلك مرة واحدة على الأقل لكل تكرار.
• كيف تكتب المرحلة 3 الأشعة إلى المخزن المؤقت دون إنشاء مسافات في كل مكان؟ إنه لا يستخدم عدادًا ذريًا لهذا الغرض؟
• لا يزال عدد المسارات النشطة في تناقص ، فكيف يمكن لهذا المخطط أن يساعد على الإطلاق؟

لنبدأ بالسؤال الأخير: إذا قمنا بنقل مليون مهمة إلى وحدة معالجة الرسومات ، فلن يتم إنشاء مليون مؤشر ترابط. يعتمد العدد الحقيقي للخيوط المنفذة في وقت واحد على الجهاز ، ولكن في الحالة العامة ، يتم تنفيذ عشرات الآلاف من الخيوط. فقط عندما ينخفض ​​الحمل عن هذا الرقم ، سنلاحظ مشاكل في التوظيف ناتجة عن عدد صغير من المهام.

مصدر قلق آخر هو الإدخال / الإخراج واسع النطاق من المخازن المؤقتة. هذه بالفعل مشكلة ، ولكنها ليست خطيرة كما قد تتوقع: الوصول إلى البيانات يمكن التنبؤ به بشكل كبير ، خاصة عند الكتابة إلى المخازن المؤقتة ، وبالتالي فإن التأخير لا يسبب مشاكل. في الواقع ، تم تطوير وحدات معالجة الرسومات في المقام الأول لهذا النوع من معالجة البيانات.

هناك جانب آخر تتعامل معه وحدات معالجة الرسومات بشكل جيد للغاية وهو العدادات الذرية ، وهو أمر غير متوقع تمامًا للمبرمجين الذين يعملون في عالم وحدة المعالجة المركزية. يتطلب z-buffer وصولاً سريعًا ، وبالتالي فإن تنفيذ العدادات الذرية في وحدات معالجة الرسومات الحديثة فعال للغاية. في الممارسة العملية ، تكون عملية الكتابة الذرية مكلفة تمامًا مثل الكتابة غير المفصلة للذاكرة العالمية. في كثير من الحالات ، سيتم إخفاء التأخير عن طريق التنفيذ المتوازي على نطاق واسع في وحدة معالجة الرسومات.

يبقى سؤالان: مكالمات kernel ونقل البيانات في اتجاهين للعدادات. الأخير هو في الواقع مشكلة ، لذلك نحن بحاجة إلى تغيير معماري آخر: الخيوط المستمرة .

العواقب

قبل الخوض في التفاصيل ، سننظر في الآثار المترتبة على استخدام خوارزمية تتبع مسار واجهة الموجة. أولاً ، دعنا نقول عن المخازن المؤقتة. نحتاج إلى مخزن مؤقت لإخراج بيانات المرحلة 1 ، أي الأشعة الأولية. لكل شعاع نحتاج:

• أصل الشعاع: ثلاث قيم تعويم ، أي 12 بايت
• اتجاه الشعاع: ثلاث قيم تعويم ، أي 12 بايت

في الممارسة العملية ، من الأفضل زيادة حجم المخزن المؤقت. إذا قمت بتخزين 16 بايت لبداية واتجاه الحزمة ، فستتمكن وحدة معالجة الرسومات من قراءتها في عملية قراءة واحدة 128 بت. البديل هو عملية قراءة 64 بت ، تليها عملية 32 بت للحصول على float3 ، والذي يكون بطيئًا تقريبًا. وهذا يعني أنه بالنسبة لشاشة بحجم 1920 × 1080 ، نحصل على: 1920 × 1080 × 32 = = 64 ميغابايت. نحتاج أيضًا إلى مخزن مؤقت لنتائج التقاطع التي أنشأتها Extend kernel. هذا هو 128 بت لكل عنصر ، وهو 32 ميغابايت. علاوة على ذلك ، يمكن لنواة "الظل" إنشاء ما يصل إلى 1920 × 1080 مسار (الحد الأعلى) ، ولا يمكننا كتابتها إلى المخزن المؤقت الذي نقرأ منه. هذا هو 64 ميغابايت أخرى. وأخيرًا ، إذا كان مسار التتبع ينبعث من أشعة الظل ، فإن هذا هو مخزن مؤقت آخر سعة 64 ميجابايت. بعد تلخيص كل شيء ، نحصل على 224 ميغابايت من البيانات ، وهذا فقط لخوارزمية واجهة الموجة. أو حوالي 1 جيجابايت في قرار 4K.

نحن هنا بحاجة إلى التعود على ميزة أخرى: لدينا الكثير من الذاكرة. قد يبدو. أن 1 غيغابايت كثير ، وهناك طرق لتقليل هذا الرقم ، لكن إذا تعاملت مع هذا بشكل واقعي ، فعندما نحتاج حقًا إلى تتبع المسارات في 4K ، فإن استخدام 1 غيغابايت على GPU بسعة 8 غيغابايت سيكون أقل مشاكلنا.

أكثر خطورة من متطلبات الذاكرة ، ستكون العواقب خوارزمية التقديم. لقد اقترحت حتى الآن أننا بحاجة إلى إنشاء شعاع تمديد واحد ، وربما ، شعاع ظل واحد لكل خيط في لب الظل. ولكن ماذا لو أردنا إجراء Ambient Occasion باستخدام 16 أشعة لكل بكسل؟ يجب تخزين 16 من أشعة AO في المخزن المؤقت ، ولكن الأسوأ من ذلك أنها لن تظهر إلا في التكرار التالي. تنشأ مشكلة مماثلة عند تتبع أشعة في نمط الأبيض: من المستحيل تقريبًا إنبعاث شعاع ظل لعدة مصادر ضوئية أو تقسيم شعاع في تصادم مع الزجاج.

من ناحية أخرى ، فإن تتبع مسار واجهة الموجة يحل المشكلات التي أدرجناها في قسم الإشغال:

• في المرحلة 1 ، تُنشئ جميع التدفقات بدون شروط أشعة أساسية وتكتبها إلى المخزن المؤقت.
• في المرحلة 2 ، تتقاطع جميع التدفقات بدون شروط مع المشهد وتكتب نتائج التقاطع إلى المخزن المؤقت.
• في الخطوة 3 ، نبدأ في حساب نتائج التقاطع بنسبة إشغال 100٪.
• في الخطوة 4 ، نعالج قائمة مستمرة من أشعة الظل بدون مسافات.

في الوقت الذي نعود فيه إلى المرحلة 2 بالأشعة الباقية بطول شريحتين ، حصلنا مرة أخرى على مخزن مؤقت للأشعة المضغوطة ، يضمن التشغيل الكامل عندما تبدأ النواة.

بالإضافة إلى ذلك ، هناك ميزة إضافية لا ينبغي الاستهانة بها. يتم عزل رمز في أربع خطوات منفصلة. يمكن لكل نواة استخدام جميع موارد GPU المتاحة (ذاكرة التخزين المؤقت ، الذاكرة المشتركة ، السجلات) دون مراعاة النوى الأخرى. قد يسمح ذلك لجرافيك بتنفيذ رمز التقاطع مع المشهد في المزيد من سلاسل الرسائل ، لأن هذا الرمز لا يتطلب العديد من السجلات مثل رمز التظليل. لمزيد من المواضيع ، كلما كان ذلك أفضل يمكنك إخفاء التأخير.

بدوام كامل ، إخفاء قناع التأخير ، تسجيل التدفق: ترتبط كل هذه الفوائد ارتباطًا مباشرًا بظهور وطبيعة منصة GPU. بالنسبة إلى وحدة معالجة الرسومات ، تعد خوارزمية تتبع مسار واجهة الموجة أمرًا طبيعيًا جدًا.

هل يستحق كل هذا العناء؟

بالطبع ، لدينا سؤال: هل التوظيف الأمثل يبرر الإدخال / الإخراج من المخازن المؤقتة وتكلفة استدعاء النوى الإضافية؟

الجواب نعم ، لكن إثبات ذلك ليس بالأمر السهل.

إذا عدنا إلى مسار التتبع مع ShaderToy لثانية واحدة ، فسنرى أن معظمهم يستخدمون مشهدًا بسيطًا مشفرًا. ليست استبداله بمشهد كامل المهمة مهمة تافهة: بالنسبة لملايين البدائيين ، يصبح تقاطع الحزمة ويصبح المشهد مشكلة معقدة ، غالبًا ما يتم ترك حلها إلى NVidia ( Optix ) أو AMD ( Radeon-Rays ) أو Intel ( Embree ). لا يمكن لأي من هذه الخيارات أن تحل بسهولة محل المشهد الثابت في أداة التتبع الشعاعي الاصطناعي CUDA. في CUDA ، يتطلب التناظرية الأقرب (Optix) التحكم في تنفيذ البرنامج. يسمح لك Embree في وحدة المعالجة المركزية بتتبع الحزم الفردية من الكود الخاص بك ، لكن تكلفة ذلك هي عبء كبير في الأداء: إنه يفضل تتبع مجموعات كبيرة من الحزم بدلاً من الحزم الفردية.


شاشة من حان الوقت قدمت مع اللواء 1.

هل تتبع مسار واجهة الموجة يكون أسرع من بديله (الضخمة ، كما يسميها لين وزملاؤه) يعتمد على الوقت الذي يقضيه في المراكز (المشاهد الكبيرة والتظليل المكلف تقلل من التكلفة النسبية التي تتجاوزها خوارزمية واجهة الموجة) ، على الحد الأقصى لطول المسار ، والعمالة الضخمة والاختلافات في الحمل على السجلات في أربع مراحل. في نسخة مبكرة من Brigade Path Tracer الأصلي ، وجدنا أنه حتى مشهد بسيط مع مزيج من الأسطح العاكسة ولامبرت التي تعمل على GTX480 استفادت من استخدام واجهة الموجة.

تدفق تتبع المسار في المنارة 2

تحتوي منصة Lighthouse 2 على اثنين من تتبع مسار واجهة الموجة. أول استخدام Optix Prime لتنفيذ المرحلتين 2 و 4 (مراحل تقاطع الأشعة والمشاهد) ؛ في الثانية ، يتم استخدام Optix مباشرة لتنفيذ هذه الوظيفة.

Optix Prime هو إصدار مبسط من Optix لا يتعامل إلا مع تقاطع مجموعة من الحزم مع مشهد يتكون من مثلثات. على عكس مكتبة Optix الكاملة ، لا يدعم رمز التقاطع المخصص ، ولا يتقاطع مع المثلثات فقط. ومع ذلك ، هذا هو بالضبط ما هو مطلوب لتتبع مسار واجهة الموجة.

يتم تطبيق تتبع مسار واجهة الموجة المستندة إلى Optix في rendercore.cpp لمشروع rendercore.cpp . تبدأ تهيئة Optix Prime في الدالة Init وتستخدم rtpContextCreate . يتم إنشاء المشهد باستخدام rtpModelCreate . يتم إنشاء مخازن شعاع مختلفة في وظيفة rtpBufferDescCreate باستخدام rtpBufferDescCreate . لاحظ أنه بالنسبة لهذه المخازن المؤقتة ، فإننا نوفر مؤشرات الأجهزة المعتادة: وهذا يعني أنه يمكن استخدامها في كلٍ من Optix وفي مراكز CUDA العادية.

يبدأ Render طريقة Render . لملء المخزن المؤقت للأشعة الأساسية ، generateEyeRays مجموعة CUDA تسمى generEyeRays. بعد ملء المخزن المؤقت ، يتم استدعاء Optix Prime باستخدام rtpQueryExecute . مع ذلك ، تتم كتابة نتائج التقاطع إلى extensionHitBuffer . لاحظ أن جميع المخازن المؤقتة تبقى في وحدة معالجة الرسومات: باستثناء مكالمات kernel ، لا توجد حركة مرور بين وحدة المعالجة المركزية ووحدة معالجة الرسومات. يتم تطبيق مرحلة "الظل" في قلب shade CUDA العادي. تنفيذه في pathtracer.cu .

تجدر الإشارة إلى بعض تفاصيل التنفيذ لـ optixprime_b . أولاً ، يتم تتبع أشعة الظل خارج دورة واجهة الموجة. هذا صحيح: تؤثر شعاع الظل على البكسل فقط إذا لم يتم حظره ، ولكن في جميع الحالات الأخرى لا تكون نتيجتها مطلوبة في أي مكان آخر. وهذا يعني أن شعاع الظل يمكن التخلص منه ، ويمكن تتبعه في أي وقت وبأي ترتيب. في حالتنا ، نستخدم هذا من خلال تجميع أشعة الظل بحيث تكون الدفعة التي تم تتبعها مؤخرًا كبيرة بقدر الإمكان. هذا له نتيجة واحدة غير سارة: مع تكرار N لخوارزمية واجهة الموجة والأشعة السينية الأولية ، فإن الحد الأقصى لعدد الأشعة الظل يساوي XN .

تفصيل آخر هو معالجة العدادات المختلفة. يجب أن تعرف مراحل "التجديد" و "الظل" عدد المسارات النشطة. يتم تحديث عدادات هذا في وحدة معالجة الرسومات (ذريًا) ، مما يعني أنها تستخدم في وحدة معالجة الرسومات ، حتى دون الرجوع إلى وحدة المعالجة المركزية. لسوء الحظ ، يكون هذا مستحيلًا في إحدى الحالات: تحتاج مكتبة Optix Prime إلى معرفة عدد الأشعة التي تم تتبعها. للقيام بذلك ، نحتاج إلى إرجاع معلومات العدادات بمجرد تكرارها.

استنتاج

تشرح هذه المقالة ماهية تتبع مسار واجهة الموجة ولماذا من الضروري إجراء تتبع المسار بفعالية على وحدة معالجة الرسومات. يتم تقديم تطبيقه العملي في منصة Lighthouse 2 ، وهي مفتوحة المصدر ومتاحة على جيثب .