我创建了一个中位数为 3 的标准快速排序实现，它对大量随机整数数组进行排序。我想至少达到1亿个元素，但最好是10亿个。为了提高速度，我正在尝试在 Cilk++ 中并行化算法。该算法使用双递归，我生成了 Cilk 任务来执行每个递归排序。
我的算法适用于最大为 10 000 000 的数组。如果没有 Cilk 关键字，我的顺序算法可以轻松处理 1 亿个元素，但是当我尝试使用 Cilk 时，程序崩溃到桌面。我现在想知道其中的原因。我是否生成太多 Cilk 任务的速度太快？
我使用的是 Windows 7 64 位、Intel++ 编译器和集成在 Visual Studio 2010 中的 Intel Parallel Studio XE 2013。该程序被编译为 32 位应用程序。存储随机数据的内存作为对 malloc 的单个调用进行分配，并检查指针。在中位数计算中，在计算中间元素时，也防止整数溢出。
这很可能是缓冲区溢出问题。
这是我的分区：
int pivotvalue = medianOf3(data, low, high);
// pivot is placed next to the last element
int left = low;
int right = high - 1;
while (left < right) {
while (data[left] < pivotvalue) {
left++;
if (left > high) {
break;
}
}
while (data[right] >= pivotvalue) {
right--;
if (right < low) {
break;
}
}
if (left < right) {
swap(data, left, right);
}
}
// restore pivot
swap(data, left, high - 1);
return left;
我不知道 Cilk 是如何工作的，但我记得需要在嵌入式平台上修复一个快速排序实现，这可能会使堆栈溢出递归。 解决方法是对较小的"一半"数据使用递归调用，并在函数内部处理较大的"一半"(即尾递归)。 排序(或反向排序)列表将始终触发溢出，因为调用图的深度等于列表中的元素数。
是否可以使用调试器找出导致崩溃的原因？ 你能在swap()的每个条目上将数据转储到日志文件中，然后看看崩溃前的函数调用是什么样子的吗？ 是否可以在每次调用时转储堆栈的大小？每个 Cilk任务是否都有自己的堆栈，该堆栈可能小于非 Cilk 版本中使用的堆栈？
您可以通过向具有堆栈地址的swap()添加参数来跟踪堆栈使用情况。 第一次调用和任何新的 Cilk 线程都使用 NULL。 每个递归调用都使用该参数(如果它不是 NULL)，或者使用其局部变量之一的地址来确定其堆栈的位置。 转储地址差异，或在全局中跟踪它，并且仅在超过以前的最大值时才报告它。
Intel Cilk Plus(cilk++ 是不支持的其他产品)的生成深度限制为 1024。 您完全有可能溢出您的 deque，这会导致崩溃。
决定在递归树中生成多深是一种平衡行为。 您希望有足够的生成来允许工作被盗，但使用过多会增加开销。 cilk_spawn很便宜，但不是免费的。 最好在快速排序中添加检查，如果要排序的元素数低于某个阈值，则不要生成递归调用。
cilk_for的好处之一是，它可以根据你正在运行的工人数量优化产卵深度。
- Barry Tannenbaum
Intel Cilk Plus Runtime Development
对两个子问题递归的 N 项进行快速排序具有(最坏情况)递归深度 O(N)。 通常的解决方法是"tomlogic"建议的解决方法：递归较小的子问题，迭代较大的子问题。 这会将递归深度减少到 O(lg N)。
此修复将延续到并行版本。 如果串行程序占用堆栈空间 S，则 Cilk Plus 版本最多占用堆栈空间 PS。 (此属性不适用于许多其他并行框架。 因此，生成较小的子问题并迭代较大的子问题应将总堆栈空间保持在 O(P lg N 内)。
我是《结构化并行编程》一书的作者之一，该书讨论了Cilk Plus和TBB中Quicksort的并行实现。 快速排序的示例(完全递归和半递归)可以从 http://parallelbook.com/student 免费下载。
Arch D. Robison
Intel Corporation