غير الخطية القياس .صافي عمليات متعددة النوى آلة

Question

لقد واجهت سلوك غريب في .NET الذي ينفذ جزء كبير من المعالجة المتوازية على مجموعة من البيانات في الذاكرة.

عند تشغيله على معالج متعدد النوى (IntelCore2 Quad Q6600 2.4 GHz) فإنه يسلك التحجيم غير الخطية متعددة المواضيع انطلقت لمعالجة البيانات.

عند تشغيل غير مؤشرات حلقة على جوهر واحد ، عملية قادرة على استكمال ما يقرب من 2.4 ملايين العمليات الحسابية في الثانية الواحدة.عند تشغيل أربعة خيوط تتوقعون أربعة أضعاف الإنتاجية - في مكان ما في الحي من 9 ملايين العمليات الحسابية في الثانية الواحدة - لكن للأسف لا.في واقع الامر فقط يكمل حوالي 4.1 ملايين في الثانية ...قليلا جدا قصيرة من المتوقع الإنتاجية.

وعلاوة على ذلك ، فإن السلوك بغض النظر عن ما إذا كنت تستخدم PLINQ, مجموعة موضوع أو أربعة صراحة إنشاء المواضيع.غريب جدا...

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

نظرياتي في هذه اللحظة:

1. النفقات العامة من جميع تقنيات (موضوع مفاتيح السياق ، الخ) هو الساحقة الحسابات
2. المواضيع لا يحصلون على تعيين كل من النوى الأربعة وقضاء بعض الوقت في انتظار على نفس النواة ..غير متأكد من كيفية اختبار هذه النظرية...
3. .NET CLR المواضيع لا تعمل في الأولوية المتوقع أو خفية داخلية علوية.

أدناه هو ممثل مقتطف من التعليمات البرمجية التي ينبغي أن يحمل نفس السلوك:

    var evaluator = new LookupBasedEvaluator();

    // find all ten-vertex polygons that are a subset of the set of points
    var ssg = new SubsetGenerator<PolygonData>(Points.All, 10);

    const int TEST_SIZE = 10000000;  // evaluate the first 10 million records

    // materialize the data into memory...
    var polygons = ssg.AsParallel()
                      .Take(TEST_SIZE)
                      .Cast<PolygonData>()
                      .ToArray();

    var sw1 = Stopwatch.StartNew();
    // for loop completes in about 4.02 seconds... ~ 2.483 million/sec
    foreach( var polygon in polygons )
        evaluator.Evaluate(polygon);
    s1.Stop(); 
    Console.WriteLine( "Linear, single core loop: {0}", s1.ElapsedMilliseconds );

    // now attempt the same thing in parallel using Parallel.ForEach...
    // MS documentation indicates this internally uses a worker thread pool
    // completes in 2.61 seconds ... or ~ 3.831 million/sec
    var sw2 = Stopwatch.StartNew();
    Parallel.ForEach(polygons, p => evaluator.Evaluate(p));
    sw2.Stop();
    Console.WriteLine( "Parallel.ForEach() loop: {0}", s2.ElapsedMilliseconds );

    // now using PLINQ, er get slightly better results, but not by much
    // completes in 2.21 seconds ... or ~ 4.524 million/second
    var sw3 = Stopwatch.StartNew();
    polygons.AsParallel(Environment.ProcessorCount)
            .AsUnordered() // no sure this is necessary...
            .ForAll( h => evalautor.Evaluate(h) );
    sw3.Stop();
    Console.WriteLine( "PLINQ.AsParallel.ForAll: {0}", s3.EllapsedMilliseconds );

    // now using four explicit threads:
    // best, still short of expectations at 1.99 seconds = ~ 5 million/sec
    ParameterizedThreadStart tsd = delegate(object pset) { foreach (var p in (IEnumerable<Card[]>) pset) evaluator.Evaluate(p); };
     var t1 = new Thread(tsd);
     var t2 = new Thread(tsd);
     var t3 = new Thread(tsd);
     var t4 = new Thread(tsd);

     var sw4 = Stopwatch.StartNew(); 
     t1.Start(hands);
     t2.Start(hands);
     t3.Start(hands);
     t4.Start(hands);
     t1.Join();
     t2.Join();
     t3.Join();
     t4.Join();
     sw.Stop();
     Console.WriteLine( "Four Explicit Threads: {0}", s4.EllapsedMilliseconds );

Answer 1

لذلك اكتشفت أخيرا ما كانت المشكلة - وأعتقد أنه سيكون من المفيد مشاركته مع المجتمع.

كانت القضية بأكملها بأداء غير خطي نتيجة لخط واحد داخل Evaluate() طريقة:

var coordMatrix = new long[100];

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

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

الخاتمة: بعد إجراء هذا التغيير، كانت العملية المتزامنة قادرة على تحقيق 12.2 مليون حساب / ثانية.

ملاحظة مجد إلى إيغور Ostrovsky عن رابط جيرمان له إلى مدونات MSDN التي ساعدتني في تحديد المشكلة وتشخيصها.

Answer 2

نلقي نظرة على هذه المادة: http://blogs.msdn.com/pfxteam/archive/2008/08/12/8849984.aspx.

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

Answer 3

التحجيم غير الخطية هو متوقع مع خوارزمية متوازية في المقارنة مع خوارزمية متتابعة ، لأن هناك بعض الكامنة النفقات العامة في الموازاة.( مثالي بالطبع كنت ترغب في الحصول على أقرب ما يمكن.)

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

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

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

ولذلك قد يكون فكرة أفضل قسم مجموعة ، على افتراض وقت معالجة كل عنصر من المتوقع أن تكون تقريبا متساوية بغض النظر عن الموقف من عنصر.بالنظر إلى أن لديك 10 مليون سجل ، وهذا يعني تقول الموضوع: 1 للعمل على عناصر من 0 إلى 2,499,999, موضوع 2 يعمل على عناصر 2,500,000 إلى 4,999,999 ، إلخ.يمكنك تعيين كل موضوع الهوية واستخدام هذا لحساب النطاق الفعلي.

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

Answer 4

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

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

يحرر: آسف، لقد لاحظت أنك قد تناولت بالفعل كل من نقاطي.