← 揭开黑盒:理解系统的调查课堂

第二章 · 计算机选择的数学 / 第七单元 · 一起计算的条件

多几个计算者,为什么还要等?

如果一人做完需要 100 个时间单位,四个人是否只要 25?只有当全部工作都能平均分开,而且分工本身没有代价时,这个估计才成立。

预计用时:40 分钟。打开 等待的形状,先不看最终数值,预测图里的灰色等待会在哪里出现。

同一份任务,先画依赖

设想需要先准备输入,再把许多独立的行分给几个计算者,最后汇合。准备没有完成,后面的计算就无法开始。如果准备只能由一个人推进,增加人数不能让其他人提前获得尚未产生的输入。

模型把单人工作归一为 100。设必须依次完成的部分为 s,其余部分能完美平均分配给 p 个计算者,在暂不计协调时:

总时长 = s + (100 − s) / p

把 s 固定为 25,p 从 1 拖到 4。绿色计算段缩短,橙色准备段没有缩短。若继续增加人数,在这组固定假设下总时长只能趋近 25,理想加速上限为 4 倍。

这是一个关于固定工作量与串行比例的模型。若问题规模也随机器数量增加,就要重新定义比较任务;不能直接套同一个上限。

分工也会产生工作

发送输入、分配任务、协调状态、接收结果都可能花时间。页面让你假设“每增加一个人,额外花 h 个时间单位”,于是:

总时长 = s + (100 − s) / p + h × (p − 1)

s=25、p=4、h=2 时,得到 25 + 18.75 + 6 = 49.75,约为单人的 2.01 倍加速。橙色、绿色和紫色分别画出了这三项。

h 线性增长只是本例的假设。真实协调可能随消息大小、拓扑、共享资源和算法变化;页面没有测得某台机器的 h。

设计一次能反驳直觉的变化

先提出两个解释:“更多计算者总会更快”;“人数增加的收益可能被串行与协调成本抵消”。固定 s、h,只改 p。找到一组人数增加后变慢的条件。

接着把 h 设为零,比较曲线是否还会反向;再把 s 也设为零。这两步分别拿掉一种限制,能帮助你判断刚才的减速由哪个假设造成。

  1. 如果 s=100、h=0,增加人数会怎样?
    看答案

    参考:总时长保持 100,因为本模型没有可分出去的工作。这里的串行比例是固定任务中的限制,重写算法有时能改变它,但仅增加执行者数量不能。

并发与并行有什么不同

多个请求可以交错推进:甲等网络时,乙先处理数据。这是并发组织带来的机会。它不必意味着同一时刻有多个计算单元在算同一段程序。

并行计算需要真正可同时执行的工作和可用执行资源。网页里开启几个异步请求,不能单凭 async 就推出纯计算会变成多核执行。后面的 Web Worker 实验才会创建独立执行环境,并真实传递数据。

本节产物

为一个你熟悉的任务画依赖,例如处理一批照片或统计当天记录。标出可以独立处理的部分、必须等待的部分和需要汇合的位置。选一组 s、p、h,说明数值是估计还是测得;再指出哪些假设可能失效。

此时可在“能预测某种等待、知道模型缺少什么”处停下。下一节将看见另一种并行:让 同一条指令照顾更多数据。