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 AS_t model_fatTree_cluster_create(void);
15 /* The class AsClusterFatTree describes PGFT, as introduced by Eitan Zahavi
16 * in "D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations
17 * on Real Life Fat Trees" (2010). RLFT are PGFT with some restrictions to
18 * address real world constraints, which are not currently enforced (but it
19 * should certainly be checked for)
22 /* TODO : limiter link ? Loopback?
32 unsigned int level; // The 0th level represents the leafs of the PGFT
33 unsigned int position; // Position in the level
34 std::vector<unsigned int> label;
35 /* We can see the sizes sum of the two following vectors as the device
36 * ports number. If we use the notations used in Zahavi's paper,
37 * children.size() = m_level and parents.size() = w_(level+1)
40 std::vector<FatTreeLink*> children; // m, apply from lvl 0 to levels - 1
41 std::vector<FatTreeLink*> parents; // w, apply from lvl 1 to levels
42 FatTreeNode(int id, int level=-1, int position=-1);
47 FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode *source,
48 FatTreeNode *destination);
49 // unsigned int ports;
50 /* Links are dependant of the chosen network model, but must implement
54 NetworkLink *downLink;
56 FatTreeNode *downNode;
60 class AsClusterFatTree : public AsCluster {
64 virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst,
65 sg_platf_route_cbarg_t into,
67 // virtual void getRouteAndLatency(const int src, const int dst,
68 // std::vector<NetworkLink> *route,
69 // double *latency) const;
70 virtual void create_links(sg_platf_cluster_cbarg_t cluster);
71 void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster);
72 void addComputeNodes(std::vector<int> const& id);
73 void generateDotFile(const string& filename = "fatTree.dot") const;
76 //description of a PGFT (TODO : better doc)
78 std::vector<unsigned int> lowerLevelNodesNumber; // number of children by node
79 std::vector<unsigned int> upperLevelNodesNumber; // number of parents by node
80 std::vector<unsigned int> lowerLevelPortsNumber; // ports between each level l and l-1
82 std::map<int, FatTreeNode*> nodes;
83 std::vector<FatTreeLink*> links;
84 std::vector<unsigned int> nodesByLevel;
86 void addLink(sg_platf_cluster_cbarg_t cluster,
87 FatTreeNode *parent, unsigned int parentPort,
88 FatTreeNode *child, unsigned int childPort);
89 int getLevelPosition(const unsigned int level);
90 void generateLabels();
91 void generateSwitches();
92 int connectNodeToParents(sg_platf_cluster_cbarg_t cluster, FatTreeNode *node);
93 bool areRelated(FatTreeNode *parent, FatTreeNode *child);
94 bool isInSubTree(FatTreeNode *root, FatTreeNode *node);