{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/106207"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/106207","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Robust structured multigrid at extreme scales","abstract":"The solution of elliptic partial differential equations is a common performance bottleneck in scientific simulations. By exploiting structure in a problem, robust structured multigrid methods gain important performance benefits because they preserve structure throughout the multigrid hierarchy. In parallel these methods benefit from nearest neighbor stencil-based communication patterns; however, the increased communication demands of coarse-grid problems and block smoothers needed for a robust solver challenge parallel efficiency. In this dissertation, methods for reducing parallel communication through changes in the parallel implementation are explored. To reduce communication costs for coarse-grid problems, recursive agglomeration of tasks on a logically structured grid of processors is considered. This communication is optimized using a predictive performance model to guide how tasks are agglomerated. This approach provides an efficient strategy for parallel coarsening in a structured setting that can adapt to changes in the target architecture or multigrid algorithm through its incorporation in the performance model. Parallel results show favorable weak scaling using this strategy out to \\(500\\)k cores and consistency of the performance model in quantifying the cost of various redistribution decisions. To reduce communication costs in block smoothers, an automated strategy for aggregating communication across blocks is considered. With minor changes to a block solver due to the introduction of a service abstraction layer, user-level threads are used to execute blocks concurrently so communication can be aggregated. This results in a reduction in the amount of messages sent during a block smoothing operation. This strategy is demonstrated in plane smoothing to extend the strong scaling limit by reducing communication latency costs. Parallel results demonstrate scalable multilevel relaxation with \\(\\log p\\) communication complexity and plane relaxation with automated communication aggregation that doubles the strong scaling performance of a V-cycle. Lastly, the application of robust structured solvers to emerging heterogeneous architectures is considered. Benchmarks are used to develop a performance expectation for structured matrix-based operations on each target processing unit. OpenMP with unified memory is then used to offload solve phase operations in the open-source, structured variational multigrid solver Cedar. The performance expectation is then used to provide context for performance gains by targeting GPUs on Sierra---a current Power9 system at Lawrence Livermore National Laboratory. Results show speedup of a Cedar V-cycle targeting a V100 GPU over a Power9 CPU consistent with an approximate speedup estimated by comparing achievable memory bandwidth on each processing unit.","abstract_html":"The solution of elliptic partial differential equations is a common performance bottleneck in scientific simulations. By exploiting structure in a problem, robust structured multigrid methods gain important performance benefits because they preserve structure throughout the multigrid hierarchy. In parallel these methods benefit from nearest neighbor stencil-based communication patterns; however, the increased communication demands of coarse-grid problems and block smoothers needed for a robust solver challenge parallel efficiency. In this dissertation, methods for reducing parallel communication through changes in the parallel implementation are explored. To reduce communication costs for coarse-grid problems, recursive agglomeration of tasks on a logically structured grid of processors is considered. This communication is optimized using a predictive performance model to guide how tasks are agglomerated. This approach provides an efficient strategy for parallel coarsening in a structured setting that can adapt to changes in the target architecture or multigrid algorithm through its incorporation in the performance model. Parallel results show favorable weak scaling using this strategy out to \\(500\\)k cores and consistency of the performance model in quantifying the cost of various redistribution decisions. To reduce communication costs in block smoothers, an automated strategy for aggregating communication across blocks is considered. With minor changes to a block solver due to the introduction of a service abstraction layer, user-level threads are used to execute blocks concurrently so communication can be aggregated. This results in a reduction in the amount of messages sent during a block smoothing operation. This strategy is demonstrated in plane smoothing to extend the strong scaling limit by reducing communication latency costs. Parallel results demonstrate scalable multilevel relaxation with \\(\\log p\\) communication complexity and plane relaxation with automated communication aggregation that doubles the strong scaling performance of a V-cycle. Lastly, the application of robust structured solvers to emerging heterogeneous architectures is considered. Benchmarks are used to develop a performance expectation for structured matrix-based operations on each target processing unit. OpenMP with unified memory is then used to offload solve phase operations in the open-source, structured variational multigrid solver Cedar. The performance expectation is then used to provide context for performance gains by targeting GPUs on Sierra---a current Power9 system at Lawrence Livermore National Laboratory. Results show speedup of a Cedar V-cycle targeting a V100 GPU over a Power9 CPU consistent with an approximate speedup estimated by comparing achievable memory bandwidth on each processing unit.","abstract_has_math":true,"creators":["Reisner, Andrew"],"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","Moulton, David","Gropp, William","Kloeckner, Andreas"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-03-02T21:58:15Z","date_published":"2020-03-02T21:58:15Z","updated_at":"2026-07-22T22:24:45Z","subjects":["Parallel Computing","Multigrid","Solvers","Iterative Methods","High Performance Computing"],"languages":["en"],"rights":["Copyright 2019 Andrew Reisner"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/106207","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Olson, Luke","Moulton, David","Gropp, William","Kloeckner, Andreas"]},{"key":"dc:creator","label":"Author","values":["Reisner, Andrew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-03-02T21:58:15Z","2019-11-25","2019-12"]},{"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":["Parallel Computing","Multigrid","Solvers","Iterative Methods","High Performance Computing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Andrew Reisner"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/106207"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The solution of elliptic partial differential equations is a common performance bottleneck in scientific simulations. By exploiting structure in a problem, robust structured multigrid methods gain important performance benefits because they preserve structure throughout the multigrid hierarchy. In parallel these methods benefit from nearest neighbor stencil-based communication patterns; however, the increased communication demands of coarse-grid problems and block smoothers needed for a robust solver challenge parallel efficiency. In this dissertation, methods for reducing parallel communication through changes in the parallel implementation are explored. To reduce communication costs for coarse-grid problems, recursive agglomeration of tasks on a logically structured grid of processors is considered. This communication is optimized using a predictive performance model to guide how tasks are agglomerated. This approach provides an efficient strategy for parallel coarsening in a structured setting that can adapt to changes in the target architecture or multigrid algorithm through its incorporation in the performance model. Parallel results show favorable weak scaling using this strategy out to \\(500\\)k cores and consistency of the performance model in quantifying the cost of various redistribution decisions. To reduce communication costs in block smoothers, an automated strategy for aggregating communication across blocks is considered. With minor changes to a block solver due to the introduction of a service abstraction layer, user-level threads are used to execute blocks concurrently so communication can be aggregated. This results in a reduction in the amount of messages sent during a block smoothing operation. This strategy is demonstrated in plane smoothing to extend the strong scaling limit by reducing communication latency costs. Parallel results demonstrate scalable multilevel relaxation with \\(\\log p\\) communication complexity and plane relaxation with automated communication aggregation that doubles the strong scaling performance of a V-cycle. Lastly, the application of robust structured solvers to emerging heterogeneous architectures is considered. Benchmarks are used to develop a performance expectation for structured matrix-based operations on each target processing unit. OpenMP with unified memory is then used to offload solve phase operations in the open-source, structured variational multigrid solver Cedar. The performance expectation is then used to provide context for performance gains by targeting GPUs on Sierra---a current Power9 system at Lawrence Livermore National Laboratory. Results show speedup of a Cedar V-cycle targeting a V100 GPU over a Power9 CPU consistent with an approximate speedup estimated by comparing achievable memory bandwidth on each processing unit.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Andrew Reisner, accepted the attached license on 2019-11-22 at 17:01.","The student, Andrew Reisner, submitted this Dissertation for approval on 2019-11-22 at 17:09.","This Dissertation was approved for publication on 2019-11-25 at 14:35.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14596 on 2020-02-28 at 17:14:05","Made available in DSpace on 2020-03-02T21:58:15Z (GMT). No. of bitstreams: 3 REISNER-DISSERTATION-2019.pdf: 2501130 bytes, checksum: 52af5efa63fdaffa6f22bab6a0f6a042 (MD5) LICENSE.txt: 4211 bytes, checksum: 74cd8801e2d45528fc50fadf11d4188e (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: fab0b5da381dd85bb4fca02688ecdcd5 (MD5) Previous issue date: 2019-11-25"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Robust structured multigrid at extreme scales"]}]}],"canonical_facts":{"dc:contributor":["Olson, Luke","Moulton, David","Gropp, William","Kloeckner, Andreas"],"dc:creator":["Reisner, Andrew"],"dc:date":["2020-03-02T21:58:15Z","2019-11-25","2019-12"],"dc:description":["The solution of elliptic partial differential equations is a common performance bottleneck in scientific simulations. By exploiting structure in a problem, robust structured multigrid methods gain important performance benefits because they preserve structure throughout the multigrid hierarchy. In parallel these methods benefit from nearest neighbor stencil-based communication patterns; however, the increased communication demands of coarse-grid problems and block smoothers needed for a robust solver challenge parallel efficiency. In this dissertation, methods for reducing parallel communication through changes in the parallel implementation are explored. To reduce communication costs for coarse-grid problems, recursive agglomeration of tasks on a logically structured grid of processors is considered. This communication is optimized using a predictive performance model to guide how tasks are agglomerated. This approach provides an efficient strategy for parallel coarsening in a structured setting that can adapt to changes in the target architecture or multigrid algorithm through its incorporation in the performance model. Parallel results show favorable weak scaling using this strategy out to \\(500\\)k cores and consistency of the performance model in quantifying the cost of various redistribution decisions. To reduce communication costs in block smoothers, an automated strategy for aggregating communication across blocks is considered. With minor changes to a block solver due to the introduction of a service abstraction layer, user-level threads are used to execute blocks concurrently so communication can be aggregated. This results in a reduction in the amount of messages sent during a block smoothing operation. This strategy is demonstrated in plane smoothing to extend the strong scaling limit by reducing communication latency costs. Parallel results demonstrate scalable multilevel relaxation with \\(\\log p\\) communication complexity and plane relaxation with automated communication aggregation that doubles the strong scaling performance of a V-cycle. Lastly, the application of robust structured solvers to emerging heterogeneous architectures is considered. Benchmarks are used to develop a performance expectation for structured matrix-based operations on each target processing unit. OpenMP with unified memory is then used to offload solve phase operations in the open-source, structured variational multigrid solver Cedar. The performance expectation is then used to provide context for performance gains by targeting GPUs on Sierra---a current Power9 system at Lawrence Livermore National Laboratory. Results show speedup of a Cedar V-cycle targeting a V100 GPU over a Power9 CPU consistent with an approximate speedup estimated by comparing achievable memory bandwidth on each processing unit.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Andrew Reisner, accepted the attached license on 2019-11-22 at 17:01.","The student, Andrew Reisner, submitted this Dissertation for approval on 2019-11-22 at 17:09.","This Dissertation was approved for publication on 2019-11-25 at 14:35.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14596 on 2020-02-28 at 17:14:05","Made available in DSpace on 2020-03-02T21:58:15Z (GMT). No. of bitstreams: 3 REISNER-DISSERTATION-2019.pdf: 2501130 bytes, checksum: 52af5efa63fdaffa6f22bab6a0f6a042 (MD5) LICENSE.txt: 4211 bytes, checksum: 74cd8801e2d45528fc50fadf11d4188e (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: fab0b5da381dd85bb4fca02688ecdcd5 (MD5) Previous issue date: 2019-11-25"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/106207"],"dc:language":["en"],"dc:rights":["Copyright 2019 Andrew Reisner"],"dc:subject":["Parallel Computing","Multigrid","Solvers","Iterative Methods","High Performance Computing"],"dc:title":["Robust structured multigrid at extreme scales"],"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:45Z"}