% This is "sig-alternate.tex" V1.9 April 2009
% This file should be compiled with V2.4 of "sig-alternate.cls" April 2009
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.4 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.4) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.9 - April 2009

\documentclass{sig-alternate}

\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{ROSS}{'11 Tuscon, Arizona USA}
%\CopyrightYear{2007} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{XCPU3}
\subtitle{Workload Distribution and Aggregation}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Eric Van Hensbergen \\
       \affaddr{IBM Research}\\
       \affaddr{Austin, Texas}\\
       \email{bergevan@us.ibm.com}
% 2nd. author
\alignauthor
Pravin Shinde \\
       \affaddr{Parallel and Distributed Systems (PDCS)}\\
       \affaddr{Vrije Universiteit, Amsterdam}\\
       \email{pse220@few.vu.nl}
}

\maketitle

%
% Remove abstract for now
%
%\begin{abstract}
%As clusters and grids are reaching to domains like commercial application, it
%is becoming more clear that the existing workload distribution solutions which
%are tailored for high performance scientific applications, are not efficient
%for dynamic data-flow applications and many-task computing (MTC).
%
%Most of the existing workload distribution solutions that concentrate more on
%HPC applications and are not efficient in quickly deploying the dynamic
%workload involving large number of small jobs which is the typical case in
%dataflow applications. Also developing and deploying applications on existing
%infrastructures still is a non-trivial task requiring special runtimes,
%middleware support and/or language dependence.
%
%We have explored an alternate approach for simplifying workload
%distribution and aggregation based on synthetic filesystems and the private
%namespace concepts of Plan 9.  Instead of sending workloads to a remote
%cluster, XCPU3 works by bringing the remote cluster to the user's desktop,
%leading to full control over the compute environment.   XCPU3 provides
%a filesystem interface, making it runtime and language agnostic.  It also
%allows executing multiple jobs simultaneously in isolation, leading to
%better resource utilization.  XCPU3 makes all nodes independent and
%equivalent in functionality leading to the ability to localize the
%decision making and ability to handle dynamic workloads.  XCPU3 provides easy to
%use, flexible and scalable infrastructure for workload distribution and
%aggregation that can be used by dynamic workloads, many-task workloads and
%dataflow applications.
%\end{abstract}

% A category with the (minimum) three required fields
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{Theory}

%\keywords{ACM proceedings, \LaTeX, text tagging}


\section{Introduction}

%
% Removed this first section as it seems to mistarget the conference
%
%Due to the limits on the silicon technology, the trend is moving in the
%direction of multicore and manycore architectures.  Having a large number of
%less powerful computers is assumed to be economically more viable than having a
%single more powerful computer.  The increasing acceptance of clusters and
%grids coupled with the emergence of cloud computing and availability of compute
%resources as utility via \cite{ec2} \cite{azure} \cite{appengine} has increased
%the need for parallel programming and workflow management.
%
%
%The initial development around parallel programming and the traditional
%infrastructure around clusters and grids is designed to suit the
%requirements of the scientific community which tend to run large compute
%intensive applications for long durations.  With growing use of clusters and
%grid, there is increasing interest in deploying new genre of applications 
%like dataflow applications and many-task applications. Typical commercial
%applications fall into the category of dataflow applications and involve
%executing lot of small and interdependent applications for small amount 
%of time.
%Unfortunately, most of the existing workload deployment solutions are 
%ill-suited
%for these applications. These solutions are efficient in deploying large
%compute-intensive application which will run for long duration, but are highly
%inefficient in deploying large number of small applications for small amount of
%time.
%
%The major obstacle in widespread adoption is the expertise needed for writing
%parallel applications.  Also, dependence on a specific language or runtime
%environment for parallelism dictates the need for major re-writing all existing
%applications for exploiting the parallelism.
%
%
%Another crucial property exhibited by dataflow applications is that the amount
%of resources needed for total computation is unpredictable in the beginning as
%it may depend on results of intermediate computations.  This leads to the
%requirement of dynamically allocating new resources whenever needed. Most of the
%current job schedulers do not support such adaptability and flexibility.
%
%
%In this paper, we target the problem of creating a scalable infrastructure
%with the flexibility needed for running dataflow applications.  We primarily
%target the Blue Gene \cite{bgp} supercomputer as our testbed as it allows us to
%test our infrastructure on up to 64K nodes.
%
%
%The challenge is to provide the flexibility needed by dataflow applications
%using a very simple interface.  We need to provide an infrastructure with
%support for dynamically adjusting the resource reservation which can help in
%coping with unpredictable resource requirements.  This infrastructure needs to
%provide quick job-startup time even for large numbers of jobs, allowing overall
%good performance for dataflow applications.  It also needs to provide a simple
%interface for communication between nodes even when those nodes cannot
%communicate directly with each other. We do not want the application development
%for this infrastructure to be constrained to a particular language, runtime,
%middle-ware or platform.  And we need to run most of the existing applications
%without modification.
%
%
%Our primary aim is not performance improvement, but to present a new and elegant
%way for workload distribution and aggregation.  It is aimed at demonstrating
%that simple filesystem interfaces and a simple design based on the basic
%principles of the Plan 9 \cite{pike95plan} distributed operating system can be
%easy, intuitive and scalable to a large number of nodes.
%

