nm_coll_trees.h

Go to the documentation of this file.

/*
 * NewMadeleine
 * Copyright (C) 2014-2026 (see AUTHORS file)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 */
 
#include <nm_log.h>
#include <nm_core_interface.h>
 
enum nm_coll_tree_kind_e
  {
    NM_COLL_TREE_NONE = 0,
    NM_COLL_TREE_FLAT,
    NM_COLL_TREE_CHAIN,
    NM_COLL_TREE_CHAIN_MODIFIED,   
    NM_COLL_TREE_2CHAINS_MODIFIED, 
    NM_COLL_TREE_LADDER,
    NM_COLL_TREE_BINOMIAL,
    NM_COLL_TREE_3NOMIAL,
    NM_COLL_TREE_4NOMIAL,
    NM_COLL_TREE_8NOMIAL,
    NM_COLL_TREE_16NOMIAL,
    NM_COLL_TREE_BINARY,
    NM_COLL_TREE_3ARY,
    NM_COLL_TREE_4ARY,
    NM_COLL_TREE_8ARY,
    NM_COLL_TREE_HBINARY,
    NM_COLL_TREE_H4ARY,
    NM_COLL_TREE_HBINOMIAL,
    NM_COLL_TREE_H4NOMIAL,
    NM_COLL_TREE_DEFAULT,  
    _NM_COLL_TREE_MAX
  };
typedef enum nm_coll_tree_kind_e nm_coll_tree_kind_t;
 
struct nm_coll_tree_info_s
{
  nm_coll_tree_kind_t kind;
  int max_arity;  
  int n;          
  int self;       
  int root;       
  int height;     
  struct nm_coll_topology_s*p_topology; 
  void*_status;   
};
 
 
/* ** generic trees **************************************** */
 
void nm_coll_tree_init(struct nm_coll_tree_info_s*p_tree, nm_coll_tree_kind_t kind, int n, int self,
                       const struct nm_coll_topology_s*p_topology, int root);
 
void nm_coll_tree_step(const struct nm_coll_tree_info_s*p_tree, int step, int*p_parent, int*p_children, int*n_children);
 
void nm_coll_tree_destroy(struct nm_coll_tree_info_s*p_tree);
 
int nm_coll_tree_weight(const struct nm_coll_tree_info_s*p_tree, int step, int self);
 
const char*nm_coll_tree_kind_name(nm_coll_tree_kind_t kind);
 
nm_coll_tree_kind_t nm_coll_tree_kind_by_name(const char*s_kind);
 
int nm_coll_tree_has_weight(nm_coll_tree_kind_t k);
 
void nm_coll_tree_descendants(const struct nm_coll_tree_info_s*p_tree, int step, int self, int*p_descendants);
 
int nm_coll_tree_has_descendants(nm_coll_tree_kind_t k);
 
nm_coll_tree_kind_t nm_coll_tree_heuristic(int comm_size, nm_len_t data_size, const struct nm_coll_topology_s*p_topology);
 
nm_coll_tree_kind_t nm_coll_tree_weight_heuristic(int comm_size, nm_len_t data_size, const struct nm_coll_topology_s*p_topology);
 
int nm_coll_binary_nb_nodes_in_left_subtree(const struct nm_coll_tree_info_s* const p_tree);
 
static inline int nm_coll_tree_max_weight(const struct nm_coll_tree_info_s*p_tree)
{
  int max_weight = 0;
  int s;
  for(s = 0; s < p_tree->height; s++)
    {
      int p = -1, n = -1;
      int c[p_tree->max_arity];
      nm_coll_tree_step(p_tree, s, &p, c, &n);
      if(p != -1)
        {
          max_weight = nm_coll_tree_weight(p_tree, s, p_tree->self);
          break;
        }
    }
  return max_weight;
}
 
/* ** toolbox ********************************************** */
 
static inline int nm_coll_ispow2(int x)
{
  return (x != 0) && ((x & (x - 1)) == 0);
}
 
static inline int nm_coll_log2_floor(int x)
{
  assert(x > 0);
  return ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((x)) - 1));
}
 
static inline int nm_coll_log2_ceil(int x)
{
  assert(x > 0);
  return nm_coll_log2_floor(x) + (!!(x & (x - 1)));
}
 
static inline int nm_coll_log4_floor(int x)
{
  return nm_coll_log2_floor(x) / 2;
}
 
static inline int nm_coll_ipow(int base, int exp)
{
  assert(base >= 0);
  assert(exp >= 0);
  /* cascade of tests should be elided by the compiler when base is a compile-time constant */
  if(base == 2)
    return 1 << exp;
  else if(base == 4)
    return 1 << (2 * exp);
  else if(base == 8)
    return 1 << (3 * exp);
  else if(base == 16)
    return 1 << (4 * exp);
  int result = 1;
  for(;;)
    {
      if(exp & 1)
        result *= base;
      exp >>= 1;
      if(!exp)
        break;
      base *= base;
    }
  return result;
}
 
static inline int nm_coll_log_n_ceil(int x, const int n)
{
  assert(x > 0);
  assert(n >= 2);
  int l = 0;
  int exp = n - 1;
  x--;
  while(x > 0)
    {
      x -= exp;
      exp *= n;
      l++;
    }
  return l;
}
 
