Me@0: 
Me@0: 
Me@0: \documentclass[conference]{IEEEtran}
Me@0: %
Me@0: \usepackage{makeidx,geometry,amssymb,graphicx,calc,ifthen}
Me@0: %
Me@0: 
Me@0: % *** CITATION PACKAGES ***
Me@0: %
Me@0: %\usepackage{cite}
Me@0: % cite.sty was written by Donald Arseneau
Me@0: % V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
Me@0: % \cite{} output to follow that of IEEE. Loading the cite package will
Me@0: % result in citation numbers being automatically sorted and properly
Me@0: % "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
Me@0: % cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
Me@0: % \cite will automatically add leading space, if needed. Use cite.sty's
Me@0: % noadjust option (cite.sty V3.8 and later) if you want to turn this off.
Me@0: % cite.sty is already installed on most LaTeX systems. Be sure and use
Me@0: % version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
Me@0: % not currently provide for hyperlinked citations.
Me@0: % The latest version can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
Me@0: % The documentation is contained in the cite.sty file itself.
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** GRAPHICS RELATED PACKAGES ***
Me@0: %
Me@0: \ifCLASSINFOpdf
Me@0:   % \usepackage[pdftex]{graphicx}
Me@0:   % declare the path(s) where your graphic files are
Me@0:   % \graphicspath{{../pdf/}{../jpeg/}}
Me@0:   % and their extensions so you won't have to specify these with
Me@0:   % every instance of \includegraphics
Me@0:   % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
Me@0: \else
Me@0:   % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
Me@0:   % will default to the driver specified in the system graphics.cfg if no
Me@0:   % driver is specified.
Me@0:   % \usepackage[dvips]{graphicx}
Me@0:   % declare the path(s) where your graphic files are
Me@0:   % \graphicspath{{../eps/}}
Me@0:   % and their extensions so you won't have to specify these with
Me@0:   % every instance of \includegraphics
Me@0:   % \DeclareGraphicsExtensions{.eps}
Me@0: \fi
Me@0: % graphicx was written by David Carlisle and Sebastian Rahtz. It is
Me@0: % required if you want graphics, photos, etc. graphicx.sty is already
Me@0: % installed on most LaTeX systems. The latest version and documentation can
Me@0: % be obtained at: 
Me@0: % http://www.ctan.org/tex-archive/macros/latex/required/graphics/
Me@0: % Another good source of documentation is "Using Imported Graphics in
Me@0: % LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
Me@0: % epslatex.pdf at: http://www.ctan.org/tex-archive/info/
Me@0: %
Me@0: % latex, and pdflatex in dvi mode, support graphics in encapsulated
Me@0: % postscript (.eps) format. pdflatex in pdf mode supports graphics
Me@0: % in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
Me@0: % that all non-photo figures use a vector format (.eps, .pdf, .mps) and
Me@0: % not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
Me@0: % which can result in "jaggedy"/blurry rendering of lines and letters as
Me@0: % well as large increases in file sizes.
Me@0: %
Me@0: % You can find documentation about the pdfTeX application at:
Me@0: % http://www.tug.org/applications/pdftex
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** MATH PACKAGES ***
Me@0: %
Me@0: %\usepackage[cmex10]{amsmath}
Me@0: % A popular package from the American Mathematical Society that provides
Me@0: % many useful and powerful commands for dealing with mathematics. If using
Me@0: % it, be sure to load this package with the cmex10 option to ensure that
Me@0: % only type 1 fonts will utilized at all point sizes. Without this option,
Me@0: % it is possible that some math symbols, particularly those within
Me@0: % footnotes, will be rendered in bitmap form which will result in a
Me@0: % document that can not be IEEE Xplore compliant!
Me@0: %
Me@0: % Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
Me@0: % thus preventing page breaks from occurring within multiline equations. Use:
Me@0: %\interdisplaylinepenalty=2500
Me@0: % after loading amsmath to restore such page breaks as IEEEtran.cls normally
Me@0: % does. amsmath.sty is already installed on most LaTeX systems. The latest
Me@0: % version and documentation can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** SPECIALIZED LIST PACKAGES ***
Me@0: %
Me@0: %\usepackage{algorithmic}
Me@0: % algorithmic.sty was written by Peter Williams and Rogerio Brito.
Me@0: % This package provides an algorithmic environment fo describing algorithms.
Me@0: % You can use the algorithmic environment in-text or within a figure
Me@0: % environment to provide for a floating algorithm. Do NOT use the algorithm
Me@0: % floating environment provided by algorithm.sty (by the same authors) or
Me@0: % algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
Me@0: % algorithm float types and packages that provide these will not provide
Me@0: % correct IEEE style captions. The latest version and documentation of
Me@0: % algorithmic.sty can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
Me@0: % There is also a support site at:
Me@0: % http://algorithms.berlios.de/index.html
Me@0: % Also of interest may be the (relatively newer and more customizable)
Me@0: % algorithmicx.sty package by Szasz Janos:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** ALIGNMENT PACKAGES ***
Me@0: %
Me@0: %\usepackage{array}
Me@0: % Frank Mittelbach's and David Carlisle's array.sty patches and improves
Me@0: % the standard LaTeX2e array and tabular environments to provide better
Me@0: % appearance and additional user controls. As the default LaTeX2e table
Me@0: % generation code is lacking to the point of almost being broken with
Me@0: % respect to the quality of the end results, all users are strongly
Me@0: % advised to use an enhanced (at the very least that provided by array.sty)
Me@0: % set of table tools. array.sty is already installed on most systems. The
Me@0: % latest version and documentation can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/required/tools/
Me@0: 
Me@0: 
Me@0: %\usepackage{mdwmath}
Me@0: %\usepackage{mdwtab}
Me@0: % Also highly recommended is Mark Wooding's extremely powerful MDW tools,
Me@0: % especially mdwmath.sty and mdwtab.sty which are used to format equations
Me@0: % and tables, respectively. The MDWtools set is already installed on most
Me@0: % LaTeX systems. The lastest version and documentation is available at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/
Me@0: 
Me@0: 
Me@0: % IEEEtran contains the IEEEeqnarray family of commands that can be used to
Me@0: % generate multiline equations as well as matrices, tables, etc., of high
Me@0: % quality.
Me@0: 
Me@0: 
Me@0: %\usepackage{eqparbox}
Me@0: % Also of notable interest is Scott Pakin's eqparbox package for creating
Me@0: % (automatically sized) equal width boxes - aka "natural width parboxes".
Me@0: % Available at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** SUBFIGURE PACKAGES ***
Me@0: %\usepackage[tight,footnotesize]{subfigure}
Me@0: % subfigure.sty was written by Steven Douglas Cochran. This package makes it
Me@0: % easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
Me@0: % work, it is a good idea to load it with the tight package option to reduce
Me@0: % the amount of white space around the subfigures. subfigure.sty is already
Me@0: % installed on most LaTeX systems. The latest version and documentation can
Me@0: % be obtained at:
Me@0: % http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
Me@0: % subfigure.sty has been superceeded by subfig.sty.
Me@0: 
Me@0: 
Me@0: 
Me@0: %\usepackage[caption=false]{caption}
Me@0: %\usepackage[font=footnotesize]{subfig}
Me@0: % subfig.sty, also written by Steven Douglas Cochran, is the modern
Me@0: % replacement for subfigure.sty. However, subfig.sty requires and
Me@0: % automatically loads Axel Sommerfeldt's caption.sty which will override
Me@0: % IEEEtran.cls handling of captions and this will result in nonIEEE style
Me@0: % figure/table captions. To prevent this problem, be sure and preload
Me@0: % caption.sty with its "caption=false" package option. This is will preserve
Me@0: % IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
Me@0: % (recommended due to many improvements over 1.2) of subfig.sty supports
Me@0: % the caption=false option directly:
Me@0: %\usepackage[caption=false,font=footnotesize]{subfig}
Me@0: %
Me@0: % The latest version and documentation can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
Me@0: % The latest version and documentation of caption.sty can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/caption/
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** FLOAT PACKAGES ***
Me@0: %
Me@0: %\usepackage{fixltx2e}
Me@0: % fixltx2e, the successor to the earlier fix2col.sty, was written by
Me@0: % Frank Mittelbach and David Carlisle. This package corrects a few problems
Me@0: % in the LaTeX2e kernel, the most notable of which is that in current
Me@0: % LaTeX2e releases, the ordering of single and double column floats is not
Me@0: % guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
Me@0: % single column figure to be placed prior to an earlier double column
Me@0: % figure. The latest version and documentation can be found at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/base/
Me@0: 
Me@0: 
Me@0: 
Me@0: %\usepackage{stfloats}
Me@0: % stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
Me@0: % the ability to do double column floats at the bottom of the page as well
Me@0: % as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
Me@0: % LaTeX2e). It also provides a command:
Me@0: %\fnbelowfloat
Me@0: % to enable the placement of footnotes below bottom floats (the standard
Me@0: % LaTeX2e kernel puts them above bottom floats). This is an invasive package
Me@0: % which rewrites many portions of the LaTeX2e float routines. It may not work
Me@0: % with other packages that modify the LaTeX2e float routines. The latest
Me@0: % version and documentation can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
Me@0: % Documentation is contained in the stfloats.sty comments as well as in the
Me@0: % presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
Me@0: % does not allow \baselineskip to stretch. Authors submitting work to the
Me@0: % IEEE should note that IEEE rarely uses double column equations and
Me@0: % that authors should try to avoid such use. Do not be tempted to use the
Me@0: % cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
Me@0: % not format its papers in such ways.
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** PDF, URL AND HYPERLINK PACKAGES ***
Me@0: %
Me@0: %\usepackage{url}
Me@0: % url.sty was written by Donald Arseneau. It provides better support for
Me@0: % handling and breaking URLs. url.sty is already installed on most LaTeX
Me@0: % systems. The latest version can be obtained at:
Me@0: % http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
Me@0: % Read the url.sty source comments for usage information. Basically,
Me@0: % \url{my_url_here}.
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: % *** Do not adjust lengths that control margins, column widths, etc. ***
Me@0: % *** Do not use packages that alter fonts (such as pslatex).         ***
Me@0: % There should be no need to do such things with IEEEtran.cls V1.6 and later.
Me@0: % (Unless specifically asked to do so by the journal or conference you plan
Me@0: % to submit to, of course. )
Me@0: 
Me@0: 
Me@0: % correct bad hyphenation here
Me@0: \hyphenation{op-tical net-works semi-conduc-tor}
Me@0: 
Me@0: 
Me@0: \begin{document}
Me@0: \bibliographystyle{plain}
Me@0: %
Me@0: 
Me@0: \title{The Shape of Future Architectures}
Me@0: 
Me@0: \author
Me@0: {
Me@0:  \IEEEauthorblockN{Sean Halle}
Me@0:  \IEEEauthorblockA
Me@0:  {
Me@0:    University of California at Santa Cruz\\
Me@0:    and INRIA Paris\\
Me@0:    Email: sean.halle@inria.fr
Me@0:  }
Me@0:  \and
Me@0:  \IEEEauthorblockN{Albert Cohen}
Me@0:  \IEEEauthorblockA
Me@0:  { INRIA Paris\\
Me@0:    Email: albert.cohen@infria.fr
Me@0:  }
Me@0: }
Me@0: 
Me@0: 
Me@0: \maketitle             
Me@0: %
Me@0: 
Me@0: \begin{abstract}
Me@0:   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.
Me@0:   
Me@0: 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.
Me@0: 
Me@0: 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 
Me@0: \end{abstract}
Me@0: 
Me@0: \section{Motivation}
Me@0: 
Me@0: Threads were invented to be virtual sequential processors, but are 
Me@0: problematic when one has multiple physical cores. Not only
Me@0: are they difficult to use for parallel code, but their parallel performance is poor
Me@0: because they block the language from controlling
Me@0: task placement. The language often knows which cores are likely to already
Me@0: have data in the cache which a new task requires as input. If it had
Me@0: control, the language could place tasks where the data is likely to already
Me@0: reside, reducing communication and increasing performance and power
Me@0: efficiency. A thread replacement is needed that is both easy to use in
Me@0: applications and gives the language control over task placement.
Me@0: 
Me@0: The first question is, what is the easiest to use parallelism construct?  There
Me@0: exist many to choose from: Threads (for legacy reasons); Actors
Me@0: {\cite{Hewitt10}}{\cite{Actors97}}; Components {\cite{ComponentModel00}};
Me@0: process calculi {\cite{hoare78}} {\cite{milner99}};
Me@0: coordination languages {\cite{Gelernter85Linda}}; and new ones
Me@0: continually invented.
Me@0: 
Me@0: We demonstrate in this paper  a thread replacement that lets any such parallelism
Me@0: construct be plugged in.  It is the first extensible hardware abstraction,
Me@0: allowing to plug-in both preferred parallelism constructs and preferred 
Me@0: runtime scheduler. We focus in this introductory paper on
Me@0: the parallelism construct support, illustrating how to implement synchronous
Me@0: \texttt{send}-\texttt{receive} constructs motivated by process calculi,
Me@0: the \texttt{spawn} and \texttt{sync} constructs from Cilk, and even
Me@0: \texttt{mutex} and \texttt{condition variable} constructs from pthreads.
Me@0: However, the schedulers we implemented have no
Me@0: interesting performance optimizations.
Me@0: 
Me@0: The next question is, how much effort is required to implement a plugin? Our
Me@0: mechanism protects the plugin from exposure to concurrency issues, allowing
Me@0: the parallelism constructs to be implemented with sequential algorithms.  It
Me@0: accomplishes this by introducing a ``virtual'' time that sequentializes events
Me@0: that appear, to the program, to be simultaneous.
Me@0: 
Me@0: We call our abstraction Virtualized Master-Slave, or VMS. We demonstrate a user-level
Me@0: implementation in this paper, although it is ideally implemented as the base
Me@0: hardware abstraction of the OS.
Me@0: 
Me@0: It involves subtle concepts related to time in the program vs time in the
Me@0: plugin vs physical time.  We explain it in four levels, starting with an abstract definition
Me@0:  and moving down to implementation.
Me@0: 
Me@0: The first level is the theoretical definition, given in Section \ref{secAbsModel}. Second is the elements
Me@0: of our implementation and how they relate to the theoretical definition, in Section \ref{secInternal}.
Me@0: Third is the application code point of view, in Section \ref{secApp}, which is tied back to both
Me@0: the abstract model and the internal elements. The fourth view,
Me@0: also in Section \ref{secApp}, shows the implementation of the plugin for a parallel
Me@0: construct. Additionally,
Me@0: measurements of effectiveness appear
Me@0: in Section \ref{secResults} and conclusion is in \ref{secConclusion}.
Me@0: 
Me@0: \section{Background and Related Work}
Me@0: 
Me@0: {\bf Side-stepping OS Threads:\ }User-level thread packages and most parallel
Me@0: language runtimes have to side-step OS threads, by pinning one to each core,
Me@0: which effectively gives the user-level package control over the core. Our VMS
Me@0: implementation also does this. We are not claiming in this paper to have the
Me@0: OS level implementation of VMS that the model is capable of -- just the
Me@0: user-space version.
Me@0: 
Me@0: Related work either provides a variation on the Thread model, or is a full
Me@0: language with included parallelism constructs.  For example,
Me@0:  TBB {\cite{TBBHome}} is a user-space thread package with added features.
Me@0: It allows
Me@0: tasks to create other tasks and control when to start their
Me@0: execution. However, one cannot plug in alternate parallelism-control constructs, such as
Me@0: rendez-vous style send and receive, which would have to be made using locks.
Me@0:  Likewise, Cilk {\cite{CILKHome}}
Me@0: provides a simpler and easier to use version of TBB's task scheduler, but is
Me@0: limited to only tree-shaped task graphs. OpenMP {\cite{OpenMPHome}} allows
Me@0:  creating tasks and controlling their execution order,
Me@0: but is a language, not a hardware abstraction.  All of these may
Me@0: alternatively be implemented via plugins to VMS, with similar performance.
Me@0: 
Me@0: In contrast, VMS is the first hardware abstraction that doesn't impose its own concurrency
Me@0: semantics, but rather takes preferred ones as plugins. This makes it not a
Me@0: language itself, but a {\em{support}} mechanism for language level
Me@0: parallelism constructs. The parallelism constructs in Actors, Components,
Me@0: pthreads, and so on may all be implemented as VMS plugins.
Me@0: 
Me@0: {\bf Virtual Processor (VP) Definition:\ }We want to avoid the confusion
Me@0: associated with the terms ``thread'' and ``task'' so will use the term
Me@0: {\em{virtual processor}} (VP), which we define as state in combination with
Me@0: the ability to animate code or {\em{an additional level of virtual
Me@0: processors}}. The state consists of a stack with its contents, a program
Me@0: counter, a pointer to top of stack, and a pointer to the current stack frame.
Me@0: 
Me@0: \section{Abstract Definition of VMS}
Me@0: \label{secAbsModel}
Me@0: 
Me@0: We give an intuitive overview, then add details in the following sub-sections.
Me@0: 
Me@0: {\bf Intuitive Overview:\ }VMS is concerned primarily with time and
Me@0: guarantees about it. This is because parallelism constructs control how the
Me@0: time-lines of different virtual processors intersect. They also guarantee
Me@0: relations of time lines to hardware events.
Me@0: 
Me@0: As an example, consider a program that writes into a data structure in one
Me@0: time-line, then calls a \texttt{send} construct, meanwhile in a different
Me@0: time-line it calls the \texttt{receive} construct then reads the data
Me@0: structure. The constructs should guarantee that all data written before the
Me@0: \texttt{send} is readable in the other time-line after the
Me@0: \texttt{receive}.  VMS provides primitive guarantees, which plugged-in code
Me@0: builds upon to provide such higher-level guarantees.
Me@0: 
Me@0: To support parallelism constructs, VMS provides: primitive operations to create and suspend
Me@0: VPs; a way for plugged-in code to control when each VP is (re)started; and
Me@0: time-related guarantees. These are enforced on all hardware, be it shared
Me@0: memory or distributed, with strong memory consistency or weak.
Me@0: 
Me@0: {\bf Definition in Three Parts:\ }We give the abstract definition in three
Me@0: parts: a definition of the elements of a VMS computation system; a definition
Me@0: of time and the key VMS guarantee; and a definition of virtual processor
Me@0: scheduling states and transitions between them.
Me@0: 
Me@0: The definition we give is for VMS {\em{with plugins present}}. \ Hence, it
Me@0: covers the behavior of all possible parallelism constructs implementable with
Me@0: VMS. The Master mentioned in the definition is an abstract
Me@0: entity, with a plugin present. In practice, this Master entity is implemented
Me@0: as part of a core VMS, and plugins later added. This VMS-core is the
Me@0: hardware abstraction. It hides the physical hardware behind an interface that
Me@0: creates virtual processors and enforces well-defined time-behavior.
Me@0: 
Me@0: 
Me@0: \subsection{The Elements of a VMS Computation System}
Me@0: 
Me@0: \texttt{- }A VMS program has multiple VPs, which are Slaves,
Me@0: each with an independent time-line.
Me@0: 
Me@0: \texttt{- }A schedule of Slaves is generated by a Master
Me@0: entity, from within separate time-line(s).
Me@0: 
Me@0: \texttt{- }A schedule is defined as the set of points at which
Me@0: VPs are (re)animated.
Me@0: 
Me@0: \texttt{- }All semantic parallelism behavior is invoked via
Me@0: communication with the Master.
Me@0: 
Me@0: \texttt{- }Communication with the Master happens by using a
Me@0: model-provided primitive, which causes {\em{voluntary}} suspension of the
Me@0: program's VP.
Me@0: 
Me@0: 
Me@0: What is important here is: that the choice of which VP is animated, at which
Me@0: point, happens in a separate time-line; and that the VPs suspend voluntarily
Me@0: for each parallelism construct. This means that {\em{scheduling is separated
Me@0: from the application code}}, the key point.
Me@0: 
Me@0: The Master entity appears to be a single entity to the slaves, but may be
Me@0: implemented by multiple Master VPs hidden inside the VMS implementation.
Me@0: 
Me@0: VPs use the Master as an intermediary to: semantically communicate with each
Me@0: other; cause creation of new program VPs; and to influence re-animation of
Me@0: VPs. As a subtlety, notice that hardware mechanisms, such as coherent shared
Me@0: memory, allow communication to take place that is not visible to the
Me@0: parallelism constructs. Parallelism constructs must be separately called in
Me@0: order to make use of shared variable communication safe.
Me@0: 
Me@0: {\bf Definitions:\ }VMS is intended only for hardware systems that consist of processing elements
Me@0: connected by communication.  We define a memory-space to be a processing
Me@0: element, albeit without the ability to transform data. We define a
Me@0: {\em{physical core}} to be a processing element that {\em{does}} transform
Me@0: data, and require that it execute a sequential stream of instructions. We
Me@0: define a program-time as the sequence of instructions animated by a Slave VP
Me@0: (which is eventually animated by a physical core). A Slave VP has associated
Me@0: {\em{scheduling state}} that, among other things, relates to how its
Me@0: program-time progresses relative to physical time on the cores.
Me@0: 
Me@0: \subsection{Time in VMS}
Me@0: 
Me@0: \texttt{- }VMS has three levels of time: {\em{Program time}},
Me@0: {\em{ Master time}}, and {\em{Virtual time}}.
Me@0: 
Me@0: \texttt{- }Program time is local to a Slave VP, measured in
Me@0: instruction executions.
Me@0: 
Me@0: \texttt{- }Master time is hidden from the program and is
Me@0: independent from all Program times.
Me@0: 
Me@0: \texttt{- }Virtual time is the ordered set of changes in
Me@0: scheduling state of Slave VPs.
Me@0: 
Me@0: 
Me@0: 
Me@0: What is most important here is that Virtual time defines a global sequential
Me@0: ordering. This ordering is consistent with the key VMS guarantee (given
Me@0: below), and each point in it is computed within Master time.
Me@0: 
Me@0: Also, the independence between program times and master time has subtle
Me@0: advantages. It enables elegant enforcement of the VMS guarantee, and
Me@0: implementation simplifications that become clear after gaining deep
Me@0: implementation knowledge.
Me@0: 
Me@0: In VMS, each event relevant to parallel semantics is tied to a transition of
Me@0: the state of a Slave VP. This means that implementing the behavior of parallel
Me@0: semantics is equivalent to controlling the order of transitions of state of
Me@0: virtual processors.
Me@0: 
Me@0: {\bf Definitions:\ }The stream of instructions in a given program-time is
Me@0: broken into a number of {\em{trace-segments}}, separated by suspension
Me@0: points. Each trace-segment is animated by a single physical core, but not
Me@0: necessarily the same core as animated the other trace segments. A suspend
Me@0: point is created by a Slave VP executing the ``suspend'' primitive provided by
Me@0: VMS. A suspend point has no duration in program time, but has distinct start
Me@0: and end points in virtual time. The end-suspension points of two different
Me@0: program times can be tied together within virtual time, which is called a
Me@0: {\em{tie point}} and has special significance to parallel constructs. The
Me@0: physical-time of a core has no relationship to any program time, except for
Me@0: the various time-guarantees in this definition of VMS.
Me@0: 
Me@0: \begin{figure}[ht]
Me@0:  \includegraphics[width=2.9in]{../figures/Time_in_VMS_1.png}
Me@0:  \caption
Me@0:  {Mapping program time onto Virtual time. \ The
Me@0:   Master controls creation of new program time lines, and ending suspend
Me@0:   points. Here, it has ended two suspend points at a common tie-point.
Me@0:   }
Me@0: \label{figTimeMapping}
Me@0: \end{figure}
Me@0: 
Me@0: {\bf Relating time-lines to each other:\ }Figure \ref{figTimeMapping}
Me@0: illustrates how trace-segments relate to suspend points, and map onto
Me@0: virtual time. A trace segment starts in virtual time where suspend is ended, as seen.
Me@0:  In fact, the two trace segments shown have a common
Me@0: start-point within virtual time. This is because the parallelism semantics
Me@0: chose to start them at the same point -- this is what a tie
Me@0: point is.  A key note is that the lengths in virtual time have no relation to
Me@0: the lengths in program-time. The only defined feature is that those two
Me@0: trace-segments have a common start-point in virtual time. This means that the
Me@0: two suspend points are considered to be tied together.
Me@0: 
Me@0: {\bf The Key VMS guarantee:\ }\label{VMSguarantee}Being tied together
Me@0: means that all physical events that can be observed by both program-times are
Me@0: covered by the key VMS guarantee: any events triggered before the common
Me@0: suspend point in one program time are guaranteed visible in the other program
Me@0: time after the common suspend point. They {\em{might}} be visible before,
Me@0: but it's not guaranteed. In addition, events triggered after the common
Me@0: suspend point in one are guaranteed not visible before the common suspend
Me@0: point in the other. {\em{This two-part guarantee can be considered the heart
Me@0: of VMS.}}
Me@0: 
Me@0: Intuitively, a tie-point separates before it from after such that tied program
Me@0: times agree (illustrated with code in Section \ref{secApp} Figure \ref{figAnimVP}). But the subtlety is
Me@0: that events triggered before the tie-point, {\em{might}} be visible to the
Me@0: other before, and ones triggered after {\em{might not}} be visible to the
Me@0: other after -- physical events triggered before are only guaranteed visible
Me@0: {\em{after}} the tie point, and events after are only guaranteed
Me@0: {\em{not}} visible {\em{before}} the tie point.
Me@0: 
Me@0: This is a form of bounded non-determinism. The pattern of suspension
Me@0: end-points determines which trace-segments overlap in Virtual time, and events
Me@0: triggered in one might be visible in overlapped ones. But no guarantees cover
Me@0: these. If one segment tries to observe, it will see events triggered by
Me@0: overlapped segments in non-deterministic order.
Me@0: 
Me@0: The VMS implementation defines which physical events are covered by the key
Me@0: VMS guarantee (reads/writes, network communication, DMA, I/O).
Me@0: 
Me@0: {\bf Globally consistent sequential order:\ }VMS maps suspend-start,
Me@0: suspend-end, and hence tie-points, to a globally-consistent sequential order
Me@0: in Virtual time. This enables  one of VMS's key benefits: sequential
Me@0: algorithms for parallel constructs.
Me@0: 
Me@0: Tie points define parallel behavior, so an implementation of how to choose tie
Me@0: points equals an implementation of parallel constructs. The Master chooses
Me@0: tie-points, so plugging code to choose tie-points into the Master equals
Me@0: plugging in parallel constructs.
Me@0: 
Me@0: \subsection{Scheduling State}
Me@0: 
Me@0: Scheduling state is used in VMS to organize internal activity, for enforcing
Me@0: the guarantees.
Me@0: 
Me@0: \texttt{- }VPs have three scheduling states: {\em{Animated}},
Me@0: {\em{Blocked}}, {\em{Ready}} (Figure \ref{figStates}).
Me@0: 
Me@0: \texttt{- }VPs in Animated are {\em{allowed}} to advance
Me@0: program-time with {\em{local}} physical time.
Me@0: 
Me@0: \texttt{- }VPs in Blocked and Ready do not advance their
Me@0: program-time.
Me@0: 
Me@0: \texttt{- }Animated has two physical states:
Me@0: {\em{Progressing}} and {\em{Stalled}}.
Me@0: 
Me@0: \texttt{- }VPs in Progressing advance program-time with local
Me@0: physical time, those in Stalled do not (allowing non-semantic suspend).
Me@0: 
Me@0: \texttt{- }Scheduling states are defined in Virtual time only.
Me@0: 
Me@0: \texttt{- }Progressing and Stalled are defined in local
Me@0: physical time only (invisible in Virtual).
Me@0: 
Me@0: 
Me@0: \begin{figure}[h]
Me@0:   \includegraphics{../figures/Scheduling_states_2.png}
Me@0:   \caption{Scheduling states of a slave VP in the VMS model.}
Me@0:   \label{figStates}
Me@0: \end{figure}
Me@0: 
Me@0: Some important points: 1) only VPs Animated can trigger physical events that
Me@0: are seen in other program time-lines; 2) the distinction between Blocked vs
Me@0: Stalled is that a VP has to explicitly execute a VMS primitive operation to
Me@0: enter Blocked, making it part of the semantics of parallelism constructs. In
Me@0: contrast, Stalled happens invisibly, with no effect on semantic behavior. It
Me@0: is due to hardware events hidden inside VMS, such as interrupts.
Me@0: 
Me@0: The Ready state is used to separate the parallelism-construct behavior from
Me@0: the scheduling behavior. It acts as a ``staging area'' for scheduling. VPs
Me@0: placed into this state are {\em{allowed}} to be animated, then the scheduler
Me@0: decides when and where.
Me@0: 
Me@0: A subtle but illustrative point is that actions {\em{outside}} a given
Me@0: program time cause the VP to transition Blocked$\rightarrow$Ready, which
Me@0: contrasts to lock algorithms like spin-locks or Dijkstra's, where the
Me@0: concurrency-related behavior takes place {\em{inside}} program time.
Me@0: 
Me@0: {\bf Transition Between Slave Scheduling States:\ }
Me@0: 
Me@0: \texttt{- }VPs transition states as shown in Figure \ref{figStates}.
Me@0: 
Me@0: \texttt{- }Animated$\rightarrow$Blocked is caused by a Slave VP
Me@0: executing the Suspend VMS primitive.
Me@0: 
Me@0: \texttt{- }Blocked$\rightarrow$Ready is determined by the
Me@0: semantics implemented in the plugin.
Me@0: 
Me@0: \texttt{- }Ready$\rightarrow$Animated is determined by the
Me@0: scheduler in the plugin.
Me@0: 
Me@0: \texttt{- }Transitions in scheduling state have a globally
Me@0: consistent order in Virtual time.
Me@0: 
Me@0: 
Me@0: The parallelism primitives executed by a program do not control change in
Me@0: scheduling states. They merely communicate messages to the Master, via a VMS
Me@0: supplied primitive. Inside the Master, the plugin's parallelism construct
Me@0: implementation processes the message. Based on that, it performs changes in
Me@0: state from Blocked$\rightarrow$Ready, creates new VPs, and dissipates existing
Me@0: VPs. Most communication from Slave to Master requires the VP to suspend when
Me@0: it sends the message. A few messages, like creating new Slave may be sent
Me@0: without suspending.
Me@0: 
Me@0: The suspend primitive decouples local physical time from Virtual time.
Me@0: Execution causes immediate transition to Stalled in physical time, then the
Me@0: Master performs Animated$\rightarrow$Blocked, fixing that transition in
Me@0: Virtual time. The only relationship is causality. This weak relation is what
Me@0: allows suspension-points to be serialized in Virtual time, which in turn is
Me@0: what allows using sequential algorithms to implement parallelism constructs.
Me@0: 
Me@0: 
Me@0: \subsection{Plugins}
Me@0: 
Me@0: \begin{figure}[ht]
Me@0:   \includegraphics{../figures/VMS-core__plugins.png}
Me@0:   \caption
Me@0:  {
Me@0:   The Master has been split into a generic core and a language-specific plug-in.
Me@0:   The core encapsulates the hardware and remains the same across applications.
Me@0:   The plug-in is part of the parallelism-construct implementation. It is
Me@0:   loaded separately onto the hardware and linked to the application when run.
Me@0:  }
Me@0:  \label{figMasterSplit}
Me@0: \end{figure}
Me@0: 
Me@0: 
Me@0: The Master entity has two parts, a generic core part and a plugin (Figure \ref{figMasterSplit}).
Me@0:  The core part of the Master is implemented as part of
Me@0: VMS-core. The plug-in supplies two functions: the communication-handler and
Me@0: the scheduler, both having a standard prototype. The communication-handler
Me@0: implements the parallelism constructs, while scheduler assigns VPs to cores.
Me@0: 
Me@0: An {\em{instance}} of a plugin is created as part of initializing an
Me@0: application, and the instance holds the semantic and scheduling state for that
Me@0: run of the application. This state, combined with the virtual processor states
Me@0: of the slaves created during that application run, represents progress of the
Me@0: work of the application. \ For example, multi-tasking is performed simply by
Me@0: the Master switching among plug-in instances when it has a resource to offer
Me@0: to a scheduler. The parallelism-semantic state holds all information needed to
Me@0: resume (hardware state, such as TLB and cache-tags is inside VMS-core).
Me@0: 
Me@0: 
Me@0: 
Me@0: \section{Internal Workings of Our Implementation}
Me@0: \label{secInternal}
Me@0: 
Me@0: We name the elements of our example implementation and describe their logical
Me@0: function, then relate them to the abstract model. We then step through the
Me@0: operation of the elements.
Me@0: 
Me@0: {\bf Elements and Their Logical Function:\ }As illustrated in Figure \ref{figInternals},
Me@0: our VMS implementation is organized around physical cores.
Me@0:  Each core has its own {\em{master
Me@0: virtual-processor}}, \texttt{masterVP}, and a {\em{physical-core controller}}, which communicate via a set of
Me@0: scheduling slots, \texttt{schedSlot}. The Master in the abstract definition
Me@0: is implemented by the multiple \texttt{masterVP}s plus a particular plugin
Me@0: instance with its shared parallelism-semantic state (seen at the top).
Me@0: 
Me@0: On a given core, only one of: the core-controller, \texttt{masterVP}, or a
Me@0: slave VP, is animated at any point in local physical time. Each
Me@0: \texttt{masterVP} animates the same function, called
Me@0: \texttt{master\_loop}, and each slave VP animates a function from the
Me@0: application, starting with the top-level function the slave is created with,
Me@0: and following its call sequence. The core controller is implemented here as a
Me@0: Linux pthread that runs the \texttt{core\_loop} function.
Me@0: 
Me@0: Switching between VPs is done by executing a VMS primitive that suspends the
Me@0: VP. This switches the physical core over to the controller, by jumping to the
Me@0: start of the \texttt{core\_loop} function, which chooses the next VP and
Me@0: switches to that (switching is detailed in Section \ref{secApp} Figure \ref{figAssembly}).
Me@0: 
Me@0: {\bf Relation to Abstract Model:\ }We chose to implement the Master entity
Me@0: of the model by a set of \texttt{masterVP}s, plus plug-in functions and
Me@0: shared parallelism-semantic state. What we call VMS-core consists of this
Me@0: implementation of the Master, plus the core-controllers, plus the VMS
Me@0: primitive libraries, for creating new VPs and dissipating existing VPs, suspending VPs,
Me@0: and communicating from slave VP to Master. In Figure \ref{figInternals},
Me@0: everything in green is part of VMS-core, while the plugin is in red, and
Me@0: application code appears as blue, inside the slave VP.
Me@0: 
Me@0: Virtual time in the model is implemented via a combination of four things: a
Me@0: \texttt{masterLock} (not shown) that guarantees non-overlap of
Me@0: \texttt{masterVP} trace-segments; the \texttt{master\_loop} which performs
Me@0: transition Animated$\rightarrow$Blocked; the \texttt{comm\_handler\_fn}
Me@0: which performs Blocked$\rightarrow$Ready and the \texttt{scheduler\_fn}
Me@0: which performs Ready$\rightarrow$Animated. \ Each state transition is one step
Me@0: of Virtual time; is guaranteed sequential by the non-overlap of
Me@0: \texttt{masterVP} trace segments; and is global due to being in
Me@0: parallelism-semantic state that is shared (top of Figure \ref{figInternals}).
Me@0: 
Me@0: Transitions Progressing$\rightleftarrows$Stalled within the Animated state are
Me@0: invisible to the parallelism semantics, the Master, and Virtual time, and so
Me@0: have no effect on the elements seen.
Me@0: 
Me@0: 
Me@0: \begin{figure*}[!t]
Me@0:   \includegraphics[width=5in]{../figures/VMS-core__internal_workings.png}
Me@0:   \caption
Me@0:   { Internal elements of our example VMS implementation
Me@0:   }
Me@0:   \label{figInternals}
Me@0: \end{figure*}
Me@0: 
Me@0: {\bf Steps of Operation:\ }The steps of operation are numbered, in Figure \ref{figInternals}.
Me@0:  Taking them in order, 1) \texttt{master\_loop} scans
Me@0: the scheduling slots to see which ones' slaves have suspended since the
Me@0: previous scan. \ 2) It hands these to the \texttt{comm\_handler\_fn} plugged
Me@0: in (which equals transition Animated$\rightarrow$Blocked). \ 3) The VP has a
Me@0: request attached, and data in it causes \ the \texttt{comm\_handler\_fn}
Me@0: to manipulate data structures in the shared parallelism-semantic state. \
Me@0: These structures hold all the slaves in the blocked state (code-level detail
Me@0: in Figure \ref{figReqHdlr}, Section \ref{secApp}). \ 4) Some requests cause slaves to be moved to a
Me@0: \texttt{readyQ} on one of the cores (Blocked$\rightarrow$Ready). Which
Me@0: core's \texttt{readyQ} receives the slave is under plugin control,
Me@0: determined by a combination of request contents, semantic state and physical
Me@0: machine state. 5) During the scan, the \texttt{master\_loop} also looks for
Me@0: empty slots, and for each calls the \texttt{scheduler\_fn} plugged in. It
Me@0: chooses a slave from the \texttt{readyQ} on the core animating
Me@0: \texttt{master\_loop}. \ 6) The \texttt{master\_loop} then places the
Me@0: slave VP's pointer into the scheduling slot (Ready$\rightarrow$Animated),
Me@0: making it available to the \texttt{core\_loop}. 7) When done with the scan,
Me@0: \texttt{masterVP} suspends, switching animation back to the
Me@0: \texttt{core\_loop}. \ 8) \texttt{core\_loop} takes slave VPs out of the
Me@0: slots, then 9) switches animation to them. \ 10) When a slave self-suspends,
Me@0: animation returns to the \texttt{core\_loop} (detail in code in Figure 9),
Me@0: which picks another, until 11) all slots are empty and the
Me@0: \texttt{core\_loop} switches animation to the \texttt{masterVP}.
Me@0: 
Me@0: {\bf Enabling sequential implementation of parallelism semantics:\ }All of
Me@0: that happens on each core separately, but in this particular implementation we
Me@0: use a central \texttt{masterLock} to ensure that only one core's
Me@0: \texttt{masterVP} can be active at any time.  This guarantees non-overlap
Me@0: of trace-segments from different \texttt{masterVP}s, allowing the plugins to
Me@0: use sequential algorithms, without a performance penalty, as verified in
Me@0: Section \ref{secResults}.
Me@0: 
Me@0: Relating this to the abstract model: the parallelism-semantic behavior of the
Me@0: Master is implemented by the communication handler, in the plugin. It thus
Me@0: runs in the Master time referred to, in the model, in Section \ref{secAbsModel}. Requests are
Me@0: sent to the Master by self-suspension of the slaves, but sit idle until the
Me@0: other slaves in the scheduling slots have also run. This is the passive
Me@0: behavior of requests that was noted in Section \ref{secAbsModel}, which allows the
Me@0: \texttt{masterVP}s to remain suspended until needed.  This in turn enables
Me@0: the \texttt{masterVP}s from different cores to be non-overlapped. It is the
Me@0: non-overlap that enables the algorithms for the parallelism semantics to be
Me@0: sequential.
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: \section{Code Level View}
Me@0: \label{secApp}
Me@0: 
Me@0: To relate the abstract model and the internal elements to application code and
Me@0: parallelism-library code, we give code snippets that illustrate key features.
Me@0:  We start with the application then work down through the sequence of calls,
Me@0: to the plugin, using our SSR {\cite{VMSHome}} parallelism-library as an
Me@0: example.
Me@0: 
Me@0: In general, applications are either written in terms of a full custom language
Me@0: that has its own syntax, or a base language with a parallelism library, which
Me@0: is often called an {\em{embedded language}}.  Our demonstrators, VCilk
Me@0: {\cite{VMSHome}}, Vthread, and SSR, are all parallelism libraries. A full
Me@0: custom language would follow the standard practice of performing
Me@0: source-to-source transform, from custom syntax into C plus parallelism-library
Me@0: calls.
Me@0: 
Me@0: {\bf SSR:\ }SSR stands for Synchronous Send-Receive, and details of its
Me@0: calls and internal implementation will be given throughout this section. It
Me@0: has two types of construct. The first, called {\em{from-to}} has two calls:
Me@0: \texttt{SSR\_send\_from\_to} and \texttt{SSR\_receive\_from\_to}, both of
Me@0: which specify the sending VP as well as the receiving VP. \ The other, called
Me@0: {\em{of-type}} also has two calls: \texttt{SSR\_\_send\_of\_type\_to} and
Me@0: \texttt{SSR\_\_receive\_of\_type}, which allow a receiver to accept from
Me@0: anonymous senders, but select according to type of message.
Me@0: 
Me@0: 
Me@0: % An example of a double column floating figure using two subfigures.
Me@0: % (The subfig.sty package must be loaded for this to work.)
Me@0: % The subfigure \label commands are set within each subfloat command, the
Me@0: % \label for the overall figure must come after \caption.
Me@0: % \hfil must be used as a separator to get equal spacing.
Me@0: % The subfigure.sty package works much the same way, except \subfigure is
Me@0: % used instead of \subfloat.
Me@0: %
Me@0: %\begin{figure*}[!t]
Me@0: %\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
Me@0: %\label{fig_first_case}}
Me@0: %\hfil
Me@0: %\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
Me@0: %\label{fig_second_case}}}
Me@0: %\caption{Simulation results}
Me@0: %\label{fig_sim}
Me@0: %\end{figure*}
Me@0: %
Me@0: % Note that often IEEE papers with subfigures do not employ subfigure
Me@0: % captions (using the optional argument to \subfloat), but instead will
Me@0: % reference/describe all of them (a), (b), etc., within the main caption.
Me@0: 
Me@0: 
Me@0: {\bf Application View:\ } Figure \ref{figAnimVP} shows snippets of application code, which use the SSR parallelism
Me@0: library. The most important feature is that all calls take a pointer to the
Me@0: VP that is animating the call. This is seen at the top of the figure where slave VP creation takes a pointer
Me@0: to the VP asking for creation. Below that is the standard prototype for top level functions,
Me@0: showing that the function receives a pointer to the VP it is the top level function for.
Me@0: 
Me@0: The pointer is placed on the stack by VMS when it creates the VP, and is the means by
Me@0: which the application comes into possession of the pointer. This animating VP is
Me@0: passed to all library calls made from there. For example, the bottom shows a pointer to the
Me@0: animating VP placed in the position of sender in
Me@0: the \texttt{send} construct call.  Correspondingly, for the \texttt{receive} construct,
Me@0: the position of receiving VP is filled by the VP animating the call.
Me@0: 
Me@0: \begin{figure}[ht]
Me@0: {\noindent
Me@0: {\scriptsize
Me@0: {\small Creating a new processor:}
Me@0:  \begin{verbatim}
Me@0: newProcessor = SSR__create_procr( &top_VP_fn,
Me@0:  paramsPtr, animatingVP ); \end{verbatim}
Me@0: 
Me@0: {\small prototype for the top level function:}
Me@0:  \begin{verbatim}
Me@0: top_VP_fn( void *parameterStrucPtr, VirtProcr 
Me@0:  *animatingVP ); \end{verbatim}
Me@0: 
Me@0: {\small handing animating VP to parallelism constructs:}
Me@0:  \begin{verbatim}
Me@0: SSR__send_from_to( messagePtr, animatingVP, 
Me@0:  receivingVP );
Me@0: messagePtr = SSR__receive_from_to( sendingVP,
Me@0:  animatingVP ); \end{verbatim}
Me@0: }
Me@0: }
Me@0: \caption
Me@0: {
Me@0: Application code snippets showing that all calls to the parallelism library
Me@0: take the VP animating that call as a parameter.
Me@0: }
Me@0: \label{figAnimVP}
Me@0: \end{figure}
Me@0: 
Me@0: Relating these to the internal elements of our implementation, the
Me@0:  \texttt{animatingVP} suspends inside each of these
Me@0: calls, passing a request (generated in the library) to one of the \texttt{masterVP}s.
Me@0:  The \texttt{masterVP} then calls the \texttt{comm-handler}
Me@0:  plugin, and so on, as described in Section  \ref{secInternal}.
Me@0: 
Me@0: For the \texttt{SSR\_\_create\_processor} call, the comm-handler
Me@0:  in turn calls a VMS primitive to perform the creation.
Me@0:   The primitive places a pointer to the newly created VP onto its stack, so that when
Me@0: \texttt{top\_VP\_fn} is later animated, it sees the VP-pointer as a
Me@0: parameter passed to it. \ All
Me@0: application code is either such a top-level function, or has one at the root
Me@0: of the call-stack.
Me@0: 
Me@0: The send and receive calls both suspend their animating VP. When both have
Me@0: been called, the communication handler pairs them up and resumes both. This
Me@0: ties time-lines together, invoking the VMS guarantee. Both
Me@0: application-functions know, because of the VMS guarantee (Section \ref{secAbsModel}), that
Me@0: writes to shared variables made before the send call by the sender are visible
Me@0: to the receiver after the receive call. This is the programmer's view of tying
Me@0: together the local time-lines of two different VPs, as defined in Section \ref{secAbsModel}.
Me@0: 
Me@0: 
Me@0: {\bf Concurrency-Library View:\ }A parallelism library function, in
Me@0: general, only creates a request, sends it, and returns, as seen below.  To
Me@0: send a request, it uses the combined request-and-suspend VMS primitive that
Me@0: attaches the request then suspends the VP.  The primitive requires the
Me@0: pointer to the VP, to attach the request and to suspend it.
Me@0: 
Me@0: 
Me@0: \begin{figure}[ht]
Me@0: {\noindent
Me@0: {\scriptsize
Me@0:  \begin{verbatim}
Me@0: void * SSR__receive_from_to( VirtProcr *sendVP,
Me@0:  VirtProcr *receiveVP )
Me@0:  { SSRSemReq  reqData;
Me@0:    reqData.receiveVP = receiveVP;
Me@0:    reqData.sendVP    = sendVP;
Me@0:    reqData.reqType   = receive_from_to;
Me@0:    VMS__send_sem_request( &reqData, receiveVP );
Me@0:    return receiveVP->dataReturnedFromRequest;
Me@0:  } \end{verbatim}
Me@0: }
Me@0: }
Me@0: \caption{Implementation of SSR's receive\_from\_to library function.}
Me@0: \label{figImplLib}
Me@0: \end{figure}
Me@0: 
Me@0: 
Me@0: In Figure \ref{figImplLib}, notice that the request's data is on the stack of the virtual
Me@0: processor that's animating the call, which is the \texttt{receiveVP}.  The
Me@0: \texttt{VMS\_\_send\_sem\_request} suspends this VP, which changes the
Me@0: physical core's stack pointer to a different stack. So the request data is
Me@0: guaranteed to remain undisturbed while the VP is suspended.
Me@0: 
Me@0: Figure \ref{figAssembly} shows the implementation of the VMS suspend primitive. As seen in
Me@0: Figure \ref{figInternals}, suspending the \texttt{receiveVP} involves
Me@0: switching to the \texttt{core\_loop}. In our implementation, this is done by
Me@0: switching to the stack of the pthread pinned to the physical core and then
Me@0: jumping to the start-point of \texttt{core\_loop}.
Me@0: 
Me@0: This code uses standard techniques commonly employed in co-routine
Me@0: implementations. Tuning effort spent in \texttt{core\_loop} is inherited by
Me@0: all applications.
Me@0: 
Me@0: 
Me@0: \begin{figure}[ht]
Me@0: {\noindent
Me@0: {\scriptsize
Me@0:  \begin{verbatim}
Me@0: VMS__suspend_procr( VirtProcr *animatingVP )
Me@0:  { animatingVP->resumeInstrAddr = &&ResumePt;
Me@0:     //GCC takes addr of label
Me@0:    animatingVP->schedSlotAssignedTo->
Me@0:     isNewlySuspended = TRUE;
Me@0:     //for master_loop to see
Me@0:    <assembly code stores current physical core's
Me@0:      stack reg into animatingVP struct>
Me@0:    <assembly code loads stack reg with core_loop
Me@0:      stackPtr, which was saved into animatingVP>
Me@0:    <assembly code jmps to core_loop start instr
Me@0:      addr, which was also saved into animatingVP>
Me@0:  ResumePt:
Me@0:    return;
Me@0:  } \end{verbatim}
Me@0: }
Me@0: }
Me@0:   \caption
Me@0: {Implementation of VMS suspend processor.
Me@0: Re-animating the virtual processor reverses this sequence. \ It saves the
Me@0: \texttt{core\_loop}'s resume instr-addr and stack ptr into the VP structure,
Me@0: then loads the VP's stack ptr and jmps to its \texttt{resumeInstrAddr}.
Me@0: }
Me@0: \label{figAssembly}
Me@0: \end{figure}
Me@0: 
Me@0: 
Me@0: {\bf Plugin View:\ }SSR's communication handler dispatches on the
Me@0: \texttt{reqType} field of the request data, as set by the
Me@0: \texttt{SSR\_\_receive\_from\_to} code. It calls the handler code in
Me@0: Figure \ref{figReqHdlr}. This constructs a hash-key, by concatenating the from-VP's pointer
Me@0: with the to-VP's pointer. Then it looks-up that key in the hash-table that SSR uses
Me@0: to match sends with receives, which is in the shared semantic state seen at
Me@0: the top of Figure \ref{figInternals} in Section \ref{secInternal}.
Me@0: 
Me@0: The most important feature in Figure \ref{figReqHdlr} is that both send and receive
Me@0: will construct the same key, so will find the same
Me@0: hash entry.  Whichever request is handled first in Virtual time will see the
Me@0: hash entry empty, and save itself in that entry.  The second to arrive
Me@0: sees the waiting request and then resumes both VPs, by putting them into their
Me@0: \texttt{readyQ}s.
Me@0: 
Me@0: Access to the shared hash
Me@0: table can be considered private, as in a sequential algorithm.  This is because
Me@0:  our VMS-core implementation ensures that only
Me@0: one handler on one core is executing at a time. 
Me@0: 
Me@0: 
Me@0: \begin{figure}[ht]
Me@0: {\noindent
Me@0: {\scriptsize
Me@0:  \begin{verbatim}
Me@0: handle_receive_from_to( VirtProcr *requestingVP,
Me@0:  SSRSemReq *reqData, SSRSemEnv *semEnv )
Me@0:  { commHashTbl = semEnv->communicatingVPHashTable;
Me@0:    key[0] = reqData->receiveVP;   key[1] = 
Me@0:     reqData->sendVP; //send uses same key
Me@0:    waitingReqData = lookup_and_remove( key,
Me@0:     commHashTbl );  //get waiting request
Me@0:    if( waitingReqData != NULL )
Me@0:     { resume_virt_procr( waitingReqData->sendVP );
Me@0:       resume_virt_procr( waitingReqData->
Me@0:        receiveVP );
Me@0:     }
Me@0:    else
Me@0:       insert( key, reqData, commHashTbl );
Me@0:        //receive is first to arrive, make it wait
Me@0:  } \end{verbatim}
Me@0: }
Me@0: }
Me@0:   \caption
Me@0: {Pseudo-code of communication-handler for
Me@0: \texttt{receive\_from\_to} request type. The \texttt{semEnv} is a pointer
Me@0: to the shared parallelism-semantic state seen at the top of Figure
Me@0: \ref{figInternals}.
Me@0: }
Me@0: \label{figReqHdlr}
Me@0: \end{figure}
Me@0: 
Me@0: 
Me@0: 
Me@0: 
Me@0: \section{Results}
Me@0: \label{secResults}
Me@0: 
Me@0: {\bf Setup:\ }We implemented blocked dense matrix multiply with right
Me@0: sub-matrices copied to transposed form. We ran on a 1 socket by 4 core
Me@0: Core2Quad 2.4Ghz chip.
Me@0: 
Me@0: {\bf Implementation-Time:\ }As shown in Table 1, time to implement the
Me@0: three parallel libraries averages 2 days each. As an example of productivity,
Me@0: adding nested transactions, parallel singleton, and atomic function-execution
Me@0: to SSR required a single afternoon, totaling less than 100 lines of C code.
Me@0: 
Me@0: 
Me@0: \begin{table}[ht]
Me@0: \caption
Me@0: {Person-days to design, code, and
Me@0:   test each parallelism library. L.O.C. is lines of (original) C code, excluding libraries and
Me@0:   comments.
Me@0: }
Me@0: \label{tabPersonDaysLang}
Me@0: \begin{center}
Me@0: \begin{tabular}{llll}
Me@0:     & SSR & Vthread & VCilk\\
Me@0:     Design & 4 & 1 & 0.5\\
Me@0:     Code & 2 & 0.5 & 0.5\\
Me@0:     Test & 1 & 0.5 & 0.5\\
Me@0:     L.O.C. & 470 & 290 & 310
Me@0:   \end{tabular}
Me@0: \end{center}
Me@0: \end{table}
Me@0: 
Me@0: 
Me@0: {\bf Execution Performance:\ }Performance of VMS is seen in Table
Me@0: \ref{tabOverheadCycles}. The code is not optimized, but rather written
Me@0: to be easy to understand and modify. The majority of the plugin time
Me@0: is lost to cache misses because the shared parallelism-semantic state moves
Me@0: between cores on a majority of accesses. Acquisition of the master lock is slow due to the hardware
Me@0: implementing the CAS instruction.
Me@0: 
Me@0: Existing techniques will likely improve performance, such
Me@0: as localizing semantic data to cores, splitting malloc across the cores,
Me@0: pre-allocating slabs that are recycled, and pre-fetching. However, in many cases, several hundred
Me@0: nano-seconds per task is as optimal as the applications can benefit from.
Me@0: 
Me@0: \begin{table}[ht]
Me@0: \caption
Me@0: {Cycles of overhead, per scheduled
Me@0:     slave. ``comp only'' is perfect memory, ``comp + mem'' is actual cycles.
Me@0:     ``Plugin-concur'' only concurrency requests, ``plugin-all'' includes
Me@0:     create and malloc requests. Two significant digits due to variability.
Me@0: }
Me@0: \label{tabOverheadCycles}
Me@0: \begin{center}
Me@0: \begin{tabular}{|l|ll|r|r|}
Me@0: \hline
Me@0:     &  & comp & comp\\
Me@0:     &  & only & +mem\\
Me@0:     VMS Only & \texttt{master\_loop} &  91 &  \ 110\\
Me@0:     & switch VPs  & 77 &  \ 130\\
Me@0:     & (malloc) & 160 & 2300\\
Me@0:     & (create VP)  & 540 & 3800\\
Me@0: \hline
Me@0:  Language: &  &  & \\
Me@0:  SSR & plugin -- concur & 190 & 540\\
Me@0:  & plugin -- all & 530 & 2200\\
Me@0:  & lock &  &  250\\
Me@0:  Vthread & plugin -- concur & 66 & 710\\
Me@0:  & plugin -- all & 180 & 1500\\
Me@0:  & lock &  &  250\\
Me@0:  VCilk & plugin -- concur & 65 & 260\\
Me@0:  & plugin -- all & 330 & 1800\\
Me@0:  & lock &  &  250\\
Me@0: \hline
Me@0: \end{tabular}
Me@0: \end{center}
Me@0: \end{table}
Me@0: 
Me@0: 
Me@0: 
Me@0: {\bf Head to Head:\ }We
Me@0: compare our implementation of the \texttt{spawn} and \texttt{sync}
Me@0: constructs against Cilk 5.4, on the top in Table
Me@0: \ref{tabHeadToHead}, which shows that the same application code has similar
Me@0: performance. For large matrices, Cilk 5.4's better use of the memory hierarchy
Me@0: achieves 23\% better performance. However, for small matrices, VCilk is better,
Me@0:  with a factor 2 lower overhead. Cilk 5.4 does not allow controlling the number of spawn events it
Me@0: actually executes, and chooses to run smaller matrices sequentially, limiting
Me@0: our comparison.
Me@0: 
Me@0: When comparing to pthreads, our VMS based implementation has more than an
Me@0: order of magnitude better overhead per invocation of mutex or condition
Me@0: variable functionality, as seen on the bottom of Table \ref{tabHeadToHead}.
Me@0: Applications that inherently have short trace segments will synchronize often
Me@0: and benefit the most from Vthread.
Me@0: 
Me@0: 
Me@0: 
Me@0: \begin{table}[ht]
Me@0: \caption
Me@0: {On top, exe time in seconds for MM. Below, overhead for pthread vs Vthread. First column is cycles
Me@0:   for perfect memory and second is total measured cycles. pthread cycles are
Me@0:   deduced from round-trip experiments.
Me@0: }
Me@0: \label{tabHeadToHead}
Me@0: \begin{center}
Me@0: \begin{tabular}{|l@{\ }|@{\ }lr|}
Me@0: \hline
Me@0: \rule{0pt}{12pt}
Me@0:     Matrix size&Lang.&sec.\\
Me@0: [2pt]\hline
Me@0:     81x81 & Cilk & 0.017\\
Me@0:     & VCilk & 0.008\\
Me@0: \hline
Me@0:     324x324 & Cilk & 0.13\\
Me@0:     & VCilk & 0.13\\
Me@0: \hline
Me@0:     648x648 & Cilk & 0.71\\
Me@0:     & VCilk & 0.85\\
Me@0: \hline
Me@0:     1296x1296 & Cilk & 4.8\\
Me@0:     & VCilk & 6.2 \\
Me@0: [2pt]\hline
Me@0: \end{tabular}
Me@0: \begin{tabular}{c}
Me@0: \begin{tabular}{|l|rr|r|r|}
Me@0: \hline
Me@0:     operation & \multicolumn{2}{c|}{Vthread} & pthread & ratio\\
Me@0: \hline
Me@0:     & comp & total &  & \\
Me@0:     & only &  &  & \\
Me@0: [2pt]\hline
Me@0:     mutex\_lock & 85 & 1050 & 50,000 & 48:1\\
Me@0:     mutex\_unlock & 85 & 610 & 45,000 & 74:1\\
Me@0:     cond\_wait  & 85 & 850 & 60,000 & 71:1\\
Me@0:     cond\_signal & 90 & 650 & 60,000 & 92:1\\
Me@0: \hline
Me@0: \end{tabular}\\
Me@0: \end{tabular}
Me@0: \end{center}
Me@0: \end{table}
Me@0: 
Me@0: \section{Conclusion}\label{secConclusion}
Me@0: 
Me@0: We have shown an alternative to the Thread model that enables easier-to-use
Me@0: parallelism constructs by splitting
Me@0: the scheduler open, to accept new parallelism constructs in the form of
Me@0: plugins. This gives the language control over assigning virtual
Me@0: processors to physical cores, for performance, debugging, and flexibility
Me@0: benefits. Parallelism constructs of languages are implementable using
Me@0: sequential algorithms, within a matter of days, while maintaining low run-time
Me@0: overhead, on the order of a few hundred nano-seconds per concurrency
Me@0: operation.
Me@0: 
Me@0: \bibliography{Bib_for_papers}
Me@0: 
Me@0: \end{document}