A Compiler Algorithm for Managing Asynchronous Memory Read Completion

Abstract

Computers with conventional memory systems have a predictable latency between initiation and completion of a memory read. On such machines it is relatively easy for either the compiler or the processor to guarantee that a load has completed before further references to the loaded register are made. In a machine with a logically shared, but physically distributed, memory, these latencies are not statically predictable. Some existing systems, such as the Cray T3D, deal with this problem by using a hardware mechanism to enforce synchronization on a register which is the target of a remote memory access. The M-Machine currently being designed by the Concurrent VLSI Architecture Group at MIT performs remote memory accesses asynchronously, and allows program execution to continue while the access is outstanding, but does not enforce synchronization in hardware. This architectural simplification, and resulting relaxation of memory completion semantics, poses a challenge to the compiler: how can this simpler memory system be efficiently supported while maintaining program correctness. In particular, what is required to guarantee that there are no conflicts between completion of a memory operation by placing a value into a register, and other uses of the register being written. This paper describes a general solution to this problem, develops an algorithm to implement it, and shows that the algorithm is correct.