{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/101514"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/101514","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Reducing communication in sparse solvers","abstract":"Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication. Multiple methods are investigated throughout this dissertation for reducing the cost associated with communication throughout sparse matrix operations. Algorithmic changes reduce communication requirements, but also affect accuracy of the operation, leading to reduced convergence of scientific codes. We investigate a method of systematically removing relatively small non-zeros throughout an algebraic multigrid hierarchy, yielding significant reductions to the cost of sparse matrix-vector multiplication that outweigh affects of reduced accuracy of the multiplication. Therefore, the reduction in per-iteration communication costs outweigh the cost of extra solver iterations. As a result, sparsification yields improvement of both the performance and scalability of algebraic multigrid. Alterations to the parallel implementation of MPI communication also yield reduced costs with no effect on accuracy. We investigate methods of agglomerating messages on-node before injecting into the network, reducing the amount of costly inter-node communication. This node-aware communication yields improvements to both performance and scalability of matrix operations, particularly in strong scaling studies. Furthermore, we show an improvement in the cost of algebraic multigrid as a result of reduced communication costs in sparse matrix operations. Finally, performance models can be used to analyze the costs of matrix operations, indicating the source of dominant communication costs, such as initializing messages or transporting bytes of data. We investigate methods of improving traditional performance models of irregular point-to-point communication through the addition of node-awareness, queue search costs, and network contention penalties.","abstract_html":"Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication. Multiple methods are investigated throughout this dissertation for reducing the cost associated with communication throughout sparse matrix operations. Algorithmic changes reduce communication requirements, but also affect accuracy of the operation, leading to reduced convergence of scientific codes. We investigate a method of systematically removing relatively small non-zeros throughout an algebraic multigrid hierarchy, yielding significant reductions to the cost of sparse matrix-vector multiplication that outweigh affects of reduced accuracy of the multiplication. Therefore, the reduction in per-iteration communication costs outweigh the cost of extra solver iterations. As a result, sparsification yields improvement of both the performance and scalability of algebraic multigrid. Alterations to the parallel implementation of MPI communication also yield reduced costs with no effect on accuracy. We investigate methods of agglomerating messages on-node before injecting into the network, reducing the amount of costly inter-node communication. This node-aware communication yields improvements to both performance and scalability of matrix operations, particularly in strong scaling studies. Furthermore, we show an improvement in the cost of algebraic multigrid as a result of reduced communication costs in sparse matrix operations. Finally, performance models can be used to analyze the costs of matrix operations, indicating the source of dominant communication costs, such as initializing messages or transporting bytes of data. We investigate methods of improving traditional performance models of irregular point-to-point communication through the addition of node-awareness, queue search costs, and network contention penalties.","abstract_has_math":false,"creators":["Bienz, Amanda"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Olson, Luke N.","Gropp, William D.","Solomonik, Edgar","Grigori, Laura"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-09-27T16:17:35Z","date_published":"2018-09-27T16:17:35Z","updated_at":"2026-07-22T22:24:40Z","subjects":["Sparse solvers","Linear solvers","Parallel programming","Parallel communication","Algebraic multigrid","Performance modeling"],"languages":["en"],"rights":["Copyright 2018 Amanda Bienz"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/101514","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Olson, Luke N.","Gropp, William D.","Solomonik, Edgar","Grigori, Laura"]},{"key":"dc:creator","label":"Author","values":["Bienz, Amanda"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-09-27T16:17:35Z","2018-06-29","2018-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Sparse solvers","Linear solvers","Parallel programming","Parallel communication","Algebraic multigrid","Performance modeling"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Amanda Bienz"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/101514"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication. Multiple methods are investigated throughout this dissertation for reducing the cost associated with communication throughout sparse matrix operations. Algorithmic changes reduce communication requirements, but also affect accuracy of the operation, leading to reduced convergence of scientific codes. We investigate a method of systematically removing relatively small non-zeros throughout an algebraic multigrid hierarchy, yielding significant reductions to the cost of sparse matrix-vector multiplication that outweigh affects of reduced accuracy of the multiplication. Therefore, the reduction in per-iteration communication costs outweigh the cost of extra solver iterations. As a result, sparsification yields improvement of both the performance and scalability of algebraic multigrid. Alterations to the parallel implementation of MPI communication also yield reduced costs with no effect on accuracy. We investigate methods of agglomerating messages on-node before injecting into the network, reducing the amount of costly inter-node communication. This node-aware communication yields improvements to both performance and scalability of matrix operations, particularly in strong scaling studies. Furthermore, we show an improvement in the cost of algebraic multigrid as a result of reduced communication costs in sparse matrix operations. Finally, performance models can be used to analyze the costs of matrix operations, indicating the source of dominant communication costs, such as initializing messages or transporting bytes of data. We investigate methods of improving traditional performance models of irregular point-to-point communication through the addition of node-awareness, queue search costs, and network contention penalties.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo terms","The student, Amanda Bienz, accepted the attached license on 2018-06-28 at 17:53.","The student, Amanda Bienz, submitted this Dissertation for approval on 2018-06-28 at 17:53.","This Dissertation was approved for publication on 2018-06-29 at 10:55.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12687 on 2018-09-27 at 10:46:16","Made available in DSpace on 2018-09-27T16:17:35Z (GMT). No. of bitstreams: 3 BIENZ-DISSERTATION-2018.pdf: 2881415 bytes, checksum: 4b351f4cc6c24566b953b48782d90c45 (MD5) LICENSE.txt: 4209 bytes, checksum: f237d7bc7e3b8c5d64216699204b9777 (MD5) PROQUEST_LICENSE.txt: 4555 bytes, checksum: fb55affa9e343f19d310fb79c125c449 (MD5) Previous issue date: 2018-06-29"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Reducing communication in sparse solvers"]}]}],"canonical_facts":{"dc:contributor":["Olson, Luke N.","Gropp, William D.","Solomonik, Edgar","Grigori, Laura"],"dc:creator":["Bienz, Amanda"],"dc:date":["2018-09-27T16:17:35Z","2018-06-29","2018-08"],"dc:description":["Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication. Multiple methods are investigated throughout this dissertation for reducing the cost associated with communication throughout sparse matrix operations. Algorithmic changes reduce communication requirements, but also affect accuracy of the operation, leading to reduced convergence of scientific codes. We investigate a method of systematically removing relatively small non-zeros throughout an algebraic multigrid hierarchy, yielding significant reductions to the cost of sparse matrix-vector multiplication that outweigh affects of reduced accuracy of the multiplication. Therefore, the reduction in per-iteration communication costs outweigh the cost of extra solver iterations. As a result, sparsification yields improvement of both the performance and scalability of algebraic multigrid. Alterations to the parallel implementation of MPI communication also yield reduced costs with no effect on accuracy. We investigate methods of agglomerating messages on-node before injecting into the network, reducing the amount of costly inter-node communication. This node-aware communication yields improvements to both performance and scalability of matrix operations, particularly in strong scaling studies. Furthermore, we show an improvement in the cost of algebraic multigrid as a result of reduced communication costs in sparse matrix operations. Finally, performance models can be used to analyze the costs of matrix operations, indicating the source of dominant communication costs, such as initializing messages or transporting bytes of data. We investigate methods of improving traditional performance models of irregular point-to-point communication through the addition of node-awareness, queue search costs, and network contention penalties.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo terms","The student, Amanda Bienz, accepted the attached license on 2018-06-28 at 17:53.","The student, Amanda Bienz, submitted this Dissertation for approval on 2018-06-28 at 17:53.","This Dissertation was approved for publication on 2018-06-29 at 10:55.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12687 on 2018-09-27 at 10:46:16","Made available in DSpace on 2018-09-27T16:17:35Z (GMT). No. of bitstreams: 3 BIENZ-DISSERTATION-2018.pdf: 2881415 bytes, checksum: 4b351f4cc6c24566b953b48782d90c45 (MD5) LICENSE.txt: 4209 bytes, checksum: f237d7bc7e3b8c5d64216699204b9777 (MD5) PROQUEST_LICENSE.txt: 4555 bytes, checksum: fb55affa9e343f19d310fb79c125c449 (MD5) Previous issue date: 2018-06-29"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/101514"],"dc:language":["en"],"dc:rights":["Copyright 2018 Amanda Bienz"],"dc:subject":["Sparse solvers","Linear solvers","Parallel programming","Parallel communication","Algebraic multigrid","Performance modeling"],"dc:title":["Reducing communication in sparse solvers"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:40Z"}