vicente galiano ibarra - umh2005.edu.umh.es
Post on 25-Oct-2021
18 Views
Preview:
TRANSCRIPT
Computación Paralela
Curso 2012/2013Vicente Galiano Ibarra
Introducción Arquitecturas Avanzadas
IntroducciónClasificación Sistemas ParalelosRendimiento Sistemas ParalelosProcesadores VectorialesProcesadores MatricialesRedes de InterconexiónMultiprocesadoresMulticomputadores
Introducción IProcesadores superescalares
Solapamiento de instrucciones (varios cauces):
Dependencia de datos verdadera (RAW)Dependencia relativas al procedimiento Conflictos en los recursosDependencias de salida (WAW)Antidependencia (WAR)
Políticas de emisión de instrucciones
Introducción IIEl paralelismo ya existe a nivel de procesador:
Segmentación y supersegmentaciónSe aumenta el número de etapas de cada
instrucción pipeline
Cuando más etapas mayor paralelismo, etapas más sencillas y mayor frecuencia de funcionamiento.
Introducción IIIProcesadores VLIW (paralelización realizada por
el compilador)
Estas son Arquitecturas Von Neumann: máquinas secuenciales procesando datos escalares
La frontera no está clara entre los procesadores superescalares y los vectoriales (los cauces implican hardware replicado)
Clasificación Sistemas Paralelos IClasificación Flynn
SISD (Single Instruction Single Data): Máquina Von Neumann clásicaMISD (Multiple Instruction Single Data): díficil implementación (procesadores vectoriales*)SIMD (Single Instruction Multiple Data): procesadores matricialesMIMD (Multiple Instruction Multiple Data): multiprocesador
Clasificación Sistemas Paralelos II
Clasificación Sistemas Paralelos IIIFuentes de paralelismo
Paralelismo de Control:Dependencia de control de secuenciaDependencia de control de comunicación
Paralelismo de DatosParalelismo de flujo
Rendimiento Sistemas Paralelos IEficiencia / Speed-upEscalabilidadRedundancia / UtilizaciónCalidad
Rendimiento Sistemas Paralelos IIGrado de paralelismoParalelismo medioSpeed-up asintótico
Para m procesosMedia aritmética del rendimiento Media geométrica del rendimientoRendimiento medio armónicoSpeed-up armónico medio
Rendimiento Sistemas Paralelos IIILey de Amhdal:
Sn=n/(1+(n-1)α) Donde α es la probabilidad de usar un modo secuencial puro.Sn 1/α
Independientemente del número de procesadores existe un límite superior del speed-up debido a la parte secuencial
Si α = 0 el speed-up es el ideal
12
Arquitecturas Vectoriales
13
Arq. De Memoria Compartida
14
Arq. de Memoria Distribuida
Clusters
15
Arq. Mem.Comp. y Mem.Dist.
16
Pasos en el Desarrollo de Aplicaciones Científicas
17
Paralelización de Programas
18
Medidas de Paralelismo
Speed-up
esprocesador en ejecución Tiempoprocesador 1en ejecucion Tiempo
pSp =
Eficiencia
pE pS=
Procesadores Vectoriales IComputación matricial (sin dependencia de datos)Replica unidades de cálculo pero no de controlInstrucciones vectoriales:
Sin dependencia de datosInstrucciones de alta carga computacionalPatrón de acceso a memoria conocidoSustituyen a bucles
Procesadores Vectoriales I
: Processor board of a CRAY YMP vector computer (operational ca. 1992-2000). The board was liquid cooled and is one vector processor
with shared memory (access to one central memory)
Procesadores Vectoriales IIArquitecturas Vectoriales
Máquina vectorial con registros (actuales)Máquina vectorial memoria-memoria
Componentes básicosRegistros VectorialesUnidades funcionales vectorialesUnidad de carga/almacenamiento vectoresRegistros escalares
Procesadores Vectoriales IIIInstrucciones vectoriales básicas
Vector-vectorVector-escalarVector-memoriaReducción de vectoresReunir y esparcirEnmascaramiento
Procesadores Vectoriales IIIFactores que afectan al rendimiento
Longitud de los vectores y velocidad de inicializaciónLos riesgos estructurales (control de flujo)Dependencia de datos
Procesadores Vectoriales IVLongitud de vectores
Longitud natural de los vectores diferente a la de la arquitecturaVLR (Vector Lenght Register)MVL (Maximum Vector Lenght)La gestión de los parámetros anteriores puede realizarla el compilador
Separación de vectores en memoria (carga y almacenamiento con separación)
Procesadores Vectoriales VMejora del rendimiento
Encadenamiento de operacionesSentencias if
Máscara vectorialMatrices Dispersas
Dispersión/agrupamiento (scatter/gather)
Procesadores Vectoriales VIMedidas del rendimiento
Rn: Velocidad en MFLOPS para un vector de longitud nR∞: Velocidad en MFLOPS para un vector de longitud infinitaN1/2: longitud necesaria para alcanzar R∞/2
Nv: longitud para la cual el modelo vectorial es preferible al escalar
*** NOTA: Los procesadores escalares actuales obtienen rendimientos muy similares a los vectoriales
Procesadores Matriciales I
Explota el paralelismo de datos más que el paralelismo de instrucciones
Procesadores Matriciales IIModelo basado en {N,C,I,M,R}
N: Número de elementos de proceso de la máquinaC: Conjunto de instrucciones nativas de la Unidad de ControlI: Conjunto de instrucciones que se envían a los EPsM: posibilidad de enmascaramientos de los EPsR: funciones de rutado para la comunicación entre EPs
Procesadores Matriciales III
Estructura básica de un EP
Procesadores Matriciales IVLos modelos matriciales se caracterizan:
Están destinados a aplicaciones específicas a las cuales extraen gran rendimientoSu programación no es sencilla por tener que programar con mucha dependencia del hardwarePrácticamente no existen en el mercado de supercomputadores comerciales
Redes de Interconexión IEs uno de los elementos fundamentales que modifican la propia arquitectura y el rendimientoLas redes se utilizan tanto en los computadores matriciales como en multiprocesadores y multicomputadores
Redes de Interconexión IIDefiniciones básicas:
Tamaño de la red (número de nodos)Grado del nodo (de entrada y salida) CosteDiámetro de la redAnchura de la bisecciónLongitud del cableSimetría
Redes de Interconexión IIIRendimiento:
FuncionalidadLatenciaAncho de bandaComplejidad HardwareEscalabilidadCapacidad de transmisión
Redes de Interconexión IVTopología:
Grafo de interconexiónParámetros:
Ancho de la bisecciónGrado del nodoDiámetro de la redLongitud SimetríaEstructura física
Redes de Interconexión VControl de flujo, regula el tráfico en la red asignando recursos (buffers y canales) a las unidades de información:
MensajePaqueteFlit
Debe solucionar el posible bloqueo de un paquete
Redes de Interconexión VIEncaminamiento, método para elegir un camino
Dada una posición actual y un destino existe un conjunto de canales posiblesEn cada paso se elige un canal de los posibles teniendo en cuenta información que puede ser constante, aleatoria o en función del tráfico
Redes de Interconexión VIIMétodos de Encaminamiento,
Deterministas: el camino depende unívocamente del nodo destino y del nodo origenInconscientes: la elección puede ser aleatoria, en función del tiempo o en función del contenidoAdaptativos: la función depende del tráfico es decir del estado de la red
Redes de Interconexión VIIIClasificación según topología:
Se pueden clasificar en síncronas y asíncronas y de control centralizado, descentralizado y distribuido. El mercado de redes de estaciones de trabajo están copados por redes asíncronas de control distribuido:
Redes de medio compartidoRedes DirectasRedes IndirectasRedes Híbridas
Redes de Interconexión IXRedes de medio compartido:
El medio de transmisión es compartido por todos los elementos de la red
Redes directas:Cada elemento está conectado de forma directa a un conjunto (reducido) de otros dispositivosEntre elementos no vecinos es necesario la transmisión a través de varios dispositivos intermedios
Redes indirectas:Se utilizan conmutadores para conectar los elementos de comunicaciónCualquier comunicación requiere el paso a través de conmutadores
Híbrido
Redes de Interconexión XRedes de medio compartido
Redes a área localBus de contención (Ethernet)Bus de tokens (Arcnet)Tokeng Ring (IBM)
Bus de sistema (monoprocesadores y multiprocesadores)
Son las redes más sencillas en las que sólo un elemento usa la red en un momento dado, siendo la red un elemento pasivo (no genera mensajes)
Estas redes se convierten en un cuello de botella al ampliar el número de procesadores de la red
Redes de Interconexión XIRedes directas
MallasToros Hipercubos
Estas redes escalan bien. Los nodos además de otras funciones realizan las funciones de router o encaminador (bien el propio procesador o routers dedicados)
Redes de Interconexión XII
Cada nodo dispone de canales internos y de canales externosDos nodos conectados directamente son nodos vecinos o adyacentes Lógicamente todos los nodos deben ser visibles
Redes de Interconexión XIIIEjemplos de redes directas
Redes de Interconexión XIVRedes Indirectas:
Basadas en conmutadoresConmutador dispone de puertosEl conmutador se conecta con el procesador y con otros conmutadoresUna característica importante es el número de conmutadores a atravesar
Redes de Interconexión XVRedes Híbridas:
Mezcla redes de medio compartido y de redes directas o indirectasEjemplos:
Redes multibusRedes jerárquicasRedes basadas en clusters
Multiprocesadores ISistema MIMDMemoria COMPARTIDAParámetros importantes:
Red de interconexiónConsistencia de memoriaCoherencia de cachéSincronización
Multiprocesadores IIRedes de interconexión:
Buses (medio compartido)Bajo coste, Mala escalabilidad, no admite muchos
procesadoresRedes indirectas
– Red de barras cruzadasUna sola etapa de conmutación, muy cara para
muchos elementos– Redes multietapa
Como se conectan las diferentes etapas definen las características de la red
Tipos: Bloqueante, No bloqueante, Reconfigurable
Multiprocesadores IIIConsistencia de memoria:
Debemos asegurar una coherencia realizando las tareas de una sincronizaciónPor software mediante flags (no practicable)Modelo de consistencia que especifica el orden de la realización de las operaciones en memoriaLa consistencia implica la coherenciaModelos:
– Consistencia secuencial estricta– Consistencia secuencial– Otros modelos
Multiprocesadores IVConsistencia secuencial estricta:
Cualquier lectura devuelve el valor almacenado más recienteNo es implementable
Consistencia secuencial:Objetivo: modelo multihilo obtenga los mismos resultados en 1 o varios procesadoresLas operaciones se hagan visibles en el orden del programaEl compilador no puede optimizar
Multiprocesadores VOtros modelos de consistencia:
Modelos relajados que afectan a:– R R– R W– W W– W R
Consistencia de procesador– Elimina la ordenación W R por la existencia de buffers
de escritura
Ordenación por almacenamiento parcial– Elimina W W para escrituras no conflictivas
Multiprocesadores VI
Consistencia débil elimina las cuatro ordenaciones– Es necesaria la implementación de sincronizaciones
Consistencia de liberación– Sincronizaciones para poder adquirir el acceso a una
variable compartida y sincronizaciones para liberar esa variable
Multiprocesadores VIICoherencia de caché:
Las vistas en las diferentes cachés de los diferentes procesadores pueden diferirUn sistema debe mantener la coherencia de la cachéEl programador en este punto no tiene mucho que decirEste concepto es importante en nuestros programas en memoria compartida
Multiprocesadores VIIISincronización:
Cerrojos BarrerasImplementados en hardware o software
MulticomputadoresMejoran las sincronizaciones, las contenciones de memoria y la escalabilidadSolo existe memoria local El intercambio de información se realiza por mensajesA nivel rendimiento mejoran a los multiprocesadores para gran número de nodosSon muy importantes las redes de interconexión y la granularidad de los algoritmos
top related