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 graphical user interface
 108 of  \ctsim\ by using message passing to avoid issues with
 109 re-entrant code.
 110
 111 The supervisor registers itself via message passing with the
 112 \emph{Background Manager} which will display the execution
 113 progress in a pop-up window. The supervisor also registers itself
 114 with the document being processed. This is done so that if the
 115 document is closed, the document can send a message to the
 116 supervisor directing the supervisor to cancel the calculation.
 117
 118 After registering with \ctsim\ components, the supervisor creates
 119 \emph{Worker Threads}. These worker threads are the processes that
 120 actually perform the calculations. By default, \ctsim\ will create
 121 one worker thread for every CPU in the system. As the workers
 122 complete unit blocks, they notify the supervisor. The supervisor
 123 then sends progress messages to background manager which displays
 124 a gauge of the progress.
 125
 126 As the worker threads directly call the supervisor, it is crucial
 127 to lock the class data structures with \emph{Critical Sections}.
 128 Critical sections lock areas of code and prevent more than one
 129 thread to access a section of code at a time. This is used when
 130 maintaining the tables of worker threads in the supervisor.
 131
 132 After the workers have completed their tasks, they notify the
 133 supervisor. When all the workers have finished, the supervisor
 134 kills the worker threads. The supervisor then collates the work
 135 units from the workers and sends a message to \ctsim\ to create a
 136 new window to display the finished work.
 137
 138 The supervisor then deregisters itself via messages with the
 139 background manager and the document. The background manager
 140 removes the progress gauge from its display and resizes its
 141 window. Finally, the background supervisor exits and background
 142 supervisor thread terminates.
 143
 144 This functionality has been compartmentalized into inheritable C++
 145 classes \texttt{BackgroundSupervisor},
 146 \texttt{BackgroundWorkerThread}, and
 147 \texttt{BackgroundProcessingDocument}. These classes serve as base
 148 classes for the reconstruction, rasterization, and projection
 149 multithreading classes.
 150
 151 \subsection{Advantages}
 152 This structure may seem more complex than is necessary, but it has
 153 several advantages:
 154
 155 \begin{itemize}
 156 \item Since the background threads do not directly call objects in the graphical
 157 user interface thread, problems with re-entrant code in the
 158 graphical interface are eliminated.
 159 \item A supervisor can parallel process with any number of worker threads
 160 to take advantage of potentially large numbers of CPU's in SMP
 161 computers.
 162 \item Allows for continued user-interaction with \ctsim\ while lengthy calculations
 163 are performed in the background.
 164 \end{itemize}
 165
 166 \subsection{Disadvantages}
 167
 168 The above advantages are not free of cost. The disadvantages
 169 include:
 170
 171 \begin{itemize}
 172 \item Increased memory usage.\\
 173  The workers threads allocate memory to store their intermediate
 174 results. When the worker threads finish, the supervisor allocates
 175 memory for the final result and collates the results for the
 176 workers. This collation results in a doubling of the memory
 177 requirements. Of course, after collation the supervisor releases
 178 the memory used by the workers.
 179 \item Slower execution on single CPU systems. \\
 180 Creating multiple threads, sending progress messages to the
 181 background manager, and collation of results for worker threads
 182 adds overhead compared to simply calculating the result directly
 183 in the foreground. On single CPU systems this results in slower
 184 processing compared to foreground processing. On dual-CPU and
 185 greater SMP systems, though, the advantage of using multiple CPU's
 186 in parallel exceeds the overhead of background processing.
 187 \end{itemize}