Communication efficient application of sequences of planar rotations to a matrix
Thijs Steel, Julien Langou · 2024
Read Communication efficient application of sequences of planar rotations to a matrix by Thijs Steel, Julien Langou (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01852.txt.
Introduction
Thijs Steel and Julien Langou sped up a core matrix operation used in eigenvalue work in a 2024 paper. Many solvers apply long chains of small plane rotations to a matrix, and the cost can dominate. Their algorithm attacks the problem on three fronts.
A new inner kernel reuses registers in a fresh way. A blocking and packing plan keeps data flowing through fast memory. A careful count of memory traffic guides the choice of settings and yields theory insight. Tests on modern hardware beat the prior best and ran near the chip's peak rate. The authors present the work as both a practical kernel and a model for reasoning about memory-bound code.
Catalog record
| CREATOR | Thijs Steel, Julien Langou |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01852
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Communication efficient application of sequences of planar rotations to a matrix Thijs Steel, Julien Langou Abstract We present an efficient algorithm for the application of sequences of planar rotations to a matrix. Applying such sequences efficiently is important in many numerical linear algebra algorithms for eigenvalues. Our algorithm is novel in three main ways. First, we introduce a new kernel that is optimized for register reuse in a novel way. Second, we introduce a blocking and packing scheme that improves the cache efficiency of the algorithm. Finally, we thoroughly analyze the memory operations of the algorithm which leads to important theoretical insights and makes it easier to select good parameters. Numerical experiments show that our algorithm outperforms the state-of-the-art and achieves a flop rate close to the theoretical peak on modern hardware. keywords High-performance computing, cache efficiency, BLAS, Givens rotations, eigenvalue computation 1 Introduction The problem we will focus on in this paper is the application of a sequence of planar rotations to a matrix. A basic algorithm to apply such a sequence can be simple: we just loop over the rotations and apply each one to the matrix. Pseudocode for this algorithm is given in Algorithm 2 and our C implementation is not much more complicated. Applying a sequence of orthogonal transformations efficiently is an important building tool in numerical linear algebra. To achieve high performance, many factorizations limit their initial calculations to a smaller submatrix of the original matrix. Updating the rest of the matrix (which often involves the bulk of the floating-point operations) can then be done efficiently with an optimized routine. The two most common orthogonal transformations are Givens rotations and Householder reflectors. Givens rotations are applied to two vectors (usually two columns or rows of a matrix) and are defined by a cosine and a sine. Householder reflectors can involve an arbitrary number of vectors. To apply a sequence of reflectors efficiently, the most popular method relies on the WY representation [ 8 ] . Through the use of this factorization, routines that apply a sequence of reflectors to a matrix can be optimized to achieve close to the theoretical peak flop rate on modern hardware. Because of this, reflectors have become the preferred choice for orthogonal transformations. However, some algorithms require the use of rotations. In case the matrix has a special structure (for example, if it is upper triangular), applying a reflector to it can destroy that structure. If rotations are used instead, the structure can more easily be preserved. Some examples are the implicit QR algorithm [ 3 ] and the Jacobi method for the singular value decomposition [ 5 ] . The basic algorithm presented in Algorithm 2 is not very efficient on modern hardware. The main reason for this is inefficient memory access because the algorithm is not cache-friendly. If we refer to the rotation whose values are stored in position (i,j) of the matrices C and S as rotation (i,j) , then we can say that column i of the matrix the rotations are applied to is involved in rotations (i-1,j) and (i,j) for all j . But in between applying (i,j) and (i,j+1) , we need to load and store the entire matrix, so it is unlikely that the values of column i are still in the cache when we need them again. Kågström et al. [ 6 ] and later Van Zee et al. [ 10 ] have improved upon this basic algorithm in two ways, fused rotations and a wavefront pattern. 1.1 Wavefront algorithm In the standard algorithm, we need to load and store the entire matrix between applying rotation (i,j) and (i,j+1) . In an ideal world, we would just change the order of the loops so that rotation (i,j+1) is applied immediately after rotation (i,j) . Sadly, this is not allowed. Before we can apply rotation (i,j+1) , we have to apply rotation (i+1,j) . This leads to a wavefront pattern, where we apply rotation (i,j) , then (i-1,j+1) , (i-2,j+2) , \dots . Figure 1 shows this pattern visually; each of the diagonal sequences is called a wave. The advantage of this pattern is that instead of accessing n-1 columns before a column is used again, this pattern accesses k columns. Typically, k is much smaller than n , so it is much more likely that the column can remain in the cache. (a) Standard pattern (b) Wavefront pattern Figure 1 : The matrix C containing the cosines of the rotations and arrows indicating the order in which the rotations are applied. On the left, the standard pattern which applies full sequences of rotations. On the right, the wavefront pattern which applies the rotations in “waves”. 1.2 I/O complexity If we assume a two-memory machine with a small cache of size S and a large memory, we want to quantify the number of memory movement (read and write) between the memory and the cache. This is called the I/O complexity problem. Recent work on I/O lower bounds have led to techniques and tools to mechanically compute the I/O lower bounds of parametrized programs [ 7 ] . Using the IOLB tool on Algorithm 2 leads to a I/O lower bound of \frac{mnk}{\sqrt{S}}. Since the total number of operations of our code is 6mnk , this means that the operational intensity is at most 6\sqrt{S} . A quick analysis of the wavefront algorithm explained in Section 1.1 goes as follows. We need to apply mnk Givens rotations. m_{b} and k_{b} such that m_{b}k_{b}\leq S real such that a block of size m_{b} -by- k_{b} of A fits in cache. At each step of the wavefront algorithm, we need to read one column of size m_{b} , and write back ne column of size m_{b} , and load 2k_{b} cosines and sinces that represent k_{b} rotations. In this step, we will be able to do m_{b}k_{b} rotations. Forgetting start and end clean up code, we need to do (roughly) \frac{mnk}{m_{b}k_{b}} steps. And so the I/O of the algorithm is \frac{mnk}{m_{b}k_{b}}(2m_{b}+2k_{b}). For k_{b}=\sqrt{S} and mb=\sqrt{S} we get \frac{4mnk}{\sqrt{S}}. Since the total number of operations of our code is 6mnk , this means that the operational intensity for the wavefront algorithm is \frac{3}{2}\sqrt{S} . Two conclusions. First, we see that the ratio between an I/O lower bound for our problem and the wavefront algorithm is a factor 4. Second, we see that the operational intensity of our kernel is pretty good. (For comparison, the operational intensity of GEMM is \sqrt{S} .) Therefore there is potential to be able to hide I/O’s and reach GEMM-like performance. We note that an analysis of the number of cache misses of the wavefront algorithm, a related problem, is done in [ 10 , §4.2] . 1.3 Fused rotations Despite what the name suggests, fused rotations are not directly accumulated in any way. Instead, a fused rotation is a technique to increase register reuse. The advantage becomes clear when we study what happens when we apply two rotations to three vectors x , y , and z : 1. Load rotation 1 into registers 2. for i=0,1,\dots,n 3. load x[i] and y[i] into registers 4. apply rotation 1 to x[i] and y[i]