cilk_for 通过 std::set 缺少运算符-() 进行并行化的错误

Question

我试图使用cilk_for来迭代集合。 事实证明，它没有为 set 定义运算符 (..(。 Cilk_for教程解释了原因，但没有提供任何示例来处理这种情况。 他们说应该提供以下内容： 但我不确定在哪里以及如何放置值：

链接在这里

difference_type operator-(termination_type, variable_type); // where to use this?
//my example
auto func = std::bind (my_functor, std::placeholders::_1);  
std::set<vertex_id> vertex_set;
// fill the vertex_set with some vertex ids
cilk_for (auto it = vertex_set.begin(); it!=vertex_set.end(); ++it) {
   func(*it) 
}

我如何以及在何处为 cilk 编译器提供运算符 (..( 来处理这个问题？

variable_type是set::iterator，差异类型是difference_type (ptrdiff_t)但是根据他们的例子，termination_type是什么？

Answer 1

问题不在于终止表达式，它 ！= vertex_set.end((，这很好。在这种情况下，termination_type只是 std：：set：：iterator。

问题是 std：：set 没有随机访问迭代器，因此没有运算符或运算符+=。 换句话说，您无法在恒定时间内推进迭代器，也无法计算在恒定时间内两个迭代器之间的距离。没有合理的方法添加这些缺少的运算符。 cilk_for循环根本不用于遍历线性或树结构容器，如列表或集合。

要理解为什么会这样，请考虑并行执行循环所需的条件。 首先，您必须将设置的数据雕刻成大致相等的块，然后必须将这些块分派给并行工作线程。 循环的每次迭代都必须能够立即转到预期要处理的输入块。 如果它需要线性遍历整个容器以找到其块的开头，那么您在很大程度上已经破坏了使用并行循环的目的。

有几种方法可以改善这种情况。 首先是考虑你的集合是否足够大，你对它执行的操作集是否足够昂贵，以至于完全没有并行性？ 如果没有，请使用串行循环并忘记它。 如果是这样，请考虑使用其他数据结构。 您可以用基于矢量的数据结构替换集合吗？ 在网上搜索，你会发现像 AssocVector in Loki 这样的东西，它与 std：：set 具有相同的界面，但在其实现中使用 vector 并具有随机访问迭代器;它应该很容易修改或包装以在 std：：set 接口而不是 std：：map 中给出。 它通常会胜过 std：：set 或 std：：map。

如果my_functor执行大量工作，则可以通过包含生成的简单串行循环来分摊线性遍历的成本：

for (auto it = vertex_set.begin(); it!=vertex_set.end(); ++it) {
    cilk_spawn func(*it);
}
cilk_sync;

但是请注意，如果 func(( 相对较小，那么重复生成的开销将对性能产生明显的负面影响。

或者，您可以使用cilk_for，遍历索引，而不是使用迭代器，如以下代码所示：

cilk_for (std::size_t i = 0; i < vertex_set.size(); ++i) {
    auto it = vertex_set.begin();
    std::advance(it, i);  // Slow step!
    func(*it);
}

如果你的集合足够大，你可以通过将集合预先分块到迭代器的向量中来减少对 std：：advance 的调用次数。 然后，您可以并行迭代块：

// Each element of this vector is the start of a chunk of the set.
std::vector<std::set<vertex_id>::iterator> chunks;
// Create 1000 chunks
const auto chunk_size = vertex_set.size() / 1000;
auto chunk = vector_set.begin();
for (int i = 0; i < 1000; ++i) {
    chunks.push(chunk);
    advance(chunk, chunk_size);
}
chunks.push(vector_set.end());
// Now, process the chunks in parallel
cilk_for (int i = 0; i < 1000; ++i) {
    // Iterate over elements in the chunk.
    for (auto it = chunks[i]; it != chunks[i + 1]; ++it)
        func(*it);
}

根据您的情况，上述两个主题有很多变化。 确保进行一些分析和计时，以帮助您选择最佳方法。

最后，我将提到正在考虑cilk_for的变体，该变体将适用于可以递归细分的任何数据结构(如树可以(。 这样的变化会直接解决你的问题，但我不能保证什么时候会有这样的东西。