توقع وقت تشغيل الحلقة المتوازية باستخدام التقدير المسبق للجهد لكل تكرار (لعدد معين من العمال)

Question

أنا أعمل على تطبيق MATLAB لمضاعفة مصفوفات المتجهات التكيفية لمصفوفات متفرقة كبيرة جدًا قادمة من تقدير معين لـ PDE (مع بنية متناثرة معروفة).

بعد الكثير من المعالجة المسبقة، انتهى بي الأمر بعدد من الكتل المختلفة (أكبر من 200، على سبيل المثال)، والتي أريد حساب الإدخالات المحددة لها.

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

شكرا ل https://stackoverflow.com/a/9938666/2965879, ، لقد تمكنت من الاستفادة من هذا عن طريق ترتيب الكتل بترتيب عكسي، مما دفع MATLAB إلى البدء بالكتل الأكبر أولاً.

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

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

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

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

لـ 12 نواة (Resp.تكوين خادم الحوسبة الذي كنت أعمل معه)، لقد اكتشفت معلمة معقولة تبلغ 100 إدخال لكل عامل كقطع، ولكن هذا لا يعمل بشكل جيد عندما لا يكون عدد النوى صغيرًا بعد الآن بالنسبة إلى عدد الكتل (على سبيل المثال 64 مقابل 200).

لقد حاولت تقليص عدد النوى بقوى مختلفة (على سبيل المثال.1/2، 3/4)، ولكن هذا أيضًا لا يعمل بشكل متسق.بعد ذلك، حاولت تجميع الكتل في دفعات وتحديد الحد الفاصل عندما تكون الإدخالات أكبر من المتوسط ​​لكل دفعة، على التوالي.عدد الدفعات التي تكون بعيدة عن النهاية:

logical_sml = true(1,num_core); i = 0;
while all(logical_sml)
    i = i+1;
    m = mean(num_entr_asc(1:min(i*num_core,end))); % "asc" ~ ascending order 
    logical_sml = num_entr_asc(i*num_core+(1:num_core)) < i^(3/4)*m;  
        % if the small blocks were parallelised perfectly, i.e. all  
        % cores take the same time, the time would be proportional to  
        % i*m. To try to discount the different sizes (and imperfect  
        % parallelisation), we only scale with a power of i less than  
        % one to not end up with a few blocks which hold up the rest  
end  
num_block_big = num_block - (i+1)*num_core + sum(~logical_sml);

(ملحوظة:هذا الرمز لا يعمل مع المتجهات num_entr_asc الذي طوله ليس مضاعفا num_core, ، لكنني قررت حذف min(...,end) إنشاءات للوضوح.)

لقد أغفلت أيضا < max(...,...) للجمع بين الشرطين (أي.مع الحد الأدنى من الإدخالات لكل عامل)، وهو أمر ضروري حتى لا يتم العثور على الحد الأقصى في وقت مبكر جدًا.لقد فكرت قليلاً في استخدام التباين بطريقة أو بأخرى، ولكن حتى الآن كانت جميع المحاولات غير مرضية.

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

Answer 1

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

في الأساس، قررت أن الطريقة الوحيدة المعقولة هي بناء نموذج بدائي (جدًا) للمجدول للحلقة المتوازية:

function c=est_cost_para(cost_blocks,cost_it,num_cores)
% Estimate cost of parallel computation

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   c: Estimated cost of parallel computation

num_blocks=numel(cost_blocks);
c=zeros(num_cores,1);

i=min(num_blocks,num_cores);
c(1:i)=cost_blocks(end-i+1:end)+cost_it;
while i<num_blocks
    i=i+1;
    [~,i_min]=min(c); % which core finished first; is fed with next block
    c(i_min)=c(i_min)+cost_blocks(end-i+1)+cost_it;
end

c=max(c);

end

المعلمة cost_it بالنسبة للتكرار الفارغ فهو مزيج خام من العديد من الآثار الجانبية المختلفة، والتي يمكن فصلها:تكلفة التكرار الفارغ في ملف for/parfor-loop (يمكن أن تكون مختلفة أيضًا لكل كتلة)، بالإضافة إلى وقت بدء التشغيل.نقل البيانات من parfor- حلقة (وربما أكثر).السبب الرئيسي وراء جمع كل شيء معًا هو أنني لا أريد أن أضطر إلى تقدير/تحديد التكاليف الأكثر تفصيلاً.

أستخدم الروتين أعلاه لتحديد القطع بالطريقة التالية:

% function i=cutoff_ser_para(cost_blocks,cost_it,num_cores)
% Determine cut-off between serial an parallel regime

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   i: Number of blocks to be calculated serially

num_blocks=numel(cost_blocks);
cost=zeros(num_blocks+1,2);

for i=0:num_blocks
    cost(i+1,1)=sum(cost_blocks(end-i+1:end))/num_cores + i*cost_it;
    cost(i+1,2)=est_cost_para(cost_blocks(1:end-i),cost_it,num_cores);
end

[~,i]=min(sum(cost,2));
i=i-1;

end

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

لاحظ ذلك أيضًا est_cost_para يتم استدعاؤه بكتل أقل على التوالي (على الرغم من أنني أستخدم اسم المتغير cost_blocks لكلا الروتينين، أحدهما هو مجموعة فرعية من الآخر).

بالمقارنة مع النهج المتبع في سؤالي اللفظي، أرى ميزتين رئيسيتين:

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

وبطبيعة الحال، فإن التعقيد المقارب يكون أعلى عن طريق الاتصال est_cost_para مع حلقة while الخاصة بها طوال الوقت، ولكن في حالتي (num_blocks<500) هذا لا يكاد يذكر على الاطلاق.

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