{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T07:01:40Z","timestamp":1770706900549,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SCoRPiO Project","award":["323872"],"award-info":[{"award-number":["323872"]}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["261580"],"award-info":[{"award-number":["261580"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["217068"],"award-info":[{"award-number":["217068"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["248647"],"award-info":[{"award-number":["248647"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["327744"],"award-info":[{"award-number":["327744"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K017594\/1"],"award-info":[{"award-number":["EP\/K017594\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>Processor architectures has taken a turn toward many-core processors, which integrate multiple processing cores on a single chip to increase overall performance, and there are no signs that this trend will stop in the near future. Many-core processors are harder to program than multicore and single-core processors due to the need for writing parallel or concurrent programs with high degrees of parallelism. Moreover, many-cores have to operate in a mode of strong scaling because of memory bandwidth constraints. In strong scaling, increasingly finer-grain parallelism must be extracted in order to keep all processing cores busy.<\/jats:p><jats:p>Task dataflow programming models have a high potential to simplify parallel programming because they alleviate the programmer from identifying precisely all intertask dependences when writing programs. Instead, the task dataflow runtime system detects and enforces intertask dependences during execution based on the description of memory accessed by each task. The runtime constructs a task dataflow graph that captures all tasks and their dependences. Tasks are scheduled to execute in parallel, taking into account dependences specified in the task graph.<\/jats:p><jats:p>Several papers report important overheads for task dataflow systems, which severely limits the scalability and usability of such systems. In this article, we study efficient schemes to manage task graphs and analyze their scalability. We assume a programming model that supports input, output, and in\/out annotations on task arguments, as well as commutative in\/out and reductions. We analyze the structure of task graphs and identify<jats:italic>versions<\/jats:italic>and<jats:italic>generations<\/jats:italic>as key concepts for efficient management of task graphs. Then, we present three schemes to manage task graphs building on<jats:italic>graph representations, hypergraphs<\/jats:italic>, and<jats:italic>lists<\/jats:italic>. We also consider a fourth edgeless scheme that synchronizes tasks using integers. Analysis using microbenchmarks shows that the graph representation is not always scalable and that the edgeless scheme introduces least overhead in nearly all situations.<\/jats:p>","DOI":"10.1145\/2541228.2555316","type":"journal-article","created":{"date-parts":[[2014,1,14]],"date-time":"2014-01-14T13:39:57Z","timestamp":1389706797000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Analysis of dependence tracking algorithms for task dataflow execution"],"prefix":"10.1145","volume":"10","author":[{"given":"Hans","family":"Vandierendonck","sequence":"first","affiliation":[{"name":"Queen's University Belfast"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Tzenakis","sequence":"additional","affiliation":[{"name":"Queen's University Belfast"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios S.","family":"Nikolopoulos","sequence":"additional","affiliation":[{"name":"Queen's University Belfast"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS'10)","author":"Agrawal K.","unstructured":"Agrawal , K. , Leiserson , C. E. , and Sukha , J . 2010. Executing task graphs using work-stealing . In Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS'10) . 1--12. Agrawal, K., Leiserson, C. E., and Sukha, J. 2010. Executing task graphs using work-stealing. In Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS'10). 1--12."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of SAMOS XI: International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 217--224","author":"Alvanos M.","unstructured":"Alvanos , M. , Tzenakis , G. , Bilas , A. , and Nikolopoulos , D. S . 2011. Design and evaluation of a task-based parallel H.264 video encoder for heterogeneous processors . In Proceedings of SAMOS XI: International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 217--224 . Alvanos, M., Tzenakis, G., Bilas, A., and Nikolopoulos, D. S. 2011. Design and evaluation of a task-based parallel H.264 video encoder for heterogeneous processors. In Proceedings of SAMOS XI: International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 217--224."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"key":"e_1_2_1_4_1","unstructured":"Barcelona Supercomputing Center. 2008. SMP Superscalar (SMPSS) User's Manual 2.2 ed. Barcelona Supercomputing Center. Barcelona Supercomputing Center. 2008. SMP Superscalar (SMPSS) User's Manual 2.2 ed. Barcelona Supercomputing Center."},{"key":"e_1_2_1_5_1","unstructured":"Berge C. 1973. Graphs and Hypergraphs. North-Holland. Berge C. 1973. Graphs and Hypergraphs. North-Holland."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993573"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Bosilca G. Bouteiller A. Danalis A. Herault T. Lemarinier P. and Dongarra J. 2010. DAGuE: A Generic Distributed DAG Engine for High Performance Computing. Technical Report. Innovative Computing Laboratory. Bosilca G. Bouteiller A. Danalis A. Herault T. Lemarinier P. and Dongarra J. 2010. DAGuE: A Generic Distributed DAG Engine for High Performance Computing. Technical Report. Innovative Computing Laboratory.","DOI":"10.1109\/IPDPS.2011.281"},{"key":"e_1_2_1_9_1","first-page":"3","article-title":"Concurrent collections. Sci","volume":"18","author":"Budimli\u0107 Z.","year":"2010","unstructured":"Budimli\u0107 , Z. , Burke , M. , Cav\u00e9 , V. , Knobe , K. , Lowney , G. , Newton , R. , Palsberg , J. , Peixotto , D. , Sarkar , V. , Schlimbach , F. , and Ta\u015firlar , S. 2010 . Concurrent collections. Sci . Program. 18 , 3 -- 4 , 203--217. Budimli\u0107, Z., Burke, M., Cav\u00e9, V., Knobe, K., Lowney, G., Newton, R., Palsberg, J., Peixotto, D., Sarkar, V., Schlimbach, F., and Ta\u015firlar, S. 2010. Concurrent collections. Sci. Program. 18, 3--4, 203--217.","journal-title":"Program."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248397"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995896.1995945"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1080\/00031305.1981.10479327","article-title":"Rank transformations as a bridge between parametric and nonparametric statistics","volume":"35","author":"Conover W. J.","year":"1981","unstructured":"Conover , W. J. and Iman , R. L. 1981 . Rank transformations as a bridge between parametric and nonparametric statistics . American Statistician 35 , 3, 124 -- 129 . Conover, W. J. and Iman, R. L. 1981. Rank transformations as a bridge between parametric and nonparametric statistics. American Statistician 35, 3, 124--129.","journal-title":"American Statistician"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626411000151"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342010391989"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584017"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2155620.2155628"},{"key":"e_1_2_1_18_1","unstructured":"Hennessy J. L. and Patterson D. A. 2003. Computer architecture: A Quantitative Approach 3rd ed. Morgan Kaufmann. Hennessy J. L. and Patterson D. A. 2003. Computer architecture: A Quantitative Approach 3rd ed. Morgan Kaufmann."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941563"},{"key":"e_1_2_1_20_1","volume-title":"Technical Report UT-CS-09-643. LAPACK Working Note 220.","author":"Kurzak J.","year":"2009","unstructured":"Kurzak , J. and Dongarra , J . 2009 . Fully Dynamic Scheduler for Numerical Computing on Multicore Processors . Technical Report UT-CS-09-643. LAPACK Working Note 220. Kurzak, J. and Dongarra, J. 2009. Fully Dynamic Scheduler for Numerical Computing on Multicore Processors. Technical Report UT-CS-09-643. LAPACK Working Note 220."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER'08)","author":"Perez J. M.","unstructured":"Perez , J. M. , Badia , R. M. , and Labarta , J . 2008. A dependency-aware task-based programming environment for multicore architectures . In Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER'08) . 142--151. Perez, J. M., Badia, R. M., and Labarta, J. 2008. A dependency-aware task-based programming environment for multicore architectures. In Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER'08). 142--151."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810085.1810122"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145864"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503233"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar'11)","author":"Vandierendonck H.","unstructured":"Vandierendonck , H. , Pratikakis , P. , and Nikolopoulos , D. S . 2011a. Parallel programming of general-purpose programs using task-based programming models . In Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar'11) . Vandierendonck, H., Pratikakis, P., and Nikolopoulos, D. S. 2011a. Parallel programming of general-purpose programs using task-based programming models. In Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar'11)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.7"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541228.2555316","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2541228.2555316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:35:01Z","timestamp":1750232101000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541228.2555316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2541228.2555316"],"URL":"https:\/\/doi.org\/10.1145\/2541228.2555316","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}