The CPU cycles that are stolen to relay messages can significantly affect the performance of a multicomputer system. This degradation in performance in turn affects the overall cost-effectiveness of such a system. This paper compares the cost-effectiveness of four multicomputer architectures that have received a great deal of recent attention: the bidirectional straight line, the unidirectional ring, the square mesh, and the binary hypercube. Cost-effectiveness is measured by finding the ratio of the total dollar cost of a multicomputer, based upon the total cost of processors and communication links, to the total potential utilization of the processors making up the system, where the potential utilization is the fraction of time a processor has to do useful processing after subtracting time spent handling messages. The smaller the value of this ratio, the greater the cost-effectiveness of the system.

In multicomputer architectures, in which processors communicate through message-passing, the overhead encountered because of the need to relay messages can significantly affect performance. Based upon some simplifying assumptions including the rate at which a processor generates messages being proportional to its current potential utilization, processor utilizations are analytically derived in matrix form for a bidirectional straight line and square mesh. In addition, closed form derivations are provided for a unidirectional ring and an n-dimensional hypercube. Finally, the theoretical results are found to be in close agreement with discrete-event simulations of the four architectures.