rts.tex

\chapter{Runtime System Improvements}
\label{chap:rts}

\status{This chapter is finished!}

Early in the project
we tested two manually parallelised programs:
a raytracer and a mandelbrot image generator.
Both programs have a single significant loop
whose iterations are independent of one another.
We expect that a good automatic parallelisation system will parallelise this
loop as it is the best place to introduce parallelism.
When we parallelised this loop manually,
we did not get the speedups that we expected.
Therefore,
we chose to address the performance problems
before we worked on automatic parallelism.
Throughout this chapter
we continue to use these two benchmarks, along with a naive Fibonacci
program (Page~\pageref{page:fibs}).
These benchmarks are not diverse and they all create a lot of
AND-parallelism,
most of which is independent.
We use these benchmarks deliberately to test that our runtime system can
handle large amounts of parallelism efficiently.

In this chapter we investigate and correct these performance problems.
We start with the garbage collector in Section~\ref{sec:rts_gc};
we analyse the collector's effects on performance and tune its parameters
to improve performance.
In Section~\ref{sec:rts_original_scheduling} we describe how the existing runtime
system schedules sparks,
and provide background material for
Section~\ref{sec:rts_original_scheduling_performance},
which benchmarks the runtime system and describes two significant problems with
spark scheduling.
We address one of these problems by introducing work stealing in
Section~\ref{sec:rts_work_stealing}.
Then in Section~\ref{sec:rts_reorder} we reorder conjuncts in independent
parallel conjunctions to work around the second spark scheduling problem.
Finally, in Section~\ref{sec:rts_work_stealing2} we make further
improvements to
work stealing and change the data structures and algorithms used to manage
idle engines,
including how idle engines look for work, sleep and are woken up.

\input{rts_gc}
\input{rts_original_scheduling}
\input{rts_original_scheduling_performance}
\input{rts_work_stealing}
\input{rts_reorder}
%\input{rts_thread_pinning}
\input{rts_work_stealing2}

%\section{Proposed scheduling tweaks}
%\label{sec:proposed_tweaks}
%\status{Not written, May move to TS chapter}
%
%I really think that this section will move to the \tscope chapter,
%it will have more in common with that chapter and more data will be
%available.
%Secondly, \tscope can be used with micro-benchmarks to measure the
%average costs of certain operations in the RTS.
%I will not write it until at least the rest of this chapter is finished.