build: fix travis MPI/SMP build
[charm.git] / 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.