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来实现大规模的程序分析/转换工具 .PARLANSE是为了支持这个而发明的;我们想要并行性,因为我们处理的工件很大,很好,树和图形代表了数百万行代码).

(PARLANSE也不做流或SIMD,但它们不在语言范围之外.可以说可以将流和SIMD添加到C和C++中,但可能很难).