{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:18:35Z","timestamp":1763468315705,"version":"3.41.0"},"reference-count":97,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T00:00:00Z","timestamp":1467072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF Graduate Research Fellowship"},{"name":"National Science Foundation","award":["CNS-1017058, CCF-1162148 and CCF-1314547"],"award-info":[{"award-number":["CNS-1017058, CCF-1162148 and CCF-1314547"]}]},{"name":"Intel Corporation and Foxconn Technology Group"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,6,28]]},"abstract":"<jats:p>A data-graph computation\u2014popularized by such programming systems as Galois, Pregel, GraphLab, PowerGraph, and GraphChi\u2014is an algorithm that performs local updates on the vertices of a graph. During each round of a data-graph computation, an update function atomically modifies the data associated with a vertex as a function of the vertex\u2019s prior data and that of adjacent vertices. A dynamic data-graph computation updates only an active subset of the vertices during a round, and those updates determine the set of active vertices for the next round.<\/jats:p>\n          <jats:p>\n            This article introduces P\n            <jats:sc>rism<\/jats:sc>\n            , a chromatic-scheduling algorithm for executing dynamic data-graph computations. P\n            <jats:sc>rism<\/jats:sc>\n            uses a vertex coloring of the graph to coordinate updates performed in a round, precluding the need for mutual-exclusion locks or other nondeterministic data synchronization. A multibag data structure is used by P\n            <jats:sc>rism<\/jats:sc>\n            to maintain a dynamic set of active vertices as an unordered set partitioned by color. We analyze P\n            <jats:sc>rism<\/jats:sc>\n            using work-span analysis. Let\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) be a degree-\u0394 graph colored with \u03c7 colors, and suppose that\n            <jats:italic>Q<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            is the set of active vertices in a round. Define\n            <jats:italic>size<\/jats:italic>\n            (\n            <jats:italic>Q<\/jats:italic>\n            )= |\n            <jats:italic>Q<\/jats:italic>\n            | + \u2211\n            <jats:sub>\n              <jats:italic>v<\/jats:italic>\n              \u2208\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            deg(\n            <jats:italic>v<\/jats:italic>\n            ), which is proportional to the space required to store the vertices of\n            <jats:italic>Q<\/jats:italic>\n            using a sparse-graph layout. We show that a\n            <jats:italic>P<\/jats:italic>\n            -processor execution of P\n            <jats:sc>rism<\/jats:sc>\n            performs updates in\n            <jats:italic>Q<\/jats:italic>\n            using\n            <jats:italic>O<\/jats:italic>\n            (\u03c7 (lg (\n            <jats:italic>Q\/\u03c7<\/jats:italic>\n            ) + lg \u0394 ) + lg\n            <jats:italic>P<\/jats:italic>\n            span and \u0398(\n            <jats:italic>size<\/jats:italic>\n            (\n            <jats:italic>Q<\/jats:italic>\n            ) +\n            <jats:italic>P<\/jats:italic>\n            ) work.\n          <\/jats:p>\n          <jats:p>\n            These theoretical guarantees are matched by good empirical performance. To isolate the effect of the scheduling algorithm on performance, we modified GraphLab to incorporate P\n            <jats:sc>rism<\/jats:sc>\n            and studied seven application benchmarks on a 12-core multicore machine. P\n            <jats:sc>rism<\/jats:sc>\n            executes the benchmarks 1.2 to 2.1 times faster than GraphLab\u2019s nondeterministic lock-based scheduler while providing deterministic behavior.\n          <\/jats:p>\n          <jats:p>\n            This article also presents P\n            <jats:sc>rism<\/jats:sc>\n            -R, a variation of P\n            <jats:sc>rism<\/jats:sc>\n            that executes dynamic data-graph computations deterministically even when updates modify global variables with associative operations. P\n            <jats:sc>rism<\/jats:sc>\n            -R satisfies the same theoretical bounds as P\n            <jats:sc>rism<\/jats:sc>\n            , but its implementation is more involved, incorporating a multivector data structure to maintain a deterministically ordered set of vertices partitioned by color. Despite its additional complexity, P\n            <jats:sc>rism<\/jats:sc>\n            -R is only marginally slower than P\n            <jats:sc>rism<\/jats:sc>\n            . On the seven application benchmarks studied, P\n            <jats:sc>rism<\/jats:sc>\n            -R incurs a 7% geometric mean overhead relative to P\n            <jats:sc>rism<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/2896850","type":"journal-article","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:59:22Z","timestamp":1468929562000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling"],"prefix":"10.1145","volume":"3","author":[{"given":"Tim","family":"Kaler","sequence":"first","affiliation":[{"name":"MIT CSAIL, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Hasenplaugh","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao B.","family":"Schardl","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,18]]},"reference":[{"volume-title":"Proceedings of the International Conference on Parallel Processing. 53--56","author":"Adams L.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536432"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639950.1639989"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735970.1736029"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639949.1640096"},{"volume-title":"Tsitsiklis","year":"1989","author":"Bertsekas Dimitri P.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/865063"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145840"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113380"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"volume-title":"Blumofe and Dionisios Papadopoulos","year":"1999","author":"Robert","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the 1st USENIX Conference on Hot Topics in Parallelism (HotPar\u201909)","year":"2009","author":"Bocchino Robert L.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645932.673194"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800223.806778"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093157.2093165"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.842947"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12151"},{"edition":"3","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/362759.362813"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0723047"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528521.1508255"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961296.1950376"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.21127"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258493"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000120"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584017"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/277652.277725"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10476213"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767596"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/72935.72953"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218029"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0702016"},{"volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","year":"2012","author":"Gonzalez Joseph E.","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/800055.802017"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612697"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810509"},{"volume-title":"The Art of Multiprocessor Programming. Morgan Kaufmann","author":"Herlihy Maurice","key":"e_1_2_1_54_1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm192761164"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/2014698.2014870"},{"key":"e_1_2_1_57_1","unstructured":"Intel. 2012. The Threading Building Blocks. Available at http:\/\/software.intel.com.  Intel. 2012. The Threading Building Blocks. Available at http:\/\/software.intel.com."},{"key":"e_1_2_1_58_1","unstructured":"Intel. 2013. Intel Cilk Plus. Available at http:\/\/software.intel.com.  Intel. 2013. Intel Cilk Plus. Available at http:\/\/software.intel.com."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460833.1460872"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914041"},{"volume-title":"Zosel","year":"1994","author":"Koelbel Charles H.","key":"e_1_2_1_61_1"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","year":"2012","author":"Kyrola Aapo","key":"e_1_2_1_64_1"},{"volume-title":"Omohundro","year":"1986","author":"Lasser Cliff","key":"e_1_2_1_65_1"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/337449.337465"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2006.180"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312056"},{"key":"e_1_2_1_69_1","unstructured":"D. Leijen and J. Hall. 2007. Parallel performance: Optimize managed code for multi-core machines. MSDN Magazine.  D. Leijen and J. Hall. 2007. Parallel performance: Optimize managed code for multi-core machines. MSDN Magazine."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-010-0405-3"},{"volume-title":"SNAP: Stanford Network Analysis Platform. Retrieved","year":"2013","author":"Leskovec J.","key":"e_1_2_1_71_1"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI\u201910)","author":"Low Yucheng","key":"e_1_2_1_75_1"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_77_1","unstructured":"Andrew McCallum. 2012. CoRA Data Set. Available at http:\/\/people.cs.umass.edu\/mccallum\/data.html.  Andrew McCallum. 2012. CoRA Data Set. Available at http:\/\/people.cs.umass.edu\/mccallum\/data.html."},{"volume-title":"Retrieved","year":"2008","author":"McGrady D.","key":"e_1_2_1_78_1"},{"volume-title":"Retrieved","year":"2009","author":"Mitchell Tom","key":"e_1_2_1_79_1"},{"volume-title":"Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI\u201999)","year":"2073","author":"Murphy Kevin P.","key":"e_1_2_1_80_1"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541964"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354805"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528521.1508256"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344551.1344561"},{"volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann","author":"Pearl Judea","key":"e_1_2_1_87_1"},{"volume-title":"Intel Threading Building Blocks. O\u2019Reilly & Associates","author":"Reinders James","key":"e_1_2_1_88_1"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486189"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.65"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96731"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21738-3"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167156"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1093\/qjmam\/1.1.287"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555815.1555796"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.126164"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2896850","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2896850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:05Z","timestamp":1750221545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2896850"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":97,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,28]]}},"alternative-id":["10.1145\/2896850"],"URL":"https:\/\/doi.org\/10.1145\/2896850","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2016,6,28]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}