Sparsely thinking of 2021

A selection of research on numerical analysis, mathematical optimisation, and hardware accelerators published in the past year

en , Parallel computing , Linear algebra , Numerical analysis , Mathematical optimisation · 22 Dec 2021

nice-header A wordcloud from the publications of 2021.

The year 2021 is gone, which means it’s time to take a look at which publications were captured by my Google Scholar queries.

I moved on from the queries I discussed in my previous post, which turned out to be quite noisy. At the moment I have the following:

a query for applications, specifically sustainability-oriented uses of optimisation and numerical algorithm parallel numerical sparse matrix optimization graph sustainability environment pollution economics algorithm model
a query for the more theoretical stuff: (sparse linear algebra numerical) OR (parallel numerical optimization)
queries for new publications by a set of people: Hartwig Anzt, Stephen Boyd, Aydın Buluç, Coralia Cartis, Ümit V. Çatalyürek, George Constantinides, Tim Davis, James W. Demmel, Jack Dongarra, Jaroslav Fowkes, Carla P. Gomes, Nick Gould, Nicholas J. Higham, Eric C. Kerrigan, Ignacio Laguna, Ruth Misener, Yurii Nesterov, Dominique Orban, Gabriel Peyré, Tyrone Rees, Michael Saunders, Jennifer Scott, Stanimire Tomov. Unfortunately I can’t have queries for all the people I would like to follow!

Since I have been tuning the queries quite a bit thoughout the year, I have likely missed some interesting work. If you’re reading this post and think I have missed something, please leave a comment and help me out.

The last was the fourth year of my bibliography project so I thought it would be good to take a look back at how its content have evolved in time. Last year, I started experimenting with a bit of data science, but this time I’d like to get real. I’ll discuss how the project has changed in terms of size and type of publications, how the topics have changed, and my considerations about this project and the literature in the field(s).

Number and type of publications throughout the years

number-of-publications

Last year I collected fewer publications compared to the previous year, probably because my queries have changed a couple of times. To be honest, when you almost reach an average of a new publication every day, fewer publications isn’t a bad thing…

type-of-publication

Although journal articles are still the most frequent type of publication, I found interesting that an increasing number of PhD dissertations are ending up in the bibliography. However, I’m not sure what this means in terms of the field considering that part of these dissertations are more oriented to machine learning or data science than they are to numerical analysis. Is this a continuation of the trend we’ve seen in the past years? Can numerical methods now be considered part of data science?

It was good to see that some of these dissertations – for example, Rogelio Long’s – cover topics that are very close to mine.

Topics throughout the years

I carried out some topic modeling on the bibliography using the gensim package. I extracted the data from titles and abstracts, and used nltk to carry out part of the data cleaning. I added a Jupyter notebook with the code in the repository.

The analysis found 4 topics. Let’s try to give an interpretation of what they represent.

Topic 0: algorithms for graph partitioning and dimensionality reduction

One way to understand what is covered by this topic could be to look at the most frequent terms in the papers, which is represented by the following wordcloud.

topic-0

This figure tells us that words like graph, model, and analysis are very frequent in the publications with very high topic content. Unfortunately, this isn’t very helpful, beacause the same terms are frequent in other publications too. To help overcome this problem, the pyLDAvis package allows us to delve more into the topic and visualise the most relevant terms, by tuning a parameter called $\lambda$: this tells us that words like rank, vertex, approximation, and framework are the most characteristic of this topic.

The list of the top 5 publications by topic content shows what kind of publications are in this set.

Key	Title
Burkhardt2019	Optimal algebraic Breadth-First Search for sparse graphs
Karypis1999	A fast and high quality multilevel scheme for partitioning irregular graphs
Tian2021	A High-Performance Sparse Tensor Algebra Compiler in Multi-Level IR
Ayall2019	Edge Property Based Stream Order Reduce the Performance of Stream Edge Graph Partition
Giles2019	Generalised multilevel Picard approximations

Topic 1: algorithms for mathematical optimisation

Here is the wordcloud for this topic.

topic-1

