0
$\begingroup$

I'm trying to build a pure python distributed numerical algebra computation kernel based on GPU. but after I've learnt most of the software engineering, I realise that I'm seriously lacking in computational theory. Does anyone have any recommendations for books or materials? So far I have implemented a distributed matrix multiplication, and I know that I may have to write block based matrix transpose, matrix equation solving (LU,QR), eigenvalues, matrix factorisation, non-linear least squares. Any other knowledge or paper recommendations?

$\endgroup$
8
  • 1
    $\begingroup$ Why not start with something others have already done, and where you could learn by looking at other people's code? $\endgroup$ Sep 30, 2023 at 3:01
  • $\begingroup$ Now that I can distribute the matrix through the MPI interface, the most important step is not to package the communication module?QAQ $\endgroup$ Sep 30, 2023 at 15:12
  • $\begingroup$ I don't know what "package the communication module" means. $\endgroup$ Sep 30, 2023 at 22:33
  • $\begingroup$ Professor,Thanks for your attention,I'm sorry I didn't read your details before. Currently I can distribute matrix blocks based on process groups, but I can't directly implement AB.T and A.TB, I'm wondering if it's possible to package a tree-based communication module based on peer-to-peer communication and graph theory.Implement a library similar to BLAS, MPI+graph theory.Maybe we can discuss it at slack if that's possible. $\endgroup$ Oct 1, 2023 at 7:22
  • $\begingroup$ I feel that the computational kernel is a long cycle of work,This simplifies the process for others involved in distributed numerical algebra development through an efficient communication module and a matrix block slicing module based on a device mesh(process group).I'm good at machine learning systems and deep learning. and I'm sorry to say that this is my first attempt at this job, and it looks very unprofessional! $\endgroup$ Oct 1, 2023 at 7:32

1 Answer 1

7
$\begingroup$

Building such a library from scratch is a serious undertaking. The SLATE library, which targets the functionality you're looking at, has taken about 6 years with 4-7 full-time developers, most of them having Ph.D.s in numerical computing and experience with LAPACK, ScaLAPACK, MAGMA, PLASMA, etc. And there's still some missing functionality (e.g., a non-symmetric eigen-solver). So, if your goal is working software within the next year or two, you'll want to use an existing library. SLATE and DPLASMA are the options I know of that cover your desired functionality (although, I'm unaware of Python bindings for either). I work on SLATE, and DPLASMA is developed in the same group. So, feel free to reach out.

If your goal is more educational, the literature mostly exists as research papers with an occasional survey paper. But, there's a lot of engineering work that doesn't make it into publications, so I'd still recommend spending some time playing with or contributing to an existing code. Doing a Ph.D. is the traditional way to learn a lot of this material.

For a general idea of the development of this type of library and basic techniques, you could look at the ScaLAPACK user guide and the SLATE working notes and publications. (There might be some retrospectives of ScaLAPACK out there, too.) MAGMA's publications and the LAPACK working notes mostly consider single-node systems, but have a lot of good material.

For matrix multiplication, I think "Red-Blue Pebbling Revisited: Near Optimal Parallel Matrix-Matrix Multiplication" by Kwasniewski et al. is the state of the art and discusses previous works. But, even the 2.5D algorithm can achieve a decent percent of the theoretical peak.

For LU, tournament pivoting ("CALU: a communication optimal LU factorization algorithm" by Grigori and Demmel) or threshold pivoting ("Threshold Pivoting for Dense LU Factorization" by myself) do better than traditional partial pivoting. "A survey of recent developments in parallel implementations of Gaussian elimination" by Donfack et al. and my dissertation provides a discussion on a few other approaches too. "A survey of recent developments in parallel implementations of Gaussian elimination" by Kurzak et al. provides a high-level outline of SLATE's LU and Cholesky.

For QR, you'll probably want to look at CAQR from "Communication-optimal parallel and sequential QR and LU factorizations" by Demmel et al.

For SVD and hermitian eigenvalue problems, "The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale" by Dongarra et al. is a fairly robust survey.

$\endgroup$
4
  • $\begingroup$ Thanks for your reply, I'm working on some ppts from scalapack, slate. i think a solver can be broken down into 4 pieces: theory of computation,matrix block slicing based on device mesh, process group DAG communication, result collective communication. I guess it should speed up the build if there is a unified DAG engine that manages the distributed algebraic computation process and performs the computation and data circulation links of different processes. Your reply is a better reference material .DAG example:DAGuE: A Generic Distributed DAG Engine for High Performance Computing $\endgroup$ Oct 1, 2023 at 17:54
  • $\begingroup$ Yea, that's certainly the selling point of the distributed DAG engines. The downside is your performance of non-trivial routines is depends on how smart the engine is. But, I haven't looked into that, so I can't comment on that. I haven't read the DAGuE paper, but that's what underlies DPLASMA. So, I'd guess it's good. Also, DAGuE goes by the name PARSEC now, if you're looking for the more recent work. $\endgroup$ Oct 2, 2023 at 2:59
  • $\begingroup$ Thank you for your answer, it was very helpful to me and I hope to have dinner together in the future. OVO $\endgroup$ Oct 2, 2023 at 18:25
  • $\begingroup$ Hi,I am implementing LU decomposition that supports any number of graphics cards, but binary tree communication can only handle 2 ^ n graphics cards. Can you give me some suggestions $\endgroup$ Jan 28 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.