Набор инструментов для параллельных вычислений Matlab, динамическое распределение работы в циклах parfor

Question

Я работаю с длительным циклом Parfor в Matlab.

parfor iter=1:1000
   chunk_of_work(iter);
end

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

Это согласуется с циклом parfor, который статически распределяет работу.Это противоречит документации для набора инструментов параллельных вычислений , найденной здесь :

"Распределение работы является динамическим. Вместо того, чтобы назначать фиксированный диапазон итераций, рабочие распределяютсяновая итерация только после того, как они завершат обработку своей текущей итерации, что приведет к равномерному распределению рабочей нагрузки. "

Есть идеи о том, что происходит?

Answer 1

Я думаю, что документ, который вы цитируете, имеет довольно хорошее описание того, что считается статическим распределением работы: каждому работнику "назначается фиксированный диапазон итераций".Для 4 работников это будет означать, что первому присваивается iter 1: 250, второму iter 251: 500, ... или 1: 4: 100 для первого, 2: 4: 1000 для второго ии т. д.

Вы не сказали точно, что вы наблюдаете, но то, что вы описываете, хорошо согласуется с динамическим распределением рабочей нагрузки: во-первых, четыре (пример) работника работают по одному iter каждый, первый из которыхзаконченные работы над пятым, следующее, которое сделано (что вполне может быть тем же, если три из первых четырех займут несколько больше времени) работает над шестым и так далее.Теперь, если ваши выбросы имеют номера 20, 850 и 900 в том порядке, который MATLAB выбирает для обработки итераций цикла, и каждая занимает в 100 раз больше времени, это означает только то, что 21-я и 320-я итерации будут решаться тремя из четырех рабочих, а один -заняты 20-м (на 320 это будет сделано, теперь предполагается примерно равномерное распределение времени расчета не-выбросов).Рабочий, которому назначена 850-я итерация, тем не менее будет продолжать работать даже после того, как другой решит # 1000, и то же самое для # 900.На самом деле, если бы было около 1100 итераций, то ту, которая работала на # 900, нужно было бы закончить примерно в то время, когда остальные выполняются.назначьте итерации цикла parfor в порядке от 1 до 1000, что не следует предполагать]

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

Добавление: я думаю, однако, что вашенаблюдение, что «поскольку цикл приближается к завершению, рабочий * s *, который оценивал выбросы, продолжает работать», по-видимому, подразумевает, по крайней мере, один из следующих

1. выбросы каким-то образомсреди последних итераций MATLAB начинает обрабатывать
2. У вас много рабочих, в порядке величины нюколичество итераций
3. Ваша оценка количества выбросов (2-3) или оценка их штрафа за время вычислений (коэффициент 100) слишком мала

Answer 2

Проблема, с которой вы столкнулись, хорошо описана в ответе @ arne.b, мне нечего добавить к этому.

Но набор инструментов параллельных вычислений содержит функции для разложения задания на задачи для самостоятельного исполнения.Из вашего вопроса невозможно сделать вывод, что это подходит или что это не подходит для вашего приложения.Если это так, общая стратегия состоит в том, чтобы разбить задание на задачи определенного размера и заставить каждый процессор выполнить задачу, когда закончите, вернуться к стеку незавершенных задач и запустить другую.

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

Answer 3

Распределение работы в PARFOR несколько детерминировано.Вы можете точно наблюдать за тем, что происходит, когда каждый работник записывает на диск, как идут дела, но в основном получается, что PARFOR делит ваш цикл на порции детерминистическим образом, но динамически обрабатывает их.К сожалению, в настоящее время нет способа контролировать эту порцию.

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

Если вы можете предсказать свои выбросы, вы сможете воспользоваться тем, что, грубо говоря, PARFOR выполняет итерации цикла в обратном порядке, поэтому вы можете поместить их в «конец» цикла, чтобы работатьначинается на них немедленно.

Answer 4

В качестве альтернативы PARFOR, в R2013b и более поздних версиях вы можете использовать PARFEVAL и распределять работу так, как вам удобно. Вы можете даже отменить «выбросы времени», когда получите достаточные результаты, если это уместно. Конечно, при разделении существующего цикла на 1000 отдельных удаленных вызовов PARFEVAL возникают накладные расходы. Возможно, это проблема, а может и нет. Вот что я себе представляю:

for idx = 1:1000
     futures(idx) = parfeval(@chunk_of_work, 1, idx);
end
done = false; numComplete = 0;
timer = tic();
while ~done
    [idx, result] = fetchNext(futures, 10); % wait up to 10 seconds
    if ~isempty(idx)
        numComplete = numComplete + 1;
        % stash result
    end
    done = (numComplete == 1000) || (toc(timer) > 100);
end
% cancel outstanding work, has no effect on completed futures
cancel(futures);