Algorithms operating on DASH containers

Functions
template<typename GlobIter , typename UnaryPredicate >
bool	dash::all_of (GlobIter first, GlobIter last, UnaryPredicate p)
	Check whether all element in the range satisfy predicate p. More...
template<typename GlobIter , typename UnaryPredicate >
bool	dash::any_of (GlobIter first, GlobIter last, UnaryPredicate p)
	Check whether any element in the range satisfies predicate p. More...
template<class LocalInputIter , typename = typename std::enable_if< !dash::detail::is_global_iterator<LocalInputIter>::value >::type>
void	dash::broadcast (LocalInputIter in_first, LocalInputIter in_last, dash::team_unit_t root, dash::Team &team=dash::Team::All())
	Broadcast the local range of elements [in_first, in_last) from unit root to all other units in team. More...
template<class ValueType >
ValueType	dash::broadcast (dash::Shared< ValueType > &shared)
	Broadcast the value stored in dash::Shared from the unit owning the value to all other units with access to the shared object. More...
template<typename T >
void	dash::broadcast (Coarray< T > &coarr, const team_unit_t &root)
	Broadcasts the value on root to all other members of this co_array. More...
template<typename ValueType , class InputIt , class OutputIt >
OutputIt	dash::copy (InputIt in_first, InputIt in_last, OutputIt out_first)
	Copies the elements in the range, defined by [in_first, in_last), to another range beginning at out_first. More...
template<typename ValueType , class GlobInputIt >
dash::Future< ValueType * >	dash::copy_async (InputIt in_first, InputIt in_last, OutputIt out_first)
	Asynchronous variant of dash::copy. More...
template<typename GlobIter >
bool	dash::equal (GlobIter first_1, GlobIter last_1, GlobIter first_2)
	Returns true if the range [first1, last1) is equal to the range [first2, first2 + (last1 - first1)), and false otherwise. More...
template<typename GlobIter , class BinaryPredicate >
bool	dash::equal (GlobIter first_1, GlobIter last_1, GlobIter first_2, BinaryPredicate)
	Returns true if the range [first1, last1) is equal to the range [first2, first2 + (last1 - first1)) with respect to a specified predicate, and false otherwise. More...
template<typename GlobIterType >
void	dash::fill (GlobIterType first, GlobIterType last, const typename GlobIterType::value_type &value)
	Assigns the given value to the elements in the range [first, last) More...
template<typename GlobIter , typename ElementType >
GlobIter	dash::find (GlobIter first, GlobIter last, const ElementType &value)
	Returns an iterator to the first element in the range [first,last) that compares equal to val. More...
template<typename GlobIter , typename UnaryPredicate >
GlobIter	dash::find_if (GlobIter first, GlobIter last, UnaryPredicate predicate)
	Returns an iterator to the first element in the range [first,last) that satisfies the predicate p. More...
template<typename GlobIter , class UnaryPredicate >
GlobIter	dash::find_if_not (GlobIter first, GlobIter last, UnaryPredicate predicate)
	Returns an iterator to the first element in the range [first,last) that does not satisfy the predicate p. More...
template<typename GlobInputIt , class UnaryFunction >
void	dash::for_each (const GlobInputIt &first, const GlobInputIt &last, UnaryFunction func)
	Invoke a function on every element in a range distributed by a pattern. More...
template<typename GlobInputIt , class UnaryFunctionWithIndex >
void	dash::for_each_with_index (const GlobInputIt &first, const GlobInputIt &last, UnaryFunctionWithIndex func)
	Invoke a function on every element in a range distributed by a pattern. More...
template<typename GlobInputIt , class UnaryFunction >
void	dash::generate (GlobInputIt first, GlobInputIt last, UnaryFunction gen)
	Assigns each element in range [first, last) a value generated by the given function object g. More...
template<typename GlobInputIt , class UnaryFunction >
void	dash::generate_with_index (GlobInputIt first, GlobInputIt last, UnaryFunction gen)
	Assigns each element in range [first, last) a value generated by the given function object g. More...
template<class GlobInputIter >
std::enable_if< !GlobInputIter::has_view::value, LocalIndexRange< typename GlobInputIter::pattern_type::index_type >>::type	dash::local_index_range (const GlobInputIter &first, const GlobInputIter &last)
	Resolves the local index range between global iterators. More...
template<class GlobIterType >
LocalRange< const typename GlobIterType::value_type >	dash::local_range (const GlobIterType &first, const GlobIterType &last)
	Resolves the local address range between global iterators. More...
template<class ElementType , class Compare = std::less<const ElementType &>>
const ElementType *	dash::min_element (const ElementType *l_range_begin, const ElementType *l_range_end, Compare compare=std::less< const ElementType &>())
	Finds an iterator pointing to the element with the smallest value in the range [first,last). More...
template<typename GlobInputIt , class Compare = std::less< const typename dash::iterator_traits<GlobInputIt>::value_type &>>
GlobInputIt	dash::min_element (const typename std::enable_if< dash::iterator_traits< GlobInputIt >::is_global_iterator::value, GlobInputIt >::type &first, const GlobInputIt &last, Compare compare=Compare())
	Finds an iterator pointing to the element with the smallest value in the range [first,last). More...
template<class GlobIter , class Compare = std::greater<const typename GlobIter::value_type &>>
GlobIter	dash::max_element (const GlobIter &first, const GlobIter &last, Compare compare=Compare())
	Finds an iterator pointing to the element with the greatest value in the range [first,last). More...
template<class ElementType , class Compare = std::greater<ElementType &>>
const ElementType *	dash::max_element (const ElementType *first, const ElementType *last, Compare compare=Compare())
	Finds an iterator pointing to the element with the greatest value in the range [first,last). More...
template<class LocalInputIter , class InitType , class BinaryOperation = dash::plus<typename std::iterator_traits<LocalInputIter>::value_type>, typename = typename std::enable_if< !dash::detail::is_global_iterator<LocalInputIter>::value >::type>
std::iterator_traits< LocalInputIter >::value_type	dash::reduce (LocalInputIter in_first, LocalInputIter in_last, InitType init, BinaryOperation binary_op=BinaryOperation(), bool non_empty=true, dash::Team &team=dash::Team::All())
	Accumulate values in each process' range [in_first, in_last) using the provided binary reduce function binary_op, which must be commutative and associative. More...
template<class LocalInputIter , class InitType = typename std::iterator_traits<LocalInputIter>::value_type, typename = typename std::enable_if< !dash::detail::is_global_iterator<LocalInputIter>::value >::type>
std::iterator_traits< LocalInputIter >::value_type	dash::reduce (LocalInputIter in_first, LocalInputIter in_last, InitType init, bool non_empty, dash::Team &team=dash::Team::All())
	Accumulate values across the local ranges [in_first,in_last) of each process as the sum of all values in the range. More...
template<class GlobInputIt , class InitType = typename dash::iterator_traits<GlobInputIt>::value_type, class BinaryOperation = dash::plus<typename dash::iterator_traits<GlobInputIt>::value_type>, typename = typename std::enable_if< dash::detail::is_global_iterator<GlobInputIt>::value >::type>
dash::iterator_traits< GlobInputIt >::value_type	dash::reduce (GlobInputIt in_first, GlobInputIt in_last, InitType init, BinaryOperation binary_op=BinaryOperation())
	Accumulate values in the global range [in_first, in_last) using the provided binary reduce function binary_op, which must be commutative and linear. More...
