ما يمكن أن تجعل برنامج تشغيل أبطأ عند استخدام المزيد من المواضيع ؟

Question

هذا السؤال هو عن نفس البرنامج سابقا سئل عن.باختصار لدي برنامج مع هيكل حلقة مثل هذا:

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

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

أنا أول من كتب هذا البرنامج إلى استخدام خيط واحد.ثم تحويل ذلك إلى استخدام العديد من المواضيع مثل هذا الموضوع n يعمل كل التكرار من الحلقة الخارجية حيث i1 % nthreads == n.وبالتالي فإن وظيفة يعمل في كل موضوع يبدو

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

و كل thread_local_histograms تضاف في الموضوع الرئيسي في نهاية المطاف.

هنا شيء غريب:عند تشغيل البرنامج مع فقط 1 موضوع معين حجم الحساب ، فإنه يأخذ حوالي 6 ثوان.عندما تعمل مع 2 أو 3 المواضيع, تفعل بالضبط نفس الحساب ، فإنه يأخذ حوالي 9 ثوان.لماذا هذا ؟ أتوقع أن استخدام 2 المواضيع سيكون أسرع من 1 الموضوع منذ لدي ثنائي النواة وحدة المعالجة المركزية.البرنامج لا يستخدم أي mutexes أو غيرها تزامن الأوليات حتى اثنين من المواضيع يجب أن تكون قادرة على تشغيل في نفس الوقت.

للرجوع إليها:نموذجية الناتج من time (هذا على لينكس) على موضوع واحد:

real    0m5.968s
user    0m5.856s
sys     0m0.064s

واثنين من المواضيع:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

رمز هو في http://static.ellipsix.net/ext-tmp/distintegral.ccs

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

Answer 1

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

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

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

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

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

وإذا كان يعمل لينكس الحل الوحيد بالنسبة لك، يمكنك استخدام <لأ href = "http://www.kernel.org/doc/man-pages/online/pages/man3/random_r.3.html" يختلط = "نوفولو noreferrer"> random_r . انها تسمح لك لتمرير الدولة مع كل مكالمة. مجرد استخدام كائن حالة فريدة من نوعها في الموضوع. ولكن هذه الوظيفة هو امتداد سي العمومية، هو على الأرجح غير معتمدة من قبل الأنظمة الأساسية الأخرى (لا جزءا من المعايير C ولا من معايير POSIX AFAIK - عدم وجود هذه الوظيفة على نظام التشغيل Mac OS X على سبيل المثال، قد لا توجد في سولاريس أو فري).

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

static uint32_t getRandom(uint32_t * m_z, uint32_t * m_w)
{
    *m_z = 36969 * (*m_z & 65535) + (*m_z >> 16);
    *m_w = 18000 * (*m_w & 65535) + (*m_w >> 16);
    return (*m_z << 16) + *m_w;
}

من المهم أن "البذور" m_z وm_w بطريقة سليمة إلى حد ما، وإلا فإن النتائج ليست عشوائية على الإطلاق. قيمة البذور نفسها يجب أن يكون بالفعل عشوائي، ولكن هنا هل يمكن استخدام نظام عشوائي عدد المولدات.

uint32_t m_z = random();
uint32_t m_w = random();
uint32_t nextRandom;

for (...) {
    nextRandom = getRandom(&m_z, &m_w);
    // ...
}

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

static double getRandomDouble(uint32_t * m_z, uint32_t * m_w)
{
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (getRandom(m_z, m_w) + 1) * 2.328306435454494e-10;
}

وفي محاولة لجعل هذا التغيير في التعليمات البرمجية واسمحوا لي أن أعرف كيف يمكن للنتائج المؤشر هي: -)

Answer 2

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

---

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

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

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

Answer 3

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

Answer 4

أحد الاحتمالات هو أن الوقت المستغرق في إنشاء المواضيع يتجاوز الوفورات التي تتحقق من خلال استخدام مؤشرات الترابط.أعتقد أن ن ليست كبيرة جدا ، إذا كان الوقت المنقضي هو فقط 6 ثوان O(n^4) العملية.

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

هذه المادة تفاصيل الافتراضي موضوع تقارب وكيفية تغيير التعليمات البرمجية الخاصة بك لضمان المواضيع تشغيل محددة النوى.

Answer 5

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

وتجنب وجود العديد من المواضيع العمل على نفس مساحة الذاكرة. تخصيص بيانات منفصلة لكل موضوع للعمل عليه، ثم ينضم اليهم معا عند انتهاء العملية الحسابية.

Answer 6

من على قمة رأسي:

• مفاتيح السياق
• التنازع على الموارد
• وحدة المعالجة المركزية الخلاف (إذا كانوا لا يحصلون على انقسمت إلى عدة وحدات المعالجة المركزية).
• ذاكرة التخزين المؤقت سحق

Answer 7

وديفيد،

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

و، هل أنت متأكد من دعم للمواضيع في النظام الخاص بك في الواقع تستخدم معالجات متعددة؟ هل الأعلى، على سبيل المثال، وتبين أن كلا من النوى في المعالج تستخدم عند تشغيل البرنامج؟