\section{Munkres' Algorithm}
\label{munkres}

\subsection{The Munkres Modification of the ``Hungarian'' Solution}
\label{munkres_modify}

J. Munkres cited the following outline of Kuhn's algorithm for 
the Assignment problem:

\begin{enumerate}
\item 
Subtract the smallest element in $w$ from each element of $w$, 
obtaining a matrix $w'$ with non- negative elements, and at least one zero.

\item Find a minimal set $S'$ of ``lines'' (rows and columns) of $w'$, 
$n'$ in number, which contain all the zeroes of $w'$.  If $n' = n$, there 
is a set of $n$ independent zeroes of $w'$ and the elements of $w'$ 
in these $n$ positions are the desired solution.  (The positions of 
the zeroes are called independent if no two of them belong 
to the same row or column of the matrix).

\item If $n' < n$, let $h'$ denote the smallest element of $w'$ which 
is not in any line of $S'$.  Then $h' > 0$.  
For each line in $S'$, add $h'$ to each element of that line; then 
subtract $h'$ from each element of 
$w'$.  Call the new matrix $w''$.

\item Repeat Steps 2 and 3, using $w''$ in place of $w'$.

\end{enumerate}

Munkres improved upon Step 1, which though performed only once, 
has a prolonged impact upon subsequent steps.  However, 
his main contribution was in solving for Step 2.  Our 
parallelization of the Munkres steps involves what we might 
call both ``local'' as well as g``lobal'' parallelizations \cite{ho87,ra87}. 
By ``local'' we here mean faithfully following the sequential 
algorithm, and parallelizing the steps as far as possible.  However,
we also make some changes that allow a single parallel step to 
correspond to several simultaneous Munkres steps.  Each one of the 
latter, in turn, allows a ``local'' parallelization.  We do not 
intend to attach any geometric meaning to the terms ``local'' and ``global''
here; these refer only to the structure of the algorithm.  
The algorithm actually coded on the AP2S is described in 
detail in \cite{ho87}.  We now describe the performance on 
an ``enhanced'' AP2S simulation, which would be very similar 
in performance to that on a DAP \cite{re78}.

\subsection{Performance of the Parallel Munkres-style Algorithm}
\label{munkres_results}

Before displaying the results of our algorithm, 
we make a few remarks.  The sequential Munkres algorithm may require $O(n^3)$ 
time.  The performance of our parallelization can be shown in the worst 
case to be $O(n^2 \log n C)$ with $n^2$ bit-serial processors and 
weights with a magnitude $< C$, (so that $\log C$ 
is the number of bits needed to specify the weights, and $\log n$ bits 
are required to represent a processor's row or column number).  
Thus, the parallel work (processor-time product) is $n^4 \log n C$, 
which appears poor.  However, several points should be mentioned:

\begin{enumerate}
\item With random inputs, the running time is dictated by average-case 
results.  We have not analyzed this rigorously.  If 
the approximation that the weights remain random through the Munkres 
modifications is reasonable, then the average-case time bound may 
be shown to be $O(n \log n C)$.

\item Since the weights are decreasing with the repetition of the 
main steps of the algorithm, a machine that offers dynamic memory 
allocation, or deals with only as many bits as necessary at each step 
without overhead, offers an advantage.  Such is the case with the 
machine augmented with the DMC that we constructed. 
In this case the average running time is less than that indicated 
by 1.  above.

\item The constants hidden within the asymptotic bounds are quite 
small, especially for the enhanced GAPP model we are considering.  
This model allows the row-OR column-OR to occur in one cycle.

\end{enumerate}

We now justify the above assertions by displaying the results of 
the runs in Table~\ref{fig_1_munkres_results}.  
In all cases, we display the 
running time in terms of machine cycles.  The AP2S runs at 10 MHz, thus 
10,000 cycles = 1 msec.  The cycle count does not include any 
input-output time; further the cycle count assumes the ``enhanced'' 
GAPP model, in that a row-OR or column-OR is counted to take only 
one cycle.  The $x$-axis counts the number of nodes as specified 
by the DIMACS instructions.  Thus 64 nodes means that the matrix 
for the Assignment problem is $32 \times 32$, or in the language 
of graph matching there are 64 nodes divided into two sets of 32 
each.  Table~\ref{fig_1_munkres_results} shows the averaged cycle-count 
(constructed as specified by the DIMACS consortium) for 
(i) random 11-bit samples (obtained using ``assign.c'' in the DIMACS library),
(ii)  21-bit numbers (obtained using ``dcube.c'') and 
(iii) $i \times j \times 100$.  

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|} \hline \hline
{\em Size }	& {\em Cost } 	& {\em Time (in msec)} & {\em Instructions (in 1000s)} \\ \hline
16	&	1000	&   0.41  	&     4.14  \\ \hline
32	&	1000	&   1.03  	&    10.34  \\ \hline
64	&	1000	&   2.65  	&    26.45  \\ \hline
128	&	1000	&   6.56  	&    65.64  \\ \hline
256	&	1000	&   14.5  	&   145.35  \\ \hline
512	&	1000	&   34.1  	&   341.03  \\ \hline
1024	&	1000	&   75.1  	&   750.58  \\ \hline \hline
16	&    1000000	&   0.68  	&     6.78  \\ \hline
32	&    1000000	&   1.90  	&    19.05  \\ \hline
64	&    1000000	&   5.27  	&    52.69  \\ \hline
128	&    1000000	&   14.0  	&   139.6  \\ \hline
256	&    1000000	&   36.5  	&   365.1  \\ \hline
512	&    1000000	&   94.6  	&   946.2  \\ \hline
1024	&    1000000	&    239  	&  2386  \\ \hline \hline
16	& $i \times j \times 100$ & 3.20	&  31.97  \\ \hline
32	& $i \times j \times 100$ & 18.4	& 184.1   \\ \hline
64	& $i \times j \times 100$ & 110		& 1104    \\ \hline
\end{tabular}
\end{center}
\caption{Performance of Munkres' algorithm on AP2S}
\label{fig_1_munkres_results}
\end{table}

We feel that the times are surprisingly fast.  Even for the $256 \times 256$ 
matrix with all entries having 21-bits, the algorithm completes 
(with the caveats mentioned above) in less than 40 msec on the 
average, with a 10 MHz clock.  
(It should be pointed out that more modern chips or machines run at 
higher clock speeds).  For the 21-bit case, the times have dropped to 
about 16 msec.  We should note that our actual array size is 
approximately 100 x 100, so that most of the time would be spent in 
input and output for the larger sizes of problem, due to the very 
limited amount of local memory per processor.  As stated, this has not 
been included in the cycle count.  The small size of our array is also 
why we are not reporting larger sized problems.

