Tag matching logic

MPI 태그 매칭 규칙과 Eager·Rendezvous 프로토콜

MPI 표준은 송신 측의 send 연산과 수신 측의 receive를 연결하는 태그 매칭 규칙을 정의합니다. 매칭하려면 communicator, 사용자 태그, source rank, destination rank가 맞아야 합니다. 수신자는 사용자 태그와 source rank에 와일드카드를 지정할 수 있고 destination rank도 와일드 조건으로 표현될 수 있습니다.

둘 이상의 send/receive 메시지 봉투 쌍이 매칭될 수 있으면, 가장 먼저 게시된 send와 가장 먼저 게시된 receive를 포함하는 쌍을 사용해야 합니다. 그렇다고 태그가 생성 순서대로 소비된다는 뜻은 아닙니다. 먼저 생성된 태그가 규칙을 만족하지 못하면 나중 태그가 먼저 소비될 수 있습니다.

송신 메시지가 수신 측에 도착할 때 대응하는 receive가 이미 게시되어 있으면 expected message, 아직 없으면 unexpected message라고 합니다. 통신 라이브러리는 두 상황에 서로 다른 매칭 방식을 흔히 사용합니다.

MPI 구현은 라이브러리 메모리 사용량을 낮추기 위해 일반적으로 Eager와 Rendezvous 두 프로토콜을 사용합니다. Eager에서는 송신자가 send를 처리할 때 전체 메시지를 보내고, `send_cq`에 완료가 도착하면 송신 버퍼를 재사용할 수 있습니다.

Rendezvous에서는 송신자가 먼저 태그 매칭 헤더와 필요하면 일부 데이터만 보냅니다. 대응하는 수신 버퍼가 게시되면 응답자가 헤더 정보를 사용해 해당 버퍼로 직접 RDMA READ를 시작합니다. 송신 버퍼는 fin 메시지를 받은 뒤에야 재사용할 수 있습니다.

==================
Tag matching logic
==================

The MPI standard defines a set of rules, known as tag-matching, for matching
source send operations to destination receives.  The following parameters must
match the following source and destination parameters:

*        Communicator
*        User tag - wild card may be specified by the receiver
*        Source rank – wild car may be specified by the receiver
*        Destination rank – wild

The ordering rules require that when more than one pair of send and receive
message envelopes may match, the pair that includes the earliest posted-send
and the earliest posted-receive is the pair that must be used to satisfy the
matching operation. However, this doesn’t imply that tags are consumed in
the order they are created, e.g., a later generated tag may be consumed, if
earlier tags can’t be used to satisfy the matching rules.

When a message is sent from the sender to the receiver, the communication
library may attempt to process the operation either after or before the
corresponding matching receive is posted.  If a matching receive is posted,
this is an expected message, otherwise it is called an unexpected message.
Implementations frequently use different matching schemes for these two
different matching instances.

To keep MPI library memory footprint down, MPI implementations typically use
two different protocols for this purpose:

1.        The Eager protocol- the complete message is sent when the send is
processed by the sender. A completion send is received in the send_cq
notifying that the buffer can be reused.

2.        The Rendezvous Protocol - the sender sends the tag-matching header,
and perhaps a portion of data when first notifying the receiver. When the
corresponding buffer is posted, the responder will use the information from
the header to initiate an RDMA READ operation directly to the matching buffer.
A fin message needs to be received in order for the buffer to be reused.

Posted receive와 Unexpected message 목록 구현

태그 매칭 구현은 posted receive list와 unexpected message list라는 두 종류의 매칭 객체를 사용합니다. 애플리케이션은 MPI receive 루틴으로 수신 버퍼를 posted receive list에 게시하고, MPI send 루틴으로 송신 메시지를 게시합니다. posted receive list의 머리는 하드웨어가 유지할 수 있으며 소프트웨어는 이 목록의 그림자 사본을 유지해야 합니다.

send가 시작되어 수신 측에 도착했을 때 미리 게시된 receive가 없으면 메시지는 소프트웨어로 전달되어 unexpected message list에 들어갑니다. 미리 게시된 receive가 있으면 필요할 경우 rendezvous 처리를 포함해 매칭을 수행하고 지정된 수신 버퍼에 데이터를 전달합니다. 이 구조는 수신 측 MPI 태그 매칭과 계산을 겹쳐 실행할 수 있게 합니다.

새 receive가 게시되면 통신 라이브러리는 먼저 소프트웨어 unexpected message list에서 일치 항목을 찾습니다. 항목이 있으면 소프트웨어 제어 프로토콜로 사용자 버퍼에 데이터를 전달합니다. UCX 구현은 데이터 크기에 따라 eager 또는 rendezvous를 사용합니다.

unexpected 목록에 일치 항목이 없고 하드웨어가 전체 pre-posted receive list를 유지하며 추가 공간도 있으면 새 receive를 하드웨어로 넘깁니다. 소프트웨어 그림자 목록은 MPI cancel 처리뿐 아니라, receive를 하드웨어로 넘기는 동시에 일치하는 unexpected 메시지가 하드웨어에서 소프트웨어로 이동하는 경쟁 상태를 감지하는 데도 사용됩니다.

Tag matching implementation
===========================

There are two types of matching objects used, the posted receive list and the
unexpected message list. The application posts receive buffers through calls
to the MPI receive routines in the posted receive list and posts send messages
using the MPI send routines. The head of the posted receive list may be
maintained by the hardware, with the software expected to shadow this list.

When send is initiated and arrives at the receive side, if there is no
pre-posted receive for this arriving message, it is passed to the software and
placed in the unexpected message list. Otherwise the match is processed,
including rendezvous processing, if appropriate, delivering the data to the
specified receive buffer. This allows overlapping receive-side MPI tag
matching with computation.

When a receive-message is posted, the communication library will first check
the software unexpected message list for a matching receive. If a match is
found, data is delivered to the user buffer, using a software controlled
protocol. The UCX implementation uses either an eager or rendezvous protocol,
depending on data size. If no match is found, the entire pre-posted receive
list is maintained by the hardware, and there is space to add one more
pre-posted receive to this list, this receive is passed to the hardware.
Software is expected to shadow this list, to help with processing MPI cancel
operations. In addition, because hardware and software are not expected to be
tightly synchronized with respect to the tag-matching operation, this shadow
list is used to detect the case that a pre-posted receive is passed to the
hardware, as the matching unexpected message is being passed from the hardware
to the software.