bignetsim manual separated from bigsim manual
authorAbhinav Bhatele <bhatele@illinois.edu>
Mon, 23 Feb 2009 19:15:50 +0000 (19:15 +0000)
committerAbhinav Bhatele <bhatele@illinois.edu>
Mon, 23 Feb 2009 19:15:50 +0000 (19:15 +0000)
doc/bignetsim/Makefile [new file with mode: 0644]
doc/bignetsim/bignetsim.tex [new file with mode: 0644]
doc/bignetsim/manual.tex [new file with mode: 0644]
doc/bignetsim/title.html [new file with mode: 0644]

diff --git a/doc/bignetsim/Makefile b/doc/bignetsim/Makefile
new file mode 100644 (file)
index 0000000..71f0dcb
--- /dev/null
@@ -0,0 +1,11 @@
+# Stub makefile for LaTeX PPL manual
+FILE   = manual
+TEX    = $(FILE).tex bignetsim.tex
+
+DEST   = bignetsim
+LATEX2HTML     = $(L2H) -split 5
+
+include ../Makefile.common
+
+index.tex:
+       touch index.tex
diff --git a/doc/bignetsim/bignetsim.tex b/doc/bignetsim/bignetsim.tex
new file mode 100644 (file)
index 0000000..a463b43
--- /dev/null
@@ -0,0 +1,266 @@
+\section{BigSim Network Simulator}
+\label{bignetsim}
+
+The BigSim Network Simulator is also known as Bigsimulator and lives 
+in the SVN repository https://charm.cs.uiuc.edu/svn/repos/BigNetSim. 
+The Network simulator is actually more of an Inter-connection network 
+simulator and hence more important in the context of large parallel
+machines with interconnects. 
+The BigSim simulator  along with the network simulator is together 
+also known as BigNetSim.
+
+Both the simulators run on top of the POSE framework, which is a Parallel
+Discrete Event Simulation framework built on top of \charmpp{}.
+
+
+\subsection{What does this software do?}
+BigNetSim is an effort to simulate large current and future computer 
+systems to study the behavior of applications developed for those systems. 
+BigNetSim could be used to study
+\begin{itemize}
+\item  new types of interconnection topologies and routing algorithms 
+along with different types of switching architecture.
+\item application performance on different machines. This uses the API
+provided in Section \ref{bgapi} to run the application on some number
+of processors on some machine and generate (dump) all events (entry
+method executions or message send/recv).  BigNetSim is used to 
+model the machine that needs to be studied for this application and
+these logs are then fed into this simulation, and it predicts the
+performance of this application.
+\end{itemize}
+
+So, the two important uses are studying {\it interconnection networks} and
+{\it performance prediction for applications}.
+
+
+\subsection{BigNetSim Design and Internals}
+\begin{figure}[!t]
+\centering  
+  \includegraphics[width=3.2in]{figures/detailedsim_newer}
+{\sffamily\bfseries\small \caption{BigNetSim conceptual model\label{fig:detailedsim_model}}}
+\end{figure}
+
+This section focuses on the interconnection network simulation.
+The entities that form an interconnection network are:
+\begin{itemize}
+\item {\it switch:} A switch decides the routing on a packet. Switches could be
+input buffered or output buffered. The former are implemented as individual posers
+per port of each switch while the latter are implemented as a poser per switch.
+In an {\it Input Buffered (IB)} switch, a packet in a switch is stored at the input 
+port until its next route is decided and leaves the switch if it finds 
+available space on the next switch in the route.
+While in an {\it Output Buffered (OB)} switch, a packet in a switch decides beforehand 
+on the next route to take and is buffered at the output port until space is
+available on the next switch along the route.
+Switches are modeled in much detail. Ports, buffers and
+virtual channels at ports to avoid head-of-the-line blocking are
+modeled.  Hardware collectives are implemented on the switch to
+enable broadcasts, multicasts and other collective operations
+efficiently. These are configurable and can be used if the system
+being simulated supports them. We also support configurable
+strategies for arbitration, input virtual channel selection and output
+virtual channel selection. The configurability of the switch
+provides a flexible design, satisfying the requirements of
+a large number of networks.
+
+\item {\it network card:} Network cards packetize and unpacketize messages.
+A NIC is implemented as two posers. The sending and receiving entities in a
+NIC are implemented as separate posers. A NIC is attached to each node.
+\item {\it channel:} These are modeled as posers and connect a NIC to a switch
+or a switch to another switch.
+\item {\it compute node:} Each compute node connects to a network interface card.
+A compute node simulates execution of entry methods on it. It is also attached
+to a message traffic generator, which is used when only an interconnection
+network is being simulated. This traffic generator can generate any message
+pattern on each of the compute nodes.
+The traffic generator can send
+point-to-point messages, reductions, multicasts, broadcasts and other
+collective traffic.  It supports k-shift, ring, bit-transpose,
+bit-reversal, bit-complement and uniform random traffic.
+These are based on common communication patterns found in
+real applications. The frequency of message generation is determined
+by a uniform or Poisson distribution.
+\end{itemize}
+
+
+\subsection{Topology, Routing and Virtual Channel Selection}
+Topology, Routing strategies and input and output virtual channel selection
+strategies need to be decided for any inter-connection network. Once we
+have all of these in place we can simulate an inter-connection network.
+
+\subsubsection{Topology}
+For every architecture one wants to design, a topology file has to written
+which defines a few basic functions for that particular topology.
+These are:
+
+\function{void getNeighbours(int nodeid, int numP);}
+\index{getNeighbours}
+\desc{This is called initially for every switch and this populates the
+data structure {\it next} in a switch which contains the connectivity
+of that switch. The switch specified by {\it switch} has {\it numP} ports.}
+
+\function{int getNext(int portid, int nodeid, int numP)}
+\index{getNext}
+\desc{Returns the index of the switch/node that is connected to the
+switch {\it nodeid}, at {\it portid}. The number of ports this node has is {\it numP}.}
+
+\function{int getNextChannel(int portid, int nodeid, int numP)}
+\index{getNextChannel}
+\desc{Returns the index of the channel that is connected to the
+switch {\it nodeid}, at {\it portid}. The number of ports this node has is {\it numP}.}
+
+\function{int getStartPort(int nodeid, int numP, int dest)}
+\index{getStartPort}
+\desc{Return the index of the port that is connected to this compute node from a switch}
+
+\function{int getStartVc()}
+\index{getStartVc}
+\desc{Returns the index of the first virtual channel (mostly 0).}
+
+\function{int getStartSwitch(int nodeid)}
+\index{getStartSwitch}
+\desc{Returns the index of the node/switch that is connected to the first port}
+
+\function{int getStartNode()}
+\index{getStartNode}
+\desc{Returns the index of the first node. Each poser has a separate index, 
+irrespective of the type of the poser.}
+
+\function{int getEndNode()}
+\index{getEndNode}
+\desc{Returns the index of the last node.}
+
+
+\subsubsection{Routing}
+Routing strategy needs to be specified for every interconnection network.
+There is usually at least one routing strategy that needs to be defined
+for every topology, Usually we have many more. The following functions need
+to be defined for every routing strategy.
+
+\function{int selectRoute(int current, int dest, int numP, Topology* top, Packet *p, map<int,int> \&bufsize, unsigned short *xsubi)}
+\index{selectRoute}
+\desc{Returns the portid that should be taken on switch {\it current} if the destination
+is {\it dest}. The number of ports on a switch is {\it numP}. We also pass the pointer 
+to the topology and to the Packet.}
+
+\function{int selectRoute(int current, int dest, int numP, Topology* top, Packet *p, map<int,int> \&bufsize, map<int,int> \&portContention, unsigned short *xsubi)}
+\index{selectRouteCont}
+\desc{Returns the portid that should be taken on switch {\it current} if the destination
+is {\it dest}. The number of ports on a switch is {\it numP}. We also pass the pointer 
+to the topology and to the Packet. {\it Bufsize} is the state of the ports in
+a switch, i.e. how many buffers on each port are full, while {\it portContention}
+is used to give priority to certain ports, when more options are available.}
+
+\function{int expectedTime(int src, int dest, POSE\_TimeType ovt, POSE\_TimeType origOvt, int length, int *numHops)}
+\index{expectedTime}
+\desc{Returns the expected time for a packet to travel from {\it src} to {\it dest},
+when the number of hops it will need to travel is {\it numHops}.}
+
+\function{int convertOutputToInputPort(int id, Packet *p, int numP, int *next)}
+\index{convertOutputToInputPort}
+\desc{Translate this output port to input port on the switch this port is
+connected to.}
+
+
+\subsubsection{Input Virtual Channel Selection}
+For every switch, we need to know the mechanism it uses to choose input virtual channel.
+There are a few different input virtual channel selection strategies, and a switch
+can choose among them. Each should implement the following function.
+
+\function{int selectInputVc(map<int,int> \&availBuffer, map<int,int> \&request, map<int,vector<Header> > \&inBuffer, int globalVc, int curSwitch)}
+\index{selectInputVc}
+\desc{Returns the input virtual channel to be used depending on the strategy and
+the input parameters.}
+
+
+\subsubsection{Output Virtual Channel Selection}
+For every switch, we need to know the mechanism it uses to choose output virtual channel.
+There are a few different output virtual channel selection strategies, and a switch
+can choose among them. Each should implement the following function.
+
+\function{int selectOutputVc(map<int,int> \&bufsize, Packet *p, int unused)}
+\index{selectOutputVc}
+\desc{Returns the output virtual channel to be used depending on the strategy and
+the input parameters.}
+
+
+\subsection{Which Interconnection networks are implemented?}
+A large number of topologies and routing strategies are implemented in the
+software. Here, we present a list of interconnection networks. For a complete list of
+routing strategies, input/output VC selectors, refer to the corresponding 
+directories in the software.
+\begin{itemize}
+\item HyperCube
+\item FatTree
+\item DenseGraph
+\item Three dimensional Mesh
+\item K-ary-N-cube
+\item K-ary-N-fly
+\item K-ary-N-mesh
+\item K-ary-N-tree
+\item N-mesh
+\item Hybrid of Fattree and Dense Graph
+\item Hybrid of Fattree and HyperCube
+\end{itemize}
+
+
+\subsection{Using the software}
+
+BigNetSim has 2 major modes.  
+
+\begin{itemize}
+\item{ Trace based traffic simulation }
+\item{Artificial traffic generation based simulation.
+The mode of the simulator is governed by the $USE\_TRANSCEIVER$ parameter
+in the netconfig file.  When set to 0, trace based simulation is used,
+when set to 1, traffic generation is used.}
+\end{itemize}
+
+Trace based simulation.  This is used to study target application
+performance, or detailed network performance when loaded by a specific
+application.
+
+There are two command line parameters for traced based simulation.
+\begin{alltt}./bigsimulator arg1 arg2\end{alltt}
+\begin{alltt}
+       arg1 = 0 => Latency only mode
+              1 => Detailed contention model
+       arg2 = N => starts execution at the time marked by skip point N (0 is start) 
+\end{alltt}
+
+Artificial traffic generation based simulation is use to study the performance of interconnects under standard network load schemes.
+
+
+\begin{alltt}./bigsimulator arg1 arg2 arg3 arg4 arg5 arg6\end{alltt}
+example
+\begin{alltt}./bigsimulator 1 2 3 100 2031 0.1\end{alltt}
+
+\begin{alltt}
+       arg1 = 0 => Latency only mode
+              1 => Detailed contention model
+       arg2 = 1 => deterministic traffic
+              2 => poisson traffic
+       arg3 = 1 => KSHIFT 
+              2 => RING 
+              3 => BITTRANSPOSE 
+              4 => BITREVERSAL 
+              5 => BITCOMPLEMENT 
+              6 => UNIFORM\_DISTRIBUTION 
+       arg4 = number of packets
+       arg5 = message size
+       arg6 = load factor
+\end{alltt}
+
+\subsection{Build your own Interconnection network}
+To build a new interconnection network, one has to create a new directory
+for that interconnection network and then create the routing strategy,
+topology, input virtual channel selection and output virtual channel selection
+strategies for that network. If existing strategies could be used, then
+reuse them, but if new ones are required, one has to write these new
+strategies in the corresponding directories for routing, topology, etc.
+
+The InitNetwork function must be provided in InitNetwork.C for this 
+new interconnection network. It builds up all the nodes and 
+switches and NICs and channels that form the network. Look at one
+of the existing interconnection topologies for reference.
+
diff --git a/doc/bignetsim/manual.tex b/doc/bignetsim/manual.tex
new file mode 100644 (file)
index 0000000..361e6c0
--- /dev/null
@@ -0,0 +1,15 @@
+\documentclass[10pt]{article}
+\usepackage{../pplmanual}
+\input{../pplmanual}
+
+\title{BigSimulator (BigNetSim) for Extremely Large Parallel Machines}
+
+\begin{document}
+\maketitle
+
+\input{bignetsim}
+
+\input{index}
+
+\end{document}
+
diff --git a/doc/bignetsim/title.html b/doc/bignetsim/title.html
new file mode 100644 (file)
index 0000000..f1c39ed
--- /dev/null
@@ -0,0 +1 @@
+BigSimulator (BigNetSim) Parallel Simulator Manual