tree_skeletons.tpp

Go to the documentation of this file.

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

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <assert.h>

#include <mpi.h>

enum {
  TAG_REDUCE,
  TAG_UACC,
  TAG_DACC,
  TAG_DISTRIBUTE,
  TAG_DISTRIBUTE2,
  TAG_GATHER,
  TAG_SHIFTP,
  TAG_SHIFTL,
  TAG_SHIFTR,
};

/* public, static */
template< typename K1, typename K2 >
inline dist_tree< typename K1::result_type > *
tree_skeletons::map( const K1 &k1,
             const K2 &k2,
             dist_tree< typename K1::argument_type > *t )
{
  return map_adapter<
    typename K1::result_type,
    typename K1::argument_type,
    K1, K2 >( k1, k2, t );
}

/* private, static */
template< typename C, typename A, typename K1, typename K2 >
inline dist_tree< C >*
tree_skeletons::map_adapter( const K1 &k1,
                 const K2 &k2,
                 dist_tree< A > *t )
{
  dist_tree< C >* ret_tree = new dist_tree< C >( t );
  if ( !t->local_root ) return ret_tree;

  ret_tree->local_root = map_rec< C, A, K1, K2 >( k1, k2, t->local_root );
  return ret_tree;
}

/* private, static */
template< typename C, typename A, typename K1, typename K2 >
node< C >*
tree_skeletons::map_rec( const K1 &k1,
             const K2 &k2,
             node< A >* root )
{
  node< C >* ret;
  if ( !root->isLeaf( ) ) {
    // Normal internal node
    ret = new node< C >( k2( root->value ), node< C >::NORMAL );
    ret->left  = map_rec< C, A, K1, K2 >( k1, k2, root->left );
    ret->left->parent = ret;
    
    ret->right = map_rec< C, A, K1, K2 >( k1, k2, root->right );
    ret->right->parent = ret;

  } else if ( root->nodetype == node< A >::NORMAL ) {
    // Normal leaf
    ret = new node< C >( k1( root->value ), node< C >::NORMAL );

  } else {
    // Cut Node
    ret = new node< C >( k2( root->value ), node< C >::CUTNODE );
  }
  return ret;
}

/* public, static */
template< typename K1, typename K2 >
inline 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 )
{
  return zipwith_adapter<
    typename K1::result_type,
    typename K1::first_argument_type, 
    typename K1::second_argument_type,
    K1, K2 >( k1, k2, at, bt );
}

/* private, static */
template< typename E, typename A, typename C, typename K1, typename K2 >
dist_tree< E >*
tree_skeletons::zipwith_adapter( const K1 &k1, 
             const K2 &k2,
             const dist_tree< A >* at, 
             const dist_tree< C >* bt )
{
  dist_tree< E >* ret_tree = new dist_tree< E >( at );
  if ( !at->local_root ) return ret_tree;

  ret_tree->local_root
    = zipwith_rec< E, A, C, K1, K2 >( k1, k2, at->local_root, bt->local_root );
  return ret_tree;
}

/* private, static */
template< typename E, typename A, typename C, typename K1, typename K2 >
node< E >*
tree_skeletons::zipwith_rec( const K1 &k1, 
                 const K2 &k2,
                 const node< A >* root_a,
                 const node< C >* root_b )
{
  node< E >* ret_node;
  if ( !root_a->isLeaf( ) ) {
    // Normal internal node
    ret_node = new node< E >( k2( root_a->value, root_b->value ),
                  node< E >::NORMAL );
    ret_node->left
      = zipwith_rec< E, A, C, K1, K2 >( k1, k2, root_a->left,  root_b->left );
    ret_node->left->parent = ret_node;
    ret_node->right
      = zipwith_rec< E, A, C, K1, K2 >( k1, k2, root_a->right, root_b->right );
    ret_node->right->parent = ret_node;
    
  } else if ( root_a->nodetype == node< A >::NORMAL ) {
    // Normal leaf
    ret_node = new node< E >( k1( root_a->value, root_b->value ),
                  node< E >::NORMAL );
  } else {
    // Cut Node
    ret_node = new node< E >( k2( root_a->value, root_b->value ),
                  node< E >::CUTNODE );
  }
  return ret_node;
}

/* public, static */
template< typename K1, typename K2,
      typename PSI, typename PHIL, typename PHIR, typename GG >
inline typename 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 )
{
  return reduce_adapter<
    typename K1::result_type,
    typename PSI::result_type,
    typename K1::argument_type,
    K1, K2, PSI, PHIL, PHIR, GG >( k1, k2, psi, phiL, phiR, G, t );
}

/* private, static */
template< typename C, typename D, typename A, typename K1, typename K2,
      typename PSI, typename PHIL, typename PHIR, typename GG >
