\section{The Auction algorithm} \label{auction} \subsection{Description of the Auction algorithm} \label{auction_desc} We refer the reader to \cite{be91} for an excellent tutorial. We provide a brief description of the algorithm. We start with a weight matrix $w$ where $w(i, j)$ is the cost of assigning person $i$ to object $j$. Initially, all persons are unassigned. Each object, $j$, has a price, $price(j)$, initially 0. The Auction algorithm proceeds in ``rounds'' or ``bids''. In a bid, an unassigned person bids for the object, $j_i$ with maximal value $m_i$ where $m_i = max_j \{w(i, j) - price(j) \}$. It also computes the second best object value, $nm_i = max_{j, j \neq j_i} \{ w(i, j) - price(j) \} $. It then raises the price of $j_i$ by $m_i - {nm}_i + \epsilon$, unassigns any person assigned to that object and assigns itself to that object. This process is repeated until all objects have received at least one bid. If $\epsilon < \frac{1}{n}$ and $w(i, j)$ are integers, then the assignment obtained upon termination is optimal. We use $\epsilon$-scaling in our implementations, which reduces the number of bids. $\epsilon$-scaling consists of repeating the algorithm several times, starting with a large value of $\epsilon$ and progressively decreasing it until it is less than $\frac{1}{n}$ for integer costs. Also, for a given $\epsilon$, rather than wait for all objects to be matched before we reduce $\epsilon$, we set a threshold. Once the number of unmatched objects falls below this threshold, we move to the next $\epsilon$ value. The threshold is gradually reduced until it becomes 1 when $\epsilon$ is 1. %%% Describe $\epsilon$-scaling a little more. \paragraph{Combined Forward-Reverse Auction.} \cite{bct91} proposed a variation on the Auction algorithm called Reverse Auction, where, roughly, {\em objects} compete for persons by lowering their price to a level that is sufficiently low to lure a person away from his currently held object. They showed that a judicious combination of Forward and Reverse Auction solved problems faster than either one alone could. We decided against this variation despite its claimed superior performance \cite{ca91} for a simple reason: memory accesses. The weight matrix is stored as columns (FORTRAN) or as rows (C or Pascal). The Forward-Reverse Auction accesses the matrix row-wise as well as column-wise. Given that most memory systems favour block transfers, it seemed unwise to access columns of a matrix that had been stored row-wise, especially if the matrix is so large that it needs to be paged in from disk. \paragraph{Gauss-Seidel vs. Jacobi.} The variation of the Auction algorithm when only one person bids at a time, is called the {\em Gauss-Seidel} implementation. If all unassigned persons bid at the same time, we get the {\em Jacobi} implementation. Both yield correct results. The Jacobi implementation is more parallel but requires more bids for termination. The decision to use the Gauss-Seidel variation of the Auction algorithm rather than the Jacobi variation was based on the following. (i) A reasonably high proportion of the total number of bids required by the Auction algorithm is spent with very few unmatched objects as shown in Table~\ref{many_bids_for_few} and as discussed in \cite{weze91,beca89}, and (ii) the Jacobi variation requires more bids than the Gauss-Seidel \cite{weze91,beca89}. Further, we suspect that as the problem size grows, the fraction of bids with very few unmatched persons increases. \begin{table} \begin{center} \begin{tabular}{|c|c|c|} \hline \hline {\em Problem size } & {\em Fraction of bids } & {\em Number unassigned} \\ \hline 2048 & 34.1\% & $\leq 32$ \\ \hline 2048 & 25.4\% & $\leq 16$ \\ \hline 2048 & 16.3\% & $\leq 8$ \\ \hline 2048 & 11.7\% & $\leq 4$ \\ \hline 2048 & 7.7\% & $\leq 2$ \\ \hline 2048 & 4.9\% & $\leq 1$ \\ \hline \hline 4096 & 31.6\% & $\leq 32$ \\ \hline 4096 & 23.4\% & $\leq 16$ \\ \hline 4096 & 16.5\% & $\leq 8$ \\ \hline 4096 & 12.4\% & $\leq 4$ \\ \hline 4096 & 9.6\% & $\leq 2$ \\ \hline 4096 & 6.7\% & $\leq 1$ \\ \hline \hline \end{tabular} \end{center} \caption{Fraction of bids with a given number of unassigned persons} \label{many_bids_for_few} \end{table} \subsection{Characteristics of the Auction algorithm} \label{auction_charac} \begin{enumerate} \item Processor-to-memory bandwidth. The weight matrix grows as $O(n^2)$. Therefore, memory requirements and processor-to-memory bandwidth are of concern. \item The heart of the problem. The essential computational problem is finding the maximum of $n$ numbers. \item Locality of reference. The Auction algorithm does not exhibit any regularity of access patterns across bids. In other words, while the number of unmatched persons decreases rapidly, the identity of the persons in the small set of unmatched persons fluctuates rapidly and without any regularity. \item Regularity of access patterns within a bid. The data necessary to calculate a bid are in contiguous memory locations. \item Computation to communication ratio. The amount of computation done per datum read is extremely small, consisting of a few integer arithmetic operations and comparisons. \end{enumerate} We analyze these considerations in the context of a variety of architectures. We present our strategy, rationale for that strategy, performance results, lessons learnt, and what architectural features are important. \subsection{SIMD Implementation} \label{simd} The Auction algorithm was implemented on an 8K MasPar MP-1208 and a 16K Wavetracer DTC-04032. The processor-to-local-memory bandwidth\footnote{ The processor-to-local-memory bandwidth is the product of the rate at which a processor can access its local memory and the number of processors. } is $2.2$ Mbytes/sec on the Wavetracer and $1.64$ Mbytes/sec on the MasPar. This figure is arrived at as $\frac{p \times 4 }{t_{read}}$, where $t_{read} = $ the time to read a 4-Byte integer from memory, $p =$ number of processors. This bandwidth is sustainable until the problem becomes too large to fit into the memory of the processors, which is 16K processors $\times$ 32 Kbytes = $\frac{1}{2}$ Gbytes for the Wavetracer and 8K processors $\times$ 16 Kbytes = 128 Mbytes for the MasPar. Note that these machines do not perform block transfers. This did not affect our results because blocks transfers can help only when $n$ exceeded $p$ and memory limitations kept us from such large problems. While the processors have registers, they have no automatic cache mechanism. This is not a drawback for the Auction algorithm which displays no locality of reference across bids. The SIMD machine was configured as a 1-D array. The $j$th processor was assigned the $j$th column of the weight matrix, $w[1..n][j]$, $price[j]$, $s[j]$ and $t[i]$ where $s[j]$ is the $s$-vertex to which $j$ is matched and $t[i]$ is the $t$-vertex to which $i$ is matched. The built-in function to compute the maximum was used. A small part of each bid - determining which object had to be assigned to which person, unassigning objects and updating the price - was performed on the front end. A large part of the problem consists of performing a global maximum, for which a built-in function is provided. \paragraph{Results and Discussion} Our results are shown in Table~\ref{auction_simd_results}. \begin{table} \begin{center} \begin{tabular}{|r|r|r|r|r|r|} \hline \hline - & - & \multicolumn{2}{c|}{\em MasPar (time in sec)} & \multicolumn{2}{c|}{\em WaveTracer (time in sec)} \\ \hline {\em Size} & {\em Cost} & {\em Unscaled} & {\em Scaled} & {\em Unscaled} & {\em Scaled} \\ \hline $128 \times 128$ & 100000 & 0.95 & 1.24 & 25.1 & 24.27 \\ \hline $256 \times 256$ & 100000 & 2.85 & 2.50 & 74.7 & 55.29 \\ \hline $512 \times 512$ & 100000 & 7.65 & 4.62 & 198 & 117.99 \\ \hline $1024 \times 1024$ & 100000 & 19.6 & 9.94 & 565 & 277.11 \\ \hline $2048 \times 2048$ & 100000 & 48.3 & 20.43& 1342 & 603.64 \\ \hline $3072 \times 3072$ & 100000 & 71.8 & 32.53& 2043 & 980.81 \\ \hline $3800 \times 3800$ & 100000 & 82.1 & 40.69& 2373 &1237.43 \\ \hline \hline $128 \times 128$ & 10000000 & 0.83 & 1.30 & 23.5 & 27.33 \\ \hline $256 \times 256$ & 10000000 & 2.34 & 2.51 & 61.4 & 57.84 \\ \hline $512 \times 512$ & 10000000 & 6.98 & 5.04 & 189 & 131.67 \\ \hline $1024 \times 1024$ & 10000000 & 20.1 & 10.28& 575 & 290.32 \\ \hline $2048 \times 2048$ & 10000000 & 75.5 & 21.76& 2050 & 646.96 \\ \hline $3072 \times 3072$ & 10000000 & 752 & 34.29& 13027 & 1040.07\\ \hline $3800 \times 3800$ & 10000000 & 531 & 47.70& 9074 & 1463.69\\ \hline \hline $128 \times 128$ & $i \times j$ & 118.81& 2.47 & 3711.59 & 53.3 \\ \hline $256 \times 256$ & $i \times j$ & 906.12& 9.57 & 29898.51 & 275 \\ \hline $512 \times 512$ & $i \times j$ & 10151.93& 30.9 & 241913.29 & 931 \\ \hline $1024 \times 1024$ & $i \times j$ & -- & 131 & - & 4008 \\ \hline $2048 \times 2048$ & $i \times j$ & -- & 313 & - & 9707 \\ \hline $3072 \times 3072$ & $i \times j$ & -- & 689 & - & 21629 \\ \hline $3800 \times 3800$ & $i \times j$ & -- & 1463 & - & 44831 \\ \hline \hline $128 \times 128$ & $i \times j \times 100$ & 115.91 & 2.46 & 3771.35 & 59.3 \\ \hline $256 \times 256$ & $i \times j \times 100$ & 919.56 & 9.58 & 30450.25 & 286 \\ \hline $512 \times 512$ & $i \times j \times 100$ & -- & 29.5 & - & 910 \\ \hline $1024 \times 1024$ & $i \times j \times 100$ & -- & 129 & - & 4041 \\ \hline $2048 \times 2048$ & $i \times j \times 100$ & -- & 279 & - & 8938 \\ \hline $3072 \times 3072$ & $i \times j \times 100$ & -- & 588 & - & 18907 \\ \hline $3800 \times 3800$ & $i \times j \times 100$ & -- & 797 & - & 25867 \\ \hline \hline \end{tabular} \end{center} \caption{Results on SIMD Machines} \label{auction_simd_results} \end{table} We learned the following lessons: \begin{enumerate} \item The frustration of bit-serial computers. The often touted advantage of bit-serial computers does not translate into any advantage in practice. In commercially available bit-serial machines, the cycle-count for operations is a very poor indicator of actual computation time. We had recognized and solved this problem several years ago in our prototype, the AP2S \cite{rjn90} with a Distributed Macro Controller. However, such a controller remains unavailable in commercial machines. % For example, consider a 4-byte addition, $a \leftarrow b + c$, performed $n$ times in a loop or simply replicated $n$ times. One would not expect a difference in the time taken by these two dummy programs. On the contrary, there is a significant difference. This slowness is due to the controller bottle-neck. To understand this, let us explain how, for example, the Wavetracer works. On the Wavetracer, a program compiled by multiC runs on the host which sends appropriate commands to the 16 MHz command controller via a SCSI bus. The controller generates array processor microcode instructions and sends it to the sequencer. Then the sequencer executes these instructions on the array processors. Once the instructions are executed, the sequencer waits for the controller to generate the next set of microcodes. The controller waits for the host to generate the next command. The time taken for these operations is substantial. The array processor is poorly utilized unless it is executing a long operation (eg., floating-point multiplcation) such that the computation time subsumes the time for the decoding and broadcast process. Table~\ref{wave_perform} shows the disparity between the loop time and the sequential time. The disparity decreases as the operations become more complex. MasPar has a similar problem as Table~\ref{simd_myth_bit_serial} indicates. \begin{table} \begin{center} \begin{tabular}{|c|c|c|} \hline \hline {\em Operation } & {\em Loop Time } & {\em Repeated Time} \\ \hline Off-chip Memory to On-chip Memory & 1.38 & 4.96 \\ \hline Off-chip Memory to Off-chip Memory & 0.54 & 1.45 \\ \hline On-chip Memory to On-chip Memory & 2.25 & 8.28 \\ \hline 32-bit addition & 6.33 & 12.45 \\ \hline \hline \end{tabular} \end{center} \caption{Time to perform specified operation on the Wavetracer (in $\mu$sec)} \label{wave_perform} \end{table} \begin{table} \begin{center} \begin{tabular}{|c|c|c|} \hline \hline {\em Operation } & {\em Loop Time } & {\em Repeated Time} \\ \hline Memory-to-register & 6.42 & 20000 \\ \hline Memory-to-memory & 12.12 & 40000 \\ \hline Register-to-register & 3.61 & 10000 \\ \hline 32-bit addition & 20.0 & 240 \\ \hline \hline \end{tabular} \end{center} \caption{Time to perform specified operation on the MasPar (in $\mu$sec)} \label{simd_myth_bit_serial} \end{table} Another slowdown arises as follows. The flow of information from the host to the array processors is pipelined. Whenever this pipe is broken, a delay is incurred. Consider the code segments in Figure~\ref{pipeline} to find the most desired object i.e., the processor with the highest $v$ value. Variables $maxi$ and $j$ are resident on the host while $v$, $w$, $processor\_id$ and $p$ are resident on the array processors. The code on the left is about 1.25 times slower than the code to the right. This is because in assigning the maximum to $maxi$, a variable resident on the host, we are forcing the host to wait for the value of $maxi$ and hence are breaking the instruction pipeline. \begin{figure}[hbt] \begin{center} {\bf code for finding $j$: object with maximum $v = w[i] - p$} \end{center} \begin{tabbing} \hspace*{.25in} \= \hspace*{3.50in} \= \kill $ v \leftarrow w[i] - p$ \> \> $ v \leftarrow w[i] - p$ \\ % $maxi = >?= v$ \{ $= >?=$ is the max-finding operator \} \\ % {\bf if} $maxi == v$ {\bf then} \> \> {\bf if} $v == (>?= v)$ {\bf then} \\ % \> $j = $j = \> {\bf endif} \\ \end{tabbing} \caption{Effect of breaking pipeline in SIMD machines} \label{pipeline} \end{figure} \item The ability to compute an associative function. The time take to perform a 4-Byte global maximum on the MasPar is 0.51 msec and 0.34 msec from memory and register (benchmark using MPL compiler) respectively and Wavetracer is 2.9 msec (multiC compiler), instead of 326 cycles or 32.6 $\mu$sec on the AP2S which utilized the Global-OR feature of the GAPP. Global-OR of a 4-Byte word on the MasPar takes 0.1 msec and 0.07 msec from memory and register respectively, and 2.9 msec on Wavetracer. The global maximum operation finds the maximum price and the next maximum price per person, and Global-OR is used to locate the found maximum price. The average time per bid for $n = 2048$ was 2.5 msec on the SPARCstation-2, 1.241 msec on the MasPar and 9 msec on the Wavetracer. The times for the MasPar and Wavetracer would remain constant until $n > p$, after which virtualization would introduce an overhead. For $n = 2048$, we achieved a speedup of 2 on the MasPar slow down of 6 on the Wavetracer, compared to the SPARCstation 2. \item The imbalance between communication and computation. While the work of \cite{weze91} is noteworthy, we feel that the Auction algorithm is mismatched on an SIMD architecture. It is interesting to note \cite{weze91}'s conclusion that ``we have yet, however, to produce CM techniques for this problem that are significantly better than smaller scale MIMD (Multiple-Instruction Multiple-Data) machines.'' For example, the MasPar can perform 400 million integer additions per second. However, it can read only about 0.4 million integers per second from memory. The Auction algorithm makes a strong case for an MIMD machine like the CM-5 or Intel Delta, {\em provided that they provide low latency communications}. One of the guiding principles in the design philosophy of the CM-5 was to leverage the technology advancements in the ``killer-micros''. The Auction algorithm uses relatively simple instructions and has the structure necessary which makes it amenable to techniques like pipelining, block transfers and hence, an ideal candidate for powerful RISC-based processors. The performance of Auction on a single processor degrades only when we have to go out to disk repeatedly. The processor-to-local-memory bandwidth shortfall could be redressed by having many processors, each with their own communication route to memory. Since the weight matrix, which is responsible for the bandwidth shortfall, is immutable, this suggests that there is a rationale for designing of read-only memory which permits simultaneous reads and does not serialize concurrent accesses as a typical memory interface does. \item For memory intensive problems such as Auction, the time to load the data often substantial (Table~\ref{simd_read_data}). \begin{table}[hbt] \begin{center} \begin{tabular}{|c|c|} \hline \hline {\em Problem size} & {\em Time to transfer (in sec) } \\ \hline $512 \times 512$ & .072 \\ \hline $1024 \times 1024$ & 17 \\ \hline $2048 \times 2048$ & 80 \\ \hline $3072 \times 3072$ & 148 \\ \hline \hline \end{tabular} \end{center} \caption{Time to transfer data from a binaty file on the DEC workstation- host into the memory of MasPar array processors.} \label{simd_read_data} \end{table} \end{enumerate} \subsection{Shared Memory Implementation} \label{shmem} We implemented the algorithm on a 4-processor workstation- from Silicon Graphics, the IRIS 4D/340 DVX, chosen because it was representative of shared memory systems (and because it was the only machine on which we could hog vast amounts of CPU and memory without risking the ire of other users!). It has four 33 MHz R3000 RISC based processors from MIPS with 48 Mbytes of ECC memory and 2 Gbytes of disk. It has a primary cache of 64 Kbytes which is connected to the processor via a Processor Bus, which can transfer data at 8 bytes every clock cycle. An MPLink bus connects processors to memory. A second level data cache, 256 Kbytes in size, serves as a buffer between the first level cache and the MPlink bus. It provides block transfer capability for the MPlink Bus. The MPlink bus has 32 address lines and 64 data lines. An MPlink Bus transaction is six cycles in length, although the last two data transfer cycles can overlap with the first two cycles of the next transaction, resulting in a sustainable data transfer rate of 64 Mbytes/sec. This is substantially higher than the 2-4 Mbytes/sec on the SIMD machines. However, it drops to 2 Mbytes/sec when we have to go to disk through the SCSI. % (This figure is arrived at as follows. 64 bits per transaction = 8 bytes % per transaction = 2 bytes per cycle = 64 bytes per $\mu$sec (at 32 MHz) % = 64 Mbytes/sec) In order to reduce the memory traffic, the columns of the weight matrix were partitioned among the processors. A single processor was designated as the master processor. It was responsible for deciding which person would bid and also for coalescing the partial results of the other processors. Since this required a simple read from shared memory, the latency for the flow of information was negligible. Had there been more processors, the work of coalescing bids would have been distributed among the processors. We had essentially a producer-consumer relationship between the master processor and the rest of the processors. We chose not to incur the overhead of using system calls for the synchronization. Instead we used the following tagged scheme and busy-waiting (justified by the fact that we were running in single user mode and that the workload was evenly balanced, thereby making the waiting time minimal). Assume that the master decides that the bid for person $i$ must be calculated. Let this be the $b$th bid. It writes $i$ into $which\_person$ and $b$ into $tag\_which\_person$, both of which are shared locations. A slave processor knows which bid is to be calculated. It first reads $tag\_which\_person$. If this value is less than $b$, it abandons the data as premature. Note that it could not be greater than $b$. If it is equal to $b$, it starts calculating its portion of the bid for $i$. When it is done, it writes its partial results to a shared region and then writes the tag of $b$. The protocol of reading in the opposite order of writing to obtain consistent values was first suggested by Lamport \cite{la77}. The ability to predict the tags of the values makes this a ``knowledgeable'' algorithm, as defined in \cite{su192}. Lack of space prevents a formal proof that this protocol is correct. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \paragraph{Results and Discussion.} The machine was used essentially as a distributed memory machine with no dynamic reallocation of work. The shared memory was used to provide a low-latency inter-processor communication mechanism. While a single slow processor could degrade the entire performance, this was not observed because of even load balancing. Contrary to what was expected, the MPlink bus was not a bottleneck. The bottleneck was the SCSI which connects main memory to disk, which came into play when the problem size was too large for the weight matrix to fit in main memory. Figure~\ref{fluctuate} shows how the average time per bid fluctuates when $n = 4096$ and the weight matrix could not fit in main memory. Note how the change in $\epsilon$ causes an increase in the average time per bid. This is because when $\epsilon$ changes, all objects become unmatched. The average time per bid was $0.63$ msec for $n = 2048$ and $0.31$ msec for $n = 1024$. For $n \leq 2048$, the problem was resident in main memory and the time per bid was very uniform. Table~\ref{fig_shmem_results} shows the results for the shared memory implementation. \input{figure5.tex} \begin{table}[hbt] \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline \hline {\em Problem size} & Number of bids & Average time & Total time & Range of \\ - & - & per bid (msec) & (seconds) & random numbers \\ \hline \hline $1024 \times 1024$ & 30464 & 0.31 & 9.44 & 100000 \\ \hline $2048 \times 2048$ & 66360 & 0.63 & 41.82 & 100000 \\ \hline $4096 \times 4096$ & 131151 & 55.64 & 7297.8 & 100000 \\ \hline \hline \end{tabular} \end{center} \caption{Performance results on shared memory system} \label{fig_shmem_results} \end{table} \paragraph{A Note on Asynchronous Implementations} We chose not to use asynchronous variations of the Auction algorithm despite the \cite{beca89} claim that ``better asynchronous implementations outperform substantially the corresponding synchronous implementations on a shared memory machine.'' Asynchrony does not buy one anything. On the contrary, synchrony can cost one {\em when maintaining synchrony is expensive.} We found that maintaining synchrony did not induce a performance penalty. It must be stated that the minimal overhead suffered to maintain synchrony is because of the relatively few numbers of processors used and the uniformity of the load distribution. % {\em Do we get super-linear speedup ? } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Distributed Implementation} \label{dist} Parallel Virtual Machine (PVM), a public-domain software package developed at Oak Ridge National Laboratories was used to implement a distributed solution \cite{sun91}. We believed the Auction algorithm to be amenable to a distributed solution for the following reasons: \begin{enumerate} \item One of the characteristics that makes a problem amenable to a distributed solution is that the problem descriptor should be small, the computing to be done should be large and the description of the solution should be small. This is in order that the communication costs can be subsumed by the computing time. One processor was designated as the master. The problem descriptor, the identity of the person bidding, was small. Broadcasting this information to 7 processors required roughly 1.5 msec. This is roughly the time taken by a SPARCstation-2 processor (running at 40 MHz and 28.5 MIPS) to perform one bid for $n = 1024$. Therefore, if $n = c p \times 1024$, then the overhead of the broadcast would be $\frac{1}{c}$. Broadcasting is implemented in PVM using point-to-point messages with recursive doubling. Broadcast proceeds in ``rounds'', with the number of processors contributing to the broadcast effort doubling in each round. In round $r$, processor $k$ transmits to processor $(k + 2^r)~{\rm mod}~p$ and receives no acknowledgement. A processor $k$ joins the broadcast effort at round $r_k$, where $r_k =$ number of 1's in the binary representation of $k~{\rm mod}~p$. In the implementations of PVM, the UDP protocol was used \cite{po80}. Therefore, the size (in bytes) of the data message, or datagram, exhanged is computed as follows: size = Ethernet header + IP header + UDP header + data + Ethernet trailer = 14 + 20 + 8 + data + 4 = 46 + data. Hence, to broadcast 8 bytes of data, 54 bytes of data are sent. With a 10 Mbits/sec Ethernet, this should take 41 $\mu$sec ideally. \item The data could be partitioned easily by simply giving each processor some of the columns of the weight matrix. The weight matrix does not change during the course of the computation. The information to be updated in each bid, the price of the object for which a bid was submitted (if at all), is small. A further optimization was to combine this with the broadcast of the identity of the bidder. Since the cost of the broadcast is virtually unaffected by this additional information, this update introduced no additional overhead. \item One of the often ignored but important factors that slow down distributed computations is load imbalance \cite{sun92}. There are two sources of load imbalance. One arises from the workload of other users on the different machines being used. This was not relevant to us, since we had the machines to ourselves. The second arises from computational imbalance. By partitioning the work in proportion to processor speeds, it was hoped that this imbalance could be redressed. \item Since each processor had its own access to memory, we hoped to redress the processor-to-memory bandwidth. \end{enumerate} \paragraph{Results and Discussion} The Auction algorithm was implemented on 15 SPARCstation-2 processors connected on a 10 Mbits/sec Ethernet. We found that while there was no flaw in the rationale mentioned above, the performance was little short of disastrous. Why was this so? The bottleneck was the ``accumulate'' or ``gather'' routine. In a bid, each processor, $k$, operates on the columns assigned to it. It calculates ${m}^k$, ${{nm}}^k$, ${price[j]}^k$, which are the values $m$, ${nm}$ and $price[j]$ would have had had the columns assigned to $k$ been all the columns of the weight matrix. Given these partial results, we needed to compute $m$, $nm$, $price[j]$ and $k'$, the identity of the processor which has the object with the highest value (i.e., $price[j] = {price[j]}^{k'}$). Since the partial results of each processor could be coalesced using a binary tree (as is done in the broadcast), we felt that this should not take significantly longer than the broadcast time. Note that it would be overly optimistic to expect the same time as the broadcast since the broadcast consists of non-blocking sends whereas the accumulate involves both sends, receives and some small local computation. The rapid degradation in performance that the accumulate caused was unexpected. Two approaches to performing the accumulate were tried: (i) Serial: All processors send their partial information to the processor designated as master, and (ii) Recursive doubling: The processors are laid out as the nodes of a binary tree and a node sends its partial information is sent to the parent. The performance results are presented in Table~\ref{dist_gather_results}. \begin{table}[hbt] \begin{center} \begin{tabular}{|c|c|c|c|} \hline \hline {\em Number of Processors} & {\em Serial } & {\em Recursive doubling } & {\em Broadcast time} \\ - & {\em Accumulate} & {\em Accumulate} & - \\ \hline 7 & 20.2 & 18.3 & 1.42 \\ \hline 15 & 41.91 & 30.9 & 1.46 \\ \hline \hline \end{tabular} \end{center} \caption{Time (in msec) to accumulate partial results.} \label{dist_gather_results} \end{table} We came to two conclusions: \begin{enumerate} \item Given current hardware and software technology, the overhead associated with transmissions makes it impractical to run applications which require small (of the order of a few msecs) latency. This raises the following possibility to decrease latency. Any information broadcast on an Ethernet is received by all processors. Each message has the id of the receiving processor and a processor simply ignores a message that does not belong to it. This suggests designating an id for the Parallel Virtual Machine (PVM) and have a processor read all messages that had either its id or the PVM id. \item Given that the memory is distributed, slow response from even one processor would degrade the entire system performance. There is simply no way to dynamically reassign work. This makes this approach increasingly treacherous as the number of processors is increased, unless one is in a position to guarantee the workload on {\em all} the participating processors. Note that the same criticism holds for an MIMD implementation (as on a CM-5 or Intel Delta). This does not hold true for a true shared memory system, where work can be dynamically re-allocated. Of course, reallocating work means re-distributing the data and it is not sure whether the necessary bandwidth would be available especially since the Auction algorithm is communication intensive i.e., the work done on each datum read is very small, thereby making it difficult to recover the cost of the communication. \end{enumerate}