4

n x n 行列 A、n 個の係数 k (n x 1) のセット、および行 (1 x n) と呼ばれる行列があります。私の目標は、A の i 番目の行から k の i 番目の係数で重み付けされた行を減算することです。3 つの質問があります。私が思いついた3つよりも良い方法はありますか?

% Define row & coefficients used in each method
k = (1:1000).';
row = 1:1000;

% Method 1 (matrix multiply) ~15 seconds
A = magic(1e3);
tic;
for z = 1:1e3
    A = A - k*row;
end
toc;
% Method 2 (for loop) ~11 seconds
B = magic(1e3);
tic;
for z = 1:1e3
    for cr = 1:1000
        B(cr,:) = B(cr,:) - k(cr)*row;
    end
end
toc;
% method 3 (bsxfun) ~ 4 seconds
C = magic(1e3);
tic;
for z = 1:1e3
    C = C - bsxfun(@times, k, row);
end
toc

isequal(A,B)
isequal(A,C)

アルゴリズムでこれらの行減算を行っていることに注意してください。このおもちゃのテスト ケースを作成するために、コードを少し単純化しましたが、計算の核心はまだ存在しています。また、混乱を避けるために、z を使用した for ループを使用して時間を大きくしています。

4

1 に答える 1

6

短い答え:コードのより高速なバージョンは次のとおりです:

tic;
for z = 1:1e3
    for cr = 1:1000
        B(:,cr) = B(:,cr) - k*row(cr);
    end
end
toc;

この質問に対する私の以前の回答をご覧になることをお勧めします。つまり、MATLAB は列ベースであるのに対し、ループは行で動作しました。これは、列がメモリ内で連続していることを意味します。元のループは行を反復していましたが、これは非効率的です。

私のコンピューターでの実行時間:

% A - k*row
Elapsed time is 4.370238 seconds.
% B(cr,:) = B(cr,:) - k(cr)*row;
Elapsed time is 9.537338 seconds.
% C = C - bsxfun(@times, k, row);
Elapsed time is 3.039836 seconds.
B(:,cr) = B(:,cr) - k*row(cr);
Elapsed time is 2.028186 seconds.

説明。最初のバージョンは行列の乗算ではなく、サイズが 1000 x 1000 の行列になる 2 つのベクトルの外積です。穴の計算は BLAS2 ランク 1 の更新です (A=alpha x y'+A は GER 関数です)。 . 最も可能性の高い問題は、MATLAB がそれを認識せず、コードを理解したとおりに実行することです。つまり、k*row を含むすべての操作を明示的に実行します。これはまさにこのソリューションの問題です。外積は、行列のサイズに等しいサイズの追加メモリを割り当てる必要があり、それ自体に時間がかかります。このことを考慮：

  • メモリ割り当て - MATLAB がメモリ割り当てを管理する方法がわからないため、これは多くのオーバーヘッドを意味する可能性があります。
  • ベクトル k の読み取り、行
  • 結果行列 (KR) の書き込み
  • KR を読み取って A から減算する
  • Aの読み書き

2 つの 1000*1000 行列は 16 MB です。これほど多くのキャッシュがあるとは思えません。これが、このバージョンが最適ではない理由であり、利用可能なメモリ帯域幅と CPU キャッシュ サイズによっては、実際には「メモリの非効率」ループよりも遅くなる可能性があります。

KR 行列を割り当てて値をメモリに明示的に格納する必要はありません。必要な積をループで計算できます。したがって、メモリ帯域幅の要件が実質的に半分になり、メモリ割り当てのオーバーヘッドがなくなります。

  • ベクトル k の読み取り、行
  • 読み書き A

1 つのベクトルがキャッシュに収まると仮定すると (1000*8 バイトはあまり多くありません)、メモリから k と行を 1 回だけ読み取ります。これで、列をループするアルゴリズムは完全に理にかなっています (これはおそらく BLAS がこの計算を実装する方法です)

  • k と行を読み取り、キャッシュに保持する
  • CPU へのフル メモリ帯域幅で A をストリームし、k*row の積を減算し、メモリにストリームして戻します。

次に、最終的な効率の考慮事項です。私のループ構造を取ります。すべての反復で、A を読み書きし、ベクトルを読み取ります。つまり、反復ごとに 16MB のデータが移動されます。1000 回の反復により、合計で 16 GB のデータが移動されます。結果の計算に 2 秒かかると、8 GB/秒の有効なメモリ帯域幅が得られます。私のシステムでは、2 つの CPU コアを使用すると 16GB/秒のストリーム帯域幅があり、1 つを使用すると約 11 ～ 12 GB/秒です。したがって、このシーケンシャル ループは 1 つのコアで 60 ～ 70% の効率で実行されます。これはMATLAB ループであることを考えると、悪くありません:)

また、少なくとも私のコンピューターでは、列ベースのループ バージョンは、Ak 行の実装よりも 2 倍高速(2 秒対 4.37 秒) であることに注意してください。これは、k行が実際に MATLAB によって明示的に実行および構築され、合計メモリ トラフィックがループ バージョンの 2 倍であることを強く示しています。したがって、パフォーマンスが 2 倍悪くなります。

編集対応する BLAS 関数を直接呼び出すことで、最初のアルゴリズムのようにそれを試みることができます。この FEX の貢献をご覧ください。BLAS および LAPACK 関数を MATLAB から直接呼び出すことができます。役に立つかも..

于 2012-09-23T18:26:48.523 に答える