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?
30 unsigned int level; // The 0th level represents the leafs of the PGFT
31 unsigned int position; // Position in the level
32 std::vector<unsigned int> label;
33 /* We can see the sizes sum of the two following vectors as the device
34 * ports number. If we use the notations used in Zahavi's paper,
35 * children.size() = m_level and parents.size() = w_(level+1)
38 std::vector<FatTreeLink*> children; // m, apply from lvl 0 to levels - 1
39 std::vector<FatTreeLink*> parents; // w, apply from lvl 1 to levels
40 FatTreeNode(int id, int level=-1, int position=-1);
45 FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode *source,
46 FatTreeNode *destination);
47 // unsigned int ports;
48 /* Links are dependant of the chosen network model, but must implement
52 NetworkLink *downLink;
54 FatTreeNode *downNode;
58 class AsClusterFatTree : public AsCluster {
62 virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst,
63 sg_platf_route_cbarg_t into,
65 // virtual void getRouteAndLatency(const int src, const int dst,
66 // std::vector<NetworkLink> *route,
67 // double *latency) const;
68 virtual void create_links(sg_platf_cluster_cbarg_t cluster);
69 void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster);
70 void addComputeNode(int id);
71 void generateDotFile(const string& filename = "fatTree.dot") const;
74 //description of a PGFT (TODO : better doc)
76 std::vector<unsigned int> lowerLevelNodesNumber; // number of children by node
77 std::vector<unsigned int> upperLevelNodesNumber; // number of parents by node
78 std::vector<unsigned int> lowerLevelPortsNumber; // ports between each level l and l-1
80 std::map<int, FatTreeNode*> nodes;
81 std::vector<FatTreeLink*> links;
82 std::vector<unsigned int> nodesByLevel;
84 void addLink(sg_platf_cluster_cbarg_t cluster,
85 FatTreeNode *parent, unsigned int parentPort,
86 FatTreeNode *child, unsigned int childPort);
87 int getLevelPosition(const unsigned int level);
88 void generateLabels();
89 void generateSwitches();
90 int connectNodeToParents(sg_platf_cluster_cbarg_t cluster, FatTreeNode *node);
91 bool areRelated(FatTreeNode *parent, FatTreeNode *child);
92 bool isInSubTree(FatTreeNode *root, FatTreeNode *node);