template<class GlobRandomIt >
void	dash::sort (GlobRandomIt begin, GlobRandomIt end)
	Sorts the elements in the range, defined by [begin, end) in ascending order. More...
template<class GlobRandomIt , class SortableHash >
void	dash::sort (GlobRandomIt begin, GlobRandomIt end, SortableHash hash)
	Sorts the elements in the range, defined by [begin, end) in ascending order. More...
template<typename ValueType , class InputIt , class OutputIt , class UnaryOperation >
OutputIt	dash::transform (InputIt in_first, InputIt in_last, OutputIt out_first, UnaryOperation unary_op)
	Apply a given function to elements in a range and store the result in another range, beginning at out_first. More...
template<class InputIt1 , class GlobInputIt , class GlobOutputIt , class BinaryOperation >
GlobOutputIt	dash::transform (InputIt1 in_a_first, InputIt1 in_a_last, GlobInputIt in_b_first, GlobOutputIt out_first, BinaryOperation binary_op)
	Apply a given function to pairs of elements from two ranges and store the result in another range, beginning at out_first. More...

Detailed Description

Description

DASH algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on DASH containers.

Function Documentation

all_of()

template<typename GlobIter , typename UnaryPredicate >

bool dash::all_of	(	GlobIter	first,
		GlobIter	last,
		UnaryPredicate	p
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/AllOf.h>

Check whether all element in the range satisfy predicate p.

Returns

true if all elements satisfy p, false otherwise.

See also

dash::find_if

dash::find_if_not

dash::any_of

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
p	Predicate applied to the elements in range [first, last)

Examples:

ex.06.std-algo/main.cpp.

Definition at line 24 of file AllOf.h.

References dash::find_if_not().

{
  return find_if_not(first, last, p) == last;
}

any_of()

template<typename GlobIter , typename UnaryPredicate >

bool dash::any_of	(	GlobIter	first,
		GlobIter	last,
		UnaryPredicate	p
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/AnyOf.h>

Check whether any element in the range satisfies predicate p.

Returns

true if at least one element satisfies p, false otherwise.

See also

dash::find_if

dash::find_if_not

dash::all_of

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
p	Predicate applied to the elements in range [first, last)

Definition at line 23 of file AnyOf.h.

References dash::find_if().

{
  return find_if(first, last, p) != last;
}

broadcast() [1/3]

template<class LocalInputIter , typename = typename std::enable_if< !dash::detail::is_global_iterator<LocalInputIter>::value >::type>

void dash::broadcast	(	LocalInputIter	in_first,
		LocalInputIter	in_last,
		dash::team_unit_t	root,
		dash::Team &	team = dash::Team::All()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Bcast.h>

Broadcast the local range of elements [in_first, in_last) from unit root to all other units in team.

If the range is not contiguous, a local copy of the data is created, broadcast, and copied into the range on all unit except for root.

The range has to have the same size on all units.

This operation overwrites the values in the range on all units except for root.

Collective operation.

Parameters

in_first	Local iterator describing the beginning of the range to broadcast.
in_last	Local iterator describing the end of the range to broadcast.
root	The unit (member of team) to broadcast the data from.
team	The team to use for the collective operation.

Definition at line 95 of file Bcast.h.

References dash::broadcast().

Referenced by dash::broadcast().

{
  dash::internal::broadcast(
    in_first, in_last, root, team,
    typename std::iterator_traits<LocalInputIter>::iterator_category());
}

broadcast() [2/3]

template<class ValueType >

ValueType dash::broadcast

(

dash::Shared< ValueType > &

shared

)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Bcast.h>

Broadcast the value stored in dash::Shared from the unit owning the value to all other units with access to the shared object.

Collective operation.

Note

A broadcast can be more efficient than having all units access the value stored in the dash::Shared instance individually.

Parameters

shared

Instance of dash::Shared from which the value is broadcast to all units in the team that created the shared object.

Returns

The value broadcasted.

Definition at line 124 of file Bcast.h.

References dash::broadcast(), dash::Shared< ElementType >::local(), dash::Shared< ElementType >::owner(), dash::Shared< ElementType >::team(), and dash::ValueType.

{
  ValueType res{};
  auto& team  = shared.team();
  auto  owner = shared.owner();
  ValueType *ptr = (team.myid() == owner) ? shared.local() : std::addressof(res);
  dash::broadcast(ptr,
                  std::next(ptr),
                  owner,
                  shared.team());

  return *ptr;
}

broadcast() [3/3]

template<typename T >

void dash::broadcast	(	Coarray< T > &	coarr,
		const team_unit_t &	root
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Bcast.h>

Broadcasts the value on root to all other members of this co_array.

This is a wrapper for dash::coarray::cobroadcast.

Collective operation.

See also

dash::coarray::cobroadcast

Parameters

coarr	coarray which should be broadcasted
master	the value of this unit will be broadcastet

Definition at line 152 of file Bcast.h.

References dash::coarray::cobroadcast().

Referenced by dash::broadcast().

                                                            {
  dash::coarray::cobroadcast(coarr, root);
}

copy()

template<typename ValueType , class InputIt , class OutputIt >

OutputIt dash::copy	(	InputIt	in_first,
		InputIt	in_last,
		OutputIt	out_first
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Copy.h>

Copies the elements in the range, defined by [in_first, in_last), to another range beginning at out_first.

In terms of data distribution, source and destination ranges passed to dash::copy can be local (*ValueType) or global (GlobIter<ValueType>).

For a non-blocking variant of dash::copy, see dash::copy_async.

Example:

// Start blocking copy
auto copy_last =
  dash::copy(array_a.lbegin(),
             array_a.lend(),
             array_b.begin() + 200);
auto ncopied = dash::distance(array_b.begin() + 200, copy_last);

Returns

The output range end iterator that is created on completion of the copy operation.

Examples:

ex.06.std-algo/main.cpp, ex.10.radixsort/main.cpp, and ex.11.halo-stencil/main.cpp.

Referenced by dash::summa().

copy_async()

template<typename ValueType , class GlobInputIt >

dash::Future<ValueType *> dash::copy_async	(	InputIt	in_first,
		InputIt	in_last,
		OutputIt	out_first
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Copy.h>

Asynchronous variant of dash::copy.

Copies the elements in the range, defined by [in_first, in_last), to another range beginning at out_first.

In terms of data distribution, source and destination ranges passed to dash::copy can be local (*ValueType) or global (GlobIter<ValueType>).

For a blocking variant of dash::copy_async, see dash::copy.

Example:

// Start asynchronous copying
dash::Future<T*> fut_dest_end =
  dash::copy_async(array_a.block(0).begin(),
                   array_a.block(0).end(),
                   local_array);
// Overlapping computation here
// ...
// Wait for completion of asynchronous copying:
T * copy_dest_end = fut_dest_end.get();

Returns

An instance of dash::Future providing the output range end iterator that is created on completion of the asynchronous copy operation.

Referenced by dash::summa().

equal() [1/2]

template<typename GlobIter >

bool dash::equal	(	GlobIter	first_1,
		GlobIter	last_1,
		GlobIter	first_2
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Equal.h>

Returns true if the range [first1, last1) is equal to the range [first2, first2 + (last1 - first1)), and false otherwise.

Parameters

first_1	Iterator to the initial position in the sequence
last_1	Iterator to the final position in the sequence

Definition at line 51 of file Equal.h.

References dart_allreduce(), DART_OK, DART_OP_BAND, DART_TYPE_BYTE, dash::distance(), dash::GlobIter< ElementType, PatternType, GlobMemType, PointerType, ReferenceType >::local(), dash::local_range(), and dash::myid().

  {
    static_assert(
        dash::iterator_traits<GlobIter>::is_global_iterator::value,
        "invalid iterator: Need to be a global iterator");

    auto& team = first_1.team();
    auto  myid = team.myid();
    // Global iterators to local range:
    auto index_range_in  = dash::local_range(first_1, last_1);
    auto l_first_1       = index_range_in.begin;
    auto l_last_1        = index_range_in.end;
    auto dist            = std::distance(l_first_1, l_last_1);
    auto index_range_out = dash::local_range(first_2, first_2 + dist);
    auto common_dist     = std::min(
        std::distance(index_range_out.begin, index_range_out.end), dist);
    char l_result = 1;

    // check if local ranges are corresponding
    if (common_dist == dist) {
      l_result = ::dash::internal::equal_loc_impl(
          l_first_1, l_last_1, first_2.local());
    } else if(common_dist > 0) {
    l_result = ::dash::internal::equal_overlapping_impl(
        first_1, last_1, first_2);
  }

  char r_result         = 0;

  DASH_ASSERT_RETURNS(
    dart_allreduce(&l_result, &r_result, 1,
      DART_TYPE_BYTE, DART_OP_BAND, team.dart_id()),
    DART_OK);
  return r_result;
}

equal() [2/2]

template<typename GlobIter , class BinaryPredicate >

bool dash::equal	(	GlobIter	first_1,
		GlobIter	last_1,
		GlobIter	first_2,
		BinaryPredicate
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Equal.h>

Returns true if the range [first1, last1) is equal to the range [first2, first2 + (last1 - first1)) with respect to a specified predicate, and false otherwise.

Parameters

first_1	Iterator to the initial position in the sequence
last_1	Iterator to the final position in the sequence

Definition at line 100 of file Equal.h.

References dart_allreduce(), DART_OK, DART_OP_BAND, DART_TYPE_BYTE, dash::distance(), dash::GlobIter< ElementType, PatternType, GlobMemType, PointerType, ReferenceType >::local(), dash::local_range(), and dash::myid().

{
  static_assert(
      dash::iterator_traits<GlobIter>::is_global_iterator::value,
      "invalid iterator: Need to be a global iterator");

  auto & team        = first_1.team();
  auto myid          = team.myid();
  // Global iterators to local range:
  auto index_range_in   = dash::local_range(first_1, last_1);
  auto l_first_1        = index_range_in.begin;
  auto l_last_1         = index_range_in.end;
  auto dist             = std::distance(l_first_1, l_last_1);
  auto index_range_out  = dash::local_range(first_2, first_2 + dist);
  auto common_dist      = std::min(std::distance(index_range_out.begin, index_range_out.end),dist);
  char l_result         = 1;

  // check if local ranges are corresponding
  if(std::distance(index_range_out.begin, index_range_out.end) == dist){
    l_result = ::dash::internal::equal_loc_impl(l_first_1, l_last_1, first_2.local());
  } else if(common_dist > 0) {
    l_result = ::dash::internal::equal_overlapping_impl(
        first_1, last_1, first_2);
  }

  char r_result      = 0;

  DASH_ASSERT_RETURNS(
    dart_allreduce(&l_result, &r_result, 1,
      DART_TYPE_BYTE, DART_OP_BAND, team.dart_id()),
    DART_OK);
  return r_result;
}

fill()

template<typename GlobIterType >

void dash::fill	(	GlobIterType	first,
		GlobIterType	last,
		const typename GlobIterType::value_type &	value
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Fill.h>

Assigns the given value to the elements in the range [first, last)

Being a collaborative operation, each unit will assign the value to its local elements only.

Template Parameters

ElementType

Type of the elements in the sequence

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
value	Value which will be assigned to the elements in range [first, last)

Examples:

ex.08.io-hdf5/main.cpp, ex.11.halo-stencil/main.cpp, and ex.11.simple-stencil/main.cpp.

Definition at line 35 of file Fill.h.

References dash::local_range(), and dash::util::UnitLocality::num_domain_threads().

Referenced by dash::halo::HaloMemory< HaloBlock_t >::HaloMemory(), and dash::Coevent::initialize().

{
  typedef typename GlobIterType::index_type index_t;
  typedef typename GlobIterType::value_type value_t;

  // Global iterators to local range:
  auto      index_range = dash::local_range(first, last);
  value_t * lfirst      = index_range.begin;
  value_t * llast       = index_range.end;

#ifdef DASH_ENABLE_OPENMP
  dash::util::UnitLocality uloc;
  auto n_threads = uloc.num_domain_threads();
  auto nlocal    = llast - lfirst;
  DASH_LOG_DEBUG("dash::fill", "thread capacity:",  n_threads);
  #pragma omp parallel for num_threads(n_threads)
  for (index_t lt = 0; lt < nlocal; ++lt) {
    lfirst[lt] = value;
  }

#else
  std::fill(lfirst, llast, value);
#endif
}

find()

template<typename GlobIter , typename ElementType >

GlobIter dash::find	(	GlobIter	first,
		GlobIter	last,
		const ElementType &	value
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Find.h>

Returns an iterator to the first element in the range [first,last) that compares equal to val.

If no such element is found, the function returns last.

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
value	Value which is searched for using operator==

Definition at line 22 of file Find.h.

References dart_allreduce(), DART_OK, DART_OP_MIN, dash::local_begin(), dash::local_index_range(), and dash::GlobIter< ElementType, PatternType, GlobMemType, PointerType, ReferenceType >::pos().

Referenced by dash::util::LocalityDomain::leader_unit(), and dash::coarray::sync_images().

{

  //use iterator traits
  using iterator_traits = dash::iterator_traits<GlobIter>;

  using p_index_t = typename iterator_traits::index_type;

  if(first >= last) {
    return last;
  }

  p_index_t g_index;
  auto & pattern     = first.pattern();
  auto & team        = pattern.team();
  auto index_range   = dash::local_index_range(first, last);
  auto l_begin_index = index_range.begin;
  auto l_end_index   = index_range.end;
  auto first_offset  = first.pos();
  if(l_begin_index == l_end_index){
    g_index = std::numeric_limits<p_index_t>::max();
  } else {
   auto g_begin_index = pattern.global(l_begin_index);

    // Pointer to first element in local memory:
   auto const* lbegin = dash::local_begin(
       static_cast<typename GlobIter::pointer>(first), team.myid());
   // Pointers to first / final element in local range:
   const auto l_range_begin = lbegin + l_begin_index;
   const auto l_range_end   = lbegin + l_end_index;

   DASH_LOG_DEBUG("local index range", l_begin_index, l_end_index);

   auto l_result = std::find(l_range_begin, l_range_end, value);
   if (l_result == l_range_end) {
     DASH_LOG_DEBUG("Not found in local range");
     g_index = std::numeric_limits<p_index_t>::max();
    } else {
      auto l_hit_index = l_result - lbegin;
      g_index = pattern.global(l_hit_index);
    }
  }
  team.barrier();

  // receive buffer for global maximal index
  p_index_t g_hit_idx;

  DASH_ASSERT_RETURNS(
      dart_allreduce(
        &g_index,
        &g_hit_idx,
        1,
        dart_datatype<p_index_t>::value,
        DART_OP_MIN,
        team.dart_id()),
      DART_OK);

  if (g_hit_idx == std::numeric_limits<p_index_t>::max()) {
    DASH_LOG_DEBUG("element not found");
  } else {
    return first + g_hit_idx;
  }
  return last;
}

find_if()

template<typename GlobIter , typename UnaryPredicate >

GlobIter dash::find_if	(	GlobIter	first,
		GlobIter	last,
		UnaryPredicate	predicate
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Find.h>

Returns an iterator to the first element in the range [first,last) that satisfies the predicate p.

If no such element is found, the function returns last.

See also

dash::find

dash::find_if_not

Global iterators to local range:

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
predicate	Predicate which will be applied to the elements in range [first, last)

Definition at line 104 of file Find.h.

References dash::distance(), dash::Array< ElementType, IndexType, PatternType, LocalMemSpaceT >::local, dash::local_range(), dash::myid(), and dash::GlobIter< ElementType, PatternType, GlobMemType, PointerType, ReferenceType >::pos().

Referenced by dash::any_of(), dash::EpochSynchronizedAllocator< ElementType, LMemSpace, AllocationPolicy, LocalAlloc >::deallocate(), dash::find_if_not(), dash::GlobLocalMemoryPool< dash::HostSpace >::flush_local(), and dash::EpochSynchronizedAllocator< ElementType, LMemSpace, AllocationPolicy, LocalAlloc >::get_local_allocator().

{
  using iterator_traits = dash::iterator_traits<GlobIter>;

  using index_t = typename iterator_traits::index_type;

  auto& team = first.pattern().team();
  auto  myid = team.myid();
  auto index_range = dash::local_range(first, last);
  auto l_first     = index_range.begin;
  auto l_last      = index_range.end;

  auto l_result = std::find_if(l_first, l_last, predicate);
  auto l_offset = l_result == l_last ? -1 : std::distance(l_first, l_result);

  dash::Array<index_t> l_results(team.size(), team);

  l_results.local[0] = l_offset;

  team.barrier();

  // All local offsets stored in l_results
  auto result = last;

  for (auto u = 0; u < team.size(); u++) {
    if (l_results[u] >= 0) {
      auto g_offset = first.pattern().global_index(u, {l_results[u]});
      result        = first + g_offset - first.pos();
      break;
    }
  }

  team.barrier();
  return result;
}

find_if_not()

template<typename GlobIter , class UnaryPredicate >

GlobIter dash::find_if_not	(	GlobIter	first,
		GlobIter	last,
		UnaryPredicate	predicate
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Find.h>

Returns an iterator to the first element in the range [first,last) that does not satisfy the predicate p.

If no such element is found, the function returns last.

See also

dash::find

dash::find_if_not

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
predicate	Predicate which will be applied to the elements in range [first, last)

Definition at line 160 of file Find.h.

References dash::find_if().

Referenced by dash::all_of().

{
  return find_if(first, last, std::not1(predicate));
}

for_each()

template<typename GlobInputIt , class UnaryFunction >

void dash::for_each	(	const GlobInputIt &	first,
		const GlobInputIt &	last,
		UnaryFunction	func
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/ForEach.h>

Invoke a function on every element in a range distributed by a pattern.

This function has the same signature as std::for_each but Being a collaborative operation, each unit will invoke the given function on its local elements only. To support compiler optimization, this const version is provided

Template Parameters

GlobIter	Global Iterator to iterate the sequence
UnaryFunction	Function to invoke for each element in the specified range with signature (void (const ElementType &)). Signature does not need to have (const &) but must be compatible to std::for_each.

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Global iterators to local index range:

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
func	Function to invoke on every index in the range

Definition at line 32 of file ForEach.h.

References dash::local(), and dash::local_index_range().

Referenced by dash::coarray::sync_images(), and dash::io::hdf5::StoreHDF::write().

{
  using iterator_traits = dash::iterator_traits<GlobInputIt>;
  static_assert(
      iterator_traits::is_global_iterator::value,
      "must be a global iterator");
  auto index_range  = dash::local_index_range(first, last);
  auto lbegin_index = index_range.begin;
  auto lend_index   = index_range.end;
  auto & team       = first.pattern().team();
  if (lbegin_index != lend_index) {
    // Pattern from global begin iterator:
    auto & pattern    = first.pattern();
    // Local range to native pointers:
    auto lrange_begin = (first + pattern.global(lbegin_index)).local();
    auto lrange_end   = lrange_begin + lend_index;
    std::for_each(lrange_begin, lrange_end, func);
  }
  team.barrier();
}

for_each_with_index()

template<typename GlobInputIt , class UnaryFunctionWithIndex >

void dash::for_each_with_index	(	const GlobInputIt &	first,
		const GlobInputIt &	last,
		UnaryFunctionWithIndex	func
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/ForEach.h>

Invoke a function on every element in a range distributed by a pattern.

Being a collaborative operation, each unit will invoke the given function on its local elements only. The index passed to the function is a global index.

Template Parameters

GlobIter	Global Iterator to iterate the sequence
UnaryFunctionWithIndex	Function to invoke for each element in the specified range with signature void (const ElementType &, index_t) Signature does not need to have (const &) but must be compatible to std::for_each.

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Global iterators to local index range:

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
func	Function to invoke on every index in the range

Definition at line 80 of file ForEach.h.

References dash::local_index_range().

{
  using iterator_traits = dash::iterator_traits<GlobInputIt>;
  static_assert(
      iterator_traits::is_global_iterator::value,
      "must be a global iterator");

  auto index_range  = dash::local_index_range(first, last);
  auto lbegin_index = index_range.begin;
  auto lend_index   = index_range.end;
  auto & team       = first.pattern().team();
  if (lbegin_index != lend_index) {
    // Pattern from global begin iterator:
    auto & pattern    = first.pattern();
    auto first_offset = first.pos();
    // Iterate local index range:
    for (auto lindex = lbegin_index;
         lindex != lend_index;
         ++lindex) {
      auto gindex       = pattern.global(lindex);
      auto element_it   = first + (gindex - first_offset);
      func(*(element_it.local()), gindex);
    }
  }
  team.barrier();
}

generate()

template<typename GlobInputIt , class UnaryFunction >

void dash::generate	(	GlobInputIt	first,
		GlobInputIt	last,
		UnaryFunction	gen
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Generate.h>

Assigns each element in range [first, last) a value generated by the given function object g.

Being a collaborative operation, each unit will invoke the given function on its local elements only.

Template Parameters

ElementType	Type of the elements in the sequence invoke, deduced from parameter gen
UnaryFunction	Unary function with signature ElementType(void)

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Global iterators to local range:

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
gen	Generator function

Definition at line 32 of file Generate.h.

References dash::local_range().

{
  using iterator_traits = dash::iterator_traits<GlobInputIt>;
  static_assert(
      iterator_traits::is_global_iterator::value,
      "must be a global iterator");
  auto lrange = dash::local_range(first, last);
  auto lfirst = lrange.begin;
  auto llast  = lrange.end;

  std::generate(lfirst, llast, gen);
}

generate_with_index()

template<typename GlobInputIt , class UnaryFunction >

void dash::generate_with_index	(	GlobInputIt	first,
		GlobInputIt	last,
		UnaryFunction	gen
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Generate.h>

Assigns each element in range [first, last) a value generated by the given function object g.

The index passed to the function is a global index.

Being a collaborative operation, each unit will invoke the given function on its local elements only.

Template Parameters

ElementType	Type of the elements in the sequence invoke, deduced from parameter gen
UnaryFunction	Unary function with signature ElementType(index_t)

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Global iterators to local index range:

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
gen	Generator function

Definition at line 71 of file Generate.h.

References dash::local_index_range().

{
  using iterator_traits = dash::iterator_traits<GlobInputIt>;
  static_assert(
      iterator_traits::is_global_iterator::value,
      "must be a global iterator");
  auto index_range  = dash::local_index_range(first, last);
  auto lbegin_index = index_range.begin;
  auto lend_index   = index_range.end;

  if (lbegin_index != lend_index) {
    // Pattern from global begin iterator:
    auto& pattern      = first.pattern();
    auto  first_offset = first.pos();
    // Iterate local index range:
    for (auto lindex = lbegin_index; lindex != lend_index; ++lindex) {
      auto gindex     = pattern.global(lindex);
      auto element_it = first + (gindex - first_offset);
      *element_it     = gen(gindex);
    }
  }
}

local_index_range()

template<class GlobInputIter >

std::enable_if< !GlobInputIter::has_view::value, LocalIndexRange<typename GlobInputIter::pattern_type::index_type>>::type dash::local_index_range	(	const GlobInputIter &	first,
		const GlobInputIter &	last
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/LocalRange.h>

Resolves the local index range between global iterators.

Example:

Total range	0 1 2 3 4 5 6 7 8 9
Global iterators	first = 4; last = 7;
	0 1 2 3 [4 5 6 7] 8 9]
Local elements	(local index:value) 0:2 1:3 2:6 3:7
Result	(local indices) 2 3

Returns

A local index range consisting of offsets of the first and last element in local memory within the sequence limited by the given global iterators.

Template Parameters

ElementType	Type of the elements in the sequence
PatternType	Type of the global iterators' pattern implementation

Time complexity

O(d), with d dimensions in the global iterators' pattern

Parameters

first	Iterator to the initial position in the global sequence
last	Iterator to the final position in the global sequence

Definition at line 101 of file LocalRange.h.

Referenced by dash::find(), dash::for_each(), dash::for_each_with_index(), dash::generate_with_index(), dash::local_range(), and dash::min_element().

{
  typedef typename GlobInputIter::pattern_type::index_type idx_t;

  typedef typename GlobInputIter::pattern_type pattern_t;
  typedef typename pattern_t::index_type       idx_t;
  // Get offsets of iterators within global memory, O(1):
  auto begin_gindex = static_cast<idx_t>(first.pos());
  auto end_gindex   = static_cast<idx_t>(last.pos());
  DASH_LOG_TRACE("local_index_range(GlobIt,GlobIt)",
                 begin_gindex, end_gindex);
  // Get pattern from global iterators, O(1):
  const auto& pattern = first.pattern();
  DASH_LOG_TRACE_VAR("local_index_range", pattern.local_size());
  if (pattern.local_size() == 0) {
    // Local index range is empty
    DASH_LOG_TRACE("local_index_range (lsize:0) ->", 0, 0);
    return LocalIndexRange<idx_t> { 0, 0 };
  }
  // Global index of first element in pattern, O(1):
  idx_t lbegin_gindex = pattern.lbegin();
  // Global index of last element in pattern, O(1):
  idx_t lend_gindex   = pattern.lend();
  DASH_LOG_TRACE_VAR("local_index_range", lbegin_gindex);
  DASH_LOG_TRACE_VAR("local_index_range", lend_gindex);
  if (lend_gindex   <= begin_gindex ||  // local end before global begin
      lbegin_gindex >= end_gindex) {    // local begin after global end
    // No overlap, intersection is empty
    DASH_LOG_TRACE("local_index_range (intersect:0) >", 0, 0);
    return LocalIndexRange<idx_t> { 0, 0 };
  }
  // Intersect local range and global range, in global index domain:
  auto goffset_lbegin = std::max<idx_t>(lbegin_gindex, begin_gindex);
  auto goffset_lend   = std::min<idx_t>(lend_gindex, end_gindex);
  // Global positions of local range to global coordinates, O(d):
  auto lbegin_gcoords = pattern.coords(goffset_lbegin);
  // Subtract 1 from global end offset as it points one coordinate
  // past the last index which is out of the valid coordinates range:
  auto lend_gcoords   = pattern.coords(goffset_lend-1);
  // Global coordinates of local range to local indices, O(d):
  auto lbegin_index   = pattern.at(lbegin_gcoords);
  // Add 1 to local end index to it points one coordinate past the
  // last index:
  auto lend_index     = pattern.at(lend_gcoords);
  if (lend_index
      == std::numeric_limits<typename pattern_t::index_type>::max()) {
    DASH_LOG_ERROR("local_index_range !",
                   "index type too small for for local index range");
  }
  lend_index += 1;
  // Return local index range
  DASH_LOG_TRACE("local_index_range >", lbegin_index, lend_index);
  return LocalIndexRange<idx_t> { lbegin_index, lend_index };
}

local_range()

template<class GlobIterType >

LocalRange<const typename GlobIterType::value_type> dash::local_range	(	const GlobIterType &	first,
		const GlobIterType &	last
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/LocalRange.h>

Resolves the local address range between global iterators.

Example:

Total range	a b c d e f g h i j
Global iterators	first = b; last = i;

| a b [c d e f g h] i j] Local elements | a b d e Result | d e

Returns

A local range consisting of native pointers to the first and last local element within the sequence limited by the given global iterators.

Time complexity

O(d), with d dimensions in the global iterators' pattern

Parameters

first	Iterator to the initial position in the global sequence
last	Iterator to the final position in the global sequence

Definition at line 295 of file LocalRange.h.

References dash::local_begin(), and dash::local_index_range().

Referenced by dash::equal(), dash::fill(), dash::find_if(), dash::generate(), and dash::reduce().

{
  typedef typename GlobIterType::pattern_type pattern_t;
  typedef typename GlobIterType::value_type   value_t;
  typedef typename pattern_t::index_type      idx_t;
  DASH_LOG_TRACE("local_range()",
                 "gfirst.pos:", first.pos(),
                 "glast.pos:",  last.pos());
  // Global iterators to local index range, O(d):
  auto index_range   = dash::local_index_range(first, last);
  idx_t lbegin_index = index_range.begin;
  idx_t lend_index   = index_range.end;
  if (lbegin_index == lend_index) {
    // Local range is empty
    DASH_LOG_TRACE("local_range >", "empty local range",
                   lbegin_index, lend_index);
    return LocalRange<const value_t> { nullptr, nullptr };
  }
  // Local start address from global memory:
  const auto& pattern = first.pattern();

  auto* lbegin = dash::local_begin(
      static_cast<typename GlobIterType::pointer>(first.globmem().begin()),
      first.team().myid());
  // Add local offsets to local start address:
  if (lbegin == nullptr) {
    DASH_LOG_TRACE("local_range >", "lbegin null");
    return LocalRange<const value_t> { nullptr, nullptr };
  }
  DASH_LOG_TRACE("local_range >",
                 "lbegin:",      lbegin,
                 "l_idx_range:", lbegin_index, "-", lend_index);
  return LocalRange<const value_t> {
           lbegin + lbegin_index,
           lbegin + lend_index };
}

max_element() [1/2]

template<class GlobIter , class Compare = std::greater<const typename GlobIter::value_type &>>

GlobIter dash::max_element	(	const GlobIter &	first,
		const GlobIter &	last,
		Compare	compare = Compare()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/MinMax.h>

Finds an iterator pointing to the element with the greatest value in the range [first,last).

Returns

An iterator to the first occurrence of the greatest value in the range, or last if the range is empty.

Template Parameters

ElementType	Type of the elements in the sequence
Compare	Binary comparison function with signature bool (const TypeA &a, const TypeB &b)

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
compare	Element comparison function, defaults to std::less

Definition at line 332 of file MinMax.h.

References dash::min_element().

Referenced by dash::LoadBalancePattern< 1, CompBasedMeasure, MemBasedMeasure, Arrangement, IndexType >::ndim(), dash::CSRPattern< 1, Arrangement, IndexType >::ndim(), and dash::DynamicPattern< 1, Arrangement, IndexType >::ndim().

{
  // Same as min_element with different compare function
  return dash::min_element(first, last, compare);
}

max_element() [2/2]

template<class ElementType , class Compare = std::greater<ElementType &>>

const ElementType* dash::max_element	(	const ElementType *	first,
		const ElementType *	last,
		Compare	compare = Compare()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/MinMax.h>

Finds an iterator pointing to the element with the greatest value in the range [first,last).

Specialization for local range, delegates to std::min_element.

Returns

An iterator to the first occurrence of the greatest value in the range, or last if the range is empty.

Template Parameters

ElementType	Type of the elements in the sequence
Compare	Binary comparison function with signature bool (const TypeA &a, const TypeB &b)

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
compare	Element comparison function, defaults to std::less

Definition at line 362 of file MinMax.h.

References dash::min_element().

{
  // Same as min_element with different compare function
  return dash::min_element(first, last, compare);
}

min_element() [1/2]

template<class ElementType , class Compare = std::less<const ElementType &>>

const ElementType* dash::min_element	(	const ElementType *	l_range_begin,
		const ElementType *	l_range_end,
		Compare	compare = std::less<const ElementType &>()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/MinMax.h>

Finds an iterator pointing to the element with the smallest value in the range [first,last).

Specialization for local range, delegates to std::min_element.

Returns

An iterator to the first occurrence of the smallest value in the range, or last if the range is empty.

Template Parameters

ElementType	Type of the elements in the sequence
Compare	Binary comparison function with signature bool (const TypeA &a, const TypeB &b)

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Parameters

l_range_begin	Iterator to the initial position in the sequence
l_range_end	Iterator to the final position in the sequence
compare	Element comparison function, defaults to std::less

Examples:

ex.05.min_element/main.cpp.

Definition at line 47 of file MinMax.h.

References dash::min_element(), and dash::util::UnitLocality::num_domain_threads().

Referenced by dash::max_element(), and dash::min_element().

{
#ifdef DASH_ENABLE_OPENMP
#define ROUNDUP(T, A) ((T + A - 1) & ~(A - 1))

  typedef typename std::decay<ElementType>::type      value_t;
  dash::util::UnitLocality uloc;
  //TODO: ask dyloc for available memory spaces
  auto n_threads = uloc.num_domain_threads();
  DASH_LOG_DEBUG("dash::min_element", "thread capacity:",  n_threads);

  // TODO: Should also restrict on elements/units > ~10240.
  //       Find a model for the minimum work laod.
  if (n_threads > 1) {
    auto          l_size     = l_range_end - l_range_begin;
    int           min_idx_l  = 0;
    ElementType   min_val_l  = *l_range_begin;

    typedef struct min_pos_t { value_t val; size_t idx; } min_pos;

    DASH_LOG_TRACE("dash::min_element", "sizeof(min_pos):", sizeof(min_pos));

    dash::HostSpace hostSpace;

    int       align_bytes         = uloc.cache_line_size(0);
    int       single_element_sz   = ROUNDUP(sizeof(min_pos), align_bytes);

    size_t    min_vals_t_bytes    = single_element_sz * n_threads;

    auto min_vals_t_raw = static_cast<uint8_t *>(
        hostSpace.allocate(min_vals_t_bytes, align_bytes));

    DASH_LOG_TRACE("dash::min_element", "min * alloc:",   min_vals_t_raw);
    //DASH_LOG_TRACE("dash::min_element", "min * aligned:", min_vals_t);
    DASH_LOG_TRACE("dash::min_element", "min * size:",    min_vals_t_bytes);
    DASH_ASSERT_GE(min_vals_t_bytes, n_threads * sizeof(min_pos),
                   "Aligned buffer of min_pos has insufficient size");
    DASH_ASSERT_MSG(nullptr != min_vals_t_raw,
                    "Aligned allocation of min_pos returned nullptr");

    // Cannot use user-defined reduction (OpenMP 4.0) as the compare
    // predicate cannot be used in `omp declare reduction`.
    // Avoid omp for + omp critical section by using array of
    // thread-local minimum values, aligned to prevent false sharing:
    int t_id;
    #pragma omp parallel num_threads(n_threads) private(t_id)
    {
      // Documentation of Intel MIC intrinsics, see:
      // https://software.intel.com/de-de/node/523533
      // https://software.intel.com/de-de/node/523387
      t_id = omp_get_thread_num();
      DASH_LOG_TRACE("dash::min_element", "starting thread", t_id);
      auto & min_val_t = *(reinterpret_cast<min_pos *>(min_vals_t_raw + t_id * single_element_sz));
      min_val_t.idx = min_idx_l;
      min_val_t.val = min_val_l;
      // Cannot use explicit private(min_val_t) as ElementType might
      // not be default-constructible:
      #pragma omp for schedule(static)
      for (int i = 0; i < l_size; i++) {
        const ElementType & val_t = *(l_range_begin + i);
        if (compare(val_t, min_val_t.val)) {
          min_val_t.val = val_t;
          min_val_t.idx = i;
        }
      }
      DASH_LOG_TRACE("dash::min_element", "local minimum at thread", t_id,
                     "idx:", min_val_t.idx,
                     "val:", min_val_t.val);
    }

    min_pos min_pos_l = * (reinterpret_cast<min_pos *>(min_vals_t_raw));

    for (int t = 1; t < n_threads; t++) {
      const min_pos & mpt = *(reinterpret_cast<min_pos *>(min_vals_t_raw + t * single_element_sz));
      if (compare(mpt.val, min_pos_l.val)) {
        min_pos_l = mpt;
      }
    }

    hostSpace.deallocate(min_vals_t_raw, min_vals_t_bytes, align_bytes);

    return (l_range_begin + min_pos_l.idx);
  }
#endif // DASH_ENABLE_OPENMP
  return ::std::min_element(l_range_begin, l_range_end, compare);
}

min_element() [2/2]

template<typename GlobInputIt , class Compare = std::less< const typename dash::iterator_traits<GlobInputIt>::value_type &>>

GlobInputIt dash::min_element	(	const typename std::enable_if< dash::iterator_traits< GlobInputIt >::is_global_iterator::value, GlobInputIt >::type &	first,
		const GlobInputIt &	last,
		Compare	compare = Compare()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/MinMax.h>

Finds an iterator pointing to the element with the smallest value in the range [first,last).

Returns

An iterator to the first occurrence of the smallest value in the range, or last if the range is empty.

Template Parameters

ElementType	Type of the elements in the sequence
Compare	Binary comparison function with signature bool (const TypeA &a, const TypeB &b)

Time complexity

O(d) + O(nl), with d dimensions in the global iterators' pattern and nl local elements within the global range

Parameters

first	Iterator to the initial position in the sequence
last	Iterator to the final position in the sequence
compare	Element comparison function, defaults to std::less

Definition at line 161 of file MinMax.h.

References dart_allgather(), DART_OK, DART_TYPE_BYTE, dash::local_begin(), dash::local_index_range(), and dash::min_element().

Referenced by dash::min_element().

{
  typedef typename GlobInputIt::pattern_type     pattern_t;
  typedef typename pattern_t::index_type         index_t;
  typedef typename std::decay<
      typename dash::iterator_traits<GlobInputIt>::value_type>::type value_t;

  // return last for empty array
  if (first == last) {
    DASH_LOG_DEBUG("dash::min_element >",
                   "empty range, returning last", last);
    return last;
  }

  dash::util::Trace trace("min_element");

  auto & pattern = first.pattern();
  auto & team    = pattern.team();
  DASH_LOG_DEBUG("dash::min_element()",
                 "allocate minarr, size", team.size());
  // Global position of end element in range:
  auto    gi_last            = last.gpos();
  // Find the local min. element in parallel
  // Get local address range between global iterators:
  auto    local_idx_range    = dash::local_index_range(first, last);
  // Pointer to local minimum element:
  const   value_t * lmin = nullptr;
  // Local offset of local minimum element, or -1 if no element found:
  index_t l_idx_lmin         = -1;
  if (local_idx_range.begin == local_idx_range.end) {
    // local range is empty
    DASH_LOG_DEBUG("dash::min_element", "local range empty");
  } else {
    trace.enter_state("local");

    // Pointer to first element in local memory:
    auto *lbegin = dash::local_begin(
        static_cast<typename GlobInputIt::const_pointer>(first), team.myid());

    // Pointers to first / final element in local range:
    const auto * l_range_begin = lbegin + local_idx_range.begin;
    const auto * l_range_end   = lbegin + local_idx_range.end;

    lmin = dash::min_element(l_range_begin, l_range_end, compare);

    if (lmin != l_range_end) {
      DASH_LOG_TRACE_VAR("dash::min_element", *lmin);
      // Offset of local minimum in local memory:
      l_idx_lmin = lmin - lbegin;
    }

    trace.exit_state("local");
  }
  DASH_LOG_TRACE("dash::min_element",
                 "local index of local minimum:", l_idx_lmin);
  DASH_LOG_TRACE("dash::min_element",
                 "waiting for local min of other units");

  trace.enter_state("barrier");
  team.barrier();
  trace.exit_state("barrier");

  typedef struct {
    value_t  value;
    index_t  g_index;
  } local_min_t;

  std::vector<local_min_t> local_min_values(team.size());

  // Set global index of local minimum to -1 if no local minimum has been
  // found:
  local_min_t local_min;
  local_min.value   = l_idx_lmin < 0
                      ? value_t()
                      : *lmin;
  local_min.g_index = l_idx_lmin < 0
                      ? -1
                      : pattern.global(l_idx_lmin);

  DASH_LOG_TRACE("dash::min_element", "sending local minimum: {",
                 "value:",   local_min.value,
                 "g.index:", local_min.g_index, "}");

  DASH_LOG_TRACE("dash::min_element", "dart_allgather()");
  trace.enter_state("allgather");
  DASH_ASSERT_RETURNS(
    dart_allgather(
      &local_min,
      local_min_values.data(),
      sizeof(local_min_t),
      DART_TYPE_BYTE,
      team.dart_id()),
    DART_OK);
  trace.exit_state("allgather");

#ifdef DASH_ENABLE_LOGGING
  for (int lmin_u = 0; lmin_u < local_min_values.size(); lmin_u++) {
    auto lmin_entry = local_min_values[lmin_u];
    DASH_LOG_TRACE("dash::min_element", "dart_allgather >",
                   "unit:",    lmin_u,
                   "value:",   lmin_entry.value,
                   "g_index:", lmin_entry.g_index);
  }
#endif

  auto gmin_elem_it  = ::std::min_element(
                           local_min_values.begin(),
                           local_min_values.end(),
                           [&](const local_min_t & a,
                               const local_min_t & b) {
                             // Ignore elements with global index -1 (no
                             // element found):
                             return (b.g_index < 0 ||
                                     (a.g_index > 0 &&
                                      compare(a.value, b.value)));
                           });

  if (gmin_elem_it == local_min_values.end()) {
    DASH_LOG_DEBUG_VAR("dash::min_element >", last);
    return last;
  }

  auto gi_minimum    = gmin_elem_it->g_index;

  DASH_LOG_TRACE("dash::min_element",
                 "min. value:", gmin_elem_it->value,
                 "at unit:",    (gmin_elem_it - local_min_values.begin()),
                 "global idx:", gi_minimum);

  DASH_LOG_TRACE_VAR("dash::min_element", gi_minimum);
  if (gi_minimum < 0 || gi_minimum == gi_last) {
    DASH_LOG_DEBUG_VAR("dash::min_element >", last);
    return last;
  }
  // iterator 'first' is relative to start of input range, convert to start
  // of its referenced container (= container.begin()), then apply global
  // offset of minimum element:
  auto minimum = (first - first.gpos()) + gi_minimum;
  DASH_LOG_DEBUG("dash::min_element >", minimum,
                 "=", static_cast<value_t>(*minimum));

  return minimum;
}

reduce() [1/3]

template<class LocalInputIter , class InitType , class BinaryOperation = dash::plus<typename std::iterator_traits<LocalInputIter>::value_type>, typename = typename std::enable_if< !dash::detail::is_global_iterator<LocalInputIter>::value >::type>

std::iterator_traits<LocalInputIter>::value_type dash::reduce	(	LocalInputIter	in_first,
		LocalInputIter	in_last,
		InitType	init,
		BinaryOperation	binary_op = BinaryOperation(),
		bool	non_empty = true,
		dash::Team &	team = dash::Team::All()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Reduce.h>

Accumulate values in each process' range [in_first, in_last) using the provided binary reduce function binary_op, which must be commutative and associative.

The iteration order is not specified and the result is non-deterministic if binary_op is not commutative and associative.

The result type is determined by the type of the elements in the range and the value of init is cast to this type.

Collective operation.

Parameters

in_first	Local iterator describing the beginning of the range to reduce.
in_last	Local iterator describing the end of the range to accumualte
init	The initial element to use in the accumulation.
binary_op	The binary operation to apply to reduce two elements (default: using dash::plus)
non_empty	Whether all units are guaranteed to provide a non-empty local range (default false).
team	The team to use for the collective operation.

Definition at line 79 of file Reduce.h.

References DART_OP_UNDEFINED, and dash::myid().

Referenced by dash::reduce().

{
  using value_t    = typename std::iterator_traits<LocalInputIter>::value_type;
  using local_result_t = struct dash::internal::local_result<value_t>;
  auto myid        = team.myid();
  auto l_first     = in_first;
  auto l_last      = in_last;

  local_result_t l_result;
  local_result_t g_result;
  if (l_first != l_last) {
    l_result.value = std::accumulate(std::next(l_first),
                                     l_last, *l_first,
                                     binary_op);
    l_result.valid = true;
  }
  dart_operation_t dop =
                  dash::internal::dart_reduce_operation<BinaryOperation>::value;
  dart_datatype_t  dtype = dash::dart_storage<value_t>::dtype;

  if (!non_empty || dop == DART_OP_UNDEFINED || dtype == DART_TYPE_UNDEFINED)
  {
    dart_type_create_custom(sizeof(local_result_t), &dtype);

    // we need a custom reduction operation because not every unit
    // may have valid values
    dart_op_create(
      &dash::internal::reduce_custom_fn<value_t, BinaryOperation>,
      &binary_op, true, dtype, true, &dop);
    dart_allreduce(&l_result, &g_result, 1, dtype, dop, team.dart_id());
    dart_op_destroy(&dop);
    dart_type_destroy(&dtype);
  } else {
    // ideal case: we can use DART predefined reductions
    dart_allreduce(&l_result.value, &g_result.value, 1, dtype, dop, team.dart_id());
    g_result.valid = true;
  }
  if (!g_result.valid) {
    DASH_LOG_ERROR("dash::reduce()", "Found invalid reduction value!");
  }
  auto result = g_result.value;

  result = binary_op(init, result);

  return result;
}

reduce() [2/3]

template<class LocalInputIter , class InitType = typename std::iterator_traits<LocalInputIter>::value_type, typename = typename std::enable_if< !dash::detail::is_global_iterator<LocalInputIter>::value >::type>

std::iterator_traits<LocalInputIter>::value_type dash::reduce	(	LocalInputIter	in_first,
		LocalInputIter	in_last,
		InitType	init,
		bool	non_empty,
		dash::Team &	team = dash::Team::All()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Reduce.h>

Accumulate values across the local ranges [in_first,in_last) of each process as the sum of all values in the range.

The iteration order is not specified. The reduction is performed using dash::plus.

The result type is determined by the type of the elements in the range and the value of init is cast to this type.

Note

: For equivalent of semantics of MPI_Accumulate, see dash::transform.

Parameters

in_first	Local pointer describing the beginning of the range to reduce.
in_last	Local pointer describing the end of the range to accumualte
init	The initial element to use in the accumulation.
non_empty	Whether all units are guaranteed to provide a non-empty local range (default false).
team	The team to use for the collective operation.

Definition at line 162 of file Reduce.h.

References dash::reduce().

{
  using value_t = typename std::iterator_traits<LocalInputIter>::value_type;
  return dash::reduce(
            in_first,
            in_last,
            init,
            dash::plus<value_t>(),
            non_empty,
            team);
}

reduce() [3/3]

template<class GlobInputIt , class InitType = typename dash::iterator_traits<GlobInputIt>::value_type, class BinaryOperation = dash::plus<typename dash::iterator_traits<GlobInputIt>::value_type>, typename = typename std::enable_if< dash::detail::is_global_iterator<GlobInputIt>::value >::type>

dash::iterator_traits<GlobInputIt>::value_type dash::reduce	(	GlobInputIt	in_first,
		GlobInputIt	in_last,
		InitType	init,
		BinaryOperation	binary_op = BinaryOperation()
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Reduce.h>

Accumulate values in the global range [in_first, in_last) using the provided binary reduce function binary_op, which must be commutative and linear.

The iteration order is not specified and the result is non-deterministic if binary_op is not commutative and associative.

The result type is determined by the type of the elements in the range and the value of init is cast to this type.

Collective operation.

Parameters

in_first	Global iterator describing the beginning of the range to reduce.
in_last	Global iterator describing the end of the range to accumualte
init	The initial element to use in the accumulation.
binary_op	The associative, commutative binary operation to apply.

Note

: For equivalent of semantics of MPI_Accumulate, see dash::transform.

Definition at line 212 of file Reduce.h.

References dash::local_range(), and dash::reduce().

{
  auto & team      = in_first.team();
  auto index_range = dash::local_range(in_first, in_last);
  auto l_first     = index_range.begin;
  auto l_last      = index_range.end;

  // TODO: can we figure out whether or not units are empty?
  static constexpr bool units_non_empty = false;
  return dash::reduce(l_first,
                      l_last,
                      init,
                      binary_op,
                      units_non_empty,
                      team);
}

sort() [1/2]

template<class GlobRandomIt >

void dash::sort	(	GlobRandomIt	begin,
		GlobRandomIt	end
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Sort.h>

Sorts the elements in the range, defined by [begin, end) in ascending order.

The order of equal elements is not guaranteed to be preserved.

Elements are sorted using operator<. Additionally, the elements must be arithmetic, i.e. std::is_arithmetic<T> must be satisfied.

In terms of data distribution, source and destination ranges passed to dash::sort must be global (GlobIter<ValueType>).

The operation is collective among the team of the owning dash container.

Example:

dash::Array<int> arr(100);
dash::generate(arr.begin(), arr.end());
dash::sort(array.begin(),
           array.end();

sort() [2/2]

template<class GlobRandomIt , class SortableHash >

void dash::sort	(	GlobRandomIt	begin,
		GlobRandomIt	end,
		SortableHash	hash
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Sort.h>

Sorts the elements in the range, defined by [begin, end) in ascending order.

The order of equal elements is not guaranteed to be preserved.

Elements are sorted by using a user-defined hash function. Resulting values of the hash function are required to be sortable by operator<.

This variant may be appropriate if the underlying container does not hold arithmetic values (e.g. structs).

In terms of data distribution, source and destination ranges passed to dash::sort must be global (GlobIter<ValueType>).

The operation is collective among the team of the owning dash container.

Example:

struct pair { int x; int y; };
dash::Array<pair> arr(100);
dash::generate(arr.begin(), arr.end(), random());
dash::sort(array.begin(),
           array.end(),
           [](pair const & p){return p.x % 13; }
          );

transform() [1/2]

template<typename ValueType , class InputIt , class OutputIt , class UnaryOperation >

OutputIt dash::transform	(	InputIt	in_first,
		InputIt	in_last,
		OutputIt	out_first,
		UnaryOperation	unary_op
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Transform.h>

Apply a given function to elements in a range and store the result in another range, beginning at out_first.

Corresponding to MPI_Accumulate, the unary operation is executed atomically on single elements.

Precondition: All elements in the input range are contained in a single block so that

g_out_last == g_out_first + (l_in_last - l_in_first)

Semantics:

unary_op(in_first[0]), unary_op(in_first[1]), ..., unary_op(in_first[n])

Returns

Output iterator to the element past the last element transformed.

Referenced by dash::LoadBalancePattern< 1, CompBasedMeasure, MemBasedMeasure, Arrangement, IndexType >::ndim(), and dash::UnitClockFreqMeasure::unit_weights().

transform() [2/2]

template<class InputIt1 , class GlobInputIt , class GlobOutputIt , class BinaryOperation >

GlobOutputIt dash::transform	(	InputIt1	in_a_first,
		InputIt1	in_a_last,
		GlobInputIt	in_b_first,
		GlobOutputIt	out_first,
		BinaryOperation	binary_op
	)

#include </tmp/tmporruphar/dash/include/dash/algorithm/Transform.h>

Apply a given function to pairs of elements from two ranges and store the result in another range, beginning at out_first.

Corresponding to MPI_Accumulate, the binary operation is executed atomically on single elements.

Precondition: All elements in the input range are contained in a single block so that

g_out_last == g_out_first + (l_in_last - l_in_first)

Semantics:

binary_op(in_a[0], in_b[0]), binary_op(in_a[1], in_b[1]), ..., binary_op(in_a[n], in_b[n])

Example:

gptr_diff_t num_transformed_elements =
              dash::distance(
                dash::transform(in.begin(), in.end(),  // A
                                out.begin(),           // B
                                out.begin(),           // C = op(A, B)
                                dash::plus<int>()),    // op
                out.end());

Returns

Output iterator to the element past the last element transformed.

See also

dash::reduce

DASH Reduce Operations

Template Parameters

InputIt	Iterator on first (local) input range
GlobInputIt	Iterator on second (global) input range
GlobOutputIt	Iterator on global result range
BinaryOperation	Reduce operation type

Parameters

in_a_first	Iterator on begin of first local range
in_a_last	Iterator after last element of local range
in_b_first	Iterator on begin of second local range
out_first	Iterator on first element of global output range
binary_op	Reduce operation