\chapter{Algorithms}\label{algorihms}\index{Algorithms}
\setheader{{\it Appendix \thechapter}}{}{}{\ctsimheadtitle}{}{{\it Appendix \thechapter}}%
\ctsimfooter%

\ctsim\ uses a number of interesting algorithms. This appendix details some
of the techniques that \ctsim\ uses.
\section{Background Processing}\label{backgroundprocessing}\index{Background processing}
\textbf{Key Concepts}\\
\hspace*{1cm}\texttt{Multithreading}\\
\hspace*{1cm}\texttt{Critical sections}\\
\hspace*{1cm}\texttt{Message passing}\\
\hspace*{1cm}\texttt{Re-entrant code}\\

The \ctsim\ graphical shell can optionally perform background
processing. \ctsim\ uses threads as tools to achieve this
functionality. Using multiple threads, termed
\emph{multithreading}, allows \ctsim\ to:

\begin{itemize}
\item Execute a lengthy calculation in the background while the graphical shell remains
available for use.
\item Automatically take advantage of multiple central processing units (CPU's) in a
symmetric multiprocessing (SMP) computer.
\end{itemize}

When background processing option is turned on or when \ctsim\ is
running on a SMP computer, and \ctsim\ is directed to perform
reconstructions or projections, \ctsim\ will spawn a
\emph{Background Supervisor} thread. This supervisor thread then
creates a \emph{Supervisor Event Handler} (supervisor). The
supervisor thread then waits for the supervisor to finish. The
supervisor communicates with the rest of \ctsim\ by using message
passing to avoid issues with re-entrant code.

The supervisor registers itself, as always via message passing,
with the \emph{Background Manager} which will display the
execution progress in a pop-up window. The supervisor also
registers itself with the document being processed. This is done
so that if the document is closed, the document can send a message
to the supervisor directing the supervisor to cancel the
calculation.

After registering with \ctsim\ components, the supervisor creates
\emph{Worker Threads}. These worker threads are the processes that
actually perform the calculations. By default, \ctsim\ will create
one worker thread for every CPU in the system. The workers
communicate with the supervisor via message passing. As the
workers complete unit blocks, they send progress messages to the
supervisor. The supervisor then sends progress messages to
background manager which displays a gauge of the progress.

After the workers have completed their tasks, they send a status
message to the supervisor. When all the workers have finished, the
supervisor will kill the worker threads. The supervisor then
collates the work units from the workers and creates a new \ctsim\
window to display the finished work.

The supervisor then deregisters itself via messages with the
background manager and the document. The background manager
removes the progress gauge from its display and resizes its
window.

Finally, the background supervisor exits and background supervisor
thread terminates. This structure may seem more complex than is
necessary, but it has several advantages:

\begin{itemize}
\item Since the various threads do not call objects in other threads, problems
with re-entrant code are eliminated.
\item A supervisor can parallel process with any number of worker threads
to take advantage of potentially large numbers of CPU's in SMP
computers.
\end{itemize}

Though the various threads do not directly call each other, it is
prudent to lock the class data structures with \emph{Critical
Sections}. Critical sections lock areas of code and prevent more
than one thread to access a section of code at a time. This is
used when maintaining the tables of worker threads in the
supervisor and also when maintaining the tables of supervisors in
the background manager.

This functionality has been compartmentalized in the inheritable
C++ classes \texttt{BackgroundSupervisor},
\texttt{BackgroundWorkerThread}, and
\texttt{BackgroundProcessingDocument}. These classes serve as base
classes for the reconstruction and projection multithreading
classes.
