Download Diapositivas Tema 17
Document related concepts
no text concepts found
Transcript
PROCESAMIENTO PARALELO Tema 17 Eduardo Daniel Cohen – dcohen@herrera.unt.edu.ar http://www.herrera.unt.edu.ar/arqcom Multiprocesamiento D. Cohen UNT Arq de Computadoras - 2014 Evolución de la Performance Limitada por la potencia, latencia de memoria, paralelismo aprovechado. 2 Evol. de la frecuencia de reloj 3 30/05/14 3 Pregunta • ¿Por qué la frecuencia casi no creció? Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 4 Cambios de Paradigmas • VP: Potencia es barata, transistores son caros. • NP: “Pared de Potencia” Potencia cara, transistores baratos. – Puede haber transistores que no se usen nunca en un chip • VP: Multiplicaciones lentas, Acceso a Mem. Rápido • NP: “Pared de Memoria” Mem. Lenta, multiplic. rápida. (200 clocks para DRAM, 4 clocks para multiplicación FP) • VP : Incrementar ILP mediante compiladores y mejor Hw (Fuera de Orden, especulación, VLIW, …) • NP: “Pared ILP” ritmo menor de ganancias por más ILP. • NP: Paredes (ILP + M + Potencia) = Pared de Concreto – VP: Uniprocesador, mejora performance 2X / 1.5 yrs – NP: Multiprocesador, mejora performance sólo 2X / 5 yrs Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 5 Cambio abismal en diseño de Chips • RISC II (1983): 32-bit, pipeline de 5 etapas, 40,760 transistores, 3 MHz, – chip de 60 mm2, con NMOS de 3 micrones, • Tecnología 2007-8: – Un chip de 125 mm2, con CMOS de 0,065 micrones – En un chip: 2312 RISC II + FPU + Icache + Dcache • Futurología: la medida de complejidad de un chip cambiará: CPU’s en lugar de transistores. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 6 Conclusiones • Los viejos paradigmas ya no funcionan • Es necesaria una nueva solución de arquitectura basada en PARALELISMO. • Es necesario un esfuerzo combinado de – arquitectos, diseñadores de lenguaje, expertos en aplicaciones, analistas numéricos, diseño de algoritmos, programadores, … Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 7 ¿La historia se repite? “… today’s processors … are nearing an impasse as technologies approach the speed of light..” David Mitchell, The Transputer: The Time Is Now (1989) “We are dedicating all of our future product development to multicore designs. … This is a sea change in computing” Paul Otellini, President, Intel (2005) • El esfuerzo del 89 se detuvo por el gran avance que hubo en uniprocesadores. – Ahora se paga el costo de no haber insistido en esa línea (2X cada 5 años?). • Todas las Cías de Mp trabajan con Multicore. – (2X cores/ 2 años). Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 8 Temario • Ventajas y Desventajas. • Clasificación – Memoria compartida. • UMA • NUMA – Memoria no compartida. • Multihilo Simétrico. SMT. • Ventajas y desventajas del MP. – Sincronización. – Coherencia. • Diferentes MP. • Ejemplos. • Recomendaciones. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 9 Ventajas de MP • Escalabilidad: más CPUs à ¿mejor performance? à Perfil Tarea. – OLTP (procesamiento de transacciones en línea). – DSS (Decision Support Systems). – Grandes problemas de Cálculo Científico (ej. Bioinformática) • Menor Consumo / Procesador – Procesadores más simples. – Procesadores más lentos. – Se pueden “apagar” cuando no se usan. • Disponibilidad (¿si uno cae en 50 CPUs?) • Confiabilidad (si se implementan reglas de mayoría). Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 10 Desventajas MP • Más procesadores à Menos eficiencia. – Problemas de Sincronización. • Cuellos de Botella. – Segmentos no paralelizables. – Problemas de Coherencia con datos compartidos. • Dificultades: – Transparencia. – Programación en Paralelo – Lenguajes – Compiladores. – … Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 11 Clasificación • UMA (SMP) – Acceso uniforme a memoria compartida. • NUMA – Acceso no uniforme. • o – Pasaje de Mensajes. • RED o CLUSTER. – E/S no es uniforme. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 12 Message Passing • Para pasar datos en Memoria no Compartida. • Cuando un CPU calcula un dato, ejecuta SEND(Pi,Dj) – Envía el dato Dj al procesador Pi. • Cuando un CPU necesita un dato, ejecuta WAIT(Pi,Dj). – Si el dato ya está en el buffer, no pierde tiempo. – Si no está, espera la producción del dato y su latencia por la red de conexión. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 13 Clasificación • ¿Cómo comparten Datos? – Igual espacio compartido de memoria para todos (load / store). • UMA o SMP – acceso uniforme a memoria. • NUMA – acceso no uniforme a memoria. – Varios espacios privados de memoria (message passing). • Clusters – No transparentes a la aplicación. – – – – – E/S no uniforme. Se comunican a través de un nexo de E/S (red por ej.). Más Caro para mantener (n computadoras). Más escalable. Menor ancho de banda de comunicación que bus de Memoria. Se arma con PCs standards. • ¿Cómo se comunican? – Bus. – Red. • ¿Cómo se ordenan las tareas? Sincronización. • ¿Son transparentes a la aplicación? – El programador prefiere que si. – El arquitecto prefiere que no. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 14 Definiciones: Tarea – Proceso - Hilo • • • • Tarea, Proceso, Programa – son equivalentes. Multitask o Multiprogram – equivalentes - concurrentes. Multiprocess – varios procesos en paralelo. Multihilos. Una aplicación lleva a cabo distintas funciones independientes “al mismo tiempo” mediante hilos (threads). – Comparten los recursos de la aplicación. – Cada uno tiene su propio PC, SP y estado de ejecución (run, ready, wait). Ejemplos • Un hilo toma datos de E/S y otro hilo los procesa. – Ej. Vimos en Sistemas con Microprocesadores y Microcontroladores • Sonido Stereo, un hilo para cada salida de parlante. • Excel – un hilo calcula, otro maneja el menú de usuario. • Más rápido cambiar de hilo que de proceso. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 15 Escalabilidad • Un sistema es escalable si cuando incrementamos los recursos se logra una mejora proporcional en la performance. • ¿p procesadores escala p veces? • Ley de Ahmdal: Si se varía una parte de un sistema, la mejora total está limitada por la parte no modificada. – ¿Tienen una única memoria? – ¿Un único medio de conexión? – ¿Un único sistema de E/S? Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 16 Ejemplo Escalabilidad • Se desea sumar 8000 números. – – • Solución: – – – – – – • Con 8 procesadores. Suponga que toda suma demora igual: T. Cada procesador realiza 1000 sumas. Cuatro procesadores realizan 1 suma. Dos procesadores realizan 1 suma Un procesador realiza una suma. tp = 1003T, ts=8000 a=8000/1003=7,98 Se perdió un 2% de la escalabilidad máxima. ¡Y este es un muy buen caso! – Sin contar la barrera de sincronización. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 17 Escalabilidad II • Considere una tarea: – El 80% se divide en 8 hilos totalmente independientes. – El 20% restante debe ser ejecutado en forma totalmente serial – segmento crítico. – Se cuenta con 8 procesadores. • Aceleración = 1/(1- f + f/p) – f = 80% , p=8, A=3,333… – Fuerte baja, ¡y nada que ver con Hw! – ¡Es el Sw que está limitado al perfil de la tarea! – Y no estamos contando la barrera de sincronización. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 18 Segmentos Críticos para Sincronizar • Venta de Pasajes – n agencias. – – – – Pasajero 1 consulta en Argentina: 1 único lugar. Pasajero 2 consulta en Rusia. 1 único lugar. Ambos compran. En base de datos queda vendido un lugar. • Solución: la actualización es crítica, sólo un proceso puede revisar y actualizar si hay lugar. • Los otros procesos esperan hasta que se libere esta sección crítica. • Sin esta solución: Vuelos sobrevendidos. • Tema de Sistemas Operativos. • ¡¡Segmento crítico es muy caro para la arquitectura!! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 19 Paralelismo a Nivel de Instrucción (ILP) • Hasta aquí hemos visto ILP (paralelismo al nivel de Instrucción). – Se basa en encontrar el paralelismo inherente en las instrucciones de un programa. – Ventaja: transparencia. – ¿Desventaja? Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 20 ILP parado la mayoría del tiempo For an 8-way superscalar.! From: Tullsen, Eggers, and Levy," “Simultaneous Multithreading: Maximizing On-chip Parallelism”, ISCA 1995." Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Eficiencia del Superescalar (ILP) Emisión = 4 Emisión Instrucción Ciclos totalmente vacíos (desperdicio vertical) Tiempo Ciclo parcialmente vacíos, IPC < 4 (desperdicio horizontal) Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 22 Paralelismo a Nivel de Hilos (Multithread) • Si las instrucciones provienen de distintos hilos: – Ya se sabe que las instrucciones son independientes. – Mejor posibilidad de aprovechar los recursos del o de los procesadores. – Cada Thread requiere información de su estado y mapeo con registros en forma independiente. • Cada Thread aparece como un CPU virtual. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 23 Multithreading Vertical Ancho Emisión Emisión Instrucción Segundo hilo entrelezado. Tiempo Ciclo pacialmente utilizado, IPC < 4 (desperdicio horizontal) • Se mejora el desperdicio vertical, pero no el desperdicio horizontal Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 24 Chip Multiprocessing (CMP) Ancho Emisión Tiempo – – – – Reduce complejidad de cada chip (¡potencia!), Menos desperdicio vertical (menor ancho x chip) Menos desperdicio horizontal (menor ancho x chip). Mejor aún Multihilo en cada core. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 25 Multithreading Simultáneo [Tullsen, Eggers, Levy, UW, 1995] Ancho ILP tiempo • Entrelazar múltiples hilos a la vez, sin restricciones. • Requiere registros y variables de estado de hilos independientes. • Mejor todavía: SMP con Multithread en cada core. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 26 Memoria de Acceso Uniforme (UMA) • Es el caso del Dual Core. • En promedio muchas partes de un chip uniprocesador están subutilizadas: – Cachés. – Ancho de Banda de M y E/S. • ¡Entonces pongamos otro núcleo que las comparta! • Si comparten datos lo hacen vía L2. • Las interacciones se hacen dentro del chip. • Mucho más rápido que con varios chips. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 27 Evolución Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 28 Problema: Caches Write-Back • T1 se ejecuta prog T1 ST X, 1 ST Y,11 • cache-1 writes back Y • T2 se ejecuta • cache-1 writes back X • cache-2 writes back X’ & Y’ Multiprocesamiento – D. Cohen cache-1 X= 1 Y=11 memoria X=0 Y =10 X’= Y’= X= 1 Y=11 X=0 Y =11 X’= Y’= Y= Y’= X= X’= X= 1 Y=11 X=0 Y =11 X’= Y’= X=1 Y =11 X’= Y’= Y = 11 Y’= 11 X=0 X’= 0 Y = 11 Y’= 11 X=0 X’= 0 X=1 Y =11 X’= 0 Y’=11 Y =11 Y’=11 X=0 X’= 0 X= 1 Y=11 X= 1 Y=11 UNT Arq de Computadoras - 2014 cache-2 Y= Y’= X= X’= prog T2 LD Y, R1 ST Y’, R1 LD X, R2 ST X’,R2 Problema: Caches Write-Through prog T1 ST X, 1 ST Y,11 • T1 se ejecuta • T2 se ejecuta cache-1 X= 0 Y=10 memoria X=0 Y =10 X’= Y’= cache-2 Y= Y’= X=0 X’= X= 1 Y=11 X=1 Y =11 X’= Y’= Y= Y’= X=0 X’= X= 1 Y=11 X=1 Y =11 X’= 0 Y’=11 Y = 11 Y’= 11 X=0 X’= 0 prog T2 LD Y, R1 ST Y’, R1 LD X, R2 ST X’,R2 Copia Existente de X en cache-2 Caches Write-through presentan inconsistencias también. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 30 Coherencia en SMP write request: La dirección se invalida (actualiza) en otros caches antes (despues) de la escritura. read request: Si algún otro cache contiene una copia “sucia”, se realiza write-back antes de leer la memoria. • Write back mejor que Write through. § Menor tráfico en el bus. • Invalidación: menor tráfico en el bus (sin datos) • Los cachés tienen un mecanismo que espía las transacciones del resto (“Snooping Caches”). Veamos el diagrama de Estado de cada cache Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 31 Ej: 2 CPUs – idéntico bloque S = Compartido, M = Modificado, I = Inválido, Bloque no está en cache P1 reads P1 writes P2 reads P2 writes P1 reads P1 writes P2 writes P1 Read miss P2 reads, P1 writes back Write miss P2 intent to write P1 writes back S P1 writes P2 M P1 reads or writes P2 intent to write P1 reads, P2 writes back I M P2 reads or writes Write miss Read miss Multiprocesamiento – D. Cohen P1 intent to write P2 writes back S P1 intent to write UNT Arq de Computadoras - 2014 I Falsa Incoherencia state blk addr data0 data1 ... dataN Un bloque de cache contiene varias palabras. La coherencia de cache se realiza a nivel de bloque y no palabras. Suponga que P1 escribe datai y P2 escribe datak y ambas palabras están en el mismo bloque. ¿Qué puede pasar para el caso de invalidación? Más complicado cuando hay sectores críticos (SO) Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 33 Ej: Falsa Incoherencia Vs Verdadera • Suponga x1 y x2 en el mismo bloque de cache. • x1 y x2 se encuentran ya en los caches de P1 y P2 Time P1 1 Write x1 2 3 Verdadero o Falso? Por qué? True Hit; invalidar x1 en P2 Write x2 False miss; x2 irrelevante a P1 Write x1 4 5 P2 False miss; x1 irrelevante a P2 Write x2 False miss; x2 irrelevante a P1 Write x2 Multiprocesamiento – D. Cohen True Miss; Invalidar x2 en P2 UNT Arq de Computadoras - 2014 34 El problema de la Coherencia • Se crea tráfico en el bus. • “Verdadero” o “Falso” es tráfico. • Además está el problema de la sincronización (S.O). • Hay un límite de escalabilidad en SMP. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 35 NUMA: Non-uniform Memory Access CPU 0! ...! CPU 1023! Cache Cache DRAM DRAM Interconnection Network Muy buena para aplicaciones que naturalmente se ajustan a esta arquitectura. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Cada CPU tiene parte de la Memoria Total! Para acceder a otras partes de la memoria, usar la Red de Interconección.! Las aplicaciones deben tener en cuenta la latencia de la conección.! 36 Pasaje de Mensajes • Un CPU no puede acceder con Load/Store. • Protocolo para llamados entre máquinas. • Compartir Datos mediante: – Caches coherentes (ccNUMA) • Se puede emplear Load/Store. • Mayor acoplamiento. – Sistema de pasaje de mensajes • Menor acoplamiento. • Más escalable en memoria no compartida. • Cluster – Memoria no compartida con partes standard – E/S no uniforme. – No transparente a la aplicación. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 37 Clusters: Enfoque Desde la Aplicación En lugar de que el Hw cree su memoria compartida de manera transparente. Que una aplicación construya su propio modelo de memoria." Conectar un número grande de Tarjetas de varios CPUs c/u en racks. Unir los racks por medio de Redes Universidad de Illinois, 650 2-CPU Apple Xserve rápidas." Cluster, conectado con Myrinet (3.5 μs ping time – red " de baja latencia) Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 38 Clusters – para web servers En algunas aplicaciones una máquina puede resolver un query por sí misma. ! ! Ejemplo: para páginas estáticas. Cada máquina tiene una copia del sitio.! Load manager es una computadora de propósito específico que asigna pedidos entrantes HTTP a una máquina en particular. Imagen: Eric Brewer’s IEEE Internet Computing article. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 39 Clusters – Web Servers En otras aplicaciones, varias máquinas colaboran en cada transacción." ! Ej.: Búsqueda en la Web. La búsqueda se particiona entre varias máquinas, cada una contiene La máquina de búsqueda de Altavista no una parte de la usaba clusters, sino multiprocesadores con memoria compartida. Esta solución no pudo base de datos." escalar a medida que crecía la web. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 40 El caso de Sun-Niágara Superescalar de 8 vías! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 En superescalares! Algunas aplicaciones pelean para llegar a! CPI = 1. ! Una mejor productividad se logra con un gran número de núcleos de emisión única! UltraSPARC T1 – “Niágara” • Hasta 8 núcleos en un chip. • Cada núcleo. – Emisión única en orden. – Hasta 4 hilos cada core. – Cuando no puede emitir, cambia de hilo. • Cache más chico y menos complejo. – Cada fallo, cambio de hilo. • Baja Potencia, por su simplicidad – 75 W, 8 cores, 32 hilos. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 42 Niágara se usa en Sun Fire T-2000 Sun proclama: T2000 usa 1/3 potencia que la competencia Benchmarks de servidores Web se usaron para posicionar la T-2000 Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Proyecto Caja Negra! Un data center en un container para barcos.! Server, Aire Acondicionado, Alimentación.! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Conecte sólo la red, la alimentación y el agua! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Contiene 250 Servidores T2000! ! 2000 núcleos y 8000 hilos! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Cell: ! The PS3 chip! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Aplicaciones Embebidas • PS3 Chip “Cell Broadband Engine”. • Procesador adaptado a la aplicación. • Pipeline de 8 cpus en el chip. – Memoria no Compartida. – Cada core tiene su propia memoria, que se maneja explicitamente por el programador. • Un Power PC completo integrado con el grupo. – Coordina. – Ejecuta código serial. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 50 L2 Cache! 512 KB ! PowerPC! Power PC Synergistic maneja 8 Processing SPUs y Units! también (SPUs)! ejecuta código serial! 2X area of Pentium 4 -- 4GHz, + frecuencia, 75W! Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 Ej. Cell para decodificar HDTV Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 52 Generalizando: Aceleración • Performance(serie) / Performance(paralelo) La performance sigue este patrón Más CPUs Menor performance ¿Por qué? Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 53 Otra métrica: eficiencia • Eficiencia = Aceleración / p • p = cantidad de procesadores en paralelo. • Ej. Si con 4 CPUs un programa se ejecuta 3 veces más rápido à eficiencia = 3/4 En general la eficiencia Sigue esta forma. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 54 Aceleración Vs. Tamaño Conjunto de Datos • ¿Por qué? • La clave para lograr eficiencia: – escalar los datos para escalar paralelismo. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 55 ¿Cómo explotar Paralelismo? • Reprogramar con Algoritmos paralelos. – Concentrase en la parte más lenta del prog. • Enfoques para paralelizar un problema. – Descomposición del dominio de datos. • Recordar: Suma de 1000 números. – Descomposición de Funciones o tareas. • Pueden ser totalmente Independientes o requerir sincronización. – Pipelining de tareas. • Recordar: HDTV. – Combinación de las anteriores. • No escalar paralelismo sin escalar datos. • Mayor profundidad en Libro Avanzado de los autores. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 56 Reconocimiento • Este tema ha sido preparado empleando material de: – Curso CS152, Berkeley, 2006, John Lazzaro. – Conferencia de David Patterson, Berkeley, 2006. – Curso CS152, Berkeley, 2008, Krste Asanovic – Curso EE252, Stanford University, Christos Kozirakys. Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 57 Qué Aprendimos • Materia de alta complejidad. • Nivel cercano a las mejores universidades del Mundo. • Qué es una computadora. • Niveles de Abstracción. • Cómo diseñar un ISA. • Diseño de un Procesador. • Procesadores Avanzados. • Sistema de Memoria. • Sistema de E/S y Buses • Diseño para Bajo Consumo • Multiprocesadores Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 58 Qué Aprendimos • Manejo de la Complejidad (Jerarquías, Paralelismo, Abstracción). • Constancia y Tenacidad en el trabajo duro. • Pensamiento de INGENIERIA (compromisos, alternativas) • Enfrentarse a situaciones nuevas. • Mucha gimnasia mental – nos pusimos “en forma”. • Uso intensivo del “Sentido Común” – el menos común de todos. • Planteo de metas y objetivos – concentrarse para llegar. • Herramientas para salir adelante… como Ingenieros. • Humildad y gusto por el desafío. • “Todos aprendemos en base a los errores” Multiprocesamiento – D. Cohen UNT Arq de Computadoras - 2014 59