\subsection{Raytracing}
\label{raytracing}

We have ported a sequential raytracer written in Java to Javelin as an example of a real-world application that
benefits from additional processors even if communication is relatively slow.  The raytracer was written
by Frederico Inacio de Moraes, Universidade Estadual de Campinas, \cite{chico} and was first parallelized by
Laurence Vanhelsuwe \cite{vanhelsuwe97}.

Raytracing is a method that creates photo-realistic synthetic images from a mathematical description of the scene
to be generated.  A scene is defined by the camera, light sources, and objects built from textured primitives
such as cubes, spheres, and planes.  Raytracing software mathematically traces the light rays as they bounce around
the scene, reflecting and refracting until they end up in the lens of the imaginary camera.  This can involve
millions of floating-point operations and take anything from a few minutes to many days.
Since each imaginary beam of light
% from the viewpoint 
going through a pixel of the image is traced
independently, raytracing can be parallelized easily by assigning each processor a subregion of the image.


\subsubsection{Parallel Raytracing}

We have implemented our parallel raytracer using the distributed ``queue'' library discussed in Section \ref{high_level_api}.
Figure \ref{main_loop} shows the main loop of the raytracer.  Initially, the
client pushes a rectangle of the size of the image onto its local stack.  In
their main loop, hosts (where the client is a special host) pop a rectangle
from the stack and either split it or compute this region of the image.  
A pop on an empty local stack triggers a task request being
issued by the library and routed through the network by the Javelin runtime
system.  The image is split if the area of the rectangle is larger than a
given size, the {\em granularity}.  If it is split, both resulting rectangles are
pushed back onto the stack.  In the next iteration, the rectangle pushed second
may be split further.
%This scheme leads to a local stack where the rectangles do not get smaller
%from top to bottom.

\begin{figure}
\begin{verbatim}
JStack stack = new JStack();
JRectangle rect = null;
while ( ( rect = stack.pop() ) != null )
{
  if ( rect.tooBig( JAVELIN_DEFAULT_GRANULARITY ) )
  {
    rect.split_and_push( stack );
  }
  else
  {
    raytrace( rect );
  }
}
\end{verbatim}
\caption{{\em The main loop of our raytracer.}}
\label{main_loop}
\end{figure}

The library gives remote hosts tasks from the bottom of the local double-ended queue.  
Thus, most of the time large
rectangles, usually implying a compute-intensive task, are given to requesting hosts.
%This scheme tries to compensate communication cost
The basic idea of this scheme is to reduce communication by returning a remote
host a long lasting computation so that it will be busy for a while and not
send another request over the network. 
%
%Large tasks are split
%into many smaller pieces following the algorithm in Figure~\ref{main_loop}. 
%
% It is likely that a pop that cannot be satisfied locally, and hence
% triggers a remote task request, results in a large task that
% subsequently is split into successively smaller tasks until one is
% pushed onto to the local stack whose size is no larger than the
% granularity parameter.  The local deque thus is filled with several
% tasks.  This implies that most pops in Figure
% \ref{main_loop} are serviced locally.  
%
This scheme was first
used for distributed scheduling by Cilk.
%\cite{blumofe94}.
Figure \ref{simple_sequence} illustrates how this scheme applies to raytracing an image on three
processors.

Initially, processor 1 is assigned the whole image and splits it according to
the algorithm in Figure \ref{main_loop}.  When a second host becomes available
it downloads our raytracing applet from a server and requests a rectangle of
the image that has not been raytraced yet from processor 1.  This request is
satisfied from the bottom of processor 1's stack.  Thus, processor 2 is
assigned half of the image.  When a third processor becomes available, it
randomly requests work from either processor 1 or 2.  In \ref{simple_sequence_c}, processor 3 is
assigned half of the work of processor 1, i.e., a quarter of the image.  In
\ref{simple_sequence_e}, processor 1 requests work back from processor 2.

%When a host finishes raytracing a scanline of a rectangle it sends the color information
%immediately to the client.

