X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/54d19a62bc6f609898dd623e8857cd1c6474e24f..703e8696289393e60554250c2ada4ea97ed89435:/src/surf/surf_routing_cluster_fat_tree.hpp diff --git a/src/surf/surf_routing_cluster_fat_tree.hpp b/src/surf/surf_routing_cluster_fat_tree.hpp index 96ba5c97d0..6d6adcf668 100644 --- a/src/surf/surf_routing_cluster_fat_tree.hpp +++ b/src/surf/surf_routing_cluster_fat_tree.hpp @@ -1,72 +1,168 @@ -/* Copyright (c) 2014. The SimGrid Team. +/* Copyright (c) 2014-2015. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#include "surf_routing_cluster.hpp" - #ifndef SURF_ROUTING_CLUSTER_FAT_TREE_HPP_ #define SURF_ROUTING_CLUSTER_FAT_TREE_HPP_ +#include +#include +#include + +#include + +#include "surf_routing_cluster.hpp" -/* The class AsClusterFatTree describes PGFT, as introduced by Eitan Zahavi +namespace simgrid { +namespace surf { + +/** \file surf_routing_cluster_fat_tree.cpp + * The class AsClusterFatTree describes PGFT, as introduced by Eitan Zahavi * in "D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations * on Real Life Fat Trees" (2010). RLFT are PGFT with some restrictions to - * address real world constraints, which are not currently enforced (but it - * should certainly be checked for) + * address real world constraints, which are not currently enforced. */ +class XBT_PRIVATE FatTreeNode; +class XBT_PRIVATE FatTreeLink; + +/** \brief A node in a fat tree. + * A FatTreeNode can either be a switch or a processing node. Switches are + * identified by a negative ID. This class is closely related to fat + */ class FatTreeNode { public: - int id; // ID as given by the user - int level; // The 0th level represents the leafs of the PGFT - int position; // Position in the level - - /* We can see the sizes sum of the two following vectors as the device - * ports number. If we use the notations used in Zahavi's paper, - * children.size() = m_level and parents.size() = w_(level+1) - * + /** Unique ID which identifies every node. */ + int id; + /* Level into the tree, with 0 being the leafs. + */ + unsigned int level; + /* \brief Position into the level, starting from 0. + */ + unsigned int position; + /** In order to link nodes between them, each one must be assigned a label, + * consisting of l integers, l being the levels number of the tree. Each label + * is unique in the level, and the way it is generated allows the construction + * of a fat tree which fits the desired topology. + */ + std::vector label; + + /** Links to the lower level, where the position in the vector corresponds to + * a port number. + */ + std::vector children; + /** Links to the upper level, where the position in the vector corresponds to + * a port number. + */ + std::vector parents; + + /** Virtual link standing for the node global capacity. + */ + Link* limiterLink; + /** If present, communications from this node to this node will pass through it + * instead of passing by an upper level switch. */ - std::vector children; // m, apply from lvl 0 to levels - 1 - std::vector parents; // w, apply from lvl 1 to levels - FatTreeNode(int id, int level=-1, int position=-1); + Link* loopback; + FatTreeNode(sg_platf_cluster_cbarg_t cluster, int id, int level, + int position); }; + + +/** \brief Link in a fat tree. + * + * Represents a single, duplex link in a fat tree. This is necessary to have a tree. + * It is equivalent to a physical link. + */ class FatTreeLink { -private: - unsigned int ports; - std::vector linksUp; // From source to destination - std::vector linksDown; // From destination to source - FatTreeNode source; - FatTreeNode destination; public: - FatTreeLink(int source, int destination, unsigned int ports = 0); - NetworkLink getLink(int number = 0) const; + FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode *source, + FatTreeNode *destination); + /** Link going up in the tree */ + Link *upLink; + /** Link going down in the tree */ + Link *downLink; + /** Upper end of the link */ + FatTreeNode *upNode; + /** Lower end of the link */ + FatTreeNode *downNode; }; -class AsClusterFatTree : public AsCluster { + +/** + * \class AsClusterFatTree + * + * \brief Fat tree representation and routing. + * + * Generate fat trees according to the topology asked for. Almost everything + * is based on the work of Eitan Zahavi in "D-Mod-K Routing Providing + * Non-Blocking Traffic for Shift Permutations on Real Life Fat Trees" (2010). + * + * The exact topology is described in the mandatory topo_parameters + * field, and follow the "h ; m_h, ..., m_1 ; w_h, ..., w_1 ; p_h, ..., p_1" format. + * h stands for the switches levels number, i.e. the fat tree is of height h, + * without the processing nodes. m_i stands for the number of lower level nodes + * connected to a node in level i. w_i stands for the number of upper levels + * nodes connected to a node in level i-1. p_i stands for the number of + * parallel links connecting two nodes between level i and i - 1. Level h is + * the topmost switch level, level 1 is the lowest switch level, and level 0 + * represents the processing nodes. The number of provided nodes must be exactly + * the number of processing nodes required to fit the topology, which is the + * product of the m_i's. + * + * Routing is made using a destination-mod-k scheme. + */ +class XBT_PRIVATE AsClusterFatTree : public AsCluster { public: AsClusterFatTree(); ~AsClusterFatTree(); - virtual void getRouteAndLatency(RoutingEdgePtr src, RoutingEdgePtr dst, sg_platf_route_cbarg_t into, double *latency) const; - virtual void create_links(sg_platf_cluster_cbarg_t cluster); - void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster); - void addNodes(std::vector const& id); - void generateDotFile(string filename = "fatTree.dot"); + virtual void getRouteAndLatency(NetCard *src, NetCard *dst, + sg_platf_route_cbarg_t into, + double *latency) override; + + /** \brief Generate the fat tree + * + * Once all processing nodes have been added, this will make sure the fat + * tree is generated by calling generateLabels(), generateSwitches() and + * then connection all nodes between them, using their label. + */ + virtual void create_links(); + /** \brief Read the parameters in topo_parameters field. + * + * It will also store the cluster for future use. + */ + void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) override; + void addProcessingNode(int id); + void generateDotFile(const std::string& filename = "fatTree.dot") const; -protected: +private: + //description of a PGFT (TODO : better doc) unsigned int levels; - std::vector lowerLevelNodesNumber; - std::vector upperLevelNodesNumber; - std::vector lowerLevelPortsNumber; + std::vector lowerLevelNodesNumber; // number of children by node + std::vector upperLevelNodesNumber; // number of parents by node + std::vector lowerLevelPortsNumber; // ports between each level l and l-1 + std::map computeNodes; std::vector nodes; - std::map, FatTreeLink*> links; - + std::vector links; + std::vector nodesByLevel; + + sg_platf_cluster_cbarg_t cluster; + + void addLink(FatTreeNode *parent, unsigned int parentPort, + FatTreeNode *child, unsigned int childPort); + int getLevelPosition(const unsigned int level); + void generateLabels(); + void generateSwitches(); + int connectNodeToParents(FatTreeNode *node); + bool areRelated(FatTreeNode *parent, FatTreeNode *child); + bool isInSubTree(FatTreeNode *root, FatTreeNode *node); }; +} +} - #endif