# Performance Evaluation of Adaptive-Precision SpMV with Reduced-Precision Formats

Stef Graillat, Fabienne Jézéquel, Théo Mary, Roméo Molina, Daichi Mukunoki

► To cite this version:

Stef Graillat, Fabienne Jézéquel, Théo Mary, Roméo Molina, Daichi Mukunoki. Performance Evaluation of Adaptive-Precision SpMV with Reduced-Precision Formats. 2023. hal-04261073

HAL Id: hal-04261073

https://hal.science/hal-04261073v1

Preprint submitted on 26 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Performance Evaluation of Adaptive-Precision
SpMV with Reduced-Precision Formats

Stef Graillat<fnref n="1" />, Fabienne Jézéquel<fnref n="1" />,<fnref n="2" />, Théo Mary<fnref n="1" />, Roméo Molina<fnref n="1" />,<fnref n="3" />, and Daichi Mukunoki<fnref n="4" />

<table><caption>TABLE I
IEEE FORMATS AND RPFP'S REDUCED-PRECISION FORMATS</caption><thead><tr><th>Data type</th><th>Data size (bits)</th><th>Format (bits)<br>s:sign, e:exp, m:mantissa</th><th>Unit roundoff</th></tr></thead><tbody><tr><td><b>binary64</b> (FP64)</td><td>64</td><td>s(1)+e(11)+m(52)</td><td>2<sup>-53</sup></td></tr><tr><td>FP64in56b (RP56)</td><td>32+16+8</td><td>s(1)+e(11)+m(44)</td><td>2<sup>-45</sup></td></tr><tr><td>FP64in48b (RP48)</td><td>32+16</td><td>s(1)+e(11)+m(36)</td><td>2<sup>-37</sup></td></tr><tr><td>FP64in40b (RP40)</td><td>32+8</td><td>s(1)+e(11)+m(28)</td><td>2<sup>-29</sup></td></tr><tr><td><b>binary32</b> (FP32)</td><td>32</td><td>s(1)+e(8)+m(23)</td><td>2<sup>-24</sup></td></tr><tr><td>FP32in24b (RP24)</td><td>16+8</td><td>s(1)+e(8)+m(15)</td><td>2<sup>-16</sup></td></tr><tr><td><b>binary16</b> (FP16)</td><td>16</td><td>s(1)+e(5)+m(10)</td><td>2<sup>-11</sup></td></tr><tr><td>FP32in16b (RP16)</td><td>16</td><td>s(1)+e(8)+m(7)</td><td>2<sup>-8</sup></td></tr><tr><td>FP16in8b (RP8)</td><td>8</td><td>s(1)+e(5)+m(2)</td><td>2<sup>-3</sup></td></tr></tbody></table>

**Algorithm 1 Adaptive-precision SpMV y = Ax**

1: **for** i = 1 : m **do**

2: **for** k = 1 : q **do**

3: $y_i^{(k)} = 0$

4: **for** j ∈ B<sub>ik</sub> **do**

5: $y_i^{(k)} = y_i^{(k)} + a_{ij}x_j$ in precision $u_k$

6: **end for**

7: **end for**

8: $y_i = \sum_{k=1}^{q} y_i^{(k)}$ in precision $u_1$

9: **end for**

**Abstract**—This study explores the potential for performance improvement in the adaptive-precision sparse matrix-vector product (SpMV) (Graillat et al. 2023) by using reduced-precision formats other than the IEEE standard ones. In addition to FP32 and FP64, we consider to utilize reduced-precision formats of 8/16/24/40/48/56-bit length. Our evaluation compares the performance of four- and nine-precision versions with that of the existing two-precision only version using FP32 and FP64 and demonstrates the effectiveness.

**Index Terms**—sparse matrix-vector product (SpMV), mixed-precision, adaptive-precision, reduced-precision

## I. INTRODUCTION

The adaptive-precision sparse matrix-vector product (SpMV) [1] is a mixed-precision computation method for SpMV. It eliminates unnecessary bits on each element of the input matrix that do not contribute to the computed result at a target accuracy, and stores only the necessary bits with a possible minimum precision representation (or simply the element is dropped if all the bits are unnecessary). The reduced memory footprint is expected to result in faster execution time. The performance gain has so far been demonstrated only using the two-precision levels of IEEE FP32 and FP64 formats. In this study, through a reduced-precision memory accessor, we utilize some reduced-precision formats other than FP32 and FP64, such as 8/16/24/40/48/56-bit formats. Then, we demonstrate the performance with four- and nine-precision levels compared with the two-precision version on many-core CPUs.

## II. METHODS

### A. Adaptive-precision SpMV

