3.1 QR Method and Givens Rotation

The major computation in Algorithm 1 is the calculation of

$\begin{array}{l}\hfill {Ā}_i^T{({Ā}_i{Ā}_i^T)}^{-1}\text{and}{({Ā}_i{Ā}_i^T)}^{-1}\end{array}$

where ${Ā}_i$ is a block row of the augmented matrix. Each block row has three nonzero diagonal elements and few augmented elements. However, the calculation using Eq. (5) has some drawbacks. First, although the matrix is quite sparse, the direct calculation still iterates many times, especially the calculation of ${\left({Ā}_i{Ā}_i^T\right)}^{-1}$. If ${Ā}_i$ is an k × q matrix, ${Ā}_i{Ā}_i^T$ is an k × k matrix. Because ${Ā}_i$ is almost a tridiagonal matrix, ${Ā}_i{Ā}_i^T$ will be a band matrix with five diagonals. Second, the direct calculation of oblique projector using Eq. (5) is numerically unstable [9, Chapter 14], even with some pivoting strategies. A better choice is the QR method.

The QR method first decomposes the matrix ${Ā}_i^T$ into the product of an orthogonal matrix Q_i and an upper triangular matrix R_i, ${Ā}_i^T=Q_i{R}_i$. Based on that, Eq. (5) can be simplified as

$\begin{array}{l}\hfill {Ā}_i^T{\left({Ā}_i{Ā}_i^T\right)}^{-1}=Q_i{R}_i{\left(R_i^T{Q}_i^T{Q}_i{R}_i\right)}^{-1}=Q_i{R}_i{\left(R_i^T{R}_i\right)}^{-1}=Q_i{R}_i^{-T}\end{array}$

and

$\begin{array}{l}\hfill {\left({Ā}_i{Ā}_i^T\right)}^{-1}={\left(R_i^T{Q}_i^T{Q}_i{R}_i\right)}^{-1}=R_i^{-1}{R}_i^{-T}\end{array}$

assuming ${Ā}_i$ or R_i is of full rank. As can be seen, the formulas in Eqs. (6), (7) are much simpler and cleaner than that in Eq. (5).

There are several algorithms to carry out the QR decomposition [10, Chapter 5]. The most suitable one for matrix $A_i^T$ is the Givens rotation, because $A_i^T$, a tridiagonal matrix, is very close to the upper triangular matrix R_i structurally, except for one subdiagonal and few augmented elements, and the Givens rotation method annihilates those nonzero elements one by one using rotation matrices. A rotation matrix for a two-vector v = (a b)^T is

$\begin{array}{l}\hfill G=\left(\begin{array}{ll}c& s\\ -s& c\\ \end{array}\right)\end{array}$

where c = a/d, s = b/d, and $d=\sqrt{a^2+b^2}$. By premultiplying G to v, $Gv={(\sqrt{a^2+b^2}0)}^T$. Note that G is a orthonormal matrix, and it preserves the length of the multiplicand, which means v and Gv have the same length.

The QR decomposition by Givens rotation uses the diagonal and subdiagonal elements to create rotation matrices to brings zeros to the subdiagonal. The final Q matrix can be obtained by cumulating the rotation matrices.

Table 1 compares the operation counts of the Givens rotation and the direct method using Eq. (5). The size of ${Ā}_i^T$ is n × k, and the size of C_i is ℓ × k. The operation count of the direct method is based on the spare matrix multiplication and Gaussian elimination for band matrix. As can be seen, the operation count of Givens rotation is almost half in the computation of S_i, compared to that of the direct method.

Table 1

Operation Counts of Givens Rotation and Direct Multiplication

Equation	Givens Rotation	Direct Method
$u_i={Ā}_i^T{({Ā}_i{Ā}_i^T)}^{-1}{b}_i$	41k + 24	46k − 3
$S_i=C_i^T{({Ā}_i{Ā}_i^T)}^{-1}{C}_i$	5kℓ + 20k − 6ℓ + 6	9kℓ + 20k − 12ℓ + 6
$W_i={Ā}_i^T{({Ā}_i{Ā}_i^T)}^{-1}{C}_i$	2kℓ + 17k − 6	2kℓ + 6k + 14

3.2 Sparse Storage Format

Because A is tridiagonal, which is extremely sparse, a special storage format should be considered to reduce the used memory. A simple format of a tridiagonal matrix is to use three vectors to store the nonzero elements. In addition to that, we also need to consider the storage for intermediate results, such as the storage for matrix Q and matrix R.

Based on those requirements, we designed a 5n array as the major storage format, as shown in Fig. 2. Matrix A can be stored in the first three n vectors. Matrix R is also a tridiagonal matrix, whose nonzeros are all above the main diagonal. After the QR decomposition, matrix R can use the same space as matrix A’s since A is no longer needed in the computation. Matrix Q is a block diagonal matrix. To store it may take too much space. Alternatively, we keep the Q matrix in the decomposed form and store the rotation matrices G_i. Since each G_i only has two parameters, we only need two elements to store each G_i. So the last two vectors are used to store the rotation matrix G_i. When the matrix Q is required in computation, such as Eq. (6), we multiply those G_i by the multiplicand directly.

3.3 Coalesced Memory Access

We reformat the matrix storage to improve the performance on the GPU. As suggested in Ref. [11], the data accessed by threads within a block should be successively stored because threads in a thread-block read or store simultaneously. Successively stored data allows coalesced memory access on the GPU, which can read/write 128 or more elements simultaneously, depending on the GPU hardware structure.

