OAC Core: Small: Architecture and Network-aware Partitioning Algorithms for Scalable PDE Solvers

University Of Utah, Salt Lake City UT

Investigators

Abstract

Solving large-scale partial differential equations (PDE) is common in science and engineering, from studying gravitational waves to designing aerodynamic cars. Given the scale of these problems, solving such PDEs requires supercomputing resources. The latest supercomputing architectures are different from the previous generation of leadership class architectures and and are characterized by high levels of diversity within and across machines. Such diversity and heterogeneity makes it extremely difficult to effectively distribute work, i.e., partition the data or tasks, across disparate computing resources. Since the primary objective of building leadership class machines is to further scientific discovery and national prosperity, it is essential that applications, old and new, are able to scale and utilize these machines to their full potential. This project develops novel data and task partitioning algorithms that factor in the architectural characteristics of modern supercomputers to enable efficient and scalable utilization of current and future computing architectures. Existing data and task partitioning schemes do not explicitly consider the underlying architectural topology while partitioning or is done indirectly during the design of the algorithm and codes. Ignoring topology leads to loss of scalability and performance, while shifting the burden to algorithm/code design increases the development costs and complexity, and decreases portability. While data and task partitioning for parallelization, along with mapping the partitions to processes, have been studied for a long time, they have not been considered as a combined problem. To a large extent this was due to the simple structures and symmetry that existed in cluster computing architectures. Inefficiencies that did not significantly impact performance and scalability ten years ago are starting to inhibit scalability and thereby scientific discovery. This project is a first step in ensuring that scientific discovery is not hampered as a result of the difficulty in porting codes to new architectures. This project develops new graph and space-filling-curve-based partitioning algorithms that are aware of the architectural topology and are able to automatically generate data/task partitions and mappings to address problems with current schemes. The algorithms and software developed as part of this proposal will have wide-ranging impact, by improving the performance and scalability of legacy applications and reducing the development cost and improving the portability of new applications, to run efficiently on systems ranging from simple shared memory architectures to the largest heterogeneous clusters. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.