docs: Modify delivery order section and add an example program.
[charm.git] / doc / bignetsim / bignetsim.tex
1 \subsection{BigNetSim Design and Internals}
2 \begin{figure}[!t]
3 \centering  
4   \includegraphics[width=3.2in]{figures/detailedsim_newer}
5 {\sffamily\bfseries\small \caption{BigNetSim conceptual model\label{fig:detailedsim_model}}}
6 \end{figure}
7
8 This section focuses on the interconnection network simulation.
9 The entities that form an interconnection network are:
10 \begin{itemize}
11 \item {\it switch:} A switch decides the routing on a packet. Switches could be
12 input buffered or output buffered. The former are implemented as individual posers
13 per port of each switch while the latter are implemented as a poser per switch.
14 In an {\it Input Buffered (IB)} switch, a packet in a switch is stored at the input 
15 port until its next route is decided and leaves the switch if it finds 
16 available space on the next switch in the route.
17 While in an {\it Output Buffered (OB)} switch, a packet in a switch decides beforehand 
18 on the next route to take and is buffered at the output port until space is
19 available on the next switch along the route.
20 Switches are modeled in much detail. Ports, buffers and
21 virtual channels at ports to avoid head-of-the-line blocking are
22 modeled.  Hardware collectives are implemented on the switch to
23 enable broadcasts, multicasts and other collective operations
24 efficiently. These are configurable and can be used if the system
25 being simulated supports them. We also support configurable
26 strategies for arbitration, input virtual channel selection and output
27 virtual channel selection. The configurability of the switch
28 provides a flexible design, satisfying the requirements of
29 a large number of networks.
30
31 \item {\it network card:} Network cards packetize and unpacketize messages.
32 A NIC is implemented as two posers. The sending and receiving entities in a
33 NIC are implemented as separate posers. A NIC is attached to each node.
34 \item {\it channel:} These are modeled as posers and connect a NIC to a switch
35 or a switch to another switch.
36 \item {\it compute node:} Each compute node connects to a network interface card.
37 A compute node simulates execution of entry methods on it. It is also attached
38 to a message traffic generator, which is used when only an interconnection
39 network is being simulated. This traffic generator can generate any message
40 pattern on each of the compute nodes.
41 The traffic generator can send
42 point-to-point messages, reductions, multicasts, broadcasts and other
43 collective traffic.  It supports k-shift, ring, bit-transpose,
44 bit-reversal, bit-complement and uniform random traffic.
45 These are based on common communication patterns found in
46 real applications. The frequency of message generation is determined
47 by a uniform or Poisson distribution.
48 \end{itemize}
49
50
51 \subsection{Topology, Routing and Virtual Channel Selection}
52 Topology, Routing strategies and input and output virtual channel selection
53 strategies need to be decided for any inter-connection network. Once we
54 have all of these in place we can simulate an inter-connection network.
55
56 \subsubsection{Topology}
57 For every architecture one wants to design, a topology file has to written
58 which defines a few basic functions for that particular topology.
59 These are:
60
61 \function{void getNeighbours(int nodeid, int numP);}
62 \index{getNeighbours}
63 \desc{This is called initially for every switch and this populates the
64 data structure {\it next} in a switch which contains the connectivity
65 of that switch. The switch specified by {\it switch} has {\it numP} ports.}
66
67 \function{int getNext(int portid, int nodeid, int numP)}
68 \index{getNext}
69 \desc{Returns the index of the switch/node that is connected to the
70 switch {\it nodeid}, at {\it portid}. The number of ports this node has is {\it numP}.}
71
72 \function{int getNextChannel(int portid, int nodeid, int numP)}
73 \index{getNextChannel}
74 \desc{Returns the index of the channel that is connected to the
75 switch {\it nodeid}, at {\it portid}. The number of ports this node has is {\it numP}.}
76
77 \function{int getStartPort(int nodeid, int numP, int dest)}
78 \index{getStartPort}
79 \desc{Return the index of the port that is connected to this compute node from a switch}
80
81 \function{int getStartVc()}
82 \index{getStartVc}
83 \desc{Returns the index of the first virtual channel (mostly 0).}
84
85 \function{int getStartSwitch(int nodeid)}
86 \index{getStartSwitch}
87 \desc{Returns the index of the node/switch that is connected to the first port}
88
89 \function{int getStartNode()}
90 \index{getStartNode}
91 \desc{Returns the index of the first node. Each poser has a separate index, 
92 irrespective of the type of the poser.}
93
94 \function{int getEndNode()}
95 \index{getEndNode}
96 \desc{Returns the index of the last node.}
97
98
99 \subsubsection{Routing}
100 Routing strategy needs to be specified for every interconnection network.
101 There is usually at least one routing strategy that needs to be defined
102 for every topology, Usually we have many more. The following functions need
103 to be defined for every routing strategy.
104
105 \function{int selectRoute(int current, int dest, int numP, Topology* top, Packet *p, map<int,int> \&bufsize, unsigned short *xsubi)}
106 \index{selectRoute}
107 \desc{Returns the portid that should be taken on switch {\it current} if the destination
108 is {\it dest}. The number of ports on a switch is {\it numP}. We also pass the pointer 
109 to the topology and to the Packet.}
110
111 \function{int selectRoute(int current, int dest, int numP, Topology* top, Packet *p, map<int,int> \&bufsize, map<int,int> \&portContention, unsigned short *xsubi)}
112 \index{selectRouteCont}
113 \desc{Returns the portid that should be taken on switch {\it current} if the destination
114 is {\it dest}. The number of ports on a switch is {\it numP}. We also pass the pointer 
115 to the topology and to the Packet. {\it Bufsize} is the state of the ports in
116 a switch, i.e. how many buffers on each port are full, while {\it portContention}
117 is used to give priority to certain ports, when more options are available.}
118
119 \function{int expectedTime(int src, int dest, POSE\_TimeType ovt, POSE\_TimeType origOvt, int length, int *numHops)}
120 \index{expectedTime}
121 \desc{Returns the expected time for a packet to travel from {\it src} to {\it dest},
122 when the number of hops it will need to travel is {\it numHops}.}
123
124 \function{int convertOutputToInputPort(int id, Packet *p, int numP, int *next)}
125 \index{convertOutputToInputPort}
126 \desc{Translate this output port to input port on the switch this port is
127 connected to.}
128
129
130 \subsubsection{Input Virtual Channel Selection}
131 For every switch, we need to know the mechanism it uses to choose input virtual channel.
132 There are a few different input virtual channel selection strategies, and a switch
133 can choose among them. Each should implement the following function.
134
135 \function{int selectInputVc(map<int,int> \&availBuffer, map<int,int> \&request, map<int,vector<Header> > \&inBuffer, int globalVc, int curSwitch)}
136 \index{selectInputVc}
137 \desc{Returns the input virtual channel to be used depending on the strategy and
138 the input parameters.}
139
140
141 \subsubsection{Output Virtual Channel Selection}
142 For every switch, we need to know the mechanism it uses to choose output virtual channel.
143 There are a few different output virtual channel selection strategies, and a switch
144 can choose among them. Each should implement the following function.
145
146 \function{int selectOutputVc(map<int,int> \&bufsize, Packet *p, int unused)}
147 \index{selectOutputVc}
148 \desc{Returns the output virtual channel to be used depending on the strategy and
149 the input parameters.}
150