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

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

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

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

Однако представьте, что им приходится заполнять ведра из единственного, маленького водопроводного шланга. Если они прибудут к шлангу одновременно, придется подождать. Это один из примеров конфликта для общего ресурса. Может быть, двум людям не нужно одновременно использовать шланг, и поэтому шланг служит их потребностям; но если у вас есть 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, 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 является более вычислительной интенсивностью, чем суммирование, мы ожидаем, что мы не увидим одинаковых ухудшений производительности при одновременной оценке нескольких вызовов функции 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