I just can't find... why is my code seg-faulting?

Is giving my a seg-fault right at the ending point where I do the final gather from the MASTER processor.

Any help will be welcome!

Since this is an exercise, I don't want to give you an answer; I want to help you find it yourself. I hope you understand and appreciate that.

First, if you comment out the
the code won't crash; this confirms your diagnosis on where your program actually crashes.

So, let's check the parameters one by one. See man MPI_Gather for the details.

• my_CC
  This is the send buffer.
• rows_per_proc[my_rank]*NN
  This is the number of elements in the send buffer. Umm.. Are you sure about this value?
• MPI_DOUBLE
  This is the data type of elements in the send buffer.
• CC
  This is the receive buffer. It's only used in the receiving process, but you really should set it to NULL on others.
  If you use warnings when compiling, e.g mpicc -Wall, you'll see the note about CC.
• rows_per_proc[my_rank]*NN
  This is the number of elements per process in the receive buffer. Umm.. Are you sure about this value?
• MPI_DOUBLE
  This is the data type of elements in the receive buffer. (MPI can do some data type conversions on the fly.)
• MASTER
  Receiving process. You've defined this as zero, which means the root process. Quite okay.
• MPI_COMM_WORLD
  Gather is done from the entire group; okay.

Perhaps you should reconsider your MPI_Gather call. Perhaps you should take a look at the MPI_Gather example first? Pay attention to why the example uses MPI_Gatherv instead. Also, remember that the receive buffer will contain the data from each of the pp processes, including the receive process itself.

Although MPI_Gatherv() is pretty much perfect for this case, you can try to get your program working by replacing it with MPI_Send()s on all but the master process, and corresponding MPI_Recv()s on the master process. If you do that, it would probably help you understand which kind of MPI_Gather()/MPI_Gatherv() call you need to do it all at once.

Hope this helps.

I don't know MPI myself, but I expected to be able to understand an example this easy from the documentation and help the OP. The documentation is less helpful than I would have expected. There are plenty of details documented, but basic concepts are largely missing or buried.

So I think you could have explained a few of the basic concepts the OP seems to have misunderstood or pointed to some of the key spots in the doc that a beginner might easily miss. That still isn't doing the exercise.

Those parameter descriptions are a bit short of understandable, especially recvcount. The OP seems to have misunderstood recvbuf as well.

Nearby that page there is a section much more helpful within
http://www.mpi-forum.org/docs/mpi-11...69.html#Node69

Notice where it says
That gives you a direct understanding of how recvcount and recvbuf are used by MPI_Gather.

Eduardo, is the receive buffer you allocated compatible with MPI_Gather using it as the text I just quoted describes?

That's a very good suggestion.

Only after you find the documentation that tells you what MPI_Gather()/MPI_Gatherv() really do, rather than the documentation that ambiguously documents their parameters.

Also, all the places the original code says
(double **) malloc( something *sizeof(double))
are incorrect. That should be
(double **) malloc( something *sizeof(double*))
That error just wastes memory. It won't cause any crash nor wrong answer. But it is still an error.

BTW, I haven't looked through the details of your actual matrix product logic, nor do I know best technique for distributing a matrix product. But even trivial thought regarding data flow should tell you it is lame to parallelize the problem by dividing into groups of rows. You should parallelize by dividing the solution matrix into nearly square rectangular chunks.

You're right. The OpenMPI manual pages have much better descriptions and explanations of each function, and has examples for most of the functions. There is a very good MPI tutorial at Lawrence Livermoore.

I agree. You can then distribute either rectangular parts of the left and right matrices, or full rows of the left matrix and full columns of the right matrix. It'd be quite interesting to compare the total costs of each method..

For very small matrices, say < 20x20, I'd just broadcast the entire left and right side matrices to each process, have them do some of the computational work, into a result matrix which is initialized to zeros. Then you can reduce them using sum operation, to get the actual result matrix -- and it does not matter which process has done which part of the work, as long as all of the computations have been done.

It is always a good idea to think about the operation at hand:

result[row][column] = sum over i: left[row][i] * right[i][column]

Note that transposing the right matrix makes the computations a lot more efficient, since the data is then consecutive in memory.

1 members found this post helpful.

I was having trouble visualizing an underlying communication system for MPI efficient enough that there could be any savings in elapsed time vs. having one process do the whole job (matrix multiply). The ratio of work to communication goes up some when the matrix is larger. But still not enough to make sense.

