Аналогия соперничества и эффективности ресурсов

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

Конкуренция за один трубопровод: конфликт ресурсов

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

Однако представьте, что они должны заполнить ведра из одного, небольшого водяного шланга. Если они прибудут в шланг одновременно, придется подождать. Это один из примеров конфликта для общего ресурса. Возможно, двум людям не нужно одновременно использовать шланг, и поэтому шланг служит их потребностям; но если у вас есть 10 человек, перевозящих блок каждый, некоторым, возможно, всегда придётся подождать.

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

Тот же шланг, различное расстояние, различные результаты

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

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

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

Код, показанный в этом примере, можно найти в этой функции:

function paralleldemo_resource_bench

Проверьте состояние параллельного пула

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

p = gcp;
if isempty(p)
    error('pctexample:backslashbench:poolClosed', ...
        ['This example requires a parallel pool. ' ...
         'Manually start a pool using the parpool command or set ' ...
         'your parallel preferences to automatically start a pool.']);
end
poolSize = p.NumWorkers;

Настройка задачи бенчмаркинга

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

sz = 2048;
m = rand(sz*sz, 1);

Повторное суммирование

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

function sumOp(m)
    s = 0;
    for itr = 1:100 % Repeat multiple times to get accurate timing
        s = s + sum(m);
    end
end

Функция бенчмаркинга

Ядро функции синхронизации состоит из простого spmd оператор. Заметьте, что мы сохраняем минимальное время выполнения, наблюдаемое для заданного уровня параллелизма, n. Как указано в начале, мы проверяем параллельные задачи задачи, измеряя только фактическое время выполнения. Это означает, что мы не тестируем эффективность MATLAB, Parallel Computing Toolbox™ или spmd языковые конструкции. Скорее мы проверяем способность нашей ОС и оборудования одновременно запускать несколько копий программы.

function time = timingFcn(fcn, numConcurrent)

    time = zeros(1, length(numConcurrent));

    for ind = 1:length(numConcurrent)
        % Invoke the function handle fcn concurrently on n different labs.
        % Store the minimum time it takes all to complete.
        n = numConcurrent(ind);
        spmd(n)
            tconcurrent = inf;
            for itr = 1:5
                labBarrier;
                tic; % Measure only task parallel runtime.
                    fcn();
                tAllDone = gop(@max, toc);  % Time for all to complete.
                tconcurrent = min(tconcurrent, tAllDone);
            end
        end
        time(ind) = tconcurrent{1};
        clear tconcurrent itr tAllDone;
        if ind == 1
            fprintf('Execution times: %f', time(ind));
        else
            fprintf(', %f', time(ind));
        end
    end
    fprintf('\n');
end

Сравнение суммирования

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

tsum = timingFcn(@() sumOp(m), 1:poolSize);

Execution times: 0.367254, 0.381174, 0.395128, 0.421978

Бенчмаркинг БПФ

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

function fftOp(m)
    for itr = 1:10 % Repeat a few times for accurate timing
        fft(m);
    end
end

tfft = timingFcn(@() fftOp(m), 1:poolSize);

Execution times: 1.078532, 1.196302, 1.358666, 1.570749

Матричное умножение

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

function multOp(m)
    m*m;  %#ok<VUNUS> % No need to repeat for accurate timing.
end
m = reshape(m, sz, sz);
tmtimes = timingFcn(@() multOp(m), 1:poolSize);
clear m;

Execution times: 0.667003, 0.768181, 0.846016, 0.989242

Исследуйте искажение ресурса

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

