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

Question

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

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

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

Благодаря /questions/36096649/nabor-instrumentov-dlya-parallelnyih-vyichislenij-matlab-dinamicheskoe-raspredelenie-rabotyi-v-tsiklah-parfor/36096665#36096665 я смог использовать это, упорядочив блоки в обратном порядке, что побудило MATLAB начать сначала с самых больших.

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

Мое решение состоит в том, чтобы делать самые большие блоки последовательно (но распараллеливать на уровне записей!), Что хорошо, если накладные расходы на итерацию не имеют большого значения, соответственно. блоки не становятся слишком маленькими. Остальные блоки я потом делаю с parfor. В идеале я бы позволил MATLAB решить, как с этим справиться, но поскольку вложенный цикл 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(...,...) для объединения обоих условий (то есть вместе с минимальным количеством записей на одного работника), что необходимо для того, чтобы отсечение не было найдено слишком рано. Я немного подумал о том, чтобы как-то использовать дисперсию, но пока все попытки были неудовлетворительными.

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

Ps. Поскольку мой "Уважаемый стекопоток", похоже, отфильтрован, позвольте мне поблагодарить за то, что я уже нашел решение моего вопроса здесь.

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 для рассматриваемой проблемы.