CPU和GPU的SVD速度

Question

我正在测试svd,Matlab R2014a似乎没有CPUvs GPU加速.我正在使用一张GTX 460卡片和一张卡片Core 2 duo E8500.

这是我的代码:

%test SVD
n=10000;
%host
Mh= rand(n,1000);
tic
%[Uh,Sh,Vh]= svd(Mh);
svd(Mh);
toc
%device
Md = gpuArray.rand(n,1000);
tic
%[Ud,Sd,Vd]= svd(Md);
svd(Md);
toc

此外,运行时间与运行不同,但CPU和GPU版本大致相同.为什么没有加速？

这是一些测试

for i=1:10
    clear;
    m= 10000;
    n= 100;
    %host
    Mh= rand(m,n);
    tic
    [Uh,Sh,Vh]= svd(Mh);
    toc
    %device
    Md = gpuArray.rand(m,n);
    tic
    [Ud,Sd,Vd]= svd(Md);
    toc
end

>> test_gpu_svd
Elapsed time is 43.124130 seconds.
Elapsed time is 43.842277 seconds.
Elapsed time is 42.993283 seconds.
Elapsed time is 44.293410 seconds.
Elapsed time is 42.924541 seconds.
Elapsed time is 43.730343 seconds.
Elapsed time is 43.125938 seconds.
Elapsed time is 43.645095 seconds.
Elapsed time is 43.492129 seconds.
Elapsed time is 43.459277 seconds.
Elapsed time is 43.327012 seconds.
Elapsed time is 44.040959 seconds.
Elapsed time is 43.242291 seconds.
Elapsed time is 43.390881 seconds.
Elapsed time is 43.275379 seconds.
Elapsed time is 43.408705 seconds.
Elapsed time is 43.320387 seconds.
Elapsed time is 44.232156 seconds.
Elapsed time is 42.984002 seconds.
Elapsed time is 43.702430 seconds.


for i=1:10
    clear;
    m= 10000;
    n= 100;
    %host
    Mh= rand(m,n,'single');
    tic
    [Uh,Sh,Vh]= svd(Mh);
    toc
    %device
    Md = gpuArray.rand(m,n,'single');
    tic
    [Ud,Sd,Vd]= svd(Md);
    toc
end

>> test_gpu_svd
Elapsed time is 21.140301 seconds.
Elapsed time is 21.334361 seconds.
Elapsed time is 21.275991 seconds.
Elapsed time is 21.582602 seconds.
Elapsed time is 21.093408 seconds.
Elapsed time is 21.305413 seconds.
Elapsed time is 21.482931 seconds.
Elapsed time is 21.327842 seconds.
Elapsed time is 21.120969 seconds.
Elapsed time is 21.701752 seconds.
Elapsed time is 21.117268 seconds.
Elapsed time is 21.384318 seconds.
Elapsed time is 21.359225 seconds.
Elapsed time is 21.911570 seconds.
Elapsed time is 21.086259 seconds.
Elapsed time is 21.263040 seconds.
Elapsed time is 21.472175 seconds.
Elapsed time is 21.561370 seconds.
Elapsed time is 21.330314 seconds.
Elapsed time is 21.546260 seconds.

Answer 1

通常,SVD是一种难以进行小规模的常规操作.你可以在这里查看使用高端特斯拉卡,加速不是很令人印象深刻.

你有一个GTX460卡 - 费米架构.该卡针对游戏(单精度计算)而非HPC(双精度计算)进行了优化.单精度/双精度吞吐率为12.因此该卡具有873 GFLOPS SP/72 GFLOPS DP.请点击这里.

因此,如果Md数组使用双精度元素,那么对它的计算将相当慢.此外,在调用CPU例程时,很有可能会利用所有CPU内核,从而降低在GPU上运行例程的可能增益.另外,在GPU运行中,您需要花时间将缓冲区传输到设备.

根据Divakar的建议,您可以使用Md = single(Md)将数组转换为单精度并再次运行基准测试.您可以尝试使用更大的数据集大小来查看是否有更改.我不希望你的GPU上有这个例程.

更新1:

