*** empty log message ***
[charm.git] / doc / bigsim / bignetsim.tex
1 \section{BigSim Network Simulator}
2 \label{bignetsim}
3
4 The BigSim Network Simulator is also known as DetailedSim and lives 
5 in the pgms module in cvs at pose/DetailedSim. 
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 perfomrance 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 modelled 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 seclection
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{Retuns the index of the first virtual channel (mostly 0).}
119
120 \function{int getStartSwitch(int nodeid)}
121 \index{getStartSwitch}
122 \desc{Retuns 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{Retuns 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{Retuns 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{Retuns 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 list of
190 routing strategies, input/output VC selectors, refer to the corresponding 
191 directories in the software.
192 \begin{itemize}
193 \item HyperCube
194 \item FatTree
195 \item DenseGraph
196 \item Three dimensional Mesh
197 \item K-ary-N-cube
198 \item K-ary-N-fly
199 \item K-ary-N-mesh
200 \item K-ary-N-tree
201 \item N-mesh
202 \item Hybrid of Fattree and Dense Graph
203 \item Hybrid of Fattree and HyperCube
204 \end{itemize}
205
206
207 \subsection{Using the software}
208 Refer to the README file that comes in the directory containing the software.
209 It presents different schemes to use the software.
210
211
212 \subsection{Build your own Interconnection network}
213 To build a new interconnection network, one has to create a new directory
214 for that interconnection network and then create the routing strategy,
215 topology, input virtual channel selection and output virtual channel selection
216 strategies for that network. If existing strategies could be used, then
217 reuse them, but if new ones are required, one has to write these new
218 strategies in the corresponding directories for routing, topology, etc.
219
220 The InitNetwork function must be provided in InitNetwork.C for this 
221 new interconnection network. It builds up all the nodes and 
222 switches and NICs and channels that form the network. Look at one
223 of the existing interconnection topologies for reference.
224