How to: Convert an OpenMP Loop that Uses Cancellation to Use the Concurrency Runtime

Some parallel loops do not require that all iterations be executed. For example, an algorithm that searches for a value can terminate after the value is found. OpenMP does not provide a mechanism to break out of a parallel loop. However, you can use a Boolean value, or flag, to enable an iteration of the loop to indicate that the solution has been found. The Concurrency Runtime provides functionality that enables one task to cancel other tasks that have not yet started.

This example demonstrates how to convert an OpenMP parallelfor loop that does not require for all iterations to run to use the Concurrency Runtime cancellation mechanism.

Example

This example uses both OpenMP and the Concurrency Runtime to implement a parallel version of the std::any_of algorithm. The OpenMP version of this example uses a flag to coordinate among all parallel loop iterations that the condition has been met. The version that uses the Concurrency Runtime uses the concurrency::structured_task_group::cancel method to stop the overall operation when the condition is met.

// concrt-omp-parallel-any-of.cpp
// compile with: /EHsc /openmp
#include <ppl.h>
#include <array>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Uses OpenMP to determine whether a condition exists in 
// the specified range of elements.
template <class InIt, class Predicate>
bool omp_parallel_any_of(InIt first, InIt last, const Predicate& pr)
{
   typedef typename std::iterator_traits<InIt>::value_type item_type;

   // A flag that indicates that the condition exists.
   bool found = false;

   #pragma omp parallel for
      for (int i = 0; i < static_cast<int>(last-first); ++i)
      {
         if (!found)
         {
            item_type& cur = *(first + i);

            // If the element satisfies the condition, set the flag to 
            // cancel the operation.
            if (pr(cur)) {
               found = true;
            }
         }
      }

   return found;
}

// Uses the Concurrency Runtime to determine whether a condition exists in 
// the specified range of elements.
template <class InIt, class Predicate>
bool concrt_parallel_any_of(InIt first, InIt last, const Predicate& pr)
{
   typedef typename std::iterator_traits<InIt>::value_type item_type;

   structured_task_group tasks;

   // Create a predicate function that cancels the task group when
   // an element satisfies the condition.
   auto for_each_predicate = [&pr, &tasks](const item_type& cur) {
      if (pr(cur)) {
         tasks.cancel();
      }
   };

   // Create a task that calls the predicate function in parallel on each
   // element in the range.
   auto task = make_task([&]() {
       parallel_for_each(first, last, for_each_predicate);
   });

   // The condition is satisfied if the task group is in the cancelled state.
   return tasks.run_and_wait(task) == canceled;
}

int wmain()
{
   // The length of the array.
   const size_t size = 100000;
   
   // Create an array and initialize it with random values.
   array<int, size> a;   
   generate(begin(a), end(a), mt19937(42));

   // Search for a value in the array by using OpenMP and the Concurrency Runtime.

   const int what = 9114046;
   auto predicate = [what](int n) -> bool { 
      return (n == what);
   };

   wcout << L"Using OpenMP..." << endl;
   if (omp_parallel_any_of(begin(a), end(a), predicate))
   {
      wcout << what << L" is in the array." << endl;
   }
   else
   {
      wcout << what << L" is not in the array." << endl;
   }

   wcout << L"Using the Concurrency Runtime..." << endl;
   if (concrt_parallel_any_of(begin(a), end(a), predicate))
   {
      wcout << what << L" is in the array." << endl;
   }
   else
   {
      wcout << what << L" is not in the array." << endl;
   }
}

This example produces the following output.

Using OpenMP...
9114046 is in the array.
Using the Concurrency Runtime...
9114046 is in the array.

In the version of that uses OpenMP, all iterations of the loop execute, even when the flag is set. Furthermore, if a task were to have any child tasks, the flag would also have to be available to those child tasks to communicate cancellation. In the Concurrency Runtime, when a task group is canceled, the runtime cancels the entire tree of work, including child tasks. The concurrency::parallel_for_each algorithm uses tasks to perform work. Therefore, when one iteration of the loop cancels the root task, the entire tree of computation is also canceled. When a tree of work is canceled, the runtime does not start new tasks. However, the runtime allows tasks that have already started to finish. Therefore, in the case of the parallel_for_each algorithm, active loop iterations can clean up their resources.

In both versions of this example, if the array contains more than one copy of the value to search for, multiple loop iterations can each simultaneously set the result and cancel the overall operation. You can use a synchronization primitive, such as a critical section, if your problem requires that only one task performs work when a condition is met.

You can also use exception handling to cancel tasks that use the PPL. For more information about cancellation, see Cancellation in the PPL.

For more information about parallel_for_each and other parallel algorithms, see Parallel Algorithms.

Compiling the Code

Copy the example code and paste it in a Visual Studio project, or paste it in a file that is named concrt-omp-parallel-any-of.cpp and then run the following command in a Visual Studio Command Prompt window.

cl.exe /EHsc /openmp concrt-omp-parallel-any-of.cpp

See also

Migrating from OpenMP to the Concurrency Runtime
Cancellation in the PPL
Parallel Algorithms