\documentstyle{article}
\textwidth=6.5in
\textheight=9.5in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin=-0.8in     % lws?
\topskip=0pt
\parindent=1em


\begin{document}
\bibliographystyle{plain}
\noindent
{\LARGE \bf CLEMSON UNIVERSITY} \\
{\footnotesize \it DEPARTMENT OF COMPUTER SCIENCE} $\bullet$
{\footnotesize \it CLEMSON, SOUTH CAROLINA 29634-1906} \\
{\footnotesize \it Office:(803) 656-5877} $\bullet$ 
{\footnotesize \it Department:(803) 656-3444} $\bullet$ 
{\footnotesize \it Home:(803) 639-4426} $\bullet$ 
{\footnotesize \it fredh@cs.clemson.edu} \\
\underline{\hspace{6.5in}} 

\vspace{24pt}

\noindent
\today

\vspace{24pt}

\noindent
SIAM\\
Attention: Conference Department\\
3600 University City Science Center \\
Philadelphia, PA  19104-2688

\vspace{24pt}

\noindent
Dear Conference Department:

\vspace{12pt}

\noindent
Enclosed you will find a two page abstract with a page of references entitled 
``Parallel Computation of Steiner Minimal Trees'' that I would like to
present as an oral presentation at the Seventh SIAM Conference on
Parallel Processing for Scientific Computing.

\vspace{12pt}

\noindent
This paper relates to the conference theme:
Parallel Processing in Mathematics

\vspace{12pt}

\noindent
I can be reached via email at: fredh@cs.clemson.edu \\
or via phone at:
office: (803)656-5877; home: (803) 639-4426; fax: (803) 639-0145

\vspace{12pt}

\noindent
Thank you for your time and consideration.  I look forward to receiving
a response.

\vspace{24pt}

\noindent
Sincerely,  

\vspace{36pt}
\noindent
Frederick C. Harris, Jr.  

\newpage
\begin{center}
{\Large Parallel Computation of Steiner Minimal Trees }\\
Frederick C. Harris, Jr.  \\
Department of Computer Science \\
Clemson University \\
%Clemson, SC 29634-1906 \\
%fredh@cs.clemson.edu \\
\end{center}

	\section{Introduction}

	\hspace{1em}Minimizing a network's length is one of the oldest
	optimization problems in mathematics and, consequently, it has
	been worked on by many of the leading mathematicians in
	history.  In the mid-seventeenth century a simple problem was
	posed:  Find the point $P$ that minimizes the sum of the
	distances from $P$ to each of three given points in the plane.
	Solutions to this problem were derived independently by Fermat,
	Torricelli and Cavalieri.  They all deduced that either $P$ is
	inside the triangle formed by the given points and that the
	angles at $P$ formed by the lines joining $P$ to the three
	points are all $120^{\circ}$, or $P$ is one of the three
	vertices and the angle at $P$ formed by the lines joining $P$
	to the other two points is greater than or equal to
	$120^{\circ}$.

	In 1934 K\"{o}ssler and Jarn\'{i}k generalized the network
	minimization problem even further~\cite{jk34:omgodb}:  Given
	$n$ points in the plane find the shortest possible connected
	network containing these points.  This generalized problem,
	however, did not become popular until the book, {\it What is
	Mathematics}, by Courant and Robbins~\cite{cr41:wim}, appeared
	in 1941. Courant and Robbins linked the name Steiner with this
	form of the problem proposed by K\"{o}ssler and Jarn\'{i}k, and
	it became known as the Steiner Minimal Tree problem.  The
	general solution to this problem allows multiple points to be
	added, each of which is called a Steiner Point.

	Much is known about the exact solution to the Steiner Minimal
	Tree problem.  Those who wish to learn about some of the
	spin-off problems are invited to read the introductory article
	by Bern and Graham~\cite{bg89:tsnp}, the excellent survey paper
	on this problem by Hwang and Richards~\cite{hr92:survey}, or
	the recent volume in The Annals of Discrete Mathematics devoted
	completely to Steiner Tree problems~\cite{hrw:annals}.  Some of
	the basic pieces of information about the Steiner Minimal Tree
	problem that can be gleaned from these articles are: (i) Melzak
	developed the first algorithm for Steiner Minimal Trees in
	1961, (ii) all of the original $n$ points will be
	of degree 1, 2, or 3, (iii) the Steiner Points are all of
	degree 3, (iv) any two edges meet at an angle of at least
	$120^{\circ}$ in the Steiner Minimal Tree, and (v) at most
	$n-2$ Steiner Points will be added to the network.

	This paper concentrates on the Steiner Minimal Tree problem,
	henceforth referred to as the SMT problem.  In Section 2 we
	review the known algorithms for calculating Steiner Minimal
	Trees. In Section 3 we present the first parallel algorithm for
	calculating SMT's and some new results are presented in Section 4.

