File ParallelNumeric.h

↰ Parent directory (ADS/parallel)

The parallel products of matrices, beyond the book: the products by a vector of the sparse matrices CsrMatrix and SellMatrix [see File CsrMatrix.h and File SellMatrix.h], and the product of dense matrices of gemm() [see File DenseMatrix.h], on the threads of an executor [see File Executor.h], with the same results as the sequential ones, bit for bit: each entry of the output is computed by the same sequential code, with the same order of the sums, by one thread.

Definition (ADS/parallel/ParallelNumeric.h)

Detailed Description

  • multiply( ex , A , x , y ) for a CsrMatrix cuts the rows into 4 p parts of equal :math:` rows + nonzeros , the cost of a row being its nonzeros plus the store of its sum (the diagonal of the merge path of Merrill and Garland: the part q ends at the first row i with :math: i + mathit{start}( i ) geq q ( m + nnz ) / B , found by a binary search, since :math: i + mathit{start}( i ) ` grows with i), and runs the product of each part on one thread. A row is never split among threads, which would change the order of its sums; a row longer than a part is therefore a part of its own, and only a matrix with a few rows holding most of the nonzeros is unbalanced.

  • multiply( ex , A , x , y ) for a SellMatrix cuts its chunks of C rows in the same way by their places, padding included.

  • gemm( ex , … ) runs the loops of the sequential gemm() on the panels of NC columns of B and on the slices of KC of the common dimension, and parallelizes within them as BLIS does: the panel :math:` K_C times N_C ` of B is packed once, its micro-panels shared among the threads, and each thread takes a range of the rows of C (whole micro-panels of MR rows, as many to each thread as they go), packs its blocks of MC rows of A in its own buffer and runs the micro-kernels on them and on the shared panel of B (the loop of the blocks of A in parallel, which Smith et al. found the one that scales on the processors whose cores have private second levels). Each entry of C sees the same slices and the same micro-kernel as in gemm(); the small products, which gemm() computes by another path, go to it on one thread. The products by a vector move :math:` 12 nnz + 8 ( m + n ) ` bytes and are bound by the bandwidth of the memory, so that p threads gain at most the ratio of the bandwidth of the socket to that of one core.

The contracts [see File Contract.h]: those of the sequential products. D. Merrill, M. Garland, Merge-based parallel sparse matrix-vector multiplication, International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 678-689, 2016, doi:10.1109/SC.2016.57

    1. Smith, R. A. van de Geijn, M. Smelyanskiy, J. R. Hammond, F. G. Van Zee, Anatomy of high-performance many-threaded matrix multiplication, IEEE International Parallel and Distributed Processing Symposium (IPDPS), 1049-1059, 2014, doi:10.1109/IPDPS.2014.110

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions