codes-best-practices.tex 18.2 KB
 Philip Carns committed Dec 05, 2013 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}  Philip Carns committed Dec 06, 2013 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 }  Philip Carns committed Dec 05, 2013 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}  Philip Carns committed Dec 06, 2013 172 173 This document outlines best practices for developing models in the CODES/ROSS framework. The reader should already be familiar with ROSS  Philip Carns committed Dec 06, 2013 174 and discrete event simulation in general; those topics are covered in the primary  Philip Carns committed Dec 06, 2013 175 176 177 178 179 180 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.  Philip Carns committed Dec 05, 2013 181 182 \end{abstract}  Philip Carns committed Dec 06, 2013 183 \section{CODES: modularizing models}  Philip Carns committed Dec 05, 2013 184   Philip Carns committed Dec 06, 2013 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.  Philip Carns committed Dec 06, 2013 188 \subsection{Units of time}  Philip Carns committed Dec 05, 2013 189   Philip Carns committed Dec 06, 2013 190 ROSS does not dictate the units to be used in simulation timestamps.  Philip Carns committed Dec 07, 2013 191 The \texttt{tw\_stime} type could represent any time unit  Philip Carns committed Dec 06, 2013 192 (e.g. days, hours, seconds, nanoseconds, etc.). When building CODES  Philip Carns committed Dec 07, 2013 193 194 models you should \emph{always treat timestamps as double precision floating point numbers representing nanoseconds}, however.  Philip Carns committed Dec 06, 2013 195 196 197 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.  Philip Carns committed Dec 05, 2013 198   Philip Carns committed Dec 06, 2013 199 200 \subsection{Organizing models by LP types}  Philip Carns committed Dec 06, 2013 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 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.  Philip Carns committed Dec 06, 2013 230 231 232 233 234 235 236 237 238 239 240 241 One hypothetical downside to splitting up models into multiple LP types is that it likely means that your model will generate more events than a monolithic model would have. Remember that \emph{ROSS is really efficient at generating and processing events}, though! It is usually a premature optimization to try to optimize a model by replacing events with function calls in cases where you know the necessary data is available on the local MPI process. Also recall that any information exchanged via event automatically benefits by shifting burden for tracking/retaining event data and event ordering into ROSS rather than your model. This can help simplify reverse computation by breaking complex operations into smaller, easier to understand (and reverse) event units with deterministic ordering.  Philip Carns committed Dec 06, 2013 242 243 TODO: reference example, for now see how the LPs are organized in Triton model.  Philip Carns committed Dec 06, 2013 244 245 246  \subsection{Protecting data structures}  Philip Carns committed Dec 07, 2013 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 ROSS operates by exchanging events between LPs. If an LP is sending an event to another LP of the same type, then in general it can do so by allocating an event structure (e.g. \texttt{tw\_event\_new()}), populating the event structure, and transmitting it (e.g. \texttt{tw\_event\_send()}). If an LP is sending an event to another LP of a \emph{different} type, however, then it should use an explicit API to do so without exposing the other LP's event structure definition. Event structures are not a robust API for exchanging data across different LP types. If one LP type accesses the event (or state) structure of another LP type, then it entangles the two components such that one LP is dependent upon the internal architecture of another LP. This not only makes it difficult to reuse components, but also makes it difficult to check for incompatibilities 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 a) each LP be implemented in a separate source file and b) all event structs and state structs be defined only within those source files. They should not be exposed in external  Philip Carns committed Dec 06, 2013 266 267 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  Philip Carns committed Dec 07, 2013 268 between LPs of different types.  Philip Carns committed Dec 06, 2013 269   Philip Carns committed Dec 07, 2013 270 271 Section~\ref{sec:completion} will describe alternative mechanisms for exchanging information between different LP types.  Philip Carns committed Dec 06, 2013 272 273 274 275 276 277 278 279 280  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.  Philip Carns committed Dec 06, 2013 281   Philip Carns committed Dec 06, 2013 282 283 Send events into an LP using a C function API that calls event\_new under the covers.  Philip Carns committed Dec 06, 2013 284   Philip Carns committed Dec 06, 2013 285 286 287 288 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).  Philip Carns committed Dec 06, 2013 289 290 291  \section{CODES: common utilities}  Philip Carns committed Dec 07, 2013 292 293 TODO: point out what repo each of these utilities can be found in.  Philip Carns committed Dec 06, 2013 294 \subsection{codes\_mapping}  Philip Carns committed Dec 06, 2013 295 \label{sec:mapping}  Philip Carns committed Dec 06, 2013 296   Philip Carns committed Dec 06, 2013 297 TODO: pull in Misbah's codes-mapping documentation.  Philip Carns committed Dec 06, 2013 298 299 300  \subsection{modelnet}  Philip Carns committed Dec 06, 2013 301 302 303 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  Philip Carns committed Dec 06, 2013 304 305 models. Note that modelnet requires the use of the codes-mapping API, described in previous section.  Philip Carns committed Dec 06, 2013 306   Philip Carns committed Dec 06, 2013 307 308 \subsection{lp-io}  Philip Carns committed Dec 06, 2013 309 310 311 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  Philip Carns committed Dec 07, 2013 312 313 314 315 316 317 318 written with collective I/O into a unified output directory. lp-io is mostly useful for cases in which you would like each LP instance to report statistics, but for scalability and data management reasons those results should be aggregated into a single file rather than producing a separate file per LP. TODO: look at ross/IO code and determine how it relates to this.  Philip Carns committed Dec 06, 2013 319   Philip Carns committed Dec 08, 2013 320 321 322 323 324 325 326 327 328 329 \subsection{codes-workload generator} TODO: fill this in. codes-workload is an abstraction layer for feeding I/O workloads into a simulation. It supports multiple back-ends for generating those I/O events; data could come from a trace file, from Darshan, or from a synthetic description. This component is under active development right now, not complete yet. The synthetic generator is probably pretty solid for use already though.  Philip Carns committed Dec 06, 2013 330 331 332 333 334 335 336 337 \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.  Philip Carns committed Dec 07, 2013 338 339 340 341 342 343 \subsection{ross/IO} TODO: fill this in. This is the I/O library included with ROSS, based on phasta I/O library. What are the use cases and how do you use it. Does it deprecate the lp-io tool?  Philip Carns committed Dec 06, 2013 344 345 \section{CODES: reproducability and model safety}  Philip Carns committed Dec 06, 2013 346 347 348 349 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.  Philip Carns committed Dec 06, 2013 350 351 \subsection{Event magic numbers}  Philip Carns committed Dec 06, 2013 352 353 354 355 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.  Philip Carns committed Dec 06, 2013 356 357 \subsection{Small timestamps for LP transitions}  Philip Carns committed Dec 06, 2013 358 359 360 361 362 363 364 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.  Philip Carns committed Dec 06, 2013 365 366 367 368 369  \section{ROSS: general tips} \subsection{Organizing event structures}  Philip Carns committed Dec 06, 2013 370 371 372 373 374 375 376 377 378 379 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.  Philip Carns committed Dec 06, 2013 380 381 382  \subsection{Validating across simulation modes}  Philip Carns committed Dec 06, 2013 383 384 385 386 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.  Philip Carns committed Dec 06, 2013 387 388 389  \subsection{Reverse computation}  Philip Carns committed Dec 06, 2013 390 391 392 393 394 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).  Philip Carns committed Dec 07, 2013 395 396 397 398 399 400 401 402 403 404 Other things to talk about (maybe these are different subsections): \begin{itemize} \item propagate and maintain as much state as possible in event structures rather than state structures \item rely on ordering enforced by ROSS (each reverse handler only needs to reverse as single event, in order) \item keeping functions small \item building internal APIs for managing functions with reverse functions \item how to handle queues \end{itemize}  Philip Carns committed Dec 06, 2013 405 406 407 408 409 410 411 412 413 414  \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.  Philip Carns committed Dec 06, 2013 415   Philip Carns committed Dec 09, 2013 416 417 418 419 420 421 \subsection{Kicking off a simulation} TOOD: fill this in. Each LP needs to send an event to itself at the beginning of the simulation (explain why). We usually skew these with random numbers to help break ties right off the bat (explain why).  Philip Carns committed Dec 06, 2013 422 423 424 \section{TODO} \begin{itemize}  Philip Carns committed Dec 06, 2013 425 426 \item Build a single example model that demonstrates the concepts in this document, refer to it throughout.  Philip Carns committed Dec 06, 2013 427 428 429 \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  Philip Carns committed Dec 05, 2013 430 431 \end{itemize}  Philip Carns committed Dec 06, 2013 432 433 434 435 436 437 438 439 440 441 442 443 444 \begin{figure} \begin{lstlisting}[caption=Example code snippet., label=snippet-example] for (i=0; i