src/kernel/routing/TorusZone.cpp

   1 /* Copyright (c) 2014-2016. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/kernel/routing/TorusZone.hpp"
   7 #include "src/kernel/routing/NetPoint.hpp"
   8 #include "src/surf/network_interface.hpp"
   9
  10 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_cluster_torus, surf_route_cluster, "Torus Routing part of surf");
  11
  12 inline void rankId_to_coords(int rankId, std::vector<unsigned int> dimensions, unsigned int (*coords)[4])
  13 {
  14   unsigned int dim_size_product = 1;
  15   unsigned int i = 0;
  16   for (auto cur_dim_size: dimensions) {
  17     (*coords)[i] = (rankId / dim_size_product) % cur_dim_size;
  18     dim_size_product *= cur_dim_size;
  19     i++;
  20   }
  21 }
  22
  23 namespace simgrid {
  24 namespace kernel {
  25 namespace routing {
  26 TorusZone::TorusZone(NetZone* father, const char* name) : ClusterZone(father, name)
  27 {
  28 }
  29
  30 void TorusZone::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position)
  31 {
  32   /*
  33    * Create all links that exist in the torus.
  34    * Each rank creates @a dimensions-1 links
  35    */
  36   int neighbor_rank_id  = 0; // The other node the link connects
  37   int current_dimension = 0; // which dimension are we currently in?
  38       // we need to iterate over all dimensions
  39       // and create all links there
  40   int dim_product = 1; // Needed to calculate the next neighbor_id
  41   for (unsigned int j = 0; j < dimensions_.size(); j++) {
  42
  43     LinkCreationArgs link;
  44     current_dimension = dimensions_.at(j);
  45     neighbor_rank_id  = ((static_cast<int>(rank) / dim_product) % current_dimension == current_dimension - 1)
  46                            ? rank - (current_dimension - 1) * dim_product
  47                            : rank + dim_product;
  48     // name of neighbor is not right for non contiguous cluster radicals (as id != rank in this case)
  49     char* link_id  = bprintf("%s_link_from_%i_to_%i", cluster->id, id, neighbor_rank_id);
  50     link.id        = link_id;
  51     link.bandwidth = cluster->bw;
  52     link.latency   = cluster->lat;
  53     link.policy    = cluster->sharing_policy;
  54     sg_platf_new_link(&link);
  55     surf::LinkImpl* linkUp;
  56     surf::LinkImpl* linkDown;
  57     if (link.policy == SURF_LINK_FULLDUPLEX) {
  58       char* tmp_link = bprintf("%s_UP", link_id);
  59       linkUp         = surf::LinkImpl::byName(tmp_link);
  60       free(tmp_link);
  61       tmp_link = bprintf("%s_DOWN", link_id);
  62       linkDown = surf::LinkImpl::byName(tmp_link);
  63       free(tmp_link);
  64     } else {
  65       linkUp   = surf::LinkImpl::byName(link_id);
  66       linkDown = linkUp;
  67     }
  68     /*
  69      * Add the link to its appropriate position;
  70      * note that position rankId*(xbt_dynar_length(dimensions)+has_loopback?+has_limiter?)
  71      * holds the link "rankId->rankId"
  72      */
  73     privateLinks_.insert({position + j, {linkUp, linkDown}});
  74     dim_product *= current_dimension;
  75     xbt_free(link_id);
  76   }
  77   rank++;
  78 }
  79
  80 void TorusZone::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster)
  81 {
  82
  83   unsigned int iter;
  84   char* groups;
  85   xbt_dynar_t dimensions = xbt_str_split(cluster->topo_parameters, ",");
  86
  87   if (!xbt_dynar_is_empty(dimensions)) {
  88     /* We are in a torus cluster
  89      * Parse attribute dimensions="dim1,dim2,dim3,...,dimN" and safe it in a vector.
  90      * Additionally, we need to know how many ranks we have in total
  91      */
  92     xbt_dynar_foreach (dimensions, iter, groups) {
  93       dimensions_.push_back(surf_parse_get_int(groups));
  94     }
  95
  96     linkCountPerNode_ = dimensions_.size();
  97   }
  98   xbt_dynar_free(&dimensions);
  99 }
 100
 101 void TorusZone::getLocalRoute(NetPoint* src, NetPoint* dst, sg_platf_route_cbarg_t route, double* lat)
 102 {
 103
 104   XBT_VERB("torus getLocalRoute from '%s'[%d] to '%s'[%d]", src->name().c_str(), src->id(), dst->name().c_str(),
 105            dst->id());
 106
 107   if (dst->isRouter() || src->isRouter())
 108     return;
 109
 110   if (src->id() == dst->id() && hasLoopback_) {
 111     std::pair<surf::LinkImpl*, surf::LinkImpl*> info = privateLinks_.at(src->id() * linkCountPerNode_);
 112
 113     route->link_list->push_back(info.first);
 114     if (lat)
 115       *lat += info.first->latency();
 116     return;
 117   }
 118
 119   /*
 120    * Dimension based routing routes through each dimension consecutively
 121    * TODO Change to dynamic assignment
 122    */
 123   unsigned int dim_product = 1;
 124   unsigned int current_node = src->id();
 125   unsigned int next_node    = 0;
 126   /*
 127    * Arrays that hold the coordinates of the current node and
 128    * the target; comparing the values at the i-th position of
 129    * both arrays, we can easily assess whether we need to route
 130    * into this dimension or not.
 131    */
 132   unsigned int myCoords[4];
 133   rankId_to_coords(src->id(), dimensions_, &myCoords);
 134   unsigned int targetCoords[4];
 135   rankId_to_coords(dst->id(), dimensions_, &targetCoords);
 136   /*
 137    * linkOffset describes the offset where the link
 138    * we want to use is stored
 139    * (+1 is added because each node has a link from itself to itself,
 140    * which can only be the case if src->m_id == dst->m_id -- see above
 141    * for this special case)
 142    */
 143   int nodeOffset = (dimensions_.size() + 1) * src->id();
 144
 145   int linkOffset  = nodeOffset;
 146   bool use_lnk_up = false; // Is this link of the form "cur -> next" or "next -> cur"?
 147   // false means: next -> cur
 148   while (current_node != dst->id()) {
 149     dim_product = 1; // First, we will route in x-dimension
 150     int j=0;
 151     for (auto cur_dim : dimensions_){
 152       // current_node/dim_product = position in current dimension
 153       if ((current_node / dim_product) % cur_dim != (dst->id() / dim_product) % cur_dim) {
 154
 155         if ((targetCoords[j] > myCoords[j] &&
 156              targetCoords[j] <= myCoords[j] + cur_dim / 2) // Is the target node on the right, without the wrap-around?
 157             || (myCoords[j] > cur_dim / 2 &&
 158                 (myCoords[j] + cur_dim / 2) % cur_dim >=
 159                     targetCoords[j])) { // Or do we need to use the wrap around to reach it?
 160           if ((current_node / dim_product) % cur_dim == cur_dim - 1)
 161             next_node = (current_node + dim_product - dim_product * cur_dim);
 162           else
 163             next_node = (current_node + dim_product);
 164
 165           // HERE: We use *CURRENT* node for calculation (as opposed to next_node)
 166           nodeOffset = current_node * (linkCountPerNode_);
 167           linkOffset = nodeOffset + (hasLoopback_ ? 1 : 0) + (hasLimiter_ ? 1 : 0) + j;
 168           use_lnk_up = true;
 169           assert(linkOffset >= 0);
 170         } else { // Route to the left
 171           if ((current_node / dim_product) % cur_dim == 0)
 172             next_node = (current_node - dim_product + dim_product * cur_dim);
 173           else
 174             next_node = (current_node - dim_product);
 175
 176           // HERE: We use *next* node for calculation (as opposed to current_node!)
 177           nodeOffset = next_node * (linkCountPerNode_);
 178           linkOffset = nodeOffset + j + (hasLoopback_ ? 1 : 0) + (hasLimiter_ ? 1 : 0);
 179           use_lnk_up = false;
 180
 181           assert(linkOffset >= 0);
 182         }
 183         XBT_DEBUG("torus_get_route_and_latency - current_node: %i, next_node: %u, linkOffset is %i", current_node,
 184                   next_node, linkOffset);
 185         break;
 186       }
 187
 188       j++;
 189       dim_product *= cur_dim;
 190     }
 191
 192     std::pair<surf::LinkImpl*, surf::LinkImpl*> info;
 193
 194     if (hasLimiter_) { // limiter for sender
 195       info = privateLinks_.at(nodeOffset + hasLoopback_);
 196       route->link_list->push_back(info.first);
 197     }
 198
 199     info = privateLinks_.at(linkOffset);
 200
 201     if (use_lnk_up == false) {
 202       route->link_list->push_back(info.second);
 203       if (lat)
 204         *lat += info.second->latency();
 205     } else {
 206       route->link_list->push_back(info.first);
 207       if (lat)
 208         *lat += info.first->latency();
 209     }
 210     current_node = next_node;
 211     next_node    = 0;
 212   }
 213 }
 214 }
 215 }
 216 } // namespace