
\section{Winter's Sequential Algorithm}

	\vspace*{11pt}
	\subsection{Overview and Significance}

	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.

	As mentioned in Chapter II, Melzak's algorithm yields invalid
	answers and invalid tree structures for quite a few
	combinations of points.  It was not until 1981 that anyone was
	able to characterize a few of these invalid tree structures.
	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}.''

	\vspace*{11pt}
	\subsection{Winter's Algorithm}

	Winter's  breakthrough was based upon two things: the use of
	extended binary trees, and what he termed {\it pushing}.
	Winter proposed an extended binary tree as a means of
	constructing trees only once and easily identifying a Full
	Steiner Tree (FST: trees with $n$ vertices and $n-2$ Steiner
	Points) on the same set of vertices readily.

	{\it Pushing} came from the geometric nature of the problem and
	is illustrated in Figure~\ref{fig:pushing_example}.  It was
	previously known that the Steiner Point for a pair of points,
	$a$ and $b$, would lie on the circle that circumscribed that
	pair and their equilateral third point.  Winter set out to
	limit this region even further.  This limitation was
	accomplished by placing a pair of points, $a'$ and $b'$, on the
	circle at $a$ and $b$ respectively, and attempting to push them
	closer and closer together.  In his work Winter proposed and
	proved various geometric properties that would allow you to
	push $a'$ towards $b$ and $b'$ towards $a$.  If the two points
	ever crossed then it was impossible for the current branch of
	the sample space tree to contain a valid answer.

        \begin{figure}[h]
	\vspace*{22pt}
        \centerline{\psfig{figure=chap04/pushing_example.ps,height=3.0in}}
        \caption{\label{fig:pushing_example}An illustration of Winter's pushing.}
	\vspace*{22pt}
        \end{figure}

	Unfortunately, the description of Winter's algorithm is not as
	clear as one would hope, since the presence of \verb+goto+
	statements rapidly makes his program difficult to understand,
	and almost impossible to modify.  The initialization, which is
	given in Figure~\ref{fig:winter.step1}, is basically quite
	plain in its description.  Winter's goal is to build a list of
	FST's which are candidates for inclusion in the final answer.
	This list, called T\_list, is primed with the edges of the MST,
	thereby guaranteeing that the length of the SMT does not exceed
	the length of the MST.

	The rest of the algorithm sets about to expand what Winter
	termed as Q\_list,  which is a list of partial trees that the
	algorithm attempts to combine until no combinations are
	possible.  Q\_list is primed with the original input points.
	The legality of a combination is determined in the {\it
	Construct} procedure, which uses {\it pushing} to eliminate
	cases.  While this combination proceeds, the algorithm also
	attempts to take newly created members of Q\_list and create
	valid FST's out of them.  These FST's are then placed onto
	T\_list.  
	Winter's Algorithm appears in Figure~\ref{fig:winter.alg}, and
	a brief description of the terms used is provided in
	Figure~\ref{fig:winter.def}.

	This algorithm was a turning point in the calculation of
	SMT's.  It has since served as the basis for every algorithm
	for calculating SMT's and is the foundation for the parallel
	algorithm we present next.

		\begin{figure}[h]
		\vspace*{22pt}
		\input{chap04/winter.step1}
		\caption{\label{fig:winter.step1} Step 1 of Winter's algorithm.}
		\vspace*{22pt}
		\end{figure}

		\begin{figure}
		\vspace*{22pt}
		\input{chap04/winter.alg}
		\caption{\label{fig:winter.alg} Steps 2 through 7 of Winter's algorithm.}
		\vspace*{22pt}
		\end{figure}

		\begin{figure}
		\vspace*{22pt}
		\input{chap04/winter.def}
		\caption{\label{fig:winter.def} Definitions for terms in 
			Winter's algorithm.}
		\vspace*{22pt}
		\end{figure}

%\vspace*{11pt}
\section{A Parallel Algorithm}

	\vspace*{11pt}
	\subsection{Overview and Proper Structure} 
	
	When attempting to construct a parallel algorithm for a problem
	the sequential code for that problem is often the starting
	point.  In examining sequential code, major levels of
	parallelism may become self-evident.  Therefore for this
	problem the first thing to do is to look at Winter's algorithm
	and convert it into  structured code without
	\verb+goto+s.  This translation of the Initialization
	(Step 1 of Winter's Algorithm) appears in
	Figure~\ref{fig:seq_initialization} and the rest (steps 2
	through 7) appears in Figure~\ref{fig:main_loop}.

	\begin{figure}[h]
	\vspace*{22pt}
	\input{chap04/seq.alg.step1}
	\caption{\label{fig:seq_initialization} Initialization code.}
	\vspace*{22pt}
	\end{figure}

	\begin{figure}
	%\vspace*{22pt}
	\input{chap04/seq.alg.rest}
	\caption{\label{fig:main_loop} The main loop properly structured.}
	%\vspace*{22pt}
	\end{figure}

	Notice that the code in Figure~\ref{fig:main_loop} lies within
	a \verb+for+ loop.  In a first attempt to parallelize anything
	you typically look at loops that can be split across multiple
	processors.  Unfortunately, upon further inspection, the loop
	continues while \verb+p<q+ and, in the large if statement in
	the body of the loop, is the statement \verb=q++=.  This means
	that the number of iterations is data dependent and is not
	fixed at the outset.  This loop cannot be easily parallelized.

	\vspace*{11pt}
	\subsection{Mating of Vertices}
	
	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()+,
	which is shown in Figure~\ref{fig: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()+ previously described.  This boolean function, which
	determines if node $a$ (left) can mate with node $b$ (right) is
	given in Figure~\ref{fig:mate}.

		\begin{figure}[h]
		\vspace*{22pt}
		\input{chap04/a_before_b.c}
		\caption{\label{fig:a_before_b} Function a\_before\_b().}
		\vspace*{22pt}
		\end{figure}

		\begin{figure}
		\vspace*{22pt}
		\input{chap04/mate.c}
		\caption{\label{fig:mate} Function mate().}
		\vspace*{22pt}
		\end{figure}

\newpage
	%\vspace*{11pt}
	\subsection{First Approach}

	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 description from the slave's perspective is quite simple.
	A process is spawned off for each member of Q\_list that is a
	proper left subtree (Winter's algorithm allows members of
	Q\_list that are not proper left subtrees).  Each new process
	is then given all the current nodes on Q\_list.  With this
	information the slave then can determine, using the mate
	function previously described, with which nodes its left
	subtree could mate.  This mating creates new nodes that are
	sent back to the master, assigned a number and added to the
	master's Q\_list.  The slave also attempts to create an FST out
	of the new Q\_list member, and if it is successful, this FST is
	sent to the master to be added to the T\_list.  When a process
	runs out of Q\_list nodes to check it sends a request for more
	nodes to the master.

	The master also has a simple job description.  It has to
	start a process for each initial member of the Q\_list, send
	them all the current members of the Q\_list and wait for their
	messages.  Those messages will be in one of three categories:
	(i) Out\_of\_Data, (ii) New\_Node and (iii) New\_Tree.

	The Out\_of\_data message
	will signal the master that a slave has processed all the
	members of Q\_list it was given and is waiting for additional
	members.  If there are no more nodes to process, this slave can
	be idled.  If all the slaves working on Q\_list nodes of the
	same height are idle then the master will tell them all to
	terminate.  The process terminates if all levels are shut
	down.

	The New\_Node message will
	include the information necessary to add a new node to the
	Q\_list.  At this point the master will also have to spawn off
	a slave and start it up with this new node as its left
	subtree.  If there are any idle slaves that can mate with this
	node the master will send them this new node to process.

	The New\_Tree message will
	be accompanied by a tree which is to be placed on T\_list.
	These are kept and used in the extraction process described in
	the next chapter.

	This structure worked quite well for smaller problems (up to
	about 15 points), but for larger problems it reached a grinding
	halt quite rapidly.  This was due to various reasons such as
	the fact that for each slave started the entire Q\_list had to
	be sent.  This excessive message passing quickly bogged down
	the network.  Secondly in their work on 100 point problems
	Cockayne and Hewgill~\cite{ch92:icopsmt} made the comment that
	T\_list has an average length of 220, but made no comment about
	the size of Q\_list, which is the number of slaves that would
	be started.  From our work on 100 point problems this number
	easily exceeds $1,000$ which means that over $1,000$ processes
	are starting, each being sent the current Q\_list.  From these
	few problems, it is quite easy to see that some major changes
	needed to be made in order to facilitate the calculation of
	SMT's for large problems.

	\vspace*{11pt}
	\subsection{Current Approach}

	The idea for a modification to this approach 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 i
	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.

	In order to complete the implementation a few pointers are
	also maintained.  The first, called next\_proc\_to\_start, is
	kept at the earliest member of the Proc\_list that has not
	started.  The next, called earliest\_proc\_alive, is placed on
	the earliest member of the Proc\_list that is currently
	running.  

	Execution using this version is quite simple and fairly
	similar to the previous version.  The same messages previously
	described are used in this version.

	The first message is Out\_of\_data.  If a node sends a message
	to the master requesting more data, and there is nothing that
	it could mate with, it is idled, but if it had been the
	earliest\_proc\_alive, its node on the Proc\_list is finished,
	and is removed from the Proc\_list. The slave associated with
	that node would be told to change to the node pointed to by
	next\_proc\_to\_start which is then updated.  That slave is
	then sent any members of the Q\_list that it had not received.
	If the slave is told to change to a new node, the
	earliest\_proc\_alive pointer would need to be updated.  This
	pointer is walked up the Proc\_list, and if it meets a node
	that is idle, that process is terminated and the slave it was
	associated with would be told to change to the
	next\_proc\_to\_start node.  This walk would continue until the
	pointer meets a node that is currently running.
\newpage

	The second message is New\_Node. This type of message will
	still include the information necessary to add a new node to
	the Q\_list, but, as noted before, it will also cause a new
	node to be added to the Proc\_list.  If there are any idle
	slaves that could mate with this node the master sends them all
	the members of Q\_list they have not yet received.

	The third message is New\_Tree. This type of message is handled
	in the same way it is in the previous version.

	The only change made to the slave would  be the addition of a
	Change\_Node message, which could come back to it after it
	requested more data.  Implementation of this is quite trivial.
	The results for this approach are quite exciting, and the
	timings are discussed in Chapter VI.