The pyLDAvis helps us again: words like precision, optimization, solution, and convex characterise this topic. The top 5 publications by topic content are the following.

Key	Title
Gao2020c	Distributed Quasi-Newton Derivative-Free Optimization Method for Optimization Problems with Multiple Local Optima
Alghunaim2020	On the Performance and Linear Convergence of Decentralized Primal-Dual Methods
Belotti2013	Mixed-integer nonlinear optimization
Nowak2019	Multi-Tree Decomposition Methods for Large-Scale Mixed Integer Nonlinear Optimization
Andrei2020	Nonlinear Conjugate Gradient Methods for Unconstrained Optimization

Topic 2: parallelisation of algorithms

Maybe confusingly, this is a very general topic: words like parallel, model, node, message are characteristic to this set of publications, according to the pyLDAvis package. Here is the top 5 publications by topic content.

Key	Title
SoltanMohammadi2020	Automatic Sparse Computation Parallelization By Utilizing Domain-Specific Knowledge In Data Dependence Analysis
Ahrens2020b	Load Plus Communication Balancing in Contiguous Partitions for Distributed Sparse Matrices: Linear-Time Algorithms
Muro2019	Acceleration of Symmetric Sparse Matrix-Vector Product Using Improved Hierarchical Diagonal Blocking Format
Chang2019	The Complexity of $\Delta +1$ Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
Ahrens2020a	On Optimal Partitioning For Sparse Matrices In Variable Block Row Format

Here, instead, is the wordcloud for this topic

topic-2

Topic 3: hardware architectures

The last topic is the one that most reflects my background in electronic engineering, because it is oriented towards the hardware and low-level memory optimisations.

topic-3

Again, just looking at the most frequent terms in this topic – and therefore the wordcloud – is misleading. Let’s look at the top 5 publications (by content) in this category instead.

Key	Title
Ramesh2019	Hardware-Software Co-Design Accelerators for Sparse BLAS
Choo2014	Understanding and Optimizing GPU Cache Memory Performance for Compute Workloads
Candel2017	Accurately modeling the on-chip and off-chip GPU memory subsystem
LiD2015	Nested Parallelism on GPU: Exploring Parallelization Templates for Irregular Loops and Recursive Computations
Kim2019	Static code transformations for thread-dense memory accesses in GPU computing

The pyLDAvis package tells us words like GPU, memory, NVIDIA, and AMD are most characteristic of this topic.

Topic content by year

Let’s first summarise my interpretation of the topics found by gensim in the following table:

Topic number	My interpretation
0	Graph partitioning and dimensionality reduction
1	Mathematical optimisation
2	Parallelisation of algorithms
3	Hardware architectures

The following figure shows how the topic content has evolved through the years in the bibliography project.

content-distribution

We immediately notice that, while the content of topics 0 and 2 has been mostly stable, the hardware architectures content has been declining in the past couple of years. This is something I’ve noticed while adding publications throughout the year, and it’s mostly due to my interests shifting slightly more towards both software and theory. At the same time, the mathematical optimisation content has been increasing quite steeply. Why is this happening?

My informal considerations

Here is some personal observations about the data I gathered, and this year’s publications in general.

Publications about machine learning methods tend to be associated with the mathematical optimisation topic, which is why this topic has been growing so much in the past few years.
Publications about applications of machine learning or data science show up as having a large content of parallelisation of algorithms. I think this is because the Latent Dirichlet Analysis (LDA) is perplexed by them. This also explains why the keywords for topic 2 are so vague.
I expect papers like Huang’s CoSA: Scheduling by Constrained Optimization for Spatial Accelerators will become very common. This paper describes dealing with parameters of deep learning networks using conventional mathematical optimisation problems.
I think we can safely say machine learning is now simply considered a broad category of mathematical optimisation algorithms, sitting next to conventional mathematical optimisation algorithms like – just to name one – the simplex method. This also explains why so many researchers are working towards estabilishing solid mathematical foundations for machine learning algorithms.
The compenetration of machine learning and conventional mathematical optimisation is however occurring in both directions: more and more aspects of machine learning are being adapted to conventional mathematical optimisation, starting from the core elements of linear algebra. A practical example of this is the work of Nick Higham’s team on mixed-precision algorithms.
The COVID-19 pandemic and COP26 have motivated reseachers to write a lot about applications. Keywords like sustainability have exploded so much in the past year that I had to remove a query of mine because of the high noise.
Since machine learning and data science require accurate tuning based on the data at hand, I expect to see an increasing number of publications about exposing the structure of the data to lower-level algorithms and primitives.
I’m still seeing papers about optimising sparse matrix-vector multiplications! It’s interesting that such a low-level primitive has still something to offer.

