X-Git-Url: http://git.kpe.io/?a=blobdiff_plain;f=doc%2Fctsim-algorithms.tex;fp=doc%2Fctsim-algorithms.tex;h=31346aebd94aa51a589363d11e2f13798dab6194;hb=d495f34264b1b1bcfdd78ee153c900d9e64b5f7c;hp=0000000000000000000000000000000000000000;hpb=4d5f56994972346351a48730315a7d85924103ba;p=ctsim.git

diff --git a/doc/ctsim-algorithms.tex b/doc/ctsim-algorithms.tex
new file mode 100644
index 0000000..31346ae
--- /dev/null
+++ b/doc/ctsim-algorithms.tex
@@ -0,0 +1,88 @@
+\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.