Intensidad Aritmética, Ancho de banda de memoria, FLOPS

FLOPS/Intensidad = BW

Si conozco la intensidad aritmética de mi problema la relación entre el BW y FLOPS es lineal.

FLOPS = BW * Intensidad

Limitado por el pico teórico de FLOPS de la máquina.

Ancho de banda de 16 GiB/s.
Performance pico de 16 GFLOPS.

Típico: aumentar cores sin tocar el subsistema de memoria.

Computadora desbalanceada.

Como cambia el modelo según el grado de optimización (FLOP & Memoria).

(Lorena A. Barba, Rio Yokota, How will the fast-multipole method fare in the exascale era?, 2013)

La cantidad de transistores se duplica cada 18 meses.

(Moore, Electronics 38(8) April 19, 1965)

Es una observación de mercado, no una ley de la física.

Nada cambió.

Esta si es una ley de la ¿física? ¿electrónica?
Posibilitó "ley" de Moore se mantuviera a lo largo de los años.

Observar: transistores son más pequeños y densidad de potencia es constante.

MOSFETs continue to function as voltage-controlled switches while all key figures of merit such as layout density, operating speed, and energy efficiency improve – provided geometric dimensions, voltages, and doping concentrations are consistently scaled to maintain the same electric field.

En el 2001 se acabó la veta del ILP.

(Dally, The Last Classical Computer, 2001)

(Gordon Moore, An Update on Moore's Law, Keynote Presentation at ISSCC 2003)

(Herb Sutter, The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, 2005)

(Bill Dally, Efficiency and Programmability: Enablers for ExaScale)

All performance is from parallelism

-

Machines are power limited

(efficiency IS performance)

-

Machines are communication limited

(locality IS performance)

.

.

(Bill Dally, Efficiency and Programmability: Enablers for ExaScale, SC13)

Comunicación, distancia y potencia en un chip típico de 20mm*20mm=400mm².

(Bill Dally, Efficiency and Programmability: Enablers for ExaScale, SC13)

Mejora en crudo

Visión más económica

• Lo que queremos: linear speedup, =100% de eficiencia.
• Lo que obtenemos: sublinear speedup, <100% de eficiencia.
• A veces, solo a veces: superlinear speedup >100% de eficiencia.

Gráfico de Guillermo Ortiz, exámen de WHPC13.

…the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by achievements in sequential processing rates of very nearly the same magnitude.
— Gene Amdahl

• S(N): aceleración para N procesadores.
• P: porción paralelizable.
• N: número de componentes paralelas.

¡Siempre necesitaremos buena preformance en 1 hilo!

(Wikipedia, Amdahl's Law)

Problema

• Quiero un speedup de 80x.
• Con 100 procesadores.
• ¿Qué fracción de la computación original puede ser secuencial?

Respuesta

0.25%

(Hennessy, Patterson, CAAQA4, p.202)

AGGGGGGGGGGGG!

La ley de Amdahl's pone límites muy fuertes en la paralelización.

Pero...

• Es para un tamaño de problema fijo.
• Usualmente a mayor poder de procesamiento, más grande es el set de datos que quiero procesar!

…speedup should be measured by scaling the problem to the number of processors, not by fixing the problem size.
— John Gustafson

Supone que el data-set aumenta linelmente con la cantidad de procesadores.

• S(P): aceleración para P procesadores.
• P: número de procesadores.
• α: fracción secuencial.

Although simply scaling the data size with processor count is rarely appropriate, assuming a fixed problem size for a much larger processor count is often inappropriate as well, since it is likely that users given a much larger multiprocessor would opt to run a larger or more detailed version of an application.

(Hennessy, Patterson, CAAQA4, p.259)

Strong scaling

El tiempo de procesamiento baja a medida que agregamos "cores" para un problema de tamaño fijo.

Weak Scaling

El tiempo de procesamiento no aumenta a medida que agregamos "cores" para un problema de tamaño variable.

• Charles Severance, Kevin Dowd, "High Performance Computing", Connexions, 2010, CC3.0.
• Patterson, Hennessy Computer Organization and Design, Fifth Edition, Morgan Kaufmann, 2012.
• Hennessy, Patterson, Computer Architecture: A Quantitative Approach, Fourth Edition, Morgan Kaufmann, 2011.
• S. Williams, A. Waterman, D. Patterson, Roofline: an insightful visual performance model for multicore architectures, Communications of the ACM, 2009
• Michael McCool, Arch Robison, James Reinders, Amdahl's Law vs. Gustafson-Barsis' Law, Dr. Dobbs, 2013.
• Samuel H. Fuller and Lynette I. Millett, Editors, The Future of Computing Performance, Game Over or Next Level?, The National Academy Press, 2011.

• SIMD (aka SSE{2,3,4} AVX{2})