{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T19:07:03Z","timestamp":1778267223251,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T00:00:00Z","timestamp":1471305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-13-MONU-0007"],"award-info":[{"award-number":["ANR-13-MONU-0007"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>To face the advent of multicore processors and the ever increasing complexity of hardware architectures, programming models based on DAG parallelism regained popularity in the high performance, scientific computing community. Modern runtime systems offer a programming interface that complies with this paradigm and powerful engines for scheduling the tasks into which the application is decomposed. These tools have already proved their effectiveness on a number of dense linear algebra applications. This article evaluates the usability and effectiveness of runtime systems based on the Sequential Task Flow model for complex applications, namely, sparse matrix multifrontal factorizations that feature extremely irregular workloads, with tasks of different granularities and characteristics and with a variable memory consumption. Most importantly, it shows how this parallel programming model eases the development of complex features that benefit the performance of sparse, direct solvers as well as their memory consumption. We illustrate our discussion with the multifrontal QR factorization running on top of the StarPU runtime system.<\/jats:p>","DOI":"10.1145\/2898348","type":"journal-article","created":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T12:14:20Z","timestamp":1471349660000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Implementing Multifrontal Sparse Solvers for Multicore Architectures with Sequential Task Flow Runtime Systems"],"prefix":"10.1145","volume":"43","author":[{"given":"Emmanuel","family":"Agullo","sequence":"first","affiliation":[{"name":"Inria-LaBRI, Talence cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alfredo","family":"Buttari","sequence":"additional","affiliation":[{"name":"CNRS-IRIT, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdou","family":"Guermouche","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Bordeaux"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florent","family":"Lopez","sequence":"additional","affiliation":[{"name":"UPS-IRIT, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_53"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/180\/1\/012037"},{"key":"e_1_2_1_3_1","volume-title":"Fully empirical autotuned QR factorization for multicore architectures. CoRR abs\/1102.5328","author":"Agullo Emmanuel","year":"2011","unstructured":"Emmanuel Agullo , Jack Dongarra , Rajib Nath , and Stanimire Tomov . 2011. Fully empirical autotuned QR factorization for multicore architectures. CoRR abs\/1102.5328 ( 2011 ). Emmanuel Agullo, Jack Dongarra, Rajib Nath, and Stanimire Tomov. 2011. Fully empirical autotuned QR factorization for multicore architectures. CoRR abs\/1102.5328 (2011)."},{"key":"e_1_2_1_4_1","unstructured":"Randy Allen and Ken Kennedy. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann.   Randy Allen and Ken Kennedy. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann."},{"key":"e_1_2_1_5_1","volume-title":"Multifrontal QR factorization in a multiprocessor environment. Numerical Linear Algebra with Applications 3(4)","author":"Amestoy Patrick R.","year":"1996","unstructured":"Patrick R. Amestoy , Iain S. Duff , and Chiara Puglisi . 1996. Multifrontal QR factorization in a multiprocessor environment. Numerical Linear Algebra with Applications 3(4) ( 1996 ), 275--300. Patrick R. Amestoy, Iain S. Duff, and Chiara Puglisi. 1996. Multifrontal QR factorization in a multiprocessor environment. Numerical Linear Algebra with Applications 3(4) (1996), 275--300."},{"key":"e_1_2_1_6_1","unstructured":"The OpenMP architecture review board. 2013. OpenMP 4.0 Complete specifications. (2013).  The OpenMP architecture review board. 2013. OpenMP 4.0 Complete specifications. (2013)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-001-0004-z"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.v21:18"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.10.003"},{"key":"e_1_2_1_11_1","volume-title":"Dense linear algebra on distributed heterogeneous hardware with a symbolic DAG approach. Scalable Computing and Communications: Theory and Practice","author":"Bosilca George","year":"2013","unstructured":"George Bosilca , Aurelien Bouteiller , Anthony Danalis , Thomas Herault , Piotr Luszczek , and Jack Dongarra . 2013. Dense linear algebra on distributed heterogeneous hardware with a symbolic DAG approach. Scalable Computing and Communications: Theory and Practice ( 2013 ), 699--733. George Bosilca, Aurelien Bouteiller, Anthony Danalis, Thomas Herault, Piotr Luszczek, and Jack Dongarra. 2013. Dense linear algebra on distributed heterogeneous hardware with a symbolic DAG approach. Scalable Computing and Communications: Theory and Practice (2013), 699--733."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063393"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1155\/2010\/521797"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/110846427"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.10.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012962640100049X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"e_1_2_1_18_1","unstructured":"Timothy A. Davis. 2014. SuiteSparse 4.4.0. (October 2014). Software package.  Timothy A. Davis. 2014. SuiteSparse 4.4.0. (October 2014). Software package."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"e_1_2_1_21_1","unstructured":"Edsger W. Dijkstra. 1965. Een algorithme ter voorkoming van de dodelijke omarming. (1965). http:\/\/www.cs.utexas.edu\/users\/EWD\/ewd01xx\/EWD108.PDF (circulated privately).  Edsger W. Dijkstra. 1965. Een algorithme ter voorkoming van de dodelijke omarming. (1965). http:\/\/www.cs.utexas.edu\/users\/EWD\/ewd01xx\/EWD108.PDF (circulated privately)."},{"key":"e_1_2_1_22_1","volume-title":"Selected Writings on Computing: A Personal Perspective","author":"Dijkstra Edsger W.","unstructured":"Edsger W. Dijkstra . 1982. The mathematics behind the banker's algorithm . In Selected Writings on Computing: A Personal Perspective . Springer , New York , 308--312. DOI:http:\/\/dx.doi.org\/10.1007\/978-1- 4612-5695-3_54 10.1007\/978-1- Edsger W. Dijkstra. 1982. The mathematics behind the banker's algorithm. In Selected Writings on Computing: A Personal Perspective. Springer, New York, 308--312. DOI:http:\/\/dx.doi.org\/10.1007\/978-1- 4612-5695-3_54"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2013.01.003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2779052"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407861"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(03)00099-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1885276.1885302"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757216"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629641"},{"key":"e_1_2_1_31_1","volume-title":"Fully dynamic scheduler for numerical computing on multicore processors. LAPACK Working Note lawn220","author":"Kurzak Jakub","year":"2009","unstructured":"Jakub Kurzak and Jack Dongarra . 2009. Fully dynamic scheduler for numerical computing on multicore processors. LAPACK Working Note lawn220 ( 2009 ). Jakub Kurzak and Jack Dongarra. 2009. Fully dynamic scheduler for numerical computing on multicore processors. LAPACK Working Note lawn220 (2009)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/7921.11325"},{"key":"e_1_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In Proceedings of HPCN'96","author":"Pellegrini Fran\u00e7ois","year":"1996","unstructured":"Fran\u00e7ois Pellegrini and Jean Roman . 1996 . Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In Proceedings of HPCN'96 , Lecture Notes in Computer Science , Vol. 1067 . Springer , 493--498. Fran\u00e7ois Pellegrini and Jean Roman. 1996. Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In Proceedings of HPCN'96, Lecture Notes in Computer Science, Vol. 1067. Springer, 493--498."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1527286.1527288"},{"key":"e_1_2_1_36_1","volume-title":"Memory and Performance Issues in Parallel Multifrontal Factorizations and Triangular Solutions with Sparse Right-Hand Sides. Th\u00e8se de doctorat","author":"Rouet Franois-Henry","unstructured":"Franois-Henry Rouet . 2012. Memory and Performance Issues in Parallel Multifrontal Factorizations and Triangular Solutions with Sparse Right-Hand Sides. Th\u00e8se de doctorat . Institut National Polytechnique de Toulouse , Toulouse, France . http:\/\/tel.archives-ouvertes.fr\/tel-00785748 Franois-Henry Rouet. 2012. Memory and Performance Issues in Parallel Multifrontal Factorizations and Triangular Solutions with Sparse Right-Hand Sides. Th\u00e8se de doctorat. Institut National Polytechnique de Toulouse, Toulouse, France. http:\/\/tel.archives-ouvertes.fr\/tel-00785748"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/356004.356006"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.993206"},{"key":"e_1_2_1_39_1","volume-title":"Sparse QR factorization on the GPU. (Jan","author":"Yeralan Sencer","year":"2015","unstructured":"Sencer Yeralan , Timothy A. Davis , and Sanjay Ranka . 2015. Sparse QR factorization on the GPU. (Jan . 2015 ). Submitted to ACM Transactions on Mathematical Software . Sencer Yeralan, Timothy A. Davis, and Sanjay Ranka. 2015. Sparse QR factorization on the GPU. (Jan. 2015). Submitted to ACM Transactions on Mathematical Software."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2898348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:29Z","timestamp":1750222589000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,16]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/2898348"],"URL":"https:\/\/doi.org\/10.1145\/2898348","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,16]]},"assertion":[{"value":"2014-11-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-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}