Parallel matrix product

In order to compute the product between 2 matrices A and B (nxm dimension) in a parallel mode, I have the following restrictions: the server sends to each client a number of rows from matrix A, and a number of rows from matrix B. This cannot be changed. Further the clients may exchange between each other information so that the matrices product to be computed, but they cannot ask the server to send any other data.

This should be done the most efficient possible, meaning by minimizing the number of messages sent between processes - considered as an expensive operation - and by doing the small calculations in parallel, as much as possible.

From what I have researched, practically the highest number of messages exchanged between the clients is n^2, in case each process broadcasts its lines to all the others. Now, the problem is that 开发者_StackOverflowif I minimize the number of messages sent - this would be around log(n) for distributing the input data - but the computation then would only be done by one process, or more, but anyhow, it is not anymore done in parallel, which was the main idea of the problem.

What could be a more efficient algorithm, that would compute this product?

(I am using MPI, if it makes any difference).

To compute the matrix product C = A x B element-by-element you simply calculate C(i,j) = dot_product(A(i,:),B(:,j)). That is, the (i,j) element of C is the dot product of row i of A and column j of B.

If you insist on sending rows of A and rows of B around then you are going to have a tough time writing a parallel program whose performance exceeds a straightforward serial program. Rather, what you ought to do is send rows of A and columns of B to processors for computation of elements of C. If you are constrained to send rows of A and rows of B, then I suggest that you do that, but compute the product on the server. That is, ignore all the worker processors and just perform the calculation serially.

One alternative would be to compute partial dot-products on worker processors and to accumulate the partial results. This will require some tricky programming; it can be done but I will be very surprised if, at your first attempt, you can write a program which outperforms (in execution speed) a simple serial program.

(Yes, there are other approaches to decomposing matrix-matrix products for parallel execution, but they are more complicated than the foregoing. If you want to investigate these then Matrix Computations is the place to start reading.)

You need also to think hard about your proposed measures of efficiency -- the most efficient message-passing program will be the one which passes no messages. If the cost of message-passing far outweighs the cost of computation then the no-message-passing implementation will be the most efficient by both measures. Generally though, measures of the efficiency of parallel programs are ratios of speedup to number of processors: so 8 times speedup on 8 processors is perfectly efficient (and usually impossible to achieve).

As stated yours is not a sensible problem. Either the problem-setter has mis-specified it, or you have mis-stated (or mis-understood) a correct specification.

Something's not right: if both matrices have n x m dimensions, then they can not be multiplied together (unless n = m). In the case of A*B, A has to have as many columns as B has rows. Are you sure that the server isn't sending rows of B's transposed? That would be equivalent to sending columns from B, in which case the solution is trivial.

Assuming that all those check out, and your clients do indeed get rows from A and B: probably the easiest solution would be for each client to send its rows of matrix B to client #0, who reassambles the original matrix B, then sends out its columns back to the other clients. Basically, client #0 would act as a server that actually knows how to efficiently decompose data. This would be 2*(n-1) messages (not counting the ones used to reunite the product matrix), but considering how you already need n messages to distribute the A and B matrices between the clients, there's no significant performance loss (it's still O(n) messages).

The biggest bottleneck here is obviously the initial gathering and redistribution of the matrix B, which scales terribly, so if you have fairly small matrices and a lot of processes, you might just be better off calculating the product serially on the server.

I don't know if this is homework. But if it is not homework, then you should probably use a library. One idea is scalapack

http://www.netlib.org/scalapack/scalapack_home.html

Scalapack is writtten in fortran, but you can call it from c++.