STAPL API Reference          
Overview   Containers   Algorithms   Views   Skeletons   Run-Time System
Modules     Classes    
Classes | Modules | Typedefs | Functions
Functional Definition of Skeletons

The functional definition of skeletons which can be composed and transformed in the Skeletons Framework. More...

+ Collaboration diagram for Functional Definition of Skeletons:

Classes

struct  stapl::skeletons::skeletons_impl::expand_from_pow_two< Op, Span, pos_aware, stapl::use_default, SetResult >
 This class abstracts the semantics of an expansion skeleton by exposing only the necessary information in its representation. More...
 
struct  stapl::skeletons::skeletons_impl::reduce< Op, Flows, Span, Tag >
 This class abstracts the semantics of a reduce skeleton by exposing only the necessary information in its representation. More...
 
struct  stapl::skeletons::skeletons_impl::scan< Op, tags::scan< Tag, tags::inclusive > >
 Most of the inclusive scan skeletons cannot work directly on inputs with non-power-of-two sizes. As a result, we have to first convert the input to the closest power of two and then perform the scan operation. More...
 
struct  stapl::skeletons::skeletons_impl::scan< Op, tags::scan< Tag, tags::exclusive > >
 Most of the exclusive scan skeletons cannot work directly on inputs with non-power-of-two sizes. As a result, we have to first convert the input to the closest power of two and then perform the scan operation. More...
 
class  stapl::skeletons::skeletons_impl::skeleton_traits< tuple< OptionalPreParams... >, OptionalParams... >
 Skeleton traits define configurable properties of a skeleton. More...
 

Modules

 Functional Definition of
 
 Functional Definition of
 
 Functional Definition of
 
 Functional Definition of
 
 Functional Definition of
 

Typedefs

template<typename Tag , typename Op >
using stapl::skeletons::result_of::scan = typename std::conditional< std::is_same< tags::binomial, typename skeletons_impl::scan_algorithm_tag_type< Tag >::type >::value||std::is_same< tags::hillis_steele, typename skeletons_impl::scan_algorithm_tag_type< Tag >::type >::value, skeletons_impl::inclusive_scan< typename std::decay< Op >::type, typename skeletons_impl::scan_algorithm_tag_type< Tag >::type >, skeletons_impl::scan< typename std::decay< Op >::type, Tag > >::type
 Hillis-Steele scan can work on inputs with non-power-of-two sizes, therefore, we do not need to wrap it with extra steps.
 

Functions

template<typename Span = stapl::use_default>
result_of::bitreversal< Span > stapl::skeletons::bitreversal (void)
 This skeleton can be used with skeletons that need their input to be permuted in a bitreversed order such as Cooley Tukey FFT skeletons. More...
 
template<typename ValueType , typename SkeletonTraits = skeletons_impl::default_skeleton_traits>
result_of::copy< ValueType, SkeletonTraits > stapl::skeletons::copy (SkeletonTraits &&traits=SkeletonTraits())
 A copy skeleton is used when writes to views are happening. The second flow to this skeleton will be writable. More...
 
template<typename Span = stapl::use_default, bool pos_aware = false, bool SetResult = false, typename Op , typename Filter = skeletons::no_filter>
result_of::expand_from_pow_two< Span, pos_aware, Op, Filter, SetResult > stapl::skeletons::expand_from_pow_two (Op &&op, Filter &&filter=Filter())
 This skeleton is used as the post-processing phase of various skeletons including broadcast, n-partition, etc. Basically, this skeleton tries to expand the result of a pow-of-two skeleton to the given non-pow-of-two size. More...
 
template<typename ValueType >
result_of::inner_product< ValueType > stapl::skeletons::inner_product ()
 Inner product skeleton specified in terms of the zip_reduce skeleton. More...
 
template<typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename = typename std::enable_if< !is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::map< Op, SkeletonTraits > stapl::skeletons::map (Op &&op, SkeletonTraits &&traits=SkeletonTraits())
 A filtered map is similar to map skeleton but it applies a filter function on the producer side before sending data along the edges to each parametric dependency. More...
 
