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

Question

Я работаю над реализацией MATLAB адаптивного умножения вектора матрицы для очень больших разреженных матриц, исходящих от конкретной дискретизации PDE (с известной структурой разреженности).

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

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

Благодаря https://stackoverflow.com/a/9938666/2965879, Я смог использовать это, заказав блоки в обратном порядке, таким образом, первым начал с самых больших.

Тем не менее, количество записей так сильно отличается от блока к блоку, что непосредственно работа PARFOR сильно ограничено блоками с наибольшим количеством записей, даже если они подаются в цикл в обратном направлении.

Мое решение состоит в том, чтобы сделать самые большие блоки последовательно (но параллельно на уровне записей!), Который хорошо, пока накладные расходы на иранд не имеют большого значения, соответственно. Блоки не становятся слишком маленькими. Остальные блоки я тогда делаю с Parfor. В идеале, я бы позволил Мэтлабу решить, как справиться с этим, но, поскольку вложенная петля Parfor теряет свой параллелизм, это не работает. Кроме того, упаковка оба петли в один (почти невозможна.

Теперь мой вопрос о том, как наилучшим образом определить это отсечение между серийным и параллельным режимом, принимая во внимание информацию, которую я имею, о количестве записей (форма кривой упорядоченных записей может отличаться для разных проблем), как ну, количество работников, которые у меня есть.

До сих пор я работал с 12 работниками, доступными по стандартной лицензии PCT, но с тех пор, как я начал работать над кластером, определение этого отсечения становится все более и более важным (поскольку для многих ядер накладные расходы Серийный цикл становится все более и более дорогостоящим по сравнению с параллельной петлей, но аналогично, наличие блоков, которые удерживают остальные, еще более дорогостоящие).

Для 12 ядер (соответствует конфигурации вычислительного сервера, с которым я работал), я выяснил разумный параметр 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-loop (и, вероятно, больше). Моя главная причина объединить все состоит в том, что я не хочу оценивать/определять более детальные затраты.

Я использую приведенную выше рутину, чтобы определить отсечение следующим образом:

% 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 с его петлей все время, но в моем случае (num_blocks<500) это абсолютно незначительно.

Наконец, если приличное значение cost_it не легко представляется, можно попытаться рассчитать его, измеряя фактическое время выполнения каждого блока, а также чисто параллельную его часть, а затем пытаясь соответствовать полученным данным для прогнозирования затрат и получить обновленную стоимость cost_it Для следующего вызова рутины (с использованием разницы между общей стоимостью и параллельными затратами или вставленной стоимостью нуля в установленную формулу). Надеемся, что это должно «сходиться» к наиболее полезному значению cost_it для рассматриваемой проблемы.