发布结果后,我看到DP/SP时间比为2.在CPU端,这是正常的,因为double在SSE寄存器中可以减少2倍的值.然而,GPU侧只有2的比率意味着gpu代码没有充分利用SM内核 - 因为理论比率为12.换句话说,我希望优化代码的SP性能要好得多,与DP相比.似乎情况并非如此.

Answer 2

正如VAndrei已经说过的那样,SVD是一种难以并行化的算法.

你的主要问题是矩阵的大小.随着基质尺寸的增加,SVD的性能迅速下降.因此,您的主要目标应该是减小矩阵的大小.这可以使用高斯正规方程(其基本上是最小二乘意义上的超定线性系统的减少)来实现.

这可以通过简单地将转置乘以矩阵来完成:

MhReduced = Mh' * Mh;

这会将矩阵缩小为cols*cols的大小(如果cols是Mh的列数).然后你就打电话[U,S,V] = svd(MhReduced);

注意:使用此方法可能会产生具有相反符号的奇异向量(如果您要比较这些方法,则非常重要).

如果你的matix条件良好,这应该没有问题.然而,在病态矩阵的情况下,该方法可能无法产生可用的结果,而由于SVD的鲁棒性,直接应用SVD仍然可以产生可用的结果.

这应该会极大地提高你的性能,至少在矩阵足够大的情况下.另一个优点是您可以使用更大的矩阵.您可能根本不需要使用GPU(因为任何一个矩阵都太大,以至于复制到GPU的成本太高,或者在缩小后矩阵太小以至于GPU的加速不够大).

另请注意,如果使用返回值,则会丢失大量性能.如果您只对SVD计算的性能感兴趣,请不要使用任何返回值.如果你只在"解向量"感兴趣,只得到V(和访问的最后一列)[~,~, V] = svd(Mh);.

编辑:

我看了你的示例代码,但我不确定它是什么,你在计算.我也意识到我很难理解我的所作所为A'*A,所以我将详细解释.

给定一个线性系统A*x=b,A表示具有m行和n列的系数矩阵,x表示解向量,b表示常量向量(均为m行),可以按如下方式计算解:

• 如果A是正方形(m=n): x = A^-1 * b,

• 如果A不是square(m!=n, m > n):

  A*x = b

  A'*A*x = A'*b

  x =(A'*A)^ - 1*A'*b

A" = (A'*A)^-1 * A'通常称为伪逆.然而,该计算确实会对矩阵的条件数产生负面影响.该问题的解决方案是使用奇异值分解(SVD).如果USV = svd(A)表示SVD的结果VS"U',S"则通过取S的非零元素的倒数形成伪逆,由此形成A" = VS"U'.

x = A"*b

然而,由于SVD相当昂贵,特别是对于大型矩阵.如果矩阵A条件良好并且不一定需要非常精确的结果(我们说的是1e-13或1e-14),(A'*A)^-1 * A则可以使用通过计算伪逆通道的更快的方法.

如果您的情况确实如此A*x=0,只需使用SVD并从V读取最后一列矢量,这就是解决方案.

如果您使用SVD不是为了解决线性系统而是为了U和S的结果(如您的示例所示),我不确定我发布的内容会对您有所帮助.

来源: 1,2,3

以下是一些示例代码供您测试.使用大型矩阵进行测试,您将看到使用(A'*A)^-1 * A'速度比替代方案快得多.

clear all

nbRows = 30000;
nbCols = 100;
% Matrix A
A = rand(nbRows,nbCols);

% Vector b
b = rand(nbRows,1);

% A*x=b

% Solve for x, using SVD
% [U,S,V]=svd(A,0);
% x= V*((U'*b)./diag(S))
tic
[U1,S1,V1]=svd(A,0);
x1= V1*((U1'*b)./diag(S1));
toc

tic
[U1,S1,V1]=svd(A,0);
x2 = V1*inv(S1)*U1'*b;
toc

% Solve for x, using manual pseudo-inverse
% A*x=b
% A'*A*x = A'*b
% x = (A'*A)^-1 * A'*b
tic
x3 = inv(A'*A) * A'*b;
toc

% Solve for x, let Matlab decide how (most likely SVD)
tic
x4 = A\b;
toc