\chapter{Results}

	\hsp{1em} 
	This chapter presents results from our implementation of the collision
	detection algorithm. In the first section, empirical
	results obtained from running the collision detection system are
	described through a series of figures. In the second section, the
	actual performance of the algorithm is described using speedup
	and efficiency metrics. Finally, the last section presents an
	explanation of the performance of the algorithm by analyzing
	the figures presented in the first section of this chapter
	and describing the actual runtime of several components of the
	collision detection system.

\section{Empirical Results}
	\hspace{1em}
	%In this section empirical data from running that collision
	%detection system are presented. 
	Results presented in this section were obtained
	by running the collision detection system on variable size
	data sets and recording the time taken to complete a collision
	detection operation. Two parallel computers where used to run
	the collision detection system. The first parallel computer
	consists of six dual processor AMD Athlon MP 1.2GHz computers
	networked together using a 100baseT network. Data in 
	Figure~\ref{fig:server-1to20} was obtained by running the
	collision detection system on the second parallel computer.
	This computer consists of twenty-one dual processor Intel 1GHz
	Pentium III computers interconnected with a high bandwidth,
	low latency network.

	In each test, a five level octree measuring one thousand units
	across is used to perform collision detection on spherical
	objects, each with a radius of 0.5 units. The spheres are randomly
	positioned within the volume enclosed by the octree. The number
	of objects used in each test is indicated in the figure.

        Figure~\ref{fig:server-local} shows the results of running the
        collision detection system on a dual-processor computer using one
        and two processors. As shown by this figure, performing collision
        detection using two processors completes in approximately half
        the time of the same operation performed using a single processor.

        \begin{figure}[h]
        \epsfxsize=5in
        \centerline{\epsffile{chap05/server_local_small.ps}}
        \caption{{\em
		Collision detection: local, 1 and 2 processors.}
	}
        \label{fig:server-local}
        \end{figure}

        In Figure~\ref{fig:server-lr-1p}, collision detection performed
        using a single processor located in the same computer and a remote
        computer are compared. In this figure, the distance between the
        line profiles represent the time needed to transport data to
        and from the remote computer.  Figure~\ref{fig:server-lr-2p}
        shows the same comparison but adds the use of a second processor.

        \begin{figure}
        \epsfxsize=5in
        \centerline{\epsffile{chap05/server_lr_1p_small.ps}}
        \caption{{\em
		Collision detection: local and remote, 1 processor.}
	}
        \label{fig:server-lr-1p}
        \end{figure}

        \begin{figure}
        \epsfxsize=5in
        \centerline{\epsffile{chap05/server_lr_2p_small.ps}}
        \caption{{\em
		Collision detection: local and remote, 2 processors.}
	} 
        \label{fig:server-lr-2p}
        \end{figure}

        Figure~\ref{fig:server-1p} shows the scalability of the
        collision detection system by comparing the time needed to
        perform the same collision detection operation using one
        to five remote computers. Each computer uses only a single
        processor. Figure~\ref{fig:server-2p} shows the results of the
        same test performed in Figure~\ref{fig:server-1p} when each
        computer uses two processors.

        \begin{figure}[h]
        \epsfxsize=5in
        \centerline{\epsffile{chap05/server_1p_small.ps}}
        \caption{{\em
		Collision detection: remote, 1 processor per machine,
		1 to 5 machines.}
	}
	\label{fig:server-1p} \end{figure}

        \begin{figure}
        \epsfxsize=5in
        \centerline{\epsffile{chap05/server_2p_small.ps}}
        \caption{{\em
		Collision detection: remote, 2 processors per machine,
		1 to 5 machines.}
	} 
	\label{fig:server-2p} \end{figure}

	Figure~\ref{fig:server-1to20} shows the performance of the
	collision detection system by comparing execution times for
	100,000 to 2,000,000 objects using one to forty processors.
	These computers are interconnected with a high
	bandwidth, low latency network. This network allows large amounts
	of data to be moved between computers at speeds in upward of
	eight times faster than a 100baseT Ethernet network. Besides 
	helping show how scalable the collision detection algorithm is,
	the primary purpose of this graph is to provide supporting
	evidence to the claim that the collision detection algorithm
	runs in ${\cal O}((n \ log \ n) / k)$ time. Unfortunately, these
	graphs appear linear. An explanation of this
	phenomenon is presented in the last section of this chapter.

        \begin{figure}
        \epsfxsize=5in
        \centerline{\epsffile{chap05/server_1to20_rotated.ps}}
        \caption{{\em
		Collision detection: remote, 2 processors per machine,
		1 to 20 machines.}
	} \label{fig:server-1to20} \end{figure}