\section{Current Implementations}

	\hspace{1em}The development of the first working implementation
	of Melzak's algorithm sparked a move into the computerized
	arena for the calculation of SMT's.  As we saw earlier Cockayne
	and Schiller~\cite{cs72:cosmt} had implemented Melzak's
	Algorithm and could calculate the SMT for all arrangements of 7
	points.  This was followed almost immediately by Boyce and
	Seery's program which they called
	STEINER72~\cite{bs75:aivocspsftmnp}.  Their work, done at Bell
	Labs could calculate the SMT for all 10 point problems.  They
	continued to work on the problem and in personal communication
	with Cockayne said they could solve 12 point problems with
	STEINER73.  Yet even with quite a few people working on the
	problem, the number of points that any program could handle was
	still very small.

	It was not until 1981 that anyone was able to characterize a
	few of the invalid tree structures mentioned by Melzak.  These
	characterizations were accomplished by Pawel Winter and were
	based upon several geometric constructions which enable one to
	eliminate many of the possible combinations previously
	generated.  He implemented these  improvements in a program
	called GeoSteiner~\cite{winter85:aaftspitep}.  In his work he
	was able to calculate in under 30 seconds  SMT's for problems
	having up to 15 vertices and stated that ``with further
	improvements, it is reasonable to assert that point sets up to
	30 V-points could be solved in less than an
	hour~\cite{winter85:aaftspitep}.''

	In 1986 Cockayne and Hewgill were able to calculate the SMT for
	79 of 100 randomly generated 30 point problems.  The remaining
	21 would not decompose into blocks of size 17 or smaller, and
	thus would have taken too much computation
	time~\cite{ch86:ecosmtitp}.  This calculation was implemented
	in the program they called EDSTEINER86.  In 1989 Cockayne and
	Hewgill made some simple changes that allowed them to calculate
	the SMT for 77 of 100 randomly generated 100 point
	problems~\cite{ch92:icopsmt}. The other 23 problems could not
	be calculated in less than 12 hours and were therefore
	terminated.

\section{Parallel Algorithm}

	\hspace{1em}Since the sequential version of the code does not
	lend itself to easy parallelization, the next thing to do is
	back up and develop an understanding for how the algorithm
	works.  The first thing that is obvious from the code is that
	you select a left subtree and then try to mate it with possible
	right subtrees.  Upon further examination we come to the
	conclusion that a left tree will mate with all trees that are
	shorter than it, and all trees of the same height that appear
	after it on Q\_list, but it will never mate with any tree that
	is taller.

	This analysis yields the need for the first function in our
	parallel algorithm which we will call \verb+a_before_b()+.
	This piece of code will determine if node $a$ would have come
	before node $b$ in Winter's Q\_list.  This is necessary since
	in a parallel implementation the calculations will not happen
	in the same order as they would have in the sequential version,
	so things will not be added to Q\_list in the same order.  With
	this function  we are able to finish the function
	\verb+mate()+.  This is a boolean function which determines if
	node $a$ (left) can mate with node $b$ (right).

	Now that the foundational building blocks are completed, design
	attention can be turned to the main algorithm.  The description
	of this is in a master--slave perspective.  This perspective
	was taken due to the structure of most parallel architectures,
	as well as the fact that all nodes on the Q\_list need a
	sequencing number assigned to them. The master will therefore
	be responsible for numbering the nodes and maintaining the main
	Q\_list and T\_list.

	The idea for the master -- slave interaction came from a paper
	by Quinn and Deo~\cite{qd85:ubspbbbba}, on parallel algorithms
	for Branch-and-Bound problems.  Their idea was to let the
	master have a list of work that needs to be done.  Each slave
	is assigned to a processor.  Each slave requests work, is given
	some, and during its processing creates more work to be done.
	This new work is placed in the master's work list, which is
	sorted in some fashion.  When a slave runs out of work to do,
	it requests more from the master.  They noted that this leaves
	some processors idle at times (particularly when the problem
	was starting and stopping), but this approach provides the best
	utilization if all branches are independent.

	This description almost perfectly matches the problem at hand.
	First, we will probably have a fixed number of processors which
	can be determined at runtime. Secondly we have a list of work
	that needs to be done.  The hard part is implementing a sorted
	work list in order to obtain a better utilization.  This is
	implemented in what we term the Proc\_list, which is a list of
	the processes that either are currently running or have not yet
	started.  This list is primed with the information about the
	initial members of Q\_list, and for every new node put on the
	Q\_list, a node which contains information about the Q\_list
	node, is placed on the Proc\_list in the a\_before\_b() sorted
	order.


\section{Results}

	\hspace{1em}From the literature it is obvious that the current
	standard for calculating SMT's has been established by Cockayne
	and Hewgill.  Their work on SMT's has pushed the boundary of
	computation out from the 15 point problems of Winter to being
	able to calculate SMT's for a large percentage of 100 point
	problems.

	Cockayne and Hewgill, in their investigation of the
	effectiveness of EDSTEINER89, randomly generated 100 problems
	with 100 points inside the unit square.  They set up a CPU
	limit of 12 hours, and 77 of 100 problems finished within that
	limit.  They described the average execution times as follows:
	T\_list construction averaged 209 minutes, Forest Management
	averaged 27 minutes, and Extraction averaged 10.8 minutes.

	The parallel algorithms we have presented here have been
	implemented in a program called PARSTEINER94.  This
	implementation is only the second SMT program since Winter's
	GEOSTEINER in 1981 and is the first parallel code.  The major
	reason that the number of SMT programs is so small is due to
	the fact that any implementation is necessarily complex.

	While preparing the code for this work, Cockayne and Hewgill
	were kind enough to supply us with 40 of the problems generated
	for \cite{ch92:icopsmt} along with their execution times.
	These data sets were given as input to PARSTEINER94, and the
	calculation timed.  For all 40 cases, the average time to
	generate T\_list was less than 20 minutes.  This is exciting
	because we have been able to generate T\_list properly, while
	cutting an order of magnitude off the time.

	These results are quite promising for various reasons.  First,
	the parallel implementation presented in this work is quite
	scalable, and therefore could be run with many more processors,
	thereby enhancing the speedup provided.  Secondly, with the PVM
	platform used, we can in the future port this work to a real
	parallel MIMD machine,  which will have much less communication
	overhead, or to a shared memory machine, where the
	communication could all but be eliminated, and expect the
	speedup to improve much more.


%\section{Future Work}

\bibliography{/home/phd/fredh/papers/bibdir/steiner,/home/phd/fredh/papers/bibdir/simulated,/home/phd/fredh/papers/bibdir/parallel,/home/phd/fredh/papers/bibdir/reliable}

\end{document}
