src/surf/surf_routing_cluster_fat_tree.cpp

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