{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:48:38Z","timestamp":1783036118516,"version":"3.54.6"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319436586","type":"print"},{"value":"9783319436593","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-43659-3_45","type":"book-chapter","created":{"date-parts":[[2016,8,8]],"date-time":"2016-08-08T02:54:01Z","timestamp":1470624841000},"page":"617-630","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":64,"title":["A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves"],"prefix":"10.1007","author":[{"given":"Weifeng","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ang","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Hogg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Iain S.","family":"Duff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brian","family":"Vinter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,9]]},"reference":[{"issue":"1","key":"45_CR1","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1142\/S0129053389000056","volume":"1","author":"E Anderson","year":"1989","unstructured":"Anderson, E., Saad, Y.: Solving sparse triangular linear systems on parallel computers. Int. J. High Speed Comput. 1(1), 73\u201395 (1989)","journal-title":"Int. J. High Speed Comput."},{"key":"45_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/978-3-662-48096-0_50","volume-title":"Euro-Par 2015: Parallel Processing","author":"H Anzt","year":"2015","unstructured":"Anzt, H., Chow, E., Dongarra, J.: Iterative sparse triangular solves for preconditioning. In: Tr\u00e4ff, J.L., Hunold, S., Versaci, F. (eds.) Euro-Par 2015. LNCS, vol. 9233, pp. 650\u2013661. Springer, Heidelberg (2015)"},{"key":"45_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484","volume-title":"Numerical Methods for Least Squares Problems","author":"\u00c5 Bj\u00f6rck","year":"1996","unstructured":"Bj\u00f6rck, \u00c5.: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics, Philadelphia (1996)"},{"issue":"2","key":"45_CR4","doi-asserted-by":"publisher","first-page":"C169","DOI":"10.1137\/140968896","volume":"37","author":"E Chow","year":"2015","unstructured":"Chow, E., Patel, A.: Fine-grained parallel incomplete LU factorization. SIAM J. Sci. Comput. 37(2), C169\u2013C193 (2015)","journal-title":"SIAM J. Sci. Comput."},{"key":"45_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881","volume-title":"Direct Methods for Sparse Linear Systems","author":"T Davis","year":"2006","unstructured":"Davis, T.: Direct Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia (2006)"},{"issue":"1","key":"45_CR6","first-page":"1:1","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1:1\u20131:25 (2011)","journal-title":"ACM Trans. Math. Softw."},{"key":"45_CR7","volume-title":"Direct Methods for Sparse Matrices","author":"IS Duff","year":"1986","unstructured":"Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Oxford University Press Inc., New York (1986)"},{"issue":"2","key":"45_CR8","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1145\/567806.567810","volume":"28","author":"IS Duff","year":"2002","unstructured":"Duff, I.S., Heroux, M.A., Pozo, R.: An overview of the sparse basic linear algebra subprograms: the new standard from the BLAS Technical forum. ACM Trans. Math. Softw. 28(2), 239\u2013267 (2002)","journal-title":"ACM Trans. Math. Softw."},{"issue":"3","key":"45_CR9","doi-asserted-by":"publisher","first-page":"C303","DOI":"10.1137\/12088358X","volume":"35","author":"JD Hogg","year":"2013","unstructured":"Hogg, J.D.: A fast dense triangular solve in CUDA. SIAM J. Sci. Comput. 35(3), C303\u2013C322 (2013)","journal-title":"SIAM J. Sci. Comput."},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Kabir, H., Booth, J.D., Aupy, G., Benoit, A., Robert, Y., Raghavan, P.: STS-k: a multilevel sparse triangular solution scheme for NUMA multicores. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2015, pp. 55:1\u201355:11 (2015)","DOI":"10.1145\/2807591.2807667"},{"key":"45_CR11","doi-asserted-by":"crossref","unstructured":"Li, A., van den Braak, G.J., Corporaal, H., Kumar, A.: Fine-grained synchronizations and dataflow programming on GPUs. In: Proceedings of the 29th ACM on International Conference on Supercomputing, ICS 2015, pp. 109\u2013118 (2015)","DOI":"10.1145\/2751205.2751232"},{"issue":"2","key":"45_CR12","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s11227-012-0825-3","volume":"63","author":"R Li","year":"2013","unstructured":"Li, R., Saad, Y.: GPU-accelerated preconditioned iterative linear solvers. J. Supercomputing 63(2), 443\u2013466 (2013)","journal-title":"J. Supercomputing"},{"key":"45_CR13","doi-asserted-by":"crossref","unstructured":"Liang, C.K., Prvulovic, M.: MiSAR: minimalistic synchronization accelerator with resource overflow management. In: Proceedings of the 42nd Annual International Symposium on Computer Architecture, ISCA 2015, pp. 414\u2013426 (2015)","DOI":"10.1145\/2749469.2750396"},{"key":"45_CR14","unstructured":"Liu, W.: Parallel and Scalable Sparse Basic Linear Algebra Subprograms. Ph.D. Thesis, University of Copenhagen (2015)"},{"key":"45_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jpdc.2015.06.010","volume":"85","author":"W Liu","year":"2015","unstructured":"Liu, W., Vinter, B.: A framework for general sparse matrix-matrix multiplication on GPUs and heterogeneous processors. J. Parallel Distrib. Comput. 85, 47\u201361 (2015)","journal-title":"J. Parallel Distrib. Comput."},{"key":"45_CR16","doi-asserted-by":"crossref","unstructured":"Liu, W., Vinter, B.: CSR5: an efficient storage format for cross-platform sparse matrix-vector multiplication. In: Proceedings of the 29th ACM International Conference on Supercomputing, ICS 2015, pp. 339\u2013350 (2015)","DOI":"10.1145\/2751205.2751209"},{"key":"45_CR17","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.parco.2015.04.004","volume":"49","author":"W Liu","year":"2015","unstructured":"Liu, W., Vinter, B.: Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processors. Parallel Comput. 49, 179\u2013193 (2015)","journal-title":"Parallel Comput."},{"issue":"4","key":"45_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00607-009-0066-3","volume":"86","author":"J Mayer","year":"2009","unstructured":"Mayer, J.: Parallel algorithms for solving linear systems with sparse triangular matrices. Computing 86(4), 291\u2013312 (2009)","journal-title":"Computing"},{"key":"45_CR19","unstructured":"Naumov, M.: Parallel Solution of Sparse Triangular Linear Systems in the Preconditioned Iterative Methods on the GPU. Technical report NVIDIA (2011)"},{"key":"45_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-319-07518-1_8","volume-title":"Supercomputing","author":"J Park","year":"2014","unstructured":"Park, J., Smelyanskiy, M., Sundaram, N., Dubey, P.: Sparsifying synchronization for high-performance shared-memory sparse triangular solver. In: Kunkel, J.M., Ludwig, T., Meuer, H.W. (eds.) ISC 2014. LNCS, vol. 8488, pp. 124\u2013140. Springer, Heidelberg (2014)"},{"key":"45_CR21","doi-asserted-by":"crossref","unstructured":"Ros, A., Kaxiras, S.: Callback: efficient synchronization without invalidation with a directory just for spin-waiting. In: Proceedings of the 42nd Annual International Symposium on Computer Architecture, ISCA 2015, pp. 427\u2013438 (2015)","DOI":"10.1145\/2749469.2750405"},{"key":"45_CR22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Y Saad","year":"2003","unstructured":"Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2003)","edition":"2"},{"issue":"1","key":"45_CR23","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1137\/0911008","volume":"11","author":"JH Saltz","year":"1990","unstructured":"Saltz, J.H.: Aggregation methods for solving sparse triangular systems on multiprocessors. SIAM J. Sci. Stat. Comput. 11(1), 123\u2013144 (1990)","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"45_CR24","unstructured":"Schreiber, R., Tang, W.P.: Vectorizing the Conjugate Gradient Method. In: Proceedings of the Symposium on CYBER 205 Applications (1982)"},{"key":"45_CR25","doi-asserted-by":"crossref","unstructured":"Scogland, T.R., Feng, W.C.: Design and evaluation of scalable concurrent queues for many-core architectures. In: Proceedings of the 6th ACM\/SPEC International Conference on Performance Engineering, ICPE 2015, pp. 63\u201374 (2015)","DOI":"10.1145\/2668930.2688048"},{"key":"45_CR26","doi-asserted-by":"crossref","unstructured":"Suchoski, B., Severn, C., Shantharam, M., Raghavan, P.: Adapting sparse triangular solution to GPUs. In: Proceedings of the 2012 41st International Conference on Parallel Processing Workshops, ICPPW 2012, pp. 140\u2013148 (2012)","DOI":"10.1109\/ICPPW.2012.23"},{"key":"45_CR27","doi-asserted-by":"crossref","unstructured":"Wang, H., Liu, W., Hou, K., Feng, W.C.: Parallel Transposition of Sparse Data Structures. In: Proceedings of the 30th ACM International Conference on Supercomputing, ICS 2016 (2016)","DOI":"10.1145\/2925426.2926291"},{"key":"45_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-19328-6_6","volume-title":"High Performance Computing for Computational Science \u2013 VECPAR 2010","author":"MM Wolf","year":"2011","unstructured":"Wolf, M.M., Heroux, M.A., Boman, E.G.: Factors impacting performance of multithreaded sparse triangular solve. In: Palma, J.M.L.M., Dayd\u00e9, M., Marques, O., Lopes, J.C. (eds.) VECPAR 2010. LNCS, vol. 6449, pp. 32\u201344. Springer, Heidelberg (2011)"},{"key":"45_CR29","doi-asserted-by":"crossref","unstructured":"Xiao, S., Feng, W.C.: Inter-block GPU Communication via fast barrier synchronization. In: 2010 IEEE International Symposium on Parallel Distributed Processing, IPDPS 2010, pp. 1\u201312 (2010)","DOI":"10.1109\/IPDPS.2010.5470477"},{"key":"45_CR30","doi-asserted-by":"crossref","unstructured":"Yan, S., Long, G., Zhang, Y.: StreamScan: fast scan algorithms for GPUs without global barrier synchronization. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPopp. 2013, pp. 229\u2013238 (2013)","DOI":"10.1145\/2517327.2442539"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2016: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-43659-3_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T15:58:03Z","timestamp":1749052683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-43659-3_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319436586","9783319436593"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-43659-3_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Euro-Par","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Grenoble","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"europar2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/europar2016.inria.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}