Novel Asynchronous Algorithms and Software for Large Sparse Systems

Lead Research Organisation: University of Leeds
Department Name: Sch of Computing


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.


10 25 50
Description We have developed a better understanding of the impact of asynchronous communication on a range of iterative methods for the solution of finite element discretizations. We have used this knowledge to enhance the parallel application of algebraic multigrid by substantially reducing the amount of synchronization required at the coarsest level.
Exploitation Route The development of improved software will allow the techniques to be used in a vast range of sectors and applications.
Sectors Aerospace, Defence and Marine,Energy,Healthcare,Manufacturing, including Industrial Biotechology

Description Collaboration with researchers at Hull has allowed us to develop faster and more efficient solvers for the medical engineering problems that they study. We are now seeking to extend this to a more general framework that can be picked up and used by other researchers in this application domain.
First Year Of Impact 2013
Sector Healthcare
Impact Types Societal