The adaptive-precision SpMV decomposes the input matrix into several low-precision matrices of different precision formats and then computed the sum of the SpMVs for the decomposed low-precision matrices. Algorithm 1 shows the adaptive-precision SpMV computing $y = Ax$, where $A \in \mathbb{R}^{m \times n}$ and $x \in \mathbb{R}^n$, with q precision levels $u_1 < u_2 < ... < u_q$, where $u_k$ ($k = 1, ..., q$) denotes the unit roundoff of each precision used. Each row i of A is partitioned into q buckets $B_{ik}$, which is determined such that the backward error (see [1] for definition) is at most in $O(\epsilon)$, where $\epsilon \ge u_1$ is a target accuracy, as

$$B_{ik} = \{j \in J_i : |a_{ij}x_j| \in (\epsilon\theta_i/u_{k+1}, \epsilon\theta_i/u_k]\},$$

where $J_i$ is the set of indices of nonzero elements in row i of A. For $\theta_i$, $\theta_i = ||A||$ is used to satisfy the norm-wise error and $\theta_i = |a_i|^T e$, where $e = [1, ..., 1]^T$, is used to satisfy the component-wise error.

### B. Reduced-precision formats

A reduced-precision memory accessor, RpFp [2], enables one to represent arbitrary precision mantissa in multiple bytes in C/C++ language by truncating the IEEE formats, as shown in Table I. For 24/40/48/56-bit formats, a reduced-precision value is represented as a structure with multiple words, and when allocating the array of the structure, an array is allocated for each word separately for efficient memory access (the

<footnote n="1">¹Sorbonne Université, CNRS, LIP6, Paris, France</footnote>

<footnote n="2">²Université Paris-Panthéon-Assas, Paris, France</footnote>

<footnote n="3">³Université Paris-Saclay, Orsay, France</footnote>

<footnote n="4">⁴RIKEN Center for Computational Science, Kobe, Japan</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Adaptive-precision SpMV with nine precision levels (a part). RpArrayToFp converts a reduced-precision format to the IEEE format.</figcaption></figure>

<table><caption>TABLE II
TEST MATRICES (SORTED BY $n_{nz}$).</caption><thead><tr><th>#</th><th>Matrix</th><th>n</th><th>n<sub>nz</sub></th></tr></thead><tbody><tr><td>0</td><td>vas_stokes_4M</td><td>4,382,246</td><td>131,577,616</td></tr><tr><td>1</td><td>Cube_Coup_dt0</td><td>2,164,760</td><td>127,206,144</td></tr><tr><td>2</td><td>Flan_1565</td><td>1,564,794</td><td>117,406,044</td></tr><tr><td>3</td><td>Long_Coup_dt6</td><td>1,470,152</td><td>87,088,992</td></tr><tr><td>4</td><td>bone010</td><td>986,703</td><td>71,666,325</td></tr><tr><td>5</td><td>vas_stokes_2M</td><td>2,146,677</td><td>65,129,037</td></tr><tr><td>6</td><td>Hook_1498</td><td>1,498,023</td><td>60,917,445</td></tr><tr><td>7</td><td>RM07R</td><td>381,689</td><td>37,464,962</td></tr></tbody></table>

structure-of-array layout). To obtain an element from the array, the elements are taken from multiple separate arrays and concatenated into a value. We note that FP32in16b (RP16) is equivalent to the bfloat16 (BF16) format and that FP16in8b (RP8) is equivalent to the FP8 E5M2 format [3].

### C. Implementation

We ported the Fortran code used in the paper [1] to the C language and applied the RpFp implementation for CPUs from [4] to it. The FP16 and RP8 formats rely on the half library<fnref n="1" />. Our implementation assumes that the input matrix fits into the 8-bit exponent range of FP32, but since FP16 and RP8 have only a 5-bit exponent, they are not used if the element is out of range. The SpMV adopts the Compressed Row Storage (CRS) format with 32-bit indexes. It is parallelized with OpenMP: a matrix row is computed with a thread. Figure 1 presents a part of the adaptive-precision SpMV code with nine precision levels, computing $y = Ax$.

## III. EVALUATION

We performed the evaluation on the dual-socket system of AMD EPYC 7713 (Zen3 architecture). This processor has the following specifications (given for one CPU): 64 cores, AVX2 (256-bit SIMD), theoretical peak performance of 2048 GFlops/s in FP64 and 4096 GFlops/s in FP32 (at 2.0 GHz), 256 MB L3 cache, DDR4 memory of 204.8 GB/s. The

<figure><img src="image_3.png" /><figcaption>Fig. 2. Error obtained from the FP128 uniform precision SpMV</figcaption></figure>

experimental code was compiled using GCC 9.4.0 with `-O3 -march=native -fopenmp -lgomp` (2 threads/core). It was executed with `numactl --interleave=all`. We collected eight potential matrices from the SuiteSparse Matrix Collection [5], as presented in Table II (each matrix has size of $n \times n$ with $n_{nz}$ nonzero elements). These matrices were numbered in $n_{nz}$ descending order. Symmetry is not considered in SpMV; the matrix is expanded to an asymmetric matrix before execution. The vector $x$ is set to $e = [1, ..., 1]^T$. For the results, we reported the shortest execution time out of 15 executions (SpMV is executed five times in a single program, and the program is executed three times.).