C
tree_skeletons::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 )
{
  //  if ( !t->local_root ) { C dummy; return dummy; }
  if ( !t->local_root ) { return static_cast< C >( false ); }

  // local_reduce
  reduce_result_t< C, D > local_result
    = reduce_local_rec< C, D, A, K1, K2, PSI, PHIL, PHIR >
    ( k1, k2, psi, phiL, phiR, t->local_root );

  // global_reduce
  return reduce_global< C, D, A, GG >( G, local_result, t );
}

/* private, static */
template< typename C, typename D, typename A, typename K1, typename K2,
      typename PSI, typename PHIL, typename PHIR >
tree_skeletons::reduce_result_t< C, D >
tree_skeletons::reduce_local_rec( const K1 &k1,
                  const K2 &k2,
                  const PSI &psi,
                  const PHIL &phiL,
                  const PHIR &phiR, 
                  const node< A >* root )
{
  reduce_result_t< C, D > ret;
  if ( root->isLeaf( ) && root->nodetype == node< A >::NORMAL ) {
    // Normal Leaf
    ret.resulttype = reduce_result_t< C, D >::TYPEC;
    ret.valC = k1( root->value );
  } else if ( root->isLeaf( ) && root->nodetype == node< A >::CUTNODE ) {
    // CutNode
    ret.resulttype = reduce_result_t< C, D >::TYPED;
    ret.valD = psi( root->value );
  } else {
    // Normal Internal Node
    reduce_result_t< C, D > retl
      = reduce_local_rec< C, D, A, K1, K2, PSI, PHIL, PHIR >
      ( k1, k2, psi, phiL, phiR, root->left );
    reduce_result_t< C, D > retr
      = reduce_local_rec< C, D, A, K1, K2, PSI, PHIL, PHIR >
      ( k1, k2, psi, phiL, phiR, root->right );

    if ( retl.resulttype == reduce_result_t< C, D >::TYPEC &&
     retr.resulttype == reduce_result_t< C, D >::TYPEC ) {
      // Simple Reduction
      ret.resulttype = reduce_result_t< C, D >::TYPEC;
      ret.valC = k2( root->value, retl.valC, retr.valC );

    } else if ( retl.resulttype == reduce_result_t< C, D >::TYPED &&
        retr.resulttype == reduce_result_t< C, D >::TYPEC ) {
      // ContractR
      ret.resulttype = reduce_result_t< C, D >::TYPED;
      ret.valD = phiR( psi( root->value ), retr.valC, retl.valD );

    } else if ( retl.resulttype == reduce_result_t< C, D >::TYPEC &&
        retr.resulttype == reduce_result_t< C, D >::TYPED ) {
      // ContractL
      ret.resulttype = reduce_result_t< C, D >::TYPED;
      ret.valD = phiL( psi( root->value ), retl.valC, retr.valD );

    } else {
      // Something wrong occur
      assert( false );
    }
  }
  return ret;
}

/* private, static */
template< typename C, typename D, typename A, typename GG >
C
tree_skeletons::reduce_global( const GG &G,
                   const tree_skeletons::reduce_result_t< C, D > &local_result,
                   const dist_tree< A > *t )
{
  C result;

  if ( t->global_node->isLeaf( ) ) {
    result = local_result.valC;
  } else {
    C resultl, resultr;

    MPI_Request req1, req2;
    MPI_Irecv( &resultl, sizeof( C ), MPI_BYTE,
           t->proc_leftchild, TAG_REDUCE, MPI_COMM_WORLD, &req1 );
    MPI_Irecv( &resultr, sizeof( C ), MPI_BYTE,
           t->proc_rightchild, TAG_REDUCE, MPI_COMM_WORLD, &req2 );
    MPI_Wait( &req1, MPI_STATUS_IGNORE );
    MPI_Wait( &req2, MPI_STATUS_IGNORE );

    result = G( local_result.valD, resultl, resultr );
  }

  if ( skeleton::rank != 0 ) {
    MPI_Request req;
    MPI_Isend( &result, sizeof( C ), MPI_BYTE,
           t->proc_parent, TAG_REDUCE, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }

  return result;
}

/* public, static */
template< typename K1, typename K2,
      typename PSI, typename PHIL, typename PHIR, typename GG >
inline 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 )
{
  return uAcc_adapter<
    typename K1::result_type,
    typename PSI::result_type,
    typename K1::argument_type,
    K1, K2, PSI, PHIL, PHIR, GG >( k1, k2, psi, phiL, phiR, G, t );
}

/* private, static */
template< typename C, typename D, typename A, typename K1, typename K2,
        typename PSI, typename PHIL, typename PHIR, typename GG >
dist_tree< C >*
tree_skeletons::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 )
{
  dist_tree< C >* ret_tree = new dist_tree< C >( t );
  if ( !t->local_root ) return ret_tree;
  
  // local reduce
  tree_skeletons::reduce_result_t< C, D > local_result
    = reduce_local_rec< C, D, A, K1, K2, PSI, PHIL, PHIR >
    ( k1, k2, psi, phiL, phiR, t->local_root );
  
  // global uAcc
  C vall, valr;
  uAcc_global_uAcc< C, D, A, GG >( G, local_result, &vall, &valr, t );

  // local uAcc
  ret_tree->local_root
    = uAcc_local_uAcc_rec< C, D, A, K1, K2 >
    ( k1, k2, vall, valr, t->local_root );

  return ret_tree;
}