This paper is organized as follow. The next section presents the background
work which has inspired this project. The \textit{Design section} will discuss
the design and the reasoning behind it. \textit{Implementation section} will
discuss how system is implemented. The \textit{Filesystem interface section}
explains the use of synthetic filesystem and presents few examples to show how
easily this interface can be used. Evaluations section presents some results
showing that this approach is feasible. Related work section positions XCPU3 in
the context of other related projects. Conclusion section will conclude this
project.

\section{Background}
This section discusses the the previous work from which XCPU3 is evolved.

\subsection{Plan 9}
Plan 9 is an operating system which was specifically designed for dealing with
networked systems.  It is based on principles like \textit{everything is file}
and \textit{private namespaces}\cite{namespace}.  It provide applications
ability to build custom namespace by mounting and binding remote resources and
then run in network oblivious manner.  The usefulness of these features can be
seen in CPU\cite{plan9-cpu} which is Plan 9's way for using remote compute
resources.  Unlike Unix based remote login and SSH where remote processes run
in the namespace and environment of remote node, CPU runs the remote processes
in local namespace and environment.  One of the key advantages of this model
simplifies the remote workload deployment as even though workload runs on
remote resources, it runs in local environment without getting affected by the
environment on remote node.

\subsection{XCPU}
XCPU\cite{ron-xcpu} \cite{lucho-xcpu} was an attempt to bring the functionality
of CPU into mainstream operating systems like Linux.  XCPU allows process
management using a \textbf{filesystem interface}.  As this underlying pseudo
filesystem can be exported over network to other nodes, it simplifies the
sharing of the compute resources.  XCPU does not provide private namespace,
which is needed for transparently accessing remote filesystem.  XCPU works
around this limitation by pushing the executable and it's dependencies needed
for requested remote execution.

To achieve scalable pushing of programs and their dependencies, XCPU uses a few
compute nodes for distributing the programs and dependencies during the program
startup time creating a tree hierarchy of the nodes.  This is known as the
\textbf{tree spawn mechanism} and it improves the scalability for XCPU to
larger numbers of nodes. With automatic pushing and the tree spawn mechanism,
XCPU not only simplifies the deployment of applications but it also scales
them better with quicker job startup time.

\subsection{XCPU2}
XCPU2 \cite{lucho-xcpu2} is evolved from XCPU and is aimed to give more
flexibility by using \textit{private namespace} support added recently into
Linux kernel\cite{linuxns}.  This allows remote processes to execute in the
namespace which provides local filesystem view.  By controlling the
environment and filesystem view of all the remote processes, every developer
is free to use any libraries and development setup, regardless of what is
installed on remote nodes.  As these processes run in the isolation provided by
the private namespace, they do not pollute the environment and filesystem view
of other processes.  This allows executing multiple processes of different
users on same remote node without conflicting with each other.

XCPU2 makes clear distinction between various nodes which are assigned with
specific responsibility.  The nodes are classified into \textit{control node}
which is responsible for reserving the compute nodes, \textit{job control node}
which are responsible remote job management and namespace management on compute
nodes. The \textit{compute nodes} are responsible for actual computation
by running the processes on inside custom namespace on users behalf.
 
