TR-155: Hot-Spot Contention in Binary Hypercube Networks

Abstract

In large parallel processing systems there is a possibility of many processors requesting access to the same data item, or “service” by the same processor, at the same time. Such hot-spot contention creates congestion in the system. Hot-spot contention has been studied previously in the context of shared-memory multiprocessor systems. This paper considers the impact of hot-spot contention in distributed-memory multicomputer systems. Since the binary hypercube network offers a reasonable compromise between network cost and performance, two hypercube-based static interconnection networks are considered. One is a standard binary hypercube and the other is a binary hypercube-based hierarchical interconnection network. The impact of hot-spot contention in both these networks is studied. Two techniques have been proposed for shared-memory multiprocessor systems to increase the system capacity in handling hot-spot references: hardware combining, and software combining. The effectiveness of the two corresponding approaches for multicomputer systems is studied here.