如何在Matlab中将基数排序串行代码转换为并行代码

Question

我对并行编程很感兴趣。我写了一个串行基数排序算法。现在我想把它转换成一个并行算法。为了将其转换为并行，我可以对其应用什么方法？当我尝试应用parfor而不是for时，我得到了错误："‘C’的有效索引在PARFOR循环中受到限制。"如何克服这一问题？

这是我写的代码：

function array = radixSort(array)
    maxx = max(array);
    base = 1;
while maxx/base > 0
    array = counting_sort(array,base);
    base = base * 10;
end
    function W = counting_sort(array,base)
        X = zeros(1,11);
        W = zeros(1,numel(array));
        for j = 1:numel(array)
            X(rem(floor(array(j)/base),10)+1) = X(rem(floor(array(j)/base),10)+1) + 1;
        end
        for i = 2:11
            X(i) = X(i) + X(i-1);
        end
        for j = numel(array):-1:1
            W(X(rem(floor(array(j)/base),10)+1)) = array(j);
            X(rem(floor(array(j)/base),10)+1) = X(rem(floor(array(j)/base),10)+1) - 1;
        end
    end
end

Answer 1

使用parfor时，应了解变量的分类。对于切片变量C，迭代i可以仅访问C(i)（简化）。在您的情况下，循环的迭代之间存在依赖关系，其中一个迭代读取前一个迭代中的数据。这使得parfor成为不可能。

据我所知，使用并行计算工具箱对代码进行并行化不是正确的选择。假设你固定了可变索引，你可能会发现代码运行得更慢。这通常是在进行简单计算时，parfor的开销会浪费比您可能节省的时间更多的时间。

要提高代码的性能，请查看矢量化或适当的内置函数。

代替

for i = 2:11
    X(i) = X(i) + X(i-1);
end

用途：

X=cumsum(X);