\section{\label{case-studies}Two Case Studies}

In the following section we present two applications implemented with
the PCM thread package.  

\subsection{Parallel Ray Tracing}  

The parallel ray tracer presented here is an optimal example to
illustrate the virtues of the PCM thread package. First, the task of
tracing a complicated picture with a reasonable size, like the one
shown in Figure~\ref{fish}, contains enough parallelism to justify the
use of a powerful parallel processor. Second, the variance in the
amount of processor cycles required to trace individual rays
necessitates the use of a dynamic load balancing schema to guarantee
acceptable utilizations and to ensure scalability. Third, we can
package the ray tracer into threads and obtain threads with
grain-sizes coarse enough to offset the overhead introduced by a
dynamic execution model.

The simplest of all ray tracing algorithms intersects a ray with every
object surface and displays the object whose intersection is closest
to the position of the observer. This algorithm is known as exhaustive
ray tracing, since it calculates all possible ray-surface
intersections.  The ray-tracer we used improves upon this basic
algorithm.  It uses a bounding volume which requires relatively simple
intersection calculations, such as a sphere, to enclose more complex
objects. If a ray does not pierce the bounding volume then all the
objects contained within can be eliminated from consideration which
substantially reduces the average costs of ray surface calculations.
This technique is further improved by arranging bounding volumes into
hierarchies. In such a scheme a number of bounding volumes could
themselves be enclosed within an even larger bounding volume so that
many objects can be eliminated if a given ray does not intersect with
a parent bounding volume.

This algorithmic improvement reduces the linear time complexity of
exhaustive ray tracing to one which is logarithmic in the number of
objects. However, this optimization also creates a large variation in
the time needed to trace a ray, making it hard to find a static work
distribution that sufficiently balances the available work.

\subsubsection{Ray Tracer Parallelization}

\begin{figure}[htbp]
\begin{center}
\begin{small}
\begin{code} 
{\bf void} Trace()\{ \\
\>  int x, y;\\
\ \\
\>  {\bf for} (y = First\_Line; y $<$ Last\_Line; y++) \\
\> \>   {\bf for} (x = First\_Column ; x $<$ Last\_Column ; x++) \{ \\
\> \> \>  pixel = calculate\_intersections(x, y); \\
\> \> \>  write\_pixel(x, y, pixel); \\
\> \> \} \\
\}
\end{code}
\end{small}
\caption{\label{ray-tracer-original} kernel of sequential ray tracer}
\end{center}
\end{figure}

To show the power of our thread package as a tool to retarget existing
sequential programs for parallel processors, we took the POV-Ray package that
implements the optimized method described above and rewrote its kernel with our
thread language. A simplified version of the original sequential kernel can be
seen in Figure~\ref{ray-tracer-original}. The details of ray-object intersection
caculation are not required to comprehend the transformations explained in the
remainder of this section. In fact, the threaded version shown in
Figure~\ref{ray-tracer-parallel} uses the exact same function,
\verb+calculate_intersection+ that the sequential version used.

