From: Kevin M. Rosenberg Date: Sun, 25 Feb 2001 17:57:49 +0000 (+0000) Subject: r585: no message X-Git-Tag: debian-4.5.3-3~432 X-Git-Url: http://git.kpe.io/?p=ctsim.git;a=commitdiff_plain;h=d495f34264b1b1bcfdd78ee153c900d9e64b5f7c r585: no message --- 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. diff --git a/doc/ctsim.prj b/doc/ctsim.prj index 55b31df..bb92ccd 100644 --- a/doc/ctsim.prj +++ b/doc/ctsim.prj @@ -4,9 +4,9 @@ 1 1 ctsim.tex -18 -5 -2 +21 +6 +1 ctsim-gui.tex @@ -14,7 +14,19 @@ TeX 12282 0 602 60 26 76 176 176 1253 763 ctsim.tex TeX -134230010 0 103 29 125 19 22 22 1099 609 +402665466 0 125 1 124 1 22 22 1099 609 +ctsim-install.tex +TeX +12282 1 0 1 4 1 110 110 1187 697 +psbox.tex +TeX +4090 0 0 1 0 1 88 88 1004 675 +ctsim-algorithms.tex +TeX +4091 2 8 22 8 36 44 44 960 631 +ctsim-sgp.tex +TeX +4090 0 1 1 0 1 44 44 960 631 ctsim-appendix.tex TeX 268447738 0 0 1 0 2 44 44 1121 631 @@ -27,9 +39,6 @@ TeX mytitle.sty DATA 273679026 0 9 1 8 22 66 66 1143 653 -ctsim-install.tex -TeX -268447738 0 34 10 42 1 110 110 1187 697 ctsim-web.tex TeX 268447739 0 24 50 0 60 88 88 1165 675 @@ -75,5 +84,6 @@ TeX *ctsim-textui *ctsim-web *ctsim-install -*ctsim-appendix +*ctsim-algorithms +*ctsim-sgp < diff --git a/doc/ctsim.tex b/doc/ctsim.tex index 18cdb94..c6cfc80 100644 --- a/doc/ctsim.tex +++ b/doc/ctsim.tex @@ -10,8 +10,8 @@ \usepackage{hyperref} \input{psbox.tex} -\latexonly{\includeonly{ctsim-concepts,ctsim-install,ctsim-gui,ctsim-textui,ctsim-web,ctsim-appendix}} -\hyphenation{poly-gon-al} +\latexonly{\includeonly{ctsim-concepts,ctsim-install,ctsim-gui,ctsim-textui,ctsim-web,ctsim-algorithms,ctsim-sgp}} +\hyphenation{poly-gon-al multi-thread-ing} \newcommand{\ctsim}{\texttt{CTSim}} \newcommand{\ctsimtext}{\texttt{CTSimText}} @@ -121,8 +121,8 @@ I hope that you enjoy \ctsim! \include{ctsim-textui} \include{ctsim-web} \include{ctsim-install} - \appendix +\include{ctsim-algorithms} \include{ctsim-sgp} \newpage