{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/50516"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/50516","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling","abstract":"With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run on these machines will have to adapt to this new landscape. In this dissertation, we focus on algebraic multigrid (AMG), a popular linear solver with many scientific and engineering applications. AMG has the attractive property of requiring work that is linear in the number of unknowns. However, it also has substantial communication requirements that impede its scalability on emerging architectures. In our treatment of AMG, we make heavy use of performance modeling, developing a methodology we like to call, ``applied performance modeling,'' that drives how we analyze and adjust AMG to improve its performance and scalability. The fundamental idea is that straightforward performance models can be used to analyze applications and architectures and draw startlingly powerful conclusions about them. We develop such models for AMG and use them to explain performance difficulties on emerging machines, analyze a large body of past work in adapting multigrid methods to massively parallel machines, and then perform a pair of practical tasks: guiding an algorithm that redistributes data to trade communication for computation, and informing the selection of thread/task mixes when using a hybrid programming model. Our performance models accurately predict the performance of the AMG solve cycle on multiple platforms, capturing the application and architectural features behind the observed performance, and are easily extended to cover new platforms and AMG algorithms. The model-guided data redistribution yields significant improvements, and the suggestions provided for thread/task mixes enable users to avoid selecting ones that would perform poorly. We are encouraged by our results so far, and expect our work to be of continued use to AMG and to other applications in the future.","abstract_html":"With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run on these machines will have to adapt to this new landscape. In this dissertation, we focus on algebraic multigrid (AMG), a popular linear solver with many scientific and engineering applications. AMG has the attractive property of requiring work that is linear in the number of unknowns. However, it also has substantial communication requirements that impede its scalability on emerging architectures. In our treatment of AMG, we make heavy use of performance modeling, developing a methodology we like to call, ``applied performance modeling,'' that drives how we analyze and adjust AMG to improve its performance and scalability. The fundamental idea is that straightforward performance models can be used to analyze applications and architectures and draw startlingly powerful conclusions about them. We develop such models for AMG and use them to explain performance difficulties on emerging machines, analyze a large body of past work in adapting multigrid methods to massively parallel machines, and then perform a pair of practical tasks: guiding an algorithm that redistributes data to trade communication for computation, and informing the selection of thread/task mixes when using a hybrid programming model. Our performance models accurately predict the performance of the AMG solve cycle on multiple platforms, capturing the application and architectural features behind the observed performance, and are easily extended to cover new platforms and AMG algorithms. The model-guided data redistribution yields significant improvements, and the suggestions provided for thread/task mixes enable users to avoid selecting ones that would perform poorly. We are encouraged by our results so far, and expect our work to be of continued use to AMG and to other applications in the future.","abstract_has_math":false,"creators":["Gahvari, Hormozd"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Gropp, William D.","Heath, Michael T.","Olson, Luke N.","Vanka, Surya Pratap","Yang, Ulrike M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-09-16T17:23:17Z","date_published":"2014-09-16T17:23:17Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Algebraic Multigrid","Performance Modeling","Massively Parallel Architectures"],"languages":["en"],"rights":["Copyright 2014 Hormozd Gahvari"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/50516","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Gropp, William D.","Heath, Michael T.","Olson, Luke N.","Vanka, Surya Pratap","Yang, Ulrike M."]},{"key":"dc:creator","label":"Author","values":["Gahvari, Hormozd"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-09-16T17:23:17Z","2014-08","2014-09-16"]},{"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":["Algebraic Multigrid","Performance Modeling","Massively Parallel Architectures"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Hormozd Gahvari"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/50516"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run on these machines will have to adapt to this new landscape. In this dissertation, we focus on algebraic multigrid (AMG), a popular linear solver with many scientific and engineering applications. AMG has the attractive property of requiring work that is linear in the number of unknowns. However, it also has substantial communication requirements that impede its scalability on emerging architectures. In our treatment of AMG, we make heavy use of performance modeling, developing a methodology we like to call, ``applied performance modeling,'' that drives how we analyze and adjust AMG to improve its performance and scalability. The fundamental idea is that straightforward performance models can be used to analyze applications and architectures and draw startlingly powerful conclusions about them. We develop such models for AMG and use them to explain performance difficulties on emerging machines, analyze a large body of past work in adapting multigrid methods to massively parallel machines, and then perform a pair of practical tasks: guiding an algorithm that redistributes data to trade communication for computation, and informing the selection of thread/task mixes when using a hybrid programming model. Our performance models accurately predict the performance of the AMG solve cycle on multiple platforms, capturing the application and architectural features behind the observed performance, and are easily extended to cover new platforms and AMG algorithms. The model-guided data redistribution yields significant improvements, and the suggestions provided for thread/task mixes enable users to avoid selecting ones that would perform poorly. We are encouraged by our results so far, and expect our work to be of continued use to AMG and to other applications in the future.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-10T18:23:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Gahvari_Hormozd.pdf: 2223628 bytes, checksum: 5c5e4f67967ba3964661d8ad4c967b34 (MD5)","Made available in DSpace on 2014-09-16T17:23:17Z (GMT). No. of bitstreams: 2 Hormozd_Gahvari.pdf: 2223592 bytes, checksum: a093157ce0fc6f5da9cf82a9b1618cec (MD5) license.txt: 4064 bytes, checksum: 248a667a859208e54fdba763951d923d (MD5)"]},{"key":"dc:title","label":"Title","values":["Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling"]}]}],"canonical_facts":{"dc:contributor":["Gropp, William D.","Heath, Michael T.","Olson, Luke N.","Vanka, Surya Pratap","Yang, Ulrike M."],"dc:creator":["Gahvari, Hormozd"],"dc:date":["2014-09-16T17:23:17Z","2014-08","2014-09-16"],"dc:description":["With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run on these machines will have to adapt to this new landscape. In this dissertation, we focus on algebraic multigrid (AMG), a popular linear solver with many scientific and engineering applications. AMG has the attractive property of requiring work that is linear in the number of unknowns. However, it also has substantial communication requirements that impede its scalability on emerging architectures. In our treatment of AMG, we make heavy use of performance modeling, developing a methodology we like to call, ``applied performance modeling,'' that drives how we analyze and adjust AMG to improve its performance and scalability. The fundamental idea is that straightforward performance models can be used to analyze applications and architectures and draw startlingly powerful conclusions about them. We develop such models for AMG and use them to explain performance difficulties on emerging machines, analyze a large body of past work in adapting multigrid methods to massively parallel machines, and then perform a pair of practical tasks: guiding an algorithm that redistributes data to trade communication for computation, and informing the selection of thread/task mixes when using a hybrid programming model. Our performance models accurately predict the performance of the AMG solve cycle on multiple platforms, capturing the application and architectural features behind the observed performance, and are easily extended to cover new platforms and AMG algorithms. The model-guided data redistribution yields significant improvements, and the suggestions provided for thread/task mixes enable users to avoid selecting ones that would perform poorly. We are encouraged by our results so far, and expect our work to be of continued use to AMG and to other applications in the future.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-10T18:23:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Gahvari_Hormozd.pdf: 2223628 bytes, checksum: 5c5e4f67967ba3964661d8ad4c967b34 (MD5)","Made available in DSpace on 2014-09-16T17:23:17Z (GMT). No. of bitstreams: 2 Hormozd_Gahvari.pdf: 2223592 bytes, checksum: a093157ce0fc6f5da9cf82a9b1618cec (MD5) license.txt: 4064 bytes, checksum: 248a667a859208e54fdba763951d923d (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/50516"],"dc:language":["en"],"dc:rights":["Copyright 2014 Hormozd Gahvari"],"dc:subject":["Algebraic Multigrid","Performance Modeling","Massively Parallel Architectures"],"dc:title":["Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling"],"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:25:40Z"}