复杂对象的并行缩减

Question

通常（据我所知）归约运算会产生一个“数字”。这使得它们很容易处理，因为实际上没有任何内存开销。

但是，我正在做一些事情，我想组合一个不平凡的数据结构的实例。也就是说，如果

x

和

y

是某个类

C

的实例，我有一个操作将

x

和

y

组合到类

z

的另一个对象

C

中。让我们写

z=a+b

，其中

+

是我从成对的

C

到

C

的操作（数学上，

+:C x C -> C

）。

我已经有了

+

的高效实现，但是在对

C

的实例列表进行（并行）减少时，我正在努力控制内存分配。

是否有一些与此问题相关的标准方法或研究？本质上，我想尽可能多地重用内存而不重新分配。

Answer 1

通常，您设计一个累加器类

A

，其中包含操作

A += C

、

A += A

和

A -> C

来收集结果。

然后将您的列表分为 N 个块，其中 N >> num_cores。

初始任务通过为每个块生成

A

来完成大部分工作，然后您可以对

A

进行更标准的并行缩减，但由于它们是临时对象，因此您可以使用

a1 += a2; return a1

而不是

return a1 + a2

。

最后，您可以使用

A -> C

将减少的累加器转换为所需的输出。