| 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} |