Прогнозирование времени выполнения параллельного цикла с использованием априорной оценки усилий на итерацию (для заданного количества рабочих)

Я придумал несколько удовлетворительное решение, поэтому, если кому-то интересно, я решил поделиться им. Я все еще был бы признателен за комментарии о том, как улучшить/доработать подход.

В принципе, я решил, что единственный разумный способ — построить (очень) рудиментарную модель планировщика для параллельного цикла:

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-цикле (также может быть разной для каждого блока), а также начало -время работы соотв. передача данных 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 для рассматриваемой проблемы.