Finally, this year’s list

Abdelfattah A, Anzt H, Boman EG, Carson E, Cojean T, Dongarra J, Gates M, Grützmacher T, Higham NJ, Li S, Lindquist N, Liu Y, Loe J, Luszczek P, Nayak P, Pranesh S, Rajamanickam S, Ribizel T, Smith B, Swirydowicz K, Thomas S, Tomov S, Tsai YM, Yamazaki I and Yang UM (2021), "A Survey of Numerical Methods Utilizing Mixed Precision Arithmetic", The International Journal of High Performance Computing Applications.

[Abstract] [BibTeX]

Abstract: Within the past years, hardware vendors have started designing low precision special function units in response to the demand of the Machine Learning community and their demand for high compute power in low precision formats. Also the server-line products are increasingly featuring low-precision special function units, such as the NVIDIA tensor cores in ORNL's Summit supercomputer providing more than an order of magnitude higher performance than what is available in IEEE double precision. At the same time, the gap between the compute power on the one hand and the memory bandwidth on the other hand keeps increasing, making data access and communication prohibitively expensive compared to arithmetic operations. To start the multiprecision focus effort, we survey the numerical linear algebra community and summarize all existing multiprecision knowledge, expertise, and software capabilities in this landscape analysis report. We also include current efforts and preliminary results that may not yet be considered "mature technology," but have the potential to grow into production quality within the multiprecision focus effort. As we expect the reader to be familiar with the basics of numerical linear algebra, we refrain from providing a detailed background on the algorithms themselves but focus on how mixed- and multiprecision technology can help improving the performance of these methods and present highlights of application significantly outperforming the traditional fixed precision methods.

BibTeX:

@article{Abdelfattah2021,
  author = {Ahmad Abdelfattah and Hartwig Anzt and Erik G. Boman and Erin Carson and Terry Cojean and Jack Dongarra and Mark Gates and Thomas Grützmacher and Nicholas J. Higham and Sherry Li and Neil Lindquist and Yang Liu and Jennifer Loe and Piotr Luszczek and Pratik Nayak and Sri Pranesh and Siva Rajamanickam and Tobias Ribizel and Barry Smith and Kasia Swirydowicz and Stephen Thomas and Stanimire Tomov and Yaohung M. Tsai and Ichitaro Yamazaki and Urike Meier Yang},
  title = {A Survey of Numerical Methods Utilizing Mixed Precision Arithmetic},
  journal = {The International Journal of High Performance Computing Applications},
  year = {2021}
}

Abdelfattah A, Barra V, Beams N, Bleile R, Brown J, Camier J-S, Carson R, Chalmers N, Dobrev V, Dudouit Y, Fischer P, Karakus A, Kerkemeier S, Kolev T, Lan Y-H, Merzari E, Min M, Phillips M, Rathnayake T, Rieben R, Stitt T, Tomboulides A, Tomov S, Tomov V, Vargas A, Warburton T and Weiss K (2021), "GPU Algorithms for Efficient Exascale Discretizations", September, 2021.

[Abstract] [BibTeX]

Abstract: In this paper we describe the research and development activities in the Center for Efficient Exascale Discretization within the US Exascale Computing Project, targeting state-of-the-art high-order finite-element algorithms for high-order applications on GPU-accelerated platforms. We discuss the GPU developments in several components of the CEED software stack, including the libCEED, MAGMA, MFEM, libParanumal, and Nek projects. We report performance and capability improvements in several CEED-enabled applications on both NVIDIA and AMD GPU systems.

