From: Stéphane Castelli <stephane.castelli@loria.fr>
Date: Tue, 15 Apr 2014 15:51:18 +0000 (+0200)
Subject: Added some work in the creation of links in the fat trees, basically the repartion... 
X-Git-Tag: v3_11~118
X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/20984b0bb3a1e3e5e213963d9182b1c15baba23c

Added some work in the creation of links in the fat trees, basically the repartion of nodes through the levels.

Method to generate a .dot file, almost done

Merge branch 'master' of git+ssh://scm.gforge.inria.fr//gitroot/simgrid/simgrid
---

20984b0bb3a1e3e5e213963d9182b1c15baba23c
diff --cc src/surf/surf_routing_cluster_fat_tree.cpp
index 5cb6728779,0000000000..f852c3682b
mode 100644,000000..100644
--- a/src/surf/surf_routing_cluster_fat_tree.cpp
+++ b/src/surf/surf_routing_cluster_fat_tree.cpp
@@@ -1,77 -1,0 +1,165 @@@
 +#include "surf_routing_cluster_fat_tree.hpp"
 +
 +#include <boost/algorithm/string/split.hpp>
 +#include <boost/algorithm/string/classification.hpp>
 +
++#include <iostream>
++#include <fstream>
 +
- AsClusterFatTree::AsClusterFatTree() : levels(0) {}
 +
++AsClusterFatTree::AsClusterFatTree() : levels(0) {}
 +
++AsClusterFatTree::~AsClusterFatTree() {
++  for (int i = 0 ; i < this->nodes.size() ; i++) {
++    delete this->nodes[i];
++  }
++}
 +
 +void AsClusterFatTree::getRouteAndLatency(RoutingEdgePtr src,
 +                                          RoutingEdgePtr dst,
 +                                          sg_platf_route_cbarg_t into,
-                                           double *latency) {
++                                          double *latency) const{
 +  // TODO
 +}
 +
