codes-best-practices.tex 15.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

\documentclass[conference,10pt,compsocconf,onecolumn]{IEEEtran}
%\documentclass{acm_proc_article-sp}
%\documentclass{sig-alternate}
% Add the compsoc option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}

% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.
%
\usepackage{setspace}
\usepackage{wrapfig}
\usepackage{color}
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
\usepackage{listing}
\usepackage{listings}

\lstset{ %
frame=single,
language=C,
captionpos=b,
columns=fullflexible,
morekeywords={aesop,pwait,pbranch,pbreak},
numbers=left,
basicstyle=\scriptsize\ttfamily,
breaklines=true,
framexleftmargin=0em,
boxpos=c,
resetmargins=true,
xleftmargin=6ex
%basicstyle=\footnotesize
}

51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171

\usepackage[pdftex]{graphicx}
%\usepackage{graphicx}
% declare the path(s) where your graphic files are
\graphicspath{{./}{data/beagle/}}
% and their extensions so you won't have to specify these with
% every instance of \includegraphics
\DeclareGraphicsExtensions{.pdf,.jpeg,.png}

% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
 % \usepackage[pdftex]{graphicx}
 % declare the path(s) where your graphic files are
 % \graphicspath{{../pdf/}{../jpeg/}}
 % and their extensions so you won't have to specify these with
 % every instance of \includegraphics
 % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
 % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
 % will default to the driver specified in the system graphics.cfg if no
 % driver is specified.
 % \usepackage[dvips]{graphicx}
 % declare the path(s) where your graphic files are
 % \graphicspath{{../eps/}}
 % and their extensions so you won't have to specify these with
 % every instance of \includegraphics
 % \DeclareGraphicsExtensions{.eps}
\fi

% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/

%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/

\usepackage{algorithm}
\usepackage[noend]{algorithmic}

% *** SUBFIGURE PACKAGES ***
\usepackage[tight,footnotesize]{subfigure}
% \usepackage{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.

%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/

% *** PDF, URL AND HYPERLINK PACKAGES ***
%
\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.

% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\begin{document}
\title{CODES Best Practices}

%\author{\IEEEauthorblockN{Someone\IEEEauthorrefmark{1}} \\
%\IEEEauthorblockA{\IEEEauthorrefmark{1}Somewhere}
%}

%\numberofauthors{6} %  in this sample file, there are a *total*


% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}

% use arabic rather than roman numerals for table references
\renewcommand{\thetable}{\arabic{table}}

% make the title area
\maketitle

\begin{abstract}
172 173 174 175 176 177 178 179 180
This document outlines best practices for developing models in the
CODES/ROSS framework.  The reader should already be familiar with ROSS
and discrete event simulation; those topics are covered in the primary
ROSS documentation.
%
The main purpose of this document is to help the reader produce
CODES models in a consistent, modular style so that componets can be more
easily shared and reused.  It also includes a few tips to help avoid common
simulation bugs.
181 182
\end{abstract}

183
\section{CODES: modularizing models}
184

185 186 187
This section covers some of the basic principles of how to organize model
components to be more modular and easier to reuse across CODES models.

188
\subsection{Units of time}
189

190 191 192 193 194 195 196 197
ROSS does not dictate the units to be used in simulation timestamps.
The \texttt{tw\_stime} type is a double precision
floating point number that could represent any time unit
(e.g. days, hours, seconds, nanoseconds, etc.).  When building CODES
models you should \emph{always treat timestamps as nanoseconds}, however.
All components within a model must agree on the time units in order to
advance simulation time consistently.  Several common utilities in the
CODES project expect to operate in terms of nanoseconds.
198

199 200
\subsection{Organizing models by LP types}

201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
ROSS allows you to use as many different LP types as you would like to
construct your models.  Try to take advantage of this as much as possible by
organizing your simulation so that each component of the system that you are
modeling is implemented within its own LP type.  For example, a storage
system model might use different LPs for hard disks, clients, network
adapters, and servers.  There are multiple reasons for dividing up models
like this:

\begin{itemize}
\item General modularity: makes it easier to pull out particular components
(for example, a disk model) for use in other models.
\item Simplicitity: if each LP type is only handling a limited set of
events, then the event structure, state structure, and event handler
functions will all be much smaller and easier to understand.
\item Reverse computation: it makes it easier to implement reverse
computation, not only because the code is simpler, but also because you can
implement and test reverse computation per component rather than having to
apply it to an entire model all at once before testing.
\end{itemize}

It is also important to note that you can divide up models not just by
hardware components, but also by functionality, just as
you would modularize the implementation of a distributed file system.  For
example, a storage daemon might include separate LPs for replication, failure
detection, and reconstruction.  Each of those LPs can share the same network
card and disk resources for accurate modeling of resource usage.  They key
reason for splitting them up is to simplify the model and to encourage
reuse.

TODO: reference example, for now see how the LPs are organized in Triton
model.
232 233 234

\subsection{Protecting data structures}

235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
Once you have organized a model into separate LP types, it is tempting to
transfer information between them by directly sending events to an LP or by
modifying the state of an LP from a different LP type.  This approach entangles the LP types,
however, so that each LP type is dependent upon how the other is
implemented.  If you change one LP then you have to take care that you don't
break assumptions in other LPs that use their event or state structures.  This causes
problems for reuse.  It also means (even if you don't plan to reuse an
LP) that incompatibilities will be difficult to detect at compile time; the
compiler has no way to know which fields in a struct must be set before
sending an event.

