tbb: параллельный поиск первого элемента

Question

У меня есть эта проблема:

• Найти первый элемент в списке, для которого выполняется данное условие.

К сожалению, список довольно длинный (100.000 элементов), и оценка состояния каждого элемента занимает в общей сложности около 30 секунд с использованием одного отдельного потока.

Есть ли способ чисто распараллелить эту проблему?Я просмотрел все шаблоны tbb, но не смог найти подходящего.

ОБНОВЛЕНИЕ : по соображениям производительности я хочу как можно раньше остановиться, когда элемент найден, и остановить обработкуостальная часть списка.Вот почему я считаю, что я не могу использовать parallel_while или parallel_do.

Answer 1

Я думаю, что лучший способ решить эту проблему с помощью TBB - parallel_pipeline.

Должны быть (как минимум) две стадии конвейера. 1-й этап серийный; он просто читает следующий элемент из списка и передает его на второй этап. Эта 2-я стадия параллельна; это оценивает условие интереса для данного элемента. Как только условие выполнено, второй этап устанавливает флаг (который должен быть либо атомарным, либо защищенным блокировкой), чтобы указать, что решение найдено. На первом этапе необходимо проверить этот флаг и прекратить чтение списка, как только будет найдено решение.

Поскольку оценка состояния выполняется параллельно для нескольких элементов, может случиться, что найденный элемент будет не первым подходящим в списке. Если это важно, вам также необходимо сохранить индекс элемента, и когда найдено подходящее решение, вы обнаруживаете, меньше ли его индекс по сравнению с ранее известным решением (если оно есть).

НТН.

Answer 2

хорошо, я сделал это так:

1. Поместите все элементы в tbb::concurrent_bounded_queue<Element> elements.
2. Создать пустую tbb::concurrent_vector<Element> results.
3. Создайте boost::thread_group и создайте несколько потоков, выполняющих эту логику:

логика для параллельного запуска:

Element e;
while (results.empty() && elements.try_pop(e) {
    if (slow_and_painfull_check(e)) {
         results.push_back(e);
    }
}

Поэтому, когда будет найден первый элемент, все остальные потоки прекратят обработку при следующей проверке results.empty().

Возможно, что два или более потока работают над элементом, для которого slow_and_painfull_check возвращает true, поэтому я просто помещаю результат в вектор и обрабатываю его вне параллельного цикла.

После завершения всех потоков в группе потоков я проверяю все элементы в results и использую тот, который идет первым.

Answer 3

Я не слишком знаком с библиотеками для этого, но просто размышляю вслух, не могли бы вы иметь группу потоков, повторяющихся на разных шагах на одном шаге из разных начальных точек?

Скажем, вы решили иметь n потоков (= количество ядер или что-то еще), каждому потоку должна быть задана определенная начальная точка до n, поэтому первый поток начинается на begin(), следующий элемент - сравнивает это begin() + n и т. д. и т. д. Второй поток начинается на begin()+1, а затем его следующее сравнение тоже n и т. д.

Таким образом, вы можете создать группу потоков, итерирующих параллельно по списку, сама итерация, предположительно, не дорогая - просто сравнение. Ни один узел не будет сравниваться более одного раза, и вы можете иметь какое-то условие, которое устанавливается, когда какой-либо из потоков устанавливает соответствие, и все должны проверить это условие перед итерацией / сравнением.

Я думаю, что это довольно просто реализовать (?)

Answer 4

Не можете ли вы преобразовать список в сбалансированное дерево или подобное? Такие структуры данных проще обрабатывать параллельно - обычно вы получаете дополнительные издержки, которые вы, возможно, заплатили, чтобы сделать их сбалансированными в первый раз ... Например, если вы пишете код функционального стиля, проверьте этот документ: Сбалансированный деревья, населяющие функциональное параллельное программирование

Answer 5

Если это связанный список, параллельный поиск не увеличит скорость.Однако связанные списки, как правило, плохо работают с кешами.Вы можете получить небольшое увеличение производительности, если у вас есть два потока: один выполняет find_first_element, а другой просто перебирает список, следя за тем, чтобы не превысить X (100?) Перед первым потоком.Второй поток не выполняет никаких сравнений, но гарантирует, что элементы кэшируются как можно лучше для первого потока.Это может помочь вашему времени, или это может иметь мало значения, или это может помешать.Протестируйте все.

Answer 6

Здесь я вижу две возможности для параллелизма: оценка одного элемента в нескольких потоках или оценка нескольких элементов одновременно в разных потоках.

Недостаточно информации для определения сложности или эффективности оценки одного элемента в нескольких потоках. Если это легко, время 30 секунд на элемент может быть уменьшено.

Я не вижу четкого соответствия в TBB для этой проблемы. Существуют проблемы со списками, не имеющими итераторов произвольного доступа, определяющими, когда останавливаться, и гарантирующими, что первый элемент найден. Возможно, есть некоторые игры, в которые вы можете играть с диапазонами, чтобы заставить его работать.

Вы могли бы также использовать некоторые конструкции потоков более низкого уровня, чтобы реализовать это самостоятельно, но есть ряд мест для неправильных результатов, которые должны быть возвращены. Чтобы предотвратить такие ошибки, я бы порекомендовал использовать существующий алгоритм. Вы можете преобразовать список в массив (или другую структуру с итераторами произвольного доступа) и использовать экспериментальный алгоритм lib_dc ++ Parellel Mode find_if, на который ссылается user383522.

Answer 7

Если вы используете GCC, GNU OpenMP предоставляет параллельные стандартные функции ссылка

Answer 8

вы можете взглянуть на http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html для реализации параллельных алгоритмов.А в частности вам нужен алгоритм find_if http://www.cplusplus.com/reference/algorithm/find_if/

Answer 9

Я никогда не слышал о библиотеке Intel tbb, но быстрое открытие и просмотр Учебника привели меня к parallel_for, который, похоже, сработает.