/* private, static */
template< typename C, typename D, typename A, typename GG >
void
tree_skeletons::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 )
{
  C result;
  
  if ( t->global_node->isLeaf( ) ) {
    result = local_result.valC;
  } else {

    MPI_Request req1, req2;
    MPI_Irecv( vall, sizeof( C ), MPI_BYTE,
           t->proc_leftchild, TAG_UACC, MPI_COMM_WORLD, &req1 );
    MPI_Irecv( valr, sizeof( C ), MPI_BYTE,
           t->proc_rightchild, TAG_UACC, MPI_COMM_WORLD, &req2 );
    MPI_Wait( &req1, MPI_STATUS_IGNORE );
    MPI_Wait( &req2, MPI_STATUS_IGNORE );

    result = G( local_result.valD, *vall, *valr );
  }
  
  if ( skeleton::rank != 0 ) {
    MPI_Request req;
    MPI_Isend( &result, sizeof( C ), MPI_BYTE,
           t->proc_parent, TAG_UACC, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }
}

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

  if ( root->isLeaf( ) && root->nodetype == node< A >::NORMAL ) {
    // Normal Leaf
    ret_node = new node< C >( k1( root->value ), node< C >::NORMAL );
  } else if ( root->nodetype == node< A >::CUTNODE ) {
    // CutNode
    ret_node = new node< C >( k2( root->value, left_result, right_result ),
                  node< C >::CUTNODE );
  } else {
    // Normal Internal Node
    node< C >* left_node
      = uAcc_local_uAcc_rec< C, D, A, K1, K2 >
      ( k1, k2, left_result, right_result, root->left );
    node< C >* right_node
      = uAcc_local_uAcc_rec< C, D, A, K1, K2 >
      ( k1, k2, left_result, right_result, root->right );

    ret_node
      = new node< C >( k2( root->value, left_node->value, right_node->value ),
               node< C >::NORMAL );
    ret_node->left  = left_node;  ret_node->left->parent  = ret_node;
    ret_node->right = right_node; ret_node->right->parent = ret_node;
  }

  return ret_node;
}

/* public, static */
template< typename OPLUS, typename GL, typename GR >
inline 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 )
{
  return dAcc_adapter<
    typename OPLUS::result_type,
    typename GL::argument_type,
    OPLUS, GL, GR >( oplus, e_oplus, gl, gr, c, t );
}

/* private, static */
template< typename C, typename A, typename OPLUS, typename GL, typename GR >
dist_tree< C >*
tree_skeletons::dAcc_adapter( const OPLUS &oplus,
                  const C &e_oplus,
                  const GL &gl,
                  const GR &gr,
                  const C &c,
                  const dist_tree< A >* t )
{
  dist_tree< C >* ret_tree = new dist_tree< C >( t );
  if ( !t->local_root ) return ret_tree;
  
  // local dAcc on path
  C c_to_left = e_oplus, c_to_right = e_oplus;
  dAcc_local_path_rec< C, A, OPLUS, GL, GR >
    ( oplus, gl, gr, t->local_root, &c_to_left, &c_to_right );
  
  // global dAcc
  C c_from_parent
    = dAcc_global_dAcc< C, A, OPLUS >( oplus, c, c_to_left, c_to_right, t );
  
  // local dAcc
  ret_tree->local_root
    = dAcc_local_dAcc_rec< C, A, OPLUS, GL, GR >
    ( oplus, gl, gr, c_from_parent, t->local_root );

  return ret_tree;
}

/* private, static */
template< typename C, typename A, typename OPLUS, typename GL, typename GR >
bool
tree_skeletons::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 )
{
  if ( root->isLeaf( ) && root->nodetype == node< A >::NORMAL ) {
    // Normal Leaf
    return false;
  } else if ( root->isLeaf( ) && root->nodetype == node< A >::CUTNODE ) {
    // CutNode
    *c_to_left  = gl( root->value );
    *c_to_right = gr( root->value );
    return true;
  } else {
    // Normal Internal Node
    if ( dAcc_local_path_rec( oplus, gl, gr, root->left,
                  c_to_left, c_to_right ) ) {
      *c_to_left  = oplus( gl( root->value ), *c_to_left  );
      *c_to_right = oplus( gl( root->value ), *c_to_right );
      return true;
    }
    if ( dAcc_local_path_rec( oplus, gl, gr, root->right,
                  c_to_left, c_to_right ) ) {
      *c_to_left  = oplus( gr( root->value ), *c_to_left  );
      *c_to_right = oplus( gr( root->value ), *c_to_right );
      return true;
    }
    return false;
  }
}

