Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

tree_skeletons Class Reference

Collection of skeletons on binary trees. More...

#include <tree_skeletons.h>

List of all members.

Static Public Member Functions

template<typename K1, typename K2>
static dist_tree< typename
K1::result_type > * 		map (const K1 &k1, const K2 &k2, dist_tree< typename K1::argument_type > *t)
 Map skeleton with Function Objects.
template<typename K1, typename K2>
static dist_tree< typename
K1::result_type > * 		zipwith (const K1 &k1, const K2 &k2, const dist_tree< typename K1::first_argument_type > *at, const dist_tree< typename K1::second_argument_type > *bt)
 Zipwith skeleton with function object.
template<typename K1, typename K2, typename PSI, typename PHIL, typename PHIR, typename GG>
static K1::result_type reduce (const K1 &k1, const K2 &k2, const PSI &psi, const PHIL &phiL, const PHIR &phiR, const GG &G, const dist_tree< typename K1::argument_type > *t)
 Reduce skeleton with Function Objects.
template<typename K1, typename K2, typename PSI, typename PHIL, typename PHIR, typename GG>
static dist_tree< typename
K1::result_type > * 		uAcc (const K1 &k1, const K2 &k2, const PSI &psi, const PHIL &phiL, const PHIR &phiR, const GG &G, const dist_tree< typename K1::argument_type > *t)
 Upwards accumulate skeleton with Function Objects.
template<typename OPLUS, typename GL, typename GR>
static dist_tree< typename
OPLUS::result_type > * 		dAcc (const OPLUS &oplus, const typename OPLUS::result_type &e_oplus, const GL &gl, const GR &gr, const typename OPLUS::result_type &c, const dist_tree< typename GL::argument_type > *t)
 Downwards accumulate skeleton with Function Objects.
template<typename A>
static dist_tree< A > * distribute (const node< A > *tree)
 Distribute skeleton.
template<typename A>
static dist_tree< A > * distribute2 (const node< A > *tree)
 Distribute skeleton.
template<typename A>
static node< A > * gather (const dist_tree< A > *tree)
 Gather skeleton.
template<typename A>
static dist_tree< A > * shiftp (const A &rootval, const dist_tree< A > *tree)
 Shift each value to its children.
template<typename A>
static dist_tree< A > * shiftl (const A &leafval, const dist_tree< A > *tree)
 Shift each left-child's value to its parent.
template<typename A>
static dist_tree< A > * shiftr (const A &leafval, const dist_tree< A > *tree)
 Shift each right-child's value to its parent.

Classes

struct  reduce_result_t
 Structure to represent the result of local reduce and local uAcc, used in the reduce and uAcc skeletons.
struct  size_and_critical

Detailed Description

Collection of skeletons on binary trees.

Definition at line 22 of file tree_skeletons.h.

Member Function Documentation

template<typename OPLUS, typename GL, typename GR>
static dist_tree< typename OPLUS::result_type >* tree_skeletons::dAcc (  const OPLUS &  oplus,
const typename OPLUS::result_type &  e_oplus,
const GL &  gl,
const GR &  gr,
const typename OPLUS::result_type &  c,
const dist_tree< typename GL::argument_type > *  t
)  [static]
 

Downwards accumulate skeleton with Function Objects.

This skeleton computes in a top-down manner updating an accumulative parameter (initially c) with an associative operator (oplus) and functions (gl for left subtree and gr for right subtree).

For parallel implementation, the binary operator oplus must be associative with the unit (e_oplus).

Definition (in Haskell): 

   dAcc :: (c -> c -> c) <assoc> -> c <unit> -> (a -> c) -> (a -> c)
               -> c -> BTree a a -> BTree c c
   dAcc (oplus) e_oplus gl gr c (Leaf a)     = Leaf c
   dAcc (oplus) e_oplus gl gr c (Node b l r)
       = Node c (dAcc (oplus) e_oplus gl gr (c oplus gl b) l)
                (dAcc (oplus) e_oplus gl gr (c oplus gr b) r)