The original data storage format that stores the adjacent tridiagonal elements successively in memory cannot make coalesced memory access. Therefore we modify to the storage method so that the element k in the ith partition is before the element k in i − 1th partition and followed by the element k in the i + 1th partition.

Fig. 3 shows an example. There are eight elements, and each block has two threads. The number of partitions is two, which means that each thread controls 8/2 = 4 elements. Elements are reformatted based on the number of threads in a block. If thread 1 needs to access elements from 1 to 4 and thread 2 needs to access elements from 5 to 8, we place elements 1 and 5 together, 3 and 6 together, and so on. The new storage lets the threads in a block access data simultaneously. Although the data reformatting also costs time, this technique fulfills the coalescing requirement on the GPU and contributes to a higher memory accessing efficiency in the following steps. Experimental results are shown in the next section.

3.4 Boundary Padding

One problem of single instruction multiple data architecture, such as GPU, is the branch divergence, which means a group of threads sharing the same program counter have different execution paths. On a Compute Unified Device Architecture (CUDA) core, threads from a block are bundled into fixed-size warps for execution. Threads within a warp follow the same instruction synchronously. If a kernel function encounters an if-then-else statement that some threads evaluate to true while others to false, a branch divergence occurs. Because of the restriction that threads in a warp cannot diverge to different conditions, warp deactivates the false conditioned threads and proceeds to the true condition, and then reverses condition. In other words, the branch divergence serializes all the possible execution paths, which can really hurt a GPU’s performance.

In the ABCD algorithm, the branch divergence occurs on the boundary process, which needs to handle different data. To solve the problem, we proposed the boundary padding technique, which adds unnecessary paddings and uses additional memory spaces for those threads with different execution on the GPU. The boundary padding technique ensures that all the threads in the same warp perform the same operations at any moment, which eliminates branch divergence.

3.4.1 Padding of the augmented matrix

Fig. 4 shows that the augmentations for the top and bottom partitions are different from those of the middle partitions, because they lack either C_{i, j} or negative identity − I, which will lead to divergences. Our implementation adds zero elements to the top and bottom parts of the augmented matrix. Those zero elements have no actual influence on the final solution. The padding does not cost extra storage. Fig. 5 shows how those padding are stored in a compact format.

3.4.2 Padding for Givens rotation

During the rotation steps, the first partition of ABCD is different from other partitions. It rotates to middle and lower diagonal, while other partitions rotate to lower and below the lower diagonal, which leads to branches. To reduce the branches, we add redundant elements to the first partition. In other words, the first partition will further rotate to the lower diagonal and the diagonal below the lower diagonal. This technique doubles the work of the first partition but unifies the work among all threads. In our experiment results, the total time of calculating the Givens rotations can be reduced to half of the original time. Fig. 6 shows the padding before and after the padding on the first partition.

4.1 Comparison With CPU Implementation

Fig. 7 shows the comparison between our implementations of the ABCD algorithm on the GPU and on CPU. The dataflow are the same for all the functions. The CPU version is implemented in C; the GPU version is implemented in CUDA. As shown in Table 2, the calculation of two implementations are similar if the matrix size is smaller than 2¹⁷ because we have to load data onto GPU memory before starting calculation. The overload caused by moving the data is large compared to calculation time. But the CPU calculation time nearly doubles when the dimension of the matrix doubles, while GPU calculation time increases only a little. The difference is because of GPU’s architecture. If the dimension rises to 4 million, a 24.15 times speedup can be obtained by using GPU. The speedup of difference between a matrix size of 2 million and 4 million is small because we believe that GPU reaches the hardware limits.

4.2 Speedup by Memory Coalescing

Table 3 lists the speedups of different kernels made by the coalescing storage format, as described in Section 3.3. The matrix size is 4 million. The speedup is calculated by the ratio of the time without coalesced format and the time with coalesced format. Coalesced format can attribute to over five times speedup for solving $R_i^{-1}$ with multiple right-hand sides.

Table 3

Speedup by Coalesced Memory Access

Kernel (Functionality)	Speedup (Original/Coalesced)
Assign augmented matrix	1.180
Create Givens rotation	1.519
Apply Givens rotation	1.750
Solve $R_i^{-1}$	1.959
Solve $R_i^{-1}$ (multiple right-hand sides)	5.082
Calculate u and f	2.319
Calculate matrix S	1.873
Solve S−1	3.464

There are many factors influencing the possible speedup. The major one is the size of memory accessed by the kernel. More memory accesses give a larger speedup. When the data size is small, its effectiveness is limited. As shown in Table 3, only a 1.15× speedup can be obtained for the task of assigning an augmented matrix. Another reason is the data access pattern. With the original data format, increasing the number of threads cannot accelerate the performance. But with a coalesced data format, doubling the number of threads reduces almost half of the execution time. This is because the bottleneck of the program using the original data format is memory access. More threads do not help to improve the performance. On the other hand, with a coalesced data format, the memory access is no longer the performance bottleneck. So other performance-tuning techniques can take effect. The other factors influencing the speedups include memory size, total number of threads, and the operations on the memory.

4.3 Boundary Padding

Although padding adds useless work to some threads, all threads can perform the same instructions simultaneously, which increases the overall performance.

Table 4 shows the speedup of the boundary padding technique. The speedup comes from two major factors. First, the boundary padding technique reduces the branch divergence because all the threads have the same execution path. Second, the boundary padding technique increases the coalesced memory access, since the memory access pattern is unified.

The padding for a Givens rotation can not only improve the performance of creating the rotation matrix but also accelerate the kernel that applies the Givens rotations, as shown in the results in Table 4.