使用iTerand努力的A-Priori估算来预测并行循环的运行时（给定的工人数量）

Question

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

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

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

谢谢 https://stackoverflow.com/a/9938666/2965879, ，我能够通过以相反的顺序订购块来利用此功能，从而使Matlab首先从最大的块开始。

但是，从块之间，条目的数量差异很大，以至于直接运行PARFOR受到条目数量最多的块的严重限制，即使它们被反向送入环路。

我的解决方案是串行执行最大的块（但在条目级别上平行！），只要iTerand的开销并不重要，它就可以了。块不会太小。然后，我与Parfor一起做的其余块。理想情况下，我会让Matlab决定如何处理此操作，但是由于嵌套的Parfor-Loop失去了并行性，因此这行不通。另外，将两个循环打包成一个循环是不可能的。

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

到目前为止，我一直在与标准PCT许可证可用的12名工人合作，但是由于我现在开始研究一个集群，因此确定这种临界值变得越来越重要（因为对于许多核心来说，与平行循环相比，串行循环变得越来越成本，但同样，拥有剩下的块甚至更加昂贵）。

对于12个核心（分别是我正在使用的计算服务器的配置），我弄清楚了每个工作人员100个条目的合理参数，但当当核心数量不超过与块数量有关（例如64 vs 200）。

我试图将具有不同功率的内核数（例如1/2，3/4）放气，但这也不始终如一。接下来，我尝试将块分组为批处理，并确定当条目大于每批平均值时的截止时间。他们远离尽头的批次数：

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(...,...) 为了结合这两种条件（即每个工人的最低条目），这是必要的，以使截止时间不会太早。我也以某种方式考虑了一些方差，但是到目前为止，所有尝试都不令人满意。

如果有人对如何解决这个问题有一个好主意，我将非常感谢。

Answer 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- 环（每个块也可能是不同的），以及启动时间resp。数据传输 parfor- 环（可能更多）。将所有内容汇总在一起的主要原因是，我不想估计/确定更精细的成本。

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

% 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 对于两个例程，一个是另一个子集）。

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

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

当然，通过调用渐近复杂性更高 est_cost_para 一直以来一直在循环，但就我而言num_blocks<500）这绝对可以忽略不计。

最后，如果一个体面的价值 cost_it 不容易出现，可以尝试通过测量每个块的实际执行时间以及其纯粹的平行部分来计算它 cost_it 对于例行程序的下一个呼叫（通过使用总成本和并行成本之间的差异或将零成本插入拟合公式）。希望这应该“汇聚”到最有用的价值 cost_it 对于所讨论的问题。