To call this skeleton, you don't need to specify the template types.

  • OPLUS = type of function object for oplus (option),
  • GL = type of function object for gl (option),
  • GR = type of function object for gr (option).

Sample:
< Specification (in Haskell) > 

   t2 = dAcc (oplus) e_oplus gl gr c t1
< C++ code > 
   t2 = tree_skeletons::dAcc( oplus, e_oplus, gl, gr, c, t1 );

Parameters:
oplus,: A function object for binary associative operator. This function needs to inherit 
 binary_function< C, C, C >
e_oplus,: The unit of operator of oplus.
gl,: Function object for function used in updating accumulative parameter for left subtree. This function needs to inherit 
 unary_function< A, C >
gr,: Function object for function used in updating accumulative parameter for right subtree. This function needs to inherit 
 unary_function< A, C >
c,: An initial value for accumulation.
t,: A distributed tree for input.

template<typename A>
static dist_tree< A >* tree_skeletons::distribute (  const node< A > *  tree  )  [static]
 

Distribute skeleton.

This skeleton distributes an input tree to processors.

The input tree must be a perfect binary tree (i.e., all the internal node has just two children).

Parameters:
tree,: a tree to distribute.

template<typename A>
static dist_tree< A >* tree_skeletons::distribute2 (  const node< A > *  tree  )  [static]
 

Distribute skeleton.

This skeleton distributes an input tree to processors.

The input tree must be a perfect binary tree (i.e., all the internal node has just two children).

Parameters:
tree,: a tree to distribute.

template<typename A>
static node< A >* tree_skeletons::gather (  const dist_tree< A > *  tree  )  [static]
 

Gather skeleton.

This skeleton gathers nodes from a distributed tree into a tree.

Parameters:
tree,: a distributed tree to be gathered.

template<typename K1, typename K2>
static dist_tree< typename K1::result_type >* tree_skeletons::map (  const K1 &  k1,
const K2 &  k2,
dist_tree< typename K1::argument_type > *  t
)  [static]
 

Map skeleton with Function Objects.

This skeleton applies function k1 to every leaf and function k2 to every internal node.

Definition (in Haskell): 

   map :: (a -> c) -> (a -> c) -> BTree a a -> BTree c c
   map k1 k2 (Leaf a)     = Leaf (k1 a)
   map k1 k2 (Node b l r) = Node (k2 b) (map k1 k2 l) (map k1 k2 r)

To call this skeleton, you need to specify the types below.

  • K1 = type of the function for each leaf (option).
  • K2 = type of the function for each internal node (option).

Sample:
< Specification (in Haskell) > 

   t2 = map k1 k2 t1
< C++ code > 
   t2 = tree_skeletons::map( k1, k2, t1 );

Parameters:
k1,: Function object applied to every leaf. This function needs to inherit unary_function with suitable types.
k2,: Function object applied to every internal node. This function needs to inherit unary function with suitable types.
t : A distributed tree for input.

template<typename K1, typename K2, typename PSI, typename PHIL, typename PHIR, typename GG>
static K1::result_type tree_skeletons::reduce (  const K1 &  k1,
const K2 &  k2,
const PSI &  psi,
const PHIL &  phiL,
const PHIR &  phiR,
const GG &  G,
const dist_tree< typename K1::argument_type > *  t
)  [static]
 

Reduce skeleton with Function Objects.

This skeleton collapses the tree in a bottom-up manner by applying k1 for every leaf and k2 for every internal node and its children.

Definition (in Haskell): 

   reduce :: (a -> c) -> (a -> c -> c -> c) -> BTree a a -> c
   reduce k1 k2 (Leaf a)     = k1 a
   reduce k1 k2 (Node b l r) = k2 b (reduce k1 k2 l) (reduce k1 k2 r)

To guarantee the correctness of the parallel implementation, the function k2 must satisfy the conditions of the tree contraction algorithm, i.e., it is needed to derive functions psi, phiL, phiR, and G as in the conditions below.