template<typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename ExecutionParams = skeletons_impl::default_execution_params, typename = typename std::enable_if< is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::map< decltype(skeletons::transform< tags::nest > std::declval< Op >), std::declval< ExecutionParams >))), SkeletonTraits > stapl::skeletons::map (Op &&op, SkeletonTraits &&traits=SkeletonTraits(), ExecutionParams &&execution_params=ExecutionParams())
 Creates a nested skeleton composition by transforming the inner skeleton to a suitable skeleton for nested execution. More...
 
template<typename MapOp , typename RedOp >
result_of::map_reduce< MapOp, RedOp > stapl::skeletons::map_reduce (MapOp &&map_op, RedOp &&red_op)
 As its name implies it creates a map reduce skeleton by piping the result of a map skeleton to a reduce skeleton. More...
 
template<int NotifCount = 1, typename Span = stapl::use_default, typename Flows = stapl::use_default, typename Op , typename Filter = skeletons::no_filter>
result_of::notify_map< NotifCount, Span, Flows, Op, Filter > stapl::skeletons::notify_map (Op &&op, Filter &&filter=Filter())
 A notify_map is similar to map skeleton but it also depends on a notification from the first NotifCount flows passed to it. More...
 
template<std::size_t Arity = 1, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits>
result_of::pre_broadcast< Arity, Op, SkeletonTraits > stapl::skeletons::pre_broadcast (Op &&op, SkeletonTraits &&traits=SkeletonTraits())
 This skeleton chooses an element from the domain of the input for broadcast when the input domain is non-scalar and we want to broadcast one element from the domain (e.g. last one). More...
 
template<typename Tag , typename Op >
result_of::inclusive_scan< Tag, Op > stapl::skeletons::inclusive_scan (Op const &op)
 An inclusive scan is a scan in which each element in the output is the result of cumulative application of the operation on the elements before it including itself. More...
 
template<typename Tag , typename Op , typename T >
result_of::exclusive_scan< Tag, Op, T > stapl::skeletons::exclusive_scan (Op const &op, T const &initial_value)
 An exclusive scan is a scan in which each element in the output is the result of cumulative application of the operation on the elements before it. More...
 
template<typename T , typename Tag = stapl::use_default, typename Span = stapl::use_default>
result_of::scatter< T, Tag, Span > stapl::skeletons::scatter (void)
 This sink skeleton assumes a default span for the created skeleton. More...
 
template<int i, typename Op >
result_of::serial< i, Op > stapl::skeletons::serial (Op &&op, std::size_t number_of_sets)
 Construct and execute a skeleton that performs a set of serial computations. More...
 
template<std::size_t Arity = 1, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits>
result_of::set_result< Arity, Op, SkeletonTraits > stapl::skeletons::set_result (Op &&op, SkeletonTraits &&traits=SkeletonTraits())
 the skeleton which is used to specify which tasks should put their results on the environment result container according to the span which is passed in the traits More...
 
template<typename ValueType , typename Span = stapl::use_default, typename SrcSkeleton , typename DestSkeleton = decltype(skeletons::copy<ValueType>(skeleton_traits<Span>()))>
result_of::sink< ValueType, SrcSkeleton, DestSkeleton > stapl::skeletons::sink (SrcSkeleton &&skeleton, DestSkeleton &&dest_skeleton=skeletons::copy< ValueType >(skeleton_traits< Span >()))
 This sink skeleton assumes a default span for the created skeleton. More...
 
template<typename ValueType , typename Span = spans::per_location, typename Skeleton >
result_of::sink_value< ValueType, decltype(skeleton_traits< Span, true >)), Skeleton > stapl::skeletons::sink_value (Skeleton &&skeleton)
 This sink skeleton assumes a default destination skeleton and a default span for the created skeleton. More...
 
template<int Arity = 2, typename Flows = stapl::use_default, typename Span = stapl::use_default, typename PD >
result_of::tree< Arity, Flows, Span, PD > stapl::skeletons::tree (PD &&pd)
 A tree skeleton is used in many skeletons such as reduce a tree consists of a set of levels with shrinking sizes. More...
 
