¿Cómo se compara el costo computacional de una operación mpi_allgather con una operación de recopilación / dispersión?

11

Estoy trabajando en un problema que se puede paralelizar usando una sola operación mpi_allgather o una operación mpi_scatter y una mpi_gather. Estas operaciones se llaman dentro de un ciclo while, por lo que se pueden llamar muchas veces.

En la implementación con un esquema MPI_allgather, estoy reuniendo un vector distribuido en todos los procesos para la resolución de matrices duplicadas. En la otra implementación, reúno el vector distribuido en un único procesador (el nodo raíz), resuelvo el sistema lineal en este procesador y luego vuelvo a dispersar el vector solución en todos los procesos.

Tengo curiosidad por saber si el costo de una operación de recolección total es significativamente mayor que las operaciones de dispersión y recolección combinadas. ¿La longitud del mensaje juega un papel importante en su complejidad? ¿Varía entre implementaciones de mpi?

Editar:

Paul
fuente
Describa la estructura de la comunicación y los tamaños involucrados. Un MPI_Scatterseguido por MPI_Gatherno proporciona la misma comunicación semántica que MPI_Allgather. ¿Quizás haya redundancia involucrada cuando expresa la operación de cualquier manera?
Jed Brown
Paul, Jed tiene razón, ¿te refieres a MPI_Gatherseguido de a MPI_Bcast?
Aron Ahmadia
@JedBrown: agregué un poco más de información.
Paul
@AronAhmadia: No creo que deba usar un MPI_Bcast porque estoy enviando una parte del vector, a cada proceso, no todo el vector. Mi razonamiento es que un mensaje más corto será más rápido de enviar que un mensaje más grande, en general. ¿Esto tiene sentido?
Paul
¿La matriz ya está distribuida de forma redundante? ¿Ya está factorizado? ¿Comparten varios procesos los mismos cachés y bus de memoria? (Eso afectaría la velocidad de resolución de sistemas redundantes). ¿Qué tan grandes / caros son los sistemas? ¿Por qué resolver en serie?
Jed Brown

Respuestas:

9

Primero, la respuesta exacta depende de: (1) uso, es decir, argumentos de entrada de función, (2) calidad y detalles de implementación de MPI, y (3) el hardware que está utilizando. A menudo, (2) y (3) están relacionados, como cuando el proveedor de hardware optimiza MPI para su red.

En general, fusionar colectivos MPI es mejor para mensajes más pequeños, ya que los costos iniciales pueden no ser triviales y la sincronización que conlleva bloquear colectivos debe minimizarse si hay una variación en el tiempo de cómputo entre llamadas. Para mensajes más grandes, el objetivo debe ser minimizar la cantidad de datos que se envían.

Por ejemplo, en teoría, MPI_Reduce_scatter_blockdebería ser mejor que lo MPI_Reduceseguido MPI_Scatter, aunque el primero a menudo se implementa en términos del segundo, de modo que no haya una ventaja real. Existe una correlación entre la calidad de la implementación y la frecuencia de uso en la mayoría de las implementaciones de MPI, y los proveedores obviamente optimizan las funciones para las cuales esto es requerido por el contrato de la máquina.

Por otro lado, si uno está en un Blue Gene, el MPI_Reduce_scatter_blockuso MPI_Allreduce, que hace más comunicación que MPI_Reducey MPI_Scattercombinado, en realidad es bastante más rápido. Esto es algo que descubrí recientemente y es una violación interesante del principio de autoconsistencia de rendimiento en MPI (este principio se describe con más detalle en las "Pautas de rendimiento de MPI autoconsistentes" ).

En el caso específico de dispersión + reunión versus reunión total, considere que en la primera, todos los datos deben ir hacia y desde un solo proceso, lo que lo convierte en el cuello de botella, mientras que en la reunión general, los datos pueden entrar y salir de todos los rangos inmediatamente , porque todos los rangos tienen algunos datos para enviar a todos los demás. Sin embargo, enviar datos desde todos los nodos a la vez no es necesariamente una buena idea en algunas redes.

Finalmente, la mejor manera de responder a esta pregunta es hacer lo siguiente en su código y responder la pregunta por experimento.

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

