\chapter{Related work}\label{chap:related} \ifpdf    \graphicspath{{Chapter5/Chapter5Figs/PDF/}{Chapter5/Chapter5Figs/PNG/}		{Chapter5/Chapter5Figs/}}\else    \graphicspath{{Chapter5/Chapter5Figs/EPS/}{Chapter5/Chapter5Figs/}}\fi This chapter tries to put XCPU3 in the context of other work which has been done in this area.  We will briefly discuss the various relatedprojects and how they differ from XCPU3. \section{Historical solutions}Using multiple computers for getting the job done is not new.  With theavailability of cheap networking, there were attempts in the research communityto create a \textit{distributed operating system} which can be used for workloaddistribution. This section discusses few of those research projects. \subsection{Amoeba}Amoeba \cite{amoeba} was developed as a general purpose distributed operatingsystem which can solve the problem of scarcity of compute resources.  It worksby creating a \textit{processor pool} using idle workstations and use this poolfor performing long running computations.  It introduced and used concepts likeprocess migration. It provided tightly integrated mechanisms for remoteprocess execution and control allowing the resources of the entire network to beutilized as a single system. Amoeba mainly concentrated on turning the collection of workstations into atransparent distributed system.  It concentrated more on executing theapplications reliably and not on deploying the applications quickly.  \subsection{Cambridge Distributed Computing System}The Cambridge distributed computing system\cite{Needham82} system was aimed to tackle the problem faced during 1980 when the machines were less powerful andmore expensive.  The direct assignment of the machine to a user was inflexibleas the computational requirements of the users change depending on the work heis doing.  This system works by having central \textit{processor bank} whichdoes not belong to any user.  Any user can remotely use the processors from theprocessor bank and release them when computation is over.  This system alsoimplemented the network filesystem which can be accessed by any processor in theprocessor bank or workstation. This system provided the mechanism for organizing the multiple resources,but it was aimed at sharing the resources between users. \section{Traditional job deployment solutions}Increase  in the capability of the personal computers (pc) and decrease of theircost made the above research systems outdated.  As we are reaching the limits ofsilicon technology, it is becoming increasingly difficult to increase thespeeds of these processors. This has lead to the design of multicore andmanycore chips.  This trend has also promoted research in clusters and grids. In this new incarnation, most of these clusters run the Unix based operatingsystem and the responsibility of extracting parallelism from these clustersis left to the applications.  These new incarnations of clusters also useddifferent mechanisms for job deployment.  As clusters run the Unix based loosely coupled operating system on each node, the job deployment was based onthe services like remote shell.  This section discusses a few of these jobdeployment solutions used in recent clusters.  \subsection{Secure SHell(SSH)}SSH\cite{ssh} is the security aware extension of remote shell.  SSH uses publickey cryptography for key exchange and provides a secure channel by encryptingall the traffic.  The job deployment is done by the client node logging on thecompute node using SSH and using this remote shell to execute the desiredapplication.  The applications and other dependency files are transferred to the remote node either by copying them using \textit{Secure CoPy (SCP)} or fetching them over a network/distributed filesystem.  Most of the existing middleware and workload distribution systems use the aboveapproach.  Even though they provide wrappers around it to simplify the userinterface, the above are the fundamental working services.  The limitation of using SSH is that the application has to run in theenvironment of the compute node and not in the environment of the client node. This puts additional burden on the application developer to ensure that theapplication will work properly in the compute node environment.  Another limitation is that the SSH connections are one-to-one, and thisone-to-one model does not scale up for controlling large numbers of nodes. \subsubsection{PSSH}Parallel SSH (PSSH)\cite{pssh} is an attempt to overcome the limitation ofscalability.  This tool allows connecting to multiple remote nodessimultaneously.  It allows client to control all the remote nodes simultaneouslyby replicating the same commands to all the remote shells. This tool definitely improves the scalability but at the loss of flexibility asclient node loses the fine grained control on each remote node.  Also, as PSSHdoes not use any kind of hierarchy for scaling, client node is responsible formaintaining all parallel connections. \subsection{BProc: Beowulf Distributed Process Space}BProc\cite{bproc} is developed as an alternative to the loosely coupled SSHbased job deployment. BProc works by tightly coupling the kernels running oncluster nodes and gives better control on remote processes than SSH.  BProcis set of kernel modifications, utilities and libraries.  These modificationsprovide mechanisms for starting and managing processes on remote node andprocess migration by using the OS API.  BProc creates a distributed process IDspace which allows a front node to locally control all remotely startedprocesses. BProc is a good step towards getting more control over the processes clusterenvironment, but it also imposes few restrictions.  It needs a modified kernelon all the nodes.  Another restriction is on the namespace.  The remotelystarted process will work in the namespace of the compute node and not in thenamespace of the client node.  Also, the process migration is restrictive as allthe open files except standard input and standard output are lost when a processis migrated.  These restrictions lead to the loses of the flexibility which isneeded for dynamic workloads. \subsection{Multicast Reduction Network (MRNet)}The MRNet\cite{MRNet} is designed for efficient multicast and data aggregation. It uses the tree of internal processes between the front-end and the back-endof the tool.  The components of this tool communicate using logical channelscalled streams.  The internal processes attach the filters with these streams toefficiently computing the averages, sums and complex operations.  Theseprocesses internally transfer the data with high bandwidth by using packedbinary representation and zero copy data paths.  It uses multicast to reduce thecost of delivering the messages. This project concentrates on optimizing group communication but it is languagedependent.  The MRNet API is in C++ and one needs to develop the applicationsusing this API. It needs a lot more efforts from the developer side to use thisinfrastructure in comparison to XCPU3.  \subsection{Streamline}The idea of using filesystem interface for data-streams is also used by the\textit{pipefs}\cite{1400104} which is part of the streamline\cite{streamline}project.  The pipefs concentrates on extending the Unix pipeline model for fastI/O in the kernel. The pipefs presents the kernel operations as directories andlive data as pipes using a synthetic filesystem interface.  The pipefs alsoimplements a splicing mechanism which allows copy free movement of the data. This approach of using filesystem interface and splice semantics is quitesimilar to XCPU3, but the objectives of both these projects are different. Pipefs concentrates on faster I/O with filesystem interface for the Linuxkernel while XCPU3 concentrate on the flexible workload management.  We hopethat we can use the concepts from pipefs to improve the performance of XCPU3.  \subsection{Dryad}Dryad\cite{yu2008dsg} is a distributed engine for data-parallel applicationswhich is designed with a primary focus on simplicity of the programming model,reliability, efficiency and scalability.  Dryad application combinescomputational vertices with communication channels to form a dataflow graph. This system explicitly forces the developer to consider the data parallelism ofthe computation. On the other hand the system deals with hard problems likeresource allocation, scheduling and transient or permanent failures.  Dryad isflexible in giving the developers fine control over the communication graph aswell as subroutines that live on the computational vertices. It also allows theapplication developers to specify an arbitrary directed acyclic graph todescribe the application's communication patterns.  These graph vertices can usearbitrary number of inputs and outputs. In many senses, Dryad addresses the issues faced by dataflow deployments.But there are certain issues with dynamic workload which are not tackled.  Dryadassumes that the vertices in the DAG are deterministic and will not changedynamically which is not true for all dataflow deployments.  Sometimes the sizeof computation is affected by the results of a few intermediate computations. The dryad API is C++ specific which limits the usability. It needs additionalwrappers to use Dryad from other languages.  Dryad also tries to support legacyexecutables by putting them in a \textit{process wrapper} but this support isquite restrictive about what these legacy executables can do. Dryad addresses the issues like fault tolerance which are currently ignored byXCPU3, but XCPU3 is more flexible as it can support dynamic workload andchanging DAG of dataflow deployments. Also the filesystem interface of the XCPU3is much simpler and cleaner compared to the class based C++ interface of Dryad. \subsection{Condor}Condor\cite{condor-practice} is \textit{high-throughput distributed batchcomputing} system which exploits \textit{opportunistic computing} for betterperformance. It uses the idle CPU cycles of voluntary workstations solve thelarge computational problem.Condor works by breaking the large problem into smaller tasks and submittingthese smaller tasks to voluntary workstations.  Condor also provides thefault-tolerance by frequent check-pointing and restarting the tasks whichfailed. Condor also provide the way to submit scientific workflow application by usingthe meta-scheduler DAGMan (Directed Acyclic Graph Manager).  It allows user tospecify the various dependencies within tasks in form of directed acyclic graphand then DAGMan takes the responsibility of scheduling these tasks bymaintaining the proper order between them and feeding the results frompredecessor to successor. Condor differs from XCPU3 as it is aimed for voluntary computing and henceconcentrate more on fault tolerance.  It assumes that voluntary workstationsare unreliable and can leave the system anytime.  This design principle isquite opposite of XCPU3 which assumes that resources are mostly reliable.  Thisdifference in the assumptions about underlying hardware has lead to entirelydifferent systems.  Another difference which has cropped in due to differencesin underlying asumptions is that the tasks given to the Condor voluntaryworkstations do not communicate with other workstations directly.  Theytypically communicate with the agent responsible for submitting the job.  Thislack of the ability to communicate directly with other computational nodeslimit the usefulness of Condor for dataflow applications. \subsection{Other commercial solutions}Apart from the research and development going on in the academic and opensource industry, there has been lot of interest in the workload deploymentsolution in the commercial domain.  The \textit{Oracle Grid Engine}\cite{oge} isa batch-queuing system which can accept, schedule, dispatch and manage theremote executions on clusters.  Other solutions involve \textit{PBSWorks}\cite{pbsworks} which is workload and resource management solution and\textit{platform LSF (Load Sharing Facility)}\cite{platformLSF} batch jobscheduler which is aimed to help in scheduling jobs on private clouds.  Most ofthese solutions target to simplify the resource management and jobsubmission/scheduling.  But these commercial solutions mainly differ from XCPU3as they do not try to simplify the communication issues within applications. This issue of effective communication between nodes is left to the applicationdevelopers.  \section{Conclusion}The above discussions shows that there is still lot of scope available forworking on workload management systems for dataflow workloads.  There are manyexisting solutions which tackle either only part of the problem or tackled thisproblem with different constraints in mind.  We have worked on XCPU3 withscalability, flexibility and ease of use as primary objectives and theseobjectives have lead us to the current design of XCPU3.  We hope that XCPU3infrastructure will open up the doors for more solutions targeting specificuse-cases. % ------------------------------------------------------------------------ %%% Local Variables: %%% mode: latex%%% TeX-master: "../thesis"%%% End: