\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.