Variante di Broadcast

Back to    Contents

Previous :  Reduction con double      Next : I Risultati   Up to : Benchmark collettivi   

Questo test è stato aggiunto al programma goptest  solo di recente per implementare le raccomandazioni, in campo di misurazioni di prestazione collettive, riportare nel documento Accurately Measuring MPI Broadcasts in a Computational Grid di B. de Supinski and N. Karonis. Questo documento evidenzia come il classico test Broadcast Round non sia accurato in tutte le situazioni, in quanto permette un certo parallelismo di esecuzione che falsa il risultato finale. Inoltre questo parallelismo non è misurabile a priori, in quanto si presenta con intensità e frequenza non deterministiche (vedi Broadcast Round per dettagli).

Questa variante di Broadcast permette di evitare completamente l'eventuale parallelismo (pipelining) introducendo una sorta di sincronizzazione, il cui overhead è possibile misurare, e quindi sottrarre al tempo finale ottenuto. Concettualmente l'algoritmo è il seguente : 

1. si misura il tempo necessario al processo root (pid 0) per spedire e ricevere indietro un messaggio ad un certo processo pid i. Il tempo viene diviso per due ottenendo una stima del tempo di spedizione in una sola direzione;
2. root fa partire il tempo ed esegue una Broadcast;
3. il processo pid i, appena ricevuto il messaggio in Broadcast, spedisce a root un messaggio di conferma ricezione;
4. root ferma il tempo non appena riceve il messaggio da pid i, ottenendo un certo Ti;
5. si ripete questo procedimento per tutti i processi;
6. il più grande dei Ti è il risultato del test.

Gli autori di questo  hanno provato questo algoritmo con varie implementazioni di MPI_Broadcast (lineare, ad albero binomiale, ecc) ed hanno mostrato come esso dia risultati più coerenti rispetto alla Broadcast classica, dove non sempre l'implementazione teoricamente migliore risulta la più veloce anche dai test.

Nella   goptest questo algoritmo viene implementato così : 

• per prima cosa si misura la latenza di trasmissione punto punto tra root ed gli altri processi 

    MPI_Barrier(MPI_COMM_WORLD);
    if ( my_pid == root_proc )/*se sono root spedisco*/
        {
        int rep;

        time = MPI_Wtime();
        for (rep = 0; rep < reps; rep++) /*ripeto la spedizione molte volte*/
            {
            MPI_Recv(&dummy, 0, MPI_BYTE, proc, 0, MPI_COMM_WORLD, &status);
            MPI_Send(&dummy, 0, MPI_BYTE, proc, 0, MPI_COMM_WORLD);
            }
        time_latency = (MPI_Wtime() - time); /* division by 'reps' occurs later */
        }
    else if ( my_pid == proc )/*se non sono root prima ricevo e poi spedisco*/
        {
        int rep;

        for (rep = 0; rep < reps; rep++)
            {
            MPI_Send(&dummy, 0, MPI_BYTE, root_proc, 0, MPI_COMM_WORLD);
            MPI_Recv(&dummy, 0, MPI_BYTE, root_proc, 0, MPI_COMM_WORLD, &status);
            }
        }

• poi si misura il tempo per fare un broacast e ricevere la "ricevuta di ritorno" da un particolare processo 

    MPI_Barrier(MPI_COMM_WORLD);

    if ( my_pid == root_proc ) /* I am the root process */
        {
        /* priming the line */
        MPI_Bcast(lval, len, MPI_INT, root_proc, MPI_COMM_WORLD);
        MPI_Recv(&dummy, 0, MPI_BYTE, proc, acker_tag, MPI_COMM_WORLD, &status);

        /* do the actual measurement */
        time = MPI_Wtime();
        for (i = 0; i < reps; i++)
            {
            MPI_Bcast(lval, len, MPI_INT, root_proc, MPI_COMM_WORLD);
            MPI_Recv(&dummy, 0, MPI_BYTE, proc, acker_tag, MPI_COMM_WORLD,&status);
            }
        time = MPI_Wtime() - time; /* division by 'reps' occurs later */
        }
    else /* I am the ACKer or any process other than root */
        {
        if ( my_pid == proc ) /* I am the ACKER */
            for (i = 0; i < reps + 1; i++) /* "+ 1" because we primed the line */
                {
                MPI_Bcast(lval, len, MPI_INT, root_proc, MPI_COMM_WORLD);
                MPI_Send(&dummy, 0, MPI_BYTE, root_proc, acker_tag, MPI_COMM_WORLD);
                }
        else /* I am neither root nor the ACKer */
            for (i = 0; i < reps + 1; i++) /* "+ 1" because we primed the line */
                MPI_Bcast(lval, len, MPI_INT, root_proc, MPI_COMM_WORLD);
        }

• si calcola il tempo 

      (time - time_latency)/reps = OLi;

   

• si ripete per tutti i processi e si tiene il OLi più grande.

Come vedremo(I Risultati, Conclusioni) questo test è particolarmente interessante per noi in quanto, al contrario di BroadcastRound, da risultati molto simili sia per MPICH che per MPICH-G2, indipendentemente dalla dimensione del messaggio passato. Questo conferma, come era prevedibile, che entrambi implementano la primitiva MPI_Broadcast nello stesso modo (cioè con albero binomiale), e che quindi le ragioni delle differenze di  prestazioni evidenziate con gli altri test dipendono da qualche altra caratteristica di MPICH-G2 che proveremo ad individuare nelle  Conclusioni.

Previous : Reduction con double     Next :  I Risultati     Up to : Benchmark collettivi      

Back to Contents