template<int Arity = 2, typename Flows = stapl::use_default, typename Span = stapl::use_default, typename PD >
result_of::reverse_tree< Arity, Flows, Span, PD > stapl::skeletons::reverse_tree (PD &&pd)
 A reverse tree skeleton is used in many skeletons such as broadcast. A reverse tree consists of a set of levels with expanding sizes. More...
 
template<int Arity = 2, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename = typename std::enable_if< !is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::zip< Arity, Op, SkeletonTraits > stapl::skeletons::zip (Op &&op, SkeletonTraits &&traits=SkeletonTraits())
 A filtered zip is similar to zip skeleton but it applies a filter function on the producer side before sending data along the edges to each parametric dependency. More...
 
template<int Arity = 2, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename ExecutionParams = skeletons_impl::default_execution_params, typename = typename std::enable_if< is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::zip< Arity, decltype(skeletons::transform< tags::nest > std::declval< Op >), std::declval< ExecutionParams >))), SkeletonTraits > stapl::skeletons::zip (Op &&op, SkeletonTraits &&traits=SkeletonTraits(), ExecutionParams &&execution_params=ExecutionParams())
 Creates a zip skeleton over a nested skeleton composition by transforming the inner skeleton to a suitable skeleton for nested execution. More...
 
template<int Arity = 2, typename ZipOp , typename RedOp >
result_of::zip_reduce< Arity, ZipOp, RedOp > stapl::skeletons::zip_reduce (ZipOp &&zip_op, RedOp &&reduce_op)
 As its name implies it creates a zip-reduce skeleton by piping the result of a zip skeleton to a reduce skeleton. More...
 
template<typename Span = spans::only_once, typename Generator >
result_of::farm< Generator, Span > stapl::skeletons::farm (Generator &&generator)
 Given a generator, creates a farm skeleton. The generator can then generate the subsequent tasks of the program. More...
 

Detailed Description

The functional definition of skeletons which can be composed and transformed in the Skeletons Framework.

Functional definition of skeletons as higher order functions allows composition, formal transformation and optimization defined in the literature to be applied on the skeletons prior to their execution.

Function Documentation

◆ bitreversal()

template<typename Span = stapl::use_default>
result_of::bitreversal<Span> stapl::skeletons::bitreversal ( void  )

This skeleton can be used with skeletons that need their input to be permuted in a bitreversed order such as Cooley Tukey FFT skeletons.

Template Parameters
Spanthe inner span on which the bitreversal should be defined

◆ copy()

template<typename ValueType , typename SkeletonTraits = skeletons_impl::default_skeleton_traits>
result_of::copy<ValueType, SkeletonTraits> stapl::skeletons::copy ( SkeletonTraits &&  traits = SkeletonTraits())

A copy skeleton is used when writes to views are happening. The second flow to this skeleton will be writable.

Template Parameters
ValueTypethe type of each element to be copied
Parameters
traitsthe traits to be used (default = default_skeleton_traits)
Returns
a copy skeleton
See also
zip

◆ expand_from_pow_two()

template<typename Span = stapl::use_default, bool pos_aware = false, bool SetResult = false, typename Op , typename Filter = skeletons::no_filter>
result_of::expand_from_pow_two<Span, pos_aware, Op, Filter, SetResult> stapl::skeletons::expand_from_pow_two ( Op &&  op,
Filter &&  filter = Filter() 
)

This skeleton is used as the post-processing phase of various skeletons including broadcast, n-partition, etc. Basically, this skeleton tries to expand the result of a pow-of-two skeleton to the given non-pow-of-two size.

Template Parameters
Spanthe inner span on which the expand_from_pow_two should be defined
pos_awarewhether the op needs to know the position of the node in the dependence graph or not
Parameters
opthe operation to be used in order to expand the input size to the given size
filterthe filter workfunction to be applied before expanding to the given size
Returns
a expand from power of two skeleton with given span, filter, position awareness, and operation
See also
broadcast

◆ inner_product()

