Out-of-Order Execution in Sequentially Consistent Shared-Memory Systems:Theory and Experiments

Traditional implementation of sequential consistency in shared-memory systems requires memory accesses to be globally performed in program order.Based on an event ordering model for correct executions in shared-memory systems,this paper proposes and proves that out-of-order execution does not influence the correctness of an execution providing certain condition is met.Simulation results show that out-of-order execution proposed in this paper is an effective way to improve the performance of a sequentially consistent shared-memory system.

Out-of-order execution in sequentially consistent shared-memory systems: Theory and experiments

Traditional implementation of sequential consistency in shared-memory systems requires memory accesses to be globally performed in program order. Based on an event ordering model for correct executions in shared-memory systems, this paper proposes and proves that out-of-order execution does not influence the correctness of an execution providing certain condition is met. Simulation results show that out-of-order execution proposed in this paper is an effective way to improve the performance of a sequentially consistent shared-memory system. The work is supported by the President Young Investigator Foundation of Chinese Academy of Sciences and the National Natural Science Foundation of China. For the biography ofHu Weiwu please refer to p.109, No.2, Vol.13 of this Journal. Xia Peisu in an Academician of the Chinese Academy of Sciences and a Professor of the Institute of Computing Technology. She received her Ph.D. degree in electrical engineering from University of Edinburgh, United Kindom, in 1950. Her current research interests include computer architecture, computer engineering, high speed pipeline system and parallel processing.