src/kernel/routing/AsClusterFatTree.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 <fstream>
   7 #include <sstream>
   8
   9 #include "src/kernel/routing/AsClusterFatTree.hpp"
  10 #include "src/surf/network_interface.hpp"
  11
  12 #include "xbt/lib.h"
  13
  14 #include <boost/algorithm/string/split.hpp>
  15 #include <boost/algorithm/string/classification.hpp>
  16
  17 #include "src/surf/xml/platf.hpp" // FIXME: move that back to the parsing area
  18
  19
  20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_fat_tree, surf, "Routing for fat trees");
  21
  22 namespace simgrid {
  23 namespace kernel {
  24 namespace routing {
  25
  26 AsClusterFatTree::AsClusterFatTree(As* father, const char* name) : AsCluster(father, name)
  27 {
  28   XBT_DEBUG("Creating a new fat tree.");
  29 }
  30
  31 AsClusterFatTree::~AsClusterFatTree() {
  32   for (unsigned int i = 0 ; i < this->nodes_.size() ; i++) {
  33     delete this->nodes_[i];
  34   }
  35   for (unsigned int i = 0 ; i < this->links_.size() ; i++) {
  36     delete this->links_[i];
  37   }
  38 }
  39
  40 bool AsClusterFatTree::isInSubTree(FatTreeNode *root, FatTreeNode *node) {
  41   XBT_DEBUG("Is %d(%u,%u) in the sub tree of %d(%u,%u) ?", node->id,
  42             node->level, node->position, root->id, root->level, root->position);
  43   if (root->level <= node->level) {
  44     return false;
  45   }
  46   for (unsigned int i = 0 ; i < node->level ; i++) {
  47     if(root->label[i] != node->label[i]) {
  48       return false;
  49     }
  50   }
  51
  52   for (unsigned int i = root->level ; i < this->levels_ ; i++) {
  53     if(root->label[i] != node->label[i]) {
  54       return false;
  55     }
  56   }
  57   return true;
  58 }
  59
  60 void AsClusterFatTree::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency)
  61 {
  62
  63   if (dst->isRouter() || src->isRouter())
  64     return;
  65
  66   /* Let's find the source and the destination in our internal structure */
  67   auto searchedNode = this->computeNodes_.find(src->id());
  68   xbt_assert(searchedNode != this->computeNodes_.end(), "Could not find the source %s [%d] in the fat tree",
  69              src->name().c_str(), src->id());
  70   FatTreeNode* source = searchedNode->second;
  71
  72   searchedNode = this->computeNodes_.find(dst->id());
  73   xbt_assert(searchedNode != this->computeNodes_.end(), "Could not find the destination %s [%d] in the fat tree",
  74              dst->name().c_str(), dst->id());
  75   FatTreeNode* destination = searchedNode->second;
  76
  77   XBT_VERB("Get route and latency from '%s' [%d] to '%s' [%d] in a fat tree", src->name().c_str(), src->id(),
  78            dst->name().c_str(), dst->id());
  79
  80   /* In case destination is the source, and there is a loopback, let's use it instead of going up to a switch */
  81   if (source->id == destination->id && this->hasLoopback_) {
  82     into->link_list->push_back(source->loopback);
  83     if (latency)
  84       *latency += source->loopback->latency();
  85     return;
  86   }
  87
  88   FatTreeNode* currentNode = source;
  89
  90   // up part
  91   while (!isInSubTree(currentNode, destination)) {
  92     int d = destination->position; // as in d-mod-k
  93
  94     for (unsigned int i = 0; i < currentNode->level; i++)
  95       d /= this->upperLevelNodesNumber_[i];
  96
  97     int k = this->upperLevelNodesNumber_[currentNode->level];
  98     d = d % k;
  99     into->link_list->push_back(currentNode->parents[d]->upLink);
 100
 101     if (latency)
 102       *latency += currentNode->parents[d]->upLink->latency();
 103
 104     if (this->hasLimiter_)
 105       into->link_list->push_back(currentNode->limiterLink);
 106     currentNode = currentNode->parents[d]->upNode;
 107   }
 108
 109   XBT_DEBUG("%d(%u,%u) is in the sub tree of %d(%u,%u).", destination->id,
 110             destination->level, destination->position, currentNode->id,
 111             currentNode->level, currentNode->position);
 112
 113   // Down part
 114   while (currentNode != destination) {
 115     for(unsigned int i = 0 ; i < currentNode->children.size() ; i++) {
 116       if (i % this->lowerLevelNodesNumber_[currentNode->level - 1] == destination->label[currentNode->level - 1]) {
 117         into->link_list->push_back(currentNode->children[i]->downLink);
 118         if (latency)
 119           *latency += currentNode->children[i]->downLink->latency();
 120         currentNode = currentNode->children[i]->downNode;
 121         if (this->hasLimiter_)
 122           into->link_list->push_back(currentNode->limiterLink);
 123         XBT_DEBUG("%d(%u,%u) is accessible through %d(%u,%u)", destination->id,
 124                   destination->level, destination->position, currentNode->id,
 125                   currentNode->level, currentNode->position);
 126       }
 127     }
 128   }
 129 }
 130
 131 /* This function makes the assumption that parse_specific_arguments() and
 132  * addNodes() have already been called
 133  */
 134 void AsClusterFatTree::seal(){
 135   if(this->levels_ == 0) {
 136     return;
 137   }
 138   this->generateSwitches();
 139
 140
 141   if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) {
 142     std::stringstream msgBuffer;
 143
 144     msgBuffer << "We are creating a fat tree of " << this->levels_ << " levels "
 145               << "with " << this->nodesByLevel_[0] << " processing nodes";
 146     for (unsigned int i = 1 ; i <= this->levels_ ; i++) {
 147       msgBuffer << ", " << this->nodesByLevel_[i] << " switches at level " << i;
 148     }
 149     XBT_DEBUG("%s", msgBuffer.str().c_str());
 150     msgBuffer.str("");
 151     msgBuffer << "Nodes are : ";
 152
 153     for (unsigned int i = 0 ;  i < this->nodes_.size() ; i++) {
 154       msgBuffer << this->nodes_[i]->id << "(" << this->nodes_[i]->level << ","
 155                 << this->nodes_[i]->position << ") ";
 156     }
 157     XBT_DEBUG("%s", msgBuffer.str().c_str());
 158   }
 159
 160
 161   this->generateLabels();
 162
 163   unsigned int k = 0;
 164   // Nodes are totally ordered, by level and then by position, in this->nodes
 165   for (unsigned int i = 0 ; i < this->levels_ ; i++) {
 166     for (unsigned int j = 0 ; j < this->nodesByLevel_[i] ; j++) {
 167         this->connectNodeToParents(this->nodes_[k]);
 168         k++;
 169     }
 170   }
 171
 172   if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) {
 173     std::stringstream msgBuffer;
 174     msgBuffer << "Links are : ";
 175     for (unsigned int i = 0 ; i < this->links_.size() ; i++) {
 176       msgBuffer << "(" << this->links_[i]->upNode->id << ","
 177                 << this->links_[i]->downNode->id << ") ";
 178     }
 179     XBT_DEBUG("%s", msgBuffer.str().c_str());
 180   }
 181
 182
 183 }
 184
 185 int AsClusterFatTree::connectNodeToParents(FatTreeNode *node) {
 186   std::vector<FatTreeNode*>::iterator currentParentNode = this->nodes_.begin();
 187   int connectionsNumber = 0;
 188   const int level = node->level;
 189   XBT_DEBUG("We are connecting node %d(%u,%u) to his parents.",
 190             node->id, node->level, node->position);
 191   currentParentNode += this->getLevelPosition(level + 1);
 192   for (unsigned int i = 0 ; i < this->nodesByLevel_[level + 1] ; i++ ) {
 193     if(this->areRelated(*currentParentNode, node)) {
 194       XBT_DEBUG("%d(%u,%u) and %d(%u,%u) are related,"
 195                 " with %u links between them.", node->id,
 196                 node->level, node->position, (*currentParentNode)->id,
 197                 (*currentParentNode)->level, (*currentParentNode)->position, this->lowerLevelPortsNumber_[level]);
 198       for (unsigned int j = 0 ; j < this->lowerLevelPortsNumber_[level] ; j++) {
 199       this->addLink(*currentParentNode, node->label[level] +
 200                     j * this->lowerLevelNodesNumber_[level], node,
 201                     (*currentParentNode)->label[level] +
 202                     j * this->upperLevelNodesNumber_[level]);
 203       }
 204       connectionsNumber++;
 205     }
 206     ++currentParentNode;
 207   }
 208   return connectionsNumber;
 209 }
 210
 211
 212 bool AsClusterFatTree::areRelated(FatTreeNode *parent, FatTreeNode *child) {
 213   std::stringstream msgBuffer;
 214
 215   if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) {
 216     msgBuffer << "Are " << child->id << "(" << child->level << ","
 217               << child->position << ") <";
 218
 219     for (unsigned int i = 0 ; i < this->levels_ ; i++) {
 220       msgBuffer << child->label[i] << ",";
 221     }
 222     msgBuffer << ">";
 223
 224     msgBuffer << " and " << parent->id << "(" << parent->level
 225               << "," << parent->position << ") <";
 226     for (unsigned int i = 0 ; i < this->levels_ ; i++) {
 227       msgBuffer << parent->label[i] << ",";
 228     }
 229     msgBuffer << ">";
 230     msgBuffer << " related ? ";
 231     XBT_DEBUG("%s", msgBuffer.str().c_str());
 232
 233   }
 234   if (parent->level != child->level + 1) {
 235     return false;
 236   }
 237
 238   for (unsigned int i = 0 ; i < this->levels_; i++) {
 239     if (parent->label[i] != child->label[i] && i + 1 != parent->level) {
 240       return false;
 241     }
 242   }
 243   return true;
 244 }
 245
 246 void AsClusterFatTree::generateSwitches() {
 247   XBT_DEBUG("Generating switches.");
 248   this->nodesByLevel_.resize(this->levels_ + 1, 0);
 249   unsigned int nodesRequired = 0;
 250
 251   // Take care of the number of nodes by level
 252   this->nodesByLevel_[0] = 1;
 253   for (unsigned int i = 0 ; i < this->levels_ ; i++)
 254     this->nodesByLevel_[0] *= this->lowerLevelNodesNumber_[i];
 255
 256   if(this->nodesByLevel_[0] != this->nodes_.size()) {
 257     surf_parse_error("The number of provided nodes does not fit with the wanted topology."
 258                      " Please check your platform description (We need %d nodes, we got %zu)",
 259                      this->nodesByLevel_[0], this->nodes_.size());
 260     return;
 261   }
 262
 263
 264   for (unsigned int i = 0 ; i < this->levels_ ; i++) {
 265     int nodesInThisLevel = 1;
 266
 267     for (unsigned int j = 0 ;  j <= i ; j++)
 268       nodesInThisLevel *= this->upperLevelNodesNumber_[j];
 269
 270     for (unsigned int j = i+1 ; j < this->levels_ ; j++)
 271       nodesInThisLevel *= this->lowerLevelNodesNumber_[j];
 272
 273     this->nodesByLevel_[i+1] = nodesInThisLevel;
 274     nodesRequired += nodesInThisLevel;
 275   }
 276
 277
 278   // Create the switches
 279   int k = 0;
 280   for (unsigned int i = 0 ; i < this->levels_ ; i++) {
 281     for (unsigned int j = 0 ; j < this->nodesByLevel_[i + 1] ; j++) {
 282       FatTreeNode* newNode = new FatTreeNode(this->cluster_, --k, i + 1, j);
 283       XBT_DEBUG("We create the switch %d(%d,%d)", newNode->id, newNode->level, newNode->position);
 284       newNode->children.resize(this->lowerLevelNodesNumber_[i] *
 285                                this->lowerLevelPortsNumber_[i]);
 286       if (i != this->levels_ - 1) {
 287         newNode->parents.resize(this->upperLevelNodesNumber_[i + 1] *
 288                                 this->lowerLevelPortsNumber_[i + 1]);
 289       }
 290       newNode->label.resize(this->levels_);
 291       this->nodes_.push_back(newNode);
 292     }
 293   }
 294 }
 295
 296 void AsClusterFatTree::generateLabels() {
 297   XBT_DEBUG("Generating labels.");
 298   // TODO : check if nodesByLevel and nodes are filled
 299   std::vector<int> maxLabel(this->levels_);
 300   std::vector<int> currentLabel(this->levels_);
 301   unsigned int k = 0;
 302   for (unsigned int i = 0 ; i <= this->levels_ ; i++) {
 303     currentLabel.assign(this->levels_, 0);
 304     for (unsigned int j = 0 ; j < this->levels_ ; j++) {
 305       maxLabel[j] = j + 1 > i ?
 306         this->lowerLevelNodesNumber_[j] : this->upperLevelNodesNumber_[j];
 307     }
 308
 309     for (unsigned int j = 0 ; j < this->nodesByLevel_[i] ; j++) {
 310
 311       if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug )) {
 312         std::stringstream msgBuffer;
 313
 314         msgBuffer << "Assigning label <";
 315         for (unsigned int l = 0 ; l < this->levels_ ; l++) {
 316           msgBuffer << currentLabel[l] << ",";
 317         }
 318         msgBuffer << "> to " << k << " (" << i << "," << j <<")";
 319
 320         XBT_DEBUG("%s", msgBuffer.str().c_str());
 321       }
 322       this->nodes_[k]->label.assign(currentLabel.begin(), currentLabel.end());
 323
 324       bool remainder = true;
 325       unsigned int pos = 0;
 326       while (remainder && pos < this->levels_) {
 327         ++currentLabel[pos];
 328         if (currentLabel[pos] >= maxLabel[pos]) {
 329           currentLabel[pos] = 0;
 330           remainder = true;
 331           ++pos;
 332         }
 333         else {
 334           pos = 0;
 335           remainder = false;
 336         }
 337       }
 338       k++;
 339     }
 340   }
 341 }
 342
 343
 344 int AsClusterFatTree::getLevelPosition(const unsigned  int level) {
 345   xbt_assert(level <= this->levels_, "The impossible did happen. Yet again.");
 346   int tempPosition = 0;
 347
 348   for (unsigned int i = 0 ; i < level ; i++)
 349     tempPosition += this->nodesByLevel_[i];
 350
 351   return tempPosition;
 352 }
 353
 354 void AsClusterFatTree::addProcessingNode(int id) {
 355   using std::make_pair;
 356   static int position = 0;
 357   FatTreeNode* newNode;
 358   newNode = new FatTreeNode(this->cluster_, id, 0, position++);
 359   newNode->parents.resize(this->upperLevelNodesNumber_[0] *
 360                           this->lowerLevelPortsNumber_[0]);
 361   newNode->label.resize(this->levels_);
 362   this->computeNodes_.insert(make_pair(id,newNode));
 363   this->nodes_.push_back(newNode);
 364 }
 365
 366 void AsClusterFatTree::addLink(FatTreeNode *parent, unsigned int parentPort,
 367                                FatTreeNode *child, unsigned int childPort) {
 368   FatTreeLink *newLink;
 369   newLink = new FatTreeLink(this->cluster_, child, parent);
 370   XBT_DEBUG("Creating a link between the parent (%d,%d,%u) and the child (%d,%d,%u)",
 371       parent->level, parent->position, parentPort, child->level, child->position, childPort);
 372   parent->children[parentPort] = newLink;
 373   child->parents[childPort] = newLink;
 374
 375   this->links_.push_back(newLink);
 376 }
 377
 378 void AsClusterFatTree::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) {
 379   std::vector<std::string> parameters;
 380   std::vector<std::string> tmp;
 381   boost::split(parameters, cluster->topo_parameters, boost::is_any_of(";"));
 382
 383   // TODO : we have to check for zeros and negative numbers, or it might crash
 384   if (parameters.size() != 4){
 385     surf_parse_error("Fat trees are defined by the levels number and 3 vectors, see the documentation for more information");
 386   }
 387
 388   // The first parts of topo_parameters should be the levels number
 389   this->levels_ = xbt_str_parse_int(parameters[0].c_str(), "First parameter is not the amount of levels: %s");
 390
 391   // Then, a l-sized vector standing for the children number by level
 392   boost::split(tmp, parameters[1], boost::is_any_of(","));
 393   if(tmp.size() != this->levels_) {
 394     surf_parse_error("Fat trees are defined by the levels number and 3 vectors"
 395                      ", see the documentation for more information");
 396   }
 397   for(size_t i = 0 ; i < tmp.size() ; i++){
 398     this->lowerLevelNodesNumber_.push_back(xbt_str_parse_int(tmp[i].c_str(), "Invalid lower level node number: %s"));
 399   }
 400
 401   // Then, a l-sized vector standing for the parents number by level
 402   boost::split(tmp, parameters[2], boost::is_any_of(","));
 403   if(tmp.size() != this->levels_) {
 404     surf_parse_error("Fat trees are defined by the levels number and 3 vectors"
 405                      ", see the documentation for more information");
 406   }
 407   for(size_t i = 0 ; i < tmp.size() ; i++){
 408     this->upperLevelNodesNumber_.push_back(xbt_str_parse_int(tmp[i].c_str(), "Invalid upper level node number: %s"));
 409   }
 410
 411   // Finally, a l-sized vector standing for the ports number with the lower level
 412   boost::split(tmp, parameters[3], boost::is_any_of(","));
 413   if(tmp.size() != this->levels_) {
 414     surf_parse_error("Fat trees are defined by the levels number and 3 vectors"
 415                      ", see the documentation for more information");
 416
 417   }
 418   for(size_t i = 0 ; i < tmp.size() ; i++){
 419     this->lowerLevelPortsNumber_.push_back(xbt_str_parse_int(tmp[i].c_str(), "Invalid lower level node number: %s"));
 420   }
 421   this->cluster_ = cluster;
 422 }
 423
 424
 425 void AsClusterFatTree::generateDotFile(const std::string& filename) const {
 426   std::ofstream file;
 427   file.open(filename, std::ios::out | std::ios::trunc);
 428   xbt_assert(file.is_open(), "Unable to open file %s", filename.c_str());
 429
 430   file << "graph AsClusterFatTree {\n";
 431   for (unsigned int i = 0 ; i < this->nodes_.size() ; i++) {
 432     file << this->nodes_[i]->id;
 433     if(this->nodes_[i]->id < 0)
 434       file << " [shape=circle];\n";
 435     else
 436       file << " [shape=hexagon];\n";
 437   }
 438
 439   for (unsigned int i = 0 ; i < this->links_.size() ; i++ ) {
 440     file << this->links_[i]->downNode->id
 441         << " -- "
 442         << this->links_[i]->upNode->id
 443         << ";\n";
 444   }
 445   file << "}";
 446   file.close();
 447 }
 448
 449 FatTreeNode::FatTreeNode(sg_platf_cluster_cbarg_t cluster, int id, int level,
 450                          int position) : id(id), level(level),
 451                                          position(position) {
 452   s_sg_platf_link_cbarg_t linkTemplate;
 453   if(cluster->limiter_link) {
 454     memset(&linkTemplate, 0, sizeof(linkTemplate));
 455     linkTemplate.bandwidth = cluster->limiter_link;
 456     linkTemplate.latency = 0;
 457     linkTemplate.policy = SURF_LINK_SHARED;
 458     linkTemplate.id = bprintf("limiter_%d", id);
 459     sg_platf_new_link(&linkTemplate);
 460     this->limiterLink = Link::byName(linkTemplate.id);
 461     free((void*)linkTemplate.id);
 462   }
 463   if(cluster->loopback_bw || cluster->loopback_lat) {
 464     memset(&linkTemplate, 0, sizeof(linkTemplate));
 465     linkTemplate.bandwidth = cluster->loopback_bw;
 466     linkTemplate.latency = cluster->loopback_lat;
 467     linkTemplate.policy = SURF_LINK_FATPIPE;
 468     linkTemplate.id = bprintf("loopback_%d", id);
 469     sg_platf_new_link(&linkTemplate);
 470     this->loopback = Link::byName(linkTemplate.id);
 471     free((void*)linkTemplate.id);
 472   }
 473 }
 474
 475 FatTreeLink::FatTreeLink(sg_platf_cluster_cbarg_t cluster,
 476                          FatTreeNode *downNode,
 477                          FatTreeNode *upNode) : upNode(upNode),
 478                                                 downNode(downNode) {
 479   static int uniqueId = 0;
 480   s_sg_platf_link_cbarg_t linkTemplate;
 481   memset(&linkTemplate, 0, sizeof(linkTemplate));
 482   linkTemplate.bandwidth = cluster->bw;
 483   linkTemplate.latency = cluster->lat;
 484   linkTemplate.policy = cluster->sharing_policy; // sthg to do with that ?
 485   linkTemplate.id = bprintf("link_from_%d_to_%d_%d", downNode->id, upNode->id, uniqueId);
 486   sg_platf_new_link(&linkTemplate);
 487   Link* link;
 488   std::string tmpID;
 489   if (cluster->sharing_policy == SURF_LINK_FULLDUPLEX) {
 490     tmpID = std::string(linkTemplate.id) + "_UP";
 491     link =  Link::byName(tmpID.c_str());
 492     this->upLink = link; // check link?
 493     tmpID = std::string(linkTemplate.id) + "_DOWN";
 494     link = Link::byName(tmpID.c_str());
 495     this->downLink = link; // check link ?
 496   }
 497   else {
 498     link = Link::byName(linkTemplate.id);
 499     this->upLink = link;
 500     this->downLink = link;
 501   }
 502   uniqueId++;
 503   free((void*)linkTemplate.id);
 504 }
 505
 506 }}} // namespace