如何对涉及递归乘法和累加的循环进行矢量化？

Question

在 matlab 中，我有一个以下形式的循环：

a=1;
for (i = 1:N)
   a = a * b(i) + c(i);
end

这个循环可以向量化，或者部分展开吗？

Answer 1

对于每个长度为 4 的 b 和 c，当循环展开时，您将有 -

output = b1b2b3b4 + c1b2b3b4 + c2b3b4 + c3b4 + c4

因此，通用公式为：

output = b1b2b3...bN + c1b2b3..bN + c2b3..bN + c3b4..bN + ... cN-1bN + cN

b 的累积乘积可以用 cumprod 元素被翻转或 "reversed" 来计算。其余的都是关于与 c 元素相乘，这些元素移动了 1 位，然后包括来自累积乘积和 c 的剩余标量元素，最后将所有这些相加得到最终的标量输出。

所以，编码版本看起来像这样 -

cumb = cumprod(b,'reverse');
a = sum(cumb(2:end).*c(1:end-1)) + cumb(1) + c(end);

基准测试

让我们将问题中的循环方法与本文前面提出的向量化方法进行比较 post。

以下是作为函数的方法 -

function a = loopy(b,c)
N = numel(b);
a = 1;
for i = 1:N
   a = a * b(i) + c(i);
end
return;

function a = vectorized(b,c)
cumb = cumprod(b,'reverse');
a = sum(cumb(2:end).*c(1:end-1)) + cumb(1) + c(end);
return;

这是对这两种方法进行基准测试的代码 -

datasizes = 10.^(1:8);
Nd = numel(datasizes);

time_loopy = zeros(1,Nd);
time_vectorized = zeros(1,Nd);
for k1 = 1:numel(datasizes)
    N = datasizes(k1);
    b = rand(1,N);
    c = rand(1,N);

    func1 = @() loopy(b,c);
    func2 = @() vectorized(b,c);
    time_loopy(k1) = timeit(func1);
    time_vectorized(k1) = timeit(func2);
end

figure,
loglog(datasizes,time_loopy,'-rx'), hold on
loglog(datasizes,time_vectorized,'-b+'),    
set(gca,'xgrid','on'),set(gca,'ygrid','on'),
xlabel('Datasize (# elements)'), ylabel('Runtime (s)')
legend({'Loop','Vectorized'}),title('Runtime Plot')

figure,
semilogx(datasizes,time_loopy./time_vectorized,'-k.')
set(gca,'xgrid','on'),set(gca,'ygrid','on'),
xlabel('Datasize (# elements)'), ylabel('Speedup (x)')
legend({'Speedup with vectorized method over loopy one'}),title('Speedup Plot')

这是运行时和加速图 -

少量观察

阶段 #1：从开始数据大小到 1000 个元素，循环方法占上风，因为矢量化方法没有获得足够的元素，无法从一次性方法中获益。

阶段 #2：从 1000 个元素到 1000,0000 个元素，向量化方法似乎是更好的方法，因为它获得了足够的元素来处理。

第 3 阶段：对于更大的数据量情况，与使用循环方法仅使用标量值相比，使用矢量化方法存储和处理数百万个元素似乎需要内存带宽可能会回溯矢量化方法。

结论：如果性能是最重要的标准，则可以使用矢量化方法或保留基于数据大小的原始循环代码。

如何对涉及递归乘法和累加的循环进行矢量化？

How can a loop involving recursive multiplication and accumulation be vectorized?

parallel-processing

matlab

vectorization

基准测试