allTimes = [tsum(:), tfft(:), tmtimes(:)];
% Normalize the execution times.
efficiency = bsxfun(@rdivide, allTimes(1, :), allTimes);
speedup = bsxfun(@times, efficiency, (1:length(tsum))');
fig = figure;
ax = axes('parent', fig);
bar(ax, speedup);
legend(ax, 'vector sum', 'vector fft', 'matrix mult', ...
       'Location', 'NorthWest')
xlabel(ax, 'Number of concurrent processes');
ylabel(ax, 'Speedup')
title(ax, ['Effect of number of concurrent processes on ', ...
           'resource contention and speedup']);

Эффект на реальные приложения

Глядя на график выше, мы видим, что эти простые задачи масштабируются очень по-разному на том же компьютере. Когда мы также смотрим на то, что другие проблемы и разные компьютеры могут проявлять очень разное поведение, должно стать ясно, почему нельзя дать общий ответ на вопрос «Как мое (параллельное) приложение будет работать на моей многоядерной машине или на моем кластере?» Ответ на этот вопрос действительно зависит от приложения и рассматриваемого оборудования.

Измерение эффекта размера данных на соперничество ресурсов

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

szs = [128, 256, 512, 1024, 2048];
description = {'vector sum', 'vector fft', 'matrix mult', 'matrix LU', ...
    'matrix SVD', 'matrix eig'};

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

speedup = zeros(length(szs), length(description));
for i = 1:length(szs)
    sz = szs(i);
    fprintf('Using matrices of size %d-by-%d.\n', sz, sz);
    j = 1;
    for f = [{@sumOp; sz^2; 1}, {@fftOp; sz^2; 1}, {@multOp; sz; sz}, ...
            {@lu; sz; sz}, {@svd;  sz; sz}, {@eig;  sz; sz}]
        op = f{1};
        nrows = f{2};
        ncols = f{3};
        m = rand(nrows, ncols);
        % Compare sequential execution to execution on all labs.
        tcurr = timingFcn(@() op(m), [1, poolSize]);
        speedup(i, j) = tcurr(1)/tcurr(2)*poolSize;
        j = j + 1;
    end
end

Using matrices of size 128-by-128.
Execution times: 0.001472, 0.001721
Execution times: 0.002756, 0.004069
Execution times: 0.000221, 0.000367
Execution times: 0.000200, 0.000369
Execution times: 0.001314, 0.002186
Execution times: 0.006565, 0.009958
Using matrices of size 256-by-256.
Execution times: 0.005472, 0.005629
Execution times: 0.010400, 0.013956
Execution times: 0.002175, 0.002994
Execution times: 0.000801, 0.001370
Execution times: 0.008052, 0.009112
Execution times: 0.042912, 0.057383
Using matrices of size 512-by-512.
Execution times: 0.021890, 0.022754
Execution times: 0.055563, 0.083730
Execution times: 0.011029, 0.017932
Execution times: 0.005655, 0.009090
Execution times: 0.052226, 0.067276
Execution times: 0.262720, 0.353336
Using matrices of size 1024-by-1024.
Execution times: 0.090294, 0.110154
Execution times: 0.317712, 0.445605
Execution times: 0.097819, 0.131056
Execution times: 0.037662, 0.057474
Execution times: 0.392037, 0.937005
Execution times: 1.063107, 1.579232
Using matrices of size 2048-by-2048.
Execution times: 0.365510, 0.422942
Execution times: 1.067788, 1.560758
Execution times: 0.667548, 0.980306
Execution times: 0.271354, 0.391217
Execution times: 4.111523, 7.820437
Execution times: 6.101292, 8.984251

Просмотр искажения ресурса как функции от размера данных

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

fig = figure;
ax = axes('parent', fig);
plot(ax, speedup);
lines = ax.Children;
set(lines, {'Marker'}, {'+', 'o', '*', 'x', 's', 'd'}');
hold(ax, 'on');
plot(ax, repmat(poolSize, 1, length(szs)), '--');
hold(ax, 'off');
legend(ax, [description, {'ideal speedup'}], 'Location', 'SouthWest');
ax.XTick = 1:length(szs);
ax.XTickLabel = arrayfun(@(x) {sprintf('%d^2', x)}, szs);
yl = ylim;
ylim([0, max([poolSize + 0.1, yl(2)])])
xlabel(ax, 'Number of elements per process');
ylabel(ax, 'Speedup')
title(ax, 'Effect of data size on resource contention and speedup');

end