template<typename ValueType >
result_of::inner_product<ValueType> stapl::skeletons::inner_product ( )

Inner product skeleton specified in terms of the zip_reduce skeleton.

Template Parameters
ValueTypethe type of input elements to the inner product
Returns
an inner product skeleton

◆ map() [1/2]

template<typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename = typename std::enable_if< !is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::map<Op, SkeletonTraits> stapl::skeletons::map ( Op &&  op,
SkeletonTraits &&  traits = SkeletonTraits() 
)

A filtered map is similar to map skeleton but it applies a filter function on the producer side before sending data along the edges to each parametric dependency.

Template Parameters
Spanthe iteration space for the elements in this skeleton
Flowsthe flow to be used for this skeleton
Parameters
opthe workfunction to be used in each map parametric skeleton.
filterthe filter function to be used on the producer side before sending data to a parametric dependency
Returns
a map skeleton with a filter on the incoming edges
See also
map

◆ map() [2/2]

template<typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename ExecutionParams = skeletons_impl::default_execution_params, typename = typename std::enable_if< is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::map<decltype(skeletons::transform<tags::nest> std::declval<Op>), std::declval<ExecutionParams>))), SkeletonTraits> stapl::skeletons::map ( Op &&  op,
SkeletonTraits &&  traits = SkeletonTraits(),
ExecutionParams &&  execution_params = ExecutionParams() 
)

Creates a nested skeleton composition by transforming the inner skeleton to a suitable skeleton for nested execution.

Template Parameters
ExecutionParamsthe execution parameters for the nested section
Parameters
opthe skeleton to be used in the nested section
traitsthe traits to be used (default = default_skeleton_traits)
See also
map

◆ map_reduce()

template<typename MapOp , typename RedOp >
result_of::map_reduce<MapOp, RedOp> stapl::skeletons::map_reduce ( MapOp &&  map_op,
RedOp &&  red_op 
)

As its name implies it creates a map reduce skeleton by piping the result of a map skeleton to a reduce skeleton.

Parameters
map_opthe operation to be applied in the map step
red_opthe operation to be applied in the reduce step
Returns
a map-reduce skeleton

◆ notify_map()

template<int NotifCount = 1, typename Span = stapl::use_default, typename Flows = stapl::use_default, typename Op , typename Filter = skeletons::no_filter>
result_of::notify_map<NotifCount, Span, Flows, Op, Filter> stapl::skeletons::notify_map ( Op &&  op,
Filter &&  filter = Filter() 
)

A notify_map is similar to map skeleton but it also depends on a notification from the first NotifCount flows passed to it.

Template Parameters
NotifCountthe number of notification flows to notify_map
Spanthe iteration space for the elements in this skeleton
Flowsthe flow to be used for this skeleton
Parameters
opthe workfunction to be used in each notify_map parametric dependency.
filterthe filter function to be used on the producer side before sending data to a parametric dependency
Returns
a notify_map skeleton with a filter on the incoming edges
See also
notify_map

◆ pre_broadcast()

template<std::size_t Arity = 1, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits>
result_of::pre_broadcast<Arity, Op, SkeletonTraits> stapl::skeletons::pre_broadcast ( Op &&  op,
SkeletonTraits &&  traits = SkeletonTraits() 
)

This skeleton chooses an element from the domain of the input for broadcast when the input domain is non-scalar and we want to broadcast one element from the domain (e.g. last one).

Template Parameters
Aritynumber of inputs to the op workfunction
Parameters
opthe workfunction to be used in each pre_broadcast parametric dependency
traitsthe traits to be used (default = default_skeleton_traits)

◆ inclusive_scan()

template<typename Tag , typename Op >
result_of::inclusive_scan<Tag, Op> stapl::skeletons::inclusive_scan ( Op const &  op)

An inclusive scan is a scan in which each element in the output is the result of cumulative application of the operation on the elements before it including itself.

For example, if + is used as the operation, each element in the output is the sum of all elements before it, and the first element is the neutral value. An exclusive scan of [1, 2, 3, 4, ...] would be [1, 3, 6, 10, ...].

