Log-log escala paralela / gráficos de eficiencia

17

Gran parte de mi propio trabajo gira en torno a mejorar la escala de los algoritmos, y una de las formas preferidas de mostrar la escala paralela y / o la eficiencia paralela es trazar el rendimiento de un algoritmo / código sobre el número de núcleos, por ejemplo

artificial parcela de escalamiento paralelo

donde el eje representa el número de núcleos y el eje alguna métrica, por ejemplo, el trabajo realizado por unidad de tiempo. Las diferentes curvas muestran eficiencias paralelas de 20%, 40%, 60%, 80% y 100% a los 64 núcleos respectivamente.Xy

Sin embargo, desafortunadamente, en muchas publicaciones, estos resultados se trazan con una escala log-log , por ejemplo, los resultados en este o este artículo. El problema con estas parcelas log-log es que es increíblemente difícil evaluar la escala / eficiencia paralela real, p. Ej.

ingrese la descripción de la imagen aquí

Que es la misma parcela que el anterior, pero con la escala log-log. Tenga en cuenta que ahora no hay gran diferencia entre los resultados de 60%, 80% o 100% de eficiencia en paralelo. He escrito un poco más extensamente sobre esto aquí .

Así que aquí está mi pregunta: ¿Qué razón hay para mostrar resultados en la escala log-log? Yo uso regularmente escala lineal para mostrar mis propios resultados, y regularmente conseguir martillado por los árbitros diciendo que mis propios resultados escalado paralelo / eficiencia no se ven tan bien como el (log-log) los resultados de los demás, sino para la vida de mí No puedo ver por qué debería cambiar los estilos de trazado.

Pedro
fuente

Respuestas:

16

Actualmente estamos escribiendo un documento que contiene una serie de parcelas comparables, y que más o menos teníamos el mismo problema. El papel se trata de la comparación de la escala de diferentes algoritmos sobre el número de núcleos, que oscila entre 1 y hasta 100k en un BlueGene. La razón de usar LogLog-parcelas en esta situación es el número de órdenes de magnitud involucrados. No hay forma de que se puedan trazar 6 órdenes de magnitud en una escala lineal.

Y, de hecho, al trazar el tiempo sobre el número de núcleos en el registro, los algoritmos no son muy distinguibles, como puede ver en el siguiente diagrama. Horarios de una serie de algoritmos sobre loglog escala.  Los diferentes algoritmos son difíciles de distinguir.

mipag=T1/ /(pagTpag)T1Tpagpagpagmipagpag

mipag=TrmiF/ /(pagTpag)TrmiF

Al trazar la eficiencia paralela relativa en una escala de semilog muestra claramente la escala de un algoritmo, y también muestra cómo los algoritmos se desempeñan relativamente entre sí. Relativa eficiencia en paralelo de un número de algoritmos más el número de núcleos.

olenz
fuente
2
X
Tenga en cuenta que las parcelas no se ven casi tan impresionante como otros gráficos de escalamiento, cuando dejan bastante rápidamente en el logscale. Además, se puede, en teoría, también trazar la eficiencia en una parcela loglog ver más detalles en el borde derecho. Tenga en cuenta sin embargo, que esto significa que se mira en detalle con eficiencias muy bajas, lo que probablemente no es de gran interés.
olenz
14

Georg Hager escribió sobre esto en engañar a las masas - Truco 3: La escala logarítmica es su amigo .

Si bien es cierto que las parcelas log-log de gran escala no son muy discerniendo en el extremo superior, que permiten mostrar la escala a través de muchas más órdenes de magnitud. Para ver por qué esto es útil, considere un problema en 3D con el refinamiento regular. En una escala lineal, puede mostrar razonablemente rendimiento en aproximadamente dos órdenes de magnitud, por ejemplo, 1024, 8192 núcleos de núcleos y 65.536 núcleos. Es imposible para el lector saber a partir de la trama si se ejecutó algo más pequeño, y de manera realista, la trama en su mayoría sólo compara los dos más grandes carreras.

Ahora, suponiendo que podamos ajustar 1 millón de celdas de cuadrícula por núcleo en la memoria, esto significa que después de una fuerte escala dos veces por un factor de 8, todavía podemos tener 16k celdas por núcleo. Eso sigue siendo un tamaño considerable subdominio y podemos esperar que muchos algoritmos para ejecutar de manera eficiente allí. Hemos cubierto el espectro visual del gráfico (1024 a 65.536 núcleos), pero ni siquiera hemos entrado en el régimen en el fuerte de escala se hace difícil.

