tree_skeletons.h

Go to the documentation of this file.

/***
 * Copyright (c) 2005, SkeTo Project
 * All rights reserved.
 */
#ifndef __TREE_SKELETONS_H__
#define __TREE_SKELETONS_H__

#include "node.h"
#include "dist_tree.h"
#include "../util/compose.h"

class tree_skeletons
{
  // Data parallel Skeletons

public:
  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 );

private:
  template< typename C, typename A, typename K1, typename K2 >
  static dist_tree< C > *map_adapter( const K1 &k1,
                      const K2 &k2,
                      dist_tree< A > *t );

private:
  template< typename C, typename A, typename K1, typename K2 >
  static node< C >* map_rec( const K1 &k1,
                 const K2 &k2,
                 node< A > *root );

public:
  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 );

private:
  template< typename E, typename A, typename C, typename K1, typename K2 >
  static dist_tree< E >* zipwith_adapter( const K1 &k1, 
                      const K2 &k2,
                      const dist_tree< A >* at, 
                      const dist_tree< C >* bt );

private:
  template< typename E, typename A, typename C, typename K1, typename K2 >
  static node< E >* zipwith_rec( const K1 &k1, 
                 const K2 &k2, 
                 const node< A >* root_a,
                 const node< C >* root_b );

public:
  template< typename K1, typename K2,
        typename PSI, typename PHIL, typename PHIR, typename GG >
  static typename 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 );

private:
  template< typename C, typename D, typename A, typename K1, typename K2,
        typename PSI, typename PHIL, typename PHIR, typename GG >
  static C reduce_adapter( const K1 &k1, 
               const K2 &k2, 
               const PSI &psi,
               const PHIL &phiL,
               const PHIR &phiR,
               const GG &G,
               const dist_tree< A >* t );

private:
  template< typename C, typename D >
  struct reduce_result_t {
    enum {
      TYPEC,
      TYPED,
    } resulttype;
    C valC;
    D valD;
  };

private:
  template< typename C, typename D, typename A, typename K1, typename K2,
        typename PSI, typename PHIL, typename PHIR >
  static tree_skeletons::reduce_result_t< C, D >
  reduce_local_rec( const K1 &k1,
            const K2 &k2,
            const PSI &psi,
            const PHIL &phiL,
            const PHIR &phiR, 
            const node< A >* root );

private:
  template< typename C, typename D, typename A, typename GG >
  static C reduce_global( const GG &G,
              const tree_skeletons::reduce_result_t< C, D > &local_result,
              const dist_tree< A > *t );
  
public:
  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 );

private:
  template< typename C, typename D, typename A, typename K1, typename K2,
        typename PSI, typename PHIL, typename PHIR, typename GG >
  static dist_tree< C >* uAcc_adapter( const K1 &k1,
                       const K2 &k2,
                       const PSI &psi,
                       const PHIL &phiL,
                       const PHIR &phiR,
                       const GG &G,
                       const dist_tree< A > *t );

private:
  template< typename C, typename D, typename A, typename GG >
  static void uAcc_global_uAcc( const GG &G, 
                const tree_skeletons::reduce_result_t< C, D > &local_result,
                C *vall,
                C *valr,
                const dist_tree< A > *t );

private:
  template< typename C, typename D, typename A, typename K1, typename K2 >
  static node< C >* uAcc_local_uAcc_rec( const K1 &k1,
                     const K2 &k2, 
                     const C& left_result,
                     const C& right_result,
                     const node< A > *root );

public:
  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 );

private:
  template< typename C, typename A, typename OPLUS, typename GL, typename GR >
  static dist_tree< C >* dAcc_adapter( const OPLUS &oplus,
                       const C &e_oplus,
                       const GL &gl,
                       const GR &gr,
                       const C &c,
                       const dist_tree< A >* t );

private:
  template< typename C, typename A, typename OPLUS, typename GL, typename GR >
  static bool dAcc_local_path_rec( const OPLUS &oplus,
                   const GL &gl,
                   const GR &gr,
                   const node< A >* root,
                   C *c_to_left,
                   C *c_to_right );

private:
  template< typename C, typename A, typename OPLUS >
  static C dAcc_global_dAcc( const OPLUS &oplus,
                 const C &c,
                 const C &c_to_left,
                 const C &c_to_right,
                 const dist_tree< A >* t );

private:
  template< typename C, typename A, typename OPLUS, typename GL, typename GR >
  static node< C >* dAcc_local_dAcc_rec( const OPLUS &oplus,
                     const GL &gl,
                     const GR &gr, 
                     const C &c,
                     const node< A >* root );

  // Communication Skeletons

public:
  template< typename A >
  static dist_tree< A >* distribute( const node< A >* tree );

public:
  template< typename A >
  static dist_tree< A >* distribute2( const node< A >* tree );

private:
  template< typename A >
  struct size_and_critical {
    int left_size;
    int right_size;
    const node< A >* critical_node;
  };

private:
  template< typename A >
  static bool compute_size_and_get_global_tree( const node< A >* tree,
                        int nprocs,
                        node< size_and_critical< A > >** global_root,
                        int *np,
                        int *size );

private:
  template< typename A >
  static void get_global_tree_rec( node< size_and_critical< A > >** global_tree,
                   int *size_root,
                   const node< A >* tree,
                   int m );
  
private:
  template< typename A >
  static void serialize_global_structure( const node< A >* tree,
                      const node< size_and_critical< A > >* global_root,
                      int size, 
                      int *flags,
                      int *localsizes,
                      const node< A >** subroots,
                      const node< A >** subcrits );

private:
  template< typename A >
  static void serialize_global_structure_rec( const node< A >* tree,
                          const node< size_and_critical< A > >* global_root,
                          int size,
                          int *flags,
                          int *localsizes,
                          const node< A >** subroots,
                          const node< A >** subcrits,
                          int *index );
                          
private:
  template< typename A >
  static void get_local_tree( const node< A >* root,
                  const node< A >* crit_node,
                  int *flags,
                  A *values );

private:
  template< typename A >
  static void get_local_tree_rec( const node< A >* root,
                  const node< A >* crit_node,
                  int *flags,
                  A *values,
                  int *index );

public:
  template< typename A >
  static node< A >* gather( const dist_tree< A >* tree );
  
private:
  template< typename A >
  static void gather_rec( node< A >* root,
              const node< int >* global_root,
              int *proc );

private:
  template< typename A >
  static node< A >* gather_find_cutnode( node< A >* root );

private:
  template< typename A >
  static node< A >* gather_create_subtree( const int* flags,
                       const A* values );
  
private:
  template< typename A >
  static node< A >* gather_copy_tree( const node< A >* root );

public:
  template< typename A >
  static dist_tree< A >* shiftp( const A& rootval,
                 const dist_tree< A >* tree );

private:
  template< typename A >
  static node< A > *shiftp_rec( const node< A >* root,
                const A& root_val, 
                A *cut_node_val );

public:
  template< typename A >
  static dist_tree< A >* shiftl( const A& leafval,
                 const dist_tree< A >* tree );

private:
  template< typename A >
  static node< A >* shiftl_rec( const node< A > *root,
                const A& leafval,
                const A& left_child_root_val );
  
public:
  template< typename A >
  static dist_tree< A >* shiftr( const A& leafval,
                 const dist_tree< A >* tree );

private:
  template< typename A >
  static node< A >* shiftr_rec( const node< A > *root,
                const A& leafval,
                const A& right_child_root_val );

};

#include "tree_skeletons.tpp"

#endif /* __TREE_SKELETONS_H__ */

---