- void AsClusterFatTree::create_links() {
++/* This function makes the assumption that parse_specific_arguments() and
++ * addNodes() have already been called
++ */
++void AsClusterFatTree::create_links(sg_platf_cluster_cbarg_t cluster) {
++
 +  if(this->levels == 0) {
 +    return;
 +  }
-   
-   for (unsigned int i = 0 ; i < this->levels) {
-     
-   }
++  std::vector<int> nodesByLevel(this->levels); 
++  int nodesRequired = 0;
++
++
++    for (int i = 0 ; i < this->levels ; i++) {
++      int nodesInThisLevel = 1;
++      
++      for (int j = 0 ;  j < i ; j++) {
++        nodesInThisLevel *= this->upperLevelNodesNumber[j];
++      }
++      
++      for (int j = i+1 ; j < this->levels ; j++) {
++        nodesInThisLevel *= this->lowerLevelNodesNumber[j];
++      }
++
++      nodesByLevel[i] = nodesInThisLevel;
++      nodesRequired += nodesInThisLevel;
++    }
++   
++    if(nodesRequired > this->nodes.size()) {
++      surf_parse_error("There is not enough nodes to fit to the described topology. Please check your platform description (We need %d nodes, we only got %lu)", nodesRequired, this->nodes.size());
++      return;
++    }
++
++    // Nodes are totally ordered, by level and then by position, in this->nodes
++    int k = 0;
++    for (int i = 0 ; i < this->levels ; i++) {
++      for (int j = 0 ; j < nodesByLevel[i] ; j++) {
++        this->nodes[k]->level = i;
++        this->nodes[k]->position = j;
 +
++        if (i == 0) {
++          
++        }
++        else if (i == this->levels - 1) {
++          
++        }
++        else {
++          
++        }
++      }
++    }
 +}
 +
 +
++void AsClusterFatTree::addNodes(std::vector<int> const& id) {
++  for (int i = 0 ; i < id.size() ; i++) {
++    this->nodes.push_back(new FatTreeNode(id[i]));
++  }
++}
 +
 +void AsClusterFatTree::parse_specific_arguments(sg_platf_cluster_cbarg_t 
 +                                                cluster) {
 +  std::vector<string> parameters;
 +  std::vector<string> tmp;
 +  boost::split(parameters, cluster->topo_parameters, boost::is_any_of(";"));
-   
++ 
++
++  // TODO : we have to check for zeros and negative numbers, or it might crash
 +  if (parameters.size() != 4){
 +    surf_parse_error("Fat trees are defined by the levels number and 3 vectors" 
 +                     ", see the documentation for more informations");
 +    // Well, there's no doc, yet
 +  }
 +
 +  // The first parts of topo_parameters should be the levels number
-   this->levels = std::atoi(tmp[0].c_str());
++  this->levels = std::atoi(tmp[0].c_str()); // stoi() only in C++11...
 +
 +  // Then, a l-sized vector standing for the childs number by level
 +  boost::split(tmp, parameters[1], boost::is_any_of(","));
 +  if(tmp.size() != this->levels) {
 +    surf_parse_error("Fat trees are defined by the levels number and 3 vectors" 
 +                     ", see the documentation for more informations"); 
 +  }
 +  for(unsigned int i = 0 ; i < tmp.size() ; i++){
 +    this->lowerLevelNodesNumber.push_back(std::atoi(tmp[i].c_str())); 
 +  }
 +  
 +  // Then, a l-sized vector standing for the parents number by level
-    boost::split(tmp, parameters[2], boost::is_any_of(","));
++  boost::split(tmp, parameters[2], boost::is_any_of(","));
 +  if(tmp.size() != this->levels) {
 +    surf_parse_error("Fat trees are defined by the levels number and 3 vectors" 
 +                     ", see the documentation for more informations"); 
 +  }
 +  for(unsigned int i = 0 ; i < tmp.size() ; i++){
 +    this->upperLevelNodesNumber.push_back(std::atoi(tmp[i].c_str())); 
 +  }
 +  
 +  // Finally, a l-sized vector standing for the ports number with the lower level
 +  boost::split(tmp, parameters[3], boost::is_any_of(","));
 +  if(tmp.size() != this->levels) {
 +    surf_parse_error("Fat trees are defined by the levels number and 3 vectors" 
 +                     ", see the documentation for more informations"); 
 +    
 +  }
 +  for(unsigned int i = 0 ; i < tmp.size() ; i++){
 +    this->lowerLevelPortsNumber.push_back(std::atoi(tmp[i].c_str())); 
 +  }
 +}
++
++
++void AsClusterFatTree::generateDotFile(string filename) {
++  ofstream file;
++  /* Maybe should we get directly a char*, as open takes strings only beginning
++   * with c++11...
++   */
++  file.open(filename.c_str(), ios::out | ios::trunc); 
 +  
++  if(file.is_open()) {
++    /* TODO : Iterate through a map takes 10 chars with c++11, 100 with c++98.
++     * All I have to do is write it down...
++     */
++
++    // file << "graph AsClusterFatTree {\n";
++    // for (std::map<std::pair<int,int>, FatTreeLink*>::iterator link = this->links.begin() ; link != this->links.end() ; link++ ) {
++    //   for (int j = 0 ; j < link->ports ; j++) {
++    //   file << this->links[i]->source.id 
++    //        << " -- " this->links[i]->destination.id
++    //        << ";\n";
++    //   }
++    // }
++    // file << "}";
++    // file.close();
++  }
++  else {
++    std::cerr << "Unable to open file " << filename << std::endl;
++    return;
++  }
++}
++
++FatTreeNode::FatTreeNode(int id, int level, int position) : id(id),
++                                                            level(level),
++                                                            position(position){}
diff --cc src/surf/surf_routing_cluster_fat_tree.hpp
index d45cdbf3a8,0000000000..96ba5c97d0
mode 100644,000000..100644
--- a/src/surf/surf_routing_cluster_fat_tree.hpp
+++ b/src/surf/surf_routing_cluster_fat_tree.hpp
@@@ -1,42 -1,0 +1,72 @@@
 +/* Copyright (c) 2014. The SimGrid Team.
 + * All rights reserved.                                                     */
 +
 +/* This program is free software; you can redistribute it and/or modify it
 + * under the terms of the license (GNU LGPL) which comes with this package. */
 +
 +#include "surf_routing_cluster.hpp"
 +
 +#ifndef SURF_ROUTING_CLUSTER_FAT_TREE_HPP_
 +#define SURF_ROUTING_CLUSTER_FAT_TREE_HPP_
 +
 +
++/* The class AsClusterFatTree describes PGFT, as introduced by Eitan Zahavi
++ * in "D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations
++ * on Real Life Fat Trees" (2010). RLFT are PGFT with some restrictions to 
++ * address real world constraints, which are not currently enforced (but it 
++ * should certainly be checked for)
++ */
 +
- class FatTreeLink;
- class FatTreeNode;
++class FatTreeNode {
++public:
++  int id; // ID as given by the user
++  int level; // The 0th level represents the leafs of the PGFT
++  int position; // Position in the level
++  
++  /* We can see the sizes sum of the two following vectors as the device 
++   * ports number. If we use the notations used in Zahavi's paper, 
++   * children.size() = m_level and parents.size() = w_(level+1)
++   * 
++   */
++  std::vector<FatTreeNode*> children;  // m, apply from lvl 0 to levels - 1 
++  std::vector<FatTreeNode*> parents; // w, apply from lvl 1 to levels
++  FatTreeNode(int id, int level=-1, int position=-1);
++};
++
++class FatTreeLink {
++private:
++  unsigned int ports;
++  std::vector<NetworkLink> linksUp; // From source to destination
++  std::vector<NetworkLink> linksDown; // From destination to source
++  FatTreeNode source;
++  FatTreeNode destination;
++public:
++  FatTreeLink(int source, int destination, unsigned int ports = 0);
++  NetworkLink getLink(int number = 0) const;
++};
 +
 +class AsClusterFatTree : public AsCluster {
 +public:
 +  AsClusterFatTree();
-   virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst, sg_platf_route_cbarg_t into, double *latency);
-   virtual void create_links();
++  ~AsClusterFatTree();
++  virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst, sg_platf_route_cbarg_t into, double *latency) const;
++  virtual void create_links(sg_platf_cluster_cbarg_t cluster);
 +  void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster);
++  void addNodes(std::vector<int> const& id);
++  void generateDotFile(string filename = "fatTree.dot");
 +
 +protected:
 +  //description of a PGFT (TODO : better doc)
 +  unsigned int levels;
 +  std::vector<int> lowerLevelNodesNumber;
 +  std::vector<int> upperLevelNodesNumber;
 +  std::vector<int> lowerLevelPortsNumber;
 +  
-   std::vector<FatTreeNode> nodes;
++  std::vector<FatTreeNode*> nodes;
++  std::map<std::pair<int,int>, FatTreeLink*> links;
++  
 +};
 +
- class FatTreeLink {
- public:
- };
- class FatTreeNode {
-   int id;
-   std::string name;
- };
++
 +  
 +#endif