0
$\begingroup$

The LU parallel computation theories I've seen are based on $M\times N$ mesh computations, is there a theory for one dimensional device mesh LU parallel decomposition?

For example, $A$ is a matrix. we have p device, we decompose $A = [A_1, ..., A_p]$. That means, if we have only 2-3 devices involved in the computation, then the LU can only be computed by row-parallelism or column-parallelism.

Improve this question
$\endgroup$
1
  • $\begingroup$ It's too hard to implement a blocked-LU using MPI.QAQ $\endgroup$
    – Haitao Xiao
    Commented Oct 12, 2023 at 8:48

1 Answer 1

Reset to default
1
$\begingroup$

The analysis for the 2d process or device grid case carries over to the 1d grid case, just set one of your dimensions to 1.

However, using a 2d grid will scale significantly better. So, I'd recommend implementing it with support for a 2d grid since it's only a little more complicated to implement. The one case where it's significantly more complicated is if you're trying combine partial pivoting with task-based parallelism. But, for example, tournament pivoting doesn't have that issue.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This looks like it's time to look into your SLATE and MAGMA source code.QAQI've done distributed matrix multiplication, is iterative parallelism going to use the MPI virtual process topology, because my row and column MPI topology can't easily do LU iterative parallel process group communication $\endgroup$
    – Haitao Xiao
    Commented Oct 13, 2023 at 5:46
  • $\begingroup$ I see what my problem was, I didn't consider the relationship between point-to-point communication and communication topology and iteration step size.It's easy to implement a TSLU $\endgroup$
    – Haitao Xiao
    Commented Oct 14, 2023 at 12:40
  • $\begingroup$ communication-avoiding LU and QR with panel is too hard to mek, It is diffcult than TSLU and TSLR.Thanks for you teachingQAQ $\endgroup$
    – Haitao Xiao
    Commented Oct 16, 2023 at 9:59
  • $\begingroup$ thanks for tournament pivoting, It is helpful. $\endgroup$
    – Haitao Xiao
    Commented Oct 17, 2023 at 6:36

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.