Conditions (in Haskell): 

   psi :: c -> d
   phiL :: d -> c -> d -> d
   phiR :: d -> c -> d -> d
   phiG :: d -> c -> c -> c
   k2 b l' r' = G (psi b) l' r'
   k2 b l' (k2 rb rl' rr') = G (phiL (psi b) l' (psi rb)) rl' rr'
   k2 b (k2 lb ll' lr') r' = G (phiR (psi b) r' (psi lb)) ll' lr'

To call this skeleton, you need to specify the types below.

  • K1 = type of function object k1 (option),
  • K2 = type of function object k2 (option),
  • PSI = type of function object psi (option),
  • PHIL = type of function object phiL (option),
  • PHIR = type of function object phiR (option),
  • GG = type of function object G (option).

Sample:
< specification (two functions only) > 

   v = reduce k1 k2 t
< C++ code (with all functions in the conditions) > 
   v = tree_skeletons::reduce( k1, k2, psi, phiL, phiR, G, t );

Parameters:
k1,: Function object applied to every leaf. This function needs to inherit 
 unary_function< A, C >
.
k2,: Function object applied to every internal node. This function needs to inherit 
 ternary_function< A, C, C, D >
.
psi,: Function object for Initialization of the tree contraction. This function needs to inherit 
 unary_function< A, D >
.
phiL,: Function object for ContractL operation. This function needs to inherit 
 ternary_function< D, C, D, D >
.
phiR,: Function object for ContractR operation. This function needs to inherit 
 ternary_function< D, C, D, D >
.
G,: Function object for parametrized function for tree contraction. This function needs to inherit 
 ternary_function< D, C, C, C >
.
t,: The distributed tree for input

template<typename A>
static dist_tree< A >* tree_skeletons::shiftl (  const A &  leafval,
const dist_tree< A > *  tree
)  [static]
 

Shift each left-child's value to its parent.

Shiftl skeleton shift each left-child's value to its parent, that is, for each node this skeleton substitute the left-child's value for the node's value. The values of leaves are specified by the input. The value of root node will be dropped.

Definition (in Haskell): 

   shiftl :: a -> BTree a a -> BTree a a
   shiftl a (Leaf b)     = Leaf a
   shiftl a (Node b l r) = Node (root l) (shiftl a l) (shiftl a r)

Parameters:
leafval,: The value which will be assigned to the leaves' node. This value is used on all processes.
tree,: The distributed tree for input.
Attention:
: Note that leafval should be copied on all processes.

template<typename A>
static dist_tree< A >* tree_skeletons::shiftp (  const A &  rootval,
const dist_tree< A > *  tree
)  [static]
 

Shift each value to its children.

Shiftp skeleton shift each value to its children, that is, for each node this skeleton substitute the value for children's value. The value of root node is specified by the input. The values of leaves will be dropped.

Definition (in Haskell): 

   shiftp :: a -> BTree a a -> BTree a a
   shiftp c (Leaf a)     = Leaf c
   shiftp c (Node b l r) = Node c (shitp b l) (shift b r)

Parameters:
rootval,: The value which will be assigned to the root node. This value is used only on the process 0.
tree,: The distributed tree for input.

template<typename A>
static dist_tree< A >* tree_skeletons::shiftr (  const A &  leafval,
const dist_tree< A > *  tree
)  [static]
 

Shift each right-child's value to its parent.

Shiftr skeleton shift each right-child's value to its parent, that is, for each node this skeleton substitute the right-child's value for the node's value. The values of leaves are specified by the input. The value of root node will be dropped.

Definition (in Haskell): 

   shiftr :: a -> BTree a a -> BTree a a
   shiftr a (Leaf b)     = Leaf a
   shiftr a (Node b l r) = Node (root r) (shiftr a l) (shiftr a r)

Parameters:
leafval,: The value which will be assigned to the leaves' node. This value is used on all processes.
tree,: The distributed tree for input.
Attention:
: Note that leafval should be copied on all processes.

