Contention resolution and memory load balancing algorithms on distributed shared memory multiprocessors

It is well known that contention is one of the factors that limit the performance of high performance parallel computing systems that implement distributed shared memory (DSM). On cache-coherent DSM multiprocessors, one of the most intrusive forms of contention is the one that occurs at the network interface of a node, due to simultaneous requests for remote memory accesses. This thesis focuses on the issue of resolving remote memory access contention on hardware DSM systems, and on the performance impact of implementing contention resolution algorithms.; The Simultaneous Optical Multiprocessor Exchange Bus (SOME-Bus) is a low-latency, high-bandwidth, fiber-optic interconnection network supporting DSM with a unique feature that every processor is connected to the other processor through a dedicated output channel. The thesis presents simple but effective contention resolution algorithms that rely on the information of average channel utilization, average channel waiting time, number of messages in the channel queue or short-term average channel waiting time reported by each node, and uses simulation to examine the performance of the algorithms on the SOME-Bus multiprocessor. The algorithms detect potential hot spots and resolve contention using dynamic block migration, which is a novel approach for migrating home nodes on a block-level basis and balancing remote memory accesses across the nodes of the system. The algorithms require minimal support from the operating system and all the necessary message transactions happen on the hardware level. Experiments with eight parallel codes on a 64-processor SOME-Bus show that algorithms yield significant performance improvements such as reduction in the execution times, number of remote memory accesses, average channel waiting times and average network latencies. Modified contention resolution algorithms are developed with the addition of data-acknowledge message multicasting. Application of the modified algorithms yields more performance improvements in some codes.; Architectural enhancements to the network interface and directory of the SOME-Bus multiprocessor to support the contention resolution algorithms are also presented.