3

いくつかの行列演算を実行する必要がある 0 ～ 1 の値のベクトルがあります。それらはあまりスパースではありません (値の半分だけが 0 です) が、double ではなく論理変数としてそれらを保存すると、メモリが 8 倍節約されます。論理変数の場合は 1 バイト、倍精度浮動小数点の場合は 8 バイトです。

両方を double として使用するよりも、logical ベクトルと double 行列の行列乗算を行う方が遅くなりますか? 以下の予備結果を参照してください。

>> x = [0 1 0 1 0 1 0 1]; A = rand(numel(x)); xl = logical(x);
>> tic; for k = 1:10000; x * A * x'; end; toc %'
Elapsed time is 0.017682 seconds.
>> tic; for k = 1:10000; xl * A * xl'; end; toc %'
Elapsed time is 0.026810 seconds.
>> xs = sparse(x);
>> tic; for k = 1:10000; xs * A * xs'; end; toc %'
Elapsed time is 0.039566 seconds.

論理表現を使用すると、はるかに遅くなるようです (スパースはさらに遅くなります)。誰かが理由を説明できますか？タイプキャスティングの時間ですか？CPU/FPU命令セットの制限ですか？

編集:私のシステムは、Mac OS X 10.8.3、Intel Core i7 3.4 GHz の MATLAB R2012b です。

EDIT2: いくつかのコメントは、これは Mac OS X のみの問題であることを示しています。可能であれば、さまざまなアーキテクチャと OS からの結果をコンパイルしたいと思います。

EDIT3: 私の実際の問題では、可能なすべての可能なバイナリ ベクトルの長さの大部分を計算する必要がありますm。ここでmは、大きすぎ8 * m * 2^mてメモリに収まらない場合があります。

4

3 に答える 3

3

少し良いベンチマークを投稿することから始めます。より正確なタイミングを取得するために、Steve EddinsのTIMEIT関数を使用しています。

function [t,err] = test_mat_mult()
    %# data
    N = 4000; sparsity = 0.7;    %# adjust size and sparsity of data
    x = double(rand(1,N) > sparsity);
    xl = logical(x);
    xs = sparse(x);
    A = randn(N);

    %# functions
    f = cell(3,1);
    f{1} = @() mult_func(x,A);
    f{2} = @() mult_func(xl,A);
    f{3} = @() mult_func(xs,A);

    %# timeit
    t = cellfun(@timeit, f);

    %# check results
    v = cellfun(@feval, f, 'UniformOutput',true);
    err = max(abs(v-mean(v)));  %# maximum error
end

function v = mult_func(x,A)
    v = x * A * x';
end

私のマシン (WinXP 32 ビット、R2013a) での N=4000 およびスパース性=0.7 の結果は次のとおりです。

>> [t,err] = test_mat_mult
t =
     0.031212    %# double
     0.031970    %# logical
     0.071998    %# sparse
err =
   7.9581e-13

は平均doubleよりもわずかに優れているだけであることがわかりますが、予想どおり両方よりも遅いです (速度ではなく効率的なメモリ使用に重点が置かれているため)。logicalsparse

ここで、MATLAB はプラットフォーム用に最適化された BLAS 実装に依存して、全行列乗算を実行することに注意してください( を考えてくださいDGEMM)。一般的なケースでは、これには single/double 型のルーチンが含まれますが、ブール値は含まれないため、変換が発生し、logical.

Intel プロセッサでは、BLAS/LAPACK ルーチンはIntel MKL ライブラリによって提供されます。AMDについてはわかりませんが、同等のACMLを使用していると思います:

>> internal.matlab.language.versionPlugins.blas
ans =
Intel(R) Math Kernel Library Version 10.3.11 Product Build 20120606 for 32-bit applications

もちろん、まばらなケースは別の話です。(MATLAB がスパース演算の多くにSuiteSparseパッケージを使用していることは知っていますが、よくわかりません)。

于 2013-05-23T21:10:35.713 に答える
2

結果は、さまざまな表現に合理的に関連していると思います。

非スパース double 配列は、キャッシュに非常に簡単に収まる小さなデータ本体を表すのにシンプルで効率的です。

論理配列は、8 バイトではなく要素ごとに 1 バイトのみを使用するため、スペース効率が高くなりますが、要素が 8 つしかない場合は何も得られません。一方、ステップを追加して、それを使用して倍精度演算を行う前に、倍精度に変換する必要があります。

スパース配列は、配列の大部分がゼロの場合にスペースを節約するように設計された、より複雑な表現を使用します。特定のインデックスの要素がゼロであると判断するか、ゼロ以外の値を取得するには、さらに多くの操作が必要です。最小のキャッシュにも簡単に収まる 50% のゼロ以外の配列に使用するのは誤用です。ほとんどすべてがゼロである大きな配列のメモリとデータ転送コストを削減するのに最適です。スパース配列と通常配列のMatlabを参照してください

実際に 8 要素の配列を扱っている場合は、double の非スパース配列を使用する必要があります。実際の作業に大きな配列が含まれる場合は、同様のサイズでベンチマークする必要があります。また、テスト データのまばらさが実際のデータと一致していることを確認する必要があります。

于 2013-05-19T13:12:37.580 に答える
2

キャッシュに完全に収まり、疎すぎない (ベンチマークのように) データを操作している場合、追加の作業 (論理型と double の間の変換、またはスパース ストレージ スキームの使用など) を行って、メモリ フットプリントを削減しようとします。コードを遅くするだけです（お気づきのように）。

L1キャッシュからのデータアクセスは、ロードされたデータ要素ごとに十分な量の計算作業が行われている場合（例の場合のように）、「効果的に無料」になるほど十分に高速です。これが発生すると、実行速度はロード/ストア トラフィックではなく、計算によって制限されます。論理変数を使用すると、より多くの計算を行うことになり、ベンチマークが遅くなります。

実際に解決したい問題のワーキング セットの大きさは? プロセッサの L2 キャッシュよりも少なくとも大きくない場合は、通常の double マトリックスを使用する必要があります。論理変数の使用が有利になる正確なしきい値は、かなり大きくなる可能性がありますが、決定するにはある程度の実験が必要です。(これは、MATLAB が変換を正確に処理する方法にも依存します。乗算のタイリングの一部として変換を行う必要があります。MATLAB がそれを行わない場合、doubleどんなに大きくても、 を使用するよりも高速になることはありません。データセットは）です。

于 2013-05-19T14:31:33.010 に答える