src/surf/surf_routing_cluster_fat_tree.hpp

   1 /* Copyright (c) 2014. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include "surf_routing_cluster.hpp"
   8
   9 #ifndef SURF_ROUTING_CLUSTER_FAT_TREE_HPP_
  10 #define SURF_ROUTING_CLUSTER_FAT_TREE_HPP_
  11
  12
  13 /* The class AsClusterFatTree describes PGFT, as introduced by Eitan Zahavi
  14  * in "D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations
  15  * on Real Life Fat Trees" (2010). RLFT are PGFT with some restrictions to
  16  * address real world constraints, which are not currently enforced (but it
  17  * should certainly be checked for)
  18  */
  19
  20 /* TODO : limiter link ? Loopback?
  21  *
  22  */
  23 class FatTreeNode;
  24 class FatTreeLink;
  25
  26 /* \class FatTreeNode
  27  * \brief A node in a fat tree
  28  */
  29 class FatTreeNode {
  30 public:
  31   /* \brief Unique ID which identifies every node
  32    */
  33   int id;
  34   /* \brief Level into the tree, with 0 being the leafs
  35    */
  36   unsigned int level;
  37   /* \brief Position into the level, starting from 0
  38    */
  39   unsigned int position;
  40   /* In order to link nodes between them, each one must be assigned a label,
  41    * consisting of l integers, l being the levels number of the tree. Each label
  42    * is unique in the level, and the way it is generated allows the construction
  43    * of a fat tree which fits the desired topology
  44    */
  45   std::vector<unsigned int> label;
  46
  47   /* Links to the lower level, where the position in the vector corresponds to
  48    * a port number.
  49    */
  50   std::vector<FatTreeLink*> children;
  51   /* Links to the upper level, where the position in the vector corresponds to
  52    * a port number.
  53    */
  54   std::vector<FatTreeLink*> parents;
  55
  56   NetworkLink* limiterLink;
  57   NetworkLink* loopback;
  58   FatTreeNode(sg_platf_cluster_cbarg_t cluster, int id, int level,
  59               int position);
  60 };
  61
  62 class FatTreeLink {
  63 public:
  64   FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode *source,
  65               FatTreeNode *destination);
  66   /* Links are dependant of the chosen network model, but must implement
  67    * NetworkLink
  68    */
  69   NetworkLink *upLink;
  70   NetworkLink *downLink;
  71   FatTreeNode *upNode;
  72   FatTreeNode *downNode;
  73 };
  74
  75 class AsClusterFatTree : public AsCluster {
  76 public:
  77   AsClusterFatTree();
  78   ~AsClusterFatTree();
  79   virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst,
  80                                   sg_platf_route_cbarg_t into,
  81                                   double *latency);
  82   // virtual void getRouteAndLatency(const int src, const int dst,
  83   //                                 std::vector<NetworkLink> *route,
  84   //                                 double *latency) const;
  85   virtual void create_links();
  86   void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster);
  87   void addProcessingNode(int id);
  88   void generateDotFile(const string& filename = "fatTree.dot") const;
  89
  90 private:
  91
  92   //description of a PGFT (TODO : better doc)
  93   unsigned int levels;
  94   std::vector<unsigned int> lowerLevelNodesNumber; // number of children by node
  95   std::vector<unsigned int> upperLevelNodesNumber; // number of parents by node
  96   std::vector<unsigned int> lowerLevelPortsNumber; // ports between each level l and l-1
  97
  98   std::map<int, FatTreeNode*> computeNodes;
  99   std::vector<FatTreeNode*> nodes;
 100   std::vector<FatTreeLink*> links;
 101   std::vector<unsigned int> nodesByLevel;
 102
 103   sg_platf_cluster_cbarg_t cluster;
 104
 105   void addLink(FatTreeNode *parent, unsigned int parentPort,
 106                FatTreeNode *child, unsigned int childPort);
 107   int getLevelPosition(const unsigned int level);
 108   void generateLabels();
 109   void generateSwitches();
 110   int connectNodeToParents(FatTreeNode *node);
 111   bool areRelated(FatTreeNode *parent, FatTreeNode *child);
 112   bool isInSubTree(FatTreeNode *root, FatTreeNode *node);
 113 };
 114 #endif