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

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

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

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

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

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

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

Источник

4 ответа

Решение

Я думаю, что документ, который вы цитируете, имеет довольно хорошее описание того, что считается статическим распределением работы: каждому работнику "назначается фиксированный диапазон итераций". Для 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, должно быть закончено примерно в то время, когда остальные.

[отредактировано в соответствии с оригинальной формулировкой, подразумевающей, что MATLAB будет по-прежнему назначать итерации цикла parfor в порядке от 1 до 1000, что не следует предполагать]

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

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

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

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

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

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

Источник

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

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

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

Источник

В качестве альтернативы 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);
Источник
Другие вопросы по тегам