template<typename K1, typename K2, typename PSI, typename PHIL, typename PHIR, typename GG>
static dist_tree< typename K1::result_type >* tree_skeletons::uAcc (  const K1 &  k1,
const K2 &  k2,
const PSI &  psi,
const PHIL &  phiL,
const PHIR &  phiR,
const GG &  G,
const dist_tree< typename K1::argument_type > *  t
)  [static]
 

Upwards accumulate skeleton with Function Objects.

This skeleton computes on the tree in a bottom-up manner like reduce, and the difference is that this skeleton returns a tree of the same shape as input tree by leaving the intermediate result on every node.

The meaning of functions and the conditions of additional functions for parallel implementation are the same as reduce skeleton.

Definition (in Haskell): 

   uAcc :: (a -> c) -> (a -> c -> c -> c) -> BTree a a -> BTree c c
   uAcc k1 k2 (Leaf a)     = Leaf (k1 a)
   uAcc k1 k2 (Node b l r) = let l' = uAcc k1 k2 l
                                 r' = uAcc k1 k2 r
                             in  Node (k2 b (root l') (root r')) l' r'

Conditions:
For conditions of psi, phiL, phiR, G, see conditions in reduce.

To call this skeleton, you need to specify the types below.

  • K1 = type of function object k1 (option),
  • K2 = type of function object k2 (option),
  • PSI = type of function object psi (option),
  • PHIL = type of function object phiL (option),
  • PHIR = type of function object phiR (option),
  • GG = type of function object G (option).

Sample:
< specification (two functions only) > 

   t2 = uAcc k1 k2 t1
< C++ code (with all functions in the conditions) > 
   t2 = tree_skeletons::uAcc( k1, k2, psi, phiL, phiR, G, t1 );

Parameters:
k1,: Function object applied to every leaf. This function needs to inherit 
 unary_function< A, C >
.
k2,: Function object applied to every internal node. This function needs to inherit 
 ternary_function< A, C, C, D >
.
psi,: Function object for Initialization of the tree contraction. This function needs to inherit 
 unary_function< A, D >
.
phiL,: Function object for ContractL operation. This function needs to inherit 
 ternary_function< D, C, D, D >
.
phiR,: Function object for ContractR operation. This function needs to inherit 
 ternary_function< D, C, D, D >
.
G,: Function object for parametrized function for tree contraction. This function needs to inherit 
 ternary_function< D, C, C, C >
.
t,: The distributed tree for input

template<typename K1, typename K2>
static dist_tree< typename K1::result_type >* tree_skeletons::zipwith (  const K1 &  k1,
const K2 &  k2,
const dist_tree< typename K1::first_argument_type > *  at,
const dist_tree< typename K1::second_argument_type > *  bt
)  [static]
 

Zipwith skeleton with function object.

This skeleton zips up two trees of the same shape into a tree by applying k1 for every pair of leaves and k2 for every pair of internal nodes.

Definition (in Haskell): 

   zipwith :: (a -> c -> e) -> (a -> c -> e) -> BTree a a -> BTree c c -> BTree e e
   zipwith k1 k2 (Leaf a) (Leaf a')           = Leaf (k1 a a')
   zipwith k1 k2 (Node b l r) (Node b' l' r') = Node (k2 b b') (zipwith k1 k2 l l')
                                                               (zipwith k1 k2 r r')

To call this skeleton, you need to specify the types below.

  • K1 = type of function object k1 (option),
  • K2 = type of function object k2 (option).

Sample:
< Specification (in Haskell) > 

   t = zipwith k1 k2 at bt
< C++ code > 
   t = tree_skeletons::zipwith( k1, k2, at, bt );

Parameters:
k1,: Function object applied to every pair of leaves. This function needs to inherit binary_function with suitable types.
k2,: Function object applied to every pair of internal nodes. This function needs to inherit binary_function with suitable types.
at,: The first tree to zip up.
bt,: The second tree to zip up.

The documentation for this class was generated from the following file:
Generated on Wed Jan 18 22:21:12 2006 for SkeTo -- Skeleton Library in Tokyo by  doxygen 1.4.4