\section{Analysis of Empirical Results}
	\hspace{1em}
	The tables in this section describe the performance of the collision
	detection system using actual runtime data. Each table contains
	the speedup and efficiency of the collision detection system for a
	variable number of processors and data set sizes. In each case,
	speedup is calculated by dividing the runtime of the serial
	algorithm by the parallel runtime of the algorithm. Speedup
	indicates how many time faster the collision detection system
	performs using multiple processors compared to the serial
	implementation of the algorithm. Efficiency is calculated by
	dividing the speedup of the algorithm by the number of processors
	used to attain the speedup value. The efficiency of an algorithm
	is a percentage that indicates how much of the total processing
	capabilities of the parallel computer an algorithm can use to
	while executing.

	In Table \ref{tab:perf_local_100k} and Table
	\ref{tab:perf_local_199k} speedup and efficiency are calculated
	for the collision detection system running on a dual processor
	computer with two different size data sets. As show in these
	tables, a larger data set causes the collision detection algorithm
	to perform more efficiently.

	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processor& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 1,460,885& NA& NA\\
	\hline
		2& 761,157& 1.919& 95.95\%\\
	\hline
	\end{tabular}
	\end{center}
	\caption{{\em
		Collision detection: Local computer,
		100,000 objects.}
	}
        \label{tab:perf_local_100k}
	\end{table}

	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processor& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 2,921,999& NA& NA\\
	\hline
		2& 1,471,116& 1.986& 99.31\%\\
	\hline
	\end{tabular}
	\end{center} 
	\caption{{\em
		Collision detection: Local computer,
		199,000 objects.}
	} \label{tab:perf_local_199k}
	\end{table}

	In Table \ref{tab:scale_1proc_100k}, \ref{tab:scale_1proc_199k},
	\ref{tab:scale_2proc_100k}, and \ref{tab:scale_2proc_199k},
	speedup and efficiency of the collision detection system are
	calculated using a variable number of processors. These tables
	demonstrate that the collision detection system is capable of
	scaling as the number of processors increases and still achieve
	speedup. However, as the number of processors increases,
	efficiency of the system decreases.  

	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processor& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 1,708,203& NA& NA\\
	\hline
		2& 965,051& 1.77& 88.5\%\\
	\hline
		3& 685,805& 2.49& 83.0\%\\
	\hline
		4& 571,763& 2.99& 74.8\%\\
	\hline
		5& 502,234& 3.40& 68.0\%\\
	\hline
	\end{tabular}
	\end{center} 
	\caption{{\em
		Collision detection: 1 processor per computer,
		100,000 objects.}
	}
        \label{tab:scale_1proc_100k}
	\end{table}

	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processor& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 3,379,940& NA& NA\\
	\hline
		2& 1,908,001& 1.77& 88.5\%\\
	\hline
		3& 1,395,906& 2.42& 80.7\%\\
	\hline
		4& 1,140,158& 2.96& 74.1\%\\
	\hline
		5& 986,878& 3.42& 68.5\%\\
	\hline
	\end{tabular}
	\end{center} 
	\caption{{\em
		Collision detection: 1 processor per computer,
		199,000 objects.}
	}
        \label{tab:scale_1proc_199k}
	\end{table}

	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processors& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 3,379,940& NA& NA\\
	\hline
		2& 1,953,981& 1.71& 85.5\%\\
	\hline
		4& 1,212,657& 2.79& 69.8\%\\
	\hline
		6& 928,884& 3.69& 61.5\%\\
	\hline
		8& 828,263& 4.30& 53.7\%\\
	\hline
		10& 713,694& 4.64& 46.4\%\\ 
	\hline
	\end{tabular}
	\end{center} 
	\caption{{\em
		Collision detection: 2 processors per computer,
		100,000 objects.}
	}
        \label{tab:scale_2proc_100k}
	\end{table}

	\begin{table}
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processor& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 3,379,940& NA& NA\\
	\hline
		2& 1,953,981& 1.73& 86.5\%\\
	\hline
		4& 1,212,657& 2.79& 69.7\%\\
	\hline
		6& 928,884& 3.64& 60.6\%\\
	\hline
		8& 828,263& 4.08& 51.0\%\\
	\hline
		10& 713,694& 4.74& 47.4\%\\ 
	\hline
	\end{tabular}
	\end{center} 
	\caption{{\em
		Collision detection: 2 processors per computer,
		199,000 objects.}
	}
        \label{tab:scale_2proc_199k}
	\end{table}

	Tables~\ref{tab:many_proc_1m} and~\ref{tab:many_proc_2m}
	shows that as the number of processors increases the system can
	retain efficiency if the amount of work (the number of objects)
	is increased.
	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processor& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 29,537,415& NA& NA\\
	\hline
		2& 15,596,299& 1.89& 94.7\%\\
	\hline
		10& 3,615,147& 8.17& 81.7\%\\
	\hline
		20& 2,177,746& 13.56& 67.8\%\\
	\hline
		30& 1,682,112& 17.56& 58.5\%\\
	\hline
		40& 1,480,608& 19.95& 49.9\%\\ 
	\hline
	\end{tabular}
	\end{center} 

	\caption{{\em
		Collision detection: 2 processors per computer,
		1,000,000 objects.}
	}
        \label{tab:many_proc_1m}

	\begin{center}
	\begin{tabular}{|c|c|c|c|}
	\hline
		Processors& Execution time ($\mu$sec.)& Speedup& Efficiency\\
	\hline
		1& 59,706,876& NA& NA\\
	\hline
		2& 31,332,310& 1.91& 95.3\%\\
	\hline
		10& 7,215,860& 8.27& 82.7\%\\
	\hline
		20& 4,298,207& 13.89& 69.5\%\\
	\hline
		30& 3,331,193& 17.92& 59.7\%\\
	\hline
		40& 2,889,864& 20.66& 51.7\%\\
	\hline
	\end{tabular}
	\end{center} 
	\caption{{\em
		Collision detection: 2 processors per computer,
		2,000,000 objects.}
	}
        \label{tab:many_proc_2m}
	\end{table}

