Numerical algorithms
Scope: Numerical analysis underlies all numerical computation in any application areas. Algorithms are given a particular focus to understand how exascale impacts technologies. EESI2 studies the following technologies:
- Dense linear algebra
- Graph partitioning
- Sparse direct methods
- Iterative methods
- Eigenvalue problems
- Optimization & control
- Structured & unstructured grids
- Monte Carlo
- Tensors
- Fast Multipole Methods
Challenges:
Memory access is a major bottleneck in computations. Therefore algorithms need to maximise the number of useful calculations per memory access. Scheduling methods, memory affinity schemes, load balancing methods, are challenged.
A lot of overheads is generated by load-balancing, synchronisation, communication or fault tolerance mechanisms, that hinders the path toward exascale.
Additionally, some technologies solve issues but create new problems, eg stability of the overall system, overhead of asynchronous methods. For example, data structures using octree features face irregular computation patterns with load-balancing issues.
New applications, such as Big Data, or low rank approximations and compression methods require to adapt methods to matrix structures.
Path:
Memory issues can be tackled by using blocking/tiling and communication hiding methods.
Some overheads can be addressed by expressing computations at multiple levels of abstraction as task graphs and making use of data-driven schedulers.
Algorithms based on modular frameworks can be scalable to support alternative scheduling, load-balancing methods or memory affinity schemes.
Asynchronous/chaotic relaxation methods offer better use of parallelisation.
Most of issues require to address the trade off between speed, accuracy and reproducibility, the impact of fault tolerance on algorithm design and uncertainty quantification
Application auto-tuning will become a trivial feature.