这是一篇关于在管道中调度工人以最小化总处理时间的文章,以及这种调度与托马斯·杰斐逊之间的意外联系。
- 背景与动机:制造中的装配线和 CPU 中的指令流水线提供了一种并行形式,通过将任务分解为阶段,无需额外成本即可获得并行性。将此技术应用于软件,可编写纯顺序程序并利用并行硬件。文中讨论了在各阶段之间分配 CPU/核心的最佳方式,旨在开发测试概念的库,并创建使用这些概念的编程语言。
- 灵感与先前工作:流水线在制造(如福特的汽车生产线)和 CPU 处理指令中取得巨大成功,这启发了在软件中应用流水线。相关的软件流水线并行示例包括数据流式语言、LMAX Disruptor 模式和数据库引擎等。作者受这些启发开始思考软件中的流水线,并在之前的帖子中有所探索,本文将采取更全局的方法。
- 整体架构:系统由管道、工人和调度器三部分组成。调度器监控管道,根据输入队列长度和平均服务时间计算工人的分配配置。工人按调度器指示处理输入批次并报告结果。管道由源、多个阶段和汇组成,源提供输入,汇处理输出,中间阶段进行有趣的处理。
- 原型实现:代码大部分是连接组件的管道工作,重点是工人完成后调度器如何确定下一步动作。通过生成所有可能的工人分配配置,计算每个配置的得分并选择得分最低的配置来分配工人。还实现了相关的辅助函数,如计算得分、合并地图等。
- 运行原型:在 REPL 中给出了多个示例,展示了如何根据不同的输入队列长度和已完成阶段情况,分配工人以最小化总处理时间。
- 与托马斯·杰斐逊的意外联系:作者提出的调度想法让朋友联想到托马斯·杰斐逊的议会席位分配方法,两者在原理上有相似之处,通过计算“得分”(输入队列长度乘以平均服务时间)来分配资源。但在具体例子中,两种方法存在细微差异。
- 结论与未来工作:展示了在管道中弹性扩展单个阶段的 CPU/核心数量的策略,若系统负载变化可重新平衡核心以维持吞吐量或减少负载时将核心用于其他系统部分。还指出当前实现使用简单并发队列连接阶段时,扩展阶段会破坏输出的确定性,可使用 Disruptors 解决。作者收集了其他待办事项并欢迎感兴趣的人联系。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。