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
   8 \section{Phantom Processing}\label{phantomprocessing}
   9 \textbf{Key Concepts}\\
  10 \hspace*{1cm}\texttt{Geometric transformations}\\
  11 \hspace*{1cm}\texttt{Matrix algebra}\\
  12
  13 Phantom objects are processed in two different ways: rasterization
  14 and projections. \ctsim\ uses optimized techniques to perform
  15 those procedures.
  16
  17 The primary tool used to optimize these processes is
  18 \emph{Geometric transformations}. For every primitive
  19 \helpref{phantom element}{phantomelements}, a standardized
  20 configuration is defined. This standard configuration is used to
  21 speed the process of collecting projections.
  22
  23 In general, to transform an object into the standard
  24 configuration, the following sequence of transformations occur.
  25 When this sequence is performed, the coordinates are termed the
  26 \emph{normalized phantom element} coordinates.
  27
  28 \begin{itemize}
  29 \item Scaling by the inverse of its size, that is usually
  30 scaling by \texttt{(1/dx,1/dy)}.
  31 \item Translating the object to the origin, that is usually translation by
  32 \texttt{(-cx,-cy)}.
  33 \item Rotating the object by \texttt{-r}.
  34 \end{itemize}
  35
  36 These steps can by combined into a single matrix multiplication
  37 which involves only 4 multiplications and 6 additions to transform
  38 both \texttt{x} and \texttt{y} coordinates. This matrix is
  39 precalculated and stored when the phantom is created. Similarly,
  40 the inverse of the matrix is precalculated and store to perform
  41 the inverse of this transformation.
  42
  43 As an example of this technique, consider the problem of finding
  44 the length of an arbitrary line that may intersect an arbitary
  45 ellipse. Define the endpoints of the line by \texttt{(x1,y1)} and
  46 \texttt{(x2,y2)}.
  47
  48 \begin{enumerate}
  49 \item First, transform the coordinates into the normalized
  50 phantom element coordinates. At this point, the ellipse will have
  51 been transformed into a unit circle centered at \texttt{(0,0)}.
  52 \item Translate the
  53 coordinates by \texttt{(-x1,-y2)}. The line now has the endpoint
  54 centered at the origin. The ellipse will now have its center at
  55 \texttt{(-x1,-y1)}.
  56 \item Rotate the coordinates by the negative of angle of the line
  57 with respect to the x-axis.
  58 \end{enumerate}
  59
  60 At this point the line will now lie along the positive x-axis with
  61 one end at \texttt{(0,0)}. The circle will be rotated around the
  62 origin as well. At this point, it is fairly trivial to calculate
  63 the length of the intersection of the line with the unit circle.
  64 For example, if the \texttt{y} coordinate for the center of the
  65 circle is greater than \texttt{1} or less than \texttt{-1}, then
  66 we know that the unit circle doesn't intersect the line at all and
  67 stop further processing. Otherwise, the endpoints of the
  68 intersection of the line with the unit circle is a simple
  69 calculation.
  70
  71 Those new, intersected endpoints are then inverse transformed by
  72 reverse of the above transformation sequence. After the inverse
  73 translation, the transformed endpoints will be the endpoints of
  74 the line that intersect the actual ellipse prior to any
  75 transformations.
  76
  77 Though this sequence of events is somewhat complex, it is quite
  78 fast since the multiple transformations can be combined into a
  79 single matrix multiplication. Further, this technique is amendable
  80 to rapidly calculating the intersection of a line with any of the
  81 phantom elements that \ctsim\ supports.
  82
  83 \section{Background Processing}\label{backgroundprocessing}\index{Background processing}
  84 \textbf{Key Concepts}\\
  85 \hspace*{1cm}\texttt{Multithreading}\\
  86 \hspace*{1cm}\texttt{Critical sections}\\
  87 \hspace*{1cm}\texttt{Message passing}\\
  88 \hspace*{1cm}\texttt{Re-entrant code}\\
  89
  90 The \ctsim\ graphical shell can optionally perform background
  91 processing. \ctsim\ uses threads as tools to achieve this
  92 functionality. Using multiple threads, termed
  93 \emph{multithreading}, allows \ctsim\ to:
  94
  95 \begin{itemize}
  96 \item Execute a lengthy calculation in the background while the graphical shell remains
  97 available for use.
  98 \item Automatically take advantage of multiple central processing units (CPU's) in a
  99 symmetric multiprocessing (SMP) computer.
 100 \end{itemize}
 101
 102 When background processing option is turned on or when \ctsim\ is
 103 running on a SMP computer, and \ctsim\ is directed to perform
 104 reconstruction, rasterization, or projections, \ctsim\ will spawn
 105 a \emph{Background Supervisor} thread. This supervisor thread then
 106 creates a \emph{Supervisor Event Handler} (supervisor).  The
 107 supervisor communicates with the rest of \ctsim\ by using message
 108 passing to avoid issues with re-entrant code.
 109
 110 Though the various threads do not directly call each other, it is
 111 prudent to lock the class data structures with \emph{Critical
 112 Sections}. Critical sections lock areas of code and prevent more
 113 than one thread to access a section of code at a time. This is
 114 used when maintaining the tables of worker threads in the
 115 supervisor and also when maintaining the tables of supervisors in
 116 the background manager.
 117
 118 The supervisor registers itself via message passing with the
 119 \emph{Background Manager} which will display the execution
 120 progress in a pop-up window. The supervisor also registers itself
 121 with the document being processed. This is done so that if the
 122 document is closed, the document can send a message to the
 123 supervisor directing the supervisor to cancel the calculation.
 124
 125 After registering with \ctsim\ components, the supervisor creates
 126 \emph{Worker Threads}. These worker threads are the processes that
 127 actually perform the calculations. By default, \ctsim\ will create
 128 one worker thread for every CPU in the system. The workers
 129 communicate with the supervisor via message passing. As the
 130 workers complete unit blocks, they send progress messages to the
 131 supervisor. The supervisor then sends progress messages to
 132 background manager which displays a gauge of the progress.
 133
 134 After the workers have completed their tasks, they send a status
 135 message to the supervisor. When all the workers have finished, the
 136 supervisor will kill the worker threads. The supervisor then
 137 collates the work units from the workers and creates a new \ctsim\
 138 window to display the finished work.
 139
 140 The supervisor then deregisters itself via messages with the
 141 background manager and the document. The background manager
 142 removes the progress gauge from its display and resizes its
 143 window. Finally, the background supervisor exits and background
 144 supervisor thread terminates.
 145
 146 This functionality has been compartmentalized into inheritable C++
 147 classes \texttt{BackgroundSupervisor},
 148 \texttt{BackgroundWorkerThread}, and
 149 \texttt{BackgroundProcessingDocument}. These classes serve as base
 150 classes for the reconstruction, rasterization, and projection
 151 multithreading classes.
 152
 153 \subsection{Advantages}
 154 This structure may seem more complex than is necessary, but it has
 155 several advantages:
 156
 157 \begin{itemize}
 158 \item Since the various threads do not call objects in other threads, problems
 159 with re-entrant code are eliminated.
 160 \item A supervisor can parallel process with any number of worker threads
 161 to take advantage of potentially large numbers of CPU's in SMP
 162 computers.
 163 \item Allows for continued user-interaction with \ctsim\ while lengthy calculations
 164 are performed in the background.
 165 \end{itemize}
 166
 167 \subsection{Disadvantages}
 168
 169 The above advantages are not free of cost. The disadvantages
 170 include:
 171
 172 \begin{itemize}
 173 \item Increased memory usage.\\
 174  The workers threads allocate memory to store their intermediate
 175 results. When the worker threads finish, the supervisor allocates
 176 memory for the final result and collates the results for the
 177 workers. This collation results in a doubling of the memory
 178 requirements. Of course, after collation the supervisor
 179 deallocates the memory used by the workers.
 180 \item Slower execution on single CPU systems. \\
 181 The message passing between threads and collation
 182 of results for worker threads adds overhead compared to simply
 183 calculating the result directly in the foreground. On single CPU
 184 systems this results in slower processing compared to foreground
 185 processing. On dual-CPU and greater SMP systems, though, the
 186 advantage of using multiple CPU's in parallel exceeds the overhead
 187 of background processing.
 188 \end{itemize}