Уменьшение количества итераций в OpenMP parallel для

Question

У меня есть parallel for в программе на С ++, которая должна зацикливаться до некоторого количества итераций. Каждая итерация вычисляет возможное решение для алгоритма, и я хочу выйти из цикла, как только я нахожу допустимый (это нормально, если сделано несколько дополнительных итераций). Я знаю, что число итераций должно быть исправлено с начала в parallel for, но поскольку я не увеличиваю число итераций в следующем коде, есть ли какая-либо гарантия того, что эти потоки проверяют условие, прежде чем продолжить свою текущую итерацию?

void fun() 
{ 
    int max_its = 100; 

    #pragma omp parallel for schedule(dynamic, 1) 
    for(int t = 0; t < max_its; ++t) 
    { 
    ... 
    if(some condition) 
     max_its = t; // valid to make threads exit the for? 
    } 
} 

Answer 1

Вы не можете изменить max_its, так как стандарт говорит, что это должно быть выражение инварианта цикла.

Что вы можете сделать, хотя, использует булево общую переменную в качестве флага:

void fun() 
{ 
    int max_its = 100; 
    bool found = false; 
    #pragma omp parallel for schedule(dynamic, 1) shared(found) 
    for(int t = 0; t < max_its; ++t) 
    { 
    if(! found) { 
    ... 
    } 
    if(some condition) { 
    #pragma omp atomic 
     found = true; // valid to make threads exit the for? 
    } 
    } 
} 

Логика такого рода могут быть также реализованы с помощью задач вместо конструкции разделения работы. Эскиз кода будет что-то вроде следующего:

void algorithm(int t, bool& found) { 
#pragma omp task shared(found) 
{ 
    if(!found) { 
    // Do work 
    if (/* conditionc*/) { 
     #pragma omp atomic 
     found = true 
    } 
    } 
} // task 
} // function 


void fun() 
{ 
    int max_its = 100; 
    bool found = false; 
    #pragma omp parallel 
    { 
    #pragma omp single 
    { 
     for(int t = 0; t < max_its; ++t) 
     { 
     algorithm(t,found); 
     } 
    } // single 
    } // parallel 
} 

Идея заключается в том, что один поток создает max_its задачи. Каждая задача будет назначена ожидающему потоку. Если некоторые из задач найдут правильное решение, то все остальные будут проинформированы об обнаруженной общей переменной.

Answer 2

Если some_condition логическое выражение, которое «всегда действует», то вы можете сделать:

for(int t = 0; t < max_its && !some_condition; ++t) 

Таким образом, это очень ясно, что !some_condition требуется продолжить цикл, и нет необходимости читать остальную часть кода, чтобы узнать, что «если some_condition, концы петли»

В противном случае (например, если some_condition является результатом s вычисление ome внутри цикла, и сложно «переместить» some_condition в состояние «for-loop», а затем использовать break - это, безусловно, правильная вещь.

Answer 3

Изменение счетчика циклов работает для большинства реализаций конструкций OpenHMP, но программа больше не будет соответствовать OpenMP, и нет гарантии, что программа будет работать с другими компиляторами.

Поскольку OP в порядке с некоторыми дополнительными итерациями, отменой OpenMP будет путь. В OpenMP 4.0 для этой цели была создана конструкция «отменить». Он запросит завершение работы схемы сборки и телепортирует потоки до конца.

void fun() 
{ 
    int max_its = 100; 

#pragma omp parallel for schedule(dynamic, 1) 
    for(int t = 0; t < max_its; ++t) 
    { 
    ... 
    if(some condition) { 
#pragma omp cancel for 
    } 
#pragma omp cancellation point for 
    } 
} 

Имейте в виду, что, возможно, там может быть цена, чтобы заплатить с точки зрения производительности, но вы можете принять это, если общая производительность лучше при прерывании цикла.

В пре-4.0 реализаций OpenMP, единственное решение OpenMP-совместимый будет иметь если заявление подойти к регулярному конец цикла как можно быстрее, без выполнения фактического тело цикла:

void fun() 
{ 
    int max_its = 100; 

#pragma omp parallel for schedule(dynamic, 1) 
    for(int t = 0; t < max_its; ++t) 
    { 
    if(!some condition) { 
     ... loop body ... 
    } 
    } 
} 

Надеюсь, что это поможет!

Приветствия, -Michael