タスク並列処理におけるリソース競合の問題
この例では、「(並列) アプリケーションのパフォーマンスがマルチコア マシンまたはクラスターでどの程度のものになるか」という質問に対して具体的な回答を提示するのがなぜ非常に難しいのかということについて考えます。最も一般的な回答は「ハードウェアとアプリケーションによって異なる」というものであり、ここでは、それ以上の回答ができない理由を説明します。
この例では、一般的なマルチコア コンピューターで発生するメモリ アクセスの競合について説明します。この例では、CPU が 1 つだけ搭載されている同じマルチコア コンピューターですべてのワーカーが実行されている例を取り上げます。
関連する例:
対象の問題を単純化するため、ディスク IO を伴わずにタスクを並列実行する場合のコンピューターの性能のベンチマークを実行します。こうすることで、並列アプリケーションに影響する可能性のある以下のような要素を考慮しなくても済みます。
プロセス間通信の量
プロセス間通信のネットワーク帯域幅とレイテンシ
プロセスの起動時間とシャットダウン時間
プロセスへの要求の送信時間
ディスク IO 性能
その結果、以下の要素のみを考慮することになります。
タスク並列コードの実行時間
リソース競合と効率性に関する例
なぜ、このようなシンプルなベンチマークを実行することに意義があるのかを理解するため、次の例について考えてみてください。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 キャッシュに対して大きすぎると、メモリ アクセスの競合によるパフォーマンスの低下が見られるようになります。このようなことが発生する要因はいくつかありますが、この例で最も重要なのは以下の点です。
関数で行うデータ計算の量が比較的少ない。この場合の代表例はベクトルの総和計算です。
関数でアクセスするデータ チャンクが小さいか、または関数のデータ アクセス パターンが不規則である。以下のグラフに固有値計算 (eig) と特異値分解 (svd) の場合の値を示します。
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