AF:Small: Combinatorial Algorithms to Enable Derivative Computations on Multicore Architectures

点击翻译按钮获取中文摘要

Derivatives are required in numerous contexts in computational science and engineering, including in algorithms for nonlinear optimization and nonlinear differential equations. This project targets the current state-of-the-art technology for computing derivatives, Automatic Differentiation (AD), and its adaptation to multi-core architectures. Algorithms and software from this effort will be useful to the high-performance computing and computational science and engineering communities. Advances in AD technology will directly contribute to improved methods for uncertainty quantification and sensitivity analysis, both of which play crucial roles in high-fidelity predictive computer simulations for scientific applications of national interest. Modules based on parts of this project will be included in suitable graduate courses. As part of this project, the Principle Investigators will visit and give seminars describing this research at a four-year undergraduate college in Indiana to motivate students to pursue graduate studies in science and engineering.Automatic (or Algorithmic) Differentiation (AD) is a modern technology of growing importance for evaluating derivatives accurately and efficiently, but it generates a number of combinatorial problems for which efficient algorithms remain to be found. Multi-core computing platforms, by bringing substantial computing power to the desktop, are well positioned to accelerate innovation and discovery in science and engineering, as long as they are furnished with suitable enabling algorithms and software. Focusing on general-purpose combinatorial abstractions, this project seeks to accelerate progress on both fundamental AD algorithms and those needed to enable derivative computation on multi-core platforms. The specific goals are to: (1) Develop graph-based, symmetry-exploiting models and algorithms for efficient computation of Hessians via AD, (2) Develop combinatorial algorithms to support efficient computation of large, sparse Jacobian and Hessian matrices using AD on multi-core architectures, and (3) Develop combinatorial algorithms for concurrency discovery in irregular computations on multi-core architectures. Many of the targeted combinatorial problems are NP-hard to solve optimally, and fast algorithms that yield near-optimal solutions will be emphasized. To ensure that the algorithms would run correctly, reliably and in a scalable manner on the rapidly evolving multi-core platforms, careful attention will be paid to programming models, algorithm and data structure design, and memory management. Suitable large-scale nonlinear optimization problems will be used to guide the algorithm development effort and as a vehicle for demonstrating impact.