Muchos son los nombres

Unidades de procesamiento independientes.

• SMP (Symmetric Multiprocessing).
• Manycore.
• Multicore.

Veremos el impacto en la performance y sus límites.

Speedup y Eficiencia

donde, T1 tiempo secuencial, Tp tiempo paralelo para p procesadores.

Escalado perfecto: "N procesadores, tienen que ir N veces más rápido".

Típico gráfico balístico

• ¿Es comparable la performance secuencial con la paralela N=1?
  • Comparar algoritmos secuenciales y su paralelización: relative speedup.
  • Comparar el mejor secuencial y el mejor paralelo: true speedup.
• ¿Escalar linealmente es sinónimo de buena performance?
• ¿Podemos tener escalado sublineal y que sea útil? (cost-effective).
• ¿Existe el escalado superlineal?

(Hennessy, Patterson, CAAQA4, p.260)

(Hennessy, Patterson, CAAQA4, p.261)

• 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!

Gustafson's Law

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)

SIMD < SIMT < SMT

Even in server workloads, where there’s naturally a lot of independent processing, single-threaded latency still matters.

Urs Hölzle, Brawny cores still beat wimpy cores, most of the time, Google, 2010.

So why doesn’t everyone want wimpy-core systems? Because in many corners of the real world, they’re prohibited by law—Amdahl’s law. Even though many Internet services benefit from seemingly unbounded request- and data-level parallelism, such systems aren’t above the law. As the number of parallel threads increases, reducing serialization and communication overheads can become increasingly difficult. In a limit case, the amount of inherently serial work performed on behalf of a user request by slow single-threaded cores will dominate overall execution time.

Extraer paralelismo del programa que se está ejecutando tiene sus límites.

Cómo aprovechar toda la infraestructura de:

• Register renaming.
• Scheduling dinámico.
• Múltiples unidades de ejecución (entero y punto flotante).
• etc ...

Symmetric Multithreading (SMT)

Un hilo es un mecanismo para marcar código que se puede ejecutar en paralelo.

Idea: si las unidades de ejecución están libres, hacer un interleaving de otro stream independiente de instrucciones.

• 2 hilos a la vez en 1 core.
• Explota el paralelismo interno de cada unidad de ejecución.
• Ellos proclaman: "Most power efficient performance feature"
  • Muy poca área.
  • Da beneficios a la mayoría de los workloads.
  • Muchísimo más eficiente que agregar un core.

(Glenn Hinton, Intel Fellow, Nehalem Lead Architect, Key Nehalem Choices, 2010.)

(Glenn Hinton, Intel Fellow, Nehalem Lead Architect, Key Nehalem Choices, 2010.)

• Presentado en 2002, Pentium 4 (Northwood).
• Intel Core y Core2, no la tuvieron.
• Reapareción en Nehalem, Sandy Bridge, Ivy Bridge.
• AMD Bulldozer es también como SMT.

(Wikipedia, Intel Processor Roadmap.)

Crítica

Agner Fog, How good is hyperthreading?, blog entry, 2009.

Alguna vez nos dieron para probar un Intel® Xeon® Processor X7560 (8 cores, 16 threads), pero con Hyperthreading deshabilitado (citation needed).

(Hennessy, Patterson, CAAQA4, p.178)

(Hennessy, Patterson, CAAQA4, p.174)

• Superscalar: Athlon 64.
• Coarse Multithreading (MT): ?
• Fine MT: Sun T1 (Niágara).
• SMT: Power5, Intel Core Nehalem.

Cada vez más complejo.

• Unidades de ejecución.
  • Sandy Bridge vs. Bulldozer, diferentes elecciones.
• Memoria caché.

Más información:

• David Black-­Schaffer, Resource Sharing in Multicore Processors, 2011.

• Rendimientos decrecientes en la explotación de ILP.
• Problemas de consumo.
• Ventajas enormes en la relación costo-performance de los SMP.

Reforzado por:

• Gran demanda de server workloads (web, altamente paralelas).
• Gran demanda de data-intensive workloads (análisis de datos, altamente paralelas).
• ?Desinterés por el desktop? (pero si su GPU)
• Madurez para entender los problemas de la multiprogramación a gran escala.
• Amortización de costos de diseño a través de la replicación.

Distribuídos o integrados

• Clusters: commodity & custom.
• Multiprocesadores en un chip (multicore)

Multiprocesadores

• Memoria compartida centralizada.
• Memoria compartida distribuida.

Uniform memory access (UMA).

• Poca escalabilidad.
• Usado por Intel hasta Core2.

-- acá es donde CAAQA4 se queda viejo (sadface) --

Non-uniform memory access (NUMA).

• Buena escalabilidad.
• El programa tiene que saber que la memoria está distribuída (performance).
  • Sin embargo el espacio de direcciones es único.
• Intel reemplazó el FSB por Quickpath-QPI desde Nehalem, ¿2009?.
• AMD la usa desde mucho antes (Hypertransport-HT en Direct Connect Architecture- DCA , desde Athlon 64 X2, 2006).

(Frequently Asked Questions: NUMA, SMP and AMDs Direct Connect Architecture)

• problema cachear memoria compartida, >=2 copias de la misma información.
• Mantener la coherencia entre las copias, dar consistencia al acceso de datos compartidos.

Orden sequencial, perserva el órden de read versus write, etc.:

R->W, R->R, W->R, W->W.

• Relajar W->R.
  total store ordering, processor consistency.
• Relajar W->W.
  partial store.
• Relajar R->W, R->R.
  weak ordering.

X86 implementa algo asi como total store ordering (TSO).

Modelos definidos en prosa y con ejemplos. Difícil de formalizarlos, similar a TSO. Se lo denomina X86-TSO.

• Dave Dices, QPI Quiescence, Oracle, 2010.
• Relaxed Memory Concurrency Page.

Una formalización:

• Peter Sewell, et.al, x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors, CACM, 2010, No.7.

Barreras de memoria en hardware

Para forzar consistencia secuencial. Flush de memoria (load&stores), stores y loads.

MFENCE, SFENCE y LFENCE.

_mm_mfence(), _mm_sfence(), _mm_lfence()

Pensar en los mensajes que se transmiten en la red:

• Invalidación de cache.
• Comunicación de memoria no-local.

Gran impacto en la performance.

• lstopo: lista la topología de memoria.
• numactl: memory policies for NUMA system.

Artículos

• Getting High Performance on NUMA-based Nehalem-EX System with MKL Without Controlling NUMA Policy for Shared Memory, Intel, 2010.
• Lee T. Schermerhorn, Automatic Page Migration for Linux, A Matter of Hygiene, HP/Open Source & Linux Organization, linux.conf.au, 2007.
• Tobias Klug, On the Importance of Thread Placement on Multicore Architectures, HPCLatAm11, 2011.

• Hennessy, Patterson, Computer Architecture: A Quantitative Approach, Fourth Edition, Morgan Kaufmann, 2007.

Sincronización

OpenMP