Line data    Source code

       1           1 : /**
       2             :  * @file lib/topology/topology.c
       3             :  *
       4             :  * @brief Topology library
       5             :  *
       6             :  * This library is allows models to setup and query different topologies.
       7             :  *
       8             :  * SPDX-FileCopyrightText: 2008-2021 HPDCS Group <rootsim@googlegroups.com>
       9             :  * SPDX-License-Identifier: GPL-3.0-only
      10             :  */
      11             : #include <lib/topology/topology.h>
      12             : 
      13             : #include <core/intrinsics.h>
      14             : #include <lib/lib_internal.h>
      15             : 
      16             : #include <math.h>
      17             : #include <memory.h>
      18             : 
      19           1 : __attribute((weak)) struct topology_settings_t topology_settings;
      20             : 
      21             : /// this is used to store the common characteristics of the topology
      22             : struct {
      23             :         lp_id_t regions_cnt;                    /**< the number of LPs involved in the topology */
      24             :         uint32_t edge;                          /**< the pre-computed edge length (if it makes sense for the current topology geometry) */
      25             :         enum _topology_geometry_t geometry;     /**< the topology geometry (see ROOT-Sim.h) */
      26           0 : } topology_global;
      27             : 
      28             : /**
      29             :  * Initialize the topology module for each LP hosted on the machine.
      30             :  * This needs to be called right after LP basic initialization before starting to process events.
      31             :  */
      32           1 : void topology_global_init(void)
      33             : {
      34             :         if (!topology_settings.default_geometry &&
      35             :                 !topology_settings.out_of_topology)
      36             :                 // the strong symbol isn't defined: we aren't needed
      37             :                 return;
      38             : 
      39             :         // set default values
      40             :         const lp_id_t regions_cnt = n_lps - topology_settings.out_of_topology;
      41             :         topology_global.regions_cnt = regions_cnt;
      42             :         topology_global.geometry = topology_settings.default_geometry;
      43             :         // compute the edge value for topologies it makes sense for
      44             :         unsigned edge;
      45             : 
      46             :         switch (topology_global.geometry) {
      47             :                 case TOPOLOGY_SQUARE:
      48             :                 case TOPOLOGY_HEXAGON:
      49             :                 case TOPOLOGY_TORUS:
      50             :                         edge = sqrt(regions_cnt);
      51             :                         // we make sure there are no "lonely" LPs
      52             :                         if (edge * edge != regions_cnt) {
      53             :                                 log_log(LOG_FATAL, "Invalid number of regions for this topology geometry (must be a square number)\n");
      54             :                                 exit(-1);
      55             :                         }
      56             :                         break;
      57             :                 default:
      58             :                         // the edge value is actually unused
      59             :                         edge = 0;
      60             :                         break;
      61             :         }
      62             :         // set the edge value
      63             :         topology_global.edge = edge;
      64             : }
      65             : 
      66           0 : __attribute__ ((pure)) lp_id_t RegionsCount(void)
      67             : {
      68             :         return topology_global.regions_cnt;
      69             : }
      70             : 
      71           0 : __attribute__ ((pure)) lp_id_t DirectionsCount(void)
      72             : {
      73             :         switch (topology_global.geometry) {
      74             :         case TOPOLOGY_MESH:
      75             :                 return topology_global.regions_cnt - 1;
      76             :         case TOPOLOGY_HEXAGON:
      77             :                 return 6;
      78             :         case TOPOLOGY_TORUS:
      79             :         case TOPOLOGY_SQUARE:
      80             :                 return 4;
      81             :         case TOPOLOGY_STAR:
      82             :                 return 2;
      83             :         case TOPOLOGY_RING:
      84             :                 return 1;
      85             :         case TOPOLOGY_BIDRING:
      86             :                 return 2;
      87             :         }
      88             :         return UINT_MAX;
      89             : }
      90             : 
      91           0 : __attribute__ ((pure)) lp_id_t GetReceiver(lp_id_t from,
      92             :                                             enum _direction_t direction)
      93             : {
      94             :         const lp_id_t sender = from;
      95             :         const uint32_t edge = topology_global.edge;
      96             :         const lp_id_t regions_cnt = topology_global.regions_cnt;
      97             :         unsigned x, y;
      98             : 
      99             :         if (unlikely(regions_cnt <= from))
     100             :                 return DIRECTION_INVALID;
     101             : 
     102             :         switch (topology_global.geometry) {
     103             : 
     104             :         case TOPOLOGY_HEXAGON:
     105             :                 y = sender / edge;
     106             :                 x = sender - y * edge;
     107             : 
     108             :                 switch (direction) {
     109             :                 case DIRECTION_NW:
     110             :                         x += (y & 1U) - 1;
     111             :                         y -= 1;
     112             :                         break;
     113             :                 case DIRECTION_NE:
     114             :                         x += (y & 1U);
     115             :                         y -= 1;
     116             :                         break;
     117             :                 case DIRECTION_SW:
     118             :                         x += (y & 1U) - 1;
     119             :                         y += 1;
     120             :                         break;
     121             :                 case DIRECTION_SE:
     122             :                         x += (y & 1U);
     123             :                         y += 1;
     124             :                         break;
     125             :                 case DIRECTION_E:
     126             :                         x += 1;
     127             :                         break;
     128             :                 case DIRECTION_W:
     129             :                         x -= 1;
     130             :                         break;
     131             :                 default:
     132             :                         return DIRECTION_INVALID;
     133             :                 }
     134             :                 return (x < edge && y < edge) ? y * edge + x : DIRECTION_INVALID;
     135             : 
     136             :         case TOPOLOGY_SQUARE:
     137             :                 y = sender / edge;
     138             :                 x = sender - y * edge;
     139             : 
     140             :                 switch (direction) {
     141             :                 case DIRECTION_N:
     142             :                         y -= 1;
     143             :                         break;
     144             :                 case DIRECTION_S:
     145             :                         y += 1;
     146             :                         break;
     147             :                 case DIRECTION_E:
     148             :                         x += 1;
     149             :                         break;
     150             :                 case DIRECTION_W:
     151             :                         x -= 1;
     152             :                         break;
     153             :                 default:
     154             :                         return DIRECTION_INVALID;
     155             :                 }
     156             :                 return (x < edge && y < edge) ? y * edge + x : DIRECTION_INVALID;
     157             : 
     158             :         case TOPOLOGY_TORUS:
     159             :                 y = sender / edge;
     160             :                 x = sender - y * edge;
     161             : 
     162             :                 switch (direction) {
     163             :                 case DIRECTION_N:
     164             :                         y += edge - 1;
     165             :                         y %= edge;
     166             :                         break;
     167             :                 case DIRECTION_S:
     168             :                         y += 1;
     169             :                         y %= edge;
     170             :                         break;
     171             :                 case DIRECTION_E:
     172             :                         x += 1;
     173             :                         x %= edge;
     174             :                         break;
     175             :                 case DIRECTION_W:
     176             :                         x += edge - 1;
     177             :                         x %= edge;
     178             :                         break;
     179             :                 default:
     180             :                         return DIRECTION_INVALID;
     181             :                 }
     182             :                 return y * edge + x;
     183             : 
     184             :         case TOPOLOGY_MESH:
     185             :                 return likely((lp_id_t)direction < regions_cnt) ? direction : DIRECTION_INVALID;
     186             : 
     187             :         case TOPOLOGY_BIDRING:
     188             :                 switch (direction) {
     189             :                         case DIRECTION_N:
     190             :                                 return (sender + 1) % regions_cnt;
     191             :                         case DIRECTION_S:
     192             :                                 return (sender + regions_cnt - 1) % regions_cnt;
     193             :                         default:
     194             :                                 return DIRECTION_INVALID;
     195             :                 }
     196             :         case TOPOLOGY_RING:
     197             :                 return likely(direction == DIRECTION_N) ? direction : DIRECTION_INVALID;
     198             : 
     199             :         case TOPOLOGY_STAR:
     200             :                 if(sender) {
     201             :                         if(!direction)
     202             :                                 return 0;
     203             :                 } else {
     204             :                         if((uint64_t)direction + 1 < regions_cnt)
     205             :                                 return direction + 1;
     206             :                 }
     207             :         }
     208             :         return DIRECTION_INVALID;
     209             : }
     210             : 
     211           0 : lp_id_t FindReceiver(void)
     212             : {
     213             :         const lp_id_t dir_cnt = DirectionsCount();
     214             :         const unsigned bits = 64 - intrinsics_clz(dir_cnt);
     215             :         uint64_t rnd = RandomU64();
     216             :         unsigned i = 64;
     217             :         do {
     218             :                 lp_id_t dir = rnd & ((UINT64_C(1) << bits) - 1);
     219             :                 if (dir < dir_cnt) {
     220             :                         dir += 2 * (topology_global.geometry == TOPOLOGY_HEXAGON);
     221             :                         const lp_id_t ret = GetReceiver(lp_id_get(), dir);
     222             :                         if (ret != DIRECTION_INVALID)
     223             :                                 return ret;
     224             :                 }
     225             : 
     226             :                 if (likely((i -= bits) >= bits)) {
     227             :                         rnd >>= bits;
     228             :                 } else {
     229             :                         rnd = RandomU64();
     230             :                         i = 64;
     231             :                 }
     232             :         } while(1);
     233             : }