| 1 |
// -*- C++ -*- |
| 2 |
//===-- parallel_impl.h ---------------------------------------------------===// |
| 3 |
// |
| 4 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 5 |
// See https://llvm.org/LICENSE.txt for license information. |
| 6 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 7 |
// |
| 8 |
//===----------------------------------------------------------------------===// |
| 9 |
|
| 10 |
#ifndef _PSTL_PARALLEL_IMPL_H |
| 11 |
#define _PSTL_PARALLEL_IMPL_H |
| 12 |
|
| 13 |
#include <atomic> |
| 14 |
// This header defines the minimum set of parallel routines required to support Parallel STL, |
| 15 |
// implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library |
| 16 |
|
| 17 |
namespace __pstl |
| 18 |
{ |
| 19 |
namespace __internal |
| 20 |
{ |
| 21 |
|
| 22 |
//------------------------------------------------------------------------ |
| 23 |
// parallel_find |
| 24 |
//----------------------------------------------------------------------- |
| 25 |
/** Return extremum value returned by brick f[i,j) for subranges [i,j) of [first,last) |
| 26 |
Each f[i,j) must return a value in [i,j). */ |
| 27 |
template <class _ExecutionPolicy, class _Index, class _Brick, class _Compare> |
| 28 |
_Index |
| 29 |
__parallel_find(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first) |
| 30 |
{ |
| 31 |
typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType; |
| 32 |
const _DifferenceType __n = __last - __first; |
| 33 |
_DifferenceType __initial_dist = __b_first ? __n : -1; |
| 34 |
std::atomic<_DifferenceType> __extremum(__initial_dist); |
| 35 |
// TODO: find out what is better here: parallel_for or parallel_reduce |
| 36 |
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, |
| 37 |
[__comp, __f, __first, &__extremum](_Index __i, _Index __j) { |
| 38 |
// See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of |
| 39 |
// why using a shared variable scales fairly well in this situation. |
| 40 |
if (__comp(__i - __first, __extremum)) |
| 41 |
{ |
| 42 |
_Index __res = __f(__i, __j); |
| 43 |
// If not '__last' returned then we found what we want so put this to extremum |
| 44 |
if (__res != __j) |
| 45 |
{ |
| 46 |
const _DifferenceType __k = __res - __first; |
| 47 |
for (_DifferenceType __old = __extremum; __comp(__k, __old); |
| 48 |
__old = __extremum) |
| 49 |
{ |
| 50 |
__extremum.compare_exchange_weak(__old, __k); |
| 51 |
} |
| 52 |
} |
| 53 |
} |
| 54 |
}); |
| 55 |
return __extremum != __initial_dist ? __first + __extremum : __last; |
| 56 |
} |
| 57 |
|
| 58 |
//------------------------------------------------------------------------ |
| 59 |
// parallel_or |
| 60 |
//------------------------------------------------------------------------ |
| 61 |
//! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last) |
| 62 |
template <class _ExecutionPolicy, class _Index, class _Brick> |
| 63 |
bool |
| 64 |
__parallel_or(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f) |
| 65 |
{ |
| 66 |
std::atomic<bool> __found(false); |
| 67 |
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, |
| 68 |
[__f, &__found](_Index __i, _Index __j) { |
| 69 |
if (!__found.load(std::memory_order_relaxed) && __f(__i, __j)) |
| 70 |
{ |
| 71 |
__found.store(true, std::memory_order_relaxed); |
| 72 |
__par_backend::__cancel_execution(); |
| 73 |
} |
| 74 |
}); |
| 75 |
return __found; |
| 76 |
} |
| 77 |
|
| 78 |
} // namespace __internal |
| 79 |
} // namespace __pstl |
| 80 |
|
| 81 |
#endif /* _PSTL_PARALLEL_IMPL_H */ |