The XCPU2 lacks fine-grained granularity of the control.  It only supports
managing all \textit{compute nodes} together in identical way, and does not
give any mechanism to control each \textit{compute node} individually.  This
lack of control on every node is a major deterrent for dataflow applications.
This limitation was major motivation for us to develop XCPU3 for providing much
needed flexibility and fine grained control over over all compute nodes using
simple interface.


%%%%%%%%%%%%%%%%%%%%%%%%%%%% End of Introduction chapter %%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%% Start of Design chapter %%%%%%%%%%%%%%%%%%%%%%%

\section{Design}

The key challenge in this design was to provide the flexibility needed by
dataflow applications while achieving scalability to the large number of nodes
available. 

\subsection{Key design decisions}

We decided to adopt a few guiding principles which will help us to reach our
goal of flexibility with scalability.  We also decided to keep the design simple,
and we believe that the simple design should lead to the simple and flexible
interface. We also hope that the lack of complexity may help in improving
scalability. In this section we present those decisions which influenced most
aspects of system design and implementation.

\subsubsection{Localization of decision making}
The key requirement for us was scalability to a large number of nodes.  We
planned to design the system without any central component which should have
knowledge of the entire system.  We plan to distribute and localize the
computations as well as decisions like scheduling, job management and
workload distribution/aggregation.

We avoid decision making based on global knowledge and promote use of local
information.  We hope that if each node tries to attempt a local optimum, we
will reach the global optimum.  This may not be true in all cases, We hope
that in those cases, we hope to perform acceptably well if not optimal.


\subsubsection{Independence of every node}
As we plan to distribute and localize all functionalities, it was essential to
replicate these functionalities at multiple levels making localization
possible.  The granularity of functionality replication decides the granularity of control,
and hence influences the flexibility provided by the system.  As we aim for 
maximum flexibility, we have decided for replicating the following three
functionalities at each node.
\begin{enumerate}
\item \textbf{Resource reservation}: Each node should be able to reserve more
resources on it's own without involvement of any central entity.

\item \textbf{Job management}: Every node should be capable of starting and
managing new jobs using his reservations.

\item \textbf{Computation}: Every node should be able to perform the
computation by running the requested application in isolation and returning
the results.
\end{enumerate}

We intend to provide each node with the capability to perform all of these roles
simultaneously instead of binding them in one role at one time.  This design
makes the interface to every node a building block identical to each other, 
and provides the flexibility to build any structure with these building blocks.

There are a few downsides in making every node independent.  With independence
of every node, each node can be a source of failures and faults.
One will need to come up with better ways to deal with faults and
failures when so many sources of them are present.  This takes the XCPU3 in
realms of \textbf{Distributed Systems} opening many more possibilities and
questions.

For purpose of this exploration, we avoid these complexities by assuming a very
simple model for handling failures.  Any failure anywhere in the system will
result in the failure of the entire operation.  We assume that failures will
be in-frequent, so aborting and restarting operation should be acceptable for
such infrequent failures.

\subsubsection{Filesystem Interface}
We want to keep XCPU3 interface agnostic from language, runtime and middleware.
Plan 9 has proven that the filesystem interface is very flexible and yet
powerful in the world of distributed applications.  We aim to follow the same
principle of \textbf{Everything is a file} from Plan 9.

Every node will provide access to its services via filesystem interfaces.
This interface will be exported as the filesystem over the network so that other
nodes can use it. Other nodes can mount this filesystem and use it as
interface for interacting with that node.  Multiple remote nodes can be
aggregated into the filesystem hierarchy providing a clean and easy way to
access them.

Multiple overlay views can be created by \textit{binding} the same filesystem
at multiple locations with different names.  This ability of creating ad-hoc
overlays allow users to arrange remote resources as per his needs without
worrying about their actual locations.

Other advantages of using filesystem interfaces are that 
\begin{enumerate}
\item Existing tools/commands used with traditional filesystem can be directly
used with XCPU3.

\item filesystems come with their own mechanism for access control list for
providing the security.  We can leave the security to these already proven 
mechanisms instead of implementing our own.

\item We inherit the ability to export, mount and bind the filesystem
without writing any explicit code for it.