Una opción aún mejor es hacer que su código lo mida experimentalmente durante las dos primeras iteraciones, luego use el que sea más rápido para las iteraciones restantes:

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}
Jeff
fuente
Esa no es una mala idea ... cronometra a ambos y determina cuál es más rápido.
Paul
El hardware de los entornos HPC más modernos optimiza muchas llamadas MPI. A veces esto lleva a incrementos de velocidad increíbles, otras veces a comportamientos extremadamente opacos. ¡Ten cuidado!
meawoppl
@Jeff: Me acabo de dar cuenta de que omití un detalle importante ... Estoy trabajando con un clúster en el Centro de Computación Avanzada de Texas, donde usan una red de topología de árbol gordo. ¿Afectaría eso a la diferencia en el rendimiento entre los enfoques de reunión total y transmisión conjunta?
Paul
@Paul Topology no es el factor dominante aquí, pero un árbol gordo tiene un ancho de banda de bisección sustancial, lo que debería hacer que todo sea barato. Sin embargo, reunir siempre debe ser más barato que allgather. Sin embargo, para mensajes más grandes, podría ser menor que un factor de 2.
Jeff
5

Jeff tiene toda la razón acerca de que la única manera de estar seguro es medir: después de todo, somos científicos, y esta es una pregunta empírica, y brinda excelentes consejos sobre cómo implementar tales mediciones. Permítanme ahora ofrecer una visión contraria (o, tal vez, complementaria).

Hay que hacer una distinción entre escribir un código para ser ampliamente utilizado y ajustarlo a un fin específico. En general, estamos haciendo lo primero: crear nuestro código para que a) podamos usarlo en una amplia variedad de plataformas, yb) el código se pueda mantener y ampliar en los años venideros. Pero a veces estamos haciendo lo otro: tenemos un año de asignación en una máquina grande, y estamos aumentando el conjunto requerido de simulaciones grandes y necesitamos una cierta línea de base de rendimiento para obtener lo que necesitamos hacer durante el momento de la asignación otorgada.

Cuando estamos escribiendo código, hacer que sea ampliamente utilizable y mantenible es mucho más importante que reducir un pequeño porcentaje del tiempo de ejecución en una máquina en particular. En este caso, lo correcto es casi siempre usar la rutina que mejor describa lo que desea hacer: esta es generalmente la llamada más específica que puede hacer y que hace lo que desea. Por ejemplo, si un allgather o allgatherv directo hace lo que desea, debe usar eso en lugar de deshacerse de las operaciones de dispersión / recolección. Las razones son que:

  • El código ahora representa más claramente lo que está tratando de hacer, lo que lo hace más comprensible para la siguiente persona que viene a su código al año siguiente sin tener idea de lo que se supone que debe hacer el código (esa persona bien podría ser usted);
  • Las optimizaciones están disponibles a nivel MPI para este caso más específico que no están en el caso más general, por lo que su biblioteca MPI puede ayudarlo; y
  • Tratar de tirar el tuyo probablemente sea contraproducente; incluso si funciona mejor en la máquina X con la implementación de MPI Y.ZZ, puede funcionar mucho peor cuando se muda a otra máquina o actualiza su implementación de MPI.

En este caso bastante común, si descubre que algún colectivo MPI funciona de manera irrazonablemente lenta en su máquina, lo mejor que puede hacer es presentar un informe de error con el proveedor de mpi; no desea complicar su propio software tratando de evitar el código de la aplicación, lo que debería corregirse correctamente en el nivel de la biblioteca MPI.

Sin embargo . Si está en modo "sintonización": tiene un código que funciona, debe aumentar a escalas muy grandes en un corto período de tiempo (por ejemplo, una asignación de un año), y ha perfilado su código y descubrió que esta parte particular de su código es un cuello de botella, entonces tiene sentido comenzar a realizar estas afinaciones muy específicas. Esperemos que no sean partes a largo plazo de su código; idealmente, estos cambios permanecerán en alguna rama específica del proyecto de su repositorio, pero es posible que deba hacerlos. En ese caso, la codificación de dos enfoques diferentes que se distinguen por directivas de preprocesador, o un enfoque de "autoajuste" para un patrón de comunicación específico, puede tener mucho sentido.

Por lo tanto, no estoy en desacuerdo con Jeff, solo quiero agregar un contexto sobre cuándo debería preocuparse lo suficiente por esas preguntas de rendimiento relativo para modificar su código para tratarlo.


fuente
Creo que estoy más interesado en la portabilidad que en la optimización en este momento, pero siempre tengo curiosidad por saber si hay otra implementación que sea igualmente portátil pero más rápida :)
Paul