%%%%
%%%%
\begin{figure}[htb]
\begin{center}
\begin{small}
\begin{code} 
{\bf thread} Join({\bf Cont} parent\_join, {\bf int} s1, {\bf int} s2, {\bf int} s3, {\bf int} s4 ) \{\\
\>  {\sf send\_argument}(SIGNAL, parent\_join); \\
\} \\
\ \\
{\bf thread} Trace({\bf Cont} parent\_join, {\bf int} sx, {\bf int} ex, {\bf int} sy, {\bf int} ey) \{ \\
\>  {\bf if}((sx == ex) \&\& (sy == ey)) \{ \\
\> \>    pixel = calculate\_intersections(sx, sy); \\
\> \>    write\_pixel(sx,sy,pixel); \\ 
\> \>    {\sf send\_argument}(SIGNAL, parent\_join); \\
\> \} \\
\> {\bf else} \{ \\
\> \> {\bf closure} k1, p1, p2, p3, p4; \\
\> \> {\bf int} xoff = (ex - sx) $>>$ 1, yoff = (ey - sy) $>>$ 1; \\
\ \\
\> \> k1 = {\sf make\_closure}(Join, parent\_join, \_ , \_ , \_ , \_ ); \\
\> \> p1 = {\sf make\_closure}(Trace, {\bf cont}\{k1,Join:s1\}, sx, (sx + xoff), sy, (sy + yoff); \\
\> \> p2 = {\sf make\_closure}(Trace, {\bf cont}\{k1,Join:s2\}, sx, (sx + xoff), (sy + yoff +1 ), ey); \\
\> \> p3 = {\sf make\_closure}(Trace, {\bf cont}\{k1,Join:s3\}, (sx + xoff + 1), ex, sy, (sy + yoff);\\
\> \> p4 = {\sf make\_closure}(Trace, {\bf cont}\{k1,Join:s4\}, (sx + xoff + 1), ex, (sy + yoff +1 ), ey); \\
\> \> {\sf post}(p1); {\sf post}(p2); {\sf post}(p3); {\sf post}(p4); \\
\> \}\\
\}
\end{code}
\end{small}
\caption{\label{ray-tracer-parallel} kernel of PCM ray tracer}
\end{center}
\end{figure}

%%As mentioned in the introduction, the PCM thread package allows the programmer to
%%combine sequential and multithreaded programming styles. The mix of the two styles,
%%leading to the most efficient implementation, however, needs to be explored by the
%%programmer. Typically, the programmer will try to maximize the granularity to reduce
%%the dynamic execution overhead, at the same time making sure that enough parallelism
%%is exposed to keep all the available processors fully utilized. 
%%
%%We will show that in the case of the ray tracer the {\em optimal mix} of the two execution
%%styles consists almost entirely of sequential code. Nothing but the kernel shown in
%%Figure~\ref{ray-tracer-original} had to be rewritten to achieve both goals mentioned above.
%%The multithreaded version, shown in Figure~\ref{ray-tracer-parallel}, consists of a simple
%%recursion, with the body of the original loop forming the bottom case of the
%%recursion.
%%
%%We should note at this point that we decided to duplicate the object database, which describes 
%%the actual picture, onto each node to avoid the necessity of a global address space.
%%Although a single distributed copy of the object database would have significantly reduced
%%the memory requirements of the ray tracer, there was no need to consider this option, since
%%even the most complex picture fit well into 32 MBytes of physical memory available on each
%%CM-5 computing node. 

The {\em Trace} thread traces a subwindow of the original picture, specified by the
four coordinates in the argument list. {\em Trace} accomplishes this task by
recursively splitting its subwindow into even smaller subwindows until the size of
the newly created windows reaches the size of a single pixel. The implementation
shown tries to split a trace job into four jobs by splitting the picture along both
the x and y dimension.

Note that unlike the Fibonacci example, neither the sequential nor the
parallel ray tracer return results. They simply write the RGB-values
for the computed pixels into a preallocated buffer. The absence of a
result forces us to resort to an alternative way to detect the
termination of the program. The thread {\em Join} is used to implement
a fairly general concept of a {\em signal tree}. The underlying idea
is to use a tree to collect all the signals produced by the bottom
cases of the recursion and to return a single signal to the top
closure after all the signals have been collected.

%%NThe shape ofthe signal tree
%%is going to be almost identical to the one of the trace computation. The only
%%difference will be that the the leaves nodes of the trace recursion refrain from
%%creating another level of signal join closures. They will simply send a signal to
%%the join closure they inherited from their parent trace thread.
%%The code shown in Figure~\ref{ray-tracer-parallel} uses a special join thread to do
%%the signal joining. A new dynamic instance of this join thread will be created,
%%whenever a trace job decides to split its work into smaller trace jobs. All those
%%newly created dynamic instances of trace will then be made to send a signal to the
%%newly created join closure -- this is done by passing the continuation of the newly
%%created join closure as an argument to each newly instance of trace. After receiving
%%all its signals, this join closure will then send a single signal to the next higher
%%level of the signal tree. 

\begin{figure}[htb]
\centerline{\psfigure{fish}{3.2in} \hspace{0.2in} \psfigure{fishworkload}{3.2in}}
\caption{\label{fish} Traced picture and work histogram}
\end{figure}

\subsubsection{Ray Tracer Results}

To test our multithreaded implementation, we traced pictures of
different complexities on various machine sizes. We adjusted the
picture size so that enough parallelism would be generated to justify
the use of the largest machine configuration used during our test
runs.

We first compared the uniprocessor timings of the multithreaded code
with those of the original sequential code, both running on the same
CM-5 processing node. The results showed no measurable difference
between the sequential and the multithreaded timings. To explain
this, we need to have a look at the actual thread granularity.  To
trace the picture shown in Figure~\ref{fish} with a resolution of
512$\times$512 pixels, around 300,000 threads are created over the
running time of about 1590 seconds, resulting in an average running
time per thread of about 3 milliseconds ( $\approx$ 100,000 Sparc
cycles). This long thread run length makes the average overhead of 80
cycles/thread negligible.

In a second step, we compared the speedup behavior of our
multithreaded ray tracer with that of an implementation using a static
load balancing scheme (see Table~\ref{results-ray-tracer}). The static
algorithm employs a simple work distribution that assigns exactly the
same number of rays to each node. For the static case we listed two
timings: the execution time of the fastest processor and the execution
time of the slowest processor. We can see that already with two nodes,
the slower processor requires 64\% more compute cycles than the
faster processor.  Even worse, this gap widens as we increase the
number of processors. With 64 nodes, the slowest processor is already
taking 3.6 times longer than the fastest processor.

As pointed out at the beginning of this section, the time required to
trace an individual ray can vary significantly, as shown by the
execution timings obtained with the static load balancer in
Table~\ref{results-ray-tracer}. To show this uneven work requirement,
we calculated a work histogram for our example. The left part of
Figure~\ref{fish} shows the traced picture and the right part shows
the work histogram. In the histogram brighter points represent higher
workloads, darker points lighter workloads.

\begin{table}[htb]
\begin{center}
\begin{small}
\begin{tabular}{||r||r|r|r||r|r|r||r||} \hline \hline
  & \multicolumn{3}{c||}{static load distribution} & \multicolumn{3}{c||}{dynamic load distribution}   &  \\ \hline
nodes    & min. time & max. time &   traced    & time      & max. traced & min. traced & impr.    \\ \hline \hline
 1 node  &           & 1590 sec. & 262144 rays & 1590 sec. & 262144 rays &             &          \\ \hline
 2 nodes & 602 sec.  &  988 sec. & 131072 rays &  795 sec. & 135312 rays & 126832 rays & 24    \% \\ \hline 
 4 nodes & 236 sec.  &  523 sec. &  65536 rays &  396 sec. &  79073 rays &  48867 rays & 32    \% \\ \hline
 8 nodes & 101 sec.  &  257 sec. &  32768 rays &  189 sec. &  45175 rays &  21464 rays & 35    \% \\ \hline
16 nodes &  46 sec.  &  128 sec. &  16384 rays &   90 sec. &  22616 rays &  10711 rays & 43    \% \\ \hline
32 nodes &  23 sec.  &   70 sec. &   8192 rays &   46 sec. &  12543 rays &   5859 rays & 52    \% \\ \hline
64 nodes &  10 sec.  &   36 sec. &   4096 rays &   23 sec. &   7210 rays &   2595 rays & 56    \% \\ \hline \hline
\end{tabular}
\end{small}
\caption{\label{results-ray-tracer} ray tracing result overview}
\end{center}
\end{table}

As a comparison, the multithreaded ray tracer not only performs better for all
machine configurations than the static solution, it even achieves perfect linear
speedup.

We added two additional columns to the data, showing the range of number of
pixels traced per processor. Those numbers reflect the effect of the dynamic
load balancer. As we expect, the difference between the maximum and minimum
number of pixels traced per node increases as we move to larger machine
configurations.