\item Filesystem interfaces are simpler to program than socket interfaces.  This
can lead to simpler code and hence lesser bugs.

\item Users don't need special privileges or administrative access to interact
with the filesystem.  This simplifies the user experience in running XCPU3 based
applications.
\end{enumerate}

The filesystem interface has following limitations which affect our system
design.

\begin{enumerate}

\item The critical limitation concerns the POSIX standard for failure
reporting in filesystem.  POSIX standard dictates that file operations should
report their success or failure in the form of a single number which may not be
enough to provide the information about the reason behind failures.  Plan 9
overcomes this limitation by returning a string which can provide more
verbose information instead of a single number.  But this breaks the POSIX
compatibility.  So, we need to find an alternate way to report information
about failures in POSIX compatible way.

\item Another drawback is the way a failure of remote services is detected.
The filesystem interface relies on the underlying networking protocol for
detecting failures by waiting for timeouts, and then reporting them back to
users as an error.  This makes the filesystem interface less desirable where
quick failure detection and recovery is needed.


\end{enumerate}

Our decision to choose the filesystem interface despite of it's drawbacks is the
trade-off we are willing to do for flexibility and simplicity.  We limit
ourself with the assumption that failures will be infrequent.  With this
assumption, we are willing to accept the delays in reporting failures at the
remote end.


\section{Implementation}

This section discusses the implementation issues in more detail.  This chapter
concentrates on how XCPU3 was implemented and discusses implementation
decisions which have proven to be important.


\subsection{Inferno}
Inferno\cite{inferno} is an open source distributed operating system which is a 
direct descendant of the \textbf{Plan 9} operating system.  It runs natively on
multiple hardware platforms and can also run as a user-space application on
top of other operating systems.  For the purpose of this document
\textit{"hosted Inferno OS"} or \textit{"userspace Inferno"} refers to Inferno
running as user-space application on top of other operating systems.

As we are aiming for a flexible heterogeneous environment with different
operating systems and different architectures, we found the Inferno operating
system to be an attractive platform.  It allowed us to develop XCPU3 once and
easily deploy it on different platforms while enjoying the Plan 9 features
on all those platforms.

This decision does come with the cost of performance loss.  Each node needs
to run hosted Inferno in user-space which takes up some resources of the node. 
Our choice of Inferno gave us the flexibility and features of the Plan 9
operating system on other operating systems.  It allowed us to quickly
implement and deploy our filesystem on multiple platforms easily at the cost
of some performance.

\subsection{Implementation details}

XCPU3 is implemented as the filesystem in the Inferno kernel.  Figure 
\ref{fig:XCPU3} shows the placement of XCPU3 in the context of applications,
host operating system and the Inferno.

\begin{figure}[h]
  \begin{center}
    \leavevmode
      \includegraphics[height=0.2\textheight,width=0.5\textwidth]
		{./img/XCPU3Structure}
    \caption{XCPU3 Structure}
    \label{fig:XCPU3}
  \end{center}
\end{figure}

The XCPU3 filesystem is exported by Inferno using the \texttt{9P} protocol. 
This protocol is used by Plan 9 and Inferno extensively to access any file. 
Recently the Linux kernel has added support for the \texttt{9P}
protocol\cite{graverobbers}.  This allows Linux to mount filesystems
exported over the 9P protocol.  Other Unix based operating systems can use
FUSE\cite{FUSE} for accessing the 9P based filesystems. 

In a typical setup, Inferno runs in the hosted environment on an operating
system like Linux or Plan 9.  The hosted inferno will export the XCPU3
filesystem which can be mounted by the local host operating system. The 
applications interact with this mounted XCPU3 filesystem using the native
filesystem interfaces (e.g. VFS for Linux). Any interaction with this XCPU3
filesystem is communicated to Inferno using \textit{9P}. The XCPU3 kernel module
inside the inferno kernel then receives and interprets the user actions.  If
needed, it uses services from the host operating system or from other XCPU3
filesystems deployed on remote locations.  The XCPU3 filesystem then sends the
prepared response over 9P. The host operating system will relay this response
back to the application via the local filesystem interface.


\subsection{The big picture (connecting multiple XCPU3 nodes)}
The real power of the XCPU3 is the ability to connect with each other and form

Lines 1–500 of 1099. Load more