tag_matching.rst 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
  1. ==================
  2. Tag matching logic
  3. ==================
  4. The MPI standard defines a set of rules, known as tag-matching, for matching
  5. source send operations to destination receives. The following parameters must
  6. match the following source and destination parameters:
  7. * Communicator
  8. * User tag - wild card may be specified by the receiver
  9. * Source rank – wild car may be specified by the receiver
  10. * Destination rank – wild
  11. The ordering rules require that when more than one pair of send and receive
  12. message envelopes may match, the pair that includes the earliest posted-send
  13. and the earliest posted-receive is the pair that must be used to satisfy the
  14. matching operation. However, this doesn’t imply that tags are consumed in
  15. the order they are created, e.g., a later generated tag may be consumed, if
  16. earlier tags can’t be used to satisfy the matching rules.
  17. When a message is sent from the sender to the receiver, the communication
  18. library may attempt to process the operation either after or before the
  19. corresponding matching receive is posted. If a matching receive is posted,
  20. this is an expected message, otherwise it is called an unexpected message.
  21. Implementations frequently use different matching schemes for these two
  22. different matching instances.
  23. To keep MPI library memory footprint down, MPI implementations typically use
  24. two different protocols for this purpose:
  25. 1. The Eager protocol- the complete message is sent when the send is
  26. processed by the sender. A completion send is received in the send_cq
  27. notifying that the buffer can be reused.
  28. 2. The Rendezvous Protocol - the sender sends the tag-matching header,
  29. and perhaps a portion of data when first notifying the receiver. When the
  30. corresponding buffer is posted, the responder will use the information from
  31. the header to initiate an RDMA READ operation directly to the matching buffer.
  32. A fin message needs to be received in order for the buffer to be reused.
  33. Tag matching implementation
  34. ===========================
  35. There are two types of matching objects used, the posted receive list and the
  36. unexpected message list. The application posts receive buffers through calls
  37. to the MPI receive routines in the posted receive list and posts send messages
  38. using the MPI send routines. The head of the posted receive list may be
  39. maintained by the hardware, with the software expected to shadow this list.
  40. When send is initiated and arrives at the receive side, if there is no
  41. pre-posted receive for this arriving message, it is passed to the software and
  42. placed in the unexpected message list. Otherwise the match is processed,
  43. including rendezvous processing, if appropriate, delivering the data to the
  44. specified receive buffer. This allows overlapping receive-side MPI tag
  45. matching with computation.
  46. When a receive-message is posted, the communication library will first check
  47. the software unexpected message list for a matching receive. If a match is
  48. found, data is delivered to the user buffer, using a software controlled
  49. protocol. The UCX implementation uses either an eager or rendezvous protocol,
  50. depending on data size. If no match is found, the entire pre-posted receive
  51. list is maintained by the hardware, and there is space to add one more
  52. pre-posted receive to this list, this receive is passed to the hardware.
  53. Software is expected to shadow this list, to help with processing MPI cancel
  54. operations. In addition, because hardware and software are not expected to be
  55. tightly synchronized with respect to the tag-matching operation, this shadow
  56. list is used to detect the case that a pre-posted receive is passed to the
  57. hardware, as the matching unexpected message is being passed from the hardware
  58. to the software.