Cilk的共享内存并行编程方法是万灵丹吗？

Question

共享内存并行编程（特别是多核）中的哪些挑战无法用Cilk风格的解决方案解决或者无法有效地解决（即嵌套数据并行与每核心工作窃取任务deques）？

Answer 1

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

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

Cilk看起来似乎无法处理好部分任务，因为它只提供嵌套并行。尝试对以下一组并行任务进行编码：A，B，C，D带有排序约束A在B之前，A在D之前，C在D之前（这是嵌套任务并行不能完成的最小部分任务顺序的规范示例直接编码）。你失去了一些嵌套并行性的并行性。平行性是宝贵的，你不想浪费机会平行。

它不处理（AFAIK）跨线程边界的异常处理。 如果你想构建一个非常庞大，复杂的符号应用程序，这是必需的。 如果你想投机计算，这也很有用。

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

第二个含义是Cilk应用程序无法缓冲大型数据结构，因为您选择的任何大小堆栈都是有界限的，并且有一些示例可能会用完堆栈。 （这不是Cilk的设计缺陷，仅仅是它的实现）。这太糟糕了，因为巨大的东西是你想要并行的地方之一。

有关替代方法，请参阅PARLANSE，其中提供了 任意大量的计算谷物，其中包含工作窃取，但带有堆分配的谷物和激活记录。每个谷物都有自己的上下文（因此可以实现大量相互作用的谷物集合，因为当需要等待某个事件时，它可以直接保存谷物状态。PARLANSE同步原语包括期货，信号量和关键函数结果（见下文）

PARLANSE提供明确的“团队”（一组计算颗粒）作为抽象，例外传播出函数到计算颗粒的顶端（Java将其定义为“未定义”，这是愚蠢的）作为一个异步终止异常（在try子句中可捕获），允许其他孩子清理

因为某些动作（例如，异步终止异常）可以发生在任意次， PARLANSE提供关键函数的概念，其结果保证以原子方式返回给调用方，因此函数可以确实地返回结果，或者不会，并且该函数可以安全地清理异步中止处理程序中的资源。

特殊的“部分订单”团队允许对部分订单已知的计算进行编码;我认为如果你有大量的这样的话，这比Cilk的嵌套并行性更有效率。我们使用PARLANSE来实现large-scale program analysis/transformation tools.。PARLANSE是为了支持这一点而发明的;我们想要并行化是因为我们处理的工件是巨大的，树和图形，代表了数百万行代码）。 （PARLANSE不会做流或SIMD，但它们不在语言范围之外，人们可以争论地将流和SIMD添加到C和C++，但它可能很难）。