<blockquote>
<p><strong>About this answer</strong></p>
<p>This answer is Part II of the accepted answer <a href="https://stackoverflow.com/a/54032744/9059420">above</a>.</p>
</blockquote>
<hr/>
<h2>7号。Naive与Pool的Chunksize算法</h2>
<p>在详细讨论之前,请考虑下面的两个gif。对于不同长度的<code>iterable</code>范围,它们显示了两个比较的算法如何对传递的<code>iterable</code>进行分块(到那时它将是一个序列)以及生成的任务如何分布。工作线程的顺序是随机的,实际上每个工作线程的分布式任务数可能与此图像不同,这些图像适用于较宽场景中的轻型任务和/或任务。如前所述,这里也不包括间接费用。然而,对于在传输数据量可忽略的密集场景中的足够重的任务,实际计算得出的结果非常相似。</p>
<p><img src="https://user-images.githubusercontent.com/32203938/53185266-f337da80-35fe-11e9-9eb6-0b04f35a5263.gif" alt="cs_4_50"/></p>
<p><img src="https://user-images.githubusercontent.com/32203938/53185334-16628a00-35ff-11e9-8366-99fc27065b60.gif" alt="cs_200_250"/></p>
<p>如第5章所示。Pool's Chunksize Algorithm“</strong>”,使用Pool's Chunksize Algorithm,对于足够大的iterable,chunks的数量将稳定在<code>n_chunks == n_workers * 4</code>处,同时它使用朴素的方法在<code>n_chunks == n_workers</code>和<code>n_chunks == n_workers + 1</code>之间切换。对于应用的naive算法:因为<code>n_chunks % n_workers == 1</code>是<code>True</code>对于<code>n_chunks == n_workers + 1</code>,将创建一个新的节,其中只使用一个worker。</p>
<blockquote>
<p>Naive Chunksize-Algorithm:</p>
<p>You might think you created tasks in the same number of workers, but this will only be true for cases where there is no remainder for <code>len_iterable / n_workers</code>. If there <em>is</em> a remainder, there will be a new section with only one task for a single worker. At that point your computation will not be parallel anymore.</p>
</blockquote>
<p>下面的图与第5章中的图相似,但显示的是节数而不是块数。对于Pool的完整chunksize算法(<code>n_pool2</code>),<code>n_sections</code>将稳定在臭名昭著的硬编码因子<code>4</code>。对于naive算法,<code>n_sections</code>将在1和2之间交替。</p>
<p><a href="https://i.stack.imgur.com/aiIPx.png" rel="noreferrer"><img src="https://i.stack.imgur.com/aiIPx.png" alt="figure10"/></a></p>
<p>对于Pool的chunksize算法,通过前面提到的<strong>额外处理,在<code>n_chunks = n_workers * 4</code>处保持稳定,防止在此处创建新的节,并将<strong>空闲共享</strong>限制为一个工作线程足够长的时间。不仅如此,该算法还将不断缩小空闲份额的相对大小,从而使RDE值收敛到100%。</p>
<p>例如,<code>n_workers=4</code>的“足够长”就是<code>len_iterable=210</code>。对于等于或大于该值的iterable,空闲共享将限制为一个worker,这是最初由于chunksize算法中的<code>4</code>乘法而丢失的特性。</p>
<p><a href="https://i.stack.imgur.com/VpxaO.png" rel="noreferrer"><img src="https://i.stack.imgur.com/VpxaO.png" alt="figure11"/></a></p>
<p>naive chunksize算法也收敛到100%,但收敛速度较慢。会聚效应完全取决于这样一个事实:在有两个部分的情况下,尾部的相对部分会收缩。只有一个雇员的尾部被限制在x轴长度<code>n_workers - 1</code>,这是<code>len_iterable / n_workers</code>可能的最大余数。</p>
<blockquote>
<p>How do actual RDE values differ for the naive and Pool's chunksize-algorithm?</p>
</blockquote>
<p>下面是两张热图,显示了小于等于5000的所有iterable长度的RDE值,以及小于等于2小于等于100的所有工人的RDE值。
色阶从0.5到1(50%-100%)。你会注意到更多的黑暗区域(较低的RDE值)为天真的算法在左边的热图。相反,右边Pool的chunksize算法绘制了一幅更加阳光明媚的图片。</p>
<p><a href="https://i.stack.imgur.com/G6Jt8.png" rel="noreferrer"><img src="https://i.stack.imgur.com/G6Jt8.png" alt="figure12"/></a></p>
<p>左下角暗角与右上角亮角的对角线梯度,再次显示出对工人数量的依赖,即所谓的“长iterable”。</p>
<blockquote>
<p>How bad can it get with each algorithm?</p>
</blockquote>
<p>在Pool的chunksize算法中,81.25%的RDE<strong></p>
<p><a href="https://i.stack.imgur.com/hzUZc.png" rel="noreferrer"><img src="https://i.stack.imgur.com/hzUZc.png" alt="figure13"/></a></p>
<p>使用朴素的chunksize算法,情况会变得更糟。计算得出的最低RDE为50.72%。在这种情况下,几乎一半的计算时间只有一个工人在运行!所以,小心,骄傲的<a href="https://ark.intel.com/de/products/95830/Intel-Xeon-Phi-Processor-7290-16GB-1-50-GHz-72-core-" rel="noreferrer">Knights Landing</a>主人。;)</p>
<p><a href="https://i.stack.imgur.com/jGEa4.png" rel="noreferrer"><img src="https://i.stack.imgur.com/jGEa4.png" alt="figure14"/></a></p>
<hr/>
<h2>8个。真实性检查</h2>
<p>在前几章中,我们考虑了纯数学分布问题的一个简化模型,从使多处理首先成为一个棘手话题的细节中剥离出来。为了更好地理解分布模型(DM)<em>单独</em>有助于解释实际中观察到的工人利用率,我们现在来看看由<em>real</em>计算绘制的并行计划。</p>
<h2>设置</h2>
<p>下面的图都处理了一个简单的、cpu绑定的伪函数的并行执行,这个伪函数用不同的参数调用,这样我们就可以观察绘制的并行调度如何随输入值的变化而变化。此函数中的“工作”仅包含范围对象上的迭代。这已经足够让核心保持忙碌,因为我们传递了大量的数字。可选地,该函数接受一些taskel惟一的额外<code>data</code>,该额外^{。由于每个taskel包含的工作量都是完全相同的,因此我们仍然在处理一个密集的场景。</p>
<p>函数的修饰是一个包装器,它采用ns分辨率的时间戳(Python 3.7+)。时间戳用于计算taskel的时间跨度,因此可以绘制经验并行调度。</p>
<pre><code>@stamp_taskel
def busy_foo(i, it, data=None):
"""Dummy function for CPU-bound work."""
for _ in range(int(it)):
pass
return i, data
def stamp_taskel(func):
"""Decorator for taking timestamps on start and end of decorated
function execution.
"""
@wraps(func)
def wrapper(*args, **kwargs):
start_time = time_ns()
result = func(*args, **kwargs)
end_time = time_ns()
return (current_process().name, (start_time, end_time)), result
return wrapper
</code></pre>
<p>Pool的starmap方法也被修饰为只有starmap调用本身是计时的。”此调用的“开始”和“结束”确定生成的并行计划的x轴上的最小值和最大值。</p>
<p>我们将观察一台机器上四个工作进程上40个任务的计算,这些任务的规格如下:
Python 3.7.1、Ubuntu 18.04.2、英特尔酷睿™ i7-2600K CPU@3.40GHz×8</p>
<p>将改变的输入值是for循环中的迭代次数
(30k、30M、600M)和额外的发送数据大小(每个taskel、numpy ndarray:0 MiB、50 MiB)。</p>
<pre><code>...
N_WORKERS = 4
LEN_ITERABLE = 40
ITERATIONS = 30e3 # 30e6, 600e6
DATA_MiB = 0 # 50
iterable = [
# extra created data per taskel
(i, ITERATIONS, np.arange(int(DATA_MiB * 2**20 / 8))) # taskel args
for i in range(LEN_ITERABLE)
]
with Pool(N_WORKERS) as pool:
results = pool.starmap(busy_foo, iterable)
</code></pre>
<p>下面所示的运行是经过精心挑选的,它们具有相同的块顺序,因此与分布模型中的并行调度相比,您可以更好地发现差异,但不要忘记工作人员获得任务的顺序是不确定的。</p>
<h2>DM预测</h2>
<p>重申一下,分布模型“预测”了一个平行的时间表,就像我们在第6.2章中已经看到的那样:</p>
<p><a href="https://i.stack.imgur.com/oxKuf.png" rel="noreferrer"><img src="https://i.stack.imgur.com/oxKuf.png" alt="figure15"/></a></p>
<h2>第一次运行:每个taskel 3万次迭代和0 MiB数据</h2>
<p><a href="https://i.stack.imgur.com/gNqre.png" rel="noreferrer"><img src="https://i.stack.imgur.com/gNqre.png" alt="figure16"/></a></p>
<p>我们在这里的第一次运行非常短,任务非常“轻”。整个<code>pool.starmap()</code>调用总共只花了14.5毫秒。
您会注意到,与<strong>DM</strong>相反,空闲不限于尾部部分,而是在任务之间甚至在任务之间发生。这是因为我们真正的日程安排自然包括各种开销。这里的空闲意味着taskel的所有<em>外部</em>。可能<em>真实</em>空闲<em>在</em>期间,taskel没有捕获之前已经提到的内容。</p>
<p>你还可以看到,并不是所有的工人都能同时完成他们的任务。这是因为所有的工作线程都通过共享的<code>inqueue</code>进行传输,并且一次只能读取一个工作线程。这同样适用于<code>outqueue</code>。这可能会导致更大的不安,只要你传输非边际大小的数据,我们将看到稍后。</p>
<p>此外,您可以看到,尽管每个taskel包含相同的工作量,但实际测量的taskel时间跨度变化很大。分发给worker-3和worker-4的任务比前两个worker处理的任务需要更多的时间。对于这次运行,我怀疑这是由于<a href="https://en.wikipedia.org/wiki/Intel_Turbo_Boost" rel="noreferrer">turbo boost</a>此时worker-3/4的核心不再可用,所以他们以较低的时钟速率处理任务。</p>
<p>整个计算过程非常轻巧,硬件或操作系统引入的混沌因子会使PS</strong>急剧倾斜。计算是“风中之叶”,即使对于理论上合适的情况,<strong>DM</strong>预测也没有什么意义。</p>
<h2>第二次运行:每个任务3000万次迭代和0 MiB数据</h2>
<p><a href="https://i.stack.imgur.com/dg7gi.png" rel="noreferrer"><img src="https://i.stack.imgur.com/dg7gi.png" alt="figure17"/></a></p>
<p>将for循环中的迭代次数从30000次增加到3000万次,可以得到一个接近完美ma的真正并行调度与由<strong>DM</strong>提供的数据预测的结果一致,hurray!每个taskel的计算量现在已经足够大,可以在开始和中间忽略空闲部分,只让<strong>DM</strong>预测的大空闲部分可见。</p>
<h2>第三次运行:每任务3000万次迭代和50 MiB数据</h2>
<p><a href="https://i.stack.imgur.com/BkMCf.png" rel="noreferrer"><img src="https://i.stack.imgur.com/BkMCf.png" alt="figure18"/></a></p>
<p>保持30M的迭代,但是每个taskel来回发送50mib会再次扭曲图片。在这里排队效应是显而易见的。Worker-4需要比Worker-1等待第二个任务更长的时间。现在想象一下这个有70名工人的时间表吧!</p>
<p>如果任务在计算上非常轻巧,但是可以提供大量数据作为有效负载,那么单个共享队列的瓶颈可能会阻止向池中添加更多工作线程的任何额外好处,即使它们由物理核心支持。在这种情况下,工人-1可以完成它的第一个任务,并等待一个新的工作,甚至在工人-40已经得到它的第一个任务。</p>
<p>现在应该很明显了,为什么一个<code>Pool</code>中的计算时间并不总是随着工作人员的数量而减少。沿着<em>发送相对大量的数据可能会导致出现这样的情况:大部分时间都花在等待数据复制到一个工作者的地址空间,而一次只能给一个工作者供电。</p>
<h2>第4次运行:每个taskel有6亿次迭代和50 MiB数据</h2>
<p><a href="https://i.stack.imgur.com/ZrPR0.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ZrPR0.png" alt="figure19"/></a></p>
<p>在这里,我们再次发送50mib,但将迭代次数从30M增加到600M,从而使总计算时间从10s增加到152s。再次绘制的并行调度<em></em>,与预测的调度接近完美匹配,通过数据复制产生的开销被边缘化。</p>
<hr/>
<h2>9号。结论</h2>
<p>讨论的<code>4</code>乘法增加了调度灵活性,但也利用了taskel分布中的不均匀性。如果没有这种乘法运算,空闲共享将仅限于一个工人,即使是短期的iterable(对于密集场景下的<strong>DM</strong>)。Pool的chunksize算法需要输入的iterables具有一定的大小才能恢复这种特性。</p>
<p>正如这个答案所希望的那样,Pool的chunksize算法与naive方法相比,平均而言,至少在平均情况下,并且在不考虑长开销的情况下,可以获得更好的核心利用率。这里的naive算法的分布效率(DE)可以低至~51%,而Pool的chunksize算法的分布效率低至~81%。<strong>DE</strong>但是不包括IPC这样的并行化开销(PO)。第8章表明,对于具有边际化开销的稠密场景,<strong>DE</strong>仍然具有很强的预测能力。</p>
<p>尽管Pool的chunksize算法比naive方法获得了更高的DE<strong>DE<strong>,但它并没有为每个输入星座提供最优的taskel分布。</strong>而一个简单的静态chunking算法不能优化(包括开销)并行效率(PE),它不可能总是提供100%的相对分布效率(RDE),也就是说,与<code>chunksize=1</code>相同。一个简单的chunksize算法只包含基本的数学,并且可以以任何方式“切蛋糕”。</p>
<p>与Pool实现的“等大小分块”算法不同,“均匀大小分块”算法将为每个<code>len_iterable</code>/<code>n_workers</code>组合提供100%的RDE<strong>。均匀大小的分块算法在Pool的源代码中实现起来稍微复杂一些,但是可以在现有算法的基础上进行调整,只需将任务打包到外部即可(我将从这里链接,以防我在如何实现这一点上落下一个Q/A)。</p>