Performance of a hierarchically interconnected multiprocessor

Abstract

A queuing model of a parallel processor with an interconnection network incorporating a hierarchy of paths is developed and analyzed. The model captures the behavior of the processors, the interconnection network, and the storage modules. The network considered includes fast paths that operate in the absence of contention and alternate paths with contention resolution. The network overall performance is shown to be close to that of a contention-free network of fast paths. It is shown that, as the load varies, this hierarchical interconnection network is robust with respect to ideal networks with no delay. An analysis of the effects of 'hot spots' shows that processor throughput is limited by storage rather than communications bandwidth and that an upper bound on the processor utilization is inversely proportional to the miss probability. The analysis suggests that a fetch-and-add network could be incorporated into a connection hierarchy whose average performance is close to that of a network with no combining, so this may be an effective way to handle hot spots without much penalty to overall system performance.