From a18117755285a374ec3d5830309c924f2830e3ba Mon Sep 17 00:00:00 2001 From: Martin Quinson Date: Tue, 13 Dec 2016 09:57:00 +0100 Subject: [PATCH] clang-format changes related to the previous commit --- src/kernel/routing/ClusterZone.cpp | 40 +- src/kernel/routing/ClusterZone.hpp | 18 +- src/kernel/routing/DijkstraZone.cpp | 144 +++---- src/kernel/routing/DijkstraZone.hpp | 39 +- src/kernel/routing/DragonflyZone.cpp | 303 +++++++------- src/kernel/routing/DragonflyZone.hpp | 93 ++--- src/kernel/routing/EmptyZone.cpp | 11 +- src/kernel/routing/EmptyZone.hpp | 5 +- src/kernel/routing/FatTreeZone.cpp | 321 +++++++-------- src/kernel/routing/FatTreeZone.hpp | 49 ++- src/kernel/routing/FloydZone.cpp | 60 +-- src/kernel/routing/FloydZone.hpp | 13 +- src/kernel/routing/FullZone.cpp | 37 +- src/kernel/routing/FullZone.hpp | 9 +- src/kernel/routing/NetZoneImpl.cpp | 582 +++++++++++++-------------- src/kernel/routing/NetZoneImpl.hpp | 7 +- src/kernel/routing/RoutedZone.cpp | 89 ++-- src/kernel/routing/RoutedZone.hpp | 11 +- src/kernel/routing/TorusZone.cpp | 374 ++++++++--------- src/kernel/routing/TorusZone.hpp | 24 +- src/kernel/routing/VivaldiZone.cpp | 2 +- src/kernel/routing/VivaldiZone.hpp | 2 +- src/surf/sg_platf.cpp | 8 +- src/surf/surf_routing.hpp | 2 +- 24 files changed, 1135 insertions(+), 1108 deletions(-) diff --git a/src/kernel/routing/ClusterZone.cpp b/src/kernel/routing/ClusterZone.cpp index 520ac663e7..dc72ef325a 100644 --- a/src/kernel/routing/ClusterZone.cpp +++ b/src/kernel/routing/ClusterZone.cpp @@ -25,9 +25,9 @@ void AsCluster::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t xbt_assert(!privateLinks_.empty(), "Cluster routing: no links attached to the source node - did you use host_link tag?"); - if (! src->isRouter()) { // No specific link for router + if (!src->isRouter()) { // No specific link for router - if((src->id() == dst->id()) && hasLoopback_ ){ + if ((src->id() == dst->id()) && hasLoopback_) { std::pair info = privateLinks_.at(src->id() * linkCountPerNode_); route->link_list->push_back(info.first); if (lat) @@ -35,7 +35,7 @@ void AsCluster::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t return; } - if (hasLimiter_){ // limiter for sender + if (hasLimiter_) { // limiter for sender std::pair info = privateLinks_.at(src->id() * linkCountPerNode_ + (hasLoopback_ ? 1 : 0)); route->link_list->push_back(info.first); } @@ -47,7 +47,6 @@ void AsCluster::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t if (lat) *lat += info.first->latency(); } - } if (backbone_) { @@ -56,7 +55,7 @@ void AsCluster::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t *lat += backbone_->latency(); } - if (! dst->isRouter()) { // No specific link for router + if (!dst->isRouter()) { // No specific link for router std::pair info = privateLinks_.at(dst->id() * linkCountPerNode_ + hasLoopback_ + hasLimiter_); if (info.second) { // link down @@ -64,28 +63,29 @@ void AsCluster::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t if (lat) *lat += info.second->latency(); } - if (hasLimiter_){ // limiter for receiver - info = privateLinks_.at(dst->id() * linkCountPerNode_ + hasLoopback_); - route->link_list->push_back(info.first); + if (hasLimiter_) { // limiter for receiver + info = privateLinks_.at(dst->id() * linkCountPerNode_ + hasLoopback_); + route->link_list->push_back(info.first); } } } void AsCluster::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges) { - xbt_assert(router_,"Malformed cluster. This may be because your platform file is a hypergraph while it must be a graph."); + xbt_assert(router_, + "Malformed cluster. This may be because your platform file is a hypergraph while it must be a graph."); /* create the router */ xbt_node_t routerNode = new_xbt_graph_node(graph, router_->cname(), nodes); xbt_node_t backboneNode = nullptr; - if(backbone_) { + if (backbone_) { backboneNode = new_xbt_graph_node(graph, backbone_->getName(), nodes); new_xbt_graph_edge(graph, routerNode, backboneNode, edges); } - for (auto src: vertices_){ - if (! src->isRouter()) { + for (auto src : vertices_) { + if (!src->isRouter()) { xbt_node_t previous = new_xbt_graph_node(graph, src->cname(), nodes); std::pair info = privateLinks_.at(src->id()); @@ -115,20 +115,21 @@ void AsCluster::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges) } } -void AsCluster::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int , int position){ +void AsCluster::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int, int position) +{ char* link_id = bprintf("%s_link_%d", cluster->id, id); s_sg_platf_link_cbarg_t link; memset(&link, 0, sizeof(link)); - link.id = link_id; + link.id = link_id; link.bandwidth = cluster->bw; - link.latency = cluster->lat; - link.policy = cluster->sharing_policy; + link.latency = cluster->lat; + link.policy = cluster->sharing_policy; sg_platf_new_link(&link); Link *linkUp, *linkDown; if (link.policy == SURF_LINK_FULLDUPLEX) { - char *tmp_link = bprintf("%s_UP", link_id); + char* tmp_link = bprintf("%s_UP", link_id); linkUp = Link::byName(tmp_link); xbt_free(tmp_link); tmp_link = bprintf("%s_DOWN", link_id); @@ -141,5 +142,6 @@ void AsCluster::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, privateLinks_.insert({position, {linkUp, linkDown}}); xbt_free(link_id); } - -}}} +} +} +} diff --git a/src/kernel/routing/ClusterZone.hpp b/src/kernel/routing/ClusterZone.hpp index 8f08d195ef..0096ae11a6 100644 --- a/src/kernel/routing/ClusterZone.hpp +++ b/src/kernel/routing/ClusterZone.hpp @@ -14,7 +14,7 @@ namespace simgrid { namespace kernel { namespace routing { -class XBT_PRIVATE AsCluster: public AsImpl { +class XBT_PRIVATE AsCluster : public AsImpl { public: explicit AsCluster(As* father, const char* name); @@ -28,15 +28,15 @@ public: /* The pair is {linkUp, linkDown} */ std::unordered_map> privateLinks_; - Link* backbone_ = nullptr; - void *loopback_ = nullptr; - NetCard *router_ = nullptr; - bool hasLimiter_ = false; - bool hasLoopback_ = false; + Link* backbone_ = nullptr; + void* loopback_ = nullptr; + NetCard* router_ = nullptr; + bool hasLimiter_ = false; + bool hasLoopback_ = false; unsigned int linkCountPerNode_ = 1; /* may be 1 (if only a private link), 2 or 3 (if limiter and loopback) */ - }; - -}}} // namespace +} +} +} // namespace #endif /* SIMGRID_ROUTING_CLUSTER_HPP_ */ diff --git a/src/kernel/routing/DijkstraZone.cpp b/src/kernel/routing/DijkstraZone.cpp index 10a5cc93b6..e7d12b5161 100644 --- a/src/kernel/routing/DijkstraZone.cpp +++ b/src/kernel/routing/DijkstraZone.cpp @@ -12,24 +12,24 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_dijkstra, surf, "Routing part of surf /* Free functions */ -static void route_cache_elem_free(void *e) +static void route_cache_elem_free(void* e) { - route_cache_element_t elm = (route_cache_element_t) e; + route_cache_element_t elm = (route_cache_element_t)e; if (elm) { xbt_free(elm->pred_arr); xbt_free(elm); } } -static void graph_node_map_elem_free(void *e) +static void graph_node_map_elem_free(void* e) { - graph_node_map_element_t elm = (graph_node_map_element_t) e; + graph_node_map_element_t elm = (graph_node_map_element_t)e; xbt_free(elm); } -static void graph_edge_data_free(void *e) // FIXME: useless code duplication +static void graph_edge_data_free(void* e) // FIXME: useless code duplication { - sg_platf_route_cbarg_t e_route = (sg_platf_route_cbarg_t) e; + sg_platf_route_cbarg_t e_route = (sg_platf_route_cbarg_t)e; if (e_route) { delete e_route->link_list; xbt_free(e_route); @@ -47,18 +47,18 @@ void AsDijkstra::seal() unsigned int cursor2, cursor; /* Create the topology graph */ - if(!routeGraph_) + if (!routeGraph_) routeGraph_ = xbt_graph_new_graph(1, nullptr); - if(!graphNodeMap_) + if (!graphNodeMap_) graphNodeMap_ = xbt_dict_new_homogeneous(&graph_node_map_elem_free); /* Add the loopback if needed */ if (surf_network_model->loopback_ && hierarchy_ == RoutingMode::base) { - xbt_dynar_foreach(xbt_graph_get_nodes(routeGraph_), cursor, node) { + xbt_dynar_foreach (xbt_graph_get_nodes(routeGraph_), cursor, node) { xbt_edge_t edge = nullptr; bool found = false; - xbt_dynar_foreach(xbt_graph_node_get_outedges(node), cursor2, edge) { + xbt_dynar_foreach (xbt_graph_node_get_outedges(node), cursor2, edge) { if (xbt_graph_edge_get_target(edge) == node) { found = true; break; @@ -67,7 +67,7 @@ void AsDijkstra::seal() if (!found) { sg_platf_route_cbarg_t e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1); - e_route->link_list = new std::vector(); + e_route->link_list = new std::vector(); e_route->link_list->push_back(surf_network_model->loopback_); xbt_graph_new_edge(routeGraph_, node, node, e_route); } @@ -77,33 +77,33 @@ void AsDijkstra::seal() /* initialize graph indexes in nodes after graph has been built */ xbt_dynar_t nodes = xbt_graph_get_nodes(routeGraph_); - xbt_dynar_foreach(nodes, cursor, node) { - graph_node_data_t data = (graph_node_data_t) xbt_graph_node_get_data(node); - data->graph_id = cursor; + xbt_dynar_foreach (nodes, cursor, node) { + graph_node_data_t data = (graph_node_data_t)xbt_graph_node_get_data(node); + data->graph_id = cursor; } } xbt_node_t AsDijkstra::routeGraphNewNode(int id, int graph_id) { - xbt_node_t node = nullptr; - graph_node_data_t data = nullptr; + xbt_node_t node = nullptr; + graph_node_data_t data = nullptr; graph_node_map_element_t elm = nullptr; - data = xbt_new0(struct graph_node_data, 1); - data->id = id; + data = xbt_new0(struct graph_node_data, 1); + data->id = id; data->graph_id = graph_id; - node = xbt_graph_new_node(routeGraph_, data); + node = xbt_graph_new_node(routeGraph_, data); - elm = xbt_new0(struct graph_node_map_element, 1); + elm = xbt_new0(struct graph_node_map_element, 1); elm->node = node; - xbt_dict_set_ext(graphNodeMap_, (char *) (&id), sizeof(int), (xbt_dictelm_t) elm, nullptr); + xbt_dict_set_ext(graphNodeMap_, (char*)(&id), sizeof(int), (xbt_dictelm_t)elm, nullptr); return node; } graph_node_map_element_t AsDijkstra::nodeMapSearch(int id) { - return (graph_node_map_element_t)xbt_dict_get_or_null_ext(graphNodeMap_, (char *) (&id), sizeof(int)); + return (graph_node_map_element_t)xbt_dict_get_or_null_ext(graphNodeMap_, (char*)(&id), sizeof(int)); } /* Parsing */ @@ -146,49 +146,48 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ int src_id = src->id(); int dst_id = dst->id(); - int *pred_arr = nullptr; - int size = 0; + int* pred_arr = nullptr; + int size = 0; xbt_dynar_t nodes = xbt_graph_get_nodes(routeGraph_); /* Use the graph_node id mapping set to quickly find the nodes */ graph_node_map_element_t src_elm = nodeMapSearch(src_id); graph_node_map_element_t dst_elm = nodeMapSearch(dst_id); - int src_node_id = ((graph_node_data_t) xbt_graph_node_get_data(src_elm->node))->graph_id; - int dst_node_id = ((graph_node_data_t) xbt_graph_node_get_data(dst_elm->node))->graph_id; + int src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id; + int dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id; /* if the src and dst are the same */ if (src_node_id == dst_node_id) { xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t); xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t); - xbt_edge_t edge = xbt_graph_get_edge(routeGraph_, node_s_v, node_e_v); + xbt_edge_t edge = xbt_graph_get_edge(routeGraph_, node_s_v, node_e_v); if (edge == nullptr) THROWF(arg_error, 0, "No route from '%s' to '%s'", src->name().c_str(), dst->name().c_str()); sg_platf_route_cbarg_t e_route = (sg_platf_route_cbarg_t)xbt_graph_edge_get_data(edge); - for (auto link: *e_route->link_list) { + for (auto link : *e_route->link_list) { route->link_list->insert(route->link_list->begin(), link); if (lat) *lat += static_cast(link)->latency(); } - } route_cache_element_t elm = nullptr; - if (routeCache_) { /* cache mode */ - elm = (route_cache_element_t) xbt_dict_get_or_null_ext(routeCache_, (char *) (&src_id), sizeof(int)); + if (routeCache_) { /* cache mode */ + elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routeCache_, (char*)(&src_id), sizeof(int)); } - if (elm) { /* cached mode and cache hit */ + if (elm) { /* cached mode and cache hit */ pred_arr = elm->pred_arr; - } else { /* not cached mode, or cache miss */ + } else { /* not cached mode, or cache miss */ - int nr_nodes = xbt_dynar_length(nodes); - double * cost_arr = xbt_new0(double, nr_nodes); /* link cost from src to other hosts */ - pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */ + int nr_nodes = xbt_dynar_length(nodes); + double* cost_arr = xbt_new0(double, nr_nodes); /* link cost from src to other hosts */ + pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */ xbt_heap_t pqueue = xbt_heap_new(nr_nodes, xbt_free_f); /* initialize */ @@ -202,31 +201,30 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ pred_arr[i] = 0; /* initialize priority queue */ - int *nodeid = xbt_new0(int, 1); - *nodeid = i; + int* nodeid = xbt_new0(int, 1); + *nodeid = i; xbt_heap_push(pqueue, nodeid, cost_arr[i]); - } /* apply dijkstra using the indexes from the graph's node array */ while (xbt_heap_size(pqueue) > 0) { - int *v_id = (int *) xbt_heap_pop(pqueue); + int* v_id = (int*)xbt_heap_pop(pqueue); xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t); - xbt_edge_t edge = nullptr; + xbt_edge_t edge = nullptr; unsigned int cursor; - xbt_dynar_foreach(xbt_graph_node_get_outedges(v_node), cursor, edge) { - xbt_node_t u_node = xbt_graph_edge_get_target(edge); - graph_node_data_t data = (graph_node_data_t) xbt_graph_node_get_data(u_node); - int u_id = data->graph_id; - sg_platf_route_cbarg_t tmp_e_route = (sg_platf_route_cbarg_t) xbt_graph_edge_get_data(edge); - int cost_v_u = tmp_e_route->link_list->size(); /* count of links, old model assume 1 */ + xbt_dynar_foreach (xbt_graph_node_get_outedges(v_node), cursor, edge) { + xbt_node_t u_node = xbt_graph_edge_get_target(edge); + graph_node_data_t data = (graph_node_data_t)xbt_graph_node_get_data(u_node); + int u_id = data->graph_id; + sg_platf_route_cbarg_t tmp_e_route = (sg_platf_route_cbarg_t)xbt_graph_edge_get_data(edge); + int cost_v_u = tmp_e_route->link_list->size(); /* count of links, old model assume 1 */ if (cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) { pred_arr[u_id] = *v_id; cost_arr[u_id] = cost_v_u + cost_arr[*v_id]; - int *nodeid = xbt_new0(int, 1); - *nodeid = u_id; + int* nodeid = xbt_new0(int, 1); + *nodeid = u_id; xbt_heap_push(pqueue, nodeid, cost_arr[u_id]); } } @@ -245,8 +243,8 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ for (int v = dst_node_id; v != src_node_id; v = pred_arr[v]) { xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t); - xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t); - xbt_edge_t edge = xbt_graph_get_edge(routeGraph_, node_pred_v, node_v); + xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t); + xbt_edge_t edge = xbt_graph_get_edge(routeGraph_, node_pred_v, node_v); if (edge == nullptr) THROWF(arg_error, 0, "No route from '%s' to '%s'", src->name().c_str(), dst->name().c_str()); @@ -254,15 +252,15 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ prev_gw_src = gw_src; sg_platf_route_cbarg_t e_route = (sg_platf_route_cbarg_t)xbt_graph_edge_get_data(edge); - gw_src = e_route->gw_src; - gw_dst = e_route->gw_dst; + gw_src = e_route->gw_src; + gw_dst = e_route->gw_dst; if (v == dst_node_id) first_gw = gw_dst; if (hierarchy_ == RoutingMode::recursive && v != dst_node_id && strcmp(gw_dst->name().c_str(), prev_gw_src->name().c_str())) { - std::vector *e_route_as_to_as = new std::vector(); + std::vector* e_route_as_to_as = new std::vector(); getGlobalRoute(gw_dst_net_elm, prev_gw_src_net_elm, e_route_as_to_as, nullptr); auto pos = route->link_list->begin(); @@ -274,7 +272,7 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ } } - for (auto link: *e_route->link_list) { + for (auto link : *e_route->link_list) { route->link_list->insert(route->link_list->begin(), link); if (lat) *lat += static_cast(link)->latency(); @@ -289,10 +287,10 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ if (routeCache_ && elm == nullptr) { /* add to predecessor list of the current src-host to cache */ - elm = xbt_new0(struct route_cache_element, 1); + elm = xbt_new0(struct route_cache_element, 1); elm->pred_arr = pred_arr; - elm->size = size; - xbt_dict_set_ext(routeCache_, (char *) (&src_id), sizeof(int), (xbt_dictelm_t) elm, nullptr); + elm->size = size; + xbt_dict_set_ext(routeCache_, (char*)(&src_id), sizeof(int), (xbt_dictelm_t)elm, nullptr); } if (!routeCache_) @@ -301,7 +299,7 @@ void AsDijkstra::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_ AsDijkstra::~AsDijkstra() { - xbt_graph_free_graph(routeGraph_, &xbt_free_f, &graph_edge_data_free, &xbt_free_f); + xbt_graph_free_graph(routeGraph_, &xbt_free_f, &graph_edge_data_free, &xbt_free_f); xbt_dict_free(&graphNodeMap_); xbt_dict_free(&routeCache_); } @@ -316,20 +314,21 @@ AsDijkstra::AsDijkstra(As* father, const char* name, bool cached) : AsRoutedGrap void AsDijkstra::addRoute(sg_platf_route_cbarg_t route) { - NetCard *src = route->src; - NetCard *dst = route->dst; + NetCard* src = route->src; + NetCard* dst = route->dst; const char* srcName = src->name().c_str(); const char* dstName = dst->name().c_str(); addRouteCheckParams(route); /* Create the topology graph */ - if(!routeGraph_) + if (!routeGraph_) routeGraph_ = xbt_graph_new_graph(1, nullptr); - if(!graphNodeMap_) + if (!graphNodeMap_) graphNodeMap_ = xbt_dict_new_homogeneous(&graph_node_map_elem_free); - /* we don't check whether the route already exist, because the algorithm may find another path through some other nodes */ + /* we don't check whether the route already exist, because the algorithm may find another path through some other + * nodes */ /* Add the route to the base */ sg_platf_route_cbarg_t e_route = newExtendedRoute(hierarchy_, route, 1); @@ -337,29 +336,30 @@ void AsDijkstra::addRoute(sg_platf_route_cbarg_t route) // Symmetrical YES if (route->symmetrical == true) { - if(!route->gw_dst && !route->gw_src) + if (!route->gw_dst && !route->gw_src) XBT_DEBUG("Load Route from \"%s\" to \"%s\"", dstName, srcName); else XBT_DEBUG("Load ASroute from %s@%s to %s@%s", dstName, route->gw_dst->name().c_str(), srcName, route->gw_src->name().c_str()); - xbt_dynar_t nodes = xbt_graph_get_nodes(routeGraph_); + xbt_dynar_t nodes = xbt_graph_get_nodes(routeGraph_); xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src->id(), xbt_node_t); xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst->id(), xbt_node_t); - xbt_edge_t edge = xbt_graph_get_edge(routeGraph_, node_e_v, node_s_v); + xbt_edge_t edge = xbt_graph_get_edge(routeGraph_, node_e_v, node_s_v); if (edge) THROWF(arg_error, 0, "Route from %s@%s to %s@%s already exists", dstName, route->gw_dst->name().c_str(), srcName, route->gw_src->name().c_str()); if (route->gw_dst && route->gw_src) { - NetCard *gw_tmp = route->gw_src; - route->gw_src = route->gw_dst; - route->gw_dst = gw_tmp; + NetCard* gw_tmp = route->gw_src; + route->gw_src = route->gw_dst; + route->gw_dst = gw_tmp; } sg_platf_route_cbarg_t link_route_back = newExtendedRoute(hierarchy_, route, 0); newRoute(dst->id(), src->id(), link_route_back); } } - -}}} // namespace +} +} +} // namespace diff --git a/src/kernel/routing/DijkstraZone.hpp b/src/kernel/routing/DijkstraZone.hpp index 34c2d0e40e..51541ce9f7 100644 --- a/src/kernel/routing/DijkstraZone.hpp +++ b/src/kernel/routing/DijkstraZone.hpp @@ -10,7 +10,7 @@ typedef struct graph_node_data { int id; - int graph_id; /* used for caching internal graph id's */ + int graph_id; /* used for caching internal graph id's */ } s_graph_node_data_t, *graph_node_data_t; typedef struct graph_node_map_element { @@ -18,7 +18,7 @@ typedef struct graph_node_map_element { } s_graph_node_map_element_t, *graph_node_map_element_t; typedef struct route_cache_element { - int *pred_arr; + int* pred_arr; int size; } s_route_cache_element_t, *route_cache_element_t; @@ -40,26 +40,27 @@ public: xbt_node_t routeGraphNewNode(int id, int graph_id); graph_node_map_element_t nodeMapSearch(int id); void newRoute(int src_id, int dst_id, sg_platf_route_cbarg_t e_route); - /** - * For each vertex (node) already in the graph, - * make sure it also has a loopback link; this loopback - * can potentially already be in the graph, and in that - * case nothing will be done. - * - * If no loopback is specified for a node, we will use - * the loopback that is provided by the routing platform. - * - * After this function returns, any node in the graph - * will have a loopback attached to it. - */ + /** + * For each vertex (node) already in the graph, + * make sure it also has a loopback link; this loopback + * can potentially already be in the graph, and in that + * case nothing will be done. + * + * If no loopback is specified for a node, we will use + * the loopback that is provided by the routing platform. + * + * After this function returns, any node in the graph + * will have a loopback attached to it. + */ void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t route, double* lat) override; void addRoute(sg_platf_route_cbarg_t route) override; - xbt_graph_t routeGraph_ = nullptr; /* xbt_graph */ - xbt_dict_t graphNodeMap_ = nullptr; /* map */ - xbt_dict_t routeCache_ = nullptr; /* use in cache mode */ + xbt_graph_t routeGraph_ = nullptr; /* xbt_graph */ + xbt_dict_t graphNodeMap_ = nullptr; /* map */ + xbt_dict_t routeCache_ = nullptr; /* use in cache mode */ }; - -}}} // namespaces +} +} +} // namespaces #endif /* SURF_ROUTING_DIJKSTRA_HPP_ */ diff --git a/src/kernel/routing/DragonflyZone.cpp b/src/kernel/routing/DragonflyZone.cpp index 1ce8275dd8..146e00781f 100644 --- a/src/kernel/routing/DragonflyZone.cpp +++ b/src/kernel/routing/DragonflyZone.cpp @@ -7,8 +7,8 @@ #include "src/kernel/routing/NetCard.hpp" #include "src/surf/network_interface.hpp" -#include #include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_cluster_dragonfly, surf_route_cluster, "Dragonfly Routing part of surf"); @@ -20,78 +20,80 @@ AsClusterDragonfly::AsClusterDragonfly(As* father, const char* name) : AsCluster { } -AsClusterDragonfly::~AsClusterDragonfly() { - if(this->routers_ != nullptr){ - for (unsigned int i=0; inumGroups_*this->numChassisPerGroup_*this->numBladesPerChassis_;i++) - delete(routers_[i]); +AsClusterDragonfly::~AsClusterDragonfly() +{ + if (this->routers_ != nullptr) { + for (unsigned int i = 0; i < this->numGroups_ * this->numChassisPerGroup_ * this->numBladesPerChassis_; i++) + delete (routers_[i]); xbt_free(routers_); } } -unsigned int *AsClusterDragonfly::rankId_to_coords(int rankId) +unsigned int* AsClusterDragonfly::rankId_to_coords(int rankId) { - //coords : group, chassis, blade, node - unsigned int *coords = (unsigned int *) malloc(4 * sizeof(unsigned int)); - coords[0] = rankId/ (numChassisPerGroup_*numBladesPerChassis_*numNodesPerBlade_); - rankId=rankId%(numChassisPerGroup_*numBladesPerChassis_*numNodesPerBlade_); - coords[1] = rankId/ (numBladesPerChassis_*numNodesPerBlade_); - rankId=rankId%(numBladesPerChassis_*numNodesPerBlade_); - coords[2] = rankId/ numNodesPerBlade_; - coords[3]=rankId%numNodesPerBlade_; + // coords : group, chassis, blade, node + unsigned int* coords = (unsigned int*)malloc(4 * sizeof(unsigned int)); + coords[0] = rankId / (numChassisPerGroup_ * numBladesPerChassis_ * numNodesPerBlade_); + rankId = rankId % (numChassisPerGroup_ * numBladesPerChassis_ * numNodesPerBlade_); + coords[1] = rankId / (numBladesPerChassis_ * numNodesPerBlade_); + rankId = rankId % (numBladesPerChassis_ * numNodesPerBlade_); + coords[2] = rankId / numNodesPerBlade_; + coords[3] = rankId % numNodesPerBlade_; return coords; } -void AsClusterDragonfly::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) { +void AsClusterDragonfly::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) +{ std::vector parameters; std::vector tmp; boost::split(parameters, cluster->topo_parameters, boost::is_any_of(";")); // TODO : we have to check for zeros and negative numbers, or it might crash - if (parameters.size() != 4){ + if (parameters.size() != 4) { surf_parse_error( "Dragonfly are defined by the number of groups, chassis per groups, blades per chassis, nodes per blade"); } // Blue network : number of groups, number of links between each group boost::split(tmp, parameters[0], boost::is_any_of(",")); - if(tmp.size() != 2) { + if (tmp.size() != 2) { surf_parse_error("Dragonfly topologies are defined by 3 levels with 2 elements each, and one with one element"); } - this->numGroups_=xbt_str_parse_int(tmp[0].c_str(), "Invalid number of groups: %s"); - this->numLinksBlue_=xbt_str_parse_int(tmp[1].c_str(), "Invalid number of links for the blue level: %s"); + this->numGroups_ = xbt_str_parse_int(tmp[0].c_str(), "Invalid number of groups: %s"); + this->numLinksBlue_ = xbt_str_parse_int(tmp[1].c_str(), "Invalid number of links for the blue level: %s"); // Black network : number of chassis/group, number of links between each router on the black network boost::split(tmp, parameters[1], boost::is_any_of(",")); - if(tmp.size() != 2) { + if (tmp.size() != 2) { surf_parse_error("Dragonfly topologies are defined by 3 levels with 2 elements each, and one with one element"); } - this->numChassisPerGroup_=xbt_str_parse_int(tmp[0].c_str(), "Invalid number of groups: %s"); - this->numLinksBlack_=xbt_str_parse_int(tmp[1].c_str(), "Invalid number of links for the black level: %s"); + this->numChassisPerGroup_ = xbt_str_parse_int(tmp[0].c_str(), "Invalid number of groups: %s"); + this->numLinksBlack_ = xbt_str_parse_int(tmp[1].c_str(), "Invalid number of links for the black level: %s"); - - // Green network : number of blades/chassis, number of links between each router on the green network + // Green network : number of blades/chassis, number of links between each router on the green network boost::split(tmp, parameters[2], boost::is_any_of(",")); - if(tmp.size() != 2) { + if (tmp.size() != 2) { surf_parse_error("Dragonfly topologies are defined by 3 levels with 2 elements each, and one with one element"); } - this->numBladesPerChassis_=xbt_str_parse_int(tmp[0].c_str(), "Invalid number of groups: %s"); - this->numLinksGreen_=xbt_str_parse_int(tmp[1].c_str(), "Invalid number of links for the green level: %s"); - + this->numBladesPerChassis_ = xbt_str_parse_int(tmp[0].c_str(), "Invalid number of groups: %s"); + this->numLinksGreen_ = xbt_str_parse_int(tmp[1].c_str(), "Invalid number of links for the green level: %s"); // The last part of topo_parameters should be the number of nodes per blade - this->numNodesPerBlade_ = xbt_str_parse_int(parameters[3].c_str(), "Last parameter is not the amount of nodes per blade: %s"); + this->numNodesPerBlade_ = + xbt_str_parse_int(parameters[3].c_str(), "Last parameter is not the amount of nodes per blade: %s"); this->cluster_ = cluster; } /* * Generate the cluster once every node is created */ -void AsClusterDragonfly::seal(){ - if(this->numNodesPerBlade_ == 0) { +void AsClusterDragonfly::seal() +{ + if (this->numNodesPerBlade_ == 0) { return; } @@ -99,146 +101,153 @@ void AsClusterDragonfly::seal(){ this->generateLinks(); } -DragonflyRouter::DragonflyRouter(int group, int chassis, int blade):group_(group),chassis_(chassis),blade_(blade){ } +DragonflyRouter::DragonflyRouter(int group, int chassis, int blade) : group_(group), chassis_(chassis), blade_(blade) +{ +} -DragonflyRouter::~DragonflyRouter(){ - if(this->myNodes_!=nullptr) +DragonflyRouter::~DragonflyRouter() +{ + if (this->myNodes_ != nullptr) xbt_free(myNodes_); - if(this->greenLinks_!=nullptr) + if (this->greenLinks_ != nullptr) xbt_free(greenLinks_); - if(this->blackLinks_!=nullptr) + if (this->blackLinks_ != nullptr) xbt_free(blackLinks_); - if(this->blueLinks_!=nullptr) + if (this->blueLinks_ != nullptr) xbt_free(blueLinks_); } - -void AsClusterDragonfly::generateRouters() { - this->routers_=static_cast(xbt_malloc0(this->numGroups_*this->numChassisPerGroup_*this->numBladesPerChassis_*sizeof(DragonflyRouter*))); - - for(unsigned int i=0;inumGroups_;i++){ - for(unsigned int j=0;jnumChassisPerGroup_;j++){ - for(unsigned int k=0;knumBladesPerChassis_;k++){ - DragonflyRouter* router = new DragonflyRouter(i,j,k); - this->routers_[i*this->numChassisPerGroup_*this->numBladesPerChassis_+j*this->numBladesPerChassis_+k]=router; +void AsClusterDragonfly::generateRouters() +{ + this->routers_ = static_cast(xbt_malloc0(this->numGroups_ * this->numChassisPerGroup_ * + this->numBladesPerChassis_ * sizeof(DragonflyRouter*))); + + for (unsigned int i = 0; i < this->numGroups_; i++) { + for (unsigned int j = 0; j < this->numChassisPerGroup_; j++) { + for (unsigned int k = 0; k < this->numBladesPerChassis_; k++) { + DragonflyRouter* router = new DragonflyRouter(i, j, k); + this->routers_[i * this->numChassisPerGroup_ * this->numBladesPerChassis_ + j * this->numBladesPerChassis_ + + k] = router; } } } } -void AsClusterDragonfly::createLink(char* id, int numlinks, Link** linkup, Link** linkdown){ - *linkup=nullptr; - *linkdown=nullptr; +void AsClusterDragonfly::createLink(char* id, int numlinks, Link** linkup, Link** linkdown) +{ + *linkup = nullptr; + *linkdown = nullptr; s_sg_platf_link_cbarg_t linkTemplate; memset(&linkTemplate, 0, sizeof(linkTemplate)); linkTemplate.bandwidth = this->cluster_->bw * numlinks; - linkTemplate.latency = this->cluster_->lat; - linkTemplate.policy = this->cluster_->sharing_policy; // sthg to do with that ? - linkTemplate.id = id; + linkTemplate.latency = this->cluster_->lat; + linkTemplate.policy = this->cluster_->sharing_policy; // sthg to do with that ? + linkTemplate.id = id; sg_platf_new_link(&linkTemplate); XBT_DEBUG("Generating link %s", id); Link* link; std::string tmpID; if (this->cluster_->sharing_policy == SURF_LINK_FULLDUPLEX) { - tmpID = std::string(linkTemplate.id) + "_UP"; - link = Link::byName(tmpID.c_str()); - *linkup = link; // check link? - tmpID = std::string(linkTemplate.id) + "_DOWN"; - link = Link::byName(tmpID.c_str()); + tmpID = std::string(linkTemplate.id) + "_UP"; + link = Link::byName(tmpID.c_str()); + *linkup = link; // check link? + tmpID = std::string(linkTemplate.id) + "_DOWN"; + link = Link::byName(tmpID.c_str()); *linkdown = link; // check link ? - } - else { - link = Link::byName(linkTemplate.id); - *linkup = link; + } else { + link = Link::byName(linkTemplate.id); + *linkup = link; *linkdown = link; } free((void*)linkTemplate.id); } - -void AsClusterDragonfly::generateLinks() { +void AsClusterDragonfly::generateLinks() +{ static int uniqueId = 0; - char* id = nullptr; + char* id = nullptr; Link* linkup; - Link *linkdown; + Link* linkdown; - unsigned int numRouters = this->numGroups_*this->numChassisPerGroup_*this->numBladesPerChassis_; + unsigned int numRouters = this->numGroups_ * this->numChassisPerGroup_ * this->numBladesPerChassis_; if (this->cluster_->sharing_policy == SURF_LINK_FULLDUPLEX) - numLinksperLink_=2; - - //Links from routers to their local nodes. - for(unsigned int i=0; irouters_[i]->myNodes_=static_cast(xbt_malloc0(numLinksperLink_*this->numNodesPerBlade_*sizeof(Link*))); - this->routers_[i]->greenLinks_=static_cast(xbt_malloc0(this->numBladesPerChassis_*sizeof(Link*))); - this->routers_[i]->blackLinks_=static_cast(xbt_malloc0(this->numChassisPerGroup_*sizeof(Link*))); - - for(unsigned int j=0; j< numLinksperLink_*this->numNodesPerBlade_; j+=numLinksperLink_){ - id = bprintf("local_link_from_router_%d_to_node_%d_%d", i, j/numLinksperLink_, uniqueId); + numLinksperLink_ = 2; + + // Links from routers to their local nodes. + for (unsigned int i = 0; i < numRouters; i++) { + // allocate structures + this->routers_[i]->myNodes_ = + static_cast(xbt_malloc0(numLinksperLink_ * this->numNodesPerBlade_ * sizeof(Link*))); + this->routers_[i]->greenLinks_ = static_cast(xbt_malloc0(this->numBladesPerChassis_ * sizeof(Link*))); + this->routers_[i]->blackLinks_ = static_cast(xbt_malloc0(this->numChassisPerGroup_ * sizeof(Link*))); + + for (unsigned int j = 0; j < numLinksperLink_ * this->numNodesPerBlade_; j += numLinksperLink_) { + id = bprintf("local_link_from_router_%d_to_node_%d_%d", i, j / numLinksperLink_, uniqueId); this->createLink(id, 1, &linkup, &linkdown); if (this->cluster_->sharing_policy == SURF_LINK_FULLDUPLEX) { - this->routers_[i]->myNodes_[j] = linkup; - this->routers_[i]->myNodes_[j+1] = linkdown; - } - else { + this->routers_[i]->myNodes_[j] = linkup; + this->routers_[i]->myNodes_[j + 1] = linkdown; + } else { this->routers_[i]->myNodes_[j] = linkup; } uniqueId++; } } - //Green links from routers to same chassis routers - alltoall - for(unsigned int i=0; inumGroups_*this->numChassisPerGroup_;i++){ - for(unsigned int j=0; jnumBladesPerChassis_;j++){ - for(unsigned int k=j+1;knumBladesPerChassis_;k++){ - id = bprintf("green_link_in_chassis_%d_between_routers_%d_and_%d_%d", i%numChassisPerGroup_, j, k, uniqueId); + // Green links from routers to same chassis routers - alltoall + for (unsigned int i = 0; i < this->numGroups_ * this->numChassisPerGroup_; i++) { + for (unsigned int j = 0; j < this->numBladesPerChassis_; j++) { + for (unsigned int k = j + 1; k < this->numBladesPerChassis_; k++) { + id = bprintf("green_link_in_chassis_%d_between_routers_%d_and_%d_%d", i % numChassisPerGroup_, j, k, uniqueId); this->createLink(id, this->numLinksGreen_, &linkup, &linkdown); - this->routers_[i*numBladesPerChassis_+j]->greenLinks_[k] = linkup; - this->routers_[i*numBladesPerChassis_+k]->greenLinks_[j] = linkdown; + this->routers_[i * numBladesPerChassis_ + j]->greenLinks_[k] = linkup; + this->routers_[i * numBladesPerChassis_ + k]->greenLinks_[j] = linkdown; uniqueId++; } } } - //Black links from routers to same group routers - alltoall - for(unsigned int i=0; inumGroups_;i++){ - for(unsigned int j=0; jnumChassisPerGroup_;j++){ - for(unsigned int k=j+1;knumChassisPerGroup_;k++){ - for(unsigned int l=0;lnumBladesPerChassis_;l++){ - id = bprintf("black_link_in_group_%d_between_chassis_%d_and_%d_blade_%d_%d", i, j, k,l, uniqueId); - this->createLink(id, this->numLinksBlack_,&linkup, &linkdown); - this->routers_[i*numBladesPerChassis_*numChassisPerGroup_+j*numBladesPerChassis_+l]->blackLinks_[k] = linkup; - this->routers_[i*numBladesPerChassis_*numChassisPerGroup_+k*numBladesPerChassis_+l]->blackLinks_[j] = linkdown; + // Black links from routers to same group routers - alltoall + for (unsigned int i = 0; i < this->numGroups_; i++) { + for (unsigned int j = 0; j < this->numChassisPerGroup_; j++) { + for (unsigned int k = j + 1; k < this->numChassisPerGroup_; k++) { + for (unsigned int l = 0; l < this->numBladesPerChassis_; l++) { + id = bprintf("black_link_in_group_%d_between_chassis_%d_and_%d_blade_%d_%d", i, j, k, l, uniqueId); + this->createLink(id, this->numLinksBlack_, &linkup, &linkdown); + this->routers_[i * numBladesPerChassis_ * numChassisPerGroup_ + j * numBladesPerChassis_ + l] + ->blackLinks_[k] = linkup; + this->routers_[i * numBladesPerChassis_ * numChassisPerGroup_ + k * numBladesPerChassis_ + l] + ->blackLinks_[j] = linkdown; uniqueId++; } } } } - - //Blue links between groups - Not all routers involved, only one per group is linked to others. Let's say router n of each group is linked to group n. -//FIXME: in reality blue links may be attached to several different routers - for(unsigned int i=0; inumGroups_;i++){ - for(unsigned int j=i+1; jnumGroups_;j++){ - unsigned int routernumi=i*numBladesPerChassis_*numChassisPerGroup_+j; - unsigned int routernumj=j*numBladesPerChassis_*numChassisPerGroup_+i; - this->routers_[routernumi]->blueLinks_=static_cast(xbt_malloc0(sizeof(Link*))); - this->routers_[routernumj]->blueLinks_=static_cast(xbt_malloc0(sizeof(Link*))); - id = bprintf("blue_link_between_group_%d_and_%d_routers_%d_and_%d_%d", i, j, routernumi,routernumj, uniqueId); - this->createLink(id, this->numLinksBlue_, &linkup, &linkdown); - this->routers_[routernumi]->blueLinks_[0] = linkup; - this->routers_[routernumj]->blueLinks_[0] = linkdown; - uniqueId++; + // Blue links between groups - Not all routers involved, only one per group is linked to others. Let's say router n of + // each group is linked to group n. + // FIXME: in reality blue links may be attached to several different routers + for (unsigned int i = 0; i < this->numGroups_; i++) { + for (unsigned int j = i + 1; j < this->numGroups_; j++) { + unsigned int routernumi = i * numBladesPerChassis_ * numChassisPerGroup_ + j; + unsigned int routernumj = j * numBladesPerChassis_ * numChassisPerGroup_ + i; + this->routers_[routernumi]->blueLinks_ = static_cast(xbt_malloc0(sizeof(Link*))); + this->routers_[routernumj]->blueLinks_ = static_cast(xbt_malloc0(sizeof(Link*))); + id = bprintf("blue_link_between_group_%d_and_%d_routers_%d_and_%d_%d", i, j, routernumi, routernumj, uniqueId); + this->createLink(id, this->numLinksBlue_, &linkup, &linkdown); + this->routers_[routernumi]->blueLinks_[0] = linkup; + this->routers_[routernumj]->blueLinks_[0] = linkdown; + uniqueId++; } } } void AsClusterDragonfly::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t route, double* latency) { - //Minimal routing version. + // Minimal routing version. // TODO : non-minimal random one, and adaptive ? if (dst->isRouter() || src->isRouter()) @@ -256,82 +265,88 @@ void AsClusterDragonfly::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_rout return; } - unsigned int *myCoords = rankId_to_coords(src->id()); - unsigned int *targetCoords = rankId_to_coords(dst->id()); + unsigned int* myCoords = rankId_to_coords(src->id()); + unsigned int* targetCoords = rankId_to_coords(dst->id()); XBT_DEBUG("src : %u group, %u chassis, %u blade, %u node", myCoords[0], myCoords[1], myCoords[2], myCoords[3]); - XBT_DEBUG("dst : %u group, %u chassis, %u blade, %u node", targetCoords[0], targetCoords[1], targetCoords[2], targetCoords[3]); + XBT_DEBUG("dst : %u group, %u chassis, %u blade, %u node", targetCoords[0], targetCoords[1], targetCoords[2], + targetCoords[3]); - DragonflyRouter* myRouter = routers_[myCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+myCoords[1] * numBladesPerChassis_+myCoords[2]]; - DragonflyRouter* targetRouter = routers_[targetCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+targetCoords[1] *numBladesPerChassis_ +targetCoords[2]]; - DragonflyRouter* currentRouter=myRouter; + DragonflyRouter* myRouter = routers_[myCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + + myCoords[1] * numBladesPerChassis_ + myCoords[2]]; + DragonflyRouter* targetRouter = routers_[targetCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + + targetCoords[1] * numBladesPerChassis_ + targetCoords[2]]; + DragonflyRouter* currentRouter = myRouter; - //node->router local link - route->link_list->push_back(myRouter->myNodes_[myCoords[3]*numLinksperLink_]); + // node->router local link + route->link_list->push_back(myRouter->myNodes_[myCoords[3] * numLinksperLink_]); if (latency) *latency += myRouter->myNodes_[myCoords[3] * numLinksperLink_]->latency(); - if (hasLimiter_) { // limiter for sender + if (hasLimiter_) { // limiter for sender std::pair info = privateLinks_.at(src->id() * linkCountPerNode_ + hasLoopback_); route->link_list->push_back(info.first); } - if(targetRouter!=myRouter){ + if (targetRouter != myRouter) { - //are we on a different group ? - if(targetRouter->group_ != currentRouter->group_){ - //go to the router of our group connected to this one. - if(currentRouter->blade_!=targetCoords[0]){ - //go to the nth router in our chassis + // are we on a different group ? + if (targetRouter->group_ != currentRouter->group_) { + // go to the router of our group connected to this one. + if (currentRouter->blade_ != targetCoords[0]) { + // go to the nth router in our chassis route->link_list->push_back(currentRouter->greenLinks_[targetCoords[0]]); if (latency) *latency += currentRouter->greenLinks_[targetCoords[0]]->latency(); - currentRouter=routers_[myCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+myCoords[1] * numBladesPerChassis_+targetCoords[0]]; + currentRouter = routers_[myCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + + myCoords[1] * numBladesPerChassis_ + targetCoords[0]]; } - if(currentRouter->chassis_!=0){ - //go to the first chassis of our group + if (currentRouter->chassis_ != 0) { + // go to the first chassis of our group route->link_list->push_back(currentRouter->blackLinks_[0]); if (latency) *latency += currentRouter->blackLinks_[0]->latency(); - currentRouter=routers_[myCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+targetCoords[0]]; + currentRouter = routers_[myCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + targetCoords[0]]; } - //go to destination group - the only optical hop + // go to destination group - the only optical hop route->link_list->push_back(currentRouter->blueLinks_[0]); if (latency) *latency += currentRouter->blueLinks_[0]->latency(); - currentRouter=routers_[targetCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+myCoords[0]]; + currentRouter = routers_[targetCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + myCoords[0]]; } - - //same group, but same blade ? - if(targetRouter->blade_ != currentRouter->blade_){ + // same group, but same blade ? + if (targetRouter->blade_ != currentRouter->blade_) { route->link_list->push_back(currentRouter->greenLinks_[targetCoords[2]]); if (latency) *latency += currentRouter->greenLinks_[targetCoords[2]]->latency(); - currentRouter=routers_[targetCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+targetCoords[2]]; + currentRouter = routers_[targetCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + targetCoords[2]]; } - //same blade, but same chassis ? - if(targetRouter->chassis_ != currentRouter->chassis_){ + // same blade, but same chassis ? + if (targetRouter->chassis_ != currentRouter->chassis_) { route->link_list->push_back(currentRouter->blackLinks_[targetCoords[1]]); if (latency) *latency += currentRouter->blackLinks_[targetCoords[1]]->latency(); - currentRouter=routers_[targetCoords[0]*(numChassisPerGroup_*numBladesPerChassis_)+targetCoords[1]*numBladesPerChassis_+targetCoords[2]]; + currentRouter = routers_[targetCoords[0] * (numChassisPerGroup_ * numBladesPerChassis_) + + targetCoords[1] * numBladesPerChassis_ + targetCoords[2]]; } } - if (hasLimiter_) { // limiter for receiver + if (hasLimiter_) { // limiter for receiver std::pair info = privateLinks_.at(dst->id() * linkCountPerNode_ + hasLoopback_); route->link_list->push_back(info.first); } - //router->node local link - route->link_list->push_back(targetRouter->myNodes_[targetCoords[3]*numLinksperLink_+numLinksperLink_-1]); + // router->node local link + route->link_list->push_back(targetRouter->myNodes_[targetCoords[3] * numLinksperLink_ + numLinksperLink_ - 1]); if (latency) *latency += targetRouter->myNodes_[targetCoords[3] * numLinksperLink_ + numLinksperLink_ - 1]->latency(); xbt_free(myCoords); xbt_free(targetCoords); } -}}} // namespace +} +} +} // namespace diff --git a/src/kernel/routing/DragonflyZone.hpp b/src/kernel/routing/DragonflyZone.hpp index 622945553f..767d0fc16d 100644 --- a/src/kernel/routing/DragonflyZone.hpp +++ b/src/kernel/routing/DragonflyZone.hpp @@ -12,22 +12,20 @@ namespace simgrid { namespace kernel { namespace routing { - class XBT_PRIVATE DragonflyRouter { - public: - unsigned int group_; - unsigned int chassis_; - unsigned int blade_; - surf::Link** blueLinks_=nullptr; - surf::Link** blackLinks_=nullptr; - surf::Link** greenLinks_=nullptr; - surf::Link** myNodes_=nullptr; - DragonflyRouter(int i, int j, int k); - ~DragonflyRouter(); +public: + unsigned int group_; + unsigned int chassis_; + unsigned int blade_; + surf::Link** blueLinks_ = nullptr; + surf::Link** blackLinks_ = nullptr; + surf::Link** greenLinks_ = nullptr; + surf::Link** myNodes_ = nullptr; + DragonflyRouter(int i, int j, int k); + ~DragonflyRouter(); }; - -/** +/** * \class AsClusterDragonfly * * \brief Dragonfly representation and routing. @@ -36,55 +34,58 @@ class XBT_PRIVATE DragonflyRouter { * Cray Cascade: a Scalable HPC System based on a Dragonfly Network * Greg Faanes, Abdulla Bataineh, Duncan Roweth, Tom Court, Edwin Froese, * Bob Alverson, Tim Johnson, Joe Kopnick, Mike Higgins and James Reinhard - * Cray Inc, Chippewa Falls, Wisconsin, USA + * Cray Inc, Chippewa Falls, Wisconsin, USA * or http://www.cray.com/sites/default/files/resources/CrayXCNetwork.pdf * - * We use the same denomination for the different levels, with a Green, + * We use the same denomination for the different levels, with a Green, * Black and Blue color scheme for the three different levels. - * + * * Description of the topology has to be given with a string of type : * "3,4;4,3;5,1;2" * * Last part : "2" : 2 nodes per blade * Third part : "5,1" : five blades/routers per chassis, with one link between each (green network) - * Second part : "4,3" = four chassis per group, with three links between each nth router of each chassis (black network) - * First part : "3,4" = three electrical groups, linked in an alltoall + * Second part : "4,3" = four chassis per group, with three links between each nth router of each chassis (black + * network) + * First part : "3,4" = three electrical groups, linked in an alltoall * pattern by 4 links each (blue network) * * LIMITATIONS (for now): * - Routing is only static and uses minimal routes. - * - When n links are used between two routers/groups, we consider only one link with n times the bandwidth (needs to be validated on a real system) + * - When n links are used between two routers/groups, we consider only one link with n times the bandwidth (needs to + * be validated on a real system) * - All links have the same characteristics for now - * - Blue links are all attached to routers in the chassis n°0. This limits + * - Blue links are all attached to routers in the chassis n°0. This limits * the number of groups possible to the number of blades in a chassis. This * is also not realistic, as blue level can use more links than a single * Aries can handle, thus it should use several routers. */ -class XBT_PRIVATE AsClusterDragonfly - : public AsCluster { - public: - explicit AsClusterDragonfly(As* father, const char* name); - ~AsClusterDragonfly() override; -// void create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position) override; - void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency) override; - void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) override; - void seal() override; - void generateRouters(); - void generateLinks(); - void createLink(char* id, int numlinks, Link** linkup, Link** linkdown); - unsigned int * rankId_to_coords(int rankId); - private: - sg_platf_cluster_cbarg_t cluster_; - unsigned int numNodesPerBlade_ = 0; - unsigned int numBladesPerChassis_ = 0; - unsigned int numChassisPerGroup_ = 0; - unsigned int numGroups_ = 0; - unsigned int numLinksGreen_ = 0; - unsigned int numLinksBlack_ = 0; - unsigned int numLinksBlue_ = 0; - unsigned int numLinksperLink_ = 1; //fullduplex -> 2, only for local link - DragonflyRouter** routers_=nullptr; - }; +class XBT_PRIVATE AsClusterDragonfly : public AsCluster { +public: + explicit AsClusterDragonfly(As* father, const char* name); + ~AsClusterDragonfly() override; + // void create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position) override; + void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency) override; + void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) override; + void seal() override; + void generateRouters(); + void generateLinks(); + void createLink(char* id, int numlinks, Link** linkup, Link** linkdown); + unsigned int* rankId_to_coords(int rankId); -}}} +private: + sg_platf_cluster_cbarg_t cluster_; + unsigned int numNodesPerBlade_ = 0; + unsigned int numBladesPerChassis_ = 0; + unsigned int numChassisPerGroup_ = 0; + unsigned int numGroups_ = 0; + unsigned int numLinksGreen_ = 0; + unsigned int numLinksBlack_ = 0; + unsigned int numLinksBlue_ = 0; + unsigned int numLinksperLink_ = 1; // fullduplex -> 2, only for local link + DragonflyRouter** routers_ = nullptr; +}; +} +} +} #endif diff --git a/src/kernel/routing/EmptyZone.cpp b/src/kernel/routing/EmptyZone.cpp index 50b9ac3ae3..95d7b19951 100644 --- a/src/kernel/routing/EmptyZone.cpp +++ b/src/kernel/routing/EmptyZone.cpp @@ -16,16 +16,19 @@ namespace kernel { namespace routing { AsNone::AsNone(As* father, const char* name) : AsImpl(father, name) -{} +{ +} AsNone::~AsNone() = default; void AsNone::getLocalRoute(NetCard* /*src*/, NetCard* /*dst*/, sg_platf_route_cbarg_t /*res*/, double* /*lat*/) -{} +{ +} void AsNone::getGraph(xbt_graph_t /*graph*/, xbt_dict_t /*nodes*/, xbt_dict_t /*edges*/) { XBT_ERROR("No routing no graph"); } - -}}} +} +} +} diff --git a/src/kernel/routing/EmptyZone.hpp b/src/kernel/routing/EmptyZone.hpp index c7e5ec38e2..80d1d1f06b 100644 --- a/src/kernel/routing/EmptyZone.hpp +++ b/src/kernel/routing/EmptyZone.hpp @@ -21,7 +21,8 @@ public: void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency) override; void getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges) override; }; - -}}} // namespace +} +} +} // namespace #endif /* SURF_ROUTING_NONE_HPP_ */ diff --git a/src/kernel/routing/FatTreeZone.cpp b/src/kernel/routing/FatTreeZone.cpp index ef040f97fb..97c57d3bcc 100644 --- a/src/kernel/routing/FatTreeZone.cpp +++ b/src/kernel/routing/FatTreeZone.cpp @@ -12,8 +12,8 @@ #include "xbt/lib.h" -#include #include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_fat_tree, surf, "Routing for fat trees"); @@ -26,29 +26,31 @@ AsClusterFatTree::AsClusterFatTree(As* father, const char* name) : AsCluster(fat XBT_DEBUG("Creating a new fat tree."); } -AsClusterFatTree::~AsClusterFatTree() { - for (unsigned int i = 0 ; i < this->nodes_.size() ; i++) { +AsClusterFatTree::~AsClusterFatTree() +{ + for (unsigned int i = 0; i < this->nodes_.size(); i++) { delete this->nodes_[i]; } - for (unsigned int i = 0 ; i < this->links_.size() ; i++) { + for (unsigned int i = 0; i < this->links_.size(); i++) { delete this->links_[i]; } } -bool AsClusterFatTree::isInSubTree(FatTreeNode *root, FatTreeNode *node) { - XBT_DEBUG("Is %d(%u,%u) in the sub tree of %d(%u,%u) ?", node->id, - node->level, node->position, root->id, root->level, root->position); +bool AsClusterFatTree::isInSubTree(FatTreeNode* root, FatTreeNode* node) +{ + XBT_DEBUG("Is %d(%u,%u) in the sub tree of %d(%u,%u) ?", node->id, node->level, node->position, root->id, root->level, + root->position); if (root->level <= node->level) { return false; } - for (unsigned int i = 0 ; i < node->level ; i++) { - if(root->label[i] != node->label[i]) { + for (unsigned int i = 0; i < node->level; i++) { + if (root->label[i] != node->label[i]) { return false; } } - - for (unsigned int i = root->level ; i < this->levels_ ; i++) { - if(root->label[i] != node->label[i]) { + + for (unsigned int i = root->level; i < this->levels_; i++) { + if (root->label[i] != node->label[i]) { return false; } } @@ -93,7 +95,7 @@ void AsClusterFatTree::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_ d /= this->upperLevelNodesNumber_[i]; int k = this->upperLevelNodesNumber_[currentNode->level]; - d = d % k; + d = d % k; into->link_list->push_back(currentNode->parents[d]->upLink); if (latency) @@ -104,13 +106,12 @@ void AsClusterFatTree::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_ currentNode = currentNode->parents[d]->upNode; } - XBT_DEBUG("%d(%u,%u) is in the sub tree of %d(%u,%u).", destination->id, - destination->level, destination->position, currentNode->id, - currentNode->level, currentNode->position); + XBT_DEBUG("%d(%u,%u) is in the sub tree of %d(%u,%u).", destination->id, destination->level, destination->position, + currentNode->id, currentNode->level, currentNode->position); // Down part while (currentNode != destination) { - for(unsigned int i = 0 ; i < currentNode->children.size() ; i++) { + for (unsigned int i = 0; i < currentNode->children.size(); i++) { if (i % this->lowerLevelNodesNumber_[currentNode->level - 1] == destination->label[currentNode->level - 1]) { into->link_list->push_back(currentNode->children[i]->downLink); if (latency) @@ -118,9 +119,8 @@ void AsClusterFatTree::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_ currentNode = currentNode->children[i]->downNode; if (this->hasLimiter_) into->link_list->push_back(currentNode->limiterLink); - XBT_DEBUG("%d(%u,%u) is accessible through %d(%u,%u)", destination->id, - destination->level, destination->position, currentNode->id, - currentNode->level, currentNode->position); + XBT_DEBUG("%d(%u,%u) is accessible through %d(%u,%u)", destination->id, destination->level, + destination->position, currentNode->id, currentNode->level, currentNode->position); } } } @@ -129,75 +129,68 @@ void AsClusterFatTree::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_ /* This function makes the assumption that parse_specific_arguments() and * addNodes() have already been called */ -void AsClusterFatTree::seal(){ - if(this->levels_ == 0) { +void AsClusterFatTree::seal() +{ + if (this->levels_ == 0) { return; } this->generateSwitches(); - - if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { + if (XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { std::stringstream msgBuffer; msgBuffer << "We are creating a fat tree of " << this->levels_ << " levels " << "with " << this->nodesByLevel_[0] << " processing nodes"; - for (unsigned int i = 1 ; i <= this->levels_ ; i++) { + for (unsigned int i = 1; i <= this->levels_; i++) { msgBuffer << ", " << this->nodesByLevel_[i] << " switches at level " << i; } XBT_DEBUG("%s", msgBuffer.str().c_str()); msgBuffer.str(""); msgBuffer << "Nodes are : "; - for (unsigned int i = 0 ; i < this->nodes_.size() ; i++) { - msgBuffer << this->nodes_[i]->id << "(" << this->nodes_[i]->level << "," - << this->nodes_[i]->position << ") "; + for (unsigned int i = 0; i < this->nodes_.size(); i++) { + msgBuffer << this->nodes_[i]->id << "(" << this->nodes_[i]->level << "," << this->nodes_[i]->position << ") "; } XBT_DEBUG("%s", msgBuffer.str().c_str()); } - this->generateLabels(); unsigned int k = 0; // Nodes are totally ordered, by level and then by position, in this->nodes - for (unsigned int i = 0 ; i < this->levels_ ; i++) { - for (unsigned int j = 0 ; j < this->nodesByLevel_[i] ; j++) { - this->connectNodeToParents(this->nodes_[k]); - k++; + for (unsigned int i = 0; i < this->levels_; i++) { + for (unsigned int j = 0; j < this->nodesByLevel_[i]; j++) { + this->connectNodeToParents(this->nodes_[k]); + k++; } } - - if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { + + if (XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { std::stringstream msgBuffer; msgBuffer << "Links are : "; - for (unsigned int i = 0 ; i < this->links_.size() ; i++) { - msgBuffer << "(" << this->links_[i]->upNode->id << "," - << this->links_[i]->downNode->id << ") "; + for (unsigned int i = 0; i < this->links_.size(); i++) { + msgBuffer << "(" << this->links_[i]->upNode->id << "," << this->links_[i]->downNode->id << ") "; } XBT_DEBUG("%s", msgBuffer.str().c_str()); } - - } -int AsClusterFatTree::connectNodeToParents(FatTreeNode *node) { +int AsClusterFatTree::connectNodeToParents(FatTreeNode* node) +{ std::vector::iterator currentParentNode = this->nodes_.begin(); - int connectionsNumber = 0; - const int level = node->level; - XBT_DEBUG("We are connecting node %d(%u,%u) to his parents.", - node->id, node->level, node->position); + int connectionsNumber = 0; + const int level = node->level; + XBT_DEBUG("We are connecting node %d(%u,%u) to his parents.", node->id, node->level, node->position); currentParentNode += this->getLevelPosition(level + 1); - for (unsigned int i = 0 ; i < this->nodesByLevel_[level + 1] ; i++ ) { - if(this->areRelated(*currentParentNode, node)) { + for (unsigned int i = 0; i < this->nodesByLevel_[level + 1]; i++) { + if (this->areRelated(*currentParentNode, node)) { XBT_DEBUG("%d(%u,%u) and %d(%u,%u) are related," - " with %u links between them.", node->id, - node->level, node->position, (*currentParentNode)->id, - (*currentParentNode)->level, (*currentParentNode)->position, this->lowerLevelPortsNumber_[level]); - for (unsigned int j = 0 ; j < this->lowerLevelPortsNumber_[level] ; j++) { - this->addLink(*currentParentNode, node->label[level] + - j * this->lowerLevelNodesNumber_[level], node, - (*currentParentNode)->label[level] + - j * this->upperLevelNodesNumber_[level]); + " with %u links between them.", + node->id, node->level, node->position, (*currentParentNode)->id, (*currentParentNode)->level, + (*currentParentNode)->position, this->lowerLevelPortsNumber_[level]); + for (unsigned int j = 0; j < this->lowerLevelPortsNumber_[level]; j++) { + this->addLink(*currentParentNode, node->label[level] + j * this->lowerLevelNodesNumber_[level], node, + (*currentParentNode)->label[level] + j * this->upperLevelNodesNumber_[level]); } connectionsNumber++; } @@ -206,34 +199,31 @@ int AsClusterFatTree::connectNodeToParents(FatTreeNode *node) { return connectionsNumber; } - -bool AsClusterFatTree::areRelated(FatTreeNode *parent, FatTreeNode *child) { +bool AsClusterFatTree::areRelated(FatTreeNode* parent, FatTreeNode* child) +{ std::stringstream msgBuffer; - if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { - msgBuffer << "Are " << child->id << "(" << child->level << "," - << child->position << ") <"; + if (XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { + msgBuffer << "Are " << child->id << "(" << child->level << "," << child->position << ") <"; - for (unsigned int i = 0 ; i < this->levels_ ; i++) { + for (unsigned int i = 0; i < this->levels_; i++) { msgBuffer << child->label[i] << ","; } msgBuffer << ">"; - - msgBuffer << " and " << parent->id << "(" << parent->level - << "," << parent->position << ") <"; - for (unsigned int i = 0 ; i < this->levels_ ; i++) { + + msgBuffer << " and " << parent->id << "(" << parent->level << "," << parent->position << ") <"; + for (unsigned int i = 0; i < this->levels_; i++) { msgBuffer << parent->label[i] << ","; } msgBuffer << ">"; msgBuffer << " related ? "; XBT_DEBUG("%s", msgBuffer.str().c_str()); - } if (parent->level != child->level + 1) { return false; } - - for (unsigned int i = 0 ; i < this->levels_; i++) { + + for (unsigned int i = 0; i < this->levels_; i++) { if (parent->label[i] != child->label[i] && i + 1 != parent->level) { return false; } @@ -241,49 +231,46 @@ bool AsClusterFatTree::areRelated(FatTreeNode *parent, FatTreeNode *child) { return true; } -void AsClusterFatTree::generateSwitches() { +void AsClusterFatTree::generateSwitches() +{ XBT_DEBUG("Generating switches."); this->nodesByLevel_.resize(this->levels_ + 1, 0); unsigned int nodesRequired = 0; // Take care of the number of nodes by level this->nodesByLevel_[0] = 1; - for (unsigned int i = 0 ; i < this->levels_ ; i++) + for (unsigned int i = 0; i < this->levels_; i++) this->nodesByLevel_[0] *= this->lowerLevelNodesNumber_[i]; - - if(this->nodesByLevel_[0] != this->nodes_.size()) { + + if (this->nodesByLevel_[0] != this->nodes_.size()) { surf_parse_error("The number of provided nodes does not fit with the wanted topology." " Please check your platform description (We need %d nodes, we got %zu)", this->nodesByLevel_[0], this->nodes_.size()); return; } - - for (unsigned int i = 0 ; i < this->levels_ ; i++) { + for (unsigned int i = 0; i < this->levels_; i++) { int nodesInThisLevel = 1; - - for (unsigned int j = 0 ; j <= i ; j++) + + for (unsigned int j = 0; j <= i; j++) nodesInThisLevel *= this->upperLevelNodesNumber_[j]; - - for (unsigned int j = i+1 ; j < this->levels_ ; j++) + + for (unsigned int j = i + 1; j < this->levels_; j++) nodesInThisLevel *= this->lowerLevelNodesNumber_[j]; - this->nodesByLevel_[i+1] = nodesInThisLevel; + this->nodesByLevel_[i + 1] = nodesInThisLevel; nodesRequired += nodesInThisLevel; } - // Create the switches int k = 0; - for (unsigned int i = 0 ; i < this->levels_ ; i++) { - for (unsigned int j = 0 ; j < this->nodesByLevel_[i + 1] ; j++) { + for (unsigned int i = 0; i < this->levels_; i++) { + for (unsigned int j = 0; j < this->nodesByLevel_[i + 1]; j++) { FatTreeNode* newNode = new FatTreeNode(this->cluster_, --k, i + 1, j); XBT_DEBUG("We create the switch %d(%d,%d)", newNode->id, newNode->level, newNode->position); - newNode->children.resize(this->lowerLevelNodesNumber_[i] * - this->lowerLevelPortsNumber_[i]); + newNode->children.resize(this->lowerLevelNodesNumber_[i] * this->lowerLevelPortsNumber_[i]); if (i != this->levels_ - 1) { - newNode->parents.resize(this->upperLevelNodesNumber_[i + 1] * - this->lowerLevelPortsNumber_[i + 1]); + newNode->parents.resize(this->upperLevelNodesNumber_[i + 1] * this->lowerLevelPortsNumber_[i + 1]); } newNode->label.resize(this->levels_); this->nodes_.push_back(newNode); @@ -291,45 +278,44 @@ void AsClusterFatTree::generateSwitches() { } } -void AsClusterFatTree::generateLabels() { +void AsClusterFatTree::generateLabels() +{ XBT_DEBUG("Generating labels."); // TODO : check if nodesByLevel and nodes are filled std::vector maxLabel(this->levels_); std::vector currentLabel(this->levels_); unsigned int k = 0; - for (unsigned int i = 0 ; i <= this->levels_ ; i++) { + for (unsigned int i = 0; i <= this->levels_; i++) { currentLabel.assign(this->levels_, 0); - for (unsigned int j = 0 ; j < this->levels_ ; j++) { - maxLabel[j] = j + 1 > i ? - this->lowerLevelNodesNumber_[j] : this->upperLevelNodesNumber_[j]; + for (unsigned int j = 0; j < this->levels_; j++) { + maxLabel[j] = j + 1 > i ? this->lowerLevelNodesNumber_[j] : this->upperLevelNodesNumber_[j]; } - - for (unsigned int j = 0 ; j < this->nodesByLevel_[i] ; j++) { - if(XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug )) { + for (unsigned int j = 0; j < this->nodesByLevel_[i]; j++) { + + if (XBT_LOG_ISENABLED(surf_route_fat_tree, xbt_log_priority_debug)) { std::stringstream msgBuffer; msgBuffer << "Assigning label <"; - for (unsigned int l = 0 ; l < this->levels_ ; l++) { + for (unsigned int l = 0; l < this->levels_; l++) { msgBuffer << currentLabel[l] << ","; } - msgBuffer << "> to " << k << " (" << i << "," << j <<")"; - + msgBuffer << "> to " << k << " (" << i << "," << j << ")"; + XBT_DEBUG("%s", msgBuffer.str().c_str()); } this->nodes_[k]->label.assign(currentLabel.begin(), currentLabel.end()); - bool remainder = true; + bool remainder = true; unsigned int pos = 0; while (remainder && pos < this->levels_) { ++currentLabel[pos]; if (currentLabel[pos] >= maxLabel[pos]) { currentLabel[pos] = 0; - remainder = true; + remainder = true; ++pos; - } - else { - pos = 0; + } else { + pos = 0; remainder = false; } } @@ -338,49 +324,51 @@ void AsClusterFatTree::generateLabels() { } } - -int AsClusterFatTree::getLevelPosition(const unsigned int level) { +int AsClusterFatTree::getLevelPosition(const unsigned int level) +{ xbt_assert(level <= this->levels_, "The impossible did happen. Yet again."); int tempPosition = 0; - for (unsigned int i = 0 ; i < level ; i++) + for (unsigned int i = 0; i < level; i++) tempPosition += this->nodesByLevel_[i]; return tempPosition; } -void AsClusterFatTree::addProcessingNode(int id) { +void AsClusterFatTree::addProcessingNode(int id) +{ using std::make_pair; static int position = 0; FatTreeNode* newNode; newNode = new FatTreeNode(this->cluster_, id, 0, position++); - newNode->parents.resize(this->upperLevelNodesNumber_[0] * - this->lowerLevelPortsNumber_[0]); + newNode->parents.resize(this->upperLevelNodesNumber_[0] * this->lowerLevelPortsNumber_[0]); newNode->label.resize(this->levels_); - this->computeNodes_.insert(make_pair(id,newNode)); + this->computeNodes_.insert(make_pair(id, newNode)); this->nodes_.push_back(newNode); } -void AsClusterFatTree::addLink(FatTreeNode *parent, unsigned int parentPort, - FatTreeNode *child, unsigned int childPort) { - FatTreeLink *newLink; +void AsClusterFatTree::addLink(FatTreeNode* parent, unsigned int parentPort, FatTreeNode* child, unsigned int childPort) +{ + FatTreeLink* newLink; newLink = new FatTreeLink(this->cluster_, child, parent); - XBT_DEBUG("Creating a link between the parent (%d,%d,%u) and the child (%d,%d,%u)", - parent->level, parent->position, parentPort, child->level, child->position, childPort); + XBT_DEBUG("Creating a link between the parent (%d,%d,%u) and the child (%d,%d,%u)", parent->level, parent->position, + parentPort, child->level, child->position, childPort); parent->children[parentPort] = newLink; - child->parents[childPort] = newLink; + child->parents[childPort] = newLink; this->links_.push_back(newLink); } -void AsClusterFatTree::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) { +void AsClusterFatTree::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) +{ std::vector parameters; std::vector tmp; boost::split(parameters, cluster->topo_parameters, boost::is_any_of(";")); // TODO : we have to check for zeros and negative numbers, or it might crash - if (parameters.size() != 4){ - surf_parse_error("Fat trees are defined by the levels number and 3 vectors, see the documentation for more information"); + if (parameters.size() != 4) { + surf_parse_error( + "Fat trees are defined by the levels number and 3 vectors, see the documentation for more information"); } // The first parts of topo_parameters should be the levels number @@ -388,117 +376,112 @@ void AsClusterFatTree::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster // Then, a l-sized vector standing for the children number by level boost::split(tmp, parameters[1], boost::is_any_of(",")); - if(tmp.size() != this->levels_) { - surf_parse_error("Fat trees are defined by the levels number and 3 vectors" + if (tmp.size() != this->levels_) { + surf_parse_error("Fat trees are defined by the levels number and 3 vectors" ", see the documentation for more information"); } - for(size_t i = 0 ; i < tmp.size() ; i++){ + for (size_t i = 0; i < tmp.size(); i++) { this->lowerLevelNodesNumber_.push_back(xbt_str_parse_int(tmp[i].c_str(), "Invalid lower level node number: %s")); } - + // Then, a l-sized vector standing for the parents number by level boost::split(tmp, parameters[2], boost::is_any_of(",")); - if(tmp.size() != this->levels_) { - surf_parse_error("Fat trees are defined by the levels number and 3 vectors" + if (tmp.size() != this->levels_) { + surf_parse_error("Fat trees are defined by the levels number and 3 vectors" ", see the documentation for more information"); } - for(size_t i = 0 ; i < tmp.size() ; i++){ + for (size_t i = 0; i < tmp.size(); i++) { this->upperLevelNodesNumber_.push_back(xbt_str_parse_int(tmp[i].c_str(), "Invalid upper level node number: %s")); } - + // Finally, a l-sized vector standing for the ports number with the lower level boost::split(tmp, parameters[3], boost::is_any_of(",")); - if(tmp.size() != this->levels_) { - surf_parse_error("Fat trees are defined by the levels number and 3 vectors" + if (tmp.size() != this->levels_) { + surf_parse_error("Fat trees are defined by the levels number and 3 vectors" ", see the documentation for more information"); - } - for(size_t i = 0 ; i < tmp.size() ; i++){ + for (size_t i = 0; i < tmp.size(); i++) { this->lowerLevelPortsNumber_.push_back(xbt_str_parse_int(tmp[i].c_str(), "Invalid lower level node number: %s")); } this->cluster_ = cluster; } - -void AsClusterFatTree::generateDotFile(const std::string& filename) const { +void AsClusterFatTree::generateDotFile(const std::string& filename) const +{ std::ofstream file; file.open(filename, std::ios::out | std::ios::trunc); xbt_assert(file.is_open(), "Unable to open file %s", filename.c_str()); file << "graph AsClusterFatTree {\n"; - for (unsigned int i = 0 ; i < this->nodes_.size() ; i++) { + for (unsigned int i = 0; i < this->nodes_.size(); i++) { file << this->nodes_[i]->id; - if(this->nodes_[i]->id < 0) + if (this->nodes_[i]->id < 0) file << " [shape=circle];\n"; else file << " [shape=hexagon];\n"; } - for (unsigned int i = 0 ; i < this->links_.size() ; i++ ) { - file << this->links_[i]->downNode->id - << " -- " - << this->links_[i]->upNode->id - << ";\n"; + for (unsigned int i = 0; i < this->links_.size(); i++) { + file << this->links_[i]->downNode->id << " -- " << this->links_[i]->upNode->id << ";\n"; } file << "}"; file.close(); } -FatTreeNode::FatTreeNode(sg_platf_cluster_cbarg_t cluster, int id, int level, - int position) : id(id), level(level), - position(position) { +FatTreeNode::FatTreeNode(sg_platf_cluster_cbarg_t cluster, int id, int level, int position) + : id(id), level(level), position(position) +{ s_sg_platf_link_cbarg_t linkTemplate; - if(cluster->limiter_link) { + if (cluster->limiter_link) { memset(&linkTemplate, 0, sizeof(linkTemplate)); linkTemplate.bandwidth = cluster->limiter_link; - linkTemplate.latency = 0; - linkTemplate.policy = SURF_LINK_SHARED; - linkTemplate.id = bprintf("limiter_%d", id); + linkTemplate.latency = 0; + linkTemplate.policy = SURF_LINK_SHARED; + linkTemplate.id = bprintf("limiter_%d", id); sg_platf_new_link(&linkTemplate); this->limiterLink = Link::byName(linkTemplate.id); free((void*)linkTemplate.id); } - if(cluster->loopback_bw || cluster->loopback_lat) { + if (cluster->loopback_bw || cluster->loopback_lat) { memset(&linkTemplate, 0, sizeof(linkTemplate)); linkTemplate.bandwidth = cluster->loopback_bw; - linkTemplate.latency = cluster->loopback_lat; - linkTemplate.policy = SURF_LINK_FATPIPE; - linkTemplate.id = bprintf("loopback_%d", id); + linkTemplate.latency = cluster->loopback_lat; + linkTemplate.policy = SURF_LINK_FATPIPE; + linkTemplate.id = bprintf("loopback_%d", id); sg_platf_new_link(&linkTemplate); this->loopback = Link::byName(linkTemplate.id); free((void*)linkTemplate.id); - } + } } -FatTreeLink::FatTreeLink(sg_platf_cluster_cbarg_t cluster, - FatTreeNode *downNode, - FatTreeNode *upNode) : upNode(upNode), - downNode(downNode) { +FatTreeLink::FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode* downNode, FatTreeNode* upNode) + : upNode(upNode), downNode(downNode) +{ static int uniqueId = 0; s_sg_platf_link_cbarg_t linkTemplate; memset(&linkTemplate, 0, sizeof(linkTemplate)); linkTemplate.bandwidth = cluster->bw; - linkTemplate.latency = cluster->lat; - linkTemplate.policy = cluster->sharing_policy; // sthg to do with that ? - linkTemplate.id = bprintf("link_from_%d_to_%d_%d", downNode->id, upNode->id, uniqueId); + linkTemplate.latency = cluster->lat; + linkTemplate.policy = cluster->sharing_policy; // sthg to do with that ? + linkTemplate.id = bprintf("link_from_%d_to_%d_%d", downNode->id, upNode->id, uniqueId); sg_platf_new_link(&linkTemplate); Link* link; std::string tmpID; if (cluster->sharing_policy == SURF_LINK_FULLDUPLEX) { - tmpID = std::string(linkTemplate.id) + "_UP"; - link = Link::byName(tmpID.c_str()); - this->upLink = link; // check link? - tmpID = std::string(linkTemplate.id) + "_DOWN"; - link = Link::byName(tmpID.c_str()); + tmpID = std::string(linkTemplate.id) + "_UP"; + link = Link::byName(tmpID.c_str()); + this->upLink = link; // check link? + tmpID = std::string(linkTemplate.id) + "_DOWN"; + link = Link::byName(tmpID.c_str()); this->downLink = link; // check link ? - } - else { - link = Link::byName(linkTemplate.id); - this->upLink = link; + } else { + link = Link::byName(linkTemplate.id); + this->upLink = link; this->downLink = link; } uniqueId++; free((void*)linkTemplate.id); } - -}}} // namespace +} +} +} // namespace diff --git a/src/kernel/routing/FatTreeZone.hpp b/src/kernel/routing/FatTreeZone.hpp index 91f2c54d31..4e356df6df 100644 --- a/src/kernel/routing/FatTreeZone.hpp +++ b/src/kernel/routing/FatTreeZone.hpp @@ -24,10 +24,10 @@ public: int id; /* Level into the tree, with 0 being the leafs. */ - unsigned int level; + unsigned int level; /* \brief Position into the level, starting from 0. */ - unsigned int position; + 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 @@ -36,12 +36,12 @@ public: std::vector label; /** Links to the lower level, where the position in the vector corresponds to - * a port number. + * a port number. */ std::vector children; /** Links to the upper level, where the position in the vector corresponds to - * a port number. - */ + * a port number. + */ std::vector parents; /** Virtual link standing for the node global capacity. @@ -54,8 +54,6 @@ public: FatTreeNode(sg_platf_cluster_cbarg_t cluster, int id, int level, int position); }; - - /** \brief Link in a fat tree (@ref AsClusterFatTree). * * Represents a single, duplex link in a fat tree. This is necessary to have a tree. @@ -63,18 +61,18 @@ public: */ class FatTreeLink { public: - FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode *source, FatTreeNode *destination); + FatTreeLink(sg_platf_cluster_cbarg_t cluster, FatTreeNode* source, FatTreeNode* destination); /** Link going up in the tree */ - Link *upLink; + Link* upLink; /** Link going down in the tree */ - Link *downLink; + Link* downLink; /** Upper end of the link */ - FatTreeNode *upNode; + FatTreeNode* upNode; /** Lower end of the link */ - FatTreeNode *downNode; + FatTreeNode* downNode; }; -/** +/** * \class AsClusterFatTree * * \brief Fat tree representation and routing. @@ -91,7 +89,7 @@ public: * 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 + * 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 @@ -107,9 +105,9 @@ public: void getLocalRoute(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 + * tree is generated by calling generateLabels(), generateSwitches() and * then connection all nodes between them, using their label. */ void seal() override; @@ -122,13 +120,12 @@ public: void generateDotFile(const std::string& filename = "fatTree.dot") const; private: - - //description of a PGFT (TODO : better doc) + // description of a PGFT (TODO : better doc) unsigned int levels_ = 0; 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::vector links_; @@ -136,16 +133,16 @@ private: sg_platf_cluster_cbarg_t cluster_ = nullptr; - void addLink(FatTreeNode *parent, unsigned int parentPort, - FatTreeNode *child, unsigned int childPort); + 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); + int connectNodeToParents(FatTreeNode* node); + bool areRelated(FatTreeNode* parent, FatTreeNode* child); + bool isInSubTree(FatTreeNode* root, FatTreeNode* node); }; - -}}} // namespaces +} +} +} // namespaces #endif diff --git a/src/kernel/routing/FloydZone.cpp b/src/kernel/routing/FloydZone.cpp index 9a3333b176..145f128e90 100644 --- a/src/kernel/routing/FloydZone.cpp +++ b/src/kernel/routing/FloydZone.cpp @@ -12,9 +12,9 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_floyd, surf, "Routing part of surf"); -#define TO_FLOYD_COST(i,j) (costTable_)[(i)+(j)*table_size] -#define TO_FLOYD_PRED(i,j) (predecessorTable_)[(i)+(j)*table_size] -#define TO_FLOYD_LINK(i,j) (linkTable_)[(i)+(j)*table_size] +#define TO_FLOYD_COST(i, j) (costTable_)[(i) + (j)*table_size] +#define TO_FLOYD_PRED(i, j) (predecessorTable_)[(i) + (j)*table_size] +#define TO_FLOYD_LINK(i, j) (linkTable_)[(i) + (j)*table_size] namespace simgrid { namespace kernel { @@ -23,11 +23,12 @@ namespace routing { AsFloyd::AsFloyd(As* father, const char* name) : AsRoutedGraph(father, name) { predecessorTable_ = nullptr; - costTable_ = nullptr; - linkTable_ = nullptr; + costTable_ = nullptr; + linkTable_ = nullptr; } -AsFloyd::~AsFloyd(){ +AsFloyd::~AsFloyd() +{ if (linkTable_ == nullptr) // Dealing with a parse error in the file? return; int table_size = vertices_.size(); @@ -72,7 +73,7 @@ void AsFloyd::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t r getGlobalRoute(prev_dst_gw, e_route->gw_src, route->link_list, lat); } - for (auto link: *e_route->link_list) { + for (auto link : *e_route->link_list) { route->link_list->push_back(link); if (lat) *lat += link->latency(); @@ -89,11 +90,11 @@ void AsFloyd::addRoute(sg_platf_route_cbarg_t route) addRouteCheckParams(route); - if(!linkTable_) { + if (!linkTable_) { /* Create Cost, Predecessor and Link tables */ - costTable_ = xbt_new0(double, table_size * table_size); /* link cost from host to host */ - predecessorTable_ = xbt_new0(int, table_size * table_size); /* predecessor host numbers */ - linkTable_ = xbt_new0(sg_platf_route_cbarg_t, table_size * table_size); /* actual link between src and dst */ + costTable_ = xbt_new0(double, table_size* table_size); /* link cost from host to host */ + predecessorTable_ = xbt_new0(int, table_size* table_size); /* predecessor host numbers */ + linkTable_ = xbt_new0(sg_platf_route_cbarg_t, table_size * table_size); /* actual link between src and dst */ /* Initialize costs and predecessors */ for (int i = 0; i < table_size; i++) @@ -117,8 +118,8 @@ void AsFloyd::addRoute(sg_platf_route_cbarg_t route) TO_FLOYD_LINK(route->src->id(), route->dst->id()) = newExtendedRoute(hierarchy_, route, 1); TO_FLOYD_PRED(route->src->id(), route->dst->id()) = route->src->id(); - TO_FLOYD_COST(route->src->id(), route->dst->id()) = (TO_FLOYD_LINK(route->src->id(), route->dst->id()))->link_list->size(); - + TO_FLOYD_COST(route->src->id(), route->dst->id()) = + (TO_FLOYD_LINK(route->src->id(), route->dst->id()))->link_list->size(); if (route->symmetrical == true) { if (route->gw_dst) // AS route (to adapt the error message, if any) @@ -132,13 +133,13 @@ void AsFloyd::addRoute(sg_platf_route_cbarg_t route) "The route between %s and %s already exists. You should not declare the reverse path as symmetrical.", route->dst->name().c_str(), route->src->name().c_str()); - if(route->gw_dst && route->gw_src) { + if (route->gw_dst && route->gw_src) { NetCard* gw_tmp = route->gw_src; - route->gw_src = route->gw_dst; - route->gw_dst = gw_tmp; + route->gw_src = route->gw_dst; + route->gw_dst = gw_tmp; } - if(!route->gw_src && !route->gw_dst) + if (!route->gw_src && !route->gw_dst) XBT_DEBUG("Load Route from \"%s\" to \"%s\"", route->dst->name().c_str(), route->src->name().c_str()); else XBT_DEBUG("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", route->dst->name().c_str(), route->gw_src->name().c_str(), @@ -146,19 +147,21 @@ void AsFloyd::addRoute(sg_platf_route_cbarg_t route) TO_FLOYD_LINK(route->dst->id(), route->src->id()) = newExtendedRoute(hierarchy_, route, 0); TO_FLOYD_PRED(route->dst->id(), route->src->id()) = route->dst->id(); - TO_FLOYD_COST(route->dst->id(), route->src->id()) = (TO_FLOYD_LINK(route->dst->id(), route->src->id()))->link_list->size(); /* count of links, old model assume 1 */ + TO_FLOYD_COST(route->dst->id(), route->src->id()) = + (TO_FLOYD_LINK(route->dst->id(), route->src->id()))->link_list->size(); /* count of links, old model assume 1 */ } } -void AsFloyd::seal(){ +void AsFloyd::seal() +{ /* set the size of table routing */ size_t table_size = vertices_.size(); - if(!linkTable_) { + if (!linkTable_) { /* Create Cost, Predecessor and Link tables */ - costTable_ = xbt_new0(double, table_size * table_size); /* link cost from host to host */ - predecessorTable_ = xbt_new0(int, table_size * table_size); /* predecessor host numbers */ - linkTable_ = xbt_new0(sg_platf_route_cbarg_t, table_size * table_size); /* actual link between src and dst */ + costTable_ = xbt_new0(double, table_size* table_size); /* link cost from host to host */ + predecessorTable_ = xbt_new0(int, table_size* table_size); /* predecessor host numbers */ + linkTable_ = xbt_new0(sg_platf_route_cbarg_t, table_size * table_size); /* actual link between src and dst */ /* Initialize costs and predecessors */ for (unsigned int i = 0; i < table_size; i++) @@ -174,9 +177,9 @@ void AsFloyd::seal(){ for (unsigned int i = 0; i < table_size; i++) { sg_platf_route_cbarg_t e_route = TO_FLOYD_LINK(i, i); if (!e_route) { - e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1); - e_route->gw_src = nullptr; - e_route->gw_dst = nullptr; + e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1); + e_route->gw_src = nullptr; + e_route->gw_dst = nullptr; e_route->link_list = new std::vector(); e_route->link_list->push_back(surf_network_model->loopback_); TO_FLOYD_LINK(i, i) = e_route; @@ -200,5 +203,6 @@ void AsFloyd::seal(){ } } } - -}}} +} +} +} diff --git a/src/kernel/routing/FloydZone.hpp b/src/kernel/routing/FloydZone.hpp index 1e5a87d48f..c3023b22a2 100644 --- a/src/kernel/routing/FloydZone.hpp +++ b/src/kernel/routing/FloydZone.hpp @@ -13,7 +13,7 @@ namespace kernel { namespace routing { /** Floyd routing data: slow initialization, fast lookup, lesser memory requirements, shortest path routing only */ -class XBT_PRIVATE AsFloyd: public AsRoutedGraph { +class XBT_PRIVATE AsFloyd : public AsRoutedGraph { public: explicit AsFloyd(As* father, const char* name); ~AsFloyd() override; @@ -24,11 +24,12 @@ public: private: /* vars to compute the Floyd algorithm. */ - int *predecessorTable_; - double *costTable_; - sg_platf_route_cbarg_t *linkTable_; + int* predecessorTable_; + double* costTable_; + sg_platf_route_cbarg_t* linkTable_; }; - -}}} // namespaces +} +} +} // namespaces #endif /* SURF_ROUTING_FLOYD_HPP_ */ diff --git a/src/kernel/routing/FullZone.cpp b/src/kernel/routing/FullZone.cpp index 2d5f73ea5c..3a3c6dcf5b 100644 --- a/src/kernel/routing/FullZone.cpp +++ b/src/kernel/routing/FullZone.cpp @@ -9,16 +9,17 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_full, surf, "Routing part of surf"); -#define TO_ROUTE_FULL(i,j) routingTable_[(i)+(j)*table_size] +#define TO_ROUTE_FULL(i, j) routingTable_[(i) + (j)*table_size] namespace simgrid { namespace kernel { namespace routing { AsFull::AsFull(As* father, const char* name) : AsRoutedGraph(father, name) { - } +} -void AsFull::seal() { +void AsFull::seal() +{ int i; sg_platf_route_cbarg_t e_route; @@ -34,9 +35,9 @@ void AsFull::seal() { for (i = 0; i < table_size; i++) { e_route = TO_ROUTE_FULL(i, i); if (!e_route) { - e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1); - e_route->gw_src = nullptr; - e_route->gw_dst = nullptr; + e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1); + e_route->gw_src = nullptr; + e_route->gw_dst = nullptr; e_route->link_list = new std::vector(); e_route->link_list->push_back(surf_network_model->loopback_); TO_ROUTE_FULL(i, i) = e_route; @@ -45,15 +46,16 @@ void AsFull::seal() { } } -AsFull::~AsFull(){ +AsFull::~AsFull() +{ if (routingTable_) { int table_size = static_cast(vertices_.size()); /* Delete routing table */ for (int i = 0; i < table_size; i++) for (int j = 0; j < table_size; j++) { - if (TO_ROUTE_FULL(i,j)){ - delete TO_ROUTE_FULL(i,j)->link_list; - xbt_free(TO_ROUTE_FULL(i,j)); + if (TO_ROUTE_FULL(i, j)) { + delete TO_ROUTE_FULL(i, j)->link_list; + xbt_free(TO_ROUTE_FULL(i, j)); } } xbt_free(routingTable_); @@ -64,7 +66,7 @@ void AsFull::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t re { XBT_DEBUG("full getLocalRoute from %s[%d] to %s[%d]", src->cname(), src->id(), dst->cname(), dst->id()); - size_t table_size = vertices_.size(); + size_t table_size = vertices_.size(); sg_platf_route_cbarg_t e_route = TO_ROUTE_FULL(src->id(), dst->id()); if (e_route != nullptr) { @@ -80,8 +82,8 @@ void AsFull::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t re void AsFull::addRoute(sg_platf_route_cbarg_t route) { - NetCard* src = route->src; - NetCard* dst = route->dst; + NetCard* src = route->src; + NetCard* dst = route->dst; addRouteCheckParams(route); size_t table_size = vertices_.size(); @@ -106,8 +108,8 @@ void AsFull::addRoute(sg_platf_route_cbarg_t route) if (route->symmetrical == true && src != dst) { if (route->gw_dst && route->gw_src) { NetCard* gw_tmp = route->gw_src; - route->gw_src = route->gw_dst; - route->gw_dst = gw_tmp; + route->gw_src = route->gw_dst; + route->gw_dst = gw_tmp; } if (route->gw_dst) // AS route (to adapt the error message, if any) xbt_assert( @@ -123,5 +125,6 @@ void AsFull::addRoute(sg_platf_route_cbarg_t route) TO_ROUTE_FULL(dst->id(), src->id())->link_list->shrink_to_fit(); } } - -}}} // namespace +} +} +} // namespace diff --git a/src/kernel/routing/FullZone.hpp b/src/kernel/routing/FullZone.hpp index ce252da0ca..3628e90c80 100644 --- a/src/kernel/routing/FullZone.hpp +++ b/src/kernel/routing/FullZone.hpp @@ -13,7 +13,7 @@ namespace kernel { namespace routing { /** Full routing: fast, large memory requirements, fully expressive */ -class XBT_PRIVATE AsFull: public AsRoutedGraph { +class XBT_PRIVATE AsFull : public AsRoutedGraph { public: explicit AsFull(As* father, const char* name); void seal() override; @@ -22,9 +22,10 @@ public: void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency) override; void addRoute(sg_platf_route_cbarg_t route) override; - sg_platf_route_cbarg_t *routingTable_ = nullptr; + sg_platf_route_cbarg_t* routingTable_ = nullptr; }; - -}}} // namespaces +} +} +} // namespaces #endif /* SIMGRID_ROUTING_FULL_HPP_ */ diff --git a/src/kernel/routing/NetZoneImpl.cpp b/src/kernel/routing/NetZoneImpl.cpp index 5e6bd31676..79bbdf0d5d 100644 --- a/src/kernel/routing/NetZoneImpl.cpp +++ b/src/kernel/routing/NetZoneImpl.cpp @@ -6,270 +6,257 @@ #include "xbt/log.h" #include "simgrid/s4u/host.hpp" -#include "src/kernel/routing/NetZoneImpl.hpp" #include "src/kernel/routing/NetCard.hpp" +#include "src/kernel/routing/NetZoneImpl.hpp" #include "src/surf/cpu_interface.hpp" #include "src/surf/network_interface.hpp" XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_route); namespace simgrid { - namespace kernel { - namespace routing { - - class BypassRoute { - public: - explicit BypassRoute(NetCard* gwSrc, NetCard* gwDst) : gw_src(gwSrc), gw_dst(gwDst) {} - const NetCard* gw_src; - const NetCard* gw_dst; - std::vector links; - }; - - AsImpl::AsImpl(As* father, const char* name) : As(father, name) - { - xbt_assert(nullptr == xbt_lib_get_or_null(as_router_lib, name, ROUTING_ASR_LEVEL), - "Refusing to create a second AS called '%s'.", name); - - netcard_ = new NetCard(name, NetCard::Type::As, static_cast(father)); - xbt_lib_set(as_router_lib, name, ROUTING_ASR_LEVEL, static_cast(netcard_)); - XBT_DEBUG("AS '%s' created with the id '%d'", name, netcard_->id()); - } - AsImpl::~AsImpl() - { - for (auto& kv : bypassRoutes_) - delete kv.second; +namespace kernel { +namespace routing { + +class BypassRoute { +public: + explicit BypassRoute(NetCard* gwSrc, NetCard* gwDst) : gw_src(gwSrc), gw_dst(gwDst) {} + const NetCard* gw_src; + const NetCard* gw_dst; + std::vector links; +}; + +AsImpl::AsImpl(As* father, const char* name) : As(father, name) +{ + xbt_assert(nullptr == xbt_lib_get_or_null(as_router_lib, name, ROUTING_ASR_LEVEL), + "Refusing to create a second AS called '%s'.", name); + + netcard_ = new NetCard(name, NetCard::Type::As, static_cast(father)); + xbt_lib_set(as_router_lib, name, ROUTING_ASR_LEVEL, static_cast(netcard_)); + XBT_DEBUG("AS '%s' created with the id '%d'", name, netcard_->id()); +} +AsImpl::~AsImpl() +{ + for (auto& kv : bypassRoutes_) + delete kv.second; +} + +simgrid::s4u::Host* AsImpl::createHost(const char* name, std::vector* speedPerPstate, int coreAmount) +{ + simgrid::s4u::Host* res = new simgrid::s4u::Host(name); + + if (hierarchy_ == RoutingMode::unset) + hierarchy_ = RoutingMode::base; + + res->pimpl_netcard = new NetCard(name, NetCard::Type::Host, this); + + surf_cpu_model_pm->createCpu(res, speedPerPstate, coreAmount); + + return res; +} + +void AsImpl::addBypassRoute(sg_platf_route_cbarg_t e_route) +{ + /* Argument validity checks */ + if (e_route->gw_dst) { + XBT_DEBUG("Load bypassASroute from %s@%s to %s@%s", e_route->src->cname(), e_route->gw_src->cname(), + e_route->dst->cname(), e_route->gw_dst->cname()); + xbt_assert(!e_route->link_list->empty(), "Bypass route between %s@%s and %s@%s cannot be empty.", + e_route->src->cname(), e_route->gw_src->cname(), e_route->dst->cname(), e_route->gw_dst->cname()); + xbt_assert(bypassRoutes_.find({e_route->src, e_route->dst}) == bypassRoutes_.end(), + "The bypass route between %s@%s and %s@%s already exists.", e_route->src->cname(), + e_route->gw_src->cname(), e_route->dst->cname(), e_route->gw_dst->cname()); + } else { + XBT_DEBUG("Load bypassRoute from %s to %s", e_route->src->cname(), e_route->dst->cname()); + xbt_assert(!e_route->link_list->empty(), "Bypass route between %s and %s cannot be empty.", e_route->src->cname(), + e_route->dst->cname()); + xbt_assert(bypassRoutes_.find({e_route->src, e_route->dst}) == bypassRoutes_.end(), + "The bypass route between %s and %s already exists.", e_route->src->cname(), e_route->dst->cname()); } - simgrid::s4u::Host* AsImpl::createHost(const char* name, std::vector* speedPerPstate, int coreAmount) - { - simgrid::s4u::Host* res = new simgrid::s4u::Host(name); + /* Build a copy that will be stored in the dict */ + kernel::routing::BypassRoute* newRoute = new kernel::routing::BypassRoute(e_route->gw_src, e_route->gw_dst); + for (auto link : *e_route->link_list) + newRoute->links.push_back(link); + + /* Store it */ + bypassRoutes_.insert({{e_route->src, e_route->dst}, newRoute}); +} + +/** @brief Get the common ancestor and its first children in each line leading to src and dst + * + * In the recursive case, this sets common_ancestor, src_ancestor and dst_ancestor are set as follows. + * @verbatim + * platform root + * | + * ... <- possibly long path + * | + * common_ancestor + * / \ + * / \ + * / \ <- direct links + * / \ + * / \ + * src_ancestor dst_ancestor <- must be different in the recursive case + * | | + * ... ... <-- possibly long pathes (one hop or more) + * | | + * src dst + * @endverbatim + * + * In the base case (when src and dst are in the same AS), things are as follows: + * @verbatim + * platform root + * | + * ... <-- possibly long path + * | + * common_ancestor==src_ancestor==dst_ancestor <-- all the same value + * / \ + * / \ <-- direct links (exactly one hop) + * / \ + * src dst + * @endverbatim + * + * A specific recursive case occurs when src is the ancestor of dst. In this case, + * the base case routing should be used so the common_ancestor is specifically set + * to src_ancestor==dst_ancestor. + * Naturally, things are completely symmetrical if dst is the ancestor of src. + * @verbatim + * platform root + * | + * ... <-- possibly long path + * | + * src == src_ancestor==dst_ancestor==common_ancestor <-- same value + * | + * ... <-- possibly long path (one hop or more) + * | + * dst + * @endverbatim + */ +static void find_common_ancestors(NetCard* src, NetCard* dst, + /* OUT */ AsImpl** common_ancestor, AsImpl** src_ancestor, AsImpl** dst_ancestor) +{ + /* Deal with the easy base case */ + if (src->containingAS() == dst->containingAS()) { + *common_ancestor = src->containingAS(); + *src_ancestor = *common_ancestor; + *dst_ancestor = *common_ancestor; + return; + } - if (hierarchy_ == RoutingMode::unset) - hierarchy_ = RoutingMode::base; + /* engage the full recursive search */ - res->pimpl_netcard = new NetCard(name, NetCard::Type::Host, this); + /* (1) find the path to root of src and dst*/ + AsImpl* src_as = src->containingAS(); + AsImpl* dst_as = dst->containingAS(); - surf_cpu_model_pm->createCpu(res, speedPerPstate, coreAmount); + xbt_assert(src_as, "Host %s must be in an AS", src->cname()); + xbt_assert(dst_as, "Host %s must be in an AS", dst->cname()); - return res; + /* (2) find the path to the root routing component */ + std::vector path_src; + AsImpl* current = src->containingAS(); + while (current != nullptr) { + path_src.push_back(current); + current = static_cast(current->father()); } - - void AsImpl::addBypassRoute(sg_platf_route_cbarg_t e_route) - { - /* Argument validity checks */ - if (e_route->gw_dst) { - XBT_DEBUG("Load bypassASroute from %s@%s to %s@%s", e_route->src->cname(), e_route->gw_src->cname(), - e_route->dst->cname(), e_route->gw_dst->cname()); - xbt_assert(!e_route->link_list->empty(), "Bypass route between %s@%s and %s@%s cannot be empty.", - e_route->src->cname(), e_route->gw_src->cname(), e_route->dst->cname(), e_route->gw_dst->cname()); - xbt_assert(bypassRoutes_.find({e_route->src, e_route->dst}) == bypassRoutes_.end(), - "The bypass route between %s@%s and %s@%s already exists.", e_route->src->cname(), - e_route->gw_src->cname(), e_route->dst->cname(), e_route->gw_dst->cname()); - } else { - XBT_DEBUG("Load bypassRoute from %s to %s", e_route->src->cname(), e_route->dst->cname()); - xbt_assert(!e_route->link_list->empty(), "Bypass route between %s and %s cannot be empty.", e_route->src->cname(), - e_route->dst->cname()); - xbt_assert(bypassRoutes_.find({e_route->src, e_route->dst}) == bypassRoutes_.end(), - "The bypass route between %s and %s already exists.", e_route->src->cname(), e_route->dst->cname()); - } - - /* Build a copy that will be stored in the dict */ - kernel::routing::BypassRoute* newRoute = new kernel::routing::BypassRoute(e_route->gw_src, e_route->gw_dst); - for (auto link : *e_route->link_list) - newRoute->links.push_back(link); - - /* Store it */ - bypassRoutes_.insert({{e_route->src, e_route->dst}, newRoute}); + std::vector path_dst; + current = dst->containingAS(); + while (current != nullptr) { + path_dst.push_back(current); + current = static_cast(current->father()); } - /** @brief Get the common ancestor and its first children in each line leading to src and dst + /* (3) find the common father. + * Before that, index_src and index_dst may be different, they both point to nullptr in path_src/path_dst + * So we move them down simultaneously as long as they point to the same content. * - * In the recursive case, this sets common_ancestor, src_ancestor and dst_ancestor are set as follows. - * @verbatim - * platform root - * | - * ... <- possibly long path - * | - * common_ancestor - * / \ - * / \ - * / \ <- direct links - * / \ - * / \ - * src_ancestor dst_ancestor <- must be different in the recursive case - * | | - * ... ... <-- possibly long pathes (one hop or more) - * | | - * src dst - * @endverbatim - * - * In the base case (when src and dst are in the same AS), things are as follows: - * @verbatim - * platform root - * | - * ... <-- possibly long path - * | - * common_ancestor==src_ancestor==dst_ancestor <-- all the same value - * / \ - * / \ <-- direct links (exactly one hop) - * / \ - * src dst - * @endverbatim - * - * A specific recursive case occurs when src is the ancestor of dst. In this case, - * the base case routing should be used so the common_ancestor is specifically set - * to src_ancestor==dst_ancestor. - * Naturally, things are completely symmetrical if dst is the ancestor of src. - * @verbatim - * platform root - * | - * ... <-- possibly long path - * | - * src == src_ancestor==dst_ancestor==common_ancestor <-- same value - * | - * ... <-- possibly long path (one hop or more) - * | - * dst - * @endverbatim + * This works because all SimGrid platform have a unique root element (that is the last element of both paths). */ - static void find_common_ancestors(NetCard* src, NetCard* dst, - /* OUT */ AsImpl** common_ancestor, AsImpl** src_ancestor, AsImpl** dst_ancestor) - { - /* Deal with the easy base case */ - if (src->containingAS() == dst->containingAS()) { - *common_ancestor = src->containingAS(); - *src_ancestor = *common_ancestor; - *dst_ancestor = *common_ancestor; - return; - } - - /* engage the full recursive search */ - - /* (1) find the path to root of src and dst*/ - AsImpl* src_as = src->containingAS(); - AsImpl* dst_as = dst->containingAS(); - - xbt_assert(src_as, "Host %s must be in an AS", src->cname()); - xbt_assert(dst_as, "Host %s must be in an AS", dst->cname()); - - /* (2) find the path to the root routing component */ - std::vector path_src; - AsImpl* current = src->containingAS(); - while (current != nullptr) { - path_src.push_back(current); - current = static_cast(current->father()); - } - std::vector path_dst; - current = dst->containingAS(); - while (current != nullptr) { - path_dst.push_back(current); - current = static_cast(current->father()); - } - - /* (3) find the common father. - * Before that, index_src and index_dst may be different, they both point to nullptr in path_src/path_dst - * So we move them down simultaneously as long as they point to the same content. - * - * This works because all SimGrid platform have a unique root element (that is the last element of both paths). - */ - AsImpl* father = nullptr; // the AS we dropped on the previous loop iteration - while (path_src.size() > 1 && path_dst.size() > 1 && - path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) { - father = path_src.at(path_src.size() - 1); - path_src.pop_back(); - path_dst.pop_back(); - } + AsImpl* father = nullptr; // the AS we dropped on the previous loop iteration + while (path_src.size() > 1 && path_dst.size() > 1 && + path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) { + father = path_src.at(path_src.size() - 1); + path_src.pop_back(); + path_dst.pop_back(); + } - /* (4) we found the difference at least. Finalize the returned values */ - *src_ancestor = path_src.at(path_src.size() - 1); /* the first different father of src */ - *dst_ancestor = path_dst.at(path_dst.size() - 1); /* the first different father of dst */ - if (*src_ancestor == *dst_ancestor) { // src is the ancestor of dst, or the contrary - *common_ancestor = *src_ancestor; - } else { - *common_ancestor = father; - } + /* (4) we found the difference at least. Finalize the returned values */ + *src_ancestor = path_src.at(path_src.size() - 1); /* the first different father of src */ + *dst_ancestor = path_dst.at(path_dst.size() - 1); /* the first different father of dst */ + if (*src_ancestor == *dst_ancestor) { // src is the ancestor of dst, or the contrary + *common_ancestor = *src_ancestor; + } else { + *common_ancestor = father; } +} + +/* PRECONDITION: this is the common ancestor of src and dst */ +bool AsImpl::getBypassRoute(routing::NetCard* src, routing::NetCard* dst, + /* OUT */ std::vector* links, double* latency) +{ + // If never set a bypass route return nullptr without any further computations + if (bypassRoutes_.empty()) + return false; - /* PRECONDITION: this is the common ancestor of src and dst */ - bool AsImpl::getBypassRoute(routing::NetCard* src, routing::NetCard* dst, - /* OUT */ std::vector* links, double* latency) - { - // If never set a bypass route return nullptr without any further computations - if (bypassRoutes_.empty()) - return false; - - /* Base case, no recursion is needed */ - if (dst->containingAS() == this && src->containingAS() == this) { - if (bypassRoutes_.find({src, dst}) != bypassRoutes_.end()) { - BypassRoute* bypassedRoute = bypassRoutes_.at({src, dst}); - for (surf::Link* link : bypassedRoute->links) { - links->push_back(link); - if (latency) - *latency += link->latency(); - } - XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links", src->cname(), dst->cname(), - bypassedRoute->links.size()); - return true; + /* Base case, no recursion is needed */ + if (dst->containingAS() == this && src->containingAS() == this) { + if (bypassRoutes_.find({src, dst}) != bypassRoutes_.end()) { + BypassRoute* bypassedRoute = bypassRoutes_.at({src, dst}); + for (surf::Link* link : bypassedRoute->links) { + links->push_back(link); + if (latency) + *latency += link->latency(); } - return false; + XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links", src->cname(), dst->cname(), + bypassedRoute->links.size()); + return true; } + return false; + } - /* Engage recursive search */ + /* Engage recursive search */ + /* (1) find the path to the root routing component */ + std::vector path_src; + As* current = src->containingAS(); + while (current != nullptr) { + path_src.push_back(static_cast(current)); + current = current->father_; + } - /* (1) find the path to the root routing component */ - std::vector path_src; - As* current = src->containingAS(); - while (current != nullptr) { - path_src.push_back(static_cast(current)); - current = current->father_; - } + std::vector path_dst; + current = dst->containingAS(); + while (current != nullptr) { + path_dst.push_back(static_cast(current)); + current = current->father_; + } - std::vector path_dst; - current = dst->containingAS(); - while (current != nullptr) { - path_dst.push_back(static_cast(current)); - current = current->father_; - } + /* (2) find the common father */ + while (path_src.size() > 1 && path_dst.size() > 1 && + path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) { + path_src.pop_back(); + path_dst.pop_back(); + } - /* (2) find the common father */ - while (path_src.size() > 1 && path_dst.size() > 1 && - path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) { - path_src.pop_back(); - path_dst.pop_back(); - } + int max_index_src = path_src.size() - 1; + int max_index_dst = path_dst.size() - 1; - int max_index_src = path_src.size() - 1; - int max_index_dst = path_dst.size() - 1; - - int max_index = std::max(max_index_src, max_index_dst); - - /* (3) Search for a bypass making the path up to the ancestor useless */ - BypassRoute* bypassedRoute = nullptr; - std::pair key; - for (int max = 0; max <= max_index; max++) { - for (int i = 0; i < max; i++) { - if (i <= max_index_src && max <= max_index_dst) { - key = {path_src.at(i)->netcard_, path_dst.at(max)->netcard_}; - if (bypassRoutes_.find(key) != bypassRoutes_.end()) { - bypassedRoute = bypassRoutes_.at(key); - break; - } - } - if (max <= max_index_src && i <= max_index_dst) { - key = {path_src.at(max)->netcard_, path_dst.at(i)->netcard_}; - if (bypassRoutes_.find(key) != bypassRoutes_.end()) { - bypassedRoute = bypassRoutes_.at(key); - break; - } + int max_index = std::max(max_index_src, max_index_dst); + + /* (3) Search for a bypass making the path up to the ancestor useless */ + BypassRoute* bypassedRoute = nullptr; + std::pair key; + for (int max = 0; max <= max_index; max++) { + for (int i = 0; i < max; i++) { + if (i <= max_index_src && max <= max_index_dst) { + key = {path_src.at(i)->netcard_, path_dst.at(max)->netcard_}; + if (bypassRoutes_.find(key) != bypassRoutes_.end()) { + bypassedRoute = bypassRoutes_.at(key); + break; } } - - if (bypassedRoute) - break; - - if (max <= max_index_src && max <= max_index_dst) { - key = {path_src.at(max)->netcard_, path_dst.at(max)->netcard_}; + if (max <= max_index_src && i <= max_index_dst) { + key = {path_src.at(max)->netcard_, path_dst.at(i)->netcard_}; if (bypassRoutes_.find(key) != bypassRoutes_.end()) { bypassedRoute = bypassRoutes_.at(key); break; @@ -277,69 +264,82 @@ namespace simgrid { } } - /* (4) If we have the bypass, use it. If not, caller will do the Right Thing. */ - if (bypassedRoute) { - XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links. We may have to complete it with recursive " - "calls to getRoute", - src->cname(), dst->cname(), bypassedRoute->links.size()); - if (src != key.first) - getGlobalRoute(src, const_cast(bypassedRoute->gw_src), links, latency); - for (surf::Link* link : bypassedRoute->links) { - links->push_back(link); - if (latency) - *latency += link->latency(); - } - if (dst != key.second) - getGlobalRoute(const_cast(bypassedRoute->gw_dst), dst, links, latency); - return true; - } - XBT_DEBUG("No bypass route from '%s' to '%s'.", src->cname(), dst->cname()); - return false; - } + if (bypassedRoute) + break; - void AsImpl::getGlobalRoute(routing::NetCard* src, routing::NetCard* dst, - /* OUT */ std::vector* links, double* latency) - { - s_sg_platf_route_cbarg_t route; - memset(&route,0,sizeof(route)); - - XBT_DEBUG("Resolve route from '%s' to '%s'", src->cname(), dst->cname()); - - /* Find how src and dst are interconnected */ - AsImpl *common_ancestor, *src_ancestor, *dst_ancestor; - find_common_ancestors(src, dst, &common_ancestor, &src_ancestor, &dst_ancestor); - XBT_DEBUG("elements_father: common ancestor '%s' src ancestor '%s' dst ancestor '%s'", - common_ancestor->name(), src_ancestor->name(), dst_ancestor->name()); - - /* Check whether a direct bypass is defined. If so, use it and bail out */ - if (common_ancestor->getBypassRoute(src, dst, links, latency)) - return; - - /* If src and dst are in the same AS, life is good */ - if (src_ancestor == dst_ancestor) { /* SURF_ROUTING_BASE */ - route.link_list = links; - common_ancestor->getLocalRoute(src, dst, &route, latency); - return; + if (max <= max_index_src && max <= max_index_dst) { + key = {path_src.at(max)->netcard_, path_dst.at(max)->netcard_}; + if (bypassRoutes_.find(key) != bypassRoutes_.end()) { + bypassedRoute = bypassRoutes_.at(key); + break; } + } + } - /* Not in the same AS, no bypass. We'll have to find our path between the ASes recursively*/ + /* (4) If we have the bypass, use it. If not, caller will do the Right Thing. */ + if (bypassedRoute) { + XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links. We may have to complete it with recursive " + "calls to getRoute", + src->cname(), dst->cname(), bypassedRoute->links.size()); + if (src != key.first) + getGlobalRoute(src, const_cast(bypassedRoute->gw_src), links, latency); + for (surf::Link* link : bypassedRoute->links) { + links->push_back(link); + if (latency) + *latency += link->latency(); + } + if (dst != key.second) + getGlobalRoute(const_cast(bypassedRoute->gw_dst), dst, links, latency); + return true; + } + XBT_DEBUG("No bypass route from '%s' to '%s'.", src->cname(), dst->cname()); + return false; +} + +void AsImpl::getGlobalRoute(routing::NetCard* src, routing::NetCard* dst, + /* OUT */ std::vector* links, double* latency) +{ + s_sg_platf_route_cbarg_t route; + memset(&route, 0, sizeof(route)); + + XBT_DEBUG("Resolve route from '%s' to '%s'", src->cname(), dst->cname()); + + /* Find how src and dst are interconnected */ + AsImpl *common_ancestor, *src_ancestor, *dst_ancestor; + find_common_ancestors(src, dst, &common_ancestor, &src_ancestor, &dst_ancestor); + XBT_DEBUG("elements_father: common ancestor '%s' src ancestor '%s' dst ancestor '%s'", common_ancestor->name(), + src_ancestor->name(), dst_ancestor->name()); + + /* Check whether a direct bypass is defined. If so, use it and bail out */ + if (common_ancestor->getBypassRoute(src, dst, links, latency)) + return; + + /* If src and dst are in the same AS, life is good */ + if (src_ancestor == dst_ancestor) { /* SURF_ROUTING_BASE */ + route.link_list = links; + common_ancestor->getLocalRoute(src, dst, &route, latency); + return; + } - route.link_list = new std::vector(); + /* Not in the same AS, no bypass. We'll have to find our path between the ASes recursively*/ - common_ancestor->getLocalRoute(src_ancestor->netcard_, dst_ancestor->netcard_, &route, latency); - xbt_assert((route.gw_src != nullptr) && (route.gw_dst != nullptr), "bad gateways for route from \"%s\" to \"%s\"", - src->cname(), dst->cname()); + route.link_list = new std::vector(); - /* If source gateway is not our source, we have to recursively find our way up to this point */ - if (src != route.gw_src) - getGlobalRoute(src, route.gw_src, links, latency); - for (auto link: *route.link_list) - links->push_back(link); - delete route.link_list; + common_ancestor->getLocalRoute(src_ancestor->netcard_, dst_ancestor->netcard_, &route, latency); + xbt_assert((route.gw_src != nullptr) && (route.gw_dst != nullptr), "bad gateways for route from \"%s\" to \"%s\"", + src->cname(), dst->cname()); - /* If dest gateway is not our destination, we have to recursively find our way from this point */ - if (route.gw_dst != dst) - getGlobalRoute(route.gw_dst, dst, links, latency); - } + /* If source gateway is not our source, we have to recursively find our way up to this point */ + if (src != route.gw_src) + getGlobalRoute(src, route.gw_src, links, latency); + for (auto link : *route.link_list) + links->push_back(link); + delete route.link_list; -}}} // namespace + /* If dest gateway is not our destination, we have to recursively find our way from this point */ + if (route.gw_dst != dst) + getGlobalRoute(route.gw_dst, dst, links, latency); +} +} +} +} // namespace diff --git a/src/kernel/routing/NetZoneImpl.hpp b/src/kernel/routing/NetZoneImpl.hpp index 2ff562085e..d442e7c1fd 100644 --- a/src/kernel/routing/NetZoneImpl.hpp +++ b/src/kernel/routing/NetZoneImpl.hpp @@ -8,8 +8,8 @@ #include "xbt/graph.h" -#include "simgrid/s4u/forward.hpp" #include "simgrid/s4u/As.hpp" +#include "simgrid/s4u/forward.hpp" #include "src/surf/xml/platf_private.hpp" // FIXME: kill sg_platf_route_cbarg_t to remove that UGLY include @@ -99,7 +99,8 @@ private: std::map, BypassRoute*> bypassRoutes_; // src x dst -> route routing::NetCard* netcard_ = nullptr; // Our representative in the father AS }; - -}}}; // Namespace simgrid::kernel::routing +} +} +}; // Namespace simgrid::kernel::routing #endif /* SIMGRID_SURF_AS_HPP */ diff --git a/src/kernel/routing/RoutedZone.cpp b/src/kernel/routing/RoutedZone.cpp index 4c67d85908..e87b942487 100644 --- a/src/kernel/routing/RoutedZone.cpp +++ b/src/kernel/routing/RoutedZone.cpp @@ -4,13 +4,13 @@ * under the terms of the license (GNU LGPL) which comes with this package. */ #include "xbt/dict.h" -#include "xbt/log.h" -#include "xbt/sysdep.h" #include "xbt/dynar.h" #include "xbt/graph.h" +#include "xbt/log.h" +#include "xbt/sysdep.h" -#include "src/kernel/routing/RoutedZone.hpp" #include "src/kernel/routing/NetCard.hpp" +#include "src/kernel/routing/RoutedZone.hpp" #include "src/surf/network_interface.hpp" XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_routing_generic, surf_route, "Generic implementation of the surf routing"); @@ -26,16 +26,16 @@ void routing_route_free(sg_platf_route_cbarg_t route) /* ************************************************************************** */ /* *********************** GENERIC BUSINESS METHODS ************************* */ -static const char *instr_node_name(xbt_node_t node) +static const char* instr_node_name(xbt_node_t node) { - void *data = xbt_graph_node_get_data(node); - char *str = (char *) data; + void* data = xbt_graph_node_get_data(node); + char* str = (char*)data; return str; } -xbt_node_t new_xbt_graph_node(xbt_graph_t graph, const char *name, xbt_dict_t nodes) +xbt_node_t new_xbt_graph_node(xbt_graph_t graph, const char* name, xbt_dict_t nodes) { - xbt_node_t ret = (xbt_node_t) xbt_dict_get_or_null(nodes, name); + xbt_node_t ret = (xbt_node_t)xbt_dict_get_or_null(nodes, name); if (ret) return ret; @@ -46,16 +46,16 @@ xbt_node_t new_xbt_graph_node(xbt_graph_t graph, const char *name, xbt_dict_t no xbt_edge_t new_xbt_graph_edge(xbt_graph_t graph, xbt_node_t s, xbt_node_t d, xbt_dict_t edges) { - const char *sn = instr_node_name(s); - const char *dn = instr_node_name(d); - int len = strlen(sn) + strlen(dn) + 1; - char *name = (char *) xbt_malloc(len * sizeof(char)); + const char* sn = instr_node_name(s); + const char* dn = instr_node_name(d); + int len = strlen(sn) + strlen(dn) + 1; + char* name = (char*)xbt_malloc(len * sizeof(char)); snprintf(name, len, "%s%s", sn, dn); - xbt_edge_t ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name); + xbt_edge_t ret = (xbt_edge_t)xbt_dict_get_or_null(edges, name); if (ret == nullptr) { snprintf(name, len, "%s%s", dn, sn); - ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name); + ret = (xbt_edge_t)xbt_dict_get_or_null(edges, name); } if (ret == nullptr) { @@ -76,13 +76,13 @@ AsRoutedGraph::AsRoutedGraph(As* father, const char* name) : AsImpl(father, name void AsRoutedGraph::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges) { - for (auto my_src: vertices_){ - for (auto my_dst: vertices_){ + for (auto my_src : vertices_) { + for (auto my_dst : vertices_) { if (my_src == my_dst) continue; sg_platf_route_cbarg_t route = xbt_new0(s_sg_platf_route_cbarg_t, 1); - route->link_list = new std::vector(); + route->link_list = new std::vector(); getLocalRoute(my_src, my_dst, route, nullptr); @@ -99,13 +99,13 @@ void AsRoutedGraph::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edg previous_name = my_src->cname(); } - for (auto link: *route->link_list) { - const char *link_name = link->getName(); - current = new_xbt_graph_node(graph, link_name, nodes); - current_name = link_name; + for (auto link : *route->link_list) { + const char* link_name = link->getName(); + current = new_xbt_graph_node(graph, link_name, nodes); + current_name = link_name; new_xbt_graph_edge(graph, previous, current, edges); - XBT_DEBUG (" %s -> %s", previous_name, current_name); - previous = current; + XBT_DEBUG(" %s -> %s", previous_name, current_name); + previous = current; previous_name = current_name; } @@ -117,10 +117,10 @@ void AsRoutedGraph::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edg current_name = my_dst->cname(); } new_xbt_graph_edge(graph, previous, current, edges); - XBT_DEBUG (" %s -> %s", previous_name, current_name); + XBT_DEBUG(" %s -> %s", previous_name, current_name); delete route->link_list; - xbt_free (route); + xbt_free(route); } } } @@ -128,15 +128,16 @@ void AsRoutedGraph::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edg /* ************************************************************************** */ /* ************************* GENERIC AUX FUNCTIONS ************************** */ /* change a route containing link names into a route containing link entities */ -sg_platf_route_cbarg_t AsRoutedGraph::newExtendedRoute(RoutingMode hierarchy, sg_platf_route_cbarg_t routearg, int change_order) +sg_platf_route_cbarg_t AsRoutedGraph::newExtendedRoute(RoutingMode hierarchy, sg_platf_route_cbarg_t routearg, + int change_order) { sg_platf_route_cbarg_t result; - result = xbt_new0(s_sg_platf_route_cbarg_t, 1); + result = xbt_new0(s_sg_platf_route_cbarg_t, 1); result->link_list = new std::vector(); xbt_assert(hierarchy == RoutingMode::base || hierarchy == RoutingMode::recursive, - "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here."); + "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here."); if (hierarchy == RoutingMode::recursive) { xbt_assert(routearg->gw_src && routearg->gw_dst, "nullptr is obviously a deficient gateway"); @@ -155,13 +156,13 @@ sg_platf_route_cbarg_t AsRoutedGraph::newExtendedRoute(RoutingMode hierarchy, sg return result; } -void AsRoutedGraph::getRouteCheckParams(NetCard *src, NetCard *dst) +void AsRoutedGraph::getRouteCheckParams(NetCard* src, NetCard* dst) { xbt_assert(src, "Cannot find a route from nullptr to %s", dst->cname()); xbt_assert(dst, "Cannot find a route from %s to nullptr", src->cname()); - As *src_as = src->containingAS(); - As *dst_as = dst->containingAS(); + As* src_as = src->containingAS(); + As* dst_as = dst->containingAS(); xbt_assert(src_as == dst_as, "Internal error: %s@%s and %s@%s are not in the same AS as expected. Please report that bug.", @@ -171,28 +172,31 @@ void AsRoutedGraph::getRouteCheckParams(NetCard *src, NetCard *dst) "%s@%s). Please report that bug.", src->cname(), dst->cname(), src_as->name(), dst_as->name(), name()); } -void AsRoutedGraph::addRouteCheckParams(sg_platf_route_cbarg_t route) { - NetCard *src = route->src; - NetCard *dst = route->dst; +void AsRoutedGraph::addRouteCheckParams(sg_platf_route_cbarg_t route) +{ + NetCard* src = route->src; + NetCard* dst = route->dst; const char* srcName = src->cname(); const char* dstName = dst->cname(); - if(!route->gw_dst && !route->gw_src) { + if (!route->gw_dst && !route->gw_src) { XBT_DEBUG("Load Route from \"%s\" to \"%s\"", srcName, dstName); xbt_assert(src, "Cannot add a route from %s to %s: %s does not exist.", srcName, dstName, srcName); xbt_assert(dst, "Cannot add a route from %s to %s: %s does not exist.", srcName, dstName, dstName); - xbt_assert(! route->link_list->empty(), "Empty route (between %s and %s) forbidden.", srcName, dstName); - xbt_assert(! src->isAS(), "When defining a route, src cannot be an AS such as '%s'. Did you meant to have an ASroute?", srcName); - xbt_assert(! dst->isAS(), "When defining a route, dst cannot be an AS such as '%s'. Did you meant to have an ASroute?", dstName); + xbt_assert(!route->link_list->empty(), "Empty route (between %s and %s) forbidden.", srcName, dstName); + xbt_assert(!src->isAS(), + "When defining a route, src cannot be an AS such as '%s'. Did you meant to have an ASroute?", srcName); + xbt_assert(!dst->isAS(), + "When defining a route, dst cannot be an AS such as '%s'. Did you meant to have an ASroute?", dstName); } else { XBT_DEBUG("Load ASroute from %s@%s to %s@%s", srcName, route->gw_src->cname(), dstName, route->gw_dst->cname()); xbt_assert(src->isAS(), "When defining an ASroute, src must be an AS but '%s' is not", srcName); xbt_assert(dst->isAS(), "When defining an ASroute, dst must be an AS but '%s' is not", dstName); xbt_assert(route->gw_src->isHost() || route->gw_src->isRouter(), - "When defining an ASroute, gw_src must be an host or a router but '%s' is not.", srcName); + "When defining an ASroute, gw_src must be an host or a router but '%s' is not.", srcName); xbt_assert(route->gw_dst->isHost() || route->gw_dst->isRouter(), - "When defining an ASroute, gw_dst must be an host or a router but '%s' is not.", dstName); + "When defining an ASroute, gw_dst must be an host or a router but '%s' is not.", dstName); xbt_assert(route->gw_src != route->gw_dst, "Cannot define an ASroute from '%s' to itself", route->gw_src->cname()); @@ -206,5 +210,6 @@ void AsRoutedGraph::addRouteCheckParams(sg_platf_route_cbarg_t route) { onRouteCreation(route->symmetrical, route->src, route->dst, route->gw_src, route->gw_dst, route->link_list); } - -}}} +} +} +} diff --git a/src/kernel/routing/RoutedZone.hpp b/src/kernel/routing/RoutedZone.hpp index 0ecf61526f..0c2d547ec9 100644 --- a/src/kernel/routing/RoutedZone.hpp +++ b/src/kernel/routing/RoutedZone.hpp @@ -17,12 +17,15 @@ public: explicit AsRoutedGraph(As* father, const char* name); void getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges) override; - virtual sg_platf_route_cbarg_t newExtendedRoute(RoutingMode hierarchy, sg_platf_route_cbarg_t routearg, int change_order); + virtual sg_platf_route_cbarg_t newExtendedRoute(RoutingMode hierarchy, sg_platf_route_cbarg_t routearg, + int change_order); + protected: - void getRouteCheckParams(NetCard *src, NetCard *dst); + void getRouteCheckParams(NetCard* src, NetCard* dst); void addRouteCheckParams(sg_platf_route_cbarg_t route); }; - -}}} // namespace +} +} +} // namespace #endif /* SIMGRID_ROUTING_GENERIC_HPP_ */ diff --git a/src/kernel/routing/TorusZone.cpp b/src/kernel/routing/TorusZone.cpp index 7785d210a9..1da873a586 100644 --- a/src/kernel/routing/TorusZone.cpp +++ b/src/kernel/routing/TorusZone.cpp @@ -10,220 +10,224 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_cluster_torus, surf_route_cluster, "Torus Routing part of surf"); -inline unsigned int *rankId_to_coords(int rankId, xbt_dynar_t dimensions) +inline unsigned int* rankId_to_coords(int rankId, xbt_dynar_t dimensions) { unsigned int i = 0, cur_dim_size = 1, dim_size_product = 1; - unsigned int *coords = (unsigned int *) malloc(xbt_dynar_length(dimensions) * sizeof(unsigned int)); + unsigned int* coords = (unsigned int*)malloc(xbt_dynar_length(dimensions) * sizeof(unsigned int)); for (i = 0; i < xbt_dynar_length(dimensions); i++) { cur_dim_size = xbt_dynar_get_as(dimensions, i, int); - coords[i] = (rankId / dim_size_product) % cur_dim_size; + coords[i] = (rankId / dim_size_product) % cur_dim_size; dim_size_product *= cur_dim_size; } return coords; } - namespace simgrid { - namespace kernel { - namespace routing { - AsClusterTorus::AsClusterTorus(As* father, const char* name) : AsCluster(father, name) - { - } - AsClusterTorus::~AsClusterTorus() { - xbt_dynar_free(&dimensions_); - } +namespace kernel { +namespace routing { +AsClusterTorus::AsClusterTorus(As* father, const char* name) : AsCluster(father, name) +{ +} +AsClusterTorus::~AsClusterTorus() +{ + xbt_dynar_free(&dimensions_); +} - void AsClusterTorus::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position) { - char *link_id; - unsigned int j = 0; - /* - * Create all links that exist in the torus. - * Each rank creates @a dimensions-1 links - */ - int neighbor_rank_id = 0; // The other node the link connects - int current_dimension = 0, // which dimension are we currently in? - // we need to iterate over all dimensions - // and create all links there - dim_product = 1; // Needed to calculate the next neighbor_id - for (j = 0; j < xbt_dynar_length(dimensions_); j++) { - - s_sg_platf_link_cbarg_t link; - memset(&link, 0, sizeof(link)); - current_dimension = xbt_dynar_get_as(dimensions_, j, int); - neighbor_rank_id = (((int)rank / dim_product) % current_dimension == current_dimension - 1) - ? rank - (current_dimension - 1) * dim_product - : rank + dim_product; - //name of neighbor is not right for non contiguous cluster radicals (as id != rank in this case) - link_id = bprintf("%s_link_from_%i_to_%i", cluster->id, id, neighbor_rank_id); - link.id = link_id; - link.bandwidth = cluster->bw; - link.latency = cluster->lat; - link.policy = cluster->sharing_policy; - sg_platf_new_link(&link); - Link* linkUp; - Link* linkDown; - if (link.policy == SURF_LINK_FULLDUPLEX) { - char *tmp_link = bprintf("%s_UP", link_id); - linkUp = Link::byName(tmp_link); - free(tmp_link); - tmp_link = bprintf("%s_DOWN", link_id); - linkDown = Link::byName(tmp_link); - free(tmp_link); - } else { - linkUp = Link::byName(link_id); - linkDown = linkUp; - } - /* - * Add the link to its appropriate position; - * note that position rankId*(xbt_dynar_length(dimensions)+has_loopback?+has_limiter?) - * holds the link "rankId->rankId" - */ - privateLinks_.insert({position + j, {linkUp, linkDown}}); - dim_product *= current_dimension; - xbt_free(link_id); - } - rank++; +void AsClusterTorus::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position) +{ + char* link_id; + unsigned int j = 0; + /* + * Create all links that exist in the torus. + * Each rank creates @a dimensions-1 links + */ + int neighbor_rank_id = 0; // The other node the link connects + int current_dimension = 0, // which dimension are we currently in? + // we need to iterate over all dimensions + // and create all links there + dim_product = 1; // Needed to calculate the next neighbor_id + for (j = 0; j < xbt_dynar_length(dimensions_); j++) { + + s_sg_platf_link_cbarg_t link; + memset(&link, 0, sizeof(link)); + current_dimension = xbt_dynar_get_as(dimensions_, j, int); + neighbor_rank_id = (((int)rank / dim_product) % current_dimension == current_dimension - 1) + ? rank - (current_dimension - 1) * dim_product + : rank + dim_product; + // name of neighbor is not right for non contiguous cluster radicals (as id != rank in this case) + link_id = bprintf("%s_link_from_%i_to_%i", cluster->id, id, neighbor_rank_id); + link.id = link_id; + link.bandwidth = cluster->bw; + link.latency = cluster->lat; + link.policy = cluster->sharing_policy; + sg_platf_new_link(&link); + Link* linkUp; + Link* linkDown; + if (link.policy == SURF_LINK_FULLDUPLEX) { + char* tmp_link = bprintf("%s_UP", link_id); + linkUp = Link::byName(tmp_link); + free(tmp_link); + tmp_link = bprintf("%s_DOWN", link_id); + linkDown = Link::byName(tmp_link); + free(tmp_link); + } else { + linkUp = Link::byName(link_id); + linkDown = linkUp; } + /* + * Add the link to its appropriate position; + * note that position rankId*(xbt_dynar_length(dimensions)+has_loopback?+has_limiter?) + * holds the link "rankId->rankId" + */ + privateLinks_.insert({position + j, {linkUp, linkDown}}); + dim_product *= current_dimension; + xbt_free(link_id); + } + rank++; +} - void AsClusterTorus::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) { - - unsigned int iter; - char *groups; - xbt_dynar_t dimensions = xbt_str_split(cluster->topo_parameters, ","); - - if (!xbt_dynar_is_empty(dimensions)) { - dimensions_ = xbt_dynar_new(sizeof(int), nullptr); - /* We are in a torus cluster - * Parse attribute dimensions="dim1,dim2,dim3,...,dimN" - * and safe it in a dynarray. - * Additionally, we need to know how many ranks we have in total - */ - xbt_dynar_foreach(dimensions, iter, groups) { - int tmp = surf_parse_get_int(xbt_dynar_get_as(dimensions, iter, char *)); - xbt_dynar_set_as(dimensions_, iter, int, tmp); - } - - linkCountPerNode_ = xbt_dynar_length(dimensions_); +void AsClusterTorus::parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) +{ - } - xbt_dynar_free(&dimensions); + unsigned int iter; + char* groups; + xbt_dynar_t dimensions = xbt_str_split(cluster->topo_parameters, ","); + + if (!xbt_dynar_is_empty(dimensions)) { + dimensions_ = xbt_dynar_new(sizeof(int), nullptr); + /* We are in a torus cluster + * Parse attribute dimensions="dim1,dim2,dim3,...,dimN" + * and safe it in a dynarray. + * Additionally, we need to know how many ranks we have in total + */ + xbt_dynar_foreach (dimensions, iter, groups) { + int tmp = surf_parse_get_int(xbt_dynar_get_as(dimensions, iter, char*)); + xbt_dynar_set_as(dimensions_, iter, int, tmp); } - void AsClusterTorus::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t route, double* lat) - { + linkCountPerNode_ = xbt_dynar_length(dimensions_); + } + xbt_dynar_free(&dimensions); +} - XBT_VERB("torus getLocalRoute from '%s'[%d] to '%s'[%d]", src->name().c_str(), src->id(), dst->name().c_str(), - dst->id()); +void AsClusterTorus::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t route, double* lat) +{ - if (dst->isRouter() || src->isRouter()) - return; + XBT_VERB("torus getLocalRoute from '%s'[%d] to '%s'[%d]", src->name().c_str(), src->id(), dst->name().c_str(), + dst->id()); - if (src->id() == dst->id() && hasLoopback_) { - std::pair info = privateLinks_.at(src->id() * linkCountPerNode_); + if (dst->isRouter() || src->isRouter()) + return; - route->link_list->push_back(info.first); - if (lat) - *lat += info.first->latency(); - return; - } + if (src->id() == dst->id() && hasLoopback_) { + std::pair info = privateLinks_.at(src->id() * linkCountPerNode_); + route->link_list->push_back(info.first); + if (lat) + *lat += info.first->latency(); + return; + } - /* - * Dimension based routing routes through each dimension consecutively - * TODO Change to dynamic assignment - */ - unsigned int j, cur_dim, dim_product = 1; - unsigned int current_node = src->id(); - unsigned int next_node = 0; - /* - * Arrays that hold the coordinates of the current node and - * the target; comparing the values at the i-th position of - * both arrays, we can easily assess whether we need to route - * into this dimension or not. - */ - unsigned int* myCoords = rankId_to_coords(src->id(), dimensions_); - unsigned int* targetCoords = rankId_to_coords(dst->id(), dimensions_); - /* - * linkOffset describes the offset where the link - * we want to use is stored - * (+1 is added because each node has a link from itself to itself, - * which can only be the case if src->m_id == dst->m_id -- see above - * for this special case) - */ - int nodeOffset = (xbt_dynar_length(dimensions_) + 1) * src->id(); - - int linkOffset = nodeOffset; - bool use_lnk_up = false; // Is this link of the form "cur -> next" or "next -> cur"? - // false means: next -> cur - while (current_node != dst->id()) { - dim_product = 1; // First, we will route in x-dimension - for (j = 0; j < xbt_dynar_length(dimensions_); j++) { - cur_dim = xbt_dynar_get_as(dimensions_, j, int); - - // current_node/dim_product = position in current dimension - if ((current_node / dim_product) % cur_dim != (dst->id() / dim_product) % cur_dim) { - - if ((targetCoords[j] > myCoords[j] && targetCoords[j] <= myCoords[j] + cur_dim / 2) // Is the target node on the right, without the wrap-around? - || (myCoords[j] > cur_dim / 2 && (myCoords[j] + cur_dim / 2) % cur_dim >= targetCoords[j])) { // Or do we need to use the wrap around to reach it? - if ((current_node / dim_product) % cur_dim == cur_dim - 1) - next_node = (current_node + dim_product - dim_product * cur_dim); - else - next_node = (current_node + dim_product); - - // HERE: We use *CURRENT* node for calculation (as opposed to next_node) - nodeOffset = current_node * (linkCountPerNode_); - linkOffset = nodeOffset + (hasLoopback_?1:0) + (hasLimiter_?1:0) + j; - use_lnk_up = true; - assert(linkOffset >= 0); - } else { // Route to the left - if ((current_node / dim_product) % cur_dim == 0) - next_node = (current_node - dim_product + dim_product * cur_dim); - else - next_node = (current_node - dim_product); - - // HERE: We use *next* node for calculation (as opposed to current_node!) - nodeOffset = next_node * (linkCountPerNode_); - linkOffset = nodeOffset + j + (hasLoopback_?1:0) + (hasLimiter_?1:0) ; - use_lnk_up = false; - - assert(linkOffset >= 0); - } - XBT_DEBUG("torus_get_route_and_latency - current_node: %i, next_node: %u, linkOffset is %i", - current_node, next_node, linkOffset); - - break; - } - - dim_product *= cur_dim; + /* + * Dimension based routing routes through each dimension consecutively + * TODO Change to dynamic assignment + */ + unsigned int j, cur_dim, dim_product = 1; + unsigned int current_node = src->id(); + unsigned int next_node = 0; + /* + * Arrays that hold the coordinates of the current node and + * the target; comparing the values at the i-th position of + * both arrays, we can easily assess whether we need to route + * into this dimension or not. + */ + unsigned int* myCoords = rankId_to_coords(src->id(), dimensions_); + unsigned int* targetCoords = rankId_to_coords(dst->id(), dimensions_); + /* + * linkOffset describes the offset where the link + * we want to use is stored + * (+1 is added because each node has a link from itself to itself, + * which can only be the case if src->m_id == dst->m_id -- see above + * for this special case) + */ + int nodeOffset = (xbt_dynar_length(dimensions_) + 1) * src->id(); + + int linkOffset = nodeOffset; + bool use_lnk_up = false; // Is this link of the form "cur -> next" or "next -> cur"? + // false means: next -> cur + while (current_node != dst->id()) { + dim_product = 1; // First, we will route in x-dimension + for (j = 0; j < xbt_dynar_length(dimensions_); j++) { + cur_dim = xbt_dynar_get_as(dimensions_, j, int); + + // current_node/dim_product = position in current dimension + if ((current_node / dim_product) % cur_dim != (dst->id() / dim_product) % cur_dim) { + + if ((targetCoords[j] > myCoords[j] && + targetCoords[j] <= myCoords[j] + cur_dim / 2) // Is the target node on the right, without the wrap-around? + || (myCoords[j] > cur_dim / 2 && + (myCoords[j] + cur_dim / 2) % cur_dim >= + targetCoords[j])) { // Or do we need to use the wrap around to reach it? + if ((current_node / dim_product) % cur_dim == cur_dim - 1) + next_node = (current_node + dim_product - dim_product * cur_dim); + else + next_node = (current_node + dim_product); + + // HERE: We use *CURRENT* node for calculation (as opposed to next_node) + nodeOffset = current_node * (linkCountPerNode_); + linkOffset = nodeOffset + (hasLoopback_ ? 1 : 0) + (hasLimiter_ ? 1 : 0) + j; + use_lnk_up = true; + assert(linkOffset >= 0); + } else { // Route to the left + if ((current_node / dim_product) % cur_dim == 0) + next_node = (current_node - dim_product + dim_product * cur_dim); + else + next_node = (current_node - dim_product); + + // HERE: We use *next* node for calculation (as opposed to current_node!) + nodeOffset = next_node * (linkCountPerNode_); + linkOffset = nodeOffset + j + (hasLoopback_ ? 1 : 0) + (hasLimiter_ ? 1 : 0); + use_lnk_up = false; + + assert(linkOffset >= 0); } + XBT_DEBUG("torus_get_route_and_latency - current_node: %i, next_node: %u, linkOffset is %i", current_node, + next_node, linkOffset); - std::pair info; + break; + } - if (hasLimiter_) { // limiter for sender - info = privateLinks_.at(nodeOffset + hasLoopback_); - route->link_list->push_back(info.first); - } + dim_product *= cur_dim; + } - info = privateLinks_.at(linkOffset); + std::pair info; - if (use_lnk_up == false) { - route->link_list->push_back(info.second); - if (lat) - *lat += info.second->latency(); - } else { - route->link_list->push_back(info.first); - if (lat) - *lat += info.first->latency(); - } - current_node = next_node; - next_node = 0; - } - free(myCoords); - free(targetCoords); + if (hasLimiter_) { // limiter for sender + info = privateLinks_.at(nodeOffset + hasLoopback_); + route->link_list->push_back(info.first); + } + + info = privateLinks_.at(linkOffset); - return; + if (use_lnk_up == false) { + route->link_list->push_back(info.second); + if (lat) + *lat += info.second->latency(); + } else { + route->link_list->push_back(info.first); + if (lat) + *lat += info.first->latency(); } + current_node = next_node; + next_node = 0; + } + free(myCoords); + free(targetCoords); -}}} // namespace + return; +} +} +} +} // namespace diff --git a/src/kernel/routing/TorusZone.hpp b/src/kernel/routing/TorusZone.hpp index d53af2ea76..052d7b081c 100644 --- a/src/kernel/routing/TorusZone.hpp +++ b/src/kernel/routing/TorusZone.hpp @@ -12,16 +12,18 @@ namespace simgrid { namespace kernel { namespace routing { - class XBT_PRIVATE AsClusterTorus : public AsCluster { - public: - explicit AsClusterTorus(As* father, const char* name); - ~AsClusterTorus() override; - void create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position) override; - void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency) override; - void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) override; - private: - xbt_dynar_t dimensions_ = nullptr; - }; +class XBT_PRIVATE AsClusterTorus : public AsCluster { +public: + explicit AsClusterTorus(As* father, const char* name); + ~AsClusterTorus() override; + void create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int rank, int position) override; + void getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg_t into, double* latency) override; + void parse_specific_arguments(sg_platf_cluster_cbarg_t cluster) override; -}}} +private: + xbt_dynar_t dimensions_ = nullptr; +}; +} +} +} #endif diff --git a/src/kernel/routing/VivaldiZone.cpp b/src/kernel/routing/VivaldiZone.cpp index 84bdcb39f5..df9854721e 100644 --- a/src/kernel/routing/VivaldiZone.cpp +++ b/src/kernel/routing/VivaldiZone.cpp @@ -7,8 +7,8 @@ #include -#include "src/kernel/routing/VivaldiZone.hpp" #include "src/kernel/routing/NetCard.hpp" +#include "src/kernel/routing/VivaldiZone.hpp" #include "src/surf/network_interface.hpp" XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_vivaldi, surf, "Routing part of surf"); diff --git a/src/kernel/routing/VivaldiZone.hpp b/src/kernel/routing/VivaldiZone.hpp index d757c9f55e..0998640236 100644 --- a/src/kernel/routing/VivaldiZone.hpp +++ b/src/kernel/routing/VivaldiZone.hpp @@ -13,7 +13,7 @@ namespace kernel { namespace routing { /* This extends cluster because each host has a private link */ -class XBT_PRIVATE AsVivaldi: public AsCluster { +class XBT_PRIVATE AsVivaldi : public AsCluster { public: explicit AsVivaldi(As* father, const char* name); diff --git a/src/surf/sg_platf.cpp b/src/surf/sg_platf.cpp index 442574b29f..3615da64f8 100644 --- a/src/surf/sg_platf.cpp +++ b/src/surf/sg_platf.cpp @@ -26,16 +26,16 @@ #include "src/surf/network_interface.hpp" #include "src/kernel/routing/ClusterZone.hpp" +#include "src/kernel/routing/DijkstraZone.hpp" #include "src/kernel/routing/DragonflyZone.hpp" +#include "src/kernel/routing/EmptyZone.hpp" #include "src/kernel/routing/FatTreeZone.hpp" -#include "src/kernel/routing/TorusZone.hpp" -#include "src/kernel/routing/DijkstraZone.hpp" #include "src/kernel/routing/FloydZone.hpp" #include "src/kernel/routing/FullZone.hpp" +#include "src/kernel/routing/NetCard.hpp" #include "src/kernel/routing/NetZoneImpl.hpp" -#include "src/kernel/routing/EmptyZone.hpp" +#include "src/kernel/routing/TorusZone.hpp" #include "src/kernel/routing/VivaldiZone.hpp" -#include "src/kernel/routing/NetCard.hpp" XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_parse); diff --git a/src/surf/surf_routing.hpp b/src/surf/surf_routing.hpp index 0db638b501..64b1b709ce 100644 --- a/src/surf/surf_routing.hpp +++ b/src/surf/surf_routing.hpp @@ -9,8 +9,8 @@ #include #include -#include "surf_interface.hpp" #include "src/kernel/routing/NetZoneImpl.hpp" +#include "surf_interface.hpp" #include #include -- 2.20.1