Download Tema_1
Document related concepts
no text concepts found
Transcript
Tema 1: Introducción Motivación del procesamiento paralelo, su “inevitabilidad” Supercomputadores: Los Top 500 Paralelismo en Multiprocesadores: Perspectiva histórica y enfoque actual Avance sobre Arquitecturas de Paso de Mensajes (introducción a las prácticas de la asignatura) Evaluación de las prestaciones de un sistema paralelo y sus límites (Ley de Amdahl) Arquitecturas Paralelas Un computador paralelo es una colección de elementos de procesamiento que cooperan para resolver rápidamente grandes problemas computacionales. Cuestiones abiertas: • ¿Cuántos elementos de procesamiento? • ¿De qué potencia son esos elementos? • ¿Cuánta memoria hay disponible? • ¿Cómo se comunican los procesadores? • ¿Cuáles son las abstracciones para expresar la cooperación? •¿Cómo se traduce todo esto en rendimiento? •¿Cómo se escala la arquitectura? ¿ Porqué estudiar las Arquitecturas Paralelas ? •A nivel de prestaciones, la computación paralela nos coloca varios años por delante respecto a sistemas monoprocesadores. Su uso es, pues, inevitable en muchas aplicaciones reales en la actualidad. •Proporcionan una alternativa a basar las prestaciones únicamente en la frecuencia de reloj del procesador. Su uso es, pues, inevitable desde el punto de vista tecnológico. •Este estudio se aplica a todas las etapas de diseño, abriendo posibilidades de paralelismo en muchos niveles. Abstracción del Pase de Mensajes •La combinación send-recv establece una copia memoria a memoria y una sincronización entre los procesos involucrados •Enviar un mensaje consume mucho tiempo: - Construir la cabecera del mensaje; copiar los datos en el buffer de la red; enviar el mensaje; copiar los datos en el buffer receptor; copiar los datos del espacio S.O. al espacio usuario Inevitabilidad Tecnológica (I): General •En cuanto a tecnología del chip, los factores principales de diseño que afectan a las prestaciones son: - Disminución del “feature size” (d) - Aumento del tamaño del chip en si mismo (waffer scale integration) •La disminución del “feature size (d)” se traduce en: - Aumento de la velocidad de reloj proporcional a l - Aumento del número de transistores proporcional a l2 (efecto total proporcional a l3) •¿ Cuánto cabe esperar que continúe disminuyendo l ? - Ley de Moore (Dr. G ordon Moore, Chairman, Intel) - “La densidad de circuitos en un chip se dobla cada 18 meses”. (Nota: Ley totalmente empírica) Inevitabilidad Tecnológica (II): Paralelismo y Ley de Moore * Ley de Moore Prestaciones pico de varios computadores a lo largo de los años La experiencia demuestra que la ley empírica de Moore se Cumple en la práctica. (Nota: La Ley de Moore se aplica solo a “prestaciones pico”. Las prestaciones finales se ven muy afectadas por otras consideraciones de diseño, muchas de ellas relacionadas con el software). * Barreras - Hipótesis: No es posible crecer más que lo indicado por la Ley de Moore (que aún siendo mucho, es un límite) Extrapolación de tasas de crecimiento de prestaciones (análisis de los top 500) * Consideraciones Adicionalmente es concebible que finalmente se llegue a los límites de las actuales tecnologías de semiconductores, necesitándose un cambio cualitativo imprevisible. Conclusión: Paralelismo en la ejecución de operaciones como única forma de sobrepasar la Ley de Moore. Inevitabilidad Tecnológica (III): Memoria (I) • Descomposición de un problema * Computación * Datos * Visualización • Consideraciones sobre la memoria * Es un hecho que el volumen de datos asociados a las necesidades computacionales actuales crece de una forma exponencial. * Es un hecho que la velocidad de acceso a memoria crece mucho más lentamente que la velocidad a la que se puede operar con los datos Inevitabilidad Tecnológica (III): Memoria (II) Gráfica de aumento de la velocidad y capacidad de la memoria Conclusión: 1) Paralelismo en la ejecución como forma de enmascarar latencias de acceso a memoria. 2) Paralelismo en el acceso a los datos en diferentes bancos de memoria. Inevitabilidad en las aplicaciones Nuevas áreas de computación científica emergen, y otras se consolidan, con necesidades generales de computación que crecen experimentalmente.BioInformática: - Distintos proyectos Genoma (por ejemplo “Proyecto Genoma Humano”) - Proyectos en Genoma Estructural - Farmacogenómica: nuevas revoluciones en medicina. Medicina: - Paso de scanners en 2D a scanners en 3D y 4D. Física: - Física atómica - Nuevos retos en la computación cuántica. Aparecen nuevas áreas en computación de propósito general.- Todo lo relacionado con vida - Data warehousing y Data Mining - Gráficos Conclusión: Las nuevas áreas de aplicación de la computación nos fuerzan a ir más allá de los límites de la Ley de Moore, tanto en velocidad de cálculo como en acceso a memoria. El único camino es la computación paralela. Hacia el paralelismo: Gestión del ‘budget” de transistores por chip Dos alternativas octogonales que deben balancearse: - Aumentar la complejidad de las unidades funcionales (UF’s), o incluso replicarlas - Colocar diversas etapas de memoria “on chip” Conclusión: “Alternativas condenadas a entenderse”. Hacia el paralelismo: Aumento de la complejidad de los UF’s De esta forma conseguimos: - Paralelismo a nivel de bit - Paralelismo a nivel de instrucción (ILP) - Paralelismo a nivel de hebra Hacia el paralelismo: Ejemplo de cambio cualitativo Ejemplo de : - Introducción del paralelismo a nivel de bit. - Introducción de economía de escala en diseño y producción. Hacia el paralelismo: Contra ejemplo (límites en cambios) - Límites al paralelismo a nivel de bit - Límites al paralelismo a nivel de ILP Conclusión: Hay que introducir el paralelismo a todos los niveles, adoptando una perspectiva jerárquica y agotando cada nivel intermedio. El nivel último son los multiprocesadores. Evolución de las Arquitecturas 2002 Computer product segments Computing power Client computers Desktop supercomputers Desktop computers Notebook computers Special servers (supercomputers, massively parallel computers, and others) Enterprise servers Special servers: (legacy, midrange) transactions data mining simulation video virtual reality Web and local-area network servers Home servers Server computers Application Specific PCs $$ hundreds $$ millions 1997 Computer product segments Massively parallel computers Computing power Supercomputers Mainframe computers Desktop supercomputers Workstation computers Personal computers Minicomputers Workstation servers PC servers Application Specific PCs $$ hundreds $$ millions Supercomputación: Generales -Concepto de “Supercomputación” como motor estratégico de arquitecturas de altas prestaciones. - ¿Qué es un Supercomputador? * Definiciones “conceptuales” - “Un computador excepcionalmente rápido” - “Un sistema para resolver grandes problemas muy rápidamente” * Definición “tecnológica” -” Un computador cuyo cuello de botella está en la I/O” (Convex Inc.) * Definición “operativa” - “Es uno de los 500 sistemas más rápidos del mundo en cada momento según el conocido test Linpak” - Establecimiento de la iniciativa “Top 500” como mecanismo para analizar la evolución de los supercomputadores. Arquitectura Paralela: AYER Históricamente, la computación paralela ha consistido en una serie de modelos rivales y arquitecturas divergentes, sin una línea de desarrollo predecible. La incertidumbre arquitectural ha paralizado el desarrollo del software paralelo Arquitectura Paralela: HOY Extensión de la noción clásica de la arquitectura de computadores (ISA), para soportar comunicación y cooperación. Arquitectura de Comunicaciones = Abstracción de la Comunicación + Implementación Abstracción: •Primitivas de comunicación HW/SW visibles al programador (ISA) •Ej.: memoria compartida, pase de mensajes, … •Se asume que las primitivas se implementen eficientemente. Implementación: •Integración del controlador de comunicaciones •Estructura de la red de interconexión Arquitectura de Comunicaciones Aplicaciones Paralelas Multiprogramación Paso de Paralelismo Memoria compartida mensajes de datos Modelo de Programación Abstracción de las comunicaciones Compilación o Librería Sistema Operativo Interfaz Usuario/sistema Frontera Hardware/Software Comunicación Hardware Una frontera plana significa convergencia en la estructura organizativa Mapeo Simple/Complejo de la abstracción de las comunicaciones en las primitivas de hardware Arquitecturas Paralelas Básicas: • • Arquitectura de Memoria Compartida Arquitectura de Memoria Privada Arquitecturas de Pase de Mensajes Concepto: Comunicación tipo “correo postal” Proceso 0 Dato Puedo enviar? Proceso 1 Si Data Data Data Data Data Data Data Dato Tiempo Propiedad Clave: La comunicación (cooperación) entre procesadores está integrada al nivel de I/O, y no en el sistema de memoria (ahora los bloques de diseño son computadores completos) Abstracción de la Comunicación: Espacio en el Direccionamiento Local Los procesadores solo pueden acceder a su memoria local, estableciéndose la comunicación/sincronización mediante llamadas explícitas al S.O. (mensajes send/receive) Abstracción del Pase de Mensajes •La combinación send-recv establece una copia memoria a memoria y una sincronización entre los procesos involucrados •Enviar un mensaje consume mucho tiempo: - Construir la cabecera del mensaje; copiar los datos en el buffer de la red; enviar el mensaje; copiar los datos en el buffer receptor; copiar los datos del espacio S.O. al espacio usuario Aspectos de Diseño Denominación: ¿Cómo se designan a los datos lógicamente compartidos y/o a los nodos? Latencia: ¿Cuál es la latencia de comunicación? Ancho de Banda: ¿Cuántos datos pueden comunicarse por segundo? Sincronización: ¿Cómo pueden sincronizarse los productores y consumidores de datos? Granularidad de los Nodos: ¿Cómo se divide el Si entre procesadores y memoria? Aplicabilidad: ¿Propósito general o propósito especial? Latencia y Ancho de Banda Latencia y ancho de banda son factores clave en el rendimiento de una arquitectura paralela y se utilizan en la evaluación de alternativas de diseño. Opciones para Controlar la Latencia • Reducir la frecuencia de las operaciones de latencia alta • Reducir la latencia: caches, controlador de comunicaciones • Enmascarar la latencia: superposición entre comunicaciones y computaciones, anticipación, ... Coste de la Comunicación Coste Comunicación = Frecc x (Coste c + Latencia + Tamaño Transf. - Superpos. Ancho de Banda Frecc : Número de operaciones de comunicación por unidad de computación en el programa (software y hardware) Costec : Tiempo consumido en iniciar y gestionar la comunicación. Latencia: Tiempo para transferir datos desde la fuente al destino a través de la red de interconexión. Tamaño Transf.: Determinado por la línea cache (memoria compartida) o variable según el programa (pase de mensajes) Ancho de Banda: Velocidad de transferencia de datos a través de la red. Superpos.: Porción de la operación de comunicación realizaDa simultáneamente con computación útil. Compromisos de Diseño Latencia y Ancho de Banda interaccionan en los sistemas paralelos reales de una forma más o menos compleja. Multiprocesador de Bus Compartido El ancho de banda del bus es fijo, y debe compartirse por los accesos a memoria (fallos cache) de todos los procesadores: peligro de contención (saturación). El factor de escala del bus depende de su ancho de banda, la velocidad del procesador, la mezcla de instrucciones y el índice de fallos cache. El ancho de banda puede incrementarse sustituyendo el bus por una red escalable. Pero estas redes suelen tener mayor latencia que un bus único en el caso de no saturación (no sobrecarga) Conceptos básicos de evaluación Ts: Tiempo requerido para resolver el problema en un procesador individual (“Tiempo en secuencial”) TP: Tiempo requerido para resolver el problema en un sistema de p procesadores (“Tiempo en paralelo”) + Aceleración: Ts/TP + Eficiencia: TS/(pTp) + Balanceo: Tultimo procesador - Tprimer procesador Ley de Amdahl aplicada al paralelismo Definición: Si un sistema consiste de p procesadores idénticos Y la parte serie de un programa es una fracción f, entonces la máxima aceleración que podemos alcanzar, S, es: S < — (f + ( 1 - f)/p)-1 El límite para p -> es S = f-1 Ejemplos para distintos f, P y s : f p S S/p 0,5 64 1024 64 1024 64 1024 64 1024 64 1024 16384 1,969 1,998 4,706 4,981 8,767 9,913 15,422 19,636 39,264 91,184 99,399 0,031 0,002 0,074 0,005 0,137 0,010 0,241 0,019 0,614 0,089 0,006 0,2 0,1 0,05 0,01 Gráfica de la Ley de Amdahl aplicada a MPP’s Aceleración _1 f f=0 Overhead = 0 f= 0 Overhead = 0 f=0 Overhead = 0 Número de Procesadores Conclusión fundamental: La fracción serie, f, de un programa limita la aceleración 1 a , aún en el caso de contar con infinitos procef sadores. La overhead asociada con la paralelización, que siempre ocurre en un sistema real, reduce este límite aún mas.