performance - Cilk 的共享内存并行编程方法是 Elixir 吗？

Question

共享内存并行编程(尤其是多核)中的哪些挑战无法使用 Cilk 风格的解决方案解决或无法有效解决(即嵌套数据并行与每核工作窃取任务双端队列)？

Answer 1

我认为 Cilk 的模型是嵌套任务并行性(您可以使用它来实现数据并行性)。它很可爱，但是......

Cilk 不支持 SIMD 数据并行或流并行。

Cilk 似乎不能很好地处理任务的部分顺序，因为它只提供嵌套并行性。尝试对以下一组并行任务进行编码:A、B、C、D，具有顺序约束 A 在 B 之前，A 在 D 之前，C 在 D 之前。(这是嵌套任务并行无法实现的最小部分任务顺序的典型示例直接编码)。您失去了一些使用嵌套并行性实现它的并行性。并行是宝贵的，您不想浪费并行的机会。

它不处理(据我所知)跨线程边界的异常处理。如果你想构建一个非常大的、复杂的符号应用程序，这是必需的。如果您想进行推测性计算，它也很有用。

我也不认为 Cilk 可以处理计算粒度之间的大量交互(等待同步事件)，因为 Cilk 程序中的 AFAIK 只能具有与操作系统提供的线程一样多的实时并行计算。这是由于 Cilk 实现选择了生活在标准 C/C++ 编译器及其堆栈模型之上，在大多数工作站中，这些模型使用一个大堆栈每个线程模型。您可能会达到 10 或 100，但不会达到 10,000；这在处理非常大的图形时很重要。 [我不知道 Cilk 甚至允许计算粒度同步这一事实，但我看不出任何技术原因说明如果它放弃大堆栈模型它就不能同步]。

第二个含义是 Cilk 应用程序无法递归处理庞大的数据结构，因为无论您选择的堆栈大小都是有界的，并且在某些示例中您会用完堆栈。 (这不是 Cilk 的设计缺陷，只是其实现的缺陷)。这太糟糕了，因为大型事物是您需要并行性的地方之一。

有关替代方案，请参阅 PARLANSE , 它提供任意大量的计算粒度，具有工作窃取，但具有堆分配的粒度和激活记录。每个 grain 都有自己的上下文(因此可以实现大量交互的 grains 集，因为在需要等待事件时保存 grain 状态很简单。PARLANSE 同步原语包括 future 、信号量和关键函数结果(见下文)

PARLANSE 提供明确的“团队”(一组计算粒度)作为抽象，异常从函数传播到计算粒度的顶部(Java 将其定义为“未定义”，这是愚蠢的)，给团队父，作为异步中止异常(可在 try 子句中捕获)返回给所有其他团队子项，以允许其他子项进行清理。

因为某些操作(例如，异步中止异常)可以在任意时间发生，PARLANSE 提供了关键函数的概念，其结果保证以原子方式返回给调用者，因此函数要么确定返回结果，要么不返回结果，并且该函数可以在异步中止处理程序中安全地清理资源。

特殊的“偏序”团队允许对已知偏序的计算进行编码；如果您有大量这样的集合，我认为这比 Cilk 的嵌套并行性更有效。

(我们使用 PARLANSE 来实现 large-scale program analysis/transformation tools.。PARLANSE 就是为了支持这一点而发明的；我们需要并行性，因为我们处理的工件是巨大的，嗯，树和图，代表数百万行代码)。

(PARLANSE 也不支持流或 SIMD，但它们并没有超出该语言的范围。可以说可以将流和 SIMD 添加到 C 和 C++ 中，但这可能非常困难)。