\section{Conclusions}
\label{end}

Three algorithms have been designed on simple bit-level SIMD machines.  
A simple parallel algorithm for the Assignment problem, with 
theoretically sub-optimal speed, has been shown to be surprisingly 
fast in practice.  Theoretically superior in the worst case, our 
cost scaling algorithm has difficulty keeping pace on average 
case data.  This is because for randomly selected finite precision 
data, there are potentially many optima, and a simple algorithm 
(which may require many passes in the worst case) 
tends to converge to one of them rather quickly.  Lacking, however, 
from the classes of input data are ``real-world'' data taken 
from practical problems, which are often decidedly non-random.  
It would be interesting to analyze the performances for 
such inputs, if it could be obtained. 

We reached the following conclusions regarding the Auction algorithm.
Its extreme simplicity makes it amenable to easy coding as well
as keeps the constant factors, hidden in the big-$O$ notation, small.
The algorithm performs very little computation for each datum read.
The computation power of most machines significantly exceeds their
communication power (both processor-to-memory and processor-to-processor).
A significant fraction of the bids have very few objects unmatched, 
a situation which seems to worsen as the problem size increases.
Hence, we do not believe that it is amenable to ``massively'' 
parallel implementations as has hitherto been claimed. 
However, for reasonably small numbers of processors, it performs very well.

Our SIMD implementations squeezed the most out of the machine but
came up short against the following inherent limitations:
low memory-to-processor bandwidth, slow controller, breaks
in the host-to-array-processor pipeline. Our shared memory 
implementations showed perfect speedup. However, they also
showed that processor-to-memory bandwidth was the bottleneck
when the problem could not be fit into the main memory.
Our distributed implementations were an effort to redress the
processor-to-memory bandwidth by trying to fit the problem
into the main memory of many processors. While solving this problem,
we ran into unacceptably high processor-to-processor latency.

The algorithm on the GAPP was written in assembler code, while the 
current Wavetracer implementation was written in MultiC 
in a few days.  For reasonable comparisons we are concentrating on 
the machine cycles used by each of the parallel arrays.  However, 
the controller at the front end of the array has also proven 
to be a major issue.  In particular, the response times on the 
Wavetracer are much slower than the computation time.  This is 
almost entirely due to the fact that the controller is a 
bottleneck, and is unable to decode instructions for the parallel 
machine to keep pace with the speed of the processor.  This is in 
contrast to our controller, called the DMC and alluded to earlier, 
which could keep pace with the machine, and allowed subroutine calls, 
memory allocation, and reprogrammability all without any penalty 
in machine speed.  Such controllers have been demonstrated 
by this investigation to be essential to realize the performance 
promised by massively parallel processors.