3

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

4

1 回答 1

6

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

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

Cilk 似乎不能很好地处理任务的部分顺序，因为它只提供嵌套并行性。尝试编写以下并行任务集：A,B,C,D 具有排序约束 A 在 B 之前，A 在 D 之前，C 在 D 之前。（这是嵌套任务并行性不能的最小部分任务顺序的规范示例直接编码）。你失去了一些用嵌套并行实现这个的并行性。并行是宝贵的，你不想浪费并行的机会。

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

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

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

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

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

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

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

（我们使用 PARLANSE 来实现大规模的程序分析/转换工具。PARLANSE 是为了支持这一点而发明的；我们需要并行性，因为我们处理的工件是巨大的树和图，代表数百万行代码）。

（PARLANSE 也不做流或 SIMD，但它们并没有超出语言的范围。可以说，可以将流和 SIMD 添加到 C 和 C++，但它可能非常困难）。

于 2010-10-20T23:47:25.590 回答