\section{Analysis of Algorithm Runtime}

	One of the goals of obtaining empirical data of the runtime of
	this algorithm was to provide supporting evidence to the claim
	that it performs in ${\cal O}(n \ log \ n ) / k$ time. Figure
	\ref{fig:server-1to20} was intended to do this by
	producing data that when graphed, resulted in a curve similar to
	an $n \ log \ n$ curve. Unfortunately, none of the plotted lines
	in Figure \ref{fig:server-1to20} are curved. In fact,
	these lines appear linear.

	To understand why these lines do not fit a characteristic $n \
	log \ n$ curve, individual components that contribute to the
	runtime of the algorithm where timed and compared. Based on
	our findings, all operations performed internal to the collision
	detection system are performing as expected, except for the
	{\bf ResolveObject()} routine, which is responsible for generating
	the octal codes for each object. 

	The following list of functions and times are the primary
	contributing factors that make up the runtime of the collision
	detection system.

	\begin{itemize}
	\item
	Slave computer: {\bf qsort()} 88,953 $\mu$ sec.
	\item
	Slave computer: {\bf ResolveObject()} 1,307,631 $\mu$ sec.
	\item
	Networked slave computer: {\bf MergeSlaveResults()} 38,622 $\mu$
		sec.
	\item
	Master computer: {\bf MergeSlaveResults()} 791,490 $\mu$ sec.
	\end{itemize}

	Obviously, the major contributing factor to the runtime of
	the collision detection algorithm is the {\bf ResolveObject()}
	function. The runtime of the {\bf ResolveObject()} function grows
	linearly with the number of objects it operates on and, because
	the runtime of the {\bf ResolveObject()} function is an order of
	magnitude greater than the other runtimes, the effects other
	contributing components have on the overall runtime of the
	collision detection algorithm are diminished. This explains
	why the lines in Figure \ref{fig:server-1to20} appear
	so linear.

	The second largest contributing factor in the list is the
	{\bf MergeSlaveResults()} function performed by the master
	process. Although in this example, the runtime for the
	{\bf MergeSlaveResults()} function appears large compared to the
	{\bf qsort()} runtime, this is actually the effect of the number
	of processors being used in the collision detection system. In
	this example, forty slave processors are being used. If $k$
	was smaller, or $n$ was sufficiently larger, then the runtime of
	the {\bf qsort()} routine would dominate all other contributing
	factors and make the curves in Figure \ref{fig:server-1to20}
	appear more $n \ log \ n$.

% Figs ....




