Implementing a weak form of memory consistency on a tree-based system

Abstract

In this thesis, we propose and implement a weak form of memory consistency, called the Release Consistency for the Tree structure (RCT) model. This model exploits the properties of a tree network to yield a programming model, which for all practical purposes is as simple as the earlier proposed RC model [1], but yields better performance owing to fewer access order restrictions. The RCT model correctly executes all programs that are free of data races. This RCT model is relevant to a Cache Only Memory Architecture (COMA), with a hierarchical cache-bus structure in which the processors are located on the lowest bus, while the directory is distributed among the higher-level buses. The uniqueness of the path between any two nodes in such a network ensures that messages issued by one node reach any other node in the order in which they were issued. Our consistency model recognizes two major access categories: competing and non-competing. Competing category accesses synchronize interprocess accesses to data. This data, which is not supposed to be accessed in the presence of races, falls in the non-competing category. For the RCT model to work, the Sequential Consistency (SC) execution of competing category accesses must be guaranteed by the hardware. This is done by having each processor and directory node implement a suite of rules, called the Network Protocol (NP), which governs their state transitions and outputs. Accesses to non-competing data can be performed out of program order and do not have to be atomic. The RCT model benefits from its implementation on a tree network in two ways. First, competing category writes complete faster since they do not have to receive invalidation acknowledgments from the individual processors that cache the data. Secondly, non-competing writes need not be acknowledged, and release accesses need not stall pending the completion of the coherence phase of previous non-competing writes. We have also combined the fetching and the invalidation phases of the write miss service, since we believe that this arrangement will reduce write miss latencies. To achieve SC executions of competing category accesses, the NP ensures that competing accesses to the same item are serialized, and that all nodes see a consistent order of writes to competing items. The former goal is met by aborting accesses whenever their network transactions interfere, while the latter goal is met by a combination of access order restrictions and the message-passing properties of the network. The NP is also exploited to support Spin Locks, while incurring minimal additional hardware overheads. Finally, since the system we have chosen is a COMA, the data blocks in the memory lack a home location, and hence, cache replacements could lead to the loss of this data. The NP addresses this problem by incorporating a mechanism to detect the last copy of a data block and effect its relocation. The possibility of interference between cache replacements and memory accesses is precluded by aborting the memory access whenever necessary. Hence, the results regarding the SC execution of competing accesses will still hold in the face of cache replacements. Thus, we have implemented an RC-like memory model on a COMA with a tree interconnection, by identifying the state transition rules and the access order restrictions that are necessary to give correct executions of data race-free programs.