doc/bignetsim/manual.rst

   1 ========================
   2 BigSimulator (BigNetSim)
   3 ========================
   4
   5 .. contents::
   6    :depth: 3
   7
   8 .. _bignetsim:
   9
  10 BigSim Network Simulator
  11 ========================
  12
  13 The BigSim Network Simulator is also known as Bigsimulator and lives in
  14 the SVN repository https://charm.cs.uiuc.edu/svn/repos/BigNetSim. The
  15 Network simulator is actually more of an Inter-connection network
  16 simulator and hence more important in the context of large parallel
  17 machines with interconnects. The BigSim simulator along with the network
  18 simulator is together also known as BigNetSim.
  19
  20 Both the simulators run on top of the POSE framework, which is a
  21 Parallel Discrete Event Simulation framework built on top of Charm++.
  22
  23 What does this software do?
  24 ---------------------------
  25
  26 BigNetSim is an effort to simulate large current and future computer
  27 systems to study the behavior of applications developed for those
  28 systems. BigNetSim could be used to study
  29
  30 -  new types of interconnection topologies and routing algorithms along
  31    with different types of switching architecture.
  32
  33 -  application performance on different machines. This uses the API
  34    provided in Section :numref:`bgapi` to run the application on
  35    some number of processors on some machine and generate (dump) all
  36    events (entry method executions or message send/recv). BigNetSim is
  37    used to model the machine that needs to be studied for this
  38    application and these logs are then fed into this simulation, and it
  39    predicts the performance of this application.
  40
  41 So, the two important uses are studying *interconnection networks* and
  42 *performance prediction for applications*.
  43
  44 Compiling BigSimulator
  45 ----------------------
  46
  47 To compile the simulator which is called BigSimulator (or BigNetSim), we
  48 need the regular Charm++ build (netlrts-linux-x86_64 in our example). It
  49 needs to be complemented with a few more libraries from BigSim and with
  50 the Pose discrete-event simulator. These pieces can be built,
  51 respectively, with:
  52
  53 .. code-block:: bash
  54
  55    $ ./build bgampi netlrts-linux-x86_64 -O2
  56    $ ./build pose netlrts-linux-x86_64 -O2
  57
  58 Access to the discrete-event simulation is realized via a Charm++
  59 package originally named BigNetSim (now called BigSimulator). Assuming
  60 that the ’subversion’ (svn) package is available, this package can be
  61 obtained from the Web with a subversion checkout such as:
  62
  63 .. code-block:: bash
  64
  65    $ svn co https://charm.cs.uiuc.edu/svn/repos/BigNetSim/
  66
  67 In the subdir ’trunk/’ created by the checkout, the file Makefile.common
  68 must be edited so that ’CHARMBASE’ points to the regular Charm++
  69 installation. Having that done, one chooses a topology in that subdir
  70 (e.g. BlueGene for a torus topology) by doing a "cd" into the
  71 corresponding directory (e.g. ’cd BlueGene’). Inside that directory, one
  72 should simply "make". This will produce the binary
  73 "../tmp/bigsimulator". That file, together with file
  74 "BlueGene/netconfig.vc", will be used during a simulation. It may be
  75 useful to set the variable SEQUENTIAL to 1 in Makefile.common to build a
  76 sequential (non-parallel) version of bigsimulator.
  77
  78 Using BigSimulator
  79 ------------------
  80
  81 BigSimulator (BigNetSim) has 2 major modes.
  82
  83 -  Trace based traffic simulation
  84
  85 -  Artificial traffic generation based simulation. The mode of the
  86    simulator is governed by the :math:`USE\_TRANSCEIVER` parameter in
  87    the netconfig file. When set to 0, trace based simulation is used,
  88    when set to 1, traffic generation is used.
  89
  90 Trace based simulation. This is used to study target application
  91 performance, or detailed network performance when loaded by a specific
  92 application.
  93
  94 There are two command line parameters for traced based simulation.
  95
  96 .. code-block:: none
  97
  98      ./charmrun +p2 ./bigsimulator arg1 arg2
  99
 100 .. code-block:: none
 101
 102      arg1 = 0 => Latency only mode
 103             1 => Detailed contention model
 104      arg2 = N => starts execution at the time marked by skip point N (0 is start)
 105
 106 Simple Latency Model
 107 ~~~~~~~~~~~~~~~~~~~~
 108
 109 To use the simple latency model, follow the setup procedure above,
 110 noting that the files are located in the trunk/SimpleLatency directory.
 111 This will produce the "bigsimulator" file.
 112
 113 The command line parameters used for this model are different. The
 114 format is as follows:
 115
 116 .. code-block:: none
 117
 118      [charmrun +p#] bigsimulator -lat <latency> -bw <bandwidth>
 119                   [-cpp <cost per packet> -psize <packet size>]
 120                   [-winsize <window size>] [-skip] [-print_params]
 121
 122 .. code-block:: none
 123
 124      Latency (lat)         - type double; in microseconds
 125      Bandwidth (bw)        - type double; in GB/s
 126      Cost per packet (cpp) - type double; in microseconds
 127      Packet size (psize)   - type int; in bytes
 128      Window size (winsize) - type int; in log entries
 129
 130 The implemented equation is: :math:`lat + (N/bw) + cpp \times (N/psize)`
 131
 132 Latency and bandwidth are required. If cost per packet is given, then
 133 packet size must be given, as well. Otherwise, cost per packet defaults
 134 to 0.0. Packet size, if given, must be a positive integer.
 135
 136 The -winsize flag allows the user to specify the size of the window
 137 (number of log entries) used when reading in the bgTrace log files. This
 138 is useful if the log files are large. If -winsize is not specified, the
 139 value defaults to 0, which indicates that no windowing will be used
 140 (i.e., there will be one window for each time line that is equal to the
 141 size of the time line).
 142
 143 As with the second parameter in the examples of part (a) of this
 144 section, the -skip flag indicates that the simulation should skip
 145 forward to the time stamp set during trace creation (see the BigSim
 146 tutorial talk from the 2008 Charm++ workshop). If -skip is not included,
 147 then no skipping will occur.
 148
 149 The -print_params flag is provided for debugging convenience. When
 150 present, the simple latency model parameters will be displayed during
 151 simulation initialization.
 152
 153 Artificial Traffic Models
 154 ~~~~~~~~~~~~~~~~~~~~~~~~~
 155
 156 Artificial traffic generation based simulation is use to study the
 157 performance of interconnects under standard network load schemes.
 158
 159 .. code-block:: none
 160
 161      ./bigsimulator arg1 arg2 arg3 arg4 arg5 arg6
 162
 163 example
 164
 165 .. code-block:: none
 166
 167      ./bigsimulator 1 2 3 100 2031 0.1
 168
 169 .. code-block:: none
 170
 171      arg1 = 0 => Latency only mode
 172             1 => Detailed contention model
 173      arg2 = 1 => deterministic traffic
 174             2 => poisson traffic
 175      arg3 = 1 => KSHIFT
 176             2 => RING
 177             3 => BITTRANSPOSE
 178             4 => BITREVERSAL
 179             5 => BITCOMPLEMENT
 180             6 => UNIFORM_DISTRIBUTION
 181      arg4 = number of packets
 182      arg5 = message size
 183      arg6 = load factor
 184
 185 Which Interconnection networks are implemented?
 186 -----------------------------------------------
 187
 188 A large number of topologies and routing strategies are implemented in
 189 the software. Here, we present a list of interconnection networks. For a
 190 complete list of routing strategies, input/output VC selectors, refer to
 191 the corresponding directories in the software.
 192
 193 -  HyperCube
 194
 195 -  FatTree
 196
 197 -  DenseGraph
 198
 199 -  Three dimensional Mesh
 200
 201 -  K-ary-N-cube
 202
 203 -  K-ary-N-fly
 204
 205 -  K-ary-N-mesh
 206
 207 -  K-ary-N-tree
 208
 209 -  N-mesh
 210
 211 -  Hybrid of Fattree and Dense Graph
 212
 213 -  Hybrid of Fattree and HyperCube
 214
 215 Build your own Interconnection network
 216 --------------------------------------
 217
 218 To build a new interconnection network, one has to create a new
 219 directory for that interconnection network and then create the routing
 220 strategy, topology, input virtual channel selection and output virtual
 221 channel selection strategies for that network. If existing strategies
 222 could be used, then reuse them, but if new ones are required, one has to
 223 write these new strategies in the corresponding directories for routing,
 224 topology, etc.
 225
 226 The InitNetwork function must be provided in InitNetwork.C for this new
 227 interconnection network. It builds up all the nodes and switches and
 228 NICs and channels that form the network. Look at one of the existing
 229 interconnection topologies for reference.
 230
 231 BigNetSim Design and Internals
 232 ------------------------------
 233
 234 .. figure:: figures/detailedsim_newer.png
 235    :width: 3.2in
 236
 237    BigNetSim conceptual model
 238
 239 This section focuses on the interconnection network simulation. The
 240 entities that form an interconnection network are:
 241
 242 -  *switch:* A switch decides the routing on a packet. Switches could be
 243    input buffered or output buffered. The former are implemented as
 244    individual posers per port of each switch while the latter are
 245    implemented as a poser per switch. In an *Input Buffered (IB)*
 246    switch, a packet in a switch is stored at the input port until its
 247    next route is decided and leaves the switch if it finds available
 248    space on the next switch in the route. While in an *Output Buffered
 249    (OB)* switch, a packet in a switch decides beforehand on the next
 250    route to take and is buffered at the output port until space is
 251    available on the next switch along the route. Switches are modeled in
 252    much detail. Ports, buffers and virtual channels at ports to avoid
 253    head-of-the-line blocking are modeled. Hardware collectives are
 254    implemented on the switch to enable broadcasts, multicasts and other
 255    collective operations efficiently. These are configurable and can be
 256    used if the system being simulated supports them. We also support
 257    configurable strategies for arbitration, input virtual channel
 258    selection and output virtual channel selection. The configurability
 259    of the switch provides a flexible design, satisfying the requirements
 260    of a large number of networks.
 261
 262 -  *network card:* Network cards packetize and unpacketize messages. A
 263    NIC is implemented as two posers. The sending and receiving entities
 264    in a NIC are implemented as separate posers. A NIC is attached to
 265    each node.
 266
 267 -  *channel:* These are modeled as posers and connect a NIC to a switch
 268    or a switch to another switch.
 269
 270 -  *compute node:* Each compute node connects to a network interface
 271    card. A compute node simulates execution of entry methods on it. It
 272    is also attached to a message traffic generator, which is used when
 273    only an interconnection network is being simulated. This traffic
 274    generator can generate any message pattern on each of the compute
 275    nodes. The traffic generator can send point-to-point messages,
 276    reductions, multicasts, broadcasts and other collective traffic. It
 277    supports k-shift, ring, bit-transpose, bit-reversal, bit-complement
 278    and uniform random traffic. These are based on common communication
 279    patterns found in real applications. The frequency of message
 280    generation is determined by a uniform or Poisson distribution.
 281
 282 Topology, Routing and Virtual Channel Selection
 283 -----------------------------------------------
 284
 285 Topology, Routing strategies and input and output virtual channel
 286 selection strategies need to be decided for any inter-connection
 287 network. Once we have all of these in place we can simulate an
 288 inter-connection network.
 289
 290 Topology
 291 ~~~~~~~~
 292
 293 For every architecture one wants to design, a topology file has to
 294 written which defines a few basic functions for that particular
 295 topology. These are:
 296
 297 ``void getNeighbours(int nodeid, int numP)``
 298
 299 This is called initially for every switch and this populates the data
 300 structure next in a switch which contains the connectivity of that
 301 switch. The switch specified by switch has numP ports.
 302
 303 ``int getNext(int portid, int nodeid, int numP)``
 304
 305 Returns the index of the switch/node that is connected to the switch
 306 nodeid, at portid. The number of ports this node has is numP.
 307
 308 ``int getNextChannel(int portid, int nodeid, int numP)``
 309
 310 Returns the index of the channel that is connected to the switch nodeid,
 311 at portid. The number of ports this node has is numP.
 312
 313 ``int getStartPort(int nodeid, int numP, int dest)``
 314
 315 Return the index of the port that is connected to this compute node from
 316 a switch
 317
 318 ``int getStartVc()``
 319
 320 Returns the index of the first virtual channel (mostly 0).
 321
 322 ``int getStartSwitch(int nodeid)``
 323
 324 Returns the index of the node/switch that is connected to the first port
 325
 326 ``int getStartNode()``
 327
 328 Returns the index of the first node. Each poser has a separate index,
 329 irrespective of the type of the poser.
 330
 331 ``int getEndNode()``
 332
 333 Returns the index of the last node.
 334
 335 Routing
 336 ~~~~~~~
 337
 338 Routing strategy needs to be specified for every interconnection
 339 network. There is usually at least one routing strategy that needs to be
 340 defined for every topology, Usually we have many more. The following
 341 functions need to be defined for every routing strategy.
 342
 343 ``int selectRoute(int current, int dest, int numP, Topology* top, Packet
 344 *p, map<int,int> &bufsize, unsigned short *xsubi)``
 345
 346 Returns the portid that should be taken on switch current if the
 347 destination is dest. The number of ports on a switch is numP. We also
 348 pass the pointer to the topology and to the Packet.
 349
 350 ``int selectRoute(int current, int dest, int numP, Topology* top, Packet
 351 *p, map<int,int> &bufsize, map<int,int> &portContention, unsigned short
 352 *xsubi)``
 353
 354 Returns the portid that should be taken on switch current if the
 355 destination is dest. The number of ports on a switch is numP. We also
 356 pass the pointer to the topology and to the Packet. Bufsize is the state
 357 of the ports in a switch, i.e. how many buffers on each port are full,
 358 while portContention is used to give priority to certain ports, when
 359 more options are available.
 360
 361 ``int expectedTime(int src, int dest, POSE_TimeType ovt, POSE_TimeType
 362 origOvt, int length, int *numHops)``
 363
 364 Returns the expected time for a packet to travel from src to dest, when
 365 the number of hops it will need to travel is numHops.
 366
 367 ``int convertOutputToInputPort(int id, Packet *p, int numP, int *next)``
 368
 369 Translate this output port to input port on the switch this port is
 370 connected to.
 371
 372 Input Virtual Channel Selection
 373 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 374
 375 For every switch, we need to know the mechanism it uses to choose input
 376 virtual channel. There are a few different input virtual channel
 377 selection strategies, and a switch can choose among them. Each should
 378 implement the following function.
 379
 380 ``int selectInputVc(map<int,int> &availBuffer, map<int,int> &request,
 381 map<int,vector<Header> > &inBuffer, int globalVc, int curSwitch)``
 382
 383 Returns the input virtual channel to be used depending on the strategy
 384 and the input parameters.
 385
 386 Output Virtual Channel Selection
 387 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 388
 389 For every switch, we need to know the mechanism it uses to choose output
 390 virtual channel. There are a few different output virtual channel
 391 selection strategies, and a switch can choose among them. Each should
 392 implement the following function.
 393
 394 ``int selectOutputVc(map<int,int> &bufsize, Packet *p, int unused)``
 395
 396 Returns the output virtual channel to be used depending on the strategy
 397 and the input parameters.