النفقات العامة بسبب استخدام الأحداث

Question

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

المشكلة هي ما يلي: لدي حوالي 1000 حلقات من كل حوالي 10'000 تكرار تفعل ذلك. يجب تنفيذ هذه الحلقات بالتتابع، لكن لدي 4 CPUs متاحة. ما أحاول القيام به هو تقسيم حلقات التكرار 10'000 في حلقات التكرارات 4 2'500، أي واحدة لكل موضوع. ولكن لا بد لي من انتظار الحلقات الأربعة الصغيرة حتى النهاية قبل الذهاب إلى التكرار "الكبير" التالي. هذا يعني أنني لا أستطيع حزم الوظائف.

مشكلتي هي أن استخدام تجمع الخيط و 4 خيوط أبطأ بكثير من القيام بالوظائف بالتتابع (وجود حلقة واحدة تنفذها مؤشر ترابط منفصل أبطأ بكثير من تنفيذها مباشرة في الخيط الرئيسي بالتتابع).

أنا على ويندوز، لذلك أقوم بإنشاء أحداث مع CreateEvent() ثم انتظر واحدا منهم باستخدام WaitForMultipleObjects(2, handles, false, INFINITE) حتى يستدعي الخيط الرئيسي SetEvent().

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

سؤالي هو: هل من الطبيعي أن تستخدم استخدام الأحداث "الكثير من" الوقت؟ إذا كان الأمر كذلك، هل هناك آلية أخرى يمكنني استخدامها وهذا سيكون أقل تكلفة؟

فيما يلي بعض الكود لتوضيح (بعض الأجزاء ذات الصلة المنسوخة من فئة تجمع الخيط الخاصة بي):

// thread function
unsigned __stdcall ThreadPool::threadFunction(void* params) {
    // some housekeeping
    HANDLE signals[2];
    signals[0] = waitSignal;
    signals[1] = endSignal;

    do {
        // wait for one of the signals
        waitResult = WaitForMultipleObjects(2, signals, false, INFINITE);

        // try to get the next job parameters;
        if (tp->getNextJob(threadId, data)) {
            // execute job
            void* output = jobFunc(data.params);

            // tell thread pool that we're done and collect output
            tp->collectOutput(data.ID, output);
        }

        tp->threadDone(threadId);
    }
    while (waitResult - WAIT_OBJECT_0 == 0);

    // if we reach this point, endSignal was sent, so we are done !

    return 0;
}

// create all threads
for (int i = 0; i < nbThreads; ++i) {
    threadData data;
    unsigned int threadId = 0;
    char eventName[20];

    sprintf_s(eventName, 20, "WaitSignal_%d", i);

    data.handle = (HANDLE) _beginthreadex(NULL, 0, ThreadPool::threadFunction,
        this, CREATE_SUSPENDED, &threadId);
    data.threadId = threadId;
    data.busy = false;
    data.waitSignal = CreateEvent(NULL, true, false, eventName);

    this->threads[threadId] = data;

    // start thread
    ResumeThread(data.handle);
}

// add job
void ThreadPool::addJob(int jobId, void* params) {
    // housekeeping
    EnterCriticalSection(&(this->mutex));

    // first, insert parameters in the list
    this->jobs.push_back(job);

    // then, find the first free thread and wake it
    for (it = this->threads.begin(); it != this->threads.end(); ++it) {
        thread = (threadData) it->second;

        if (!thread.busy) {
            this->threads[thread.threadId].busy = true;

            ++(this->nbActiveThreads);

            // wake thread such that it gets the next params and runs them
            SetEvent(thread.waitSignal);
            break;
        }
    }

    LeaveCriticalSection(&(this->mutex));
}

Answer 1

إذا كنت تعاني من حلقات متوازية واستخدام VS 2008، فاقترح النظر في OpenMP. إذا كنت تستخدم Visual Studio 2010 Beta 1، أود أن أقترح النظر إلى مكتبة نمط الموازية, ، وخاصة "موازية ل" / "موازية لكل" واجهات برمجة التطبيقات أو ال "فريق العمل فئة لأن هذه من المرجح أن تفعل ما تحاول القيام به، فقط مع رمز أقل.

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

أود أن أقترح النظر إلى هذا تحت profiler مثل Xperf. Profiler F1 في Visual Studio 2010 Beta 1 (يحتوي على أوضاع التزامن الجديدة 2 تساعد على الرؤية بالتنافس) أو VTENE VTUNE.

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

حظا طيبا وفقك الله

-Rick.

Answer 2

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

يمكنك العثور على بعض التفاصيل هنا.

Answer 3

نعم، WaitForMultipleObjects مكلفة للغاية. إذا كانت وظائفك صغيرة، فإن العلبة العامة للمزامنة ستبدأ في تغلب على تكلفة القيام بهذه المهمة بالفعل، كما تراه.

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

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

Answer 4

احترس، ما زلت تطلب وظيفة التالية بعد انبعاث النهاية.

for( ;; ) {
    // wait for one of the signals
    waitResult = WaitForMultipleObjects(2, signals, false, INFINITE);
    if( waitResult - WAIT_OBJECT_0 != 0 )
        return;
    //....
}

Answer 5

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

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

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

Answer 6

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

بالمناسبة، ما هو سؤالك بالضبط؟ سأكون قادرا على الإجابة أكثر دقة مع سؤال أكثر دقة :)

تعديل:

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

يجب أن تبحث عن اختناقات المزامنة بين الخيوط. يمكنك تتبع مواد المواضيع في انتظار أن تبدأ ...

تحرير: بعد المزيد من التلميحات ...

إذا اعتقدت بشكل صحيح، فإن مشكلتك هي استخدام كور / معالجات جهاز الكمبيوتر الخاص بك بكفاءة بفعالية لبعض تجهيز بعض المعالجة المتسلسلة ESSENCEALY.

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

Answer 7

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

"باهظ الثمن" هو مصطلح نسبي. هل الطائرات باهظة الثمن؟ هي السيارات؟ أو الدراجات ... الأحذية ...؟

في هذه الحالة، السؤال هو: هل الأحداث "باهظة الثمن" نسبة إلى الوقت المستغرق إلى الوظائف لتنفيذ الوظائف؟ سيساعد ذلك في نشر بعض الأرقام المطلقة: كم من الوقت تأخذ العملية عندما "غير مدعومة"؟ هل هي أشهر، أو عدد قليل من femtoseconds؟

ماذا يحدث للوقت الذي تزيد حجم الخيط؟ جرب حجم حمام السباحة من 1، ثم 2 ثم 4، إلخ.

أيضا، كما كان لديك بعض المشكلات مع Threadpools هنا في الماضي، أود أن أقترح بعض التصحيح لحساب عدد المرات التي يتم فيها استدعاء ThreadFunction الخاص بك بالفعل ... هل تتطابق مع ما تتوقعه؟

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

Answer 8

منذ أن تقول أنه كذلك كثيراً أبطأ بالتوازي من التنفيذ المتسلسل، أفترض أن وقت المعالجة الخاص بك لتكرير حلقة 2500 الداخلية الصغيرة (في نطاق الثواني الصغيرة القليلة). ثم ليس هناك الكثير الذي يمكنك القيام به باستثناء مراجعة خوارزمية الخاص بك لتقسيم قطع أكبر من المسبقة؛ لن يساعد OpenMP ولم تساعد كل تقنيات المزامنة الأخرى إما لأنها جميعا تعتمد جميعها بشكل أساسي على الأحداث (لا تتأهل SPIN LOOPS).

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

Answer 9

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

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