/* private, static */
template< typename C, typename A, typename OPLUS >
C
tree_skeletons::dAcc_global_dAcc( const OPLUS &oplus,
                  const C &c,
                  const C &c_to_left,
                  const C &c_to_right,
                  const dist_tree< A >* t )
{
  C c_from_parent;
  if ( skeleton::rank == 0 ) {
    c_from_parent = c;
  } else {
    MPI_Request req;
    MPI_Irecv( &c_from_parent, sizeof( C ), MPI_BYTE,
           t->proc_parent, TAG_DACC, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }

  if ( t->global_node->isLeaf( ) ) {
  } else {
    C sent_c_to_left  = oplus( c_from_parent, c_to_left );
    C sent_c_to_right = oplus( c_from_parent, c_to_right );

    MPI_Request req1, req2;
    MPI_Isend( &sent_c_to_left, sizeof( C ), MPI_BYTE,
           t->proc_leftchild, TAG_DACC, MPI_COMM_WORLD, &req1 );
    MPI_Isend( &sent_c_to_right, sizeof( C ), MPI_BYTE,
           t->proc_rightchild, TAG_DACC, MPI_COMM_WORLD, &req2 );
    MPI_Wait( &req1, MPI_STATUS_IGNORE );
    MPI_Wait( &req2, MPI_STATUS_IGNORE );

  }    

  return c_from_parent;
}

/* private, static */
template< typename C, typename A, typename OPLUS, typename GL, typename GR >
node< C >*
tree_skeletons::dAcc_local_dAcc_rec( const OPLUS &oplus,
                     const GL &gl,
                     const GR &gr, 
                     const C &c,
                     const node< A >* root )
{
  node< C >* ret_node
    = new node< C >( c, ( root->nodetype == node< A >::NORMAL ) ? node< C >::NORMAL : node< C >::CUTNODE );

  if ( !root->isLeaf( ) ) {
    ret_node->left = dAcc_local_dAcc_rec( oplus, gl, gr,
                      oplus( c, gl( root->value ) ),
                      root->left );
    ret_node->left->parent = ret_node;
    ret_node->right = dAcc_local_dAcc_rec( oplus, gl, gr,
                      oplus( c, gr( root->value ) ),
                      root->right );
    ret_node->right->parent = ret_node;
  }

  return ret_node;
}

/* public, static */
template< typename A >
dist_tree< A >*
tree_skeletons::distribute2( const node< A >* s_tree )
{
  dist_tree< A >* d_tree = new dist_tree< A >( );

  if ( skeleton::rank == 0 ) {
    // master process
    // assert( tree_util::check_perfect_binary_tree( s_tree ) );

    node< tree_skeletons::size_and_critical< A > >* global_root;
    int np;
    int size;
    
    if ( !compute_size_and_get_global_tree( s_tree, skeleton::procs, &global_root, &np, &size ) ) {
      std::exit( 1 );
    }

    // (1) number of blocks
    MPI_Bcast( &np, 1, MPI_INT, 0, MPI_COMM_WORLD );

    // (2) global_trees
    int *localsizes = new int[ np ];
    const node< A >** subroots = new const node< A >*[ np ];
    const node< A >** subcrits = new const node< A >*[ np ];
    {
      int *flags = new int[ np ];
      serialize_global_structure( s_tree, global_root, size, 
                  flags, localsizes, subroots, subcrits );

      MPI_Bcast( flags, np, MPI_INT, 0, MPI_COMM_WORLD );
      MPI_Bcast( localsizes, np, MPI_INT, 0, MPI_COMM_WORLD );

      d_tree->read_from_file_create_global_tree( flags, localsizes );

      delete [] flags;
    }

    // obtain maximum local-size to allocate memory once.
    int max_size = 0;
    for ( int p = 0; p < np; p++ ) {
      if ( max_size < localsizes[ p ] ) max_size = localsizes[ p ];
    }

    int *flags = new int[ max_size ];
    A *values = new A[ max_size ];
    
    // (3-1) subtrees ( other process but root )
    for ( int p = 1; p < np; p++ ) {
      get_local_tree( subroots[ p ], subcrits[ p ], flags, values );

      MPI_Request req1, req2;
      MPI_Isend( flags, localsizes[ p ], MPI_INT,
         p, TAG_DISTRIBUTE, MPI_COMM_WORLD, &req1 );
      MPI_Isend( values, localsizes[ p ] * sizeof( A ), MPI_BYTE,
         p, TAG_DISTRIBUTE2, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );
    }

    // (3-2) subtrees ( root process )
    {
      get_local_tree( subroots[ 0 ], subcrits[ 0 ], flags, values );
      d_tree->read_from_file_create_subtree( flags, values );
    }

    delete [] values;
    delete [] flags;
  }
  else {
    // slave process
    // (1) number of blocks
    int np;
    MPI_Bcast( &np, 1, MPI_INT, 0, MPI_COMM_WORLD );

    // (2) global trees
    {
      int *localsizes = new int[ np ];
      int *flags = new int[ np ];

      MPI_Bcast( flags, np, MPI_INT, 0, MPI_COMM_WORLD );
      MPI_Bcast( localsizes, np, MPI_INT, 0, MPI_COMM_WORLD );

      d_tree->read_from_file_create_global_tree( flags, localsizes );

      delete[] flags;
      delete[] localsizes;
    }

    // (3-2) subtrees
    if ( skeleton::rank < np ) {
      const int localsize = d_tree->global_node->value;
      int *flags = new int[ localsize ];
      A *values = new A[ localsize ];

      MPI_Request req1, req2;
      MPI_Irecv( flags, localsize, MPI_INT,
         0, TAG_DISTRIBUTE, MPI_COMM_WORLD, &req1 );
      MPI_Irecv( values, localsize * sizeof( A ), MPI_BYTE,
         0, TAG_DISTRIBUTE2, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );

      d_tree->read_from_file_create_subtree( flags, values );

      delete[] values;
      delete[] flags;
    }
  }

  return d_tree;
}

template< typename A >
int temp_get_size_rec( const node< A >* tree )
{
  if ( tree == NULL ) return 0;

  int size_left, size_right;
  size_left  = temp_get_size_rec( tree->left );
  size_right = temp_get_size_rec( tree->right );

  return 1 + size_left + size_right;
}

template< typename A >
bool
tree_skeletons::compute_size_and_get_global_tree( const node< A >* tree,
                          int nprocs,
                          node< size_and_critical< A > >** global_root,
                          int *np,
                          int *size )
{
  // get size;
  *size = tree_util::get_size_rec( tree );
  int m = 2 * *size / ( nprocs / 2 + 1 );

  // ( critical_subroot, size ) = get_global_tree_rec( tree, m );
  node< size_and_critical< A > >* global_tree;
  int s;
  get_global_tree_rec( &global_tree, &s, tree, m );

  *np = temp_get_size_rec( global_tree ) * 2 + 1;
  assert( *np <= nprocs );

  *global_root = global_tree;

  return true;
}

template< typename A >
void
tree_skeletons::get_global_tree_rec( node< size_and_critical< A > >** global_tree,
                     int *size_root,
                     const node< A >* tree,
                     int m )
{
  if ( tree->isLeaf( ) ) {
    *global_tree = NULL;
    *size_root = 1;
    return;
  } 

  int size, size_left, size_right;
  node< size_and_critical< A > > *global_root, *global_left, *global_right;

  get_global_tree_rec( &global_left,  &size_left,  tree->left,  m );
  get_global_tree_rec( &global_right, &size_right, tree->right, m );

  size = 1 + size_left + size_right;
  if ( ( tree_util::ceil_divided_by_m( size, m )
     > tree_util::ceil_divided_by_m( size_left, m ) ) &&
       ( tree_util::ceil_divided_by_m( size, m )
     > tree_util::ceil_divided_by_m( size_right, m ) ) ) {
    global_root = new node< size_and_critical< A > >( );
    global_root->value.critical_node = tree;
    global_root->value.left_size  = size_left;
    global_root->value.right_size = size_right;
    
    global_root->left  = global_left;
    global_root->right = global_right;
    if ( global_root->left  ) global_root->left ->parent = global_root;
    if ( global_root->right ) global_root->right->parent = global_root;

    *global_tree = global_root;
    *size_root = size;
  } else {
    if ( global_left ) {
      *global_tree = global_left;
    } else {
      *global_tree = global_right;
    }
    *size_root = size;

  }
}

template< typename A >
void
tree_skeletons::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 )
{
  int index = 0;
  serialize_global_structure_rec( tree, global_root, size,
                  flags, localsizes, subroots, subcrits,
                  &index );
}

