リソース競合と効率性に関する例

なぜ、このようなシンプルなベンチマークを実行することに意義があるのかを理解するため、次の例について考えてみてください。1 人の人がバケツに水を満たし、少し離れた場所まで運び、空にして、元の場所に戻って再び水を満たすという工程が 1 分で行われる場合、2 人でそれぞれ 1 つのバケツを使用して同じ工程を行うとすると、どのくらいの時間がかかるでしょうか。このシンプルな例えは、この例で説明するタスク並列処理のベンチマークを非常によく表しています。最初の印象では、2 人が同時に同じことを行うと 1 人の場合に比べて効率性が低下して非合理的になるように思えます。

1 本のパイプをめぐる競合: リソース競合

前述の例で何も問題なく作業が行われた場合、2 人は バケツ 1 杯の水を運ぶ一連の工程をそれぞれ 1 分で完了させます。各人が 1 つのバケツを速やかに満たして目的の場所まで運び、空にして戻り、お互いの作業を決して妨げないようにします。

しかし、バケツの水は 1 本の細いホースを使用して満たさなければならないという状況を想像してみてください。2 人が同時にホースにたどりつくと、1 人は待たなければなりません。これは、共有リソースの競合の一例です。おそらく 2 人であれば同時にホースを使用しなくても済むため、このホース 1 本でニーズを満たしているかもしれません。しかし、10 人がそれぞれ 1 つのバケツで水を運ぶ場合は、誰かが必ず待たなければならなくなるでしょう。

この例では、ホースがコンピューターのハードウェア (さらに具体的に言うと、コンピューター メモリへのアクセス) に相当します。複数のプログラムが 1 つの CPU コアでそれぞれ同時に実行され、それらすべてがコンピューターのメモリに格納されているデータにアクセスする必要がある場合、メモリ帯域幅が限られるため、いくつかのプログラムが待機しなければならなくなることもあります。

同じホース、異なる距離、異なる結果

前述の例をさらに進め、2 人がそれぞれ 1 つのバケツを運ぶときにホースで競合が発生し、その場合は、タスクを変更して、少し遠くまで水を運ぶようにするものとします。この変更されたタスクを実行する場合、2 人は時間の大部分を作業 (つまり、バケツの運搬) に費やし、共有リソース (つまり、ホース) の競合の時間はわずかになります。そのため、同時にホースが必要になる可能性は低くなり、したがって、変更されたタスクでは並列処理効率が元のタスクに比べて高くなります。

以上のことをこの例のベンチマークに当てはめると、プログラムの実行ではコンピューター メモリへの多数のアクセスが必要でも、データが取得されると、それを使用して実行する処理の量は非常に少ないということになります。一方で、プログラムで取得したデータを使用して多量の計算を実行する場合は、データの取得にどのくらいの時間がかかるかということは重要ではなくなり、メモリ アクセス待機時間は計算時間に比べてわずかなものとなります。

また、アルゴリズムのメモリ アクセスがどの程度予測可能かということもメモリ アクセス競合の度合いに影響します。メモリが規則的かつ予測可能な方法でアクセスされる場合は、メモリが不規則にアクセスされる場合ほど競合が発生することはなくなります。この件については、特異値分解の計算の方が行列の乗算よりも競合が発生しやすい例などを使用して後述します。

この例のコードは以下の関数に含まれています。

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;

ベンチマークの問題を用意

ここでの計算用に、処理のたびにコンピューターのメモリから CPU に取得しなければならないような大きなサイズの入力行列を作成します。つまり、リソース競合を意図的に発生させるのに十分な大きさにするということです。

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 言語構成のパフォーマンスのベンチマークを実行するのではありません。そうではなく、プログラムの多数のコピーを同時に実行するための OS とハードウェアの性能のベンチマークを実行します。

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 の値を変えながら測定します。この総和計算は極めてシンプルなものであるため、複数の総和計算をマルチコア CPU で同時に実行してリソース競合が発生するようにします。その結果、複数の計算の評価を同時に行う場合は、これらの評価を同時に行わなければアイドル状態になる CPU で計算の評価を 1 回だけ実行する場合よりも、総和計算にかかる時間は長くなることが予測されます。

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

Execution times: 0.367254, 0.381174, 0.395128, 0.421978

FFT のベンチマーク

ここでは、計算量の多い問題である ベクトルの FFT の計算問題について考えます。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

行列乗算

最後に、FFT や総和計算よりもさらに計算量が多い問題について考えます。行列乗算の場合もメモリ アクセスが極めて規則的であるため、マルチコア マシンで非常に効率的に並列実行できる可能性があります。

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

データ サイズを要因とするリソース競合の確認

結果を確認するときには、関数でどのようにデータが CPU のキャッシュとやり取りされるかということに留意しなければなりません。データ サイズが小さい場合は、すべての関数で CPU キャッシュが常に使用されます。その場合、完全な高速化を実現できることが予測できます。入力データが CPU キャッシュに対して大きすぎると、メモリ アクセスの競合によるパフォーマンスの低下が見られるようになります。このようなことが発生する要因はいくつかありますが、この例で最も重要なのは以下の点です。

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