5

我正在为来自 PDE 的特定离散化（具有已知的稀疏结构）的非常大的稀疏矩阵进行自适应矩阵向量乘法的 MATLAB 实现。

经过大量预处理后，我最终得到了许多不同的块（例如，大于 200），我想为其计算选定的条目。

预处理步骤之一是确定我要计算的每个块的（数量）条目，这使我几乎完美地衡量了每个块将花费的时间量（对于所有意图和目的，正交努力是每个条目都相同）。

感谢https://stackoverflow.com/a/9938666/2965879，我能够通过以相反的顺序对块进行排序来利用它，从而促使 MATLAB 首先从最大的块开始。

但是，每个块的条目数量差异很大，以至于直接运行 parfor 会受到条目数量最多的块的严重限制，即使它们被反向输入循环。

我的解决方案是串行执行最大的块（但在条目级别上并行化！），只要每个迭代的开销无关紧要，这很好。块不会变得太小。然后我用 parfor 完成其余的块。理想情况下，我会让 MATLAB 决定如何处理这个问题，但是由于嵌套的 parfor 循环失去了并行性，所以这不起作用。此外，将两个循环打包成一个（几乎）是不可能的。

我现在的问题是关于如何最好地确定串行和并行机制之间的截止值，同时考虑到我所拥有的关于条目数量的信息（对于不同的问题，有序条目的曲线形状可能会有所不同），如以及我可用的工人数量。

到目前为止，我一直在与标准 PCT 许可下可用的 12 名工作人员一起工作，但是自从我现在开始在集群上工作，确定这个截止值变得越来越重要（因为对于许多内核来说与并行循环相比，串行循环变得越来越昂贵，但类似地，拥有支撑其余部分的块甚至更昂贵）。

对于 12 个核心（分别是我正在使用的计算服务器的配置），我已经找到了一个合理的参数，即每个工作人员 100 个条目作为截止值，但是当核心数量不是时，这不起作用相对于块的数量（例如 64 对 200）来说已经很小了。

我试图缩小具有不同功率（例如 1/2、3/4）的核心数量，但这也不能始终如一地工作。接下来，我尝试将块分组并确定当条目大于每批平均值时的截止值，resp。他们离终点的批次数：

logical_sml = true(1,num_core); i = 0;
while all(logical_sml)
    i = i+1;
    m = mean(num_entr_asc(1:min(i*num_core,end))); % "asc" ~ ascending order 
    logical_sml = num_entr_asc(i*num_core+(1:num_core)) < i^(3/4)*m;  
        % if the small blocks were parallelised perfectly, i.e. all  
        % cores take the same time, the time would be proportional to  
        % i*m. To try to discount the different sizes (and imperfect  
        % parallelisation), we only scale with a power of i less than  
        % one to not end up with a few blocks which hold up the rest  
end  
num_block_big = num_block - (i+1)*num_core + sum(~logical_sml);

（注意：此代码不适用于num_entr_asc长度不是 的倍数的向量，但为了便于阅读num_core，我决定省略这些结构。）min(...,end)

我还省略了< max(...,...)for 组合这两个条件（即加上每个工人的最少条目），这是必要的，这样就不会太早发现截止。我也考虑过以某种方式使用方差，但到目前为止，所有尝试都不能令人满意。

如果有人对如何解决这个问题有一个好主意，我将不胜感激。
感谢您阅读这个很长的问题，
最好的问候，
阿克塞尔

附言。由于我的“亲爱的 stackoverflow”似乎被过滤了，让我感谢我已经在这里找到了我的问题的解决方案。

4

1 回答 1

1

我想出了一个有点令人满意的解决方案，所以如果有人感兴趣，我想我会分享它。对于如何改进/微调方法，我仍然很感激。

基本上，我认为唯一明智的方法是为并行循环构建一个（非常）基本的调度程序模型：

function c=est_cost_para(cost_blocks,cost_it,num_cores)
% Estimate cost of parallel computation

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   c: Estimated cost of parallel computation

num_blocks=numel(cost_blocks);
c=zeros(num_cores,1);

i=min(num_blocks,num_cores);
c(1:i)=cost_blocks(end-i+1:end)+cost_it;
while i<num_blocks
    i=i+1;
    [~,i_min]=min(c); % which core finished first; is fed with next block
    c(i_min)=c(i_min)+cost_blocks(end-i+1)+cost_it;
end

c=max(c);

end

空迭代的参数cost_it是许多不同副作用的粗略混合，可以想象将其分开：for/循环中空迭代的成本parfor（每个块也可能不同），以及启动时间分别 parfor-loop（可能更多）的数据传输。我将所有内容放在一起的主要原因是我不想估计/确定更精细的成本。

我使用上述例程通过以下方式确定截止：

% function i=cutoff_ser_para(cost_blocks,cost_it,num_cores)
% Determine cut-off between serial an parallel regime

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   i: Number of blocks to be calculated serially

num_blocks=numel(cost_blocks);
cost=zeros(num_blocks+1,2);

for i=0:num_blocks
    cost(i+1,1)=sum(cost_blocks(end-i+1:end))/num_cores + i*cost_it;
    cost(i+1,2)=est_cost_para(cost_blocks(1:end-i),cost_it,num_cores);
end

[~,i]=min(sum(cost,2));
i=i-1;

end

特别是，我不会夸大/更改est_cost_para假设（除了cost_it）最乐观的调度可能的值。我保持原样主要是因为我不知道什么会最有效。为保守起见（即避免向并行循环提供太大的块），当然可以添加一些百分比作为缓冲区，甚至使用大于 1 的幂来增加并行成本。

还要注意，它est_cost_para是用连续更少的块调用的（尽管我cost_blocks对两个例程都使用了变量名，一个是另一个的子集）。

与我冗长的问题中的方法相比，我看到了两个主要优点：

  1. 与使用单个公式相比，使用模拟调度程序可以更好地捕获数据（块数量及其成本）和内核数量之间相对复杂的依赖性。
  2. 通过计算串行/并行分布的所有可能组合的成本，然后取最小值，在从一侧读取数据时不会过早“卡住”（例如，相对于迄今为止的数据而言较大的跳跃，但与总数相比很小）。

当然，通过一直调用est_cost_para它的 while 循环，渐近复杂度会更高，但在我的情况下 ( num_blocks<500)，这绝对可以忽略不计。

最后，如果一个合适的值cost_it不能轻易呈现，可以尝试通过测量每个块的实际执行时间以及它的纯并行部分来计算它，然后尝试将结果数据拟合到成本预测并获得下一次例程调用的更新值cost_it（通过使用总成本和并行成本之间的差异或通过在拟合公式中插入零成本）。cost_it这应该有望“收敛”到对所讨论的问题最有用的价值。

于 2013-11-27T17:00:49.830 回答