Избегание накладных расходов

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

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;
pctRunOnAll 'mpiSettings(''DeadlockDetection'', ''off'');'

Starting parallel pool (parpool) using the 'bigMJS' profile ... connected to 12 workers.

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

Мы хотим эталонное матричное левое деление (\), а не стоимость входа в spmd блок, время, необходимое для создания матрицы или других параметров. Поэтому мы отделяем генерацию данных от решения линейной системы и измеряем только время, необходимое для выполнения последней. Мы генерируем входные данные, используя 2-D блок-циклический codistributor, так как это наиболее эффективная схема распределения для решения линейной системы. Наш бенчмаркинг состоит из измерения времени, которое требуется всем работникам, чтобы завершить решение линейной системы A*x = b. Снова мы пытаемся удалить любой возможный источник накладных расходов.

function [A, b] = getData(n)
    fprintf('Creating a matrix of size %d-by-%d.\n', n, n);
    spmd
        % Use the codistributor that usually gives the best performance
        % for solving linear systems.
        codistr = codistributor2dbc(codistributor2dbc.defaultLabGrid, ...
                                    codistributor2dbc.defaultBlockSize, ...
                                    'col');
        A = codistributed.rand(n, n, codistr);
        b = codistributed.rand(n, 1, codistr);
    end
end

function time = timeSolve(A, b)
    spmd
        tic;
        x = A\b; %#ok<NASGU> We don't need the value of x.
        time = gop(@max, toc); % Time for all to complete.
    end
    time = time{1};
end

Выбор размера задачи

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

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

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

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

% Declare the matrix sizes ranging from 1000-by-1000 up to 45% of system
% memory available to each worker.
maxMemUsagePerWorker = 0.45*memoryPerWorker*1024^3; % In bytes.
maxMatSize = round(sqrt(maxMemUsagePerWorker*poolSize/8));
matSize = round(linspace(1000, maxMatSize, 5));

Сравнение эффективности: Gigaflops

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

Создавая графики, такие как эти, мы можем ответить на такие вопросы, как:

Учитывая размер матрицы, функция бенчмаркинга создает матрицу A и правую сторону b один раз, а затем решает A\b несколько раз, чтобы получить точную меру времени, которое это занимает. Мы используем количество плавающих операций HPC Challenge, так что для матрицы n на n мы считаем операции с плавающей точкой как 2/3*n^3 + 3/2*n^2.

function gflops = benchFcn(n)
    numReps = 3;
    [A, b] = getData(n);
    time = inf;
    % We solve the linear system a few times and calculate the Gigaflops
    % based on the best time.
    for itr = 1:numReps
        tcurr = timeSolve(A, b);
        if itr == 1
            fprintf('Execution times: %f', tcurr);
        else
            fprintf(', %f', tcurr);
        end
        time = min(tcurr, time);
    end
    fprintf('\n');
    flop = 2/3*n^3 + 3/2*n^2;
    gflops = flop/time/1e9;
end

Выполнение бенчмарков

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

fprintf(['Starting benchmarks with %d different matrix sizes ranging\n' ...
         'from %d-by-%d to %d-by-%d.\n'], ...
        length(matSize), matSize(1), matSize(1), matSize(end), ...
        matSize(end));
gflops = zeros(size(matSize));
for i = 1:length(matSize)
    gflops(i) = benchFcn(matSize(i));
    fprintf('Gigaflops: %f\n\n', gflops(i));
end
results.matSize = matSize;
results.gflops = gflops;

Starting benchmarks with 5 different matrix sizes ranging
from 1000-by-1000 to 76146-by-76146.
Creating a matrix of size 1000-by-1000.
Analyzing and transferring files to the workers ...done.
Execution times: 1.038931, 0.592114, 0.575135
Gigaflops: 1.161756

Creating a matrix of size 19787-by-19787.
Execution times: 119.402579, 118.087116, 119.323904
Gigaflops: 43.741681

Creating a matrix of size 38573-by-38573.
Execution times: 552.256063, 549.088060, 555.753578
Gigaflops: 69.685485

Creating a matrix of size 57360-by-57360.
Execution times: 3580.232186, 3726.588242, 3113.261810
Gigaflops: 40.414533

Creating a matrix of size 76146-by-76146.
Execution times: 9261.720799, 9099.777287, 7968.750495
Gigaflops: 36.937936

Графическое изображение эффективности

Теперь мы можем построить график результатов и сравнить с ожидаемым графиком, показанным выше.

fig = figure;
ax = axes('parent', fig);
plot(ax, matSize/1000, gflops);
lines = ax.Children;
lines.Marker = '+';
ylabel(ax, 'Gigaflops')
xlabel(ax, 'Matrix size in thousands')
titleStr = sprintf(['Solving A\\b for different matrix sizes on ' ...
                    '%d workers'], poolSize);
title(ax, titleStr, 'Interpreter', 'none');

