src/surf/surf_routing_cluster_fat_tree.cpp

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