<h2>简短的回答</h2>
<p>Pool的chunksize算法是一种启发式算法。它为您试图填充到Pool方法中的所有可想象的问题场景提供了一个简单的解决方案。因此,它不能针对任何<em>特定的</em>场景进行优化。</p>
<p>该算法任意地将iterable划分为大约4倍于naive方法的块。更多的块意味着更多的开销,但是增加了调度的灵活性。这个答案将如何显示,这将导致平均更高的工人利用率,但是<em>没有</em>保证每种情况下更短的总体计算时间。</p>
<p>“很高兴知道”你可能会想,“但是知道这对我解决具体的多处理问题有什么帮助呢?”好吧,不是的。更诚实的简短回答是,“没有简短的答案”,“多处理是复杂的”和“取决于”。观察到的症状可能有不同的根源,即使是在类似的情况下。</p>
<p>这个答案试图为您提供一些基本概念,帮助您更清楚地了解Pool的调度黑盒。它还试图给你一些基本的工具来识别和避免潜在的悬崖,因为它们与块大小有关。</p>
<blockquote>
<p><strong>Table of Contents</strong></p>
<p>Part I</p>
<ol>
<li>Definitions</li>
<li>Parallelization Goals</li>
<li>Parallelization Scenarios</li>
<li>Risks of Chunksize > 1</li>
<li>Pool's Chunksize-Algorithm</li>
<li><p>Quantifying Algorithm Efficiency</p>
<p>6.1 Models</p>
<p>6.2 Parallel Schedule</p>
<p>6.3 Efficiencies</p>
<p>6.3.1 Absolute Distribution Efficiency (ADE)</p>
<p>6.3.2 Relative Distribution Efficiency (RDE)</p></li>
</ol>
<p><a href="https://stackoverflow.com/a/54813527/9059420">Part II</a></p>
<ol start="7">
<li>Naive vs. Pool's Chunksize-Algorithm</li>
<li>Reality Check</li>
<li>Conclusion</li>
</ol>
</blockquote>
<p>有必要先澄清一些重要的术语。</p>
<hr/>
<h2>一。定义</h2>
<p><br/>
<strong>块</strong></p>
<p>这里的块是池方法调用中指定的<code>iterable</code>参数的共享。如何计算chunksize以及它会产生什么样的影响,是这个答案的主题。</p>
<p><br/>
<strong>任务</strong></p>
<p>工作进程中任务的物理表示形式(以数据表示)如下图所示。</p>
<p><a href="https://i.stack.imgur.com/7nT9z.png" rel="noreferrer"><img src="https://i.stack.imgur.com/7nT9z.png" alt="figure0"/></a></p>
<p>此图显示了对<code>pool.map()</code>的调用示例,该调用沿着代码行显示,取自<code>multiprocessing.pool.worker</code>函数,在该函数中,从<code>inqueue</code>读取的任务将被解包。<code>worker</code>是池工作进程的<code>MainThread</code>中的基本主函数。pool方法中指定的<code>func</code>-参数将只与<code>apply_async</code>等单调用方法的<code>worker</code>-函数中的<code>func</code>-变量和<code>imap</code>与<code>chunksize=1</code>匹配。对于其他带有<code>chunksize</code>-参数的池方法,处理函数<code>func</code>将是映射器函数(<code>mapstar</code>或<code>starmapstar</code>)。此函数将用户指定的<code>func</code>-参数映射到iterable(-->;“map tasks”)传输块的每个元素上。所需时间将<strong>任务定义为<strong>工作单元。</p>
<p><br/>
<strong>Taskel</strong></p>
<p>虽然一个块的<em>整个</em>处理的单词“task”的用法与<code>multiprocessing.pool</code>中的代码相匹配,但没有迹象表明对用户指定的<code>func</code>使用一个
应将块的元素作为参数引用。为了避免命名冲突带来的混淆(考虑池的<code>maxtasksperchild</code>方法的<code>__init__</code>参数),这个答案将引用
任务中的单个工作单元称为taskel。</p>
<blockquote>
<p>A <strong>taskel</strong> (from <strong>task + el</strong>ement) is the smallest unit of work within a <strong>task</strong>.
It is the single execution of the function specified with the <code>func</code>-parameter of a <code>Pool</code>-method, called with arguments obtained from <strong>a single element</strong> of the transmitted <strong>chunk</strong>.
A <strong>task</strong> consists of <code>chunksize</code> <strong>taskels</strong>.</p>
</blockquote>
<p><br/>
<strong>并行化开销(PO)</strong></p>
<p><strong>PO</strong>由Python内部开销和进程间通信(IPC)开销组成。Python中的每个任务开销都附带打包和解包任务及其结果所需的代码。IPC开销包括必要的线程同步和不同地址空间之间的数据复制(需要两个复制步骤:父级->;队列->;子级)。IPC开销的大小取决于操作系统、硬件和数据大小,这使得对影响的概括变得困难。</p>
<hr/>
<h2>2。并行化目标</h2>
<p>当使用多处理时,我们的总体目标(显然)是最小化所有任务的总处理时间。为了实现这一总体目标,我们的技术目标需要优化硬件资源的利用。</p>
<p>实现技术目标的一些重要子目标是:</p>
<ul>
<li>最小化并行化开销(最著名的,但不是单独的:<a href="https://en.wikipedia.org/wiki/Inter-process_communication" rel="noreferrer">IPC</a>)</li>
<li>所有cpu核心的高利用率</li>
<li>限制内存使用以防止操作系统过度分页(<a href="https://en.wikipedia.org/wiki/Thrashing_(computer_science)" rel="noreferrer">trashing</a>)</li>
</ul>
<p>首先,这些任务需要足够的计算量(密集),以获得并行化所需的回报。PO的相关性随着每任务绝对计算时间的增加而降低。或者,换句话说,对于您的问题,每个任务的绝对计算时间<em>越大,减少PO的必要性就越小。如果每个taskel的计算将花费数小时,则IPC开销相比之下可以忽略不计。这里的主要关注点是防止在分配完所有任务后使工作进程空闲。保持所有核心加载意味着,我们尽可能地并行化。</p>
<hr/>
<h2>三。并行化场景</h2>
<blockquote>
<p>What factors determine an optimal chunksize argument to methods like multiprocessing.Pool.map()</p>
</blockquote>
<p>问题的主要因素是,在我们的单个任务中,有多少计算时间可以<em>变化</em>。要命名它,最佳块大小的选择取决于。。。</p>
<blockquote>
<p><strong>Coefficient of Variation</strong> (<a href="https://en.wikipedia.org/wiki/Coefficient_of_variation" rel="noreferrer">CV</a>) for computation times per taskel.</p>
</blockquote>
<p>从这种变化的程度来看,在一个尺度上有两种极端情况:</p>
<ol>
<li>所有任务都需要完全相同的计算时间。</li>
<li>任务可能需要几秒钟或几天才能完成。</li>
</ol>
<p>为了更好地记忆,我将这些场景称为:</p>
<ol>
<li><strong>密集场景</strong></li>
<li><strong>广泛的场景</strong></li>
</ol>
<p><br/></p>
<h2>密集场景</h2>
<p>在密集的场景中,最好一次分发所有任务,将必需的IPC和上下文切换保持在最低限度。这意味着我们只想创建尽可能多的块,尽可能多的工作进程。如上所述,PO的权重随着每个taskel计算时间的缩短而增加。</p>
<p>为了获得最大的吞吐量,我们还希望所有工作进程都处于忙碌状态,直到处理完所有任务(没有空闲的工作进程)。为了实现这个目标,分布的块应该大小相等或接近。</p>
<p><br/></p>
<h2>广阔的前景</h2>
<p>对于一个<strong>广泛的场景来说,最好的例子是一个优化问题,在这个问题中,结果要么快速收敛,要么计算可能需要数小时,甚至数天。通常,在这种情况下,无法预测任务将包含“轻任务”和“重任务”的混合,因此,在一个任务批中同时分发太多任务是不可取的。一次分配的任务比可能的要少,这意味着增加了调度的灵活性。这是需要在这里达到我们的子目标,所有核心的高利用率。</p>
<p>默认情况下,如果<code>Pool</code>方法完全针对密集场景进行优化,那么它们将越来越多地为靠近广泛场景的每个问题创建次优的计时。</p>
<hr/>
<h2>四。块大小风险1</h2>
<p>考虑一下这个简化的伪代码示例,它是一个<strong>广泛的场景</strong>-iterable,我们希望将其传递到pool方法中:</p>
<pre><code>good_luck_iterable = [60, 60, 86400, 60, 86400, 60, 60, 84600]
</code></pre>
<p>与实际值不同的是,我们假设所需的计算时间以秒为单位,为了简单起见,只有1分钟或1天。
我们假设池有四个工作进程(在四个核心上),并且<code>chunksize</code>设置为<code>2</code>。由于订单将被保留,发送给工人的数据块将是:</p>
<pre><code>[(60, 60), (86400, 60), (86400, 60), (60, 84600)]
</code></pre>
<p>因为我们有足够多的工人,并且计算时间足够长,我们可以说,每个工人进程首先都会得到一个块来工作。(快速完成任务不一定要这样)。此外,我们可以说,整个处理过程大约需要86400+60秒,因为这是这个人工场景中一个块的最高总计算时间,我们只分配一次块。</p>
<p>现在考虑这个iterable,它只有一个元素与以前的iterable相比,切换其位置:</p>
<pre><code>bad_luck_iterable = [60, 60, 86400, 86400, 60, 60, 60, 84600]
</code></pre>
<p>…以及相应的块:</p>
<pre><code>[(60, 60), (86400, 86400), (60, 60), (60, 84600)]
</code></pre>
<p>只可惜我们的iterable的排序几乎翻了一番(86400+86400)我们的总处理时间!得到恶意(8640086400)块的工人正在阻止任务中的第二个重任务分配给已经完成(60,60)块的空闲工人之一。显然,如果我们设置<code>chunksize=1</code>,我们就不会冒这样不愉快的后果的风险。</p>
<p>这是大块的风险。对于较大的块大小,我们用调度灵活性换取较少的开销,在上面这样的情况下,这是一个糟糕的交易。</p>
<p>我们将在第6章中看到什么。量化算法的效率</strong>,较大的块大小也可能导致对密集场景的次优结果</strong>。</p>
<hr/>
<h2>5个。池的块大小算法</h2>
<p>下面您将在源代码中找到算法的稍加修改的版本。如您所见,我切断了下半部分并将其包装成一个函数,用于外部计算<code>chunksize</code>参数。我还用<code>factor</code>参数替换了<code>4</code>,并外包了<code>len()</code>调用。</p>
<pre><code># mp_utils.py
def calc_chunksize(n_workers, len_iterable, factor=4):
"""Calculate chunksize argument for Pool-methods.
Resembles source-code within `multiprocessing.pool.Pool._map_async`.
"""
chunksize, extra = divmod(len_iterable, n_workers * factor)
if extra:
chunksize += 1
return chunksize
</code></pre>
<p>为了确保我们都在同一个页面上,下面是<code>divmod</code>要做的:</p>
<p><code>divmod(x, y)</code>是一个内置函数,返回<code>(x//y, x%y)</code>。
<code>x // y</code>是底除法,从<code>x / y</code>返回向下舍入的商,而
<code>x % y</code>是从<code>x / y</code>返回余数的模运算。
因此,例如<code>divmod(10, 3)</code>返回<code>(3, 1)</code>。</p>
<p>现在,当你看<code>chunksize, extra = divmod(len_iterable, n_workers * 4)</code>时,你会注意到<code>n_workers</code>这里是<code>x / y</code>中的除数<code>y</code>,并乘以<code>4</code>,而不需要以后通过<code>if extra: chunksize +=1</code>进行进一步的调整,会导致初始块大小<em>至少比原来小4倍(对于<code>len_iterable >= n_workers * 4</code>)。</p>
<p>要查看乘以<code>4</code>对中间块大小结果的影响,请考虑以下函数:</p>
<pre><code>def compare_chunksizes(len_iterable, n_workers=4):
"""Calculate naive chunksize, Pool's stage-1 chunksize and the chunksize
for Pool's complete algorithm. Return chunksizes and the real factors by
which naive chunksizes are bigger.
"""
cs_naive = len_iterable // n_workers or 1 # naive approach
cs_pool1 = len_iterable // (n_workers * 4) or 1 # incomplete pool algo.
cs_pool2 = calc_chunksize(n_workers, len_iterable)
real_factor_pool1 = cs_naive / cs_pool1
real_factor_pool2 = cs_naive / cs_pool2
return cs_naive, cs_pool1, cs_pool2, real_factor_pool1, real_factor_pool2
</code></pre>
<p>上面的函数计算原始块大小(<code>cs_naive</code>)和池的块大小算法的第一步块大小(<code>cs_pool1</code>),以及完整池算法的块大小(<code>cs_pool2</code>)。此外,它还计算实际因子</strong></em><code>rf_pool1 = cs_naive / cs_pool1</code>和<code>rf_pool2 = cs_naive / cs_pool2</code>,这些因子告诉我们原始计算的块大小比池的内部版本大多少倍。</p>
<p>下面是用这个函数的输出创建的两个图。左边的图只显示了<code>n_workers=4</code>的块大小,直到可输入的长度<code>500</code>。右图显示<code>rf_pool1</code>的值。对于iterable length<code>16</code>,实际因子变为<code>>=4</code>(对于<code>len_iterable >= n_workers * 4</code>),对于iterable length<code>28-31</code>,最大值为<code>7</code>。这与原来的因子有很大的偏差,算法收敛到更长的迭代次数这里的“Longer”是相对的,取决于指定的工人数。</p>
<p><a href="https://i.stack.imgur.com/DlDQa.png" rel="noreferrer"><img src="https://i.stack.imgur.com/DlDQa.png" alt="figure1"/></a></p>
<p>记住,chunksize<code>cs_pool1</code>仍然缺少<code>extra</code>调整,而完整算法中<code>cs_pool2</code>包含的<code>divmod</code>中的剩余部分。</p>
<p>算法继续:</p>
<pre><code>if extra:
chunksize += 1
</code></pre>
<p>现在,如果有<em>是</em>的余数(divmod操作的一个<code>extra</code>),那么将chunksize增加1显然不能解决每个任务。毕竟,如果是这样的话,就不会有余数了。</p>
<p>从下图中可以看出,“<strong>额外处理</strong>”的效果是,<code>rf_pool2</code>的<strong>实因子</strong>现在从</em><code>4</code>下面的<em>向<code>4</code>收敛,并且偏差稍微平滑一些。<code>n_workers=4</code>和<code>len_iterable=500</code>的标准差从<code>0.5233</code>的<code>rf_pool1</code>下降到<code>0.4115</code>的<code>rf_pool2</code>。</p>
<p><a href="https://i.stack.imgur.com/DKDzL.png" rel="noreferrer"><img src="https://i.stack.imgur.com/DKDzL.png" alt="figure2"/></a></p>
<p>最后,将<code>chunksize</code>增加1会产生这样的效果,即发送的最后一个任务的大小只有<code>len_iterable % chunksize or chunksize</code>。</p>
<p>更有趣的是d我们以后将如何看到,更重要的是,额外治疗的效果</strong>,但是可以观察到生成块的数量</strong>(<code>n_chunks</code>)。
对于足够长的iterable,Pool完成的chunksize算法(下图中的<code>n_pool2</code>)将把chunks的数量稳定在<code>n_chunks == n_workers * 4</code>。
相反,随着iterable长度的增长,naive算法(在初始burp之后)在<code>n_chunks == n_workers</code>和<code>n_chunks == n_workers + 1</code>之间保持交替。</p>
<p><a href="https://i.stack.imgur.com/zVjBq.png" rel="noreferrer"><img src="https://i.stack.imgur.com/zVjBq.png" alt="figure3"/></a></p>
<p>下面您将看到Pool和naive chunksize算法的两个增强信息函数。下一章将需要这些函数的输出。</p>
<pre><code># mp_utils.py
from collections import namedtuple
Chunkinfo = namedtuple(
'Chunkinfo', ['n_workers', 'len_iterable', 'n_chunks',
'chunksize', 'last_chunk']
)
def calc_chunksize_info(n_workers, len_iterable, factor=4):
"""Calculate chunksize numbers."""
chunksize, extra = divmod(len_iterable, n_workers * factor)
if extra:
chunksize += 1
# `+ (len_iterable % chunksize > 0)` exploits that `True == 1`
n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
# exploit `0 == False`
last_chunk = len_iterable % chunksize or chunksize
return Chunkinfo(
n_workers, len_iterable, n_chunks, chunksize, last_chunk
)
</code></pre>
<p>不要被<code>calc_naive_chunksize_info</code>可能出乎意料的外观所迷惑。来自<code>divmod</code>的<code>extra</code>不用于计算块大小。</p>
<pre><code>def calc_naive_chunksize_info(n_workers, len_iterable):
"""Calculate naive chunksize numbers."""
chunksize, extra = divmod(len_iterable, n_workers)
if chunksize == 0:
chunksize = 1
n_chunks = extra
last_chunk = chunksize
else:
n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
last_chunk = len_iterable % chunksize or chunksize
return Chunkinfo(
n_workers, len_iterable, n_chunks, chunksize, last_chunk
)
</code></pre>
<hr/>
<h2>6。量化算法效率</h2>
<p>现在,在我们看到<code>Pool</code>的chunksize算法的输出与naive算法的输出看起来有什么不同之后。。。</p>
<ul>
<li><strong>如何判断Pool的方法是否真的改善了某些东西?</strong></li>
<li><strong>这究竟是什么东西?</strong></li>
</ul>
<p>如前一章所示,对于更长的iterable(任务数更多),Pool的chunksize算法<em>大约</em>将iterable划分为比naive方法多4倍的<em>块。较小的数据块意味着更多的任务,而更多的任务意味着更多的并行化开销(PO)</strong>,这一成本必须与增加的调度灵活性相权衡(回忆一下“数据块大小风险”1“</strong>)。</p>
<p>由于相当明显的原因,Pool的基本chunksize算法不能将调度灵活性与我们的<strong>PO</strong>相比较。IPC开销取决于操作系统、硬件和数据大小。算法不知道我们在什么硬件上运行代码,也不知道taskel需要多长时间才能完成。它是一个启发式的,为所有可能的场景提供基本功能。这意味着它不能针对任何特定场景进行优化。如前所述,<strong>PO</strong>也变得越来越不关心每个taskel的计算时间(负相关)。</p>
<p>当您回忆起第2章中的并行化目标时,一个要点是:</p>
<ul>
<li>所有cpu核心的高利用率</li>
</ul>
<p>前面提到的<em>一些</em>,Pool的chunksize算法<em>可以</em>尝试改进的是最小化空闲的工作进程,分别是cpu核的利用率。</p>
<p>关于<code>multiprocessing.Pool</code>的一个重复的问题是,在您希望所有工作进程都很忙的情况下,人们会对未使用的核心/空闲的工作进程产生疑问。虽然这可能有许多原因,但在计算结束时空闲的工作进程是我们经常可以观察到的,即使在工作进程数不是块数的除数的情况下(等于每个任务的计算时间),也可以观察到这种情况。</p>
<p>现在的问题是:</p>
<blockquote>
<p>How can we practically translate our understanding of chunksizes into something which enables us to explain observed worker-utilization, or even compare the efficiency of different algorithms in that regard?</p>
</blockquote>
<hr/>
<h2>6.1模型</h2>
<p>为了在这里获得更深入的见解,我们需要一种并行计算的抽象形式,它将过于复杂的现实简化到可管理的复杂程度,同时在定义的边界内保持重要性。这种抽象称为<em>模型</em>。这种“<strong>并行化模型”(PM)</strong>的实现会生成工作映射元数据(时间戳),如果要收集数据,则实际计算也会这样。模型生成的元数据允许在特定约束下预测并行计算的度量。</p>
<p><a href="https://i.stack.imgur.com/4gjoC.png" rel="noreferrer"><img src="https://i.stack.imgur.com/4gjoC.png" alt="figure4"/></a></p>
<p>这里定义的<strong>PM</strong>中的两个子模型之一是<strong>分布模型删除(DM)</strong>。DM</strong>解释了当不考虑除相应的chunksize算法、工人数量、输入iterable(任务数量)及其计算持续时间以外的其他因素时,原子工作单元(任务)如何分布在并行工人和时间上。这意味着任何形式的开销都不包括在内。</p>
<p>为了获得一个完整的<strong>PM</strong>,<strong>DM</strong>被扩展为一个<strong>开销模型(OM)</strong>,表示各种形式的<strong>并行开销(PO)</strong>。这样的模型需要为每个节点分别进行校准(硬件和操作系统依赖)。在a<strong>OM</strong>中表示多少形式的开销是开放的,因此可以存在具有不同复杂度的多个<strong>OMs</strong>。实现的<strong>OM</strong>所需的精度级别由特定计算的<strong>PO</strong>的总权重确定。较短的任务会导致较高的<strong>PO</strong>权重,如果我们试图预测并行化效率(PE),则反过来需要更精确的<strong>OM</strong>。</p>
<hr/>
<h2>6.2平行进度表(PS)</h2>
<p>并行调度是并行计算的二维表示,其中x轴表示时间,y轴表示并行工作者池。工人的数量和总的计算时间标志着矩形的延伸,在矩形中绘制较小的矩形。这些较小的矩形表示原子工作单元(taskel)。</p>
<p>在下面,您可以看到用<strong>密集场景的池块大小算法的<strong>DM</strong>中的数据绘制的<strong>PS</strong>的可视化效果。</p>
<p><a href="https://i.stack.imgur.com/zgfRF.png" rel="noreferrer"><img src="https://i.stack.imgur.com/zgfRF.png" alt="figure5"/></a></p>
<ul>
<li>x轴被分割成相等的时间单位,其中每个单位代表taskel所需的计算时间。</li>
<li>y轴分为池使用的工作进程数。</li>
<li>此处的taskel显示为最小的青色矩形,放入匿名工作进程的时间线(时间表)中。</li>
<li>任务是工作时间线中的一个或多个任务,它们以相同的色调连续亮显。</li>
<li>空转时间单位用红色的瓷砖表示。</li>
<li>并行调度被分成几个部分。最后一段是尾部。</li>
</ul>
<p>组成部分的名称如下图所示。</p>
<p><a href="https://i.stack.imgur.com/QsIE9.png" rel="noreferrer"><img src="https://i.stack.imgur.com/QsIE9.png" alt="figure6"/></a></p>
<p>在一个完整的<strong>PM</strong>中,包括一个<strong>OM</strong>,空闲共享不限于尾部,还包括任务之间甚至任务之间的空间。</p>
<hr/>
<h2>6.3效率</h2>
<blockquote>
<p><strong>Note:</strong></p>
<p>Since earlier versions of this answer, "Parallelization Efficiency (PE)" has been renamed to "Distribution Efficiency (DE)".
<strong>PE</strong> now refers to overhead-including efficiency.</p>
</blockquote>
<p>上面介绍的模型可以量化工人利用率。我们可以区分:</p>
<ul>
<li><strong>分配效率(DE)</strong>-借助于<strong>DM</strong>计算(或针对<strong>密集场景的简化方法)。</li>
<li><strong>并行化效率(PE)</strong>-通过校准的<strong>PM(预测)计算,或根据实际计算的元数据计算。</li>
</ul>
<p>需要注意的是,对于给定的并行化问题,计算效率<strong><em>不会自动与<em>更快的</em>总体计算相关。在此上下文中,工作线程利用率仅区分具有已启动但尚未完成的任务的工作线程和不具有此类“打开”任务的工作线程。这就是说,任务的时间跨度在</em>期间可能出现的空闲<em>是<em>而不是</em>注册的。</p>
<p>所有上述效率基本上都是通过计算除法的商来获得的。<strong>DE</strong>与<st之间的差异蓉>体育</strong>伴随着忙碌的分享
占用整个并行调度的一小部分,用于开销扩展<strong>PM</strong>。</p>
<p>这个答案将进一步讨论一个简单的方法来计算密集场景的DE。这足以比较不同的块大小算法,因为。。。</p>
<ol>
<li>。。。<strong>DM</strong>是<strong>PM</strong>的一部分,随着所使用的块大小算法的不同而变化。</li>
<li>。。。每个taskel的计算持续时间相等的密集场景描述了一种“稳定状态”,这些时间跨度从方程中消失。任何其他场景都会导致随机结果,因为任务的顺序很重要。</li>
</ol>
<hr/>
<h2>6.3.1绝对分配效率(ADE)</h2>
<p>这种基本效率通常可以通过将繁忙份额除以并行调度的全部潜力来计算:</p>
<blockquote>
<p><strong>Absolute Distribution Efficiency (ADE)</strong> = <strong>Busy Share</strong> / <strong>Parallel Schedule</strong></p>
</blockquote>
<p>对于密集场景,简化的计算代码如下:</p>
<pre><code># mp_utils.py
def calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
"""Calculate Absolute Distribution Efficiency (ADE).
`len_iterable` is not used, but contained to keep a consistent signature
with `calc_rde`.
"""
if n_workers == 1:
return 1
potential = (
((n_chunks // n_workers + (n_chunks % n_workers > 1)) * chunksize)
+ (n_chunks % n_workers == 1) * last_chunk
) * n_workers
n_full_chunks = n_chunks - (chunksize > last_chunk)
taskels_in_regular_chunks = n_full_chunks * chunksize
real = taskels_in_regular_chunks + (chunksize > last_chunk) * last_chunk
ade = real / potential
return ade
</code></pre>
<p>如果没有空闲共享,则繁忙共享将等于并行调度,因此我们得到100%的ADE。在我们的简化模型中,这是一个场景,在处理所有任务所需的整个时间内,所有可用的进程都将处于忙碌状态。换句话说,整个工作可以有效地并行化到100%。</p>
<p>但是,为什么我在这里一直把<strong>PE</strong>称为<em>绝对</em><strong>PE</strong>?</p>
<p>为了理解这一点,我们必须考虑一个可能的chunksize(cs)情况,以确保最大的调度灵活性(同时,也可以有高地人数)。巧合?)以下内容:</p>
<blockquote>
<p>___________________________________<strong>~ ONE ~</strong>___________________________________</p>
</blockquote>
<p>例如,如果我们有四个工作进程和37个任务,那么即使使用<code>chunksize=1</code>也会有空闲的工作进程,因为<code>n_workers=4</code>不是37的除数。除以37/4的余数是1。剩下的这一个任务将由一个单独的工人处理,而剩下的三个则处于空闲状态。</p>
<p>同样,还有一个空闲的工人,有39个任务,你可以看到下面的图片。</p>
<p><a href="https://i.stack.imgur.com/Ysu7Y.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Ysu7Y.png" alt="figure7"/></a></p>
<p>当您比较<code>chunksize=1</code>的上部<strong>并行计划</strong>与<code>chunksize=3</code>的下部版本时,您会注意到上部<strong>并行计划</strong>较小,x轴上的时间线较短。现在应该很明显,块大小意外地变大也会导致整体计算时间的增加,即使对于密集场景也是如此。</p>
<blockquote>
<p>But why not just use the length of the x-axis for efficiency calculations?</p>
</blockquote>
<p>因为此模型中不包含开销。这两种块大小都不同,因此x轴并不是真正直接可比的。开销仍然会导致更长的总计算时间,如下图中案例2所示。</p>
<p><a href="https://i.stack.imgur.com/EzZaX.png" rel="noreferrer"><img src="https://i.stack.imgur.com/EzZaX.png" alt="figure8"/></a></p>
<hr/>
<h2>6.3.2相对分配效率(RDE)</h2>
<p>如果chunksize设置为1时,taskels的<em>更好的</em>分布是可能的,则<strong>ADE</strong>值不包含该信息。<em>更好的</em>仍然意味着空闲份额更小。</p>
<p>为了得到一个为可能的最大值而调整的<strong>DE</strong>值,我们必须将考虑的<strong>ADE</strong>除以为<code>chunksize=1</code>而得到的<strong>ADE</strong>。</p>
<blockquote>
<p><strong>Relative Distribution Efficiency (RDE)</strong> = <strong>ADE_cs_x</strong> / <strong>ADE_cs_1</strong></p>
</blockquote>
<p>下面是代码中的外观:</p>
<pre><code># mp_utils.py
def calc_rde(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
"""Calculate Relative Distribution Efficiency (RDE)."""
ade_cs1 = calc_ade(
n_workers, len_iterable, n_chunks=len_iterable,
chunksize=1, last_chunk=1
)
ade = calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk)
rde = ade / ade_cs1
return rde
</code></pre>
<p><strong>RDE</strong>,这里如何定义,本质上是一个关于并行调度尾部的故事。<strong>RDE</strong>受尾部包含的最大有效块大小的影响。(此尾部可以是x轴长度<code>chunksize</code>或<code>last_chunk</code>。)
其结果是,<strong>RDE</strong>自然收敛到100%(甚至)对于各种“尾部外观”,如下图。</p>
<p><a href="https://i.stack.imgur.com/3rKsK.png" rel="noreferrer"><img src="https://i.stack.imgur.com/3rKsK.png" alt="figure9"/></a></p>
<blockquote>
<p>A low <strong>RDE</strong> ...</p>
<ul>
<li>is a strong hint for optimization potential.</li>
<li>naturally gets less likely for longer iterables, because the relative tail-portion of the overall <strong>Parallel Schedule</strong> shrinks.</li>
</ul>
</blockquote>
<hr/>
<p>找到这个答案的第二部分。</p>