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

AF:Small：在多核架构上启用导数计算的组合算法

• 批准号: 1218916
• 负责人: Alex Pothen
• 金额: $ 30万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218916&HistoricalAwards=false
• 关键词: AF; Small; Combinatorial; Algorithms; Enable

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.

计算科学和工程的许多领域都需要导数，包括非线性优化和非线性微分方程的算法。该项目针对当前最先进的计算导数技术、自动微分（AD）及其对多核架构的适应。这项工作的算法和软件将对高性能计算和计算科学与工程社区有用。 AD技术的进步将直接有助于改进不确定性量化和敏感性分析方法，这两者在国家利益科学应用的高保真预测计算机模拟中发挥着至关重要的作用。基于该项目部分内容的模块将包含在合适的研究生课程中。作为该项目的一部分，主要研究人员将访问印第安纳州的一所四年制本科学院并举办研讨会来描述这项研究，以激励学生攻读科学和工程领域的研究生。自动（或算法）微分 (AD) 是一项现代技术，对于准确有效地评估导数而言越来越重要，但它会产生许多组合问题，仍有待找到有效的算法来解决。多核计算平台通过为桌面带来强大的计算能力，只要配备合适的支持算法和软件，就能很好地加速科学和工程领域的创新和发现。该项目专注于通用组合抽象，旨在加速基本 AD 算法和在多核平台上实现导数计算所需的算法的进展。具体目标是：(1) 开发基于图的对称性利用模型和算法，通过 AD 高效计算 Hessian 矩阵；(2) 开发组合算法，支持在多核架构上使用 AD 高效计算大型、稀疏 Jacobian 和 Hessian 矩阵；(3) 开发多核不规则计算中并发发现的组合算法 架构。 许多目标组合问题都是 NP 难题，难以最优解决，因此将强调产生接近最优解决方案的快速算法。为了确保算法在快速发展的多核平台上正确、可靠、可扩展地运行，需要特别关注编程模型、算法和数据结构设计以及内存管理。合适的大规模非线性优化问题将用于指导算法开发工作并作为展示影响的工具。