BibTeX:

@article{Abdelfattah2021a,
  author = {Ahmad Abdelfattah and Valeria Barra and Natalie Beams and Ryan Bleile and Jed Brown and Jean-Sylvain Camier and Robert Carson and Noel Chalmers and Veselin Dobrev and Yohann Dudouit and Paul Fischer and Ali Karakus and Stefan Kerkemeier and Tzanio Kolev and Yu-Hsiang Lan and Elia Merzari and Misun Min and Malachi Phillips and Thilina Rathnayake and Robert Rieben and Thomas Stitt and Ananias Tomboulides and Stanimire Tomov and Vladimir Tomov and Arturo Vargas and Tim Warburton and Kenneth Weiss},
  title = {GPU Algorithms for Efficient Exascale Discretizations},
  year = {2021}
}

Abdelfattah A, Anzt H, Ayala A, Boman E, Carson E, Cayrols S, T.Cojean, Dongarra J, Falgout R, Gates M, Gruetzmacher T, N.Higham, Kruger S, Li X, Lindquist N, Liu Y, Loe J, Luszczek P, P.Nayak, Osei-Kuffuor D, Pranesh S, Rajamanickam S, Ribizel T, B.Smith, Swirydowicz K, Thomas S, Tomov S, Tsai Y, Yamazaki I and Yang U (2021), "Advances in Mixed PrecisionAlgorithms: 2021 Edition". Thesis at: Lawrence Livermore National Laboratory.

[Abstract] [BibTeX] [URL]

Abstract: Over the last year, the ECP xSDK-multiprecision effort has made tremendous progress in developing and deploying new mixed precision technology and customizing the algorithms for the hardware deployed in the ECP flagship supercomputers. The effort also has succeeded in creating a cross-laboratory community of scientists interested in mixed precision technology and now working together in deploying this technology for ECP applications. In this report, we highlight some of the most promising and impactful achievements of the last year. Among the highlights we present areitemize
item Mixed precision IR using a dense LU factorization and achieving a 1.8× speedup on Spock;
item Results and strategies for mixed precision IR using a sparse LU factorization;
item A mixed precision eigenvalue solver;
item Mixed Precision GMRES-IR being deployed in Trilinos, and achieving a speedup of 1.4× over standard
GMRES;
item Compressed Basis (CB) GMRES being deployed in Ginkgo and achieving an average 1.4× speedup over
standard GMRES;
item Preparing hypre for mixed precision execution;
item Mixed precision sparse approximate inverse preconditioners achieving an average speedup of 1.2×;
item Detailed description of the memory accessor separating the arithmetic precision from the memory
precision, and enabling memory-bound low precision BLAS 1/2 operations to increase the accuracy by
using high precision in the computations without degrading the performance;itemize
We emphasize that many of the highlights presented here have also been submitted to peer-reviewed journals or established conferences, and are under peer-review or have already been published

BibTeX:

@techreport{Abdelfattah2021b,
  author = {A. Abdelfattah and H. Anzt and A. Ayala and E. Boman and E. Carson and S. Cayrols and T.Cojean and J. Dongarra and R. Falgout and M. Gates and T. Gruetzmacher and N.Higham and S. Kruger and X. Li and N. Lindquist and Y. Liu and J. Loe and P. Luszczek and P.Nayak and D. Osei-Kuffuor and S. Pranesh and S. Rajamanickam and T. Ribizel and B.Smith and K. Swirydowicz and S. Thomas and S. Tomov and Y. Tsai and I. Yamazaki and U.M. Yang},
  title = {Advances in Mixed PrecisionAlgorithms: 2021 Edition},
  school = {Lawrence Livermore National Laboratory},
  year = {2021},
  url = {https://www.osti.gov/servlets/purl/1814677}
}

Acer S, Boman EG, Glusa CA and Rajamanickam S (2021), "Sphynx: A parallel multi-GPU graph partitioner for distributed-memory systems", Parallel Computing., April, 2021. , pp. 102769. Elsevier BV.