include/simgrid/kernel/routing/FatTreeZone.hpp

   1 /* Copyright (c) 2014-2023. 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 #ifndef SIMGRID_ROUTING_CLUSTER_FAT_TREE_HPP_
   7 #define SIMGRID_ROUTING_CLUSTER_FAT_TREE_HPP_
   8
   9 #include <simgrid/kernel/routing/ClusterZone.hpp>
  10
  11 namespace simgrid::kernel::routing {
  12
  13 class XBT_PRIVATE FatTreeLink;
  14
  15 /** @brief A node in a fat tree (@ref FatTreeZone).
  16  * A FatTreeNode can either be a switch or a processing node. Switches are
  17  * identified by a negative ID. This class is closely related to fat
  18  */
  19 class XBT_PRIVATE FatTreeNode {
  20 public:
  21   /** Unique ID which identifies every node. */
  22   int id;
  23   /* Level into the tree, with 0 being the leafs.
  24    */
  25   unsigned int level;
  26   /* @brief Position into the level, starting from 0.
  27    */
  28   unsigned int position;
  29   /** In order to link nodes between them, each one must be assigned a label,
  30    * consisting of l integers, l being the levels number of the tree. Each label
  31    * is unique in the level, and the way it is generated allows the construction
  32    * of a fat tree which fits the desired topology.
  33    */
  34   std::vector<unsigned int> label;
  35
  36   /** Links to the lower level, where the position in the vector corresponds to
  37    * a port number.
  38    */
  39   std::vector<std::shared_ptr<FatTreeLink>> children;
  40   /** Links to the upper level, where the position in the vector corresponds to
  41    * a port number.
  42    */
  43   std::vector<std::shared_ptr<FatTreeLink>> parents;
  44
  45   /** Virtual link standing for the node global capacity.
  46    */
  47   resource::StandardLinkImpl* limiter_link_;
  48   /** If present, communications from this node to this node will pass through it
  49    * instead of passing by an upper level switch.
  50    */
  51   resource::StandardLinkImpl* loopback_;
  52   FatTreeNode(int id, int level, int position, resource::StandardLinkImpl* limiter,
  53               resource::StandardLinkImpl* loopback)
  54       : id(id), level(level), position(position), limiter_link_(limiter), loopback_(loopback)
  55   {
  56   }
  57 };
  58
  59 /** @brief Link in a fat tree (@ref FatTreeZone).
  60  *
  61  * Represents a single, duplex link in a fat tree. This is necessary to have a tree.
  62  * It is equivalent to a physical link.
  63  */
  64 class FatTreeLink {
  65 public:
  66   FatTreeLink(FatTreeNode* src, FatTreeNode* dst, resource::StandardLinkImpl* linkup,
  67               resource::StandardLinkImpl* linkdown)
  68       : up_node_(dst), down_node_(src), up_link_(linkup), down_link_(linkdown)
  69   {
  70   }
  71   /** Upper end of the link */
  72   FatTreeNode* up_node_;
  73   /** Lower end of the link */
  74   FatTreeNode* down_node_;
  75   /** Link going up in the tree */
  76   resource::StandardLinkImpl* up_link_;
  77   /** Link going down in the tree */
  78   resource::StandardLinkImpl* down_link_;
  79 };
  80
  81 /** @ingroup ROUTING_API
  82  * @brief NetZone using a Fat-Tree topology
  83  *
  84  * Generate fat trees according to the topology asked for, according to:
  85  * Eitan Zahavi, D-Mod-K Routing Providing Non-Blocking Traffic for Shift
  86  * Permutations on Real Life Fat Trees (2010).
  87  *
  88  * RLFT are PGFT with some restrictions to address real world constraints,
  89  * which are not currently enforced.
  90  *
  91  * The exact topology is described in the mandatory topo_parameters
  92  * field, and follow the "h ; m_1, ..., m_h ; w_1, ..., w_h ; p_1, ..., p_h" format.
  93  * h stands for the switches levels number, i.e. the fat tree is of height h,
  94  * without the processing nodes. m_i stands for the number of lower level nodes
  95  * connected to a node in level i. w_i stands for the number of upper levels
  96  * nodes connected to a node in level i-1. p_i stands for the number of
  97  * parallel links connecting two nodes between level i and i - 1. Level h is
  98  * the topmost switch level, level 1 is the lowest switch level, and level 0
  99  * represents the processing nodes. The number of provided nodes must be exactly
 100  * the number of processing nodes required to fit the topology, which is the
 101  * product of the m_i's.
 102  *
 103  * Routing is made using a destination-mod-k scheme.
 104  */
 105 class XBT_PRIVATE FatTreeZone : public ClusterBase {
 106   /** @brief Generate the fat tree
 107    *
 108    * Once all processing nodes have been added, this will make sure the fat
 109    * tree is generated by calling generateLabels(), generateSwitches() and
 110    * then connection all nodes between them, using their label.
 111    */
 112   // description of a PGFT (TODO : better doc)
 113   unsigned long levels_ = 0;
 114   std::vector<unsigned int> num_children_per_node_; // number of children by node
 115   std::vector<unsigned int> num_parents_per_node_;  // number of parents by node
 116   std::vector<unsigned int> num_port_lower_level_;  // ports between each level l and l-1
 117
 118   std::map<unsigned long, std::shared_ptr<FatTreeNode>> compute_nodes_;
 119   std::vector<std::shared_ptr<FatTreeNode>> nodes_;
 120   std::vector<std::shared_ptr<FatTreeLink>> links_;
 121   std::vector<unsigned int> nodes_by_level_;
 122
 123   void add_link(FatTreeNode* parent, unsigned int parent_port, FatTreeNode* child, unsigned int child_port);
 124   int get_level_position(const unsigned int level);
 125   void generate_switches(const s4u::ClusterCallbacks& set_callbacks);
 126   void generate_labels();
 127   int connect_node_to_parents(FatTreeNode* node);
 128   bool are_related(FatTreeNode* parent, FatTreeNode* child) const;
 129   bool is_in_sub_tree(const FatTreeNode* root, const FatTreeNode* node) const;
 130
 131   void do_seal() override;
 132
 133 public:
 134   explicit FatTreeZone(const std::string& name) : ClusterBase(name){};
 135   FatTreeZone(const FatTreeZone&) = delete;
 136   FatTreeZone& operator=(const FatTreeZone&) = delete;
 137   void get_local_route(const NetPoint* src, const NetPoint* dst, Route* into, double* latency) override;
 138
 139   /**
 140    * @brief Parse the topology parameters from string format
 141    *
 142    * @param topo_parameters String with topology, e.g. "2;4,4;1,2;1,2"
 143    */
 144   static s4u::FatTreeParams parse_topo_parameters(const std::string& topo_parameters);
 145   /** @brief Checks topology parameters */
 146   static void check_topology(unsigned int n_levels, const std::vector<unsigned int>& down_links,
 147                              const std::vector<unsigned int>& up_links, const std::vector<unsigned int>& link_count);
 148   /** @brief Set FatTree topology */
 149   void set_topology(unsigned int n_levels, const std::vector<unsigned int>& down_links,
 150                     const std::vector<unsigned int>& up_links, const std::vector<unsigned int>& link_count);
 151   void add_processing_node(int id, resource::StandardLinkImpl* limiter, resource::StandardLinkImpl* loopback);
 152   /**
 153    * @brief Build upper levels (switches) in Fat-Tree
 154    *
 155    * Suppose that set_topology and add_processing_node have already been called
 156    */
 157   void build_upper_levels(const s4u::ClusterCallbacks& set_callbacks);
 158   void generate_dot_file(const std::string& filename = "fat_tree.dot") const;
 159 };
 160 } // namespace simgrid::kernel::routing
 161
 162 #endif