find_first of a vector in parallel in C++

Question

У меня довольно большой вектор. Некоторые из элементов вектора параллельны определенному условию. Я хотел бы найти первый элемент, соответствующий условию.

Моя проблема очень похожа на этот вопрос (tbb: parallel find first element), но у меня нет tbb. Условие проверки очень утомительно (поэтому я не могу сделать это для всех из них последовательно). Вот почему я хотел бы запустить его параллельно. Я должен упомянуть, что мне хотелось бы найти первый элемент (поэтому для меня важна позиция индекса элемента).

Для примера, если у меня есть 4 потока.

ThreadNr Index  condition 
1   0   Not Meet 
2   1   Not Meet 
3   2   Not Meet 
4   3   Not Meet 

ThreadNr Index  condition 
1   4   Not Meet 
2   5   Meet 
3   6   Not Meet 
4   7   Meet 

Функция должна Retun порядковый номер 5. Нити должны быть распределены и работать на последовательном блоке итерации (размер блока может быть больше, что 1. Например, нить 1 работает на первых 4-х элементов, резьбы 2 на вторых 4 элементах и ​​т. Д.).

Для примера выше, если номер потока 4 (в индексе 7) нашел член до номера нити номер 2 (в индексе 5), он должен подождать, пока вся нить завершит работу. Как я уже говорил, самым низким номером индекса является цель.

Пожалуйста, исправьте меня, если у вас есть лучший алгоритм.

ПРИМЕЧАНИЕ: Я могу использовать внешние библиотеки, такие как прирост 1,62, OpenMP 2.0

Answer 1

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

int found = 0; 
int first_index = INVALID_VALUE; 
int iteration = 0; 

#pragma omp parallel 
{ 
    int my_index = INVALID_VALUE; 
    int i; 

    do 
    { 
     // Later versions of OpenMP allow for "atomic capture" 
     // but OpenMP 2.0 requires a critical directive instead 
     #pragma omp critical(iteration) 
     { 
     i = iteration++; 
     } 

     if (i < N && check(i)) 
     { 
     found = 1; 
     my_index = i; 
     } 
    } while (!found && i < N); 

    #pragma omp critical(reduction) 
    if (my_index != INVALID_VALUE) 
    { 
     if (first_index == INVALID_VALUE || my_index < first_index) 
     first_index = my_index; 
    } 

    // Only needed if more code follows before the end of the region 
    #pragma omp barrier 

    ... 
} 

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

Конструкция critical, используемая в do-loop, является дорогостоящей. Если check() не займет много времени, то вы могли бы рассмотреть возможность работы с кусками вместо итераций:

do 
{ 
    #pragma omp critical(chunk) 
    { 
     my_chunk = chunk++; 
    } 

    if (my_chunk >= N_chunks) 
     break; 

    for (i = my_chunk * chunk_size; !found && i < (my_chunk+1)*chunk_size; i++) 
    { 
     if (check(i)) 
     { 
     found = 1; 
     my_index = i; 
     break; 
     } 
    } 
} while (!found && my_chunk < N_chunks); 

---

Еще одно решение, которое работает достаточно хорошо, когда число элементов не так уж велик и проверка каждого из них дорого:

#pragma omp parallel 
{ 
    #pragma omp for schedule(dynamic,x) 
    for (i = 0; i < N; i++) 
    { 
     if (!found && check(i)) 
     { 
     my_index = i; 
     found = 1; 
     } 
    } 

    // Min reduction from the solution above 
    ... 
} 

После found становится истинным, остальные итерации цикла будет работать «пустые» тела, так как свойства shortcutting в &&.

Answer 2

С помощью OpenMP вы можете попытаться построить цикл с #pragma omp for schedule(dynamic). Каждый поток будет выполнять одну итерацию в том же порядке, что и ваш вектор. Если вы хотите проверить 4 элемента по теме, попробуйте #pragma omp for schedule(dynamic, 4)