Processor potential utilization in very-large-scale, regular, static interconnection networks.
Richard G. Born · 1988
In multicomputer architectures in which processors communicate through message passing, the overhead encountered because of the need to relay messages can significantly affect performance. The concept of potential utilization, the fraction of time a processor has to do useful processing after subtracting time spent handling messages, is defined. Based upon a set of model assumptions including the assumption that message generation rate is constant for all processors and that uniform message routing is employed, processor potential utilizations are derived in closed form for a bidirectional straight line, a unidirectional ring, and n-dimensional binary hypercube, and a square mesh. It is also found that there is a critical value for the ratio of processing time for a message to mean intergenerational time between messages, above which a processor can no longer keep up with its message traffic. Based upon the more realistic assumption that the rate at which a processor generates messages is proportional to its current potential utilization, processor potential utilizations are analytically derived in matrix form for the bidirectional straight line and the square mesh. Closed form derivations are provided for the unidirectional ring and the n-dimensional binary hypercube. In addition, two techniques for extending the results to networks with a very large number of processors are discussed. The cost-effectiveness of the topologies is considered by comparing the cost per unit total potential utilization, where the dollar cost of a network includes both the cost of the processors and the cost of the communication links. Finally, discrete-event simulations are run for each of the topologies for the purpose of providing verification of the theoretical results and for finding the effect of perturbations from the assumption that message generation rate be proportional to a processor's potential utilization.