2 Basic Structure
2.1 Data Structures
In general, programs for sparse iterative methods adopt data structures that store only information on the nonzero elements (value, row position, column position) to save memory. This chapter describes the sparse matrix storage format used in this library.
2.1.1 Compressed Row Storage (CRS) Format
The CRS format (compressed row storage) packs the nonzero elements row by row and stores their values and column indices in one-dimensional arrays. For this purpose, a row pointer (rowptr) recording the starting position of each row in the one-dimensional arrays is used. All indices are 0-based (the C and Fortran APIs can also use 1-based indices; Usage). In parallel processing, the matrix is partitioned by rows, and each process stores a contiguous block of rows (see “MPI Decomposition” in “Usage” for details). In this case, rowptr is given in local numbering, with the first owned row of each process as 0, and the column indices (crsCol) are given as global indices of the whole matrix. The column indices within each row are assumed to be in ascending order.
- Matrix structure (row and column indices count from 0)
One Process
- Rank 0 process (rows 0 to 3)
Nonzero values of the matrix ::
Row pointer ::
Column indices of nonzero values ::
Two Processes
- Rank 0 process (rows 0 to 1)
Nonzero values of the matrix ::
Row pointer ::
Column indices of nonzero values ::
- Rank 1 process (rows 2 to 3)
Nonzero values of the matrix ::
Row pointer ::
Column indices of nonzero values ::
2.2 GPUs, MPI Ranks and Data
PARCEL assigns one MPI rank to one computing resource, partitions the coefficient matrix and the vectors by rows, and gives each rank its part. MPI handles the communication between ranks, and SYCL handles the parallelism within a rank (kernels on the device for GPUs, threads of the OpenMP backend for CPUs). A build with MPI (the default for C++, C and Fortran) uses this structure even when it runs as a single process. A single-process version without MPI can also be built (“Build without MPI”).
The computing resource assigned to one rank (hereafter the device) is one of the following. See the glossary for the names of the hardware and environments.
- One GPU
- One partition of a GPU divided by MIG (NVIDIA; below)
- The GPU part of an APU (AMD Instinct MI300A; below)
- A group of CPU cores (OpenMP backend)
2.2.1 Row-Block Partitioning
Let be the global number of rows. Rank is responsible for the contiguous rows to (0-based, both ends inclusive), and its local number of rows is . Each rank holds the following.
| Data | Part held by each rank | Length |
|---|---|---|
| Coefficient matrix | CRS of the owned rows (rowptr, column indices, values). Column indices are passed as global indices |
rowptr is ; column indices and values are the number of nonzeros in the owned rows |
| Solution , right-hand side , eigenvectors | The part corresponding to the owned rows | (EigenVec of ks_arnoldi is at least ; vectors are written) |
| Preconditioner matrix | The part for the owned rows (built by the solver from the local rows of ) | — |
The number of rows may differ between ranks (non-uniform partitioning). The row blocks of all ranks together must cover without overlaps or gaps. They need not be in the order of the rank numbers. Each rank must have at least one row (a rank with 0 rows is not supported). set_crsMat() in C++ and the C and Fortran APIs check this (“MPI Decomposition” in “Usage”). The local number of rows can be obtained with parcel::matrix::n_local().
2.2.2 Mapping One Rank to One Device
Each rank creates its own SYCL queue (an in-order queue) and places the matrix and the vectors on the device of that queue. The bundled samples select the default device with sycl::queue q{sycl::default_selector_v, sycl::property::queue::in_order{}};. On a node with several GPUs, all ranks may select the same GPU by default, so restrict the GPUs visible to each rank to one before starting. For example, place the following wrapper between mpirun and the program.
#!/bin/bash
# gpu_bind.sh: assign GPU R to the rank R within the node
R=${OMPI_COMM_WORLD_LOCAL_RANK:-${PMIX_RANK:-0}}
export CUDA_VISIBLE_DEVICES=$R # NVIDIA
export HIP_VISIBLE_DEVICES=$R # AMD (MI300A)
unset ROCR_VISIBLE_DEVICES
exec "$@"mpirun -n 4 ./gpu_bind.sh ./runOn AMD GPUs, do not set HIP_VISIBLE_DEVICES and ROCR_VISIBLE_DEVICES at the same time. The two act in sequence: after ROCR_VISIBLE_DEVICES restricts the GPUs to one, HIP_VISIBLE_DEVICES tries to select the R-th of them and fails, and that rank gets no GPU and runs on the CPU OpenMP backend.
Check that each rank uses the intended device by its device name (the verification sample parcel_krylov_sample_verify.cpp prints one line with the device name for each rank at the start). If even one rank falls back to the CPU OpenMP backend, the numbers stay correct, but all ranks wait for that rank in the MPI_Allreduce of the dot products and the whole run becomes slower by orders of magnitude. For example, on an environment with one GPU per node (Miyabi-G), placing two ranks on one node makes the second rank fall back to the CPU. This mistake cannot be noticed from the numerical results alone.
2.2.2.1 MIG (NVIDIA Multi-Instance GPU)
MIG divides one GPU into partitions (instances) by SM and memory, and presents each partition as an independent GPU. From PARCEL’s point of view, one partition is one device, and as with a whole GPU, one partition is assigned to one rank. The device name of a partition includes its size (profile), such as NVIDIA GH200 120GB MIG 2g.24gb.
When several partitions are used, assign each rank to a partition with gpu_bind.sh above. Depending on the allocation, partitions of different sizes (profiles) may be mixed in the same job (2g.24gb and 1g.24gb on Miyabi-G). Partitions of different sizes run at different speeds, and the other ranks wait for the rank on the slower partition in the reduction of the dot products, so for performance measurements use partitions of the same size or whole GPUs.
2.2.2.2 APU (AMD Instinct MI300A)
The MI300A is an APU that places CPU cores and a GPU in one package and shares HBM between them. On PS-B, 1 NUMA node = 1 vnode = 1 APU (24 cores, one GPU, 124 GB), so assign one APU to one rank and request one chunk per rank in PBS with select=<number of ranks>:ncpus=24:mpiprocs=1:ngpus=1. With select=1:ngpus=4, only one vnode is allocated and only one GPU is available.
From SYCL, the GPU part of an APU appears as one device. As with other GPUs, PARCEL places the matrix and the vectors on the device in SYCL buffers and copies them to and from host buffers for the halo exchange (there is no separate path for APUs). Since the host and device memory is physically the same HBM, the host-side arrays held by the user’s program (such as the CRS arrays) and the device-side copies are taken from the same capacity of each APU.
On CPUs, one rank is responsible for a group of OpenMP threads. Place the threads of a rank within one NUMA node (or socket). The number of partitions of the blocked kernels and the default number of blocks of the block Jacobi preconditioner are determined by the number of threads per rank (“Blocking” in the “Optimization” chapter).
The recommended mapping for each environment is shown below.
| Environment | Assigned to one rank | Threads per rank |
|---|---|---|
| s86 GPU (V100 ×4 / node) | One GPU | 12 |
| Aquarius (A100) | One GPU | 9 |
| Miyabi-G (GH200; one GPU / node) | One GPU (= one node). With MIG, one partition (2g.24gb or 1g.24gb) and 18 cores |
72 (18 with MIG) |
| PS-B (MI300A ×4 / node) | One APU (one GPU part and 24 cores) | 6 |
| s86 CPU (Xeon Gold 6242R 20 cores ×2) | 5 cores | 5 |
| Miyabi-C (Xeon Max 9480) | 14 cores | 14 |
| PS-A (Xeon 6980P) | 14 cores (pinned to a NUMA node with I_MPI_PIN_DOMAIN of Intel MPI) |
14 |
| Odyssey (A64FX) | One CMG (12 cores) | 12 |
2.2.3 What set_crsMat() Does
parcel::matrix::set_crsMat() (the MPI version) receives the CRS of the owned rows and performs the following (set_crsMat() in the API Reference). Both steps are collective operations called on all ranks. Before that, it checks the input (“Setting the Matrix” in “Usage”), and if the input is broken, all ranks throw the same std::invalid_argument.
- Renumbers the column indices to local indices. The nonzeros of each row are reordered so that the columns of the own rank (index , 0 to ) come first and the columns of other ranks come after them. A column of another rank is renumbered to , where is its position in the list of column indices of other ranks referenced by the owned rows, sorted in ascending order with duplicates removed. The caller’s arrays of column indices and values are overwritten at this point (“Setting the Matrix” in “Usage”).
- Exchanges the ranges owned by all ranks (, ) with
MPI_Alltoall, compares them with the list from step 1, and builds the table of which rows’ values are sent to which rank and received from which rank (the halo exchange table).
After this, the values and column indices are transferred to the device.
2.2.4 Sparse Matrix-Vector Product and Halo Exchange
A vector that is multiplied by inside a solver has, after its local entries, an area for the values received from other ranks (the halo). The number of halo entries is the length of the list in step 1 above (pcg and power print it as nadd = at the start). Before every sparse matrix-vector product, the following halo exchange is performed.
- The values to send are packed into a send buffer on the device and copied to the host.
MPI_IsendandMPI_Irecvare performed on the host buffers, and their completion is waited for.- The received values are copied to the device and written into the halo of the vector (entries from on).
Since communication goes through host buffers, a GPU-aware (CUDA-aware, etc.) MPI is not required. When run with one rank, the halo is empty and no communication occurs. The Jacobi preconditioner performs the same halo exchange in every Jacobi iteration, while the point Jacobi and block Jacobi preconditioners do not communicate (Preconditioners chapter). Dot products and norms reduce the partial sums of the ranks with MPI_Allreduce.
2.3 Precision Configurations
PARCEL lets you specify the precision in which data are held (data precision) separately from the precision of arithmetic (computation precision), and further separately for the preconditioner and for the rest. There are four types: parcel_fp16 (half precision), parcel_float (single precision), parcel_double (double precision) and parcel_doubledouble (double-double [12,13], equivalent to quadruple precision). The precision template arguments can be omitted, and the default precision is parcel_double (what can be omitted: the types of parcel::matrix<> and parcel::vector<>, the four computation-precision arguments of the classes, and the data-precision arguments of solver() that cannot be deduced from the actual arguments; the defaults of Todd_basis and Teven_basis of pcagmres are the same type as Tbasis). The syntax is shown in “Specifying Precision” in “Usage”, and the meaning of each template argument in “Class Template Arguments (Computation Precision)” and “Template Arguments of solver() (Data Precision)” in the API Reference. This section summarizes the overall picture of the specification and the representative configurations.
2.3.1 Where Precision Is Specified
| Category | Where to specify | Macro in the samples |
|---|---|---|
| Computation precision (SpMV, vector operations, dot products) | Class template arguments Tspmv, Taxpy, Tdot |
parcel_solver_calc_type (the same type is given to all three) |
| Computation precision of the preconditioner | Class template argument Tprecon |
parcel_solver_calc_precon_type |
| Data precision (matrix, vectors) | T of parcel::matrix<T> and parcel::vector<T>, and the template arguments Tmat, Tvecx, Tvecb, Tvec of solver() (Teigen_val, Teigen_vec for the eigenvalue solvers) |
parcel_solver_data_type |
| Data precision of the preconditioner | Template arguments Tprecon_mat (preconditioner matrix) and Tprecon_vec (preconditioner vectors) of solver() |
parcel_solver_data_precon_mat_type, parcel_solver_data_precon_vec_type |
The macros are used by the bundled verification sample (tests/verify/parcel_default.hpp, where all defaults are parcel_double) and by the C and Fortran wrapper (capi/wrapper_parcel_sycl.cpp; defaults in capi/parcel_capi_default.hpp); the library itself looks only at the template arguments. When using C++ directly, different types may be given to the template arguments for each operation. pgmres and pcagmres have additional arguments for the precision of orthogonalization, the basis and the Hessenberg matrix. These are explained in “Precision of Orthogonalization and of the Basis” in the Linear Solvers chapter.
2.3.2 13 Representative Configurations
The 13 configurations used in the regression tests and their convergence tolerances in the regression tests are shown below. “Lower” and “raise” in the table are relative to double precision (double). Blank cells are parcel_double.
| Configuration | Computation precision | Computation precision of the preconditioner | Data precision | Data precision of the preconditioner | What is lowered / raised | Tolerance in the regression tests |
|---|---|---|---|---|---|---|
double |
(reference) | 1e-9 | ||||
calcF16 |
FP16 | Lowers arithmetic to FP16 | 1e-3 | |||
dataF16 |
FP16 | FP16 | Lowers arithmetic and the storage of the matrix and vectors to FP16 | 1e-2 | ||
precon_calcF16 |
FP16 | Lowers only the arithmetic of the preconditioner to FP16 | 1e-9 (relaxed for some solvers) | |||
precon_dataF16 |
FP16 | Lowers only the storage of the preconditioner matrix and vectors to FP16 | 1e-9 | |||
precon_allF16 |
FP16 | FP16 | Lowers the arithmetic and storage of the preconditioner to FP16 | 1e-9 (relaxed for some solvers) | ||
calcF |
FP32 | Lowers arithmetic to FP32 | 1e-6 | |||
dataF |
FP32 | FP32 | Lowers arithmetic and storage to FP32 | 1e-6 | ||
precon_calcF |
FP32 | Lowers only the arithmetic of the preconditioner to FP32 | 1e-9 (1e-6 for ks_arnoldi) |
|||
precon_dataF |
FP32 | Lowers only the storage of the preconditioner to FP32 | 1e-9 | |||
precon_allF |
FP32 | FP32 | Lowers the arithmetic and storage of the preconditioner to FP32 | 1e-9 (1e-6 for ks_arnoldi) |
||
calcDD |
dd | Raises arithmetic to double-double | 1e-9 | |||
dataDD |
dd | dd | Raises arithmetic and storage to double-double | 1e-9 |
The properties of the configurations are as follows. The achievable accuracy and the restrictions are detailed in “Known Limits at Low Precision” and “double-double”.
- Lowering the data precision reduces the memory of the matrix and vectors and the amount of halo communication and of transfers between the host and the device. Lowering only the computation precision does not change the amount of memory. The
data*configurations also lower the computation precision to the same type. - The tolerance differs between configurations because double-precision tolerances cannot be reached at low precision. Only
dataF16is one digit looser thancalcF16because holding the vectors in FP16 makes the recurrence residual drift away from the true residual (“Recurrence Residual and True Residual”). - The six configurations that lower only the preconditioner keep the main computation in double precision and treat the preconditioner as an approximation; most solvers reach the same tolerance as in double precision. However, with FP16 as the computation precision of the preconditioner,
pbicgstabandks_arnoldido not reach 1e-9 (about 1e-5 forpbicgstaband 1e-3 forks_arnoldi). - To lower the preconditioner data to single precision for speed (
precon_dataF), build the Jacobi preconditioner without on-the-fly computation (-DPARCEL_JACOBI_ONTHEFLY=0). The same applies to NVIDIA GPUs (including V100), without ladder splitting. The effect and the additional memory are shown in “Mixed Precision” in the “Performance” chapter (no speedup on A64FX). - double-double is meant to reduce the rounding error of arithmetic; the guideline for the tolerance is the same as in double precision.
- With FP16 data or computation precision, do not use the Cholesky QR variants of
pcagmres(the variant that does not form ,CAGMRES_Q_IMPLICIT, and the moment method). The variants that form can be used (“Known Limits at Low Precision”).
When the verification sample is built with -DPARCEL_RUNTIME_PRECISION, 9 of the above configurations (double, calcF16, dataF16, precon_calcF16, calcF, dataF, precon_calcF, calcDD, dataDD) are put into one executable and selected with the environment variable PARCEL_PRECISION (run-time options of the verification sample). The four configurations that change the data precision of the preconditioner are specified with compile-time macros.
2.3.3 Precisions Available in Each Language
How precision is specified, and which configurations are available, depend on the language.
| Language | How to specify | Available precisions |
|---|---|---|
| C++ | Template arguments of the classes and solver() (“Specifying Precision” in “Usage”) |
All combinations, including the 13 configurations. Can differ per solver and per call |
| C / Fortran | Compile-time macros of the wrapper capi/wrapper_parcel_sycl.cpp (parcel_solver_data_type, etc.) |
One configuration per built wrapper; cannot be changed at run time. Input and output arrays are double (double / real(c_double)) |
| Python | None | Double only (data and arithmetic are parcel_double). Input and output arrays are float64 |
The Python package is double only because precision is decided at build time by C++ template arguments, and only instantiated combinations can be used. The native layer of Python (python/src/parcel_py.cpp) instantiates only the double combination. Making all 13 configurations selectable from Python would require instantiating each of them, increasing the build time and the library size accordingly. In addition, NumPy has no type corresponding to double-double. To use mixed precision from Python, write the solver call in C++, or call the C API built with precision macros through ctypes or the like.
2.3.4 Integer Type
Integers such as row indices, column indices, numbers of rows and numbers of nonzeros are held, separately from the floating-point precisions, in two types: global quantities in PARCEL_INT, and indices within one rank in PARCEL_LINT. There is one width of each per build; it cannot be chosen per solver or per matrix (see “Integer Type” in the Installation chapter).
| Type | Default | Used for |
|---|---|---|
PARCEL_INT (global indices) |
int64_t |
The number of global rows, the row range of each rank (nstart, nend), the row-pointer and column-index arrays passed to set_crsMat() (global column indices), allocation of vectors, the global column indices used to build the halo-exchange tables, and the C and Fortran APIs |
PARCEL_LINT (rank-local indices) |
int32_t |
The CRS on the device (row pointers and column indices renumbered within the rank), the indices of the elements packed for the halo exchange, and the SpMV and preconditioner kernels |
User programs deal only with PARCEL_INT. set_crsMat() receives PARCEL_INT arrays, renumbers the column indices within the rank (the own rows as 0 to local rows - 1, the halo after them), copies them into PARCEL_LINT arrays and sends them to the device. During the copy, 4 (n + nnz) extra bytes are used temporarily on the host (n is the number of local rows, nnz the number of nonzeros of the rank). If the row-pointer and column-index arrays of the CRS in the user program are declared with the type PARCEL_INT, the build can be switched without changing the source.
In the default configuration, the column indices and row pointers of the CRS on the device take 4 bytes per element; one nonzero of a double-precision matrix takes 12 bytes (8 bytes for the value and 4 bytes for the column index), and one grid point of a 3D 7-point stencil matrix takes 88 bytes. Holding the global quantities in 64 bits does not increase the memory traffic of SpMV or of the preconditioners.
The ranges of matrices that can be handled are as follows.
- The number of global rows and nonzeros: the range of
PARCEL_INT. With the default 64 bits there is no practical limit - The number of nonzeros owned by one rank, and the sum of the local rows and the halo elements: each within the range of
PARCEL_LINT, that is, at most (about 2.1 billion) with the default 32 bits
If even one rank exceeds the range of PARCEL_LINT, set_crsMat() throws the same std::overflow_error on all ranks and stops. The message asks to rebuild with -DPARCEL_LOCAL_INT64 or to use more MPI ranks. Normally, use more ranks to reduce the nonzeros per rank. If that is not possible, build with -DPARCEL_LOCAL_INT64 to make PARCEL_LINT 64-bit. The CRS on the device then takes 8 bytes per index element: 16 bytes per nonzero of a double-precision matrix and 120 bytes per grid point of a 3D 7-point stencil matrix. The memory traffic of SpMV grows, and bandwidth-bound SpMV and the Jacobi preconditioner become slower. std::overflow_error is also thrown when a CRS built by a preconditioner (such as the L and U factors of block Jacobi) has more nonzeros than the original matrix and exceeds the range (in this case only the ranks that exceed it throw).
With -DPARCEL_INT32, both PARCEL_INT and PARCEL_LINT are 32-bit. The arrays passed to set_crsMat() on the host are halved and no copy is made. The CRS on the device and the performance are the same as in the default configuration. The number of global rows (the largest column index) must be at most ; if a larger matrix is passed, set_crsMat() and others throw std::overflow_error (asking to remove -DPARCEL_INT32) and stop.
The C and Fortran APIs receive these integers as 64-bit integers (parcel_int = int64_t in C, integer(parcel_int_kind) in Fortran) regardless of PARCEL_INT (“Setting the Matrix” for C in “Usage”). If the wrapper is built with -DPARCEL_INT32 and a value does not fit in 32 bits, the call returns PARCEL_ERR_ARG.
For large problems, watch out for integer overflow. A 32-bit signed integer holds values up to (about 2.15 billion). For a 3D 7-point stencil matrix the number of nonzeros is about 7 times the number of rows, so the global number of nonzeros exceeds the 32-bit range at about 310 million rows (NX of about 675), and the global number of rows at about 2.15 billion rows (NX of about 1290). Row pointer values are serial numbers of nonzeros, so they overflow before the row count does. Computed in 32 bits, such values wrap to negative or small numbers, and the program reads or writes out of bounds or silently returns wrong results. For this reason the default of the global index PARCEL_INT is 64 bits in v1.2, and set_crsMat() and others detect out-of-range values with std::overflow_error. In user programs too, keep the global numbers of rows and nonzeros, the row pointers, and index computations using them (nstart + i, grid point numbers , etc.) in PARCEL_INT (64 bits). A product of two 32-bit int values overflows at the multiplication even if it is assigned to a 64-bit variable.
The index within a rank, PARCEL_LINT, on the other hand stays 32 bits by default, for the speed of the local kernels (SpMV, preconditioners).
- Less data is read by the bandwidth-bound kernels. A CRS in double takes 12 bytes per nonzero (8 for the value + 4 for the column index), and 16 bytes with 64-bit column indices. For the SpMV of a 3D 7-point stencil matrix, the matrix data read per grid point grows from 88 to 120 bytes (about 1.4 times). The times of SpMV and the Jacobi preconditioner are roughly proportional to the data read, so they become slower accordingly.
- 32-bit integer arithmetic is fast on GPUs. The integer units of NVIDIA and AMD GPUs are basically 32-bit, and 64-bit integer multiplications and additions are split into several instructions. In SpMV, where index computations make up much of the instructions, 64-bit indices increase the instruction count and register usage.
- 32 bits suffice as long as the number of nonzeros of one rank does not exceed . For a 3D 7-point stencil, for example, up to about 300 million local rows per rank can be handled. Beyond that, first increase the number of ranks (reduce the rows per rank).