\begin{figure}[htbp]
\begin{center}
\subfigure[]{\psfig{figure=figs/simplea.ps,width=1.25in,clip=}}\quad
\subfigure[]{\psfig{figure=figs/simpleb.ps,width=1.25in,clip=}}\quad
\subfigure[]{\psfig{figure=figs/simplec.ps,width=1.25in,clip=} \label{simple_sequence_c}}\quad
\subfigure[]{\psfig{figure=figs/simpled.ps,width=1.25in,clip=}}\\
\subfigure[]{\psfig{figure=figs/simplee.ps,width=1.25in,clip=} \label{simple_sequence_e}}\quad
\subfigure[]{\psfig{figure=figs/simplef.ps,width=1.25in,clip=}}\quad
\subfigure[]{\psfig{figure=figs/simpleg.ps,width=1.25in,clip=}}\quad
\subfigure[]{\psfig{figure=figs/simple7.ps,width=1.25in,clip=}}
\end{center}
\caption{\em {Snapshots of a simple scene being raytraced by three processors.
The background coloring illustrates which processor currently owns which
part of the computation.  The black lines show how the image is split into
smaller rectangles over time.  The final picture shows which parts are
actually raytraced by which processor.}}
\label{simple_sequence}
\end{figure}


\subsubsection{Performance}

To evaluate the performance and dynamic behavior of our infrastructure we have raytraced images of the size
1024x1024 pixels for the two scenes shown in Figure \ref{simple_and_cone89}, and a randomly generated scene.  {\tt simple} is built from a plane
and two spheres; {\tt cone435} is built from a plane and 435 spheres arranged as a cone\footnote{
In favor of a better illustration Figure \ref{simple_and_cone89} shows only 89 spheres arranged as a cone.
}; {\tt random} is built from 12,288 randomly chosen primitives.

\begin{figure}[htbp]
\begin{center}
\subfigure[{\tt simple}]{\psfig{figure=figs/simple.ps,width=3in,clip=}}\quad
\subfigure[{\tt cone89}]{\psfig{figure=figs/cone89.ps,width=3in,clip=}}
\end{center}
\caption{\em {Ray traced images.}}
\label{simple_and_cone89}
\end{figure}

Figure \ref{speedup_simple_and_cone89} shows the speedup curve for our parallel raytracer running on {\tt simple} and {\tt cone435} in a
cluster of two Sparc-5s, five UltraSparcs, and one dual-processor UltraSparc connected by 10 and 100 Mbit Ethernet.
Figure \ref{speedup_random} gives the speedup curve for raytracing {\tt random} on the 64 Sparc-10 nodes of our Meiko CS-2.  We
used a simple Web ``browser'' written in Java that executes applets and applications by spawning Sun's JVM with JIT.
The graphs illustrate that the speedup that can be achieved depends on the computation to communication ratio.  The
more complex the scene, the longer it takes to compute the color of a pixel, and the less frequently communication
is required.  In general, coarse-grained applications with a high computation to communication ratio are well
suited to Javelin.

\begin{figure}[htbp]
\begin{center}
\subfigure[]{\label{speedup_simple_and_cone89} \psfig{figure=figs/speedup_cone435.eps,width=3in,clip=}}\quad
\subfigure[]{\label{speedup_random} \psfig{figure=figs/speedup_random.eps,width=3in,clip=}}
\end{center}
\caption{\em {Speedup curves for {\tt simple} and {\tt cone435} on a SparcStation cluster
and {\tt random} on a 64 Sparc-10 processor Meiko CS-2.}}
\label{speedup_curves}
\end{figure}

Figure \ref{dynamic_behavior} illustrates the dynamic assignment of
work to hosts through the Javelin runtime system.  The performance of
the processors differs within a factor of ten.  The figure shows a
high correlation between the relative performance of a host and the
fraction of work it does in a parallel run.  We have observed that
subcontracting (called work-stealing in Cilk parlance) with optimistic
propagation and exponential back-off leads to task distribution that is
close to optimal.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/balance.eps,width=3in,clip=}}
\caption{\em {The relative performance for rendering {\tt simple} locally and
the relative number of pixels computed by each host when raytracing
{\tt simple} in parallel on all four processors.  All numbers are normalized
to the Sparc-5.}}
\label{dynamic_behavior}
\end{figure}
