موازاة OpenMP على دالة متكررة

Question

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

recursivepopulatearray(theobject)
{
  <main thread>
  for each child of theobject
  {
     assign array index
     <child thread(s)>
       populate array element for child object
     </child thread(s)>
     recursivepopulatearray(childobject)
  }
  </main thread>
}

فهل من الممكن القيام بذلك باستخدام OpenMP، وإذا كان الأمر كذلك، فكيف؟هل هناك مكتبات موازية أخرى يمكنها التعامل مع هذا بشكل أفضل؟

إضافة: للإستجابة ل طلب دافيد لمزيد من التوضيح, ، اسمحوا لي أن أشرح المزيد من التفاصيل.لنفترض أن المشهد مرتب كالتالي:

-Bicycle Frame
  - Handle Bars 
  - Front Wheel
  - Back Wheel
-Car Frame
  - Front Left Wheel
  - Front Right Wheel
  - Back Left Wheel
  - Back Right Wheel

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

index 0: Bicycle Frame
index 1: Handle Bars 
index 2: Front Wheel
index 3: Back Wheel
index 4: Car Frame
index 5: Front Left Wheel
index 6: Front Right Wheel
index 7: Back Left Wheel
index 8: Back Right Wheel

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

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

Answer 1

إليك قطعة معدلة من شبه التعليمات البرمجية التي يجب أن تعمل.

populatearray(thescene)
{
  recursivepopulatearray(thescene)

  #pragma omp parallel for
  for each element in array
    populate array element based on associated object
}

recursivepopulatearray(theobject)
{
  for each childobject in theobject
  {
     assign array index and associate element with childobject
     recursivepopulatearray(childobject)
  }
}

Answer 2

أعتقد أنه يجب عليك توضيح سؤالك بشكل أفضل (على سبيل المثال:ما الذي يجب فعله بالضبط بشكل تسلسلي ولماذا)

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

Answer 3

gbjbaanb المذكورة ، يمكنك القيام بذلك بسهولة - يتطلب مجرد بيان PRAGMA لتتم بشكل مواز هذا

ولكن هناك عدد قليل من الأشياء لمشاهدة ل:

أولا، أذكر لكم أن النظام هو crutial هنا. إذا كنت بحاجة للحفاظ على ترتيب في تسطيح بنية هرمية، parallelizing (على هذا المستوى) ستكون إشكالية. كنت على الأرجح سوف تفقد تماما الطلب الخاص بك.

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

إذا كنت تريد الذهاب للقيام بذلك، ربما يجب عليك وضع المعلمة مستوى، وبشكل مواز فقط أول زوجين من المستويات. احملوا 4 سبيل المثال طفل لكل الأم، إذا كنت تتم بشكل مواز للمستويات 2 الأولى، وكنت بالفعل تم كسر هذا إلى 16 قطع متوازية (وتسمى الفترة من 4 قطع متوازية).

ومن ما ذكرتم، ويهمني ان ترك هذا الجزء المسلسل، والتركيز بدلا من الثانية حيث أذكر لكم:

و"ثم يخترق أن مجموعة عدة مرات لرسم الأشياء / تراكب، الخ."

وهذا يبدو وكأنه المكان المثالي لتتم بشكل مواز.

Answer 4

لموازنة الخيط الفرعي، ما عليك سوى وضع براغما قبل الحلقة:

#pragma omp parallel for
for (i=0; i < elements; i++) 
{
}

تم إنجاز المهمة.

الآن، أنت على حق تمامًا، حيث لا يمكنك الحصول على أي مكتبة ترابط للقيام بت واحد قبل الآخر بطريقة متوازية تمامًا (من الواضح!) انتظر حتى ينتهي الكل" الكلمة الأساسية - الحاجز)، فهي غير مصممة لمحاكاة مكتبة سلاسل المحادثات، ولكنها تسمح لك بتخزين القيم "خارج" القسم الموازي، ووضع علامة على أقسام معينة على أنها "سلسلة مفردة فقط" (كلمة أساسية مرتبة) لذلك قد يساعدك هذا في تعيين الفهارس في حلقة متوازية بينما تقوم الخيوط الأخرى بتعيين العناصر.

ألق نظرة على أ دليل البداية.

إذا كنت تستخدم Visual C++، فستحتاج أيضًا إلى تعيين علامة /omp في إعدادات إنشاء برنامج التحويل البرمجي لديك.