1

我有大约 5,000 个矩阵，它们具有相同的行数和不同的列数（20 x ~200）。这些矩阵中的每一个都必须在动态规划算法中相互比较。

在这个问题中，我询问了如何快速进行比较，并得到了一个涉及 2D 卷积的出色答案。连续地，迭代地应用该方法，就像这样

list = who('data_matrix_prefix*')
H = cell(numel(list),numel(list));  
for i=1:numel(list)
    for j=1:numel(list)
        if i ~= j
            eval([ 'H{i,j} = compare(' char(list(i)) ',' char(list(j)) ');']);
        end
    end
end

对于数据的小子集来说速度很快（例如，对于 9 个矩阵，9*9 - 9 = 72 次调用在 ~1 秒内进行，870 次调用在 ~2.5 秒内）。
然而，对所有数据进行操作需要近 2500 万次调用。
我还尝试使用 deal() 来制作一个完全由数据中的下一个元素组成的单元格数组，因此我可以在单个循环中使用 cellfun() ：

# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data.
nextData = cell(k,1);
for i=1:k
    [nextData{:}] = deal(data{i});
    H{:,i} = cellfun(@compare,data,nextData,'UniformOutput',false);
end

不幸的是，这并没有真正更快，因为所有时间都在 compare() 中。这两个代码示例似乎都不适合并行化。我无法弄清楚如何对变量进行切片。
compare() 是完全向量化的；它专门使用矩阵乘法和 conv2()（我的印象是所有这些操作，包括 cellfun()，都应该在 MATLAB 中是多线程的？）。

有没有人看到（明确的）并行化解决方案或更好的问题向量化？

注意
我意识到我的两个例子都是低效的——如果它计算一个三角形单元阵列，第一个例子的速度会快两倍，而第二个例子仍然在计算自我比较。但是，良好的并行化所节省的时间更像是 16 倍（如果我在每个人的机器上安装 MATLAB，则为 72 倍）。

另外
还有内存问题。我使用了几个 eval 将 H 的每一列附加到一个文件中，名称如 H1、H2 等，然后清除 H i。不幸的是，保存速度很慢......

4

3 回答 3

3

做

compare(a,b) == compare(b,a)

和

compare(a,a) == 1

如果是这样，请更改您的循环

for i=1:numel(list)
    for j=1:numel(list)
    ...
    end
end

到

for i=1:numel(list)
    for j= i+1 : numel(list)
    ...
    end
end

并处理对称和恒等情况。这将使您的计算时间减少一半。

于 2010-05-20T13:25:33.523 回答
1

第二个示例可以很容易地与并行处理工具箱一起使用。此工具箱可在多达 8 个不同的本地处理器之间分配代码迭代。如果要在集群上运行代码，还需要分布式计算工具箱。

%# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data.

parfor i=1:k-1 %# this will run the loop in parallel with the parallel processing toolbox
    %# only make the necessary comparisons
    H{i+1:k,i} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false);

    %# if the above doesn't work, try this
    hSlice = cell(k,1);
    hSlice{i+1:k} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false);
    H{:,i} = hSlice;
end
于 2010-05-20T11:21:35.927 回答
0

如果我理解正确，您必须执行 5000^2 矩阵比较？而不是尝试并行化比较功能，也许您应该考虑您的问题由 5000^2 个任务组成？Matlab 并行计算工具箱支持基于任务的并行。不幸的是，我在 PCT 方面的经验是大型线性代数类型问题的并行化，所以我真的不能告诉你更多。文档无疑将为您提供更多帮助。

于 2010-05-20T09:44:00.543 回答