هل يجب أن أستخدم الترابط والتكرار معًا؟

Question

لقد كنت أقوم بتعديل أشجار BSP منذ فترة وألعب أيضًا بالخيوط.عند إضافة مثلث إلى شجرة BSP، تنشأ فرصة لإنشاء مؤشر ترابط جديد لأغراض معالجة البيانات بالتوازي.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

يمكن تنفيذ عمليتي الإدراج أعلاه بواسطة خيطين، وبما أنهما لا يعدلان نفس البيانات، فيمكن استخدام المزامنة الرخيصة.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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