Axe*_*xel 5 parallel-processing matlab load-balancing parfor
我正在研究自适应矩阵向量乘法的 MATLAB 实现，用于来自 PDE 的特定离散化（具有已知的稀疏结构）的非常大的稀疏矩阵。
经过大量预处理后，我最终得到了许多不同的块（比方说，大于 200），我想为它们计算选定的条目。
预处理步骤之一是确定我想要计算的每个块的（数量）条目，这使我几乎可以完美地衡量每个块将花费的时间（对于所有意图和目的，正交工作是每个条目相同）。
感谢/sf/answers/695706651/，我能够通过以相反的顺序对块进行排序来利用它，从而促使 MATLAB 首先从最大的块开始。
然而，条目的数量因块而异，以至于直接运行 parfor 受到条目数量最多的块的严重限制，即使它们被反向送入循环。
我的解决方案是串行执行最大的块（但在条目级别并行！），只要每个 iterand 的开销无关紧要，就可以了。块不会变得太小。然后我用 parfor 做其余的块。理想情况下，我会让 MATLAB 决定如何处理这个问题，但是由于嵌套的 parfor 循环失去了并行性，所以这不起作用。此外，将两个循环打包成一个（几乎）是不可能的。
我现在的问题是关于如何最好地确定串行和并行机制之间的这个截止点，考虑到我对条目数量的信息（不同问题的有序条目曲线的形状可能不同），如以及我可用的工人数量。
到目前为止，我一直在与标准 PCT 许可下的 12 个工作人员一起工作，但是自从我现在开始在一个集群上工作，确定这个截止变得越来越重要（因为对于许多内核来说，与并行循环相比，串行循环变得越来越昂贵，但类似地，拥有阻止其余部分的块的成本甚至更高）。
对于 12 个内核（对应于我正在使用的计算服务器的配置），我已经找到了一个合理的参数，即每个工人 100 个条目作为截止，但是当内核数不是相对于块的数量来说小了（例如 64 对 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(...,...)结合这两个条件（即每个工人的最少条目数），这是必要的，这样就不会太早找到截止点。我也考虑过以某种方式使用方差，但到目前为止，所有尝试都不尽如人意。
如果有人对如何解决这个问题有好主意，我将不胜感激。
感谢您阅读这个很长的问题，
最好的问候，
阿克塞尔
附言。由于我的“亲爱的 stackoverflow”似乎被过滤了，让我多次感谢我已经在这里找到了我的问题的解决方案。
我想出了一个比较令人满意的解决方案，所以如果有人感兴趣，我想我会分享它。我仍然感谢有关如何改进/微调该方法的评论。
基本上，我认为唯一明智的方法是为并行循环构建一个（非常）基本的调度程序模型：
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循环中空迭代的成本（每个块也可能不同），以及启动时间分别。循环数据的传输（可能还有更多）。我将所有内容放在一起的主要原因是我不想估计/确定更细粒度的成本。forparforparfor
我使用上面的例程通过以下方式确定截止：
% 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，但其中一个是另一个例程的子集）。
与我冗长的问题中的方法相比，我看到两个主要优点：
当然，通过est_cost_para始终使用 while 循环进行调用，渐近复杂度会更高，但在我的情况 ( num_blocks<500) 中，这绝对可以忽略不计。
最后，如果不容易出现一个合适的值cost_it，可以尝试通过测量每个块的实际执行时间以及它的纯并行部分来计算它，然后尝试将结果数据与成本相匹配预测并获取cost_it例程下一次调用的更新值（通过使用总成本和并行成本之间的差值或通过在拟合公式中插入零成本）。cost_it对于所讨论的问题，这应该有望“收敛”到最有用的值。