fixed errors
[charm.git] / doc / bignetsim / bignetsim.tex
1 \section{BigSim Network Simulator}
2 \label{bignetsim}
3
4 The BigSim Network Simulator is also known as Bigsimulator and lives 
5 in the SVN repository https://charm.cs.uiuc.edu/svn/repos/BigNetSim. 
6 The Network simulator is actually more of an Inter-connection network 
7 simulator and hence more important in the context of large parallel
8 machines with interconnects. 
9 The BigSim simulator  along with the network simulator is together 
10 also known as BigNetSim.
11
12 Both the simulators run on top of the POSE framework, which is a Parallel
13 Discrete Event Simulation framework built on top of \charmpp{}.
14
15
16 \subsection{What does this software do?}
17 BigNetSim is an effort to simulate large current and future computer 
18 systems to study the behavior of applications developed for those systems. 
19 BigNetSim could be used to study
20 \begin{itemize}
21 \item  new types of interconnection topologies and routing algorithms 
22 along with different types of switching architecture.
23 \item application performance on different machines. This uses the API
24 provided in Section \ref{bgapi} to run the application on some number
25 of processors on some machine and generate (dump) all events (entry
26 method executions or message send/recv).  BigNetSim is used to 
27 model the machine that needs to be studied for this application and
28 these logs are then fed into this simulation, and it predicts the
29 performance of this application.
30 \end{itemize}
31
32 So, the two important uses are studying {\it interconnection networks} and
33 {\it performance prediction for applications}.
34
35
36 \subsection{BigNetSim Design and Internals}
37 \begin{figure}[!t]
38 \centering  
39   \includegraphics[width=3.2in]{figures/detailedsim_newer}
40 {\sffamily\bfseries\small \caption{BigNetSim conceptual model\label{fig:detailedsim_model}}}
41 \end{figure}
42
43 This section focuses on the interconnection network simulation.
44 The entities that form an interconnection network are:
45 \begin{itemize}
46 \item {\it switch:} A switch decides the routing on a packet. Switches could be
47 input buffered or output buffered. The former are implemented as individual posers
48 per port of each switch while the latter are implemented as a poser per switch.
49 In an {\it Input Buffered (IB)} switch, a packet in a switch is stored at the input 
50 port until its next route is decided and leaves the switch if it finds 
51 available space on the next switch in the route.
52 While in an {\it Output Buffered (OB)} switch, a packet in a switch decides beforehand 
53 on the next route to take and is buffered at the output port until space is
54 available on the next switch along the route.
55 Switches are modeled in much detail. Ports, buffers and
56 virtual channels at ports to avoid head-of-the-line blocking are
57 modeled.  Hardware collectives are implemented on the switch to
58 enable broadcasts, multicasts and other collective operations
59 efficiently. These are configurable and can be used if the system
60 being simulated supports them. We also support configurable
61 strategies for arbitration, input virtual channel selection and output
62 virtual channel selection. The configurability of the switch
63 provides a flexible design, satisfying the requirements of
64 a large number of networks.
65
66 \item {\it network card:} Network cards packetize and unpacketize messages.
67 A NIC is implemented as two posers. The sending and receiving entities in a
68 NIC are implemented as separate posers. A NIC is attached to each node.
69 \item {\it channel:} These are modeled as posers and connect a NIC to a switch
70 or a switch to another switch.
71 \item {\it compute node:} Each compute node connects to a network interface card.
72 A compute node simulates execution of entry methods on it. It is also attached
73 to a message traffic generator, which is used when only an interconnection
74 network is being simulated. This traffic generator can generate any message
75 pattern on each of the compute nodes.
76 The traffic generator can send
77 point-to-point messages, reductions, multicasts, broadcasts and other
78 collective traffic.  It supports k-shift, ring, bit-transpose,
79 bit-reversal, bit-complement and uniform random traffic.
80 These are based on common communication patterns found in
81 real applications. The frequency of message generation is determined
82 by a uniform or Poisson distribution.
83 \end{itemize}
84
85
86 \subsection{Topology, Routing and Virtual Channel Selection}
87 Topology, Routing strategies and input and output virtual channel selection
88 strategies need to be decided for any inter-connection network. Once we
89 have all of these in place we can simulate an inter-connection network.
90
91 \subsubsection{Topology}
92 For every architecture one wants to design, a topology file has to written
93 which defines a few basic functions for that particular topology.
94 These are:
95
96 \function{void getNeighbours(int nodeid, int numP);}
97 \index{getNeighbours}
98 \desc{This is called initially for every switch and this populates the
99 data structure {\it next} in a switch which contains the connectivity
100 of that switch. The switch specified by {\it switch} has {\it numP} ports.}
101
102 \function{int getNext(int portid, int nodeid, int numP)}
103 \index{getNext}
104 \desc{Returns the index of the switch/node that is connected to the
105 switch {\it nodeid}, at {\it portid}. The number of ports this node has is {\it numP}.}
106
107 \function{int getNextChannel(int portid, int nodeid, int numP)}
108 \index{getNextChannel}
109 \desc{Returns the index of the channel that is connected to the
110 switch {\it nodeid}, at {\it portid}. The number of ports this node has is {\it numP}.}
111
112 \function{int getStartPort(int nodeid, int numP, int dest)}
113 \index{getStartPort}
114 \desc{Return the index of the port that is connected to this compute node from a switch}
115
116 \function{int getStartVc()}
117 \index{getStartVc}
118 \desc{Returns the index of the first virtual channel (mostly 0).}
119
120 \function{int getStartSwitch(int nodeid)}
121 \index{getStartSwitch}
122 \desc{Returns the index of the node/switch that is connected to the first port}
123
124 \function{int getStartNode()}
125 \index{getStartNode}
126 \desc{Returns the index of the first node. Each poser has a separate index, 
127 irrespective of the type of the poser.}
128
129 \function{int getEndNode()}
130 \index{getEndNode}
131 \desc{Returns the index of the last node.}
132
133
134 \subsubsection{Routing}
135 Routing strategy needs to be specified for every interconnection network.
136 There is usually at least one routing strategy that needs to be defined
137 for every topology, Usually we have many more. The following functions need
138 to be defined for every routing strategy.
139
140 \function{int selectRoute(int current, int dest, int numP, Topology* top, Packet *p, map<int,int> \&bufsize, unsigned short *xsubi)}
141 \index{selectRoute}
142 \desc{Returns the portid that should be taken on switch {\it current} if the destination
143 is {\it dest}. The number of ports on a switch is {\it numP}. We also pass the pointer 
144 to the topology and to the Packet.}
145
146 \function{int selectRoute(int current, int dest, int numP, Topology* top, Packet *p, map<int,int> \&bufsize, map<int,int> \&portContention, unsigned short *xsubi)}
147 \index{selectRouteCont}
148 \desc{Returns the portid that should be taken on switch {\it current} if the destination
149 is {\it dest}. The number of ports on a switch is {\it numP}. We also pass the pointer 
150 to the topology and to the Packet. {\it Bufsize} is the state of the ports in
151 a switch, i.e. how many buffers on each port are full, while {\it portContention}
152 is used to give priority to certain ports, when more options are available.}
153
154 \function{int expectedTime(int src, int dest, POSE\_TimeType ovt, POSE\_TimeType origOvt, int length, int *numHops)}
155 \index{expectedTime}
156 \desc{Returns the expected time for a packet to travel from {\it src} to {\it dest},
157 when the number of hops it will need to travel is {\it numHops}.}
158
159 \function{int convertOutputToInputPort(int id, Packet *p, int numP, int *next)}
160 \index{convertOutputToInputPort}
161 \desc{Translate this output port to input port on the switch this port is
162 connected to.}
163
164
165 \subsubsection{Input Virtual Channel Selection}
166 For every switch, we need to know the mechanism it uses to choose input virtual channel.
167 There are a few different input virtual channel selection strategies, and a switch
168 can choose among them. Each should implement the following function.
169
170 \function{int selectInputVc(map<int,int> \&availBuffer, map<int,int> \&request, map<int,vector<Header> > \&inBuffer, int globalVc, int curSwitch)}
171 \index{selectInputVc}
172 \desc{Returns the input virtual channel to be used depending on the strategy and
173 the input parameters.}
174
175
176 \subsubsection{Output Virtual Channel Selection}
177 For every switch, we need to know the mechanism it uses to choose output virtual channel.
178 There are a few different output virtual channel selection strategies, and a switch
179 can choose among them. Each should implement the following function.
180
181 \function{int selectOutputVc(map<int,int> \&bufsize, Packet *p, int unused)}
182 \index{selectOutputVc}
183 \desc{Returns the output virtual channel to be used depending on the strategy and
184 the input parameters.}
185
186
187 \subsection{Which Interconnection networks are implemented?}
188 A large number of topologies and routing strategies are implemented in the
189 software. Here, we present a list of interconnection networks. For a complete
190 list of routing strategies, input/output VC selectors, refer to the
191 corresponding directories in the software.
192
193 \begin{itemize}
194 \item HyperCube
195 \item FatTree
196 \item DenseGraph
197 \item Three dimensional Mesh
198 \item K-ary-N-cube
199 \item K-ary-N-fly
200 \item K-ary-N-mesh
201 \item K-ary-N-tree
202 \item N-mesh
203 \item Hybrid of Fattree and Dense Graph
204 \item Hybrid of Fattree and HyperCube
205 \end{itemize}
206
207
208 \subsection{Using the software}
209
210 BigNetSim has 2 major modes.  
211
212 \begin{itemize}
213 \item{ Trace based traffic simulation }
214 \item{Artificial traffic generation based simulation.
215 The mode of the simulator is governed by the $USE\_TRANSCEIVER$ parameter
216 in the netconfig file.  When set to 0, trace based simulation is used,
217 when set to 1, traffic generation is used.}
218 \end{itemize}
219
220 Trace based simulation.  This is used to study target application performance,
221 or detailed network performance when loaded by a specific application.
222
223 There are two command line parameters for traced based simulation.
224 \begin{alltt}./bigsimulator arg1 arg2\end{alltt}
225 \begin{alltt}
226         arg1 = 0 => Latency only mode
227                1 => Detailed contention model
228         arg2 = N => starts execution at the time marked by skip point N (0 is start) 
229 \end{alltt}
230
231 Artificial traffic generation based simulation is use to study the performance
232 of interconnects under standard network load schemes.
233
234
235 \begin{alltt}./bigsimulator arg1 arg2 arg3 arg4 arg5 arg6\end{alltt}
236 example
237 \begin{alltt}./bigsimulator 1 2 3 100 2031 0.1\end{alltt}
238
239 \begin{alltt}
240         arg1 = 0 => Latency only mode
241                1 => Detailed contention model
242         arg2 = 1 => deterministic traffic
243                2 => poisson traffic
244         arg3 = 1 => KSHIFT 
245                2 => RING 
246                3 => BITTRANSPOSE 
247                4 => BITREVERSAL 
248                5 => BITCOMPLEMENT 
249                6 => UNIFORM\_DISTRIBUTION 
250         arg4 = number of packets
251         arg5 = message size
252         arg6 = load factor
253 \end{alltt}
254
255 \subsection{Build your own Interconnection network}
256 To build a new interconnection network, one has to create a new directory for
257 that interconnection network and then create the routing strategy, topology,
258 input virtual channel selection and output virtual channel selection strategies
259 for that network. If existing strategies could be used, then reuse them, but if
260 new ones are required, one has to write these new strategies in the
261 corresponding directories for routing, topology, etc.
262
263 The InitNetwork function must be provided in InitNetwork.C for this new
264 interconnection network. It builds up all the nodes and switches and NICs and
265 channels that form the network. Look at one of the existing interconnection
266 topologies for reference.
267