1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/0__Papers/Future_Architecture/Future_Architecture.tex	Tue Jan 03 16:29:44 2012 -0800
     1.3 @@ -0,0 +1,1183 @@
     1.4 +
     1.5 +
     1.6 +\documentclass[conference]{IEEEtran}
     1.7 +%
     1.8 +\usepackage{makeidx,geometry,amssymb,graphicx,calc,ifthen}
     1.9 +%
    1.10 +
    1.11 +% *** CITATION PACKAGES ***
    1.12 +%
    1.13 +%\usepackage{cite}
    1.14 +% cite.sty was written by Donald Arseneau
    1.15 +% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
    1.16 +% \cite{} output to follow that of IEEE. Loading the cite package will
    1.17 +% result in citation numbers being automatically sorted and properly
    1.18 +% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
    1.19 +% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
    1.20 +% \cite will automatically add leading space, if needed. Use cite.sty's
    1.21 +% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
    1.22 +% cite.sty is already installed on most LaTeX systems. Be sure and use
    1.23 +% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
    1.24 +% not currently provide for hyperlinked citations.
    1.25 +% The latest version can be obtained at:
    1.26 +% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
    1.27 +% The documentation is contained in the cite.sty file itself.
    1.28 +
    1.29 +
    1.30 +
    1.31 +
    1.32 +
    1.33 +
    1.34 +% *** GRAPHICS RELATED PACKAGES ***
    1.35 +%
    1.36 +\ifCLASSINFOpdf
    1.37 +  % \usepackage[pdftex]{graphicx}
    1.38 +  % declare the path(s) where your graphic files are
    1.39 +  % \graphicspath{{../pdf/}{../jpeg/}}
    1.40 +  % and their extensions so you won't have to specify these with
    1.41 +  % every instance of \includegraphics
    1.42 +  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
    1.43 +\else
    1.44 +  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
    1.45 +  % will default to the driver specified in the system graphics.cfg if no
    1.46 +  % driver is specified.
    1.47 +  % \usepackage[dvips]{graphicx}
    1.48 +  % declare the path(s) where your graphic files are
    1.49 +  % \graphicspath{{../eps/}}
    1.50 +  % and their extensions so you won't have to specify these with
    1.51 +  % every instance of \includegraphics
    1.52 +  % \DeclareGraphicsExtensions{.eps}
    1.53 +\fi
    1.54 +% graphicx was written by David Carlisle and Sebastian Rahtz. It is
    1.55 +% required if you want graphics, photos, etc. graphicx.sty is already
    1.56 +% installed on most LaTeX systems. The latest version and documentation can
    1.57 +% be obtained at: 
    1.58 +% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
    1.59 +% Another good source of documentation is "Using Imported Graphics in
    1.60 +% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
    1.61 +% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
    1.62 +%
    1.63 +% latex, and pdflatex in dvi mode, support graphics in encapsulated
    1.64 +% postscript (.eps) format. pdflatex in pdf mode supports graphics
    1.65 +% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
    1.66 +% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
    1.67 +% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
    1.68 +% which can result in "jaggedy"/blurry rendering of lines and letters as
    1.69 +% well as large increases in file sizes.
    1.70 +%
    1.71 +% You can find documentation about the pdfTeX application at:
    1.72 +% http://www.tug.org/applications/pdftex
    1.73 +
    1.74 +
    1.75 +
    1.76 +
    1.77 +
    1.78 +% *** MATH PACKAGES ***
    1.79 +%
    1.80 +%\usepackage[cmex10]{amsmath}
    1.81 +% A popular package from the American Mathematical Society that provides
    1.82 +% many useful and powerful commands for dealing with mathematics. If using
    1.83 +% it, be sure to load this package with the cmex10 option to ensure that
    1.84 +% only type 1 fonts will utilized at all point sizes. Without this option,
    1.85 +% it is possible that some math symbols, particularly those within
    1.86 +% footnotes, will be rendered in bitmap form which will result in a
    1.87 +% document that can not be IEEE Xplore compliant!
    1.88 +%
    1.89 +% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
    1.90 +% thus preventing page breaks from occurring within multiline equations. Use:
    1.91 +%\interdisplaylinepenalty=2500
    1.92 +% after loading amsmath to restore such page breaks as IEEEtran.cls normally
    1.93 +% does. amsmath.sty is already installed on most LaTeX systems. The latest
    1.94 +% version and documentation can be obtained at:
    1.95 +% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/
    1.96 +
    1.97 +
    1.98 +
    1.99 +
   1.100 +
   1.101 +% *** SPECIALIZED LIST PACKAGES ***
   1.102 +%
   1.103 +%\usepackage{algorithmic}
   1.104 +% algorithmic.sty was written by Peter Williams and Rogerio Brito.
   1.105 +% This package provides an algorithmic environment fo describing algorithms.
   1.106 +% You can use the algorithmic environment in-text or within a figure
   1.107 +% environment to provide for a floating algorithm. Do NOT use the algorithm
   1.108 +% floating environment provided by algorithm.sty (by the same authors) or
   1.109 +% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
   1.110 +% algorithm float types and packages that provide these will not provide
   1.111 +% correct IEEE style captions. The latest version and documentation of
   1.112 +% algorithmic.sty can be obtained at:
   1.113 +% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
   1.114 +% There is also a support site at:
   1.115 +% http://algorithms.berlios.de/index.html
   1.116 +% Also of interest may be the (relatively newer and more customizable)
   1.117 +% algorithmicx.sty package by Szasz Janos:
   1.118 +% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/
   1.119 +
   1.120 +
   1.121 +
   1.122 +
   1.123 +% *** ALIGNMENT PACKAGES ***
   1.124 +%
   1.125 +%\usepackage{array}
   1.126 +% Frank Mittelbach's and David Carlisle's array.sty patches and improves
   1.127 +% the standard LaTeX2e array and tabular environments to provide better
   1.128 +% appearance and additional user controls. As the default LaTeX2e table
   1.129 +% generation code is lacking to the point of almost being broken with
   1.130 +% respect to the quality of the end results, all users are strongly
   1.131 +% advised to use an enhanced (at the very least that provided by array.sty)
   1.132 +% set of table tools. array.sty is already installed on most systems. The
   1.133 +% latest version and documentation can be obtained at:
   1.134 +% http://www.ctan.org/tex-archive/macros/latex/required/tools/
   1.135 +
   1.136 +
   1.137 +%\usepackage{mdwmath}
   1.138 +%\usepackage{mdwtab}
   1.139 +% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
   1.140 +% especially mdwmath.sty and mdwtab.sty which are used to format equations
   1.141 +% and tables, respectively. The MDWtools set is already installed on most
   1.142 +% LaTeX systems. The lastest version and documentation is available at:
   1.143 +% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/
   1.144 +
   1.145 +
   1.146 +% IEEEtran contains the IEEEeqnarray family of commands that can be used to
   1.147 +% generate multiline equations as well as matrices, tables, etc., of high
   1.148 +% quality.
   1.149 +
   1.150 +
   1.151 +%\usepackage{eqparbox}
   1.152 +% Also of notable interest is Scott Pakin's eqparbox package for creating
   1.153 +% (automatically sized) equal width boxes - aka "natural width parboxes".
   1.154 +% Available at:
   1.155 +% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
   1.156 +
   1.157 +
   1.158 +
   1.159 +
   1.160 +
   1.161 +% *** SUBFIGURE PACKAGES ***
   1.162 +%\usepackage[tight,footnotesize]{subfigure}
   1.163 +% subfigure.sty was written by Steven Douglas Cochran. This package makes it
   1.164 +% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
   1.165 +% work, it is a good idea to load it with the tight package option to reduce
   1.166 +% the amount of white space around the subfigures. subfigure.sty is already
   1.167 +% installed on most LaTeX systems. The latest version and documentation can
   1.168 +% be obtained at:
   1.169 +% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
   1.170 +% subfigure.sty has been superceeded by subfig.sty.
   1.171 +
   1.172 +
   1.173 +
   1.174 +%\usepackage[caption=false]{caption}
   1.175 +%\usepackage[font=footnotesize]{subfig}
   1.176 +% subfig.sty, also written by Steven Douglas Cochran, is the modern
   1.177 +% replacement for subfigure.sty. However, subfig.sty requires and
   1.178 +% automatically loads Axel Sommerfeldt's caption.sty which will override
   1.179 +% IEEEtran.cls handling of captions and this will result in nonIEEE style
   1.180 +% figure/table captions. To prevent this problem, be sure and preload
   1.181 +% caption.sty with its "caption=false" package option. This is will preserve
   1.182 +% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
   1.183 +% (recommended due to many improvements over 1.2) of subfig.sty supports
   1.184 +% the caption=false option directly:
   1.185 +%\usepackage[caption=false,font=footnotesize]{subfig}
   1.186 +%
   1.187 +% The latest version and documentation can be obtained at:
   1.188 +% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
   1.189 +% The latest version and documentation of caption.sty can be obtained at:
   1.190 +% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/
   1.191 +
   1.192 +
   1.193 +
   1.194 +
   1.195 +% *** FLOAT PACKAGES ***
   1.196 +%
   1.197 +%\usepackage{fixltx2e}
   1.198 +% fixltx2e, the successor to the earlier fix2col.sty, was written by
   1.199 +% Frank Mittelbach and David Carlisle. This package corrects a few problems
   1.200 +% in the LaTeX2e kernel, the most notable of which is that in current
   1.201 +% LaTeX2e releases, the ordering of single and double column floats is not
   1.202 +% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
   1.203 +% single column figure to be placed prior to an earlier double column
   1.204 +% figure. The latest version and documentation can be found at:
   1.205 +% http://www.ctan.org/tex-archive/macros/latex/base/
   1.206 +
   1.207 +
   1.208 +
   1.209 +%\usepackage{stfloats}
   1.210 +% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
   1.211 +% the ability to do double column floats at the bottom of the page as well
   1.212 +% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
   1.213 +% LaTeX2e). It also provides a command:
   1.214 +%\fnbelowfloat
   1.215 +% to enable the placement of footnotes below bottom floats (the standard
   1.216 +% LaTeX2e kernel puts them above bottom floats). This is an invasive package
   1.217 +% which rewrites many portions of the LaTeX2e float routines. It may not work
   1.218 +% with other packages that modify the LaTeX2e float routines. The latest
   1.219 +% version and documentation can be obtained at:
   1.220 +% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
   1.221 +% Documentation is contained in the stfloats.sty comments as well as in the
   1.222 +% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
   1.223 +% does not allow \baselineskip to stretch. Authors submitting work to the
   1.224 +% IEEE should note that IEEE rarely uses double column equations and
   1.225 +% that authors should try to avoid such use. Do not be tempted to use the
   1.226 +% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
   1.227 +% not format its papers in such ways.
   1.228 +
   1.229 +
   1.230 +
   1.231 +
   1.232 +
   1.233 +% *** PDF, URL AND HYPERLINK PACKAGES ***
   1.234 +%
   1.235 +%\usepackage{url}
   1.236 +% url.sty was written by Donald Arseneau. It provides better support for
   1.237 +% handling and breaking URLs. url.sty is already installed on most LaTeX
   1.238 +% systems. The latest version can be obtained at:
   1.239 +% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
   1.240 +% Read the url.sty source comments for usage information. Basically,
   1.241 +% \url{my_url_here}.
   1.242 +
   1.243 +
   1.244 +
   1.245 +
   1.246 +
   1.247 +% *** Do not adjust lengths that control margins, column widths, etc. ***
   1.248 +% *** Do not use packages that alter fonts (such as pslatex).         ***
   1.249 +% There should be no need to do such things with IEEEtran.cls V1.6 and later.
   1.250 +% (Unless specifically asked to do so by the journal or conference you plan
   1.251 +% to submit to, of course. )
   1.252 +
   1.253 +
   1.254 +% correct bad hyphenation here
   1.255 +\hyphenation{op-tical net-works semi-conduc-tor}
   1.256 +
   1.257 +
   1.258 +\begin{document}
   1.259 +\bibliographystyle{plain}
   1.260 +%
   1.261 +
   1.262 +\title{The Shape of Future Architectures}
   1.263 +
   1.264 +\author
   1.265 +{
   1.266 + \IEEEauthorblockN{Sean Halle}
   1.267 + \IEEEauthorblockA
   1.268 + {
   1.269 +   University of California at Santa Cruz\\
   1.270 +   and INRIA Paris\\
   1.271 +   Email: sean.halle@inria.fr
   1.272 + }
   1.273 + \and
   1.274 + \IEEEauthorblockN{Albert Cohen}
   1.275 + \IEEEauthorblockA
   1.276 + { INRIA Paris\\
   1.277 +   Email: albert.cohen@infria.fr
   1.278 + }
   1.279 +}
   1.280 +
   1.281 +
   1.282 +\maketitle             
   1.283 +%
   1.284 +
   1.285 +\begin{abstract}
   1.286 +  Process technology is rapidly approaching multiple fundamental physical limits that combine to increase the cost of producing chips faster than the increase in density.  Whether or not process technology continues to shrink, the economics will slow the demand for chips from future processes.  This will, for the first time, shift the design decisions from being shortest time-to-market towards being the greatest efficiency per transistor -- either in computation delivered towards the goal end-user measurement such as throughput, or in energy per operation.
   1.287 +  
   1.288 +The implication for processor architecture is to accelerate the trend away from "easy to program" structures such as out-of-order pipelines and coherent shared memory, and towards hierarchical designs that force application information to be exploited in explicitly managing the placement and movement of data, in order to keep it as local for as much of the computation as possible.  The cost of communication will be the dominant factor driving the shape of future architectures, both from a computation-bottleneck cost and an energy per operation cost.
   1.289 +
   1.290 +Integration will be pushed towards the third dimension in order to mitigate the communication costs -- indeed main memories have long been on that path.  This approach will hasten the development of 3 dimensional integration processes.  The architecture implication is that 
   1.291 +\end{abstract}
   1.292 +
   1.293 +\section{Motivation}
   1.294 +
   1.295 +Threads were invented to be virtual sequential processors, but are 
   1.296 +problematic when one has multiple physical cores. Not only
   1.297 +are they difficult to use for parallel code, but their parallel performance is poor
   1.298 +because they block the language from controlling
   1.299 +task placement. The language often knows which cores are likely to already
   1.300 +have data in the cache which a new task requires as input. If it had
   1.301 +control, the language could place tasks where the data is likely to already
   1.302 +reside, reducing communication and increasing performance and power
   1.303 +efficiency. A thread replacement is needed that is both easy to use in
   1.304 +applications and gives the language control over task placement.
   1.305 +
   1.306 +The first question is, what is the easiest to use parallelism construct?  There
   1.307 +exist many to choose from: Threads (for legacy reasons); Actors
   1.308 +{\cite{Hewitt10}}{\cite{Actors97}}; Components {\cite{ComponentModel00}};
   1.309 +process calculi {\cite{hoare78}} {\cite{milner99}};
   1.310 +coordination languages {\cite{Gelernter85Linda}}; and new ones
   1.311 +continually invented.
   1.312 +
   1.313 +We demonstrate in this paper  a thread replacement that lets any such parallelism
   1.314 +construct be plugged in.  It is the first extensible hardware abstraction,
   1.315 +allowing to plug-in both preferred parallelism constructs and preferred 
   1.316 +runtime scheduler. We focus in this introductory paper on
   1.317 +the parallelism construct support, illustrating how to implement synchronous
   1.318 +\texttt{send}-\texttt{receive} constructs motivated by process calculi,
   1.319 +the \texttt{spawn} and \texttt{sync} constructs from Cilk, and even
   1.320 +\texttt{mutex} and \texttt{condition variable} constructs from pthreads.
   1.321 +However, the schedulers we implemented have no
   1.322 +interesting performance optimizations.
   1.323 +
   1.324 +The next question is, how much effort is required to implement a plugin? Our
   1.325 +mechanism protects the plugin from exposure to concurrency issues, allowing
   1.326 +the parallelism constructs to be implemented with sequential algorithms.  It
   1.327 +accomplishes this by introducing a ``virtual'' time that sequentializes events
   1.328 +that appear, to the program, to be simultaneous.
   1.329 +
   1.330 +We call our abstraction Virtualized Master-Slave, or VMS. We demonstrate a user-level
   1.331 +implementation in this paper, although it is ideally implemented as the base
   1.332 +hardware abstraction of the OS.
   1.333 +
   1.334 +It involves subtle concepts related to time in the program vs time in the
   1.335 +plugin vs physical time.  We explain it in four levels, starting with an abstract definition
   1.336 + and moving down to implementation.
   1.337 +
   1.338 +The first level is the theoretical definition, given in Section \ref{secAbsModel}. Second is the elements
   1.339 +of our implementation and how they relate to the theoretical definition, in Section \ref{secInternal}.
   1.340 +Third is the application code point of view, in Section \ref{secApp}, which is tied back to both
   1.341 +the abstract model and the internal elements. The fourth view,
   1.342 +also in Section \ref{secApp}, shows the implementation of the plugin for a parallel
   1.343 +construct. Additionally,
   1.344 +measurements of effectiveness appear
   1.345 +in Section \ref{secResults} and conclusion is in \ref{secConclusion}.
   1.346 +
   1.347 +\section{Background and Related Work}
   1.348 +
   1.349 +{\bf Side-stepping OS Threads:\ }User-level thread packages and most parallel
   1.350 +language runtimes have to side-step OS threads, by pinning one to each core,
   1.351 +which effectively gives the user-level package control over the core. Our VMS
   1.352 +implementation also does this. We are not claiming in this paper to have the
   1.353 +OS level implementation of VMS that the model is capable of -- just the
   1.354 +user-space version.
   1.355 +
   1.356 +Related work either provides a variation on the Thread model, or is a full
   1.357 +language with included parallelism constructs.  For example,
   1.358 + TBB {\cite{TBBHome}} is a user-space thread package with added features.
   1.359 +It allows
   1.360 +tasks to create other tasks and control when to start their
   1.361 +execution. However, one cannot plug in alternate parallelism-control constructs, such as
   1.362 +rendez-vous style send and receive, which would have to be made using locks.
   1.363 + Likewise, Cilk {\cite{CILKHome}}
   1.364 +provides a simpler and easier to use version of TBB's task scheduler, but is
   1.365 +limited to only tree-shaped task graphs. OpenMP {\cite{OpenMPHome}} allows
   1.366 + creating tasks and controlling their execution order,
   1.367 +but is a language, not a hardware abstraction.  All of these may
   1.368 +alternatively be implemented via plugins to VMS, with similar performance.
   1.369 +
   1.370 +In contrast, VMS is the first hardware abstraction that doesn't impose its own concurrency
   1.371 +semantics, but rather takes preferred ones as plugins. This makes it not a
   1.372 +language itself, but a {\em{support}} mechanism for language level
   1.373 +parallelism constructs. The parallelism constructs in Actors, Components,
   1.374 +pthreads, and so on may all be implemented as VMS plugins.
   1.375 +
   1.376 +{\bf Virtual Processor (VP) Definition:\ }We want to avoid the confusion
   1.377 +associated with the terms ``thread'' and ``task'' so will use the term
   1.378 +{\em{virtual processor}} (VP), which we define as state in combination with
   1.379 +the ability to animate code or {\em{an additional level of virtual
   1.380 +processors}}. The state consists of a stack with its contents, a program
   1.381 +counter, a pointer to top of stack, and a pointer to the current stack frame.
   1.382 +
   1.383 +\section{Abstract Definition of VMS}
   1.384 +\label{secAbsModel}
   1.385 +
   1.386 +We give an intuitive overview, then add details in the following sub-sections.
   1.387 +
   1.388 +{\bf Intuitive Overview:\ }VMS is concerned primarily with time and
   1.389 +guarantees about it. This is because parallelism constructs control how the
   1.390 +time-lines of different virtual processors intersect. They also guarantee
   1.391 +relations of time lines to hardware events.
   1.392 +
   1.393 +As an example, consider a program that writes into a data structure in one
   1.394 +time-line, then calls a \texttt{send} construct, meanwhile in a different
   1.395 +time-line it calls the \texttt{receive} construct then reads the data
   1.396 +structure. The constructs should guarantee that all data written before the
   1.397 +\texttt{send} is readable in the other time-line after the
   1.398 +\texttt{receive}.  VMS provides primitive guarantees, which plugged-in code
   1.399 +builds upon to provide such higher-level guarantees.
   1.400 +
   1.401 +To support parallelism constructs, VMS provides: primitive operations to create and suspend
   1.402 +VPs; a way for plugged-in code to control when each VP is (re)started; and
   1.403 +time-related guarantees. These are enforced on all hardware, be it shared
   1.404 +memory or distributed, with strong memory consistency or weak.
   1.405 +
   1.406 +{\bf Definition in Three Parts:\ }We give the abstract definition in three
   1.407 +parts: a definition of the elements of a VMS computation system; a definition
   1.408 +of time and the key VMS guarantee; and a definition of virtual processor
   1.409 +scheduling states and transitions between them.
   1.410 +
   1.411 +The definition we give is for VMS {\em{with plugins present}}. \ Hence, it
   1.412 +covers the behavior of all possible parallelism constructs implementable with
   1.413 +VMS. The Master mentioned in the definition is an abstract
   1.414 +entity, with a plugin present. In practice, this Master entity is implemented
   1.415 +as part of a core VMS, and plugins later added. This VMS-core is the
   1.416 +hardware abstraction. It hides the physical hardware behind an interface that
   1.417 +creates virtual processors and enforces well-defined time-behavior.
   1.418 +
   1.419 +
   1.420 +\subsection{The Elements of a VMS Computation System}
   1.421 +
   1.422 +\texttt{- }A VMS program has multiple VPs, which are Slaves,
   1.423 +each with an independent time-line.
   1.424 +
   1.425 +\texttt{- }A schedule of Slaves is generated by a Master
   1.426 +entity, from within separate time-line(s).
   1.427 +
   1.428 +\texttt{- }A schedule is defined as the set of points at which
   1.429 +VPs are (re)animated.
   1.430 +
   1.431 +\texttt{- }All semantic parallelism behavior is invoked via
   1.432 +communication with the Master.
   1.433 +
   1.434 +\texttt{- }Communication with the Master happens by using a
   1.435 +model-provided primitive, which causes {\em{voluntary}} suspension of the
   1.436 +program's VP.
   1.437 +
   1.438 +
   1.439 +What is important here is: that the choice of which VP is animated, at which
   1.440 +point, happens in a separate time-line; and that the VPs suspend voluntarily
   1.441 +for each parallelism construct. This means that {\em{scheduling is separated
   1.442 +from the application code}}, the key point.
   1.443 +
   1.444 +The Master entity appears to be a single entity to the slaves, but may be
   1.445 +implemented by multiple Master VPs hidden inside the VMS implementation.
   1.446 +
   1.447 +VPs use the Master as an intermediary to: semantically communicate with each
   1.448 +other; cause creation of new program VPs; and to influence re-animation of
   1.449 +VPs. As a subtlety, notice that hardware mechanisms, such as coherent shared
   1.450 +memory, allow communication to take place that is not visible to the
   1.451 +parallelism constructs. Parallelism constructs must be separately called in
   1.452 +order to make use of shared variable communication safe.
   1.453 +
   1.454 +{\bf Definitions:\ }VMS is intended only for hardware systems that consist of processing elements
   1.455 +connected by communication.  We define a memory-space to be a processing
   1.456 +element, albeit without the ability to transform data. We define a
   1.457 +{\em{physical core}} to be a processing element that {\em{does}} transform
   1.458 +data, and require that it execute a sequential stream of instructions. We
   1.459 +define a program-time as the sequence of instructions animated by a Slave VP
   1.460 +(which is eventually animated by a physical core). A Slave VP has associated
   1.461 +{\em{scheduling state}} that, among other things, relates to how its
   1.462 +program-time progresses relative to physical time on the cores.
   1.463 +
   1.464 +\subsection{Time in VMS}
   1.465 +
   1.466 +\texttt{- }VMS has three levels of time: {\em{Program time}},
   1.467 +{\em{ Master time}}, and {\em{Virtual time}}.
   1.468 +
   1.469 +\texttt{- }Program time is local to a Slave VP, measured in
   1.470 +instruction executions.
   1.471 +
   1.472 +\texttt{- }Master time is hidden from the program and is
   1.473 +independent from all Program times.
   1.474 +
   1.475 +\texttt{- }Virtual time is the ordered set of changes in
   1.476 +scheduling state of Slave VPs.
   1.477 +
   1.478 +
   1.479 +
   1.480 +What is most important here is that Virtual time defines a global sequential
   1.481 +ordering. This ordering is consistent with the key VMS guarantee (given
   1.482 +below), and each point in it is computed within Master time.
   1.483 +
   1.484 +Also, the independence between program times and master time has subtle
   1.485 +advantages. It enables elegant enforcement of the VMS guarantee, and
   1.486 +implementation simplifications that become clear after gaining deep
   1.487 +implementation knowledge.
   1.488 +
   1.489 +In VMS, each event relevant to parallel semantics is tied to a transition of
   1.490 +the state of a Slave VP. This means that implementing the behavior of parallel
   1.491 +semantics is equivalent to controlling the order of transitions of state of
   1.492 +virtual processors.
   1.493 +
   1.494 +{\bf Definitions:\ }The stream of instructions in a given program-time is
   1.495 +broken into a number of {\em{trace-segments}}, separated by suspension
   1.496 +points. Each trace-segment is animated by a single physical core, but not
   1.497 +necessarily the same core as animated the other trace segments. A suspend
   1.498 +point is created by a Slave VP executing the ``suspend'' primitive provided by
   1.499 +VMS. A suspend point has no duration in program time, but has distinct start
   1.500 +and end points in virtual time. The end-suspension points of two different
   1.501 +program times can be tied together within virtual time, which is called a
   1.502 +{\em{tie point}} and has special significance to parallel constructs. The
   1.503 +physical-time of a core has no relationship to any program time, except for
   1.504 +the various time-guarantees in this definition of VMS.
   1.505 +
   1.506 +\begin{figure}[ht]
   1.507 + \includegraphics[width=2.9in]{../figures/Time_in_VMS_1.png}
   1.508 + \caption
   1.509 + {Mapping program time onto Virtual time. \ The
   1.510 +  Master controls creation of new program time lines, and ending suspend
   1.511 +  points. Here, it has ended two suspend points at a common tie-point.
   1.512 +  }
   1.513 +\label{figTimeMapping}
   1.514 +\end{figure}
   1.515 +
   1.516 +{\bf Relating time-lines to each other:\ }Figure \ref{figTimeMapping}
   1.517 +illustrates how trace-segments relate to suspend points, and map onto
   1.518 +virtual time. A trace segment starts in virtual time where suspend is ended, as seen.
   1.519 + In fact, the two trace segments shown have a common
   1.520 +start-point within virtual time. This is because the parallelism semantics
   1.521 +chose to start them at the same point -- this is what a tie
   1.522 +point is.  A key note is that the lengths in virtual time have no relation to
   1.523 +the lengths in program-time. The only defined feature is that those two
   1.524 +trace-segments have a common start-point in virtual time. This means that the
   1.525 +two suspend points are considered to be tied together.
   1.526 +
   1.527 +{\bf The Key VMS guarantee:\ }\label{VMSguarantee}Being tied together
   1.528 +means that all physical events that can be observed by both program-times are
   1.529 +covered by the key VMS guarantee: any events triggered before the common
   1.530 +suspend point in one program time are guaranteed visible in the other program
   1.531 +time after the common suspend point. They {\em{might}} be visible before,
   1.532 +but it's not guaranteed. In addition, events triggered after the common
   1.533 +suspend point in one are guaranteed not visible before the common suspend
   1.534 +point in the other. {\em{This two-part guarantee can be considered the heart
   1.535 +of VMS.}}
   1.536 +
   1.537 +Intuitively, a tie-point separates before it from after such that tied program
   1.538 +times agree (illustrated with code in Section \ref{secApp} Figure \ref{figAnimVP}). But the subtlety is
   1.539 +that events triggered before the tie-point, {\em{might}} be visible to the
   1.540 +other before, and ones triggered after {\em{might not}} be visible to the
   1.541 +other after -- physical events triggered before are only guaranteed visible
   1.542 +{\em{after}} the tie point, and events after are only guaranteed
   1.543 +{\em{not}} visible {\em{before}} the tie point.
   1.544 +
   1.545 +This is a form of bounded non-determinism. The pattern of suspension
   1.546 +end-points determines which trace-segments overlap in Virtual time, and events
   1.547 +triggered in one might be visible in overlapped ones. But no guarantees cover
   1.548 +these. If one segment tries to observe, it will see events triggered by
   1.549 +overlapped segments in non-deterministic order.
   1.550 +
   1.551 +The VMS implementation defines which physical events are covered by the key
   1.552 +VMS guarantee (reads/writes, network communication, DMA, I/O).
   1.553 +
   1.554 +{\bf Globally consistent sequential order:\ }VMS maps suspend-start,
   1.555 +suspend-end, and hence tie-points, to a globally-consistent sequential order
   1.556 +in Virtual time. This enables  one of VMS's key benefits: sequential
   1.557 +algorithms for parallel constructs.
   1.558 +
   1.559 +Tie points define parallel behavior, so an implementation of how to choose tie
   1.560 +points equals an implementation of parallel constructs. The Master chooses
   1.561 +tie-points, so plugging code to choose tie-points into the Master equals
   1.562 +plugging in parallel constructs.
   1.563 +
   1.564 +\subsection{Scheduling State}
   1.565 +
   1.566 +Scheduling state is used in VMS to organize internal activity, for enforcing
   1.567 +the guarantees.
   1.568 +
   1.569 +\texttt{- }VPs have three scheduling states: {\em{Animated}},
   1.570 +{\em{Blocked}}, {\em{Ready}} (Figure \ref{figStates}).
   1.571 +
   1.572 +\texttt{- }VPs in Animated are {\em{allowed}} to advance
   1.573 +program-time with {\em{local}} physical time.
   1.574 +
   1.575 +\texttt{- }VPs in Blocked and Ready do not advance their
   1.576 +program-time.
   1.577 +
   1.578 +\texttt{- }Animated has two physical states:
   1.579 +{\em{Progressing}} and {\em{Stalled}}.
   1.580 +
   1.581 +\texttt{- }VPs in Progressing advance program-time with local
   1.582 +physical time, those in Stalled do not (allowing non-semantic suspend).
   1.583 +
   1.584 +\texttt{- }Scheduling states are defined in Virtual time only.
   1.585 +
   1.586 +\texttt{- }Progressing and Stalled are defined in local
   1.587 +physical time only (invisible in Virtual).
   1.588 +
   1.589 +
   1.590 +\begin{figure}[h]
   1.591 +  \includegraphics{../figures/Scheduling_states_2.png}
   1.592 +  \caption{Scheduling states of a slave VP in the VMS model.}
   1.593 +  \label{figStates}
   1.594 +\end{figure}
   1.595 +
   1.596 +Some important points: 1) only VPs Animated can trigger physical events that
   1.597 +are seen in other program time-lines; 2) the distinction between Blocked vs
   1.598 +Stalled is that a VP has to explicitly execute a VMS primitive operation to
   1.599 +enter Blocked, making it part of the semantics of parallelism constructs. In
   1.600 +contrast, Stalled happens invisibly, with no effect on semantic behavior. It
   1.601 +is due to hardware events hidden inside VMS, such as interrupts.
   1.602 +
   1.603 +The Ready state is used to separate the parallelism-construct behavior from
   1.604 +the scheduling behavior. It acts as a ``staging area'' for scheduling. VPs
   1.605 +placed into this state are {\em{allowed}} to be animated, then the scheduler
   1.606 +decides when and where.
   1.607 +
   1.608 +A subtle but illustrative point is that actions {\em{outside}} a given
   1.609 +program time cause the VP to transition Blocked$\rightarrow$Ready, which
   1.610 +contrasts to lock algorithms like spin-locks or Dijkstra's, where the
   1.611 +concurrency-related behavior takes place {\em{inside}} program time.
   1.612 +
   1.613 +{\bf Transition Between Slave Scheduling States:\ }
   1.614 +
   1.615 +\texttt{- }VPs transition states as shown in Figure \ref{figStates}.
   1.616 +
   1.617 +\texttt{- }Animated$\rightarrow$Blocked is caused by a Slave VP
   1.618 +executing the Suspend VMS primitive.
   1.619 +
   1.620 +\texttt{- }Blocked$\rightarrow$Ready is determined by the
   1.621 +semantics implemented in the plugin.
   1.622 +
   1.623 +\texttt{- }Ready$\rightarrow$Animated is determined by the
   1.624 +scheduler in the plugin.
   1.625 +
   1.626 +\texttt{- }Transitions in scheduling state have a globally
   1.627 +consistent order in Virtual time.
   1.628 +
   1.629 +
   1.630 +The parallelism primitives executed by a program do not control change in
   1.631 +scheduling states. They merely communicate messages to the Master, via a VMS
   1.632 +supplied primitive. Inside the Master, the plugin's parallelism construct
   1.633 +implementation processes the message. Based on that, it performs changes in
   1.634 +state from Blocked$\rightarrow$Ready, creates new VPs, and dissipates existing
   1.635 +VPs. Most communication from Slave to Master requires the VP to suspend when
   1.636 +it sends the message. A few messages, like creating new Slave may be sent
   1.637 +without suspending.
   1.638 +
   1.639 +The suspend primitive decouples local physical time from Virtual time.
   1.640 +Execution causes immediate transition to Stalled in physical time, then the
   1.641 +Master performs Animated$\rightarrow$Blocked, fixing that transition in
   1.642 +Virtual time. The only relationship is causality. This weak relation is what
   1.643 +allows suspension-points to be serialized in Virtual time, which in turn is
   1.644 +what allows using sequential algorithms to implement parallelism constructs.
   1.645 +
   1.646 +
   1.647 +\subsection{Plugins}
   1.648 +
   1.649 +\begin{figure}[ht]
   1.650 +  \includegraphics{../figures/VMS-core__plugins.png}
   1.651 +  \caption
   1.652 + {
   1.653 +  The Master has been split into a generic core and a language-specific plug-in.
   1.654 +  The core encapsulates the hardware and remains the same across applications.
   1.655 +  The plug-in is part of the parallelism-construct implementation. It is
   1.656 +  loaded separately onto the hardware and linked to the application when run.
   1.657 + }
   1.658 + \label{figMasterSplit}
   1.659 +\end{figure}
   1.660 +
   1.661 +
   1.662 +The Master entity has two parts, a generic core part and a plugin (Figure \ref{figMasterSplit}).
   1.663 + The core part of the Master is implemented as part of
   1.664 +VMS-core. The plug-in supplies two functions: the communication-handler and
   1.665 +the scheduler, both having a standard prototype. The communication-handler
   1.666 +implements the parallelism constructs, while scheduler assigns VPs to cores.
   1.667 +
   1.668 +An {\em{instance}} of a plugin is created as part of initializing an
   1.669 +application, and the instance holds the semantic and scheduling state for that
   1.670 +run of the application. This state, combined with the virtual processor states
   1.671 +of the slaves created during that application run, represents progress of the
   1.672 +work of the application. \ For example, multi-tasking is performed simply by
   1.673 +the Master switching among plug-in instances when it has a resource to offer
   1.674 +to a scheduler. The parallelism-semantic state holds all information needed to
   1.675 +resume (hardware state, such as TLB and cache-tags is inside VMS-core).
   1.676 +
   1.677 +
   1.678 +
   1.679 +\section{Internal Workings of Our Implementation}
   1.680 +\label{secInternal}
   1.681 +
   1.682 +We name the elements of our example implementation and describe their logical
   1.683 +function, then relate them to the abstract model. We then step through the
   1.684 +operation of the elements.
   1.685 +
   1.686 +{\bf Elements and Their Logical Function:\ }As illustrated in Figure \ref{figInternals},
   1.687 +our VMS implementation is organized around physical cores.
   1.688 + Each core has its own {\em{master
   1.689 +virtual-processor}}, \texttt{masterVP}, and a {\em{physical-core controller}}, which communicate via a set of
   1.690 +scheduling slots, \texttt{schedSlot}. The Master in the abstract definition
   1.691 +is implemented by the multiple \texttt{masterVP}s plus a particular plugin
   1.692 +instance with its shared parallelism-semantic state (seen at the top).
   1.693 +
   1.694 +On a given core, only one of: the core-controller, \texttt{masterVP}, or a
   1.695 +slave VP, is animated at any point in local physical time. Each
   1.696 +\texttt{masterVP} animates the same function, called
   1.697 +\texttt{master\_loop}, and each slave VP animates a function from the
   1.698 +application, starting with the top-level function the slave is created with,
   1.699 +and following its call sequence. The core controller is implemented here as a
   1.700 +Linux pthread that runs the \texttt{core\_loop} function.
   1.701 +
   1.702 +Switching between VPs is done by executing a VMS primitive that suspends the
   1.703 +VP. This switches the physical core over to the controller, by jumping to the
   1.704 +start of the \texttt{core\_loop} function, which chooses the next VP and
   1.705 +switches to that (switching is detailed in Section \ref{secApp} Figure \ref{figAssembly}).
   1.706 +
   1.707 +{\bf Relation to Abstract Model:\ }We chose to implement the Master entity
   1.708 +of the model by a set of \texttt{masterVP}s, plus plug-in functions and
   1.709 +shared parallelism-semantic state. What we call VMS-core consists of this
   1.710 +implementation of the Master, plus the core-controllers, plus the VMS
   1.711 +primitive libraries, for creating new VPs and dissipating existing VPs, suspending VPs,
   1.712 +and communicating from slave VP to Master. In Figure \ref{figInternals},
   1.713 +everything in green is part of VMS-core, while the plugin is in red, and
   1.714 +application code appears as blue, inside the slave VP.
   1.715 +
   1.716 +Virtual time in the model is implemented via a combination of four things: a
   1.717 +\texttt{masterLock} (not shown) that guarantees non-overlap of
   1.718 +\texttt{masterVP} trace-segments; the \texttt{master\_loop} which performs
   1.719 +transition Animated$\rightarrow$Blocked; the \texttt{comm\_handler\_fn}
   1.720 +which performs Blocked$\rightarrow$Ready and the \texttt{scheduler\_fn}
   1.721 +which performs Ready$\rightarrow$Animated. \ Each state transition is one step
   1.722 +of Virtual time; is guaranteed sequential by the non-overlap of
   1.723 +\texttt{masterVP} trace segments; and is global due to being in
   1.724 +parallelism-semantic state that is shared (top of Figure \ref{figInternals}).
   1.725 +
   1.726 +Transitions Progressing$\rightleftarrows$Stalled within the Animated state are
   1.727 +invisible to the parallelism semantics, the Master, and Virtual time, and so
   1.728 +have no effect on the elements seen.
   1.729 +
   1.730 +
   1.731 +\begin{figure*}[!t]
   1.732 +  \includegraphics[width=5in]{../figures/VMS-core__internal_workings.png}
   1.733 +  \caption
   1.734 +  { Internal elements of our example VMS implementation
   1.735 +  }
   1.736 +  \label{figInternals}
   1.737 +\end{figure*}
   1.738 +
   1.739 +{\bf Steps of Operation:\ }The steps of operation are numbered, in Figure \ref{figInternals}.
   1.740 + Taking them in order, 1) \texttt{master\_loop} scans
   1.741 +the scheduling slots to see which ones' slaves have suspended since the
   1.742 +previous scan. \ 2) It hands these to the \texttt{comm\_handler\_fn} plugged
   1.743 +in (which equals transition Animated$\rightarrow$Blocked). \ 3) The VP has a
   1.744 +request attached, and data in it causes \ the \texttt{comm\_handler\_fn}
   1.745 +to manipulate data structures in the shared parallelism-semantic state. \
   1.746 +These structures hold all the slaves in the blocked state (code-level detail
   1.747 +in Figure \ref{figReqHdlr}, Section \ref{secApp}). \ 4) Some requests cause slaves to be moved to a
   1.748 +\texttt{readyQ} on one of the cores (Blocked$\rightarrow$Ready). Which
   1.749 +core's \texttt{readyQ} receives the slave is under plugin control,
   1.750 +determined by a combination of request contents, semantic state and physical
   1.751 +machine state. 5) During the scan, the \texttt{master\_loop} also looks for
   1.752 +empty slots, and for each calls the \texttt{scheduler\_fn} plugged in. It
   1.753 +chooses a slave from the \texttt{readyQ} on the core animating
   1.754 +\texttt{master\_loop}. \ 6) The \texttt{master\_loop} then places the
   1.755 +slave VP's pointer into the scheduling slot (Ready$\rightarrow$Animated),
   1.756 +making it available to the \texttt{core\_loop}. 7) When done with the scan,
   1.757 +\texttt{masterVP} suspends, switching animation back to the
   1.758 +\texttt{core\_loop}. \ 8) \texttt{core\_loop} takes slave VPs out of the
   1.759 +slots, then 9) switches animation to them. \ 10) When a slave self-suspends,
   1.760 +animation returns to the \texttt{core\_loop} (detail in code in Figure 9),
   1.761 +which picks another, until 11) all slots are empty and the
   1.762 +\texttt{core\_loop} switches animation to the \texttt{masterVP}.
   1.763 +
   1.764 +{\bf Enabling sequential implementation of parallelism semantics:\ }All of
   1.765 +that happens on each core separately, but in this particular implementation we
   1.766 +use a central \texttt{masterLock} to ensure that only one core's
   1.767 +\texttt{masterVP} can be active at any time.  This guarantees non-overlap
   1.768 +of trace-segments from different \texttt{masterVP}s, allowing the plugins to
   1.769 +use sequential algorithms, without a performance penalty, as verified in
   1.770 +Section \ref{secResults}.
   1.771 +
   1.772 +Relating this to the abstract model: the parallelism-semantic behavior of the
   1.773 +Master is implemented by the communication handler, in the plugin. It thus
   1.774 +runs in the Master time referred to, in the model, in Section \ref{secAbsModel}. Requests are
   1.775 +sent to the Master by self-suspension of the slaves, but sit idle until the
   1.776 +other slaves in the scheduling slots have also run. This is the passive
   1.777 +behavior of requests that was noted in Section \ref{secAbsModel}, which allows the
   1.778 +\texttt{masterVP}s to remain suspended until needed.  This in turn enables
   1.779 +the \texttt{masterVP}s from different cores to be non-overlapped. It is the
   1.780 +non-overlap that enables the algorithms for the parallelism semantics to be
   1.781 +sequential.
   1.782 +
   1.783 +
   1.784 +
   1.785 +
   1.786 +\section{Code Level View}
   1.787 +\label{secApp}
   1.788 +
   1.789 +To relate the abstract model and the internal elements to application code and
   1.790 +parallelism-library code, we give code snippets that illustrate key features.
   1.791 + We start with the application then work down through the sequence of calls,
   1.792 +to the plugin, using our SSR {\cite{VMSHome}} parallelism-library as an
   1.793 +example.
   1.794 +
   1.795 +In general, applications are either written in terms of a full custom language
   1.796 +that has its own syntax, or a base language with a parallelism library, which
   1.797 +is often called an {\em{embedded language}}.  Our demonstrators, VCilk
   1.798 +{\cite{VMSHome}}, Vthread, and SSR, are all parallelism libraries. A full
   1.799 +custom language would follow the standard practice of performing
   1.800 +source-to-source transform, from custom syntax into C plus parallelism-library
   1.801 +calls.
   1.802 +
   1.803 +{\bf SSR:\ }SSR stands for Synchronous Send-Receive, and details of its
   1.804 +calls and internal implementation will be given throughout this section. It
   1.805 +has two types of construct. The first, called {\em{from-to}} has two calls:
   1.806 +\texttt{SSR\_send\_from\_to} and \texttt{SSR\_receive\_from\_to}, both of
   1.807 +which specify the sending VP as well as the receiving VP. \ The other, called
   1.808 +{\em{of-type}} also has two calls: \texttt{SSR\_\_send\_of\_type\_to} and
   1.809 +\texttt{SSR\_\_receive\_of\_type}, which allow a receiver to accept from
   1.810 +anonymous senders, but select according to type of message.
   1.811 +
   1.812 +
   1.813 +% An example of a double column floating figure using two subfigures.
   1.814 +% (The subfig.sty package must be loaded for this to work.)
   1.815 +% The subfigure \label commands are set within each subfloat command, the
   1.816 +% \label for the overall figure must come after \caption.
   1.817 +% \hfil must be used as a separator to get equal spacing.
   1.818 +% The subfigure.sty package works much the same way, except \subfigure is
   1.819 +% used instead of \subfloat.
   1.820 +%
   1.821 +%\begin{figure*}[!t]
   1.822 +%\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
   1.823 +%\label{fig_first_case}}
   1.824 +%\hfil
   1.825 +%\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
   1.826 +%\label{fig_second_case}}}
   1.827 +%\caption{Simulation results}
   1.828 +%\label{fig_sim}
   1.829 +%\end{figure*}
   1.830 +%
   1.831 +% Note that often IEEE papers with subfigures do not employ subfigure
   1.832 +% captions (using the optional argument to \subfloat), but instead will
   1.833 +% reference/describe all of them (a), (b), etc., within the main caption.
   1.834 +
   1.835 +
   1.836 +{\bf Application View:\ } Figure \ref{figAnimVP} shows snippets of application code, which use the SSR parallelism
   1.837 +library. The most important feature is that all calls take a pointer to the
   1.838 +VP that is animating the call. This is seen at the top of the figure where slave VP creation takes a pointer
   1.839 +to the VP asking for creation. Below that is the standard prototype for top level functions,
   1.840 +showing that the function receives a pointer to the VP it is the top level function for.
   1.841 +
   1.842 +The pointer is placed on the stack by VMS when it creates the VP, and is the means by
   1.843 +which the application comes into possession of the pointer. This animating VP is
   1.844 +passed to all library calls made from there. For example, the bottom shows a pointer to the
   1.845 +animating VP placed in the position of sender in
   1.846 +the \texttt{send} construct call.  Correspondingly, for the \texttt{receive} construct,
   1.847 +the position of receiving VP is filled by the VP animating the call.
   1.848 +
   1.849 +\begin{figure}[ht]
   1.850 +{\noindent
   1.851 +{\scriptsize
   1.852 +{\small Creating a new processor:}
   1.853 + \begin{verbatim}
   1.854 +newProcessor = SSR__create_procr( &top_VP_fn,
   1.855 + paramsPtr, animatingVP ); \end{verbatim}
   1.856 +
   1.857 +{\small prototype for the top level function:}
   1.858 + \begin{verbatim}
   1.859 +top_VP_fn( void *parameterStrucPtr, VirtProcr 
   1.860 + *animatingVP ); \end{verbatim}
   1.861 +
   1.862 +{\small handing animating VP to parallelism constructs:}
   1.863 + \begin{verbatim}
   1.864 +SSR__send_from_to( messagePtr, animatingVP, 
   1.865 + receivingVP );
   1.866 +messagePtr = SSR__receive_from_to( sendingVP,
   1.867 + animatingVP ); \end{verbatim}
   1.868 +}
   1.869 +}
   1.870 +\caption
   1.871 +{
   1.872 +Application code snippets showing that all calls to the parallelism library
   1.873 +take the VP animating that call as a parameter.
   1.874 +}
   1.875 +\label{figAnimVP}
   1.876 +\end{figure}
   1.877 +
   1.878 +Relating these to the internal elements of our implementation, the
   1.879 + \texttt{animatingVP} suspends inside each of these
   1.880 +calls, passing a request (generated in the library) to one of the \texttt{masterVP}s.
   1.881 + The \texttt{masterVP} then calls the \texttt{comm-handler}
   1.882 + plugin, and so on, as described in Section  \ref{secInternal}.
   1.883 +
   1.884 +For the \texttt{SSR\_\_create\_processor} call, the comm-handler
   1.885 + in turn calls a VMS primitive to perform the creation.
   1.886 +  The primitive places a pointer to the newly created VP onto its stack, so that when
   1.887 +\texttt{top\_VP\_fn} is later animated, it sees the VP-pointer as a
   1.888 +parameter passed to it. \ All
   1.889 +application code is either such a top-level function, or has one at the root
   1.890 +of the call-stack.
   1.891 +
   1.892 +The send and receive calls both suspend their animating VP. When both have
   1.893 +been called, the communication handler pairs them up and resumes both. This
   1.894 +ties time-lines together, invoking the VMS guarantee. Both
   1.895 +application-functions know, because of the VMS guarantee (Section \ref{secAbsModel}), that
   1.896 +writes to shared variables made before the send call by the sender are visible
   1.897 +to the receiver after the receive call. This is the programmer's view of tying
   1.898 +together the local time-lines of two different VPs, as defined in Section \ref{secAbsModel}.
   1.899 +
   1.900 +
   1.901 +{\bf Concurrency-Library View:\ }A parallelism library function, in
   1.902 +general, only creates a request, sends it, and returns, as seen below.  To
   1.903 +send a request, it uses the combined request-and-suspend VMS primitive that
   1.904 +attaches the request then suspends the VP.  The primitive requires the
   1.905 +pointer to the VP, to attach the request and to suspend it.
   1.906 +
   1.907 +
   1.908 +\begin{figure}[ht]
   1.909 +{\noindent
   1.910 +{\scriptsize
   1.911 + \begin{verbatim}
   1.912 +void * SSR__receive_from_to( VirtProcr *sendVP,
   1.913 + VirtProcr *receiveVP )
   1.914 + { SSRSemReq  reqData;
   1.915 +   reqData.receiveVP = receiveVP;
   1.916 +   reqData.sendVP    = sendVP;
   1.917 +   reqData.reqType   = receive_from_to;
   1.918 +   VMS__send_sem_request( &reqData, receiveVP );
   1.919 +   return receiveVP->dataReturnedFromRequest;
   1.920 + } \end{verbatim}
   1.921 +}
   1.922 +}
   1.923 +\caption{Implementation of SSR's receive\_from\_to library function.}
   1.924 +\label{figImplLib}
   1.925 +\end{figure}
   1.926 +
   1.927 +
   1.928 +In Figure \ref{figImplLib}, notice that the request's data is on the stack of the virtual
   1.929 +processor that's animating the call, which is the \texttt{receiveVP}.  The
   1.930 +\texttt{VMS\_\_send\_sem\_request} suspends this VP, which changes the
   1.931 +physical core's stack pointer to a different stack. So the request data is
   1.932 +guaranteed to remain undisturbed while the VP is suspended.
   1.933 +
   1.934 +Figure \ref{figAssembly} shows the implementation of the VMS suspend primitive. As seen in
   1.935 +Figure \ref{figInternals}, suspending the \texttt{receiveVP} involves
   1.936 +switching to the \texttt{core\_loop}. In our implementation, this is done by
   1.937 +switching to the stack of the pthread pinned to the physical core and then
   1.938 +jumping to the start-point of \texttt{core\_loop}.
   1.939 +
   1.940 +This code uses standard techniques commonly employed in co-routine
   1.941 +implementations. Tuning effort spent in \texttt{core\_loop} is inherited by
   1.942 +all applications.
   1.943 +
   1.944 +
   1.945 +\begin{figure}[ht]
   1.946 +{\noindent
   1.947 +{\scriptsize
   1.948 + \begin{verbatim}
   1.949 +VMS__suspend_procr( VirtProcr *animatingVP )
   1.950 + { animatingVP->resumeInstrAddr = &&ResumePt;
   1.951 +    //GCC takes addr of label
   1.952 +   animatingVP->schedSlotAssignedTo->
   1.953 +    isNewlySuspended = TRUE;
   1.954 +    //for master_loop to see
   1.955 +   <assembly code stores current physical core's
   1.956 +     stack reg into animatingVP struct>
   1.957 +   <assembly code loads stack reg with core_loop
   1.958 +     stackPtr, which was saved into animatingVP>
   1.959 +   <assembly code jmps to core_loop start instr
   1.960 +     addr, which was also saved into animatingVP>
   1.961 + ResumePt:
   1.962 +   return;
   1.963 + } \end{verbatim}
   1.964 +}
   1.965 +}
   1.966 +  \caption
   1.967 +{Implementation of VMS suspend processor.
   1.968 +Re-animating the virtual processor reverses this sequence. \ It saves the
   1.969 +\texttt{core\_loop}'s resume instr-addr and stack ptr into the VP structure,
   1.970 +then loads the VP's stack ptr and jmps to its \texttt{resumeInstrAddr}.
   1.971 +}
   1.972 +\label{figAssembly}
   1.973 +\end{figure}
   1.974 +
   1.975 +
   1.976 +{\bf Plugin View:\ }SSR's communication handler dispatches on the
   1.977 +\texttt{reqType} field of the request data, as set by the
   1.978 +\texttt{SSR\_\_receive\_from\_to} code. It calls the handler code in
   1.979 +Figure \ref{figReqHdlr}. This constructs a hash-key, by concatenating the from-VP's pointer
   1.980 +with the to-VP's pointer. Then it looks-up that key in the hash-table that SSR uses
   1.981 +to match sends with receives, which is in the shared semantic state seen at
   1.982 +the top of Figure \ref{figInternals} in Section \ref{secInternal}.
   1.983 +
   1.984 +The most important feature in Figure \ref{figReqHdlr} is that both send and receive
   1.985 +will construct the same key, so will find the same
   1.986 +hash entry.  Whichever request is handled first in Virtual time will see the
   1.987 +hash entry empty, and save itself in that entry.  The second to arrive
   1.988 +sees the waiting request and then resumes both VPs, by putting them into their
   1.989 +\texttt{readyQ}s.
   1.990 +
   1.991 +Access to the shared hash
   1.992 +table can be considered private, as in a sequential algorithm.  This is because
   1.993 + our VMS-core implementation ensures that only
   1.994 +one handler on one core is executing at a time. 
   1.995 +
   1.996 +
   1.997 +\begin{figure}[ht]
   1.998 +{\noindent
   1.999 +{\scriptsize
  1.1000 + \begin{verbatim}
  1.1001 +handle_receive_from_to( VirtProcr *requestingVP,
  1.1002 + SSRSemReq *reqData, SSRSemEnv *semEnv )
  1.1003 + { commHashTbl = semEnv->communicatingVPHashTable;
  1.1004 +   key[0] = reqData->receiveVP;   key[1] = 
  1.1005 +    reqData->sendVP; //send uses same key
  1.1006 +   waitingReqData = lookup_and_remove( key,
  1.1007 +    commHashTbl );  //get waiting request
  1.1008 +   if( waitingReqData != NULL )
  1.1009 +    { resume_virt_procr( waitingReqData->sendVP );
  1.1010 +      resume_virt_procr( waitingReqData->
  1.1011 +       receiveVP );
  1.1012 +    }
  1.1013 +   else
  1.1014 +      insert( key, reqData, commHashTbl );
  1.1015 +       //receive is first to arrive, make it wait
  1.1016 + } \end{verbatim}
  1.1017 +}
  1.1018 +}
  1.1019 +  \caption
  1.1020 +{Pseudo-code of communication-handler for
  1.1021 +\texttt{receive\_from\_to} request type. The \texttt{semEnv} is a pointer
  1.1022 +to the shared parallelism-semantic state seen at the top of Figure
  1.1023 +\ref{figInternals}.
  1.1024 +}
  1.1025 +\label{figReqHdlr}
  1.1026 +\end{figure}
  1.1027 +
  1.1028 +
  1.1029 +
  1.1030 +
  1.1031 +\section{Results}
  1.1032 +\label{secResults}
  1.1033 +
  1.1034 +{\bf Setup:\ }We implemented blocked dense matrix multiply with right
  1.1035 +sub-matrices copied to transposed form. We ran on a 1 socket by 4 core
  1.1036 +Core2Quad 2.4Ghz chip.
  1.1037 +
  1.1038 +{\bf Implementation-Time:\ }As shown in Table 1, time to implement the
  1.1039 +three parallel libraries averages 2 days each. As an example of productivity,
  1.1040 +adding nested transactions, parallel singleton, and atomic function-execution
  1.1041 +to SSR required a single afternoon, totaling less than 100 lines of C code.
  1.1042 +
  1.1043 +
  1.1044 +\begin{table}[ht]
  1.1045 +\caption
  1.1046 +{Person-days to design, code, and
  1.1047 +  test each parallelism library. L.O.C. is lines of (original) C code, excluding libraries and
  1.1048 +  comments.
  1.1049 +}
  1.1050 +\label{tabPersonDaysLang}
  1.1051 +\begin{center}
  1.1052 +\begin{tabular}{llll}
  1.1053 +    & SSR & Vthread & VCilk\\
  1.1054 +    Design & 4 & 1 & 0.5\\
  1.1055 +    Code & 2 & 0.5 & 0.5\\
  1.1056 +    Test & 1 & 0.5 & 0.5\\
  1.1057 +    L.O.C. & 470 & 290 & 310
  1.1058 +  \end{tabular}
  1.1059 +\end{center}
  1.1060 +\end{table}
  1.1061 +
  1.1062 +
  1.1063 +{\bf Execution Performance:\ }Performance of VMS is seen in Table
  1.1064 +\ref{tabOverheadCycles}. The code is not optimized, but rather written
  1.1065 +to be easy to understand and modify. The majority of the plugin time
  1.1066 +is lost to cache misses because the shared parallelism-semantic state moves
  1.1067 +between cores on a majority of accesses. Acquisition of the master lock is slow due to the hardware
  1.1068 +implementing the CAS instruction.
  1.1069 +
  1.1070 +Existing techniques will likely improve performance, such
  1.1071 +as localizing semantic data to cores, splitting malloc across the cores,
  1.1072 +pre-allocating slabs that are recycled, and pre-fetching. However, in many cases, several hundred
  1.1073 +nano-seconds per task is as optimal as the applications can benefit from.
  1.1074 +
  1.1075 +\begin{table}[ht]
  1.1076 +\caption
  1.1077 +{Cycles of overhead, per scheduled
  1.1078 +    slave. ``comp only'' is perfect memory, ``comp + mem'' is actual cycles.
  1.1079 +    ``Plugin-concur'' only concurrency requests, ``plugin-all'' includes
  1.1080 +    create and malloc requests. Two significant digits due to variability.
  1.1081 +}
  1.1082 +\label{tabOverheadCycles}
  1.1083 +\begin{center}
  1.1084 +\begin{tabular}{|l|ll|r|r|}
  1.1085 +\hline
  1.1086 +    &  & comp & comp\\
  1.1087 +    &  & only & +mem\\
  1.1088 +    VMS Only & \texttt{master\_loop} &  91 &  \ 110\\
  1.1089 +    & switch VPs  & 77 &  \ 130\\
  1.1090 +    & (malloc) & 160 & 2300\\
  1.1091 +    & (create VP)  & 540 & 3800\\
  1.1092 +\hline
  1.1093 + Language: &  &  & \\
  1.1094 + SSR & plugin -- concur & 190 & 540\\
  1.1095 + & plugin -- all & 530 & 2200\\
  1.1096 + & lock &  &  250\\
  1.1097 + Vthread & plugin -- concur & 66 & 710\\
  1.1098 + & plugin -- all & 180 & 1500\\
  1.1099 + & lock &  &  250\\
  1.1100 + VCilk & plugin -- concur & 65 & 260\\
  1.1101 + & plugin -- all & 330 & 1800\\
  1.1102 + & lock &  &  250\\
  1.1103 +\hline
  1.1104 +\end{tabular}
  1.1105 +\end{center}
  1.1106 +\end{table}
  1.1107 +
  1.1108 +
  1.1109 +
  1.1110 +{\bf Head to Head:\ }We
  1.1111 +compare our implementation of the \texttt{spawn} and \texttt{sync}
  1.1112 +constructs against Cilk 5.4, on the top in Table
  1.1113 +\ref{tabHeadToHead}, which shows that the same application code has similar
  1.1114 +performance. For large matrices, Cilk 5.4's better use of the memory hierarchy
  1.1115 +achieves 23\% better performance. However, for small matrices, VCilk is better,
  1.1116 + with a factor 2 lower overhead. Cilk 5.4 does not allow controlling the number of spawn events it
  1.1117 +actually executes, and chooses to run smaller matrices sequentially, limiting
  1.1118 +our comparison.
  1.1119 +
  1.1120 +When comparing to pthreads, our VMS based implementation has more than an
  1.1121 +order of magnitude better overhead per invocation of mutex or condition
  1.1122 +variable functionality, as seen on the bottom of Table \ref{tabHeadToHead}.
  1.1123 +Applications that inherently have short trace segments will synchronize often
  1.1124 +and benefit the most from Vthread.
  1.1125 +
  1.1126 +
  1.1127 +
  1.1128 +\begin{table}[ht]
  1.1129 +\caption
  1.1130 +{On top, exe time in seconds for MM. Below, overhead for pthread vs Vthread. First column is cycles
  1.1131 +  for perfect memory and second is total measured cycles. pthread cycles are
  1.1132 +  deduced from round-trip experiments.
  1.1133 +}
  1.1134 +\label{tabHeadToHead}
  1.1135 +\begin{center}
  1.1136 +\begin{tabular}{|l@{\ }|@{\ }lr|}
  1.1137 +\hline
  1.1138 +\rule{0pt}{12pt}
  1.1139 +    Matrix size&Lang.&sec.\\
  1.1140 +[2pt]\hline
  1.1141 +    81x81 & Cilk & 0.017\\
  1.1142 +    & VCilk & 0.008\\
  1.1143 +\hline
  1.1144 +    324x324 & Cilk & 0.13\\
  1.1145 +    & VCilk & 0.13\\
  1.1146 +\hline
  1.1147 +    648x648 & Cilk & 0.71\\
  1.1148 +    & VCilk & 0.85\\
  1.1149 +\hline
  1.1150 +    1296x1296 & Cilk & 4.8\\
  1.1151 +    & VCilk & 6.2 \\
  1.1152 +[2pt]\hline
  1.1153 +\end{tabular}
  1.1154 +\begin{tabular}{c}
  1.1155 +\begin{tabular}{|l|rr|r|r|}
  1.1156 +\hline
  1.1157 +    operation & \multicolumn{2}{c|}{Vthread} & pthread & ratio\\
  1.1158 +\hline
  1.1159 +    & comp & total &  & \\
  1.1160 +    & only &  &  & \\
  1.1161 +[2pt]\hline
  1.1162 +    mutex\_lock & 85 & 1050 & 50,000 & 48:1\\
  1.1163 +    mutex\_unlock & 85 & 610 & 45,000 & 74:1\\
  1.1164 +    cond\_wait  & 85 & 850 & 60,000 & 71:1\\
  1.1165 +    cond\_signal & 90 & 650 & 60,000 & 92:1\\
  1.1166 +\hline
  1.1167 +\end{tabular}\\
  1.1168 +\end{tabular}
  1.1169 +\end{center}
  1.1170 +\end{table}
  1.1171 +
  1.1172 +\section{Conclusion}\label{secConclusion}
  1.1173 +
  1.1174 +We have shown an alternative to the Thread model that enables easier-to-use
  1.1175 +parallelism constructs by splitting
  1.1176 +the scheduler open, to accept new parallelism constructs in the form of
  1.1177 +plugins. This gives the language control over assigning virtual
  1.1178 +processors to physical cores, for performance, debugging, and flexibility
  1.1179 +benefits. Parallelism constructs of languages are implementable using
  1.1180 +sequential algorithms, within a matter of days, while maintaining low run-time
  1.1181 +overhead, on the order of a few hundred nano-seconds per concurrency
  1.1182 +operation.
  1.1183 +
  1.1184 +\bibliography{Bib_for_papers}
  1.1185 +
  1.1186 +\end{document}