Cilk、Cilk++或OpenMP

Question

我正在用Linux创建一个多线程应用程序。以下是场景：

假设我有一个类BloomFilter的x个实例，并且我有一些y GB的数据(大于可用内存)。我需要测试每个bloom filter实例中y GB数据的成员资格。很明显，并行编程将有助于加速任务，而且，因为我只读取数据，所以它可以在所有进程或线程之间共享。

现在我不知道该用Cilk，Cilk++还是OpenMP(哪个更好)。另外，我也不知道该选择多线程还是多处理

Answer 1

Cilk Plus是英特尔目前实施的Cilk。它们都是多线程环境，即在执行过程中会产生多个线程。

如果您不熟悉并行编程，那么OpenMP可能更适合您，因为它允许对已经开发的顺序代码进行更容易的并行化。你是否已经有了你的代码的顺序版本？

OpenMP使用杂注指示编译器必须并行运行代码的哪些部分。如果我没弄错你的问题，你可能需要这样的东西：

   #pragma omp parallel for firstprivate(array_of_bloom_filters)
   for i in DATA:
      check(i,array_of_bloom_filters);

在每个线程中复制不同bloom filter的实例，以避免线程之间共享数据时的争用。

更新：这篇论文实际上考虑了一个非常不平衡的应用程序，即不同的任务(分配在不同的线程上)可能会导致非常不同的工作负载。引用你的论文，你提到了“一个高度不平衡的任务图，它挑战调度、负载平衡、终止检测和任务粗化策略”。考虑到，为了平衡线程之间的计算，有必要减小任务大小，从而增加同步所花费的时间。换句话说，良好的负载平衡总是要付出代价的。你的问题的描述不是很详细，但在我看来，你的问题是相当平衡的。如果不是这样，那么使用Cilk，它的工作窃取方法可能是不平衡工作负载的最佳解决方案。

Answer 2

在这篇文章发表时，英特尔正在投入大量精力来提升Cilk(tm) Plus；最近，一些努力已经转向OpenMP 4.0。一般来说，比较OpenMP和Cilk(tm) Plus是很困难的。

如果不可能在线程之间均匀地分配工作，那么可以在OpenMP版本中设置调度(运行时)，然后在运行时尝试各种环境变量值，例如OMP_SCHEDULE=guided、OMP_SCHEDULE=dynamic,2或OMP_SCHEDULE=auto。这些是与Cilk(tm) Plus工作窃取工作方式最接近的OpenMP类比。英特尔MKL库中的某些稀疏矩阵函数实际上会先扫描作业，并确定分配给每个线程的数量，以便平衡工作。为了使这种方法有用，串行扫描和分配所花费的时间必须比并行工作所花费的时间低一个数量级。工作窃取，或动态调度，可能会通过将线程与缓存局部性固定在一起(例如通过OMP_PROC_BIND=close )来提升缓存局部性，从而失去OpenMP的大部分潜在优势。在NUMA架构上，糟糕的缓存局部性成为一个更大的问题，它可能会导致在远程内存访问上花费大量时间。OpenMP和Cilk(tm) Plus都有在串行和并行执行之间进行切换的功能。