template< typename A >
void
tree_skeletons::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 )
{
  int cur_index = (*index)++;
  flags[ cur_index ] = ( global_root ? node< size_and_critical< A > >::SER_NODE :
             node< size_and_critical< A > >::SER_LEAF );
  localsizes[ cur_index ] = ( global_root ?
                  size - global_root->value.left_size - global_root->value.right_size :
                  size );
  subroots[ cur_index ] = tree;
  subcrits[ cur_index ] = ( global_root ? global_root->value.critical_node : NULL );

  if ( global_root ) {
    serialize_global_structure_rec( global_root->value.critical_node->left,
                    global_root->left,
                    global_root->value.left_size,
                    flags,
                    localsizes,
                    subroots,
                    subcrits,
                    index );
    serialize_global_structure_rec( global_root->value.critical_node->right,
                    global_root->right,
                    global_root->value.right_size,
                    flags,
                    localsizes,
                    subroots,
                    subcrits,
                    index );
  }     
}

template< typename A >
void
tree_skeletons::get_local_tree( const node< A >* root,
                const node< A >* crit_node,
                int *flags,
                A *values )
{
  int index = 0;
  get_local_tree_rec( root, crit_node, flags, values, &index );
}

template< typename A >
void
tree_skeletons::get_local_tree_rec( const node< A >* root,
                    const node< A >* crit_node,
                    int *flags,
                    A *values,
                    int *index )
{
  int cur_index = (*index)++;

  values[ cur_index ] = root->value;

  if ( root == crit_node ) {
    flags[ cur_index ] = node< A >::SER_CUTNODE;
  } else if ( root->isLeaf( ) ) {
    flags[ cur_index ] = node< A >::SER_LEAF;
  } else {
    flags[ cur_index ] = node< A >::SER_NODE;

    get_local_tree_rec( root->left,  crit_node, flags, values, index );
    get_local_tree_rec( root->right, crit_node, flags, values, index );
  }
}

