Run-Time Detection and Recovery From Incorrectly Reordered Memory Operations

We present a new approach for run-time detection of incorrectly reordered memory operations. This problem arises when a load operation is statically scheduled for execution earlier than sequentially preceding store operations, but the computer cannot prove whether the memory locations accessed by the operations are disjoint. Previous techniques for dealing with this problem compare the memory addresses referenced by the reordered load and store instructions; if the addresses overlap, the load instruction is regarded as incorrectly reordered, and a recovery sequence is invoked to correct the error. Instead, the approach described here compares the value loaded out-of-order with the value in the corresponding memory location at the original position of the load instruction in the program; a recovery sequence is invoked whenever the two values are not identical. In contrast to previous techniques, this approach is characterized by constant overhead independent of the type of interference among memory references (e.g. operands with different size, overlapping operands, multiple reordering) and handles special cases (e.g. asynchronous modifications, context switches). We have incorporated this technique in Chameleon, our research compiler for instruction-level parallelism, and have applied it to a VLIW processor. Simulation results have shown performance improvements up to 16% in some cases, and 4-7% in a wider sample, over scheduling without reordering ambiguous memory operations. The algorithm used selects load instructions for disambiguation in a way that causes negligible code expansion due to the recovery sequences, and very infrequent execution of such recovery sequences.

By: Mayan Moudgill and Jaime Moreno

Published in: RC20857 in 1996


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Questions about this service can be mailed to .