Аналогия для конкуренции ресурса и КПД

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

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

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

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

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

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

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

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

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

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

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

Сравнительное тестирование БПФ

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

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