0

我试图cilk_for用于迭代集合。事实证明，它没有为 set 定义 operator-(..)。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根据他们的例子是什么？

4

1 回答 1

1

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

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

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

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

如果 my_functor 做了大量工作，您也许可以使用包含 spawn 的简单串行循环来分摊线性遍历的成本：

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 的一个变体正在考虑中，它可以对任何可以递归细分的数据结构进行操作（就像树一样）。这样的变化将直接解决您的问题，但我不能保证何时可以使用这样的东西。

于 2014-12-09T20:29:15.720 回答