Если результаты бенчмарка не так хороши, как вы могли бы ожидать, вот некоторые вещи, которые следует учитывать:

Сравнение различного количества работников

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

Другие примеры, такие как Benchmarking Independent Jobs on the Cluster, объясняют, что при бенчмаркинге параллельных алгоритмов для различного количества работников обычно используется слабое масштабирование. То есть по мере увеличения количества работников мы пропорционально увеличиваем размер проблемы. В случае матричного левого деления мы должны проявить дополнительную осторожность, потому что эффективность деления сильно зависит от размера матрицы. Следующий код создает график эффективности в Gigaflops для всех размеров матрицы, с которыми мы тестировали, и всех различных количества работников, так как это дает нам самое подробное представление о характеристиках эффективности левого деления матрицы в этом конкретном кластере.

s = load('pctdemo_data_backslash.mat', 'workers4', 'workers8', ...
         'workers16', 'workers32', 'workers64');
fig = figure;
ax = axes('parent', fig);
plot(ax, s.workers4.matSize./1000, s.workers4.gflops, ...
     s.workers8.matSize./1000, s.workers8.gflops, ...
     s.workers16.matSize./1000, s.workers16.gflops, ...
     s.workers32.matSize./1000, s.workers32.gflops, ...
     s.workers64.matSize./1000, s.workers64.gflops);
lines = ax.Children;
set(lines, {'Marker'}, {'+'; 'o'; 'v'; '.'; '*'});
ylabel(ax, 'Gigaflops')
xlabel(ax, 'Matrix size in thousands')
title(ax, ...
      'Comparison data for solving A\\b on different numbers of workers');
legend('4 workers', '8 workers', '16 workers', '32 workers',  ...
       '64 workers', 'location', 'NorthWest');

Первое, что мы замечаем при взгляде на график выше, это то, что 64 рабочих позволяют нам решить намного большие линейные системы уравнений, чем это возможно только для 4 рабочих. Кроме того, мы видим, что, даже если бы можно было бы работать с матрицей размера 60,000 на 60,000 на 4 рабочих, мы получили бы эффективность приблизительно только 10 Gigaflops. Таким образом, даже если бы у 4 рабочих было достаточно памяти, чтобы решить такую большую проблему, 64 рабочих, тем не менее, значительно превзошли бы их.

Глядя на наклон кривой для 4 рабочих, мы видим, что существует только скромное увеличение эффективности между тремя самыми большими размерами матрицы. Сравнение этого с более ранним графиком ожидаемой эффективности A\b для различных размеров матрицы мы заключаем, что мы довольно близки к достижению пиковой эффективности для 4 работников с размером матрицы 7772 на 7772.

Глядя на кривую для 8 и 16 работников, мы видим, что эффективность падает для самого большого размера матрицы, что указывает на то, что мы близки или уже исчерпали доступную системную память. Однако мы видим, что увеличение эффективности между вторым и третьим по величине размером матрицы очень скромно, что указывает на стабильность какого-то рода. Поэтому мы догадываемся, что при работе с 8 или 16 рабочими мы, скорее всего, не увидим значительного увеличения Gigaflops, если увеличим системную память и протестируем с большими размерами матрицы.

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

Быстрее

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

peakPerf = [max(s.workers4.gflops), max(s.workers8.gflops), ...
            max(s.workers16.gflops), max(s.workers32.gflops), ...
            max(s.workers64.gflops)];
disp('Peak performance in Gigaflops for 4-64 workers:')
disp(peakPerf)

disp('Speedup when going from 4 workers to 8, 16, 32 and 64 workers:')
disp(peakPerf(2:end)/peakPerf(1))

Peak performance in Gigaflops for 4-64 workers:
   10.9319   23.2508   40.7157   73.5109  147.0693

Speedup when going from 4 workers to 8, 16, 32 and 64 workers:
    2.1269    3.7245    6.7244   13.4532

Поэтому мы заключаем, что мы получаем ускорение примерно 13,5 при увеличении числа рабочих в 16 раз, с 4 рабочих до 64. Как мы отмечали выше, график эффективности показывает, что мы можем увеличить эффективность на 64 рабочих местах (и тем самым улучшить ускорение еще больше), увеличивая системную память на кластерных компьютерах.

Используемый кластер

Эти данные сгенерированы с помощью 16 двухпроцессорных, восьмиядерных компьютеров, каждый с 64 ГБ памяти, подключенных к GigaBit Ethernet. При использовании 4 рабочих мест все они находились на одном компьютере. Мы использовали 2 компьютера для 8 рабочих, 4 компьютера для 16 рабочих и т.д.

Повторное включение обнаружения тупика

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

pctRunOnAll 'mpiSettings(''DeadlockDetection'', ''on'');'

end

ans = 

  struct with fields:

    matSize: [1000 19787 38573 57360 76146]
     gflops: [1.1618 43.7417 69.6855 40.4145 36.9379]