doc/ctsim-algorithms.tex

   1 \chapter{Algorithms}\label{algorihms}\index{Algorithms}
   2 \setheader{{\it Appendix \thechapter}}{}{}{\ctsimheadtitle}{}{{\it Appendix \thechapter}}%
   3 \ctsimfooter%
   4
   5 \ctsim\ uses a number of interesting algorithms. This appendix details some
   6 of the techniques that \ctsim\ uses.
   7 \section{Background Processing}\label{backgroundprocessing}\index{Background processing}
   8 \textbf{Key Concepts}\\
   9 \hspace*{1cm}\texttt{Multithreading}\\
  10 \hspace*{1cm}\texttt{Critical sections}\\
  11 \hspace*{1cm}\texttt{Message passing}\\
  12 \hspace*{1cm}\texttt{Re-entrant code}\\
  13
  14 The \ctsim\ graphical shell can optionally perform background
  15 processing. \ctsim\ uses threads as tools to achieve this
  16 functionality. Using multiple threads, termed
  17 \emph{multithreading}, allows \ctsim\ to:
  18
  19 \begin{itemize}
  20 \item Execute a lengthy calculation in the background while the graphical shell remains
  21 available for use.
  22 \item Automatically take advantage of multiple central processing units (CPU's) in a
  23 symmetric multiprocessing (SMP) computer.
  24 \end{itemize}
  25
  26 When background processing option is turned on or when \ctsim\ is
  27 running on a SMP computer, and \ctsim\ is directed to perform
  28 reconstructions or projections, \ctsim\ will spawn a
  29 \emph{Background Supervisor} thread. This supervisor thread then
  30 creates a \emph{Supervisor Event Handler} (supervisor). The
  31 supervisor thread then waits for the supervisor to finish. The
  32 supervisor communicates with the rest of \ctsim\ by using message
  33 passing to avoid issues with re-entrant code.
  34
  35 The supervisor registers itself, as always via message passing,
  36 with the \emph{Background Manager} which will display the
  37 execution progress in a pop-up window. The supervisor also
  38 registers itself with the document being processed. This is done
  39 so that if the document is closed, the document can send a message
  40 to the supervisor directing the supervisor to cancel the
  41 calculation.
  42
  43 After registering with \ctsim\ components, the supervisor creates
  44 \emph{Worker Threads}. These worker threads are the processes that
  45 actually perform the calculations. By default, \ctsim\ will create
  46 one worker thread for every CPU in the system. The workers
  47 communicate with the supervisor via message passing. As the
  48 workers complete unit blocks, they send progress messages to the
  49 supervisor. The supervisor then sends progress messages to
  50 background manager which displays a gauge of the progress.
  51
  52 After the workers have completed their tasks, they send a status
  53 message to the supervisor. When all the workers have finished, the
  54 supervisor will kill the worker threads. The supervisor then
  55 collates the work units from the workers and creates a new \ctsim\
  56 window to display the finished work.
  57
  58 The supervisor then deregisters itself via messages with the
  59 background manager and the document. The background manager
  60 removes the progress gauge from its display and resizes its
  61 window.
  62
  63 Finally, the background supervisor exits and background supervisor
  64 thread terminates. This structure may seem more complex than is
  65 necessary, but it has several advantages:
  66
  67 \begin{itemize}
  68 \item Since the various threads do not call objects in other threads, problems
  69 with re-entrant code are eliminated.
  70 \item A supervisor can parallel process with any number of worker threads
  71 to take advantage of potentially large numbers of CPU's in SMP
  72 computers.
  73 \end{itemize}
  74
  75 Though the various threads do not directly call each other, it is
  76 prudent to lock the class data structures with \emph{Critical
  77 Sections}. Critical sections lock areas of code and prevent more
  78 than one thread to access a section of code at a time. This is
  79 used when maintaining the tables of worker threads in the
  80 supervisor and also when maintaining the tables of supervisors in
  81 the background manager.
  82
  83 This functionality has been compartmentalized in the inheritable
  84 C++ classes \texttt{BackgroundSupervisor},
  85 \texttt{BackgroundWorkerThread}, and
  86 \texttt{BackgroundProcessingDocument}. These classes serve as base
  87 classes for the reconstruction and projection multithreading
  88 classes.