Avoiding Memory Contention on Tightly Coupled Multiprocessors

We propose a novel method of scheduling memory access on a non-blocking interconnection network that provides only one-to-one communication. Conflicts at the switches can be avoided if the accesses are scheduled so that no two processors attempt to access the same memory at the same time. We show how such a scheduling problem can be mapped to an edge-coloring problem for a directed graph and present algorithms for solving that problem. We give examples of the application of the algorithm and present simulation results. Keywords. Multistage interconnection networks, non-blocking networks, memory access contention, memory access scheduling, edge coloring of a digraph. 1 Introduction A typical massively parallel computer consists of a number of processing elements and an interconnection network used for exchange of information. Multistage interconnection networks are used in massively parallel computers because they scale well. The number N of inputs is usually equal to the number of o..