For these reasons we encourage that all event struct and state struct
definitions be defined only within the .c file that implements the LP that
must use those structs.  They should not be exposed in external
headers.  If the definitions are placed in a header then it makes it
possible for those event and state structs to be used as an ad-hoc interface
between LPs.

Section~\ref{sec:completion} will describe alternatives for communicating
information between LP types.

TODO: reference example, for now see how structs are defined in Triton
model.

\subsection{Techniques for exchanging information and completion events
across LP types}
\label{sec:completion}

TODO: fill this in.
264

265 266
Send events into an LP using a C function API that calls event\_new under
the covers.
267

268 269 270 271
Indicate completion back to the calling LP by either delivering an opaque 
message back to the calling LP (that was passed in by the caller in a void*
argument), or by providing an API function for 2nd LP type to
use to call back (show examples of both).
272 273 274 275

\section{CODES: common utilities}

\subsection{codes\_mapping}
276
\label{sec:mapping}
277

278
TODO: pull in Misbah's codes-mapping documentation.
279 280 281

\subsection{modelnet}

282 283 284 285 286
TODO: fill this in.  Modelnet is a network abstraction layer for use in
CODES models.  It provides a consistent API that can be used to send
messages between nodes using a variety of different network transport
models.

287 288
\subsection{lp-io}

289 290 291 292 293 294 295 296 297 298 299 300 301
TODO: fill this in.  lp-io is a simple API for storing modest-sized
simulation results (not continous traces).  It handles reverse computation
and avoids doing any disk I/O until the simulation is complete.  All data is
written with collective I/O into a unified output directory.

\subsection{codes\_event\_new}

TODO: fill this in.  codes\_event\_new is a small wrapper to tw\_event\_new
that checks the incoming timestamp and makes sure that you don't exceed the
global end timestamp for ROSS.  The assumption is that CODES models will
normally run to a completion condition rather than until simulation time
runs out, see later section for more information on this approach.

302 303
\section{CODES: reproducability and model safety}

304 305 306 307
TODO: fill this in.  These are things that aren't required for modularity,
but just help you create models that produce consistent results and avoid
some common bugs.

308 309
\subsection{Event magic numbers}

310 311 312 313
TODO: fill this in.  Put magic numbers at the top of each event struct and
check them in event handler.  This makes sure that you don't accidentally
send the wrong event type to an LP.

314 315
\subsection{Small timestamps for LP transitions}

316 317 318 319 320 321 322
TODO: fill this in.  Sometimes you need to exchange events between LPs
without really consuming significant time (for example, to transfer
information from a server to its locally attached network card).  It is
tempting to use a timestamp of 0, but this causes timestamp ties in ROSS
which might have a variety of unintended consequences.  Use
codes\_local\_latency for timing of local event transitions to add some
random noise, can be thought of as bus overhead or context switch overhead.
323 324 325 326 327

\section{ROSS: general tips}

\subsection{Organizing event structures}

328 329 330 331 332 333 334 335 336 337
TODO: fill this in.  The main idea is to use unions to organize fields
within event structures.  Keeps the size down and makes it a little clearer
what variables are used by which event types.

\subsection{Avoiding event timestamp ties}

TODO: fill this in.   Why ties are bad (hurts reproducability, if not
accuracy, which in turn makes correctness testing more difficult).  Things
you can do to avoid ties, like skewing initial events by a random number
generator.
338 339 340

\subsection{Validating across simulation modes}

341 342 343 344
TODO: fill this in.  The general idea is that during development you should
do test runs with serial, parallel conservative, and parallel optimistic
runs to make sure that you get consistent results.  These modes stress
different aspects of the model.
345 346 347

\subsection{Reverse computation}

348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
TODO: fill this in.  General philosophy of when the best time to add reverse
computation is (probably not in your initial rough draft prototype, but it
is best to go ahead and add it before the model is fully complete or else it
becomes too daunting/invasive).

Things you can do to make it easier: rely on ordering enforced by ROSS (each
reverse handler only needs to reverse as single event, in order), keeping functions small, building
internal APIs for managing functions with reverse functions, how to handle
queues, etc.).  Might need some more subsubsections to break this up.

\subsection{How to complete a simulation}

TODO: fill this in.  Most core ROSS examples are design to intentionally hit
the end timestamp for the simulation (i.e. they are modeling a continuous,
steady state system).  This isn't necessarily true when modeling a
distributed storage system.  You might instead want the simulation to end
when you have completed a particular application workload (or collection of
application workloads), when a fault has been repaired, etc.  Talk about how
to handle this cleanly.
367 368 369 370

\section{TODO}

\begin{itemize}
371 372
\item Build a single example model that demonstrates the concepts in this
document, refer to it throughout.
373 374 375
\item reference to ROSS user's guide, airport model, etc.
\item put a pdf or latex2html version of this document on the codes web page
when ready
376 377
\end{itemize}

378 379 380 381 382 383 384 385 386 387 388 389 390
\begin{figure}
\begin{lstlisting}[caption=Example code snippet., label=snippet-example]
for (i=0; i<n; i++) {
    for (j=0; j<i; j++) {
        /* do something */
    }
}
\end{lstlisting}
\end{figure}

Figure ~\ref{fig:snippet-example} shows an example of how to show a code
snippet in latex.  We can use this format as needed throughout the document.

391
\end{document}