jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg > Class Template Reference

#include <subdivide_n_gen_wk.hpp>

Inheritance diagram for jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >:

Collaboration diagram for jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >:

Public Types
typedef subdivide_n_gen_wk< Ps, TPB, alg_wrapper1< typename TPB::pool_traits_type, Alg< Conts, Fn >, TPB::pool_traits_type::result_traits_ > >	base_t
typedef base_t::container_type	container_type
typedef base_t::in_iterator	in_iterator
typedef base_t::operation_type	operation_type
typedef base_t::result_type	result_type
typedef base_t::alg_wrap_t	alg_wrap_t
typedef base_t::thread_pool_type	thread_pool_type
typedef base_t::pool_traits_type	pool_traits_type
typedef base_t::os_traits	os_traits
typedef base_t::ensure_wk_complete_t	ensure_wk_complete_t
typedef base_t::algo_work_heap_type	algo_work_heap_type

Public Member Functions
__stdcall	subdivide_n_gen_wk1 (thread_pool_type &p, operation_type &f, typename alg_wrap_t::work_complete_t &w, algo_work_heap_type const &wh, typename std::iterator_traits< in_iterator >::difference_type const number_subranges, typename thread_pool_type::pool_type::size_type const cliques) noexcept(true) FORCE_INLINE
void __fastcall	process () noexcept(false)
	Recursively call subdivide_n_gen_wk1::process(), on disjoint left and right-subsets (assuming even numbers of processors in the clique) of the input collection, until the number of work items generated is 2^n just larger than the number of threads in the pool, which implements a form of GSS(k) scheduling. More...
constexpr bool __fastcall	operator< (subdivide_n_gen_wk1 const &) const noexcept(true) FORCE_INLINE

Static Public Member Functions
static thread_pool_type::pool_type::size_type	compute_threads_per_clique (typename thread_pool_type::pool_type::size_type num_threads, typename thread_pool_type::pool_type::size_type const cliques) noexcept(true) FORCE_INLINE
static thread_pool_type::pool_type::size_type	compute_buffer_items (typename thread_pool_type::pool_type::size_type const num_threads_per_clique) noexcept(true) FORCE_INLINE

Static Public Attributes
static constexpr ppd::generic_traits::memory_access_modes	memory_access_mode

Detailed Description

template<pool_traits::size_mode_t Ps, class TPB, class Fn, class Conts, template< class, class > class Alg>
class jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >

This recursive process ensures that it takes O(log(n)) time to submit the work to the pool.

Algorithm derived from [1]. Note that if the wrapped collection implements CREW or EREW semantics, as safe_colln does, then this algorithm is an implementation CREW/EREW P-RAM model, therefore if the thread_pool is large enough, it implements an optimal schedule according to section 3.3 & Theorem 3.3 in [1].

[1] Alan Gibbons, Wojciech Rytter, "Efficient Parallel Algorithms", Cambridge University Press, 1989.

See also

safe_colln

Definition at line 621 of file subdivide_n_gen_wk.hpp.

Member Typedef Documentation

alg_wrap_t

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::alg_wrap_t jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::alg_wrap_t

Definition at line 644 of file subdivide_n_gen_wk.hpp.

algo_work_heap_type

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::algo_work_heap_type jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::algo_work_heap_type

Definition at line 649 of file subdivide_n_gen_wk.hpp.

base_t

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef subdivide_n_gen_wk< Ps, TPB, alg_wrapper1< typename TPB::pool_traits_type, Alg<Conts, Fn>, TPB::pool_traits_type::result_traits_ > > jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::base_t

Definition at line 639 of file subdivide_n_gen_wk.hpp.

container_type

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::container_type jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::container_type

Definition at line 640 of file subdivide_n_gen_wk.hpp.

ensure_wk_complete_t

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::ensure_wk_complete_t jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::ensure_wk_complete_t

Definition at line 648 of file subdivide_n_gen_wk.hpp.

in_iterator

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::in_iterator jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::in_iterator

Definition at line 641 of file subdivide_n_gen_wk.hpp.

operation_type

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::operation_type jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::operation_type

Definition at line 642 of file subdivide_n_gen_wk.hpp.