Parameters
Tagdetermines the type of inclusive scan to be used.
opthe operation to be used to compute the scan results
See also
scan

◆ exclusive_scan()

template<typename Tag , typename Op , typename T >
result_of::exclusive_scan<Tag, Op, T> stapl::skeletons::exclusive_scan ( Op const &  op,
T const &  initial_value 
)

An exclusive scan is a scan in which each element in the output is the result of cumulative application of the operation on the elements before it.

Parameters
Tvalue type of the operator
opthe operation to be used to compute the scan results
Tagdetermines the type of inclusive scan to be used.
See also
scan

◆ scatter()

template<typename T , typename Tag = stapl::use_default, typename Span = stapl::use_default>
result_of::scatter<T, Tag, Span> stapl::skeletons::scatter ( void  )

This sink skeleton assumes a default span for the created skeleton.

Template Parameters
Tthe type of elements to be copied
Parameters
skeletonthe skeleton to read the input from
dest_skeletona customized sink skeleton. By default this is assumed to be a copy skeleton
Returns
a sink skeleton with a customized destination skeleton
See also
copy

◆ serial()

template<int i, typename Op >
result_of::serial<i, Op> stapl::skeletons::serial ( Op &&  op,
std::size_t  number_of_sets 
)

Construct and execute a skeleton that performs a set of serial computations.

Parameters
opthe operator the should be applied on elements of sets.
number_of_setsThe number of sets to form. View elements are balance distributed across the sets.

◆ set_result()

template<std::size_t Arity = 1, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits>
result_of::set_result<Arity, Op, SkeletonTraits> stapl::skeletons::set_result ( Op &&  op,
SkeletonTraits &&  traits = SkeletonTraits() 
)

the skeleton which is used to specify which tasks should put their results on the environment result container according to the span which is passed in the traits

Template Parameters
Aritythe number of inputs are passed to the skeleton
Parameters
opthe workfunction to be used in each set_result_pd parametric dependency is spanned or not
traitsthe skeleton_traits to be used
See also
sink_value
skeleton_traits

◆ sink()

template<typename ValueType , typename Span = stapl::use_default, typename SrcSkeleton , typename DestSkeleton = decltype(skeletons::copy<ValueType>(skeleton_traits<Span>()))>
result_of::sink<ValueType, SrcSkeleton, DestSkeleton> stapl::skeletons::sink ( SrcSkeleton &&  skeleton,
DestSkeleton &&  dest_skeleton = skeletons::copy<ValueType>(skeleton_traits<Span>()) 
)

This sink skeleton assumes a default span for the created skeleton.

Template Parameters
ValueTypethe type of elements to be copied
Parameters
skeletonthe skeleton to read the input from
dest_skeletona customized sink skeleton. By default this is assumed to be a copy skeleton
Returns
a sink skeleton with a customized destination skeleton
See also
copy

◆ sink_value()

template<typename ValueType , typename Span = spans::per_location, typename Skeleton >
result_of::sink_value<ValueType, decltype(skeleton_traits<Span, true>)), Skeleton> stapl::skeletons::sink_value ( Skeleton &&  skeleton)

This sink skeleton assumes a default destination skeleton and a default span for the created skeleton.

Template Parameters
ValueTypethe type of elements to be copied
Spanthe span of result tasks
Parameters
skeletonthe skeleton to be plugged into result tasks
Returns
a sink_value skeleton with a default Span

◆ tree()

template<int Arity = 2, typename Flows = stapl::use_default, typename Span = stapl::use_default, typename PD >
result_of::tree<Arity, Flows, Span, PD> stapl::skeletons::tree ( PD &&  pd)

A tree skeleton is used in many skeletons such as reduce a tree consists of a set of levels with shrinking sizes.

There are variations of trees based on their span including but not limited to:

  • tree
  • right_tree
  • left-tree