I was thinking of a rectangular division of processes into intersecting teams (of course I don't know how hard teams are to set up in MPI). Given the total number of processes, computer the integer square root, then the integer quotient for the two team dimensions: Example, 23 processes. square root of 23 is 4. 23/4 is 5. So use a 4x5 set of intersecting teams and waste the extra 3 processes.

Each process would be a member of one of four teams of 5 and one of five teams of 4. Each team of 5 would multiply all of the A rows by one quarter of the B columns. Each team of 4 would multiply one fifth of the A rows by all the B columns. So each process acting simultaneously in two teams would multiply one fifth of the A rows times one quarter of the B columns.

Based on the OPs design, each process would first invent data for its twentieth of A rows and its twentieth of B columns.

Then the 5 row teams in parallel would each go through 4 team members in sequence to exchange/keep row data, so each member of a row team then had the rows of the entire team.

Then the 4 column teams in parallel would each go through 5 team members in sequence to exchange column data, and as each chunk of column data was exchanged, each process could multiply it by all the rows of its row team and store those results and discard that column chunk before going on to the next.

Then all the results could be handed to the master, which would get them in a strange sequence (by rectangular chunk, rather than by row). If it just needs to display the results it just needs an accessor function that takes row and column number and grabs the right element from the chunks oriented result. If it needs significant further work, it would need to reorder the result. But that is likely less expensive than using MPI comm enough more to deliver the result in final sequence.

If you add up all the data flow (especially if comm by teams in parallel really is in parallel) you should see enough less total work to more than compensate for idling a few processes.

If the matrix dimension isn't divided evenly by the (adjusted) number of processes, that leads to two level special case setup of dividing the matrix almost evenly by number of teams and dividing the result almost evenly by members per team. That would be twice as tricky as the adjustments the OP got only partially correct in his division by rows in the first post.

Nominal Animal:

Yes, off course I appreciate that

Your hint wether if I should use MPI_Gather or not, was really close. I already solved the entire problem and figured out A LOT of my original mistakes. Most of them relied in two great issues:

- Definition of the data structures used for collective communiction calls.
- Memory allocation issues.

Thank you very much for your first post

I am still reading / understanding the other post so I can give a cool answer to all of them

johnsfine:

I agree u.u that is why I have a book for this and I also used the tutorial from LLNL that Nominal Animal recomended on his second post (awesome recommendation Nominal Animal, thank you for that).

Quick question to johnsfine:

What is the OP?

Original poster. The person who wrote the first post of the current thread (you).

When multiple people answering the same thread start discussing subtopics among themselves, a short hand way to refer back to whoever started the topic is often needed.

1 members found this post helpful.

Matrix multiplication is just an example operation here, often used in distributed computing courses because it is easy to understand, but also illustrates well the difficulties in efficient data partitioning (for distributed computing).

There is also the fact that you should always design MPI programs to do computations while communications are in progress, preparing for the next operation (or even better, the operation after that one). That way the cost of the communication is neglible. I have designed certain spatial partitioning schemes to allow this for classical molecular dynamics simulations, including Monte Carlo MD simulations, but there has been very little interest in it. Usually people just throw more hardware -- low-latency infiniband, more computing nodes -- at it rather than fix the logic in their programs. I do understand their concern, however: it does increase complexity, and a lot of programmers (especially physicists) are unfamiliar with concepts like asynchronous I/O. (For spatially distributing Monte Carlo MD simulations I've been thus far unable to retain perfect detail balance, although the error is extremely small. The distribution mechanism does for example totally eliminate all spatial boundary errors.)

Extremely easy. You simply agree (between all participating processes in a team) to create a communicator (corresponds to a group of communicating processes) using the MPI_Comm_ functions, and use the team communicators instead of MPI_COMM_WORLD.
There are also MPI_Cart_ functions to create and manage Cartesian communications topologies, so creating the communicators according to your example would be very easy.

That is one workable strategy, but note that the wall clock duration of the operation is measured by the slowest team (or member).

It is usually more efficient to assign the work in a smorgasbord fashion: divide the work into much more chunks than there are workers, and have each worker grab the next available chunk, and work on it. The downside is of course the loss of data locality, at least in theory.

In practice, if the master process knows (or the workers tell the master) which sub-matrices the worker asking for more work already has locally, it can use a simple greedy algorithm to minimize the number of sub-matrices transmitted. This is much more robust, since if a worker is delayed for any reason, the system will automatically accommodate that.

Funnily enough, the code is not at all complex when using this kind of smorgasbord or worker pool mechanism (even tends to be quite compact!), but the logic is often hard to grasp for someone unfamiliar with the idea.

That's actually quite a common thing, and MPI has facilities to handle that gracefully.

For example, you can tag each data chunk with an arbitrary integer. In the receiving end, you can set up asynchronous receives for a specific tag (from a specific process or any process), and then just check or wait until they've all completed. You can define a sparse sub-matrix data type, and use that type to receive the data directly into the correct locations of the result matrix. (If the matrix is a continuous array, you only need one type per each different sub-matrix size. If all the sub-matrices are of the same size, one custom type is sufficient.)

johnsfine:

Now that I have finished the exercise entirely, I realized were my errors were! For example, that error in the dynamic memory allocation was enoying and I actually fixed it, so thank you.

I read your proposition to a parallel aproach for the domain decomposition of this problem in post number 5 and yes, it is awesome! The reason I did it the way I did is because the instructor wanted us to do it, specifically like that, so I decided to go with the flow

Nominal Animal:

Yes! I actually implemented to store the transposed of the matrix B and wrote a serial version of the code, for both of them, transposed and not transposed... the execution times decreases dramatically for matrix sizes up to 4000 x 4000.

I would like to thank both of you guys since your suggestions really taugh me a lot!

For me, this assignment was really illustrative since I also learned how to use gdb for debugging in parallel environments, which results very useful when the problems get really complicated.

Regards!