os_traits

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::os_traits jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::os_traits

Definition at line 647 of file subdivide_n_gen_wk.hpp.

pool_traits_type

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::pool_traits_type jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::pool_traits_type

Definition at line 646 of file subdivide_n_gen_wk.hpp.

result_type

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::result_type jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::result_type

Definition at line 643 of file subdivide_n_gen_wk.hpp.

thread_pool_type

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

typedef base_t::thread_pool_type jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::thread_pool_type

Definition at line 645 of file subdivide_n_gen_wk.hpp.

Constructor & Destructor Documentation

subdivide_n_gen_wk1()

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::subdivide_n_gen_wk1 ( thread_pool_type &  p, operation_type &  f, typename alg_wrap_t::work_complete_t &  w, algo_work_heap_type const &  wh, typename std::iterator_traits< in_iterator >::difference_type const  number_subranges, typename thread_pool_type::pool_type::size_type const  cliques  )

inlinenoexcept

Definition at line 356 of file subdivide_n_gen_wk_impl.hpp.

Member Function Documentation

compute_buffer_items()

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

subdivide_n_gen_wk< Ps, TPB, Alg >::thread_pool_type::pool_type::size_type jmmcg::ppd::private_::subdivide_n_gen_wk< Ps, TPB, Alg >::compute_buffer_items

inlinestaticnoexcept

This computation is intimately related to the way subdivide_n_gen_wk::process() spawns sub-tasks, and the two must operate in a similar manner, otherwise we might get memory-allocation errors. Note that it over-allocates memory, because it doesn't allow for memory re-use: children could re-use memory of parents.

Todo:

This is an O(n) operation, and we might want a faster algorithm, it doesn't have to be perfect, as long as the result is >= the true value.

Returns

The number of items allocated in the tree that subdivide_n_gen_wk::process() will generate. Not in bytes, but items.

See also

subdivide_n_gen_wk::process()

Definition at line 116 of file subdivide_n_gen_wk_impl.hpp.

compute_threads_per_clique()

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

subdivide_n_gen_wk< Ps, TPB, Alg >::thread_pool_type::pool_type::size_type jmmcg::ppd::private_::subdivide_n_gen_wk< Ps, TPB, Alg >::compute_threads_per_clique

inlinestaticnoexcept

Definition at line 107 of file subdivide_n_gen_wk_impl.hpp.

operator<()

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

constexpr bool __fastcall jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::operator< ( subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg > const &  ) const

inlineconstexprnoexcept

Definition at line 678 of file subdivide_n_gen_wk.hpp.

References jmmcg::ppd::private_::priority_t< joinable_t, TPB, Pri >::operator<<().

process()

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

void jmmcg::ppd::private_::subdivide_n_gen_wk1< Ps, TPB, Fn, Conts, Alg >::process ( )

inlinenoexcept

Recursively call subdivide_n_gen_wk1::process(), on disjoint left and right-subsets (assuming even numbers of processors in the clique) of the input collection, until the number of work items generated is 2^n just larger than the number of threads in the pool, which implements a form of GSS(k) scheduling.

As the subsets are disjoint inter-subset operations are effectively CRCW operations, whereas intra-subset operations are strictly EREW. This subdivision is valid according to Proposition 1.1 in section 1.2 and Brent's Theorem [1].

[1] Casanova, H., Legrand, A., Robert, Y., "Parallel Algorithms", CRC Press, 2008.

See also

nonjoinable, nonjoinable_buff

Definition at line 363 of file subdivide_n_gen_wk_impl.hpp.

Member Data Documentation

memory_access_mode

template<pool_traits::size_mode_t Ps, class TPB , class Fn , class Conts , template< class, class > class Alg>

constexpr ppd::generic_traits::memory_access_modes jmmcg::ppd::private_::subdivide_n_gen_wk< Ps, TPB, Alg >::memory_access_mode

staticconstexpr

To assist in allowing compile-time computation of the algorithmic order of the threading model.

Definition at line 466 of file subdivide_n_gen_wk.hpp.

---

The documentation for this class was generated from the following files:

• core/private_/subdivide_n_gen_wk.hpp
• core/private_/subdivide_n_gen_wk_impl.hpp