Template Parameters
Aritythe arity of the tree. The default value is 2
Flowsthe flow to be used for the tree. Some skeletons need special flows.
Spanthe iteration space for elements on each level of the tree
Parameters
pdthe parametric dependency to be used in the nodes of this tree
Returns
an n-ary tree with customized flow and span
See also
spans::tree
spans::left_aligned
spans::right_aligned

◆ reverse_tree()

template<int Arity = 2, typename Flows = stapl::use_default, typename Span = stapl::use_default, typename PD >
result_of::reverse_tree<Arity, Flows, Span, PD> stapl::skeletons::reverse_tree ( PD &&  pd)

A reverse tree skeleton is used in many skeletons such as broadcast. A reverse tree consists of a set of levels with expanding sizes.

There are variations of trees based on their span including but not limited to:

  • reverse_tree
  • right_reverse_tree
  • left_reverse_tree
Template Parameters
Aritythe arity of the reverse_tree. The default value is 2
Flowsthe flow to be used for the reverse tree. Some skeletons need special flows.
Spanthe iteration space for elements on each level of the reverse tree
Parameters
pdthe parametric dependency to be used in the nodes of this reverse tree
Returns
an n-ary reverse tree with customized flow and span
See also
spans::tree
spans::left_aligned
spans::right_aligned

◆ zip() [1/2]

template<int Arity = 2, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename = typename std::enable_if< !is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::zip<Arity, Op, SkeletonTraits> stapl::skeletons::zip ( Op &&  op,
SkeletonTraits &&  traits = SkeletonTraits() 
)

A filtered zip is similar to zip skeleton but it applies a filter function on the producer side before sending data along the edges to each parametric dependency.

Template Parameters
Aritythe arity of zip
Parameters
opthe workfunction to be used in each zip parametric dependency.
traitsthe traits to be used (default = default_skeleton_traits)
See also
zip

◆ zip() [2/2]

template<int Arity = 2, typename Op , typename SkeletonTraits = skeletons_impl::default_skeleton_traits, typename ExecutionParams = skeletons_impl::default_execution_params, typename = typename std::enable_if< is_skeleton<typename std::decay<Op>::type>::value>::type>
result_of::zip<Arity, decltype(skeletons::transform<tags::nest> std::declval<Op>), std::declval<ExecutionParams>))), SkeletonTraits> stapl::skeletons::zip ( Op &&  op,
SkeletonTraits &&  traits = SkeletonTraits(),
ExecutionParams &&  execution_params = ExecutionParams() 
)

Creates a zip skeleton over a nested skeleton composition by transforming the inner skeleton to a suitable skeleton for nested execution.

Template Parameters
Aritythe arity of zip
ExecutionParamsexecution parameters for the nested section
Parameters
opthe skeleton to be used in the nested section
traitsthe traits to be used (default = default_skeleton_traits)
See also
zip

◆ zip_reduce()

template<int Arity = 2, typename ZipOp , typename RedOp >
result_of::zip_reduce<Arity, ZipOp, RedOp> stapl::skeletons::zip_reduce ( ZipOp &&  zip_op,
RedOp &&  reduce_op 
)

As its name implies it creates a zip-reduce skeleton by piping the result of a zip skeleton to a reduce skeleton.

The difference between map_reduce and zip_reduce is in the arity of the first phase. In other words a map_reduce is a zip_reduce with the arity of 1.

Parameters
zip_opthe operation to be applied in the zip step
reduce_opthe operation to be applied in the reduce step
Returns
a zip-reduce skeleton

◆ farm()

template<typename Span = spans::only_once, typename Generator >
result_of::farm<Generator, Span> stapl::skeletons::farm ( Generator &&  generator)

Given a generator, creates a farm skeleton. The generator can then generate the subsequent tasks of the program.

An example of this type of farm can be used in the implementation of BFS (Breadth First Search), in which the initial seed define the starting point of the program.

Template Parameters
Spanthe iteration space for the elements in this skeleton. The default value is only once. Other spans can be used. In such cases the redundant additions of elements to farm should be handled by the generator.
Parameters
generatorthe generator to be used to create the initial seeds for this farm. The generator receives user provides the farm as the first argument to the generator.
See also
spans::only_once