Wie wird Barriere in Message-Passing-Systemen implementiert?

Question

Was ich verstehe, ist, dass ein Master-Prozess eine Nachricht an alle anderen Prozesse sendet. Alle anderen Prozesse senden im Gegenzug eine Nachricht an den Master-Prozess. Wäre das genug für eine Schranke um zu arbeiten? Wenn nicht, was braucht es mehr?

Answer 1

Werfen wir einen Blick auf OpenMPI's implementation of barrier. Während andere Implementierungen geringfügig abweichen können, sollte das allgemeine Kommunikationsmuster identisch sein.

Als erstes ist anzumerken, dass MPI's Barriere keine Setup-Kosten hat: Ein Prozess, der einen MPI_Barrier Anruf erreicht, wird blockiert, bis alle anderen Mitglieder der Gruppe auch MPI_Barrier angerufen haben. Beachten Sie, dass MPI nicht erfordert, dass sie denselben Anruf erreichen, nur einen Anruf an MPI_Barrier. Da die Gesamtzahl der Knoten in der Gruppe jedem Prozess bereits bekannt ist, muss daher kein zusätzlicher Zustand zum Initialisieren des Anrufs verteilt werden.

Nun wollen wir an einem gewissen Code aussehen:

/* 
* Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana 
*       University Research and Technology 
*       Corporation. All rights reserved. 
* Copyright (c) 2004-2005 The University of Tennessee and The University 
*       of Tennessee Research Foundation. All rights 
*       reserved. 
* Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, 
*       University of Stuttgart. All rights reserved. 
* Copyright (c) 2004-2005 The Regents of the University of California. 
*       All rights reserved. 
* Copyright (c) 2012  Oak Ridge National Labs. All rights reserved. 
* [...] 
*/ 

[...] 

/* 
* barrier_intra_lin 
* 
* Function: - barrier using O(N) algorithm 
* Accepts: - same as MPI_Barrier() 
* Returns: - MPI_SUCCESS or error code 
*/ 
int 
mca_coll_basic_barrier_intra_lin(struct ompi_communicator_t *comm, 
           mca_coll_base_module_t *module) 
{ 
    int i; 
    int err; 
    int size = ompi_comm_size(comm); 
    int rank = ompi_comm_rank(comm); 

Zuerst werden alle Knoten (mit Ausnahme der mit Rang 0, der Wurzelknoten) senden eine Benachrichtigung, dass sie die Barriere auf den Wurzelknoten erreicht haben:

/* All non-root send & receive zero-length message. */ 

    if (rank > 0) { 
     err = 
      MCA_PML_CALL(send 
         (NULL, 0, MPI_BYTE, 0, MCA_COLL_BASE_TAG_BARRIER, 
          MCA_PML_BASE_SEND_STANDARD, comm)); 
     if (MPI_SUCCESS != err) { 
      return err; 
     } 

Danach wartet auf sie blockieren Benachrichtigung von der Wurzel:

 err = 
      MCA_PML_CALL(recv 
         (NULL, 0, MPI_BYTE, 0, MCA_COLL_BASE_TAG_BARRIER, 
          comm, MPI_STATUS_IGNORE)); 
     if (MPI_SUCCESS != err) { 
      return err; 
     } 
    } 

der Wurzelknoten im ergänzt die andere Seite der Kommunikation. Zuerst es blockiert, bis es n-1 eingegangenen Mitteilungen (eines von jedem Knoten in der Gruppe, außer sich selbst, da er in der Sperr Anruf ist bereits):

else { 
     for (i = 1; i < size; ++i) { 
      err = MCA_PML_CALL(recv(NULL, 0, MPI_BYTE, MPI_ANY_SOURCE, 
            MCA_COLL_BASE_TAG_BARRIER, 
            comm, MPI_STATUS_IGNORE)); 
      if (MPI_SUCCESS != err) { 
       return err; 
      } 
     } 

Sobald alle Meldungen eingetroffen, sendet er die Nachrichten aus, dass jeder Knoten wartet, signalisiert, dass jeder die Barriere erreicht hat, wonach sie die Barriere Anruf lässt sich:

 for (i = 1; i < size; ++i) { 
      err = 
       MCA_PML_CALL(send 
          (NULL, 0, MPI_BYTE, i, 
           MCA_COLL_BASE_TAG_BARRIER, 
           MCA_PML_BASE_SEND_STANDARD, comm)); 
      if (MPI_SUCCESS != err) { 
       return err; 
      } 
     } 
    } 

    /* All done */ 

    return MPI_SUCCESS; 
} 

So ist die Kommunikationsmuster ist zunächst ein n:1 von allen Knoten an der Wurzel und dann ein 1:n von der Wurzel zurück zu allen Knoten. Um den Root-Knoten nicht mit Anfragen zu überlasten, erlaubt OpenMPI die Verwendung eines Baum-basierten Kommunikationsmusters, aber die Grundidee ist die gleiche: Alle Knoten benachrichtigen die Root beim Eintritt in die Barriere, während der Root die Ergebnisse aggregiert und jeden informiert bereit fortzufahren.

Answer 2

Nein, das ist nicht genug. Sobald der Master-Prozess eine Nachricht an alle anderen Prozesse gesendet hat, die ihn darüber informiert, dass er die Barriere erreicht hat und alle anderen Prozesse geantwortet haben, dass auch sie die Barriere erreicht haben, weiß nur der Master-Prozess, dass alle Prozesse die Barriere erreicht haben. In diesem Szenario wäre eine weitere Nachricht vom Master zu den anderen Prozessen notwendig.

Ich mache keinen Anspruch auf die tatsächliche Implementierung von MPI-Barrieren in irgendeiner Bibliothek, insbesondere suggeriere ich nicht, dass die beschriebene Abfolge von Nachrichten in der Praxis verwendet wird, nur dass es in der Theorie defizitär ist.