В чем причина накладных расходов времени parfeval по сравнению с последовательной реализацией?

Я пытаюсь распараллелить некоторый код, используемый в алгоритме Гаусса-Зейделя, для аппроксимации решения системы линейных уравнений.

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

Код, задействованный в сеансе параллельных вычислений, таков:

future_results(1:num_workers) = parallel.FevalFuture;
for i = 1:num_workers
    start_itv = buck_bound+1 + (i - 1) * worker_length;
    end_itv = min(buck_bound+1 + i * worker_length - 1, ends_of_buckets(current_bucket));                 
    future_results(i) = parfeval(p, @hybrid_parallel_function, 3, A, b, x, x_last, buck_bound, n, start_itv, end_itv);
end
            
for i = 1:num_workers
    [~, arr, start_itv, end_itv] = fetchNext(future_results(i));               
    x(start_itv:end_itv) = arr;
end

Функция, вызываемая parfeval, такова:

function [x_par, start_itv, end_itv] = hybrid_parallel_function (A, b, x, x_last, buck_bound, n, start_itv, end_itv)
    x_par = zeros(end_itv - start_itv + 1, 1);
    for i = start_itv:end_itv
        x_par(i-start_itv+1) = b(i);
        x_par(i-start_itv+1) = x_par(i-start_itv+1) - A(i, 1:buck_bound) * x(1:buck_bound);
        x_par(i-start_itv+1) = x_par(i-start_itv+1) - A(i, buck_bound+1:i-1) * x_last(buck_bound+1:i-1);
        x_par(i-start_itv+1) = x_par(i-start_itv+1) - A(i, i+1:n) * x_last(i+1:n);
        x_par(i-start_itv+1) = x_par(i-start_itv+1) / A(i, i);
    end
end

Весь код можно найти здесь: https://pastebin.com/hRQ5Ugqz

Профилировщик Matlab для матрицы 1000x1000.

Профилировщик Matlab для матрицы 1000x1000. Параллельный код от 20 до 135 раз медленнее, чем его последовательный аналог, в зависимости от выбранной матрицы коэффициентов (и все еще намного быстрее, чем spmd).

Вычисление парфеваля может быть лениво разделено между строками 50 и 57? Тем не менее, я не могу объяснить себе, почему существуют такие большие накладные расходы. Кажется, это как-то связано с тем, сколько раз вызывается парфеваль: я уменьшил время выполнения, уменьшив количество вызовов парфеваля.

Есть ли что-то, что можно еще оптимизировать? Должен ли я прибегать к написанию кода на C++?

Пожалуйста помоги. Большое спасибо!


person catalyst    schedule 11.04.2021    source источник
comment
Как вы настроили свой параллельный пул? По умолчанию MATLAB использует несколько сеансов MATLAB и передает данные между ними. Это предназначено для работы в вычислительных кластерах, где каждый узел в кластере выполняет один сеанс. Однако вы можете настроить его для использования параллелизма на основе потоков. В любом случае меньшее количество больших заданий распараллеливается лучше, чем большое количество маленьких.   -  person Cris Luengo    schedule 11.04.2021
comment
Возможно, вы правы, я попробую parpool('threads'), как только обновлюсь до R2020, спасибо.   -  person catalyst    schedule 12.04.2021


Ответы (1)


Здесь есть несколько возможностей. Наиболее важным является тот простой факт, что если вы используете тип кластера 'local', то рабочие процессы выполняются в однопоточном коде. В ситуациях, когда последовательный код на самом деле использует встроенную многопоточность MATLAB, вы уже в полной мере используете доступное аппаратное обеспечение ЦП, и использование параллельных рабочих операций ничего вам не даст. Не уверен, что это так для вас, но я сильно подозреваю, что это код.

Параллельное выполнение сопряжено с накладными расходами, и, как вы заметили, выполнение меньшего количества вызовов parfeval снижает эти накладные расходы. Ваш код в том виде, в котором он написан, копирует всю матрицу A для каждого работника несколько раз. Вам не нужно менять A, поэтому вы можете использовать parallel.pool.Constant, чтобы избежать повторных копий.

Хотя parfeval является более гибким, он, как правило, менее эффективен, чем parfor, в тех случаях, когда можно применить parfor.

Да, вы можете ожидать, что рабочие начнут работать, как только завершится первый вызов parfeval.

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

person Edric    schedule 12.04.2021
comment
Привет, спасибо за ответ! Надеюсь, я правильно записал parallel.pool.Constant (pastebin.com/F5DX7KAR). К сожалению, время совсем не улучшилось. Как вы и Крис Луенго сказали, мне, возможно, придется попробовать parpool («потоки»), который доступен только начиная с R2020a, поэтому мне придется подождать некоторое время, чтобы обновить. Тем временем я просмотрел std::thread и думаю, что у меня есть хорошие шансы написать его на C++, даже если это означает испорченную часть умножения матриц. - person catalyst; 12.04.2021
comment
@catalyst: если вы собираетесь реализовывать C++, не используйте std::thread, используйте любые абстракции более высокого уровня. Я предпочитаю OpenMP, но вы также можете взглянуть на Intel Treading Blocks или любое количество библиотек, упрощающих задачу распараллеливания алгоритмов. В OpenMP это так же просто, как поставить #pragma parallel for перед циклом for. - person Cris Luengo; 12.04.2021