Novel Asynchronous Algorithms and Software for Large Sparse Systems

求解大型线性和非线性稀疏系统是计算科学和工程许多领域的关键数值技术，包括气候和环境建模、核聚变、材料科学和计算化学。这些和其他应用领域对稀疏系统解决方案的依赖意味着它们在实现极端可伸缩性方面都面临困难，因为底层算法是高度同步的。该项目旨在通过使用异步迭代算法开发更具可扩展性的数值方法。在异步迭代中，更新解决方案组件的顺序是任意的，更新中使用的组件的过去值也是任意选择的。这是一种并行计算模型，其中不同的处理器独立工作，并且可以访问本地内存中的数据值。在异构计算环境中处理容错、负载平衡和通信开销对软件开发来说是一项具有挑战性的任务。在传统的同步算法中，每次迭代只能在最慢的处理器允许的情况下执行。如果处理器出现故障，或者功能较差，或者负载过重，那么这将显著影响迭代时间。使用异步方法可以克服我们现在面临的许多通信、负载平衡和容错问题，这些问题限制了我们扩展到极限的能力。这个项目的一个重要特征是在算法和软件的整个开发过程中与两个范例应用程序的需求紧密耦合，以及在这些应用程序中对原型的部署和测试。其应用是骨科和牙科植入物的设计优化以及电力系统中的智能电网。这两种应用程序都需要改进算法，以解决未来并行系统中具有挑战性的问题，并且它们呈现出具有不同特性的线性系统，从而为软件提供了有用的测试平台，并在项目期间展示了新算法的优点。

The solution of large sparse systems, both linear and nonlinear is a key numerical technology underpinning many areas of computational science and engineering, including climate and environmental modelling, nuclear fusion, materials science and computational chemistry. The reliance of these and other application domains on sparse system solution means that they all face difficulties in achieving extreme scalability, since the underlying algorithms are highly synchronous. This project aims to develop more scalable numerical methods through the use of asynchronous iterative algorithms. In asynchronous iterations, the order in which components of the solution are updated is arbitrary and the past values of components that are used in the updates are also selected arbitrarily. This is a model for parallel computation in which different processors work independently and have access to data values in local memory. Coping with fault tolerance, load balancing, and communication overheads in a heterogeneous computation environment is a challenging undertaking for software development. In traditional synchronous algorithms each iteration can only be performed as quickly as the slowest processor permits. If a processor fails, or is less capable, or has an unduly heavy load, then this markedly impacts on iteration times. The use of asynchronous methods allows one to overcome many of the communication, load balancing and fault tolerance issues we now face and which limit our ability to scale to the extreme.An important feature of this project is the close coupling throughout the development of algorithms and software with the needs of two exemplar applications, along with the deployment and testing of prototypes in these applications. The applications are the design optimization of orthopaedic and dental implants and SmartGrids within power systems. Both applications need improved algorithms in order to solve their challenging problems on future parallel systems and they present linear systems with different characteristics, thus providing both a useful test bed for the software and a means to demonstrate during the project the benefits of the new algorithms.