In this paper, we research and compare different implementations of cyclic reduction and sweep algorithms on a graphics processing unit (GPU) using different types of device memory. As a result of the work, it was found that the algorithm of the run should be used to solve the set of the tridiagonal linear system. However, the best results are shown by a parallel version of the cyclic reduction algorithm with partial use of shared memory, when solving a single linear system on the GPU.
The applicability of systems of linear equations of tridiagonal form is very extensive[
There are many algorithms and their parallel versions for solving tridiagonal systems of linear
equations. The need for parallelization naturally occurs when the size or number of systems to be
solved is very large. Most methods are based on simple arithmetic operations performed many times.
Therefore, the implementation of parallel versions of algorithms on the GPU is a reasonable solution
[
This article investigates parallel algorithms for solving systems of linear equations of tridiagonal form.
The traditional matrix algorithm and the cyclic reduction method are usually used to solve systems
of linear algebraic equations of tridiagonal form [
The advantage of the cyclic reduction method is a high degree of parallelism [
The traditional matrix algorithm Parallels for one system worse than the parallel cyclic reduction algorithm. However, there are a large number of tasks that require the solution of a set of systems. The traditional matrix algorithm is suitable for such problems. It gives a gain in acceleration due to low computational complexity.
In this paper, we investigate which algorithm for solving tridiagonal-type systems spends less time on computation. To solve this problem, we compare the he implementation of the traditional matrix algorithm, and the serial and parallel versions of the cyclic reduction algorithm using different combinations of global and shared GPU memory. Parallelization of methods is carried out using the CUDA model. Experimental research is conducted on the supercomputer "Sergey Korolev".
This work began with the implementation and research of the traditional matrix algorithm. This method is one of the most famous and popular for solving tridiagonal systems of linear arithmetic equations.
The first version of the algorithm was implemented on the CPU for further comparison in acceleration. Then an implementation of a parallel traditional matrix algorithm on the GPU using only global memory was created. The next task was to implement this method using shared memory. Since the memory size is small, the necessary factors were loaded in portions into the shared memory immediately before use. Then, after all the necessary operations, the coefficients were replaced by the next portion. To store data in shared memory, arrays of auxiliary coefficients and and the sought vector of size 2 ∙ and arrays of initial coefficients , , and of size . All calculations were performed in shared memory.
The experiments were carried out for a set of systems with matrices of size = 4095. This size was chosen to compare the results with the experimental versions of the cyclic reduction algorithm implemented for the size of matrices = 2 − 1, where ∈ ℕ.
The number of equation systems varied from 5000 to 20000. If the number of systems is less than 5000, working with memory on the GPU takes much longer than the calculations themselves.
The obtained accelerations of parallel versions of algorithms relative to the serial version on the CPU are given in table 1.
This result shows that the time it takes to copy data from global memory to shared memory and vice versa is justified by the high speed of calculations performed in shared memory.
The next step is the implementation of the sequential cyclic reduction algorithm (SERICR). This algorithm makes it impossible to carry out parallel calculations for one system, but is parallelized for a set of systems. significant information are gray.
R. Hockney [
Then, based on the obtained and and the values of the coefficients of the left and right parts of ( )
= ( ) ( ) = = varying in increments ℎ2 = 2( −1) from = 2 ( −1) to = ′ − 2 ( −1), we consider: = 0, − 1 we find the vector of solutions . It is assumed that 0 = ′ = 0. For = , 1, for , = .
However, the resulting memory savings are not sufficient to use this algorithm on big data. The solution in this situation is to store only two levels of reduction and recalculate the coefficients when they are needed.
The was implemented on the central and graphics processor devices. enough memory to store the coefficients of all levels of reduction. When implemented on the GPU recalculation was necessary. On the graphics card, the algorithm was implemented using only global memory and shared memory. of systems varied from 5000 to 25000. The obtained accelerations are shown in table 2.
The experiments were carried out for a set of systems with matrices of size = 4095. The number
The experiments were carried out for a system of equations with matrices of size memory does not give a significant benefit.
Thus, when solving a set of systems of linear algebraic equations, the best result is shown by the traditional matrix algorithm on a GPU with full load in the shared memory. Its running time is on average 6 times shorter than the running time of the cyclic reduction algorithm. However, when solving one system with a large matrix, it is more expedient to use a parallel cyclic reduction algorithm with partial loading into shared memory. Its implementation requires 7 times less time for calculations than the implementation of the traditional matrix algorithm.
As a result of this work, it was obtained that the use of shared memory for the traditional matrix algorithm gives an increase in acceleration by 47%. This is because data loaded into shared memory is reused.
For the cyclic reduction algorithm, it is advisable to load into the shared memory only those coefficients that are used twice in the calculations. At the same time, the acceleration is increased by 2%.
When solving a set of systems of linear algebraic equations, the best implementation of the traditional matrix algorithm is 6 times faster than the best implementation of the cyclic reduction algorithm. However, when solving a single system with a large matrix, the result is the opposite: the cyclic reduction algorithm is 7 times faster.