Supongamos, en cambio, que comenzamos en 16 núcleos, también con 1 millón de celdas de cuadrícula por núcleo. Ahora, si escalamos a 65536 núcleos, solo tendremos 244 celdas por núcleo, lo que será mucho más exigente. Un eje logarítmico es la única forma de representar claramente el espectro de 16 núcleos a 65536 núcleos. Por supuesto, aún puede usar un eje lineal y tener un título que diga "los puntos de datos para 16, 128 y 1024 núcleos se superponen en la figura", pero ahora está usando palabras en lugar de la figura para mostrar.

Una escala log-log también permite que su escala se "recupere" de los atributos de la máquina, como ir más allá de un solo nodo o rack. Depende de usted si esto es deseable o no.

Jed Brown
fuente
Xy
1
Es mucho más difícil escalar fuertemente un solo problema por un factor de 4096 que escalar dos tamaños diferentes de problemas por un factor de 64 cada uno. En el ejemplo que he dado, es fácil de hacer los dos casos independientes muestran mejor que 95% de eficiencia, pero tienen el caso combinado sola tener eficacia inferior al 30%. En la ciencia y la industria, no hay ninguna razón predeterminada para el tiempo deseado a su vez-en torno a caer dentro del rango de tamaños estrecha donde el algoritmo es "cómodo".
Jed Brown
¡Estoy completamente de acuerdo en que escalar de uno a miles es el gran desafío! La razón por la que considero que diferentes magnitudes son problemas diferentes es que significará cosas diferentes para el usuario final. Por ejemplo, en MD, la mayoría de los biólogos no tienen un BlueGene en el sótano, pero tienen algunas estaciones de trabajo multi-núcleo, o incluso una concesión desde hace algún tiempo en un clúster de tamaño moderado (pequeño número de nodos), y personas que buscan en general Los problemas de CFD, sin embargo, no se preocuparán mucho por el caso de un solo nodo porque el problema no cabe en la memoria. No se trata de la comodidad del algoritmo, sino de la configuración del usuario.
Pedro
2

Estoy de acuerdo con todo lo Jed tenía que decir en su respuesta, pero quería añadir lo siguiente. Me he convertido en un fanático de la forma en que Martin Berzins y sus colegas muestran la escala para su marco Uintah. Trazan una escala débil y fuerte del código en los ejes log-log (usando el tiempo de ejecución por paso del método). Creo que muestra cómo el código escala bastante bien (aunque la desviación de la escala perfecta es un poco difícil de determinar). Consulte las páginas 7 y 8, por ejemplo, las figuras 7 y 8 de este * artículo. También dan una tabla con los números correspondientes a cada figura de escala.

Una ventaja de este (no o al menos mucho que no se puede rebut) es que una vez que usted ha proporcionado los números, no hay mucho de un revisor puede decir.

* J. Luitjens, M. Berzins. “Mejora del rendimiento del Uintah: A Gran Escala-adaptativa Meshing Computational Marco”, en Actas de la 24a paralelo IEEE Internacional y Distributed Processing Symposium (IPDPS10), Atlanta, GA, pp 1--10.. 2010. DOI: 10.1109 / IPDPS.2010.5470437

Bill Barth
fuente
Cualquier posibilidad de que podría incluir la imagen directamente en su respuesta?
Aron Ahmadia
Aunque podría decirse que el uso justo para tomar prestado su figura, prefiero conducir tráfico al sitio de los autores. Tal vez voy a hacer algunos números y mi propio gráfico y volver más tarde con una figura.
Bill Barth
Desde esa perspectiva, se puede envolver la imagen de modo que se vincula al sitio del autor, así como aumentar la cantidad de texto en el enlace. Si usted quiere discutir esto más, puedo abrir un hilo de meta / charla.
Aron Ahmadia
@BillBarth Su enlace simplemente redirige a su página de inicio ahora. ¿Podría arreglarlo o incrustar la imagen pretendida?
Jed Brown
1
@JedBrown Enlace editado. Añadió la referencia completa. DOI añadió.
Bill Barth