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.