static inline int nm_coll_log_n_floor(int x, const int n)
{
  assert(x >= 1);
  assert(n >= 2);
  int l = 0;
  while(x >= n)
    {
      l++;
      x = x / n;
    }
  return l;
}
 
static inline int nm_coll_r2v(int i, const struct nm_coll_tree_info_s*p_tree)
{
  return ((p_tree->n + i - p_tree->root) % p_tree->n);
}
 
static inline int nm_coll_v2r(int i, const struct nm_coll_tree_info_s*p_tree)
{
  return ((p_tree->root + i) % p_tree->n);
}
 
/* ********************************************************* */
 
struct nm_coll_tree_status_s
{
  nm_session_t p_session;
  nm_group_t p_group;
  nm_tag_t tag;
  struct nm_coll_tree_info_s tree;
  int n_children;
  int*children;
  nm_sr_request_t*children_requests;
  nm_sr_request_t parent_request;
  int pending_reqs;                   
};
 
static inline void nm_coll_tree_status_init(struct nm_coll_tree_status_s*p_status, nm_session_t p_session,
                                            nm_coll_tree_kind_t kind, nm_group_t p_group, int root, int self,
                                            nm_tag_t tag)
{
  p_status->p_session = p_session;
  p_status->p_group = p_group;
  p_status->tag = tag;
  nm_coll_tree_init(&p_status->tree, kind, nm_group_size(p_group), self, nm_group_get_topology(p_group), root);
  p_status->n_children = -1;
  p_status->children_requests = padico_malloc((1 + p_status->tree.max_arity) * sizeof(nm_sr_request_t));
  p_status->children = padico_malloc((1 + p_status->tree.max_arity) * sizeof(int));
  p_status->pending_reqs = 0;
}
 
static inline void nm_coll_tree_status_destroy(struct nm_coll_tree_status_s*p_status)
{
  assert(p_status->p_session != NULL);
  p_status->p_session = NULL;
  assert(p_status->p_group != NULL);
  p_status->p_group = NULL;
  assert(p_status->pending_reqs == 0);
  padico_free(p_status->children_requests);
  p_status->children_requests = NULL;
  padico_free(p_status->children);
  p_status->children = NULL;
  nm_coll_tree_destroy(&p_status->tree);
}
 
static inline void nm_coll_tree_send(struct nm_coll_tree_status_s*p_coll_tree, int dest,
                                     struct nm_data_s*p_data, nm_sr_request_t*p_req)
{
  assert(dest != -1);
  nm_gate_t p_gate = nm_group_get_gate(p_coll_tree->p_group, dest);
  nm_atomic_inc(&p_coll_tree->pending_reqs);
  nm_sr_isend_data(p_coll_tree->p_session, p_gate, p_coll_tree->tag, p_data, p_req);
}
 
static inline void nm_coll_tree_issend(struct nm_coll_tree_status_s*p_coll_tree, int dest,
                                       struct nm_data_s*p_data, nm_sr_request_t*p_req)
{
  assert(dest != -1);
  nm_gate_t p_gate = nm_group_get_gate(p_coll_tree->p_group, dest);
  nm_atomic_inc(&p_coll_tree->pending_reqs);
  nm_sr_send_init(p_coll_tree->p_session, p_req);
  nm_sr_send_pack_data(p_coll_tree->p_session, p_req, p_data);
  nm_sr_send_issend(p_coll_tree->p_session, p_req, p_gate, p_coll_tree->tag);
}
 
static inline void nm_coll_tree_recv(struct nm_coll_tree_status_s*p_coll_tree, int from,
                                     struct nm_data_s*p_data, nm_sr_request_t*p_req)
{
  assert(from != -1);
  nm_gate_t p_gate = nm_group_get_gate(p_coll_tree->p_group, from);
  nm_atomic_inc(&p_coll_tree->pending_reqs);
  nm_sr_irecv_data(p_coll_tree->p_session, p_gate, p_coll_tree->tag, p_data, p_req);
}
 
static inline void nm_coll_tree_set_notifier(struct nm_coll_tree_status_s*p_coll_tree, nm_sr_request_t*p_req,
                                            void(*p_notifier)(nm_sr_event_t, const nm_sr_event_info_t*, void*))
{
  nm_sr_request_set_ref(p_req, p_coll_tree);
  nm_sr_request_monitor(p_coll_tree->p_session, p_req, NM_SR_EVENT_FINALIZED, p_notifier);
}
 
static inline int nm_coll_tree_req_index(struct nm_coll_tree_status_s*p_coll_tree, nm_sr_request_t*p_request)
{
  if( (p_request < &p_coll_tree->children_requests[0]) ||
      (p_request > &p_coll_tree->children_requests[p_coll_tree->tree.max_arity - 1]) )
    {
      NM_FATAL("given p_request = %p is not in coll_tree", p_request);
    }
  const int i = p_request - p_coll_tree->children_requests;
  assert(i >= 0);
  assert(i < p_coll_tree->tree.max_arity);
  return i;
}