Logo AND Algorithmique Numérique Distribuée

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