/* public, static */
template< typename A >
dist_tree< A >*
tree_skeletons::distribute( const node< A >* s_tree )
{
  dist_tree< A >* d_tree = new dist_tree< A >( );

  if ( skeleton::rank == 0 ) {
    // master process
    assert( tree_util::check_perfect_binary_tree( s_tree ) );

    node< tree_util::IntermediateVal< A > > *size_crit_tree;
    int np;
    
    if ( !tree_util::compute_size_and_mark_critical( s_tree, skeleton::procs, &size_crit_tree, &np ) ) {
      std::exit( 1 );
    }

    // (1) number of blocks
    MPI_Bcast( &np, 1, MPI_INT, 0, MPI_COMM_WORLD );

    // (2) global trees
    int *localsizes = new int[ np ];
    node< tree_util::IntermediateVal< A > > **subroots
      = new node< tree_util::IntermediateVal< A > >*[ np ];
    {
      int *flags = new int[ np ];
      tree_util::get_global_tree( size_crit_tree, flags, localsizes, subroots );

      MPI_Bcast( flags, np, MPI_INT, 0, MPI_COMM_WORLD );
      MPI_Bcast( localsizes, np, MPI_INT, 0, MPI_COMM_WORLD );

      d_tree->read_from_file_create_global_tree( flags, localsizes );
      delete [] flags;
    }

    // (3-1) subtrees ( root process )
    {
      int *flags = new int[ localsizes[ 0 ] ];
      A *values = new A[ localsizes[ 0 ] ];

      tree_util::get_local_tree( subroots[ 0 ], flags, values );
      d_tree->read_from_file_create_subtree( flags, values );

      delete[] values;
      delete[] flags;
    }
    
    // (3-2) subtrees ( other process )
    for ( int p = 1; p < np; p++ ) {
      int *flags = new int[ localsizes[ p ] ];
      A *values = new A[ localsizes[ p ] ];

      tree_util::get_local_tree( subroots[ p ], flags, values );
      MPI_Request req1, req2;
      MPI_Isend( flags, localsizes[ p ], MPI_INT,
         p, TAG_DISTRIBUTE, MPI_COMM_WORLD, &req1 );
      MPI_Isend( values, localsizes[ p ] * sizeof( A ), MPI_BYTE,
         p, TAG_DISTRIBUTE, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );

      delete[] values;
      delete[] flags;
    }
    delete [] subroots;
    delete [] localsizes;

    tree_util::free_all_tree( size_crit_tree );

  } else {
    // slave process

    // (1) number of blocks
    int np;
    MPI_Bcast( &np, 1, MPI_INT, 0, MPI_COMM_WORLD );

    // (2) global trees
    {
      int *localsizes = new int[ np ];
      int *flags = new int[ np ];

      MPI_Bcast( flags, np, MPI_INT, 0, MPI_COMM_WORLD );
      MPI_Bcast( localsizes, np, MPI_INT, 0, MPI_COMM_WORLD );

      d_tree->read_from_file_create_global_tree( flags, localsizes );

      delete[] flags;
      delete[] localsizes;
    }

    // (3-2) subtrees
    if ( skeleton::rank < np ) {
      const int localsize = d_tree->global_node->value;
      int *flags = new int[ localsize ];
      A *values = new A[ localsize ];

      MPI_Request req1, req2;
      MPI_Irecv( flags, localsize, MPI_INT,
         0, TAG_DISTRIBUTE, MPI_COMM_WORLD, &req1 );
      MPI_Irecv( values, localsize * sizeof( A ), MPI_BYTE,
         0, TAG_DISTRIBUTE, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );

      d_tree->read_from_file_create_subtree( flags, values );

      delete[] values;
      delete[] flags;
    }
  }

  return d_tree;
}

