8
$\begingroup$

As far as I understand, the order in which non-blocking point-to-point MPI messages (Isend and Irecv) are received is consistent with the order in which they are sent. Are there any techniques for giving certain messages priority over others?

For example, we have a multi-level algorithm in which the high resolution solutions are sent with non-blocking calls and computations on the coarse levels are done while the fine messages are being sent. However, when it comes time to send the low resolution solutions, we'd like those to take priority (they are essentially blocking).

I can also imagine that this might be useful for other algorithms as we move to the exascale: some messages are in the "critical path" while others are not.

|cite|improve this question
$\endgroup$
12
$\begingroup$

I think the answer to this is no. Once you've pushed them into the MPI stack, they're out of your control, and the MPI semantics govern the way the messages are sent.

You could certainly prioritize messages by queuing them in your code before sending them, and then checking frequently which are the most important to send. But I'm not at all convinced that you'll get any benefit. Is there evidence that your fine messages are not complete when you get ready to send the coarse ones? If there isn't, then you might want to investigate whether it is necessary at all in the first place.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Currently the fine messages are done being sent before we need to send the coarse messages, so for now we are OK. Having the communications overlap is a bit worrying -- maybe we'll have a problem if flops really do become free. Anyway, it might be easier to adjust our algorithm a bit instead of implementing a priority queuing system on top of MPI. We'll see! $\endgroup$ – Matthew Emmett Apr 27 '12 at 2:24
  • $\begingroup$ I'm trying to figure out how your algorithm can not care when the fine messages show up but has a hard condition on when the coarse ones do. Why not just delay the fine messages forever (and not send them)? Presumably at the end of each application/iteration, all the messages must be required? What are you worried will happen if the messages overlap? $\endgroup$ – Bill Barth Apr 27 '12 at 2:40
  • $\begingroup$ We're working on an multilevel time-parallel algorithm in which the coarse levels have serial dependencies: the coarse computation at iteration k on processor p depends on the coarse computation at iteration k on processor p-1. The fine levels are different: iteration k on processor p depends on iteration k-1 on processor p-1. If the coarse messages are slowed down the efficiency of the algorithm will go down, but overlap isn't catastrophic. $\endgroup$ – Matthew Emmett Apr 27 '12 at 20:03
7
$\begingroup$

Currently MPI has no provisions for prioritisation of messages and neither has the upcoming MPI 3.0 standard. It is up to the MPI implementation to decide how to transmit the messages. E.g. smaller messages might get sent faster because of certain bypasses in the communication machinery (highly implementation and system dependent). You might be able to exploit the fact that most MPI implementations break large messages into chunks and smaller messages might be able to slip between the chunks of the large ones. But, once again, this is highly implementation dependent and I wouldn't rely on that.

I did a simple experiment using Open MPI 1.5.3 over InfiniBand connection. The program sends one very large message (1 GiB) with MPI_Isend and then two short messages (16 bytes) with MPI_Send, and afterwards it waits for the big send to complete with MPI_Wait. On the other side an MPI_Irecv is first posted for the big receive and then two subsequent MPI_Recv operations, followed by MPI_Wait for the big receive. I was consistently able to receive the two short messages before the receive of the big message has been completed. Here is the output of my test:

[0] Rank 0 running on host1
[0] Starting big send at 0.000019s
[0] Starting small send at 0.215448s
[0] Starting small send 2 at 0.224105s
[0] Starting wait at 0.224114s
[0] Finished wait at 0.935843s
[1] Rank 1 running on host2
[1] Starting big receive at 0.000020s
[1] Starting small recv at 0.000037s
[1] Starting small recv 2 at 0.548396s
[1] Starting wait at 0.548418s
[1] Finished wait at 0.935780s

Both small sends succeed before the async send has completed as evident from the waiting time of ~700 ms. I would say that the first small receive succeeds some time (~300 ms) after the big receive has started in the background. I tried this using only MPI_COMM_WORLD or using a separate communicator for the small messages - results are the same. Nodes have one QDR IB HCA each and running with --mca btl_base_verbose 50 confirms that there are no alternative communication channels in use.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

This is not supported by MPI nor any other communication middleware I know of. This is probably because it's not supported by any hardware I know of, with the exception of Blue Gene, where there are high-priority packets for control messages that will overtake other messages under some conditions. However, these are not for general use since they only allow one to communicate 64 bytes (at least on Blue Gene/P).

The good news is that you don't need this. The overhead to implement it is not going to be worth it and you will find - assuming you ever investigate the low-level details - that not implementing priorities in the network allows MPI to deliver the best performance in most usages.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I'm not sure that I understand the last paragraph. Do you mean that by having fairness in the network MPI is able to deliver all messages sooner than if some had a higher priority than others? This seems counter intuitive, but admittedly I don't know the low-level details of MPI and modern interconnects - I can only relate this to my knowledge of IP networks and things like packet filters and priority queues. Anyway, thanks for the response! $\endgroup$ – Matthew Emmett Jul 23 '12 at 13:50
  • $\begingroup$ @MatthewEmmett See priority inversion. MPI does not know the application's message dependencies, so setting a higher priority in one message can cause it to impede its dependencies, thus making it take longer. Mitigating priority inversion is hard. $\endgroup$ – Jed Brown Jul 26 '12 at 4:37
2
$\begingroup$

It's a little odd that you mention this in the context of message order. Quoting you:

As far as I understand, the order in which non-blocking point-to-point MPI messages (Isend and Irecv) are received is consistent with the order in which they are sent.

It's worth pointing out here that MPI only guarantees that matching messages between processes will be received in the order they were sent. You really don't want this type of ordering to change, because it makes your code more understandable and takes a huge burden off of you as the application programmer.

However, if you sent messages with different tags, that changes the matching criteria, and you could easily receive the second before the first. See the second example in the relevant portion of the standard for details. I hope that if you have two pieces of your code sending simultaneously that you're already separating the coarse and fine messages using tags, and not trying to implement some protocol of your own on top of message ordering. This is second nature to most MPI programmers I know.

Anyway, assuming you're doing that, you're probably concerned that high-volume fine-grained messages are going to clog your network when you want to send the coarse ones. My general advice on this is that if it's not a performance problem that you can actually measure right now, then you really shouldn't bother addressing it yet. You seem to confirm that it's not an issue yet in one of the comments above.

One possible solution you might consider would be to use a non-blocking collective (NBC) like Bcast or Barrier to notify everyone that the coarse phase is done and ready to send its solution. In all likelihood, the NBC traffic isn't going to get prioritized, but notified processes can at least stop sending gobs of fine solutions until the coarse sends are done. NBC's will be in MPI-3 or you could try using libNBC if you can't wait that long.

Again, though, this seems like a lot of work for something that doesn't sound like it's a performance problem yet.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yes, I send the coarse messages with different tags than the fine messages. I was worried (as you guessed) that the high-volume messages might clog the network, but we haven't seen this yet -- it's just something that I wondered about. Thanks for your suggestion about NBCs. $\endgroup$ – Matthew Emmett Jul 27 '12 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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