We evaluated the following cases:

* **FPxx**: Uniform-precision SpMV with FPxx (xx=32 or 64).

* **RPxx**: Reduced-precision SpMV with RPxx (xx=8, 16, 24, 40, 48, or 56). The matrix and vectors are stored in RPxx while the arithmetic operations are performed in the IEEE type (FP32 or FP64) having the same exponent range as RPxx.

* **AP2**: Adaptive-precision SpMV with two precision levels using FP64 and FP32.

* **AP4**: Adaptive-precision SpMV with four precision levels using FP64, FP48, FP32, and RP16.

* **AP9**: Adaptive-precision SpMV with nine precision levels using FP64, FP56, FP48, FP40, FP32, FP24, FP16, RP16, and RP8.

Figure 2 presents the backward errors obtained from the uniform precision SpMV performed in FP128 arithmetic.

Figure 3 presents the relative execution time normalized to FP64. The constant $p$ determines the target accuracy as $\epsilon = 2^{-p}$, which corresponds to the unit roundoff shown in Table I. AP4 and AP9 are better than AP2 in many cases. For example, the maximum speedup of AP4 over AP2 is 47% (matrix #1,

<footnote n="1">¹https://sourceforge.net/projects/half/</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 3. Execution time (normalized to the time of the FP64 SpMV)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. Throughput in GB/s</figcaption></figure>

CW, p=8). However, the difference between AP4 and AP9 is trivial, or rather AP4 is better in many cases. Still, we observed the maximum improvement of 9.7% for AP9 over AP4 (matrix #2, CW, p=16) among the cases where AP4 is faster than AP2. Figure 4 presents the throughput in GB/s. As the data size decreases, the throughput can increase due to cache (note that some exceed the memory bandwidth). Figure 5 shows the distribution of the formats used in the matrix, which explains that the performance gains come from the use of dropping and low-precision formats. The effectiveness is highly matrix-dependent, but in many cases where the target accuracy is not

corresponding to the IEEE format, the introduction of reduced-precision formats has led to successful speedups.

## IV. CONCLUSION

We have demonstrated the performance of adaptive-precision SpMV with up to nine-precision levels using 8/16/24/32/40/48/56/64-bit formats. Increasing the number of precision levels used does not necessarily improve performance, and the effectiveness is strongly dependent on the matrix and target accuracy, but the effect was demonstrated in several cases.

Below are future work and perspectives.
<figure><img src="image_6.png" /><figcaption>Fig. 5. Distribution of formats used in adaptive-precision SpMV. The horizontal axis indicates the matrix number and the vertical axis indicates the percentage (up to 100%).</figcaption></figure>

* Since the use of low-precision formats does not necessarily lead to better performance, performance-oriented decisions on which formats to use can be explored (e.g., excluding RP56 that is composed of 3 elements).

* New sparse matrix formats suitable for adaptive-precision SpMV can be explored (e.g., index-compressed format is effective for low precision.).

* Compression of the exponent part or decomposition of the matrix according to the range of the exponent can be explored. Or, one can consider introducing a reduced format with a smaller exponential part, such as FP16 for BF16.

## ACKNOWLEDGMENT

This research was supported by the Japan Society for the Promotion of Science (JSPS) KAKENHI Grant #20KK0259 and the InterFLOP (ANR-20-CE46-0009) project of the

French National Agency for Research (ANR) and the inter-disciplinary CNRS project CASSIDI.

## REFERENCES

[1] S. Graillat, F. Jézéquel, T. Mary, and R. Molina, "Adaptive precision sparse matrix-vector product and its application to Krylov solvers," *SIAM Journal on Scientific Computing*, 2023, in press. [Online]. Available: https://hal.archives-ouvertes.fr/hal-03561193

[2] D. Mukunoki and T. Imamura, "Reduced-Precision Floating-Point Formats on GPUs for High Performance and Energy Efficient Computation," in *2016 IEEE International Conference on Cluster Computing (CLUSTER)*, 2016, pp. 144–145.

[3] P. Micikevicius, D. Stosic, N. Burgess, M. Cornea, P. Dubey, R. Grisen-thwaite, S. Ha, A. Heinecke, P. Judd, J. Kamalu, N. Mellempudi, S. Oberman, M. Shoeybi, M. Siu, and H. Wu, "Fp8 formats for deep learning," 2022.

[4] D. Mukunoki, M. Kawai, and T. Imamura, "Sparse Matrix-Vector Multiplication with Reduced-Precision Memory Accessor," in *16th IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC 2023)*, 2023, (accepted).

[5] T. A. Davis and Y. Hu, "The University of Florida Sparse Matrix Collection," *ACM Trans. Math. Softw.*, vol. 38, no. 1, dec 2011.