Show simple item record

dc.contributor.authorAdve, Sarita Ven_US
dc.contributor.authorHill, Mark Den_US
dc.description.abstractA model for correct program behavior commonly and often implicitly assumed by programmers is that of sequential consistency, which guarantees that all memory accesses execute atomically and in program order. An alternative programmer�s model, weak ordering, offers greater performance potential, especially for highly parallel shared memory systems. Weak ordering was first defined by Dubois, Scheurich and Briggs in terms of a set of constraints for hardware, which are not necessary for its intuitive goal. We define a system to be weakly ordered with respect to a set of software constraints if it appears sequentially consistent to software obeying those constraints. We argue that this definition more directly reflects the intuition behind weak ordering, facilitates a formal statement of the programmer�s view of the system, and does not specify unnecessary directives for hardware. For software that does not allow data races, we show that the new definition allows a violation of the old definition and makes possible implementations that have a higher performance potential. We give an example of one such implementation for cache-based systems with general interconnects to illustrate the power of the new definition. The insight gained from the implementation of weak ordering can also be applied to sequential consistency. We give an algorithm and an implementation for cache-based systems with general interconnects that has a higher performance potential than others we are aware of. We also investigate a markedly new approach that is allowed by our definition to implement weak ordering, and possibly sequential consistency.en_US
dc.publisherUniversity of Wisconsin-Madison Department of Computer Sciencesen_US
dc.titleWeak Ordering - A New Definition and Some Implicationsen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

  • CS Technical Reports
    Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record