/* public, static */
template< typename A >
node< A >*
tree_skeletons::gather( const dist_tree< A >* d_tree )
{
  if ( skeleton::rank == 0 ) {
    node< A >* s_tree = gather_copy_tree( d_tree->local_root );
    
    int proc = 1;
    gather_rec( s_tree, d_tree->global_root, &proc );
    
    return s_tree;
  } else {
    if ( d_tree->global_node ) {
      int *flags  = new int[ d_tree->global_node->value ];
      A   *values = new A[ d_tree->global_node->value ];
      int *p_flags = flags;
      A   *p_values = values;
      
      tree_util::serialize_subtree( d_tree->local_root, &p_flags, &p_values );
      
      MPI_Request req1, req2;
      MPI_Isend( flags, d_tree->global_node->value, MPI_INT,
         0, TAG_GATHER, MPI_COMM_WORLD, &req1 );
      MPI_Isend( values, d_tree->global_node->value*sizeof( A ), MPI_BYTE,
         0, TAG_GATHER, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );

      delete [] values;
      delete [] flags;
    }
    return NULL;
  }
}

/* private, static */
template< typename A >
void
tree_skeletons::gather_rec( node< A >* root,
                const node< int >* global_root,
                int *proc )
{
  node< A >* cutnode = gather_find_cutnode( root );
  if ( cutnode ) {
    {
      // left sub tree
      int curproc = (*proc)++;
      int size = global_root->left->value;
      int *flags = new int[ size ];
      A *values = new A[ size ];

      MPI_Request req1, req2;
      MPI_Irecv( flags, size, MPI_INT,
         curproc, TAG_GATHER, MPI_COMM_WORLD, &req1 );
      MPI_Irecv( values, size * sizeof( A ), MPI_BYTE,
         curproc, TAG_GATHER, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );
      
      cutnode->left = gather_create_subtree( flags, values );
      cutnode->left->parent = cutnode;

      delete [] flags;
      delete [] values;

      gather_rec( cutnode->left, global_root->left, proc );
    }
    {
      // right sub tree
      int curproc = (*proc)++;
      int size = global_root->right->value;
      int *flags = new int[ size ];
      A *values = new A[ size ];

      MPI_Request req1, req2;
      MPI_Irecv( flags, size, MPI_INT,
         curproc, TAG_GATHER, MPI_COMM_WORLD, &req1 );
      MPI_Irecv( values, size * sizeof( A ), MPI_BYTE,
         curproc, TAG_GATHER, MPI_COMM_WORLD, &req2 );
      MPI_Wait( &req1, MPI_STATUS_IGNORE );
      MPI_Wait( &req2, MPI_STATUS_IGNORE );

      cutnode->right = gather_create_subtree( flags, values );
      cutnode->right->parent = cutnode;

      delete [] flags;
      delete [] values;

      gather_rec( cutnode->right, global_root->right, proc );
    }
  }
}

/* private, static */
template< typename A >
node< A >*
tree_skeletons::gather_find_cutnode( node< A >* root )
{
  if ( root->isLeaf( ) && root->nodetype == node< A >::NORMAL ) {
    return NULL;
  } else if ( root->isLeaf( ) && root->nodetype == node< A >::CUTNODE ) {
    return root;
  } else {
    node< A > *left, *right;
    left = gather_find_cutnode( root->left );
    if ( left ) return left;
    right = gather_find_cutnode( root->right );
    if ( right ) return right;
    return NULL;
  }
}

/* private, static */
template< typename A >
node< A >*
tree_skeletons::gather_create_subtree( const int* flags,
                       const A* values )
{
  const int *pflags = flags;
  const A *pvalues = values;
  return dist_tree< A >::read_from_file_create_subtree_rec( &pflags, &pvalues );
}

/* private, static */
template< typename A >
node< A >*
tree_skeletons::gather_copy_tree( const node< A >* root )
{
  node< A >* ret_node = new node< A >( root->value, root->nodetype );

  if ( root->isLeaf( ) ) {
  } else {
    ret_node->left = gather_copy_tree( root->left );
    ret_node->left->parent = ret_node;
    ret_node->right = gather_copy_tree( root->right );
    ret_node->right->parent = ret_node;
  }

  return ret_node;
}

