Ошибка cilk_for для распараллеливания по std :: set, пропущенная operator- ()
Я пытался использовать cilk_for для перебора множества. Оказывается, у него нет оператора- (..), определенного для множества. учебник 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 согласно их примеру?
Решение
Проблема не в выражении завершения, это! = Vertex_set.end (), что нормально. В этом случае termination_type — это просто std :: set :: iterator.
Проблема в том, что std :: set не имеет итераторов с произвольным доступом и, следовательно, не имеет оператора- или оператора + =. Другими словами, вы не можете перемещать итератор за постоянное время и не можете вычислить расстояние между двумя итераторами за постоянное время. Нет разумного способа добавить эти недостающие операторы. Цикл cilk_for просто не предназначен для обхода линейных или древовидных контейнеров, таких как list или set.
Чтобы понять, почему это так, рассмотрим, что необходимо для параллельного выполнения цикла. Сначала вы должны разделить данные на примерно равные блоки, затем вы должны отправить эти блоки параллельным рабочим. Каждая итерация цикла должна быть в состоянии немедленно перейти к той части ввода, с которой она должна работать. Если ему необходимо линейно пройти весь контейнер, чтобы найти начало его фрагмента, то вы в значительной степени победили цель использования параллельного цикла.
Есть несколько способов улучшить ситуацию. Во-первых, нужно подумать, достаточно ли велик ваш набор, и набор операций, которые вы над ним выполняете, достаточно дорог, чтобы вообще беспокоиться о параллелизме? Если нет, используйте последовательный цикл и забудьте об этом. Если это так, рассмотрите возможность использования другой структуры данных. Можете ли вы заменить набор векторной структурой данных. Ищите в Интернете, и вы найдете такие вещи, как AssocVector в Loki, который имеет тот же интерфейс, что и 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, который будет работать с любой структурой данных, которая может быть рекурсивно подразделена (как дерево). Такое изменение решит вашу проблему напрямую, но я не могу обещать, когда такая вещь будет доступна.
Другие решения
detector