{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:18:08Z","timestamp":1763468288483,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,2,9]],"date-time":"2016-02-09T00:00:00Z","timestamp":1454976000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1420673 and 1301924"],"award-info":[{"award-number":["1420673 and 1301924"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,3,15]]},"abstract":"<jats:p>In fork-join parallelism, a sequential program is split into a directed acyclic graph of tasks linked by directed dependency edges, and the tasks are executed, possibly in parallel, in an order consistent with their dependencies. A popular and effective way to extend fork-join parallelism is to allow threads to create futures. A thread creates a future to hold the results of a computation, which may or may not be executed in parallel. That result is returned when some thread touches that future, blocking if necessary until the result is ready.<\/jats:p>\n          <jats:p>\n            Recent research has shown that although futures can, of course, enhance parallelism in a structured way, they can have a deleterious effect on cache locality. In the worst case, futures can incur \u03a9(\n            <jats:italic>PT<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            +\n            <jats:italic>tT<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            ) deviations, which implies \u03a9 (\n            <jats:italic>CPT<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            +\n            <jats:italic>CtT<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            ) additional cache misses, where\n            <jats:italic>C<\/jats:italic>\n            is the number of cache lines,\n            <jats:italic>P<\/jats:italic>\n            is the number of processors,\n            <jats:italic>t<\/jats:italic>\n            is the number of touches, and\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\u221e<\/jats:sub>\n            is the computation span. Since cache locality has a large impact on software performance on modern multicores, this result is troubling.\n          <\/jats:p>\n          <jats:p>\n            In this article, we show that if futures are used in a simple, disciplined way, then the situation is much better: if each future is touched only once, either by the thread that created it or by a later descendant of the thread that created it, then parallel executions with work stealing can incur at most\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>CPT<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:sub>\u221e<\/jats:sub>\n            ) additional cache misses\u2014a substantial improvement. This structured use of futures is characteristic of many (but not all) parallel applications.\n          <\/jats:p>","DOI":"10.1145\/2858650","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T13:07:16Z","timestamp":1456146436000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Well-Structured Futures and Cache Locality"],"prefix":"10.1145","volume":"2","author":[{"given":"Maurice","family":"Herlihy","sequence":"first","affiliation":[{"name":"Brown University, Rhode Island, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiyu","family":"Liu","sequence":"additional","affiliation":[{"name":"Brown University, Rhode Island, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/341800.341801"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1229428.1229448"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/277651.277678"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/69558.69562"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/227234.227246"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/215399.215403"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/258492.258517"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/237502.237574"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/209936.209958"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/S0097539793259471"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/324133.324234"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/800223.806778"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/1073970.1073974"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1411204.1411224"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/277650.277725"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1345206.1345215"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1168857.1168877"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/800055.802017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/4472.4478"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/73141.74825"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/2486159.2486174"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/1583991.1584019"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2858650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:43Z","timestamp":1750225723000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,9]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,3,15]]}},"alternative-id":["10.1145\/2858650"],"URL":"https:\/\/doi.org\/10.1145\/2858650","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2016,2,9]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}