1

同じ数の行とさまざまな数の列 (20 x 〜 200) を持つ約 5,000 の行列があります。これらの各行列は、動的計画法のアルゴリズムで互いに比較する必要があります。

この質問では、比較をすばやく実行する方法を尋ねたところ、2D 畳み込みに関する優れた回答が得られました。その方法を順番に、繰り返し適用して、

list = who('data_matrix_prefix*')
H = cell(numel(list),numel(list));  
for i=1:numel(list)
    for j=1:numel(list)
        if i ~= j
            eval([ 'H{i,j} = compare(' char(list(i)) ',' char(list(j)) ');']);
        end
    end
end

データの小さなサブセットでは高速です (たとえば、9 つの行列の場合、9*9 - 9 = 72 回の呼び出しが ~1 秒で行われ、870 回の呼び出しが ~2.5 秒で行われます)。
ただし、すべてのデータを操作するには、約 2,500 万回の呼び出しが必要です。
また、deal() を使用して、データ内の次の要素だけで構成されるセル配列を作成しようとしたので、単一のループで cellfun() を使用できました。

# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data.
nextData = cell(k,1);
for i=1:k
    [nextData{:}] = deal(data{i});
    H{:,i} = cellfun(@compare,data,nextData,'UniformOutput',false);
end

残念ながら、これは実際にはそれほど高速ではありません。これらのコード例は両方とも、並列化には適していないようです。変数をスライスする方法がわかりません。
compare() は完全にベクトル化されています。行列の乗算と conv2() のみを使用します (cellfun() を含むこれらの操作はすべて、MATLAB でマルチスレッド化する必要があるという印象を受けました)。

(明示的に) 並列化された解決策または問題のより良いベクトル化を見た人はいますか?

私の例は両方とも非効率的であることに注意
してください.1つ目は三角形のセル配列を計算すると2倍速くなり、2つ目はまだ自己比較を計算しています。しかし、優れた並列化による時間の節約は、16 倍 (全員のマシンに MATLAB をインストールした場合は 72 倍) です。

余談
メモリの問題もあります。いくつかの eval を使用して、H の各列を H1、H2 などの名前でファイルに追加し、H iをクリアしました。残念ながら、保存は非常に遅いです...

4

3 に答える 3

3

する

compare(a,b) == compare(b,a)

と

compare(a,a) == 1

その場合は、ループを変更してください

for i=1:numel(list)
    for j=1:numel(list)
    ...
    end
end

に

for i=1:numel(list)
    for j= i+1 : numel(list)
    ...
    end
end

対称性と同一性の場合を扱います。これにより、計算時間が半分に短縮されます。

于 2010-05-20T13:25:33.523 に答える
1

2 番目の例は、Parallel Processing Toolbox で使用するために簡単にスライスできます。このツールボックスは、コードの反復を最大 8 つの異なるローカル プロセッサに分散します。コードをクラスターで実行する場合は、Distributed Computing Toolbox も必要です。

%# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data.

parfor i=1:k-1 %# this will run the loop in parallel with the parallel processing toolbox
    %# only make the necessary comparisons
    H{i+1:k,i} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false);

    %# if the above doesn't work, try this
    hSlice = cell(k,1);
    hSlice{i+1:k} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false);
    H{:,i} = hSlice;
end
于 2010-05-20T11:21:35.927 に答える
0

私の理解が正しければ、5000^2 の行列比較を実行する必要がありますか? 比較関数を並列化しようとするのではなく、問題が 5000^2 タスクで構成されていると考えるべきでしょうか? Matlab Parallel Compute Toolbox は、タスクベースの並列処理をサポートしています。残念ながら、PCT での私の経験は大規模な線形代数型の問題の並列化に関するものなので、それ以上のことは言えません。ドキュメントは間違いなくあなたをもっと助けるでしょう。

于 2010-05-20T09:44:00.543 に答える