1 /* Copyright (c) 2014. The SimGrid Team.
2 * All rights reserved. */
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. */
7 #include "surf_routing_cluster.hpp"
9 #ifndef SURF_ROUTING_CLUSTER_FAT_TREE_HPP_
10 #define SURF_ROUTING_CLUSTER_FAT_TREE_HPP_
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)
20 /* TODO : limiter link ? Loopback?
29 unsigned int level; // The 0th level represents the leafs of the PGFT
30 unsigned int position; // Position in the level
31 std::vector<int> label;
32 /* We can see the sizes sum of the two following vectors as the device
33 * ports number. If we use the notations used in Zahavi's paper,
34 * children.size() = m_level and parents.size() = w_(level+1)
37 std::vector<FatTreeLink*> children; // m, apply from lvl 0 to levels - 1
38 std::vector<FatTreeLink*> parents; // w, apply from lvl 1 to levels
39 FatTreeNode(int id, int level=-1, int position=-1);
44 FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode *source,
45 FatTreeNode *destination);
46 // unsigned int ports;
47 /* Links are dependant of the chosen network model, but must implement
50 NetworkLink* linkUp; // From source to destination
51 NetworkLink* linkDown; // From destination to source
52 /* As it is symetric, it might as well be first / second instead
53 * of source / destination
56 FatTreeNode *destination;
59 class AsClusterFatTree : public AsCluster {
63 virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst,
64 sg_platf_route_cbarg_t into,
66 // virtual void getRouteAndLatency(const int src, const int dst,
67 // std::vector<NetworkLink> *route,
68 // double *latency) const;
69 virtual void create_links(sg_platf_cluster_cbarg_t cluster);
70 void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster);
71 void addComputeNodes(std::vector<int> const& id);
72 void generateDotFile(const string& filename = "fatTree.dot") const;
75 //description of a PGFT (TODO : better doc)
77 std::vector<int> lowerLevelNodesNumber; // number of children by node
78 std::vector<int> upperLevelNodesNumber; // number of parents by node
79 std::vector<int> lowerLevelPortsNumber; // ports between each level l and l-1
81 std::vector<FatTreeNode*> nodes;
82 std::map<std::pair<int,int>, FatTreeLink*> links;
83 std::vector<unsigned int> nodesByLevel;
85 void addLink(sg_platf_cluster_cbarg_t cluster,
86 FatTreeNode *parent, unsigned int parentPort,
87 FatTreeNode *child, unsigned int childPort);
88 int getLevelPosition(const unsigned int level);
89 void generateLabels();
90 void generateSwitches();
91 int connectNodeToParents(sg_platf_cluster_cbarg_t cluster, FatTreeNode *node);
92 bool areRelated(FatTreeNode *parent, FatTreeNode *child);