{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:55:04Z","timestamp":1787385304277,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>To enhance performance on shared memory multiprocessors, various techniques have been proposed to reduce the latency of memory accesses, including pipelining of accesses, out-of-order execution of accesses, and branch prediction with speculative execution. These optimizations can, however, complicate the user's model of memory. This paper attacks the problem of simplifying programming on two fronts.<\/jats:p>\n                  <jats:p>First, a general framework is presented for defining shared memory consistency conditions that allows nonsequential execution of memory accesses. The interface at which conditions are defined is between the program and the system and is architecture-independent. The framework is used to generalize three consistency conditions---sequential consistency, hybrid consistency, and weak consistency---for nonsequential execution. Thus, familiar consistency conditions can be precisely specified even in optimized architectures.<\/jats:p>\n                  <jats:p>Second, three techniques are described for structuring programs so that a shared memory that provides the weaker (and more efficient) condition of hybrid consistency appears to guarantee the stronger (and more costly) condition of sequential consistency. The benefit of these techniques is that sequentially consistent executions are easier to reason about. The first technique statically classifies accesses based on their type. This approach is extremely simple to use and leads to a general technique for writing efficient synchronization code. The third technique is to avoid data races in the program, which was previously studied in a somewhat different setting.<\/jats:p>\n                  <jats:p>Precise, yet short and comprehensible, proofs are provided for the correctness of the programming techniques. Such proofs shed light on the reasons these techniques work; we believe that the insight gained can lead to the development of other techniques.<\/jats:p>","DOI":"10.1137\/s0097539794278396","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"65-89","source":"Crossref","is-referenced-by-count":13,"title":["Shared Memory Consistency Conditions for Nonsequential Execution: Definitions and Programming Strategies"],"prefix":"10.1137","volume":"27","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Soma","family":"Chaudhuri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roy","family":"Friedman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jennifer L.","family":"Welch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676841"},{"key":"R2","unstructured":"S. Adve,\n                      Designing Memory Consistency Models for Shared\u2010Memory Multiprocessors\n                      , Technical Report 1198, Ph.D. thesis, Computer Science Department, University of Wisconsin, Madison, WI, 1993."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. Adve and M. Hill,\n                      Weak ordering\u2014a new definition\n                      , in Proc. of the 17th International Symposium on Computer Architecture, ACM, New York, 1990, pp. 2\u201314.","DOI":"10.1109\/ISCA.1990.134502"},{"key":"R4","unstructured":"S. Adve and M. Hill,\n                      A Unified Formalization of Four Shared\u2010Memory Models\n                      , Technical Report 1051, Computer Science Department, University of Wisconsin, Madison, WI, 1991."},{"key":"R5","unstructured":"S. Adve and M. Hill,\n                      Sufficient Conditions for Implementing the Data\u2010Race\u2010Free\u20101 Memory Model\n                      , Technical Report 1107, Computer Science Department, University of Wisconsin, Madison, WI, 1992."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Adve, M. Hill, B. Miller, and R. Netzer,\n                      Detecting data races on weak memory systems\n                      , in Proc. of the 18th International Symposium on Computer Architecture, ACM, New York, 1991, pp. 234\u2013243.","DOI":"10.1145\/115952.115976"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/151646.151651"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Ahamad, R. Bazzi, R. John, P. Kohli, and G. Neiger,\n                      The power of processor consistency\n                      , in Proc. of the 5th ACM Symposium On Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 251\u2013260.","DOI":"10.1145\/165231.165264"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Mustaque Ahamad, James Burns, Phillip Hutto, Gil Neiger, Causal memory, Lecture Notes in Comput. Sci., Vol. 579, Springer, Berlin, 1992, 9\u20133094c:68051","DOI":"10.1007\/BFb0022435"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050008"},{"key":"R11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/S0097539794278396","volume":"27","author":"Attiya Hagit","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289215"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"H. Attiya and R. Friedman,\n                      Programming DEC\u2010alpha based multiprocessors the easy way\n                      , in Proc. 6th ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1994, pp. 157\u2013166. Technical Report LPCR 9411, Department of Computer Science, Technion, Israel.","DOI":"10.1145\/181014.192323"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/176575.176576"},{"key":"R15","unstructured":"R. Bisiani, A. Nowatzyk, and M. Ravishankar,\n                      Coherent shared memory on a distributed memory machine\n                      , in Proc. International Conference on Parallel Processing, Penn. State Univ. Press, Philadelphia, PA, 1989, pp. I\u2013133\u2013141."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J.\u2010D. Choi and S. L. Min,\n                      Race frontier: Reproducing data races in parallel program debugging\n                      , in Proc. of the 3rd ACM Symposium on Principles and Practice of Parallel Programming, ACM, New York, 1991, pp. 145\u2013154.","DOI":"10.1145\/109625.109641"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Dinning and E. Schonberg,\n                      Detecting access anomalies in programs with critical sections\n                      , in Proc. of the ACM Workshop on Parallel and Distributed Debugging, ACM, New York, 1991, pp. 85\u201396.","DOI":"10.1145\/122759.122767"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/32.55094"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/2.15"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. Fisher,\n                      Very long instruction word architectures and the ELI\u2010512\n                      , in Proc. of the 10th International Symposium on Computer Architecture, ACM, New York, 1991, pp. 140\u2013150.","DOI":"10.1145\/800046.801649"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, and J. Hennessy,\n                      Memory consistency and event ordering in scalable shared\u2010memory multiprocessors\n                      , in Proc. of the 17th International Symposium on Computer Architecture, ACM, New York, 1990, pp. 15\u201326.","DOI":"10.1109\/ISCA.1990.134503"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"P. Gibbons and M. Merritt,\n                      Specifying non\u2010blocking shared memories\n                      , in Proc. of the 4th ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1992, pp. 306\u2013315.","DOI":"10.1145\/140901.141895"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"P. Gibbons, M. Merritt, and K. Gharachorloo,\n                      Proving sequential consistency of high\u2010performance shared memories\n                      , in Proc. of the 3rd ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1991, pp. 292\u2013303.","DOI":"10.1145\/113379.113406"},{"key":"R24","unstructured":"J. Hennessy and D. Patterson,\n                      Computer Architecture: A Quantitative Approach\n                      , Morgan Kaufmann Publishers Inc., San Mateo, CA, 1990, pp. 251\u2013349."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"M. S. Lam and R. P. Wilson,\n                      Limits of control flow on parallelism\n                      , in Proc. of the 19th International Symposium on Computer Architecture, ACM, New York, 1992, pp. 46\u201357.","DOI":"10.1109\/ISCA.1992.753303"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675439"},{"key":"R29","unstructured":"R. Lipton and J. Sandberg,\n                      PRAM: A Scalable Shared Memory\n                      , Technical Report CS\u2010TR\u2010180\u201088, Computer Science Department, Princeton University, Princeton, NJ, 1988."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"J. Mellor\u2010Crummey,\n                      On\u2010the\u2010fly detection of data races for programs with nested fork\u2010join parallelism\n                      , Proc. Supercomputer Debugging Workshop, Los Alamitos Natl. Lab, Albuquerque, NM, 1991, pp. 24\u201333.","DOI":"10.1145\/125826.125861"},{"key":"R31","unstructured":"R. Netzer,\n                      Race Condition Detection for Debugging Shared\u2010Memory Parallel Programs\n                      , Technical Report 1039, Ph.D. thesis, Computer Science Department, University of Wisconsin, Madison, WI, 1991."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"R. Netzer and B. Miller,\n                      Improving the accuracy of data race detection\n                      , in Proc. of the 3rd ACM Symposium on Principles and Practice of Parallel Programming, ACM, New York, 1991, pp. 133\u2013144.","DOI":"10.1145\/109625.109640"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Y. Patt, W. Hwu, and M. Shebanow,\n                      HPS, a new microarchitecture: Rationale and introduction\n                      , in Proc. of the 18th Annual Microprogramming Workshop, ACM, New York, 1985, pp. 103\u2013108.","DOI":"10.1145\/18927.18916"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"A. Peleg and U. Weiser,\n                      Future trends in microprocessors: Out\u2010of\u2010order execution, speculative branching and their CISC performance models\n                      , in Proc. of the 17th Convention of Electrical and Electronics Engineers in Israel, IEEE Computer Society Press, Los Alamitos, CA, 1991, pp. 263\u2013266.","DOI":"10.1109\/EEIS.1991.217647"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/358527.358537"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/42190.42277"},{"key":"R38","unstructured":"A. Singh,\n                      A Framework for Programming Using Non\u2010Atomic Variables\n                      , Technical Report TRCS\u201093\u201011, Department of Computer Science, University of California at Santa Barbara, 1993."},{"key":"R39","unstructured":"B. Smith,\n                      A massively parallel shared memory computer\n                      , in 3rd ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1991, p. 123."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1109\/2.30730"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"R. N. Zucker and J.\u2010L. Baer,\n                      A performance study of memory consistency models\n                      , in Proc. of the 19th International Symposium on Computer Architecture, ACM, New York, 1992, pp. 2\u201312.","DOI":"10.1109\/ISCA.1992.753299"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794278396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:28Z","timestamp":1787336068000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794278396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794278396"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794278396","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}