\section{Definitions and Models}
\label{defns}

\subsection{The Assignment Problem}
\label{assign_prob}
The Assignment problem we consider is as follows:  
Let $n$ be a positive integer, and let $|n|$ be $\{0, 1, \ldots, n-1\}$.
Let $w:  |n|^2 \Rightarrow Z$ be a matrix with finite precision entries.  
Find a permutation $\pi :  |n| \Rightarrow |n|$ such that 
$\sum_i (w(i, \pi(i)))$ is a minimum.  

This problem is identical to the (weighted) bipartite graph 
matching problem defined as follows. 
$G = (V, E)$ is an undirected bipartite graph such that $V$ can be 
paritioned into two disjoint sets $S$ and $T$ and all edges have 
one endpoint in $S$ and the other in $T$.
Let the number of edges $|E| = m$ and the number of vertices 
$|S| = |T| = n$.  A matching, $M$, is a 
vertex-disjoint subset of edges of $E$.  
The maximum cardinality bipartite matching problem is to find a 
matching in $G$ of maximum size.  In weighted bipartite matching, 
a weight,  $w(i,j)$ is associated with each edge $(i,j)$, and the 
cost of a matching is the sum of the weights of its edges.  The goal is to 
find a maximum matching of minimum cost, and this is the 
same as the Assignment problem. The generalizations to 
(i) rectangular matrices, 
(ii) real numbers, and 
(iii) obtaining the maximum instead of the minimum 
are straight-forward and will not be considered further, since 
these are not directly relevant to the DIMACS challenge.

\subsection{The SIMD Computing Model}
\label{model}


The SIMD model consists of an 
array of identical processors (PEs) operating in lock-step synchrony.
In each cycle, they perform the same instruction on their own
data.  In one step, a processor can perform 
one instruction or send/receive one bit/nibble from a neighbouring
processor.  Typically, the PEs have 
a limited instruction set and a very small finite precision (typically 
1 to 4 bits).  Thus, the execution time of an operation is dependent 
upon the word length.  An $n \times n$ mesh-connected array contains 
$n^2$ processors positioned on an $n$-row, $n$-column square lattice.  
Each processor can communicate with its four nearest 
neighbours, except those on the border, which have only two or three 
neighbours.  (Our algorithms could also be implemented on a mesh with 
``wraparound'' connections, yielding a speedup of a small constant factor.)

The first commercially available chip embodying this architecture was 
the GAPP invented by W. Holsztynski \cite{ho86}.  Our early results 
on the Assignment problem were implemented on an internally 
constructed machine AP2S (Adaptive Parallel Processing System, 
see \cite{rjn90} ]) based on the GAPP chip.  The AP2S contains 
a two-dimensional (108 x 96) array of approximately 10,000 processing 
elements running at 10 MHz.  Each processing element contains only 128 
bits of local memory.  Our algorithms were constructed for an 
``enhanced'' SIMD model, in which the existence of row and 
column highways is assumed.  Specifically, a row-OR or 
column-OR is assumed to take only one cycle.  (This type of 
hardware enhancement is present in the AMT DAP machine for all the sizes 
manufactured, and we expect that our implementations for this 
model would also be efficient on the DAP \cite{re78}.  It 
is, however, clearly an assumption that cannot hold in the 
limit for very large $n$.)

The AP2S system has limitations which restricted its usefulness 
for further investigations for the DIMACS project.  Primarily, 
the limited local memory severely restricted the size of problem which 
was feasible.  
Thus, the remainder of our implementations (i.e. for larger arrays) 
were done on the commercial Wavetracer DTC machine (see \cite{ja90}) and
MasPar Machines (see \cite{bl90}, \cite{nic90}). 
In the Wavetracer DTC's largest configuration, there are 16K simple bit-serial 
processors with 2Kbits of on-chip memory and 32 Kbytes of off-chip
memory per PE, each running at 11 MHz.  
While the hardware 
interconnection lattice is three-dimensional, our implementations 
configured the machine to a two-dimensional array (and to a one-dimensional
array for the Auction algorithm).  The DTC does 
not contains row and column highways. However,
it does have a global bus that can perform the NAND of a bit from each
PE in one cycle. This can be used to compute a global maximum.

The 2-D PE array of MasPar consists of 4-bit ALU running at 14 MHz and 
each PE can communicate with its 8 nearest neighbours 
through XNET. A 3 stage crossbar switch is provided for global routing, and some
floating-point assisted hardware is also included at each PE.  
There are 192 bytes of on-chip register and 16 Kbytes of
fast off-chip memory per PE.  A global-OR (GOR) hardware is provided as 
well.  The above features impact the performance
on the Assignment problem in the following ways.  The 4-bit ALU takes a quater
of the cycle count as the bit-serial ALU array if the wordlength of operands is
a multiple of 4.  The global-OR hardware only gives an edge in global
maximum/minimum, but not on column/row maximum/minimum.  The software language
used (MPL, MasPar Parallel application Language \cite{ch90}) required the programmer to
develop the partition and virtualization if the data size was larger than
the array size.

It is important to note that some of our results have a 
computer hardware/software flavor rather than a purely mathematical 
one.  For example an early invention of ours called the
Distributed Macro Controller (DMC) \cite{hora88} allows, among other things, 
a run-time allocation of memory.  This significantly enhances 
the speed of execution of the algorithm as discussed in the 
next section.  We are also interested in the bit-level performance 
of these implementations, since massively parallel machines generally use 
bit/nibble serial processors.  Further, the bit complexity is 
an inherently important quantity in the cost scaling techniques 
such as in \cite{gpv88}.  The architectures we have chosen represent 
the simplest and least expensive massively parallel computing 
models (around \$10 per PE, total systems cost of a  hundred 
thousand dollars for about 8,000 processors in the Wavetracer).  They 
represent a different way to arrange about the same amount of 
hardware as a high-end workstation, as opposed to a multimillion 
dollar supercomputer.  Thus, we view our results as an evaluation of 
the amenability of Assignment problem to this alternate architecture, and 
believe a comparison to sequential implementations on high-end 
workstations would be valid and interesting.