/* public, static */
template< typename A >
dist_tree< A >*
tree_skeletons::shiftp( const A& rootval,
            const dist_tree< A >* tree )
{
  dist_tree< A > *ret_tree = new dist_tree< A >( tree );
  if ( !tree->local_root ) return ret_tree;

  A cut_node_val;
  ret_tree->local_root = shiftp_rec( tree->local_root, rootval, &cut_node_val );

  // send cut_node_val to child process.
  if ( !tree->global_node->isLeaf( ) ) {
    MPI_Request req1, req2;
    MPI_Isend( &cut_node_val, sizeof( A ), MPI_BYTE,
           tree->proc_leftchild, TAG_SHIFTP, MPI_COMM_WORLD, &req1 );
    MPI_Isend( &cut_node_val, sizeof( A ), MPI_BYTE,
           tree->proc_rightchild, TAG_SHIFTP, MPI_COMM_WORLD, &req2 );
    MPI_Wait( &req1, MPI_STATUS_IGNORE );
    MPI_Wait( &req2, MPI_STATUS_IGNORE );
  }

  // receive root_val from parent process
  A real_rootval;
  if ( skeleton::rank == 0 ) {
    real_rootval = rootval;
  } else {
    MPI_Request req;
    MPI_Irecv( &real_rootval, sizeof( A ), MPI_BYTE,
           tree->proc_parent, TAG_SHIFTP, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }
  ret_tree->local_root->value = real_rootval;
  return ret_tree;
}

/* private, static */
template< typename A >
node< A > *
tree_skeletons::shiftp_rec( const node< A >* root,
                const A& root_val, 
                A *cut_node_val )
{
  node< A > *ret_node = new node< A >( root_val, root->nodetype );
  if ( !root->isLeaf( ) ) {
    ret_node->left  = shiftp_rec( root->left,  root->value, cut_node_val );
    ret_node->right = shiftp_rec( root->right, root->value, cut_node_val );
  }
  if ( root->nodetype == node< A >::CUTNODE ) {
    *cut_node_val = root->value;
  }
  return ret_node;
}

/* public, static */
template< typename A >
dist_tree< A >*
tree_skeletons::shiftl( const A& leafval,
            const dist_tree< A >* tree )
{
  dist_tree< A > *ret_tree = new dist_tree< A >( tree );
  if ( !tree->local_root ) return ret_tree;

  // send value of the root node to parent process,
  // if the block is a left block of the parent process.
  if ( tree->global_node->parent &&
       tree->global_node->parent->left == tree->global_node ) {
    MPI_Request req;
    MPI_Isend( &(tree->local_root->value), sizeof( A ), MPI_BYTE,
           tree->proc_parent, TAG_SHIFTL, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }

  // receive value of the cutnode from left-child process. 
  A left_child_root_val;
  if ( !tree->global_node->isLeaf( ) ) {
    MPI_Request req;
    MPI_Irecv( &left_child_root_val, sizeof( A ), MPI_BYTE,
           tree->proc_leftchild, TAG_SHIFTL, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }

  ret_tree->local_root = shiftl_rec( tree->local_root,
                     leafval,
                     left_child_root_val );
  return ret_tree;
}

/* private, static */
template< typename A >
node< A >*
tree_skeletons::shiftl_rec( const node< A > *root,
                const A& leafval,
                const A& left_child_root_val )
{
  node< A > *ret_node;
  if ( !root->isLeaf( ) ) {
    // internal node
    ret_node = new node< A >( root->left->value, node< A >::NORMAL );
    ret_node->left  = shiftl_rec( root->left,  leafval, left_child_root_val );
    ret_node->right = shiftl_rec( root->right, leafval, left_child_root_val );
  } else if ( root->nodetype == node< A >::NORMAL ) {
    // normal leaf
    ret_node = new node< A >( leafval, node< A >::NORMAL );
  } else {
    // cutnode
    ret_node = new node< A >( left_child_root_val, node< A >::CUTNODE );
  }
  return ret_node;
}

/* public, static */
template< typename A >
dist_tree< A >*
tree_skeletons::shiftr( const A& leafval,
            const dist_tree< A >* tree )
{
  dist_tree< A > *ret_tree = new dist_tree< A >( tree );
  if ( !tree->local_root ) return ret_tree;

  // send value of the root node to parent process,
  // if the block is a right block of the parent process.
  if ( tree->global_node->parent &&
       tree->global_node->parent->right == tree->global_node ) {
    MPI_Request req;
    MPI_Isend( &(tree->local_root->value), sizeof( A ), MPI_BYTE,
           tree->proc_parent, TAG_SHIFTR, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }

  // receive value of the cutnode from right-child process. 
  A right_child_root_val;
  if ( !tree->global_node->isLeaf( ) ) {
    MPI_Request req;
    MPI_Irecv( &right_child_root_val, sizeof( A ), MPI_BYTE,
           tree->proc_rightchild, TAG_SHIFTR, MPI_COMM_WORLD, &req );
    MPI_Wait( &req, MPI_STATUS_IGNORE );
  }

  ret_tree->local_root = shiftr_rec( tree->local_root,
                     leafval,
                     right_child_root_val );
  return ret_tree;
}

/* private, static */
template< typename A >
node< A >*
tree_skeletons::shiftr_rec( const node< A > *root,
                const A& leafval,
                const A& right_child_root_val )
{
  node< A > *ret_node;
  if ( !root->isLeaf( ) ) {
    // internal node
    ret_node = new node< A >( root->right->value, node< A >::NORMAL );
    ret_node->left  = shiftr_rec( root->left,  leafval, right_child_root_val );
    ret_node->right = shiftr_rec( root->right, leafval, right_child_root_val );
  } else if ( root->nodetype == node< A >::NORMAL ) {
    // normal leaf
    ret_node = new node< A >( leafval, node< A >::NORMAL );
  } else {
    // cutnode
    ret_node = new node< A >( right_child_root_val, node< A >::CUTNODE );
  }
  return ret_node;
}


#endif /* __TREE_SKELETONS_TPP__ */
#endif /* __TREE_SKELETONS_H__ */

---