arrays - 计算数组平均值的高效并行调度算法

Question

我正在尝试在一台机器上使用多个线程来查找浮点值数组的平均值。我不关心数组的大小或内存限制(假设一个中等大小的数组，大到足以保证多个线程)。特别是，我正在寻找最高效的调度算法。在我看来，静态 block 方法是最有效的。

因此，鉴于我有 x 个机器核心，将数组分块为 array.size/x 值并让每个核心对各自数组 block 的结果求和似乎是合理的。然后，将每个核心的总和结果相加，最终结果是这个值除以数组元素的总数(注意:在数组元素的#不能被 x 整除的情况下，我知道优化以在线程中尽可能均匀地分布元素)。

数组显然会在线程之间共享，但由于不涉及写入，我不需要涉及任何锁定机制或担心同步问题。

我的问题是:对于这个问题，这实际上是最有效的方法吗？

相反，例如，考虑静态交错的方法。在这种情况下，如果我有四个核心(线程)，那么线程一将对数组元素 0、4、8、12 进行操作……而线程二将对元素 1、5、9、13 进行操作……这将看起来更糟，因为每个核心都会不断地出现缓存未命中，而静态 block 方法意味着每个核心都对成功值进行操作并利用数据局部性。我运行的一些测试似乎支持这一点。

那么，谁能指出比静态 block 更好的方法，或者确认这很可能是最好的方法？

编辑:
我正在使用 Java 和 Linux (Ubuntu)。我尽量不要过多考虑所涉及的语言/平台，而只是从涉及手动将工作负载分配给多个线程的调度角度抽象地看待问题。但我明白语言和平台是重要因素。

编辑 2:
这是一些具有不同数组大小( double )的计时(纳秒/1000)。
顺序计时使用单个 java 线程。其他人使用并行工作的所有可用 (4) 内核实现各自的调度策略。

1,000,000 个元素:
---顺序
5765
1642
1565
1485
1444
1511
1446
1448
1465
1443
---静态 block
15857
4571
1489
1529
1547
1496
1445
1415
1452
1661
---静态交错
9692
4578
3071
7204
5312
2298
4518
2427
1874
1900 年

50,000,000 个元素:
---顺序
73757
69280
70255
78510
74520
69001
69593
69586
69399
69665
---静态 block
62827
52705
55393
53843
57408
56276
56083
57366
57081
57787
---静态交错
179592
306106
239443
145630
171871
303050
233730
141827
162240
292421

Answer 1

您的系统似乎没有内存带宽来利用 4 线程解决这个问题。对元素进行浮点加法不足以让 CPU 以内存可以传输数据的速度忙碌……您的 4 个内核共享相同的内存 Controller /DRAM……并正在等待内存。如果您使用 2 个线程而不是 4 个线程，您可能会看到相同的加速。

正如您所说和确认的那样，交错是一个坏主意，为什么要浪费宝贵的内存带宽将数据带入核心，然后只使用其中的四分之一。如果幸运的话，线程在某种程度上同步运行，那么您将重用 2 级或 3 级缓存中的数据，但您仍会将数据带入 L1 缓存并且只使用一小部分。

更新:添加 5000 万个元素时，一个问题是精度损失，5000 万的对数基数 2 约为 26 位， double float 有 53 位有效位(52 位显式和 1 位隐式).最好的情况是所有元素都具有相似的指数(大小相似)。如果数组中的数字具有大范围的指数，情况会变得更糟，在最坏的情况下，范围很大并且它们按数量级的降序排列。可以通过对数组进行排序并按升序添加来提高最终平均值的精度。请参阅此 SO 问题以更深入地了解添加大量项目时的精度问题:Find the average within variable number of doubles .