5

私は、PDE の特定の離散化 (既知のスパース構造) から生じる非常に大きなスパース行列の適応行列ベクトル乗算の MATLAB 実装に取り​​組んでいます。

多くの前処理の後、選択したエントリを計算したい多数の異なるブロック (たとえば、200 を超える) ができあがります。

前処理ステップの 1 つは、計算したいブロックごとの (数) エントリを決定することです。各エントリで同じ）。

https://stackoverflow.com/a/9938666/2965879のおかげで、ブロックを逆順に並べることでこれを利用できるようになり、MATLAB が最初に最大のものから開始するようになりました。

ただし、エントリの数はブロックごとに大きく異なるため、parfor を直接実行することは、ループに逆に供給されたとしても、エントリの数が最大のブロックによって厳しく制限されます。

私の解決策は、最大のブロックを連続して実行することです (ただし、エントリのレベルで並列化されます!)。これは、イテランドあたりのオーバーヘッドがあまり問題にならない限り問題ありません。ブロックは小さくなりすぎません。残りのブロックは parfor で行います。理想的には、MATLAB がこれを処理する方法を決定するようにしますが、入れ子になった parfor ループは並列性を失うため、これは機能しません。また、両方のループを 1 つにパッケージ化することは (ほぼ) 不可能です。

私の質問は、エントリ数に関する情報を考慮して、シリアル体制とパラレル体制の間のこのカットオフをどのように決定するのが最善かについてです (順序付けられたエントリの曲線の形状は、問題によって異なる場合があります)。私が利用できる労働者の数と同様に。

これまでは、標準の PCT ライセンスで利用可能な 12 のワーカーで作業していましたが、クラスターでの作業を開始して以来、このカットオフを決定することがますます重要になっています (多くのコアでは、直列ループは並列ループに比べてますますコストがかかりますが、同様に、残りを保持するブロックを持つことはさらにコストがかかります)。

12 コア (つまり、私が使用していた計算サーバーの構成) の場合、カットオフとしてワーカーあたり 100 エントリという妥当なパラメーターを見つけましたが、コアの数がそうでない場合、これはうまく機能しません。ブロック数に比べて小さくなりました (例: 64 対 200)。

コアの数をさまざまなパワー (1/2、3/4 など) で収縮させようとしましたが、これも一貫して機能しません。次に、ブロックをバッチにグループ化し、エントリがバッチごとの平均よりも大きい場合のカットオフを決定しようとしました。最後から離れているバッチの数:

logical_sml = true(1,num_core); i = 0;
while all(logical_sml)
    i = i+1;
    m = mean(num_entr_asc(1:min(i*num_core,end))); % "asc" ~ ascending order 
    logical_sml = num_entr_asc(i*num_core+(1:num_core)) < i^(3/4)*m;  
        % if the small blocks were parallelised perfectly, i.e. all  
        % cores take the same time, the time would be proportional to  
        % i*m. To try to discount the different sizes (and imperfect  
        % parallelisation), we only scale with a power of i less than  
        % one to not end up with a few blocks which hold up the rest  
end  
num_block_big = num_block - (i+1)*num_core + sum(~logical_sml);

(注: このコードはnum_entr_asc、長さが の倍数でないベクトルでは機能しませんnum_coreが、読みやすくするために構造を省略することにしましたmin(...,end)。)

< max(...,...)また、カットオフが早期に検出されないようにするために必要な、両方の条件を組み合わせる (つまり、ワーカーごとの最小エントリと一緒にする) を省略しました。分散をどうにか使用することも少し考えましたが、これまでのところすべての試みは不十分です.

誰かがこれを解決する方法について良いアイデアを持っていれば、とても感謝しています。
この非常に長い質問を読んでくれてありがとう、
よろしく、
アクセル

Ps。私の「Dear stackoverflow」はフィルタリングされているように見えるので、ここで私の質問に対する解決策を何度も見つけてくれてありがとうと言いたい.

4

1 に答える 1

1

ある程度満足のいく解決策を思いついたので、誰かが興味を持っている場合に備えて、共有したいと思いました. アプローチを改善/微調整する方法についてのコメントをいただければ幸いです。

基本的に、並列ループのスケジューラの (非常に) 初歩的なモデルを構築することが唯一の賢明な方法であると判断しました。

function c=est_cost_para(cost_blocks,cost_it,num_cores)
% Estimate cost of parallel computation

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   c: Estimated cost of parallel computation

num_blocks=numel(cost_blocks);
c=zeros(num_cores,1);

i=min(num_blocks,num_cores);
c(1:i)=cost_blocks(end-i+1:end)+cost_it;
while i<num_blocks
    i=i+1;
    [~,i_min]=min(c); % which core finished first; is fed with next block
    c(i_min)=c(i_min)+cost_blocks(end-i+1)+cost_it;
end

c=max(c);

end

空の反復のパラメータcost_itは、多くの異なる副作用の粗雑なブレンドであり、おそらく分離される可能性があります: for/parforループ内の空の反復のコスト (ブロックごとに異なる場合もあります)、および起動時間それぞれ ループのデータの送信parfor(およびおそらくそれ以上)。すべてをまとめる主な理由は、より詳細なコストを見積もり/決定する必要がないようにするためです。

上記のルーチンを使用して、次の方法でカットオフを決定します。

% function i=cutoff_ser_para(cost_blocks,cost_it,num_cores)
% Determine cut-off between serial an parallel regime

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   i: Number of blocks to be calculated serially

num_blocks=numel(cost_blocks);
cost=zeros(num_blocks+1,2);

for i=0:num_blocks
    cost(i+1,1)=sum(cost_blocks(end-i+1:end))/num_cores + i*cost_it;
    cost(i+1,2)=est_cost_para(cost_blocks(1:end-i),cost_it,num_cores);
end

[~,i]=min(sum(cost,2));
i=i-1;

end

特に、可能な限り最も楽観的なスケジューリングest_cost_paraを ( は別として) 想定している の値を膨らませたり変更したりしません。cost_it主に何が最適か分からないため、そのままにしておきます。控えめに (つまり、大きすぎるブロックを並列ループに供給しないように)、もちろんバッファーとして何パーセントかを追加するか、1 より大きい累乗を使用して並列コストを膨らませることもできます。

est_cost_paraが連続して少ないブロックで呼び出されることにも注意してください(cost_blocks両方のルーチンに変数名を使用していますが、一方は他方のサブセットです)。

私の冗長な質問のアプローチと比較して、2 つの主な利点があります。

  1. データ (ブロックの数とそのコストの両方) とコアの数の間の比較的複雑な依存関係は、単一の式で可能になるよりも、シミュレートされたスケジューラーではるかにうまくキャプチャされます。
  2. シリアル/パラレル分散のすべての可能な組み合わせのコストを計算し、最小値を取ることで、一方の側からデータを読み込んでいるときに (たとえば、これまでのデータに比べて大きなジャンプによって) 早く「スタック」することはありません。全体に比べると少ないですが）。

もちろん、est_cost_parawhile ループを常に呼び出していると、漸近的な複雑さが増しますが、私の場合 ( num_blocks<500) は、これはまったく無視できます。

最後に、適切な値がcost_itすぐに現れない場合は、各ブロックの実際の実行時間とその純粋な並列部分を測定して計算し、結果のデータをコストに適合させようとすることができます。を予測し、ルーチンの次の呼び出しのために の更新された値を取得しますcost_it(総コストと並列コストの差を使用するか、当てはめた式にゼロのコストを挿入することにより)。cost_itこれは問題の最も有用な値に「収束」するはずです。

于 2013-11-27T17:00:49.830 に答える