{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:35:15Z","timestamp":1750221315116,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T00:00:00Z","timestamp":1498780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CSR-1218695, CAREER-1253703, CCF-1421612 and XPS-1629126"],"award-info":[{"award-number":["CSR-1218695, CAREER-1253703, CCF-1421612 and XPS-1629126"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            It is notoriously challenging to develop parallel software systems that are both scalable and correct. Runtime support for parallelism\u2014such as multithreaded record and replay, data race detectors, transactional memory, and enforcement of stronger memory models\u2014helps achieve these goals, but existing commodity solutions slow programs substantially to track (i.e., detect or control) an execution\u2019s cross-thread dependencies accurately. Prior work tracks cross-thread dependencies either \u201cpessimistically,\u201d slowing every program access, or \u201coptimistically,\u201d allowing for lightweight instrumentation of most accesses but dramatically slowing accesses that are\n            <jats:italic>conflicting<\/jats:italic>\n            (i.e., involved in cross-thread dependencies).\n          <\/jats:p>\n          <jats:p>\n            This article presents two novel approaches that seek to improve the performance of dependence tracking.\n            <jats:italic>Hybrid tracking<\/jats:italic>\n            (HT) hybridizes pessimistic and optimistic tracking by overcoming a fundamental mismatch between these two kinds of tracking. HT uses an adaptive, profile-based policy to make runtime decisions about switching between pessimistic and optimistic tracking.\n            <jats:italic>Relaxed tracking<\/jats:italic>\n            (RT) attempts to reduce optimistic tracking\u2019s overhead on conflicting accesses by tracking dependencies in a \u201crelaxed\u201d way\u2014meaning that not all dependencies are tracked accurately\u2014while still preserving both program semantics and runtime support\u2019s correctness. To demonstrate the usefulness and potential of HT and RT, we build runtime support based on the two approaches. Our evaluation shows that both approaches offer performance advantages over existing approaches, but there exist challenges and opportunities for further improvement.\n          <\/jats:p>\n          <jats:p>HT and RT are distinct solutions to the same problem. It is easier to build runtime support based on HT than on RT, although RT does not incur the overhead of online profiling. This article presents the two approaches together to inform and inspire future designs for efficient parallel runtime support.<\/jats:p>","DOI":"10.1145\/3108138","type":"journal-article","created":{"date-parts":[[2017,8,30]],"date-time":"2017-08-30T12:52:18Z","timestamp":1504097538000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hybridizing and Relaxing Dependence Tracking for Efficient Parallel Runtime Support"],"prefix":"10.1145","volume":"4","author":[{"given":"Man","family":"Cao","sequence":"first","affiliation":[{"name":"Ohio State University, Columbus, OH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minjia","family":"Zhang","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aritra","family":"Sengupta","sequence":"additional","affiliation":[{"name":"Ohio State University, Columbus, OH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Swarnendu","family":"Biswas","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael D.","family":"Bond","sequence":"additional","affiliation":[{"name":"Ohio State University, Columbus, OH"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Mart\u00edn Abadi Tim Harris and Mojtaba Mehrara. 2009. Transactional memory with strong atomicity using off-the-shelf memory protection hardware. In PPoPP. 185--196.  Mart\u00edn Abadi Tim Harris and Mojtaba Mehrara. 2009. Transactional memory with strong atomicity using off-the-shelf memory protection hardware. In PPoPP. 185--196.","DOI":"10.1145\/1594835.1504203"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1787234.1787255"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/325164.325100"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.391.0211"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.442.0399"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277734"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814292"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2414729.2414732"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375591"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807426.2807434"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509519"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/582419.582440"},{"volume-title":"Computer Systems Theory, Technology, and Applications","author":"Burrows Mike","key":"e_1_2_1_14_1","unstructured":"Mike Burrows . 2004. How to implement unnecessary mutexes . In Computer Systems Theory, Technology, and Applications . Springer--Verlag , 51--57. Mike Burrows. 2004. How to implement unnecessary mutexes. In Computer Systems Theory, Technology, and Applications. Springer--Verlag, 51--57."},{"key":"e_1_2_1_15_1","volume-title":"Bond","author":"Cao Man","year":"2014","unstructured":"Man Cao , Minjia Zhang , and Michael D . Bond . 2014 . Drinking from both glasses: Adaptively combining pessimistic and optimistic synchronization for efficient parallel runtime support. In WoDet . Man Cao, Minjia Zhang, and Michael D. Bond. 2014. Drinking from both glasses: Adaptively combining pessimistic and optimistic synchronization for efficient parallel runtime support. In WoDet."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851143"},{"key":"e_1_2_1_17_1","volume-title":"STAMP: Stanford transactional applications for multi-processing. In IISWC.","author":"Minh Chi Cao","year":"2008","unstructured":"Chi Cao Minh , JaeWoong Chung , Christos Kozyrakis , and Kunle Olukotun . 2008 . STAMP: Stanford transactional applications for multi-processing. In IISWC. Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. 2008. STAMP: Stanford transactional applications for multi-processing. In IISWC."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512560"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370843"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693464"},{"key":"e_1_2_1_21_1","unstructured":"Brian Demsky and Alokika Dash. 2010. Evaluating contention management using discrete event simulation. In TRANSACT.  Brian Demsky and Alokika Dash. 2010. Evaluating contention management using discrete event simulation. In TRANSACT."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612696"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542494"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250762"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375618"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Lance Hammond Vicky Wong Mike Chen Brian D. Carlstrom John D. Davis Ben Hertzberg Manohar K. Prabhu Honggo Wijaya Christos Kozyrakis and Kunle Olukotun. 2004. Transactional memory coherence and consistency. In ISCA. 102--113.   Lance Hammond Vicky Wong Mike Chen Brian D. Carlstrom John D. Davis Ben Hertzberg Manohar K. Prabhu Honggo Wijaya Christos Kozyrakis and Kunle Olukotun. 2004. Transactional memory coherence and consistency. In ISCA. 102--113.","DOI":"10.1145\/1028176.1006711"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/949305.949340"},{"key":"e_1_2_1_29_1","volume-title":"Transactional Memory","author":"Harris Tim","unstructured":"Tim Harris , James Larus , and Ravi Rajwar . 2010. Transactional Memory ( 2 nd ed.). Morgan 8 Claypool Publishers . Tim Harris, James Larus, and Ravi Rajwar. 2010. Transactional Memory (2nd ed.). Morgan 8 Claypool Publishers.","edition":"2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1133984"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Yanyan Jiang Du Li Chang Xu Xiaoxing Ma and Jian Lu. 2015. Optimistic shared memory dependence tracing. In ASE. 524--534.  Yanyan Jiang Du Li Chang Xu Xiaoxing Ma and Jian Lu. 2015. Optimistic shared memory dependence tracing. In ASE. 524--534.","DOI":"10.1109\/ASE.2015.11"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2384616.2384641"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/582419.582433"},{"key":"e_1_2_1_34_1","article-title":"Deuce: Noninvasive software transactional memory in java","volume":"5","author":"Korland Guy","year":"2010","unstructured":"Guy Korland , Nir Shavit , and Pascal Felber . 2010 . Deuce: Noninvasive software transactional memory in java . Trans. High Perf. EAC 5 , 2 (2010). Guy Korland, Nir Shavit, and Pascal Felber. 2010. Deuce: Noninvasive software transactional memory in java. Trans. High Perf. EAC 5, 2 (2010).","journal-title":"Trans. High Perf. EAC"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676929"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254119"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735970.1736031"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.28"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040336"},{"key":"e_1_2_1_41_1","unstructured":"Hassan Salehe Matar Ismail Kuru Serdar Tasiran and Roman Dementiev. 2014. Accelerating precise race detection using commercially-available hardware transactional memory support. In WoDet.  Hassan Salehe Matar Ismail Kuru Serdar Tasiran and Roman Dementiev. 2014. Accelerating precise race detection using commercially-available hardware transactional memory support. In WoDet."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378588"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542479"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1449764.1449780"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1299042.1299063"},{"key":"e_1_2_1_46_1","unstructured":"Jessica Ouyang Peter M. Chen Jason Flinn and Satish Narayanasamy. 2013. ...and region serializability for all. In HotPar.  Jessica Ouyang Peter M. Chen Jason Flinn and Satish Narayanasamy. 2013. ...and region serializability for all. In HotPar."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629593"},{"key":"e_1_2_1_48_1","volume-title":"Barnes","author":"Ritson Carl G.","year":"2013","unstructured":"Carl G. Ritson and Frederick R. M . Barnes . 2013 . An evaluation of Intel\u2019s restricted transactional memory for CPAs. In CPA. 271--292. Carl G. Ritson and Frederick R. M. Barnes. 2013. An evaluation of Intel\u2019s restricted transactional memory for CPAs. In CPA. 271--292."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/312203.312214"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167515.1167496"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122971.1123001"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/248208.237179"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775054.2694379"},{"key":"e_1_2_1_54_1","volume-title":"Legato: End-to-end bounded region serializability using commodity hardware transactional memory. In CGO. 1--13.","author":"Sengupta Aritra","year":"2017","unstructured":"Aritra Sengupta , Man Cao , Michael D. Bond , and Milind Kulkarni . 2017 . Legato: End-to-end bounded region serializability using commodity hardware transactional memory. In CGO. 1--13. Aritra Sengupta, Man Cao, Michael D. Bond, and Milind Kulkarni. 2017. Legato: End-to-end bounded region serializability using commodity hardware transactional memory. In CGO. 1--13."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161032"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504199"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2009.20"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854287"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950370"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504288"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781145"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1736020.1736039"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503232"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892229"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688510"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737970"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854311"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3108138","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3108138","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3108138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:43Z","timestamp":1750212823000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3108138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,30]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3108138"],"URL":"https:\/\/doi.org\/10.1145\/3108138","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2017,6,30]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}