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.

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, biomedicine, the behaviour of human social interaction networks, nuclear fusion, materials science and computational chemistry as well as the specific exemplars of this project. Meanwhile, the ability of high performance computing (HPC) to address complex systems with increasingly high fidelity means that its impact is growing rapidly, not just within academia but also within government and industry. 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. The outputs of this project have the potential to make a step change in the scalability of the numerical methods, thus enabling their use on very high numbers of processors, and in turn impacting all the above areas by enabling more accurate and faster prediction, simulation, or diagnosis. An important output of the research facilitated by the network is software. Library products such as LAPACK and NAG are widely used across diverse industries and application areas, including in finance, pharmaceuticals, visualization, earth sciences, and engineering, and on a wide range of machines. The software outputs of this project are therefore of great value to the knowledge economy. The ability to model bone with the degree of resolution proposed here is of enormous interest to both the academic and non-academic communities. In particular, the technology will be of interest to orthopaedic and dental companies who are developing new medical devices. At present these are developed (with a significant degree of trial and error) by simple tests in the laboratory, followed by sample tests in small animals, implant tests in larger animals and eventually clinical trials in humans. The length of time, effort and cost involved in this whole process are very significant, and yet there are still cases where implants have failed in humans after passing the pre-clinical trials. More detailed in silico testing will reduce development time, cost and use of animals. High resolution bone modelling tools will also be of interest to clinician's managing other conditions, for example, osteoporosis or craniosynostosis, allowing them to predict risks and likely outcomes, and optimum treatment plans. It will of course also be relevant to users outside the medical sphere---for example biologists and palaeontologists, who could use it for many other applications regarding bone and and skeletal development. Development and application of SmartGrids, including smart meters and electrical vehicles, is of a great importance if the UK and other countries are to achieve significant carbon emission reductions and realize sustainable energy systems. These new grids will offer the opportunity to increase the level of renewable energy integrated into the grid. They will also allow customers, including small households, to actively participate and adjust their demand depending on energy availability and price. the new software developed through this project will open a possibility for businesses and policy makers to revisit this and investigate whether more centralized operation over larger system areas will be more beneficial. This will further enable more accurate price signal calculations and bring the possibility to define policies which will ensure better engagement with customers to reduce their energy consumption or shift it towards off-peak periods. It will also allow for better coordination of charging of electric vehicles and their use as storage devices that can also provide energy.