Novel Asynchronous Algorithms and Software for Large Sparse Systems

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

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.