Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
INSTITUTO POLITÉCNICO NACIONAL CENTRO DE INNOVACIÓN Y DESARROLLO TECNOLÓGICO EN CÓMPUTO ALGORITMO DE OPTIMIZACIÓN DE PROCESOS PARALELOS BAJO EL MODELO DE PROGRAMACIÓN MS-MPI EN ARQUITECTURA INTEL® TESIS QUE PARA OBTENER EL GRADO DE MAESTRÍA EN TECNOLOGÍA DE CÓMPUTO PRESENTA LUIS DAVID TERÁN GUTIÉRREZ DIRECTORES: DR. MIGUEL LINDIG BOS M. en C. JESÚS ANTONIO ÁLVAREZ CEDILLO Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 2 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 3 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 4 Agradecimientos: A la memoria de mi Madre y a mi padre, a los cual les debo todo lo que soy y lo que llegaré a ser. A mi familia por su cariño, amor y su comprensión al compartir mí tiempo con ellos y con esta tesis. A mis directores de tesis por su confianza, apoyo y paciencia. A mi Comité revisor por toda su ayuda. Al Instituto Politécnico Nacional y muy particularmente al Centro de Innovación y Desarrollo Tecnológico en Cómputo por todo el conocimiento adquirido durante los años de estudio. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 5 Resumen El rendimiento en un sistema clúster de memoria distribuida depende en gran media del tipo de red de interconexión utilizado, ya que los procesadores pueden permanecer ociosos en espera de datos de algún otro nodo. Las redes de interconexión presentan tiempos de latencia muy elevados comparados con los tiempos de acceso a la memoria local de cada nodo. El principio de jerarquía de memoria no ha sido explorado en los sistemas de clústeres con memoria distribuida. La hipótesis de la presente propuesta consiste en reducir los tiempos de comunicación entre nodos optimizando la distribución de procesos. Con ello, además de reducir tiempos de acceso, se reduce el tráfico en la red de interconexión. La principal aportación de la presente tesis consiste en evaluar el principio de jerarquía de memoria en sistemas clúster de memoria distribuida, identificando si al aplicar una optimización en la distribución de procesos se puede obtener una mejora en el rendimiento de los programas paralelos ejecutados. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 6 Abstract The performance in a distributed memory cluster system depends on the type of interconnection network used, since processors can remain idle waiting for data from another node. Interconnection networks have very high latency times compared with times of access to local memory of each node. The memory hierarchy principle has not been explored in cluster systems with distributed memory. The hypothesis of this thesis is to reduce the communication time between nodes optimizing the process distribution. This, in addition to reducing access times, reduces traffic in the interconnection network. The main contribution of this thesis is to evaluate the memory hierarchy principle in distributed memory cluster systems, identifying whether applying an optimization in the distribution process can obtain an improvement in the performance of parallel programs executed. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 7 Glosario de Términos 10 Gigabit Ethernet (XGbE o 10GbE): Standard IEEE 802.4ae publicado en 2002, la cual define una versión Ethernet con una velocidad de 10 Gbits/s. Computadora paralela: Es un sistema de cómputo multi-procesador que soporta programación paralela. InfiniBand: Es un bus de comunicaciones serie de alta velocidad, diseñado tanto para conexiones internas como externas. Sus especificaciones son desarrolladas y mantenidas por la Infiniband Trade Association (IBTA). Latencia: Es el tiempo o lapso transcurrido entre el inicio de la petición por un paquete de información y hasta que es recibido el primer byte. MPI (Message Passing Interface): Interfaz de Paso de Mensajes, es una especificación estándar para bibliotecas de paso de mensajes para aplicaciones de memoria distribuida usadas en cómputo paralelo. MPICH: Es una implementación portable de MPI desarrollada por Argonne National Laboratory y distribuida como software libre. La implementación original de MPICH se denominó MPICH1 e implementa el estándar MPI-1.1. La implementación más reciente es denominada MPICH2, la cual implementa el estándar MPI-2.0. MS-MPI: Implementación de Message Passing Interface (MPI) de Microsoft basado en MPICH2 incluido en Microsoft HPC Server 2008 y Windows Compute Cluster Server 2003. Plataforma Multi-procesador: Un sistema de cómputo que contiene dos o más sockets físicos. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 8 Procesador Core (Núcleo): Los circuitos que proveen funcionalidades dedicadas para decodificar, ejecutar instrucciones y transferir datos entre ciertos sub- sistemas en un procesador físico. Un procesador core puede contener uno o más procesadores lógicos. Procesador Físico: El dispositivo físico de un microprocesador capaz de ejecutar uno o más hilos de software al mismo tiempo. Cada dispositivo físico se conecta en un socket físico. Procesador Lógico: La modularidad básica de un recurso de procesador de hardware que permite al sistema operativo correr tareas o ejecutar un hilo. Cada procesador lógico puede ejecutar solamente un hilo a la vez. Procesador Multi-core: Un procesador físico que contiene más de un procesador core. Programación paralela: Es la programación en un lenguaje que permite explícitamente indicar como porciones diferentes del programa pueden ser ejecutados concurrentemente por diferentes procesadores. Scheduler: Es el planificador o asignador de tareas para sistemas operativos multitarea y multiproceso. Su función consiste en repartir el tiempo disponible de un microprocesador entre todos los procesos que están disponibles para su ejecución. Tecnología Hyper-Threading: Una funcionalidad en la familia de procesadores Intel IA-32, donde cada procesador core provee la funcionalidad de más de un procesador lógico. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 9 Índice General Contenido Agradecimientos: ..................................................................................................... 4 Resumen ................................................................................................................. 5 Abstract ................................................................................................................... 6 Glosario de Términos .............................................................................................. 7 Índice General ......................................................................................................... 9 Índice de Figuras ................................................................................................... 13 Índice de Tablas .................................................................................................... 15 Capítulo 1. Introducción .................................................................................... 16 1.1 Antecedentes ........................................................................................... 16 1.2 Objetivo de la tesis ...................................................................................16 1.2.1 Objetivo General ................................................................................ 17 1.2.2 Objetivos Particulares ........................................................................ 17 1.3 Justificación .............................................................................................. 17 1.4 Propuesta de Solución ............................................................................. 18 1.5 Organización de la tesis ........................................................................... 18 Capítulo 2. Arquitecturas paralelas ................................................................... 20 Estado del Arte ................................................................................................... 20 2.1 Análisis de rendimiento ............................................................................ 20 2.1.1 Aumento de velocidad (Speedup) ...................................................... 20 2.1.2 Eficiencia. .......................................................................................... 21 2.1.3 Ley de Amdahl ................................................................................... 23 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 10 2.1.4 El efecto Amdahl ................................................................................ 23 2.1.5 Ley de Gustafson-Barsis ................................................................... 23 2.1.6 La Métrica de Karp-Flatt .................................................................... 24 2.1.7 Relación de Isoeficiencia ................................................................... 25 2.2 Evolución del supercómputo .................................................................... 26 2.3 Arquitecturas ............................................................................................ 27 2.3.1 Arquitectura de Von Neumann ........................................................... 27 2.3.2 Taxonomía de Flynn .......................................................................... 28 2.4 Redes de interconexión ............................................................................ 31 2.5 Multiprocesamiento Simétrico (SMP) ....................................................... 32 2.6 Procesamiento Masivamente Paralelo (MPP) .......................................... 35 2.7 Clúster ...................................................................................................... 36 2.7.1 Antecedentes ..................................................................................... 36 2.7.2 Clúster Beowulf. ................................................................................. 37 2.7.3 Manejo de memoria en los sistemas clúster ...................................... 39 2.8 Distribución actual .................................................................................... 39 2.9 Sistema de Memoria ................................................................................ 41 2.9.1 Memoria cache .................................................................................. 42 2.9.2 Jerarquía de memoria ........................................................................ 43 2.9.3 Principio de localidad de memoria. .................................................... 45 2.9.4 Manejo de memoria ........................................................................... 46 Capítulo 3. Métricas de rendimiento y Benchmarks de sistemas paralelos ...... 47 3.1 Modelo LogP ............................................................................................ 47 3.2 FLOPS ..................................................................................................... 48 3.3 Linpack ..................................................................................................... 49 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 11 Capítulo 4. Consideraciones específicas. ......................................................... 50 4.1 Memoria Cache L2 en procesadores INTEL ............................................ 50 4.2 Affinity Mask ............................................................................................. 51 4.3 Tiempos de comunicación entre cores en un sistema clúster .................. 52 4.4 Trazado de la ejecución de una aplicación MS-MPI ................................. 53 4.5 Jumpshot .................................................................................................. 56 Capítulo 5. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura INTEL. ...................................................... 57 5.1 Definición del Problema ........................................................................... 57 5.2 Análisis del problema ............................................................................... 57 5.3 Metodología de Solución .......................................................................... 58 5.4 Propuesta ................................................................................................. 58 5.4.1 Procedimiento de afinidad de procesos ............................................. 58 5.4.2 Asignación de nodos ......................................................................... 59 5.4.3 Configuración de la afinidad de cores. ............................................... 61 5.5 Análisis del algoritmo ............................................................................... 63 5.6 Programa ................................................................................................. 63 Capítulo 6. Resultados ..................................................................................... 65 6.1 Incremento de rendimiento utilizando afinidad ......................................... 65 Capítulo 7. Conclusiones, recomendaciones y trabajos a futuro ...................... 77 7.1 Aportaciones de ésta tesis ....................................................................... 77 7.2 Conclusiones ............................................................................................ 77 7.3 Recomendaciones .................................................................................... 78 7.4 Trabajos a futuros .................................................................................... 78 Referencias ........................................................................................................... 79 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 12 Anexo 1. Infraestructura utilizada. ......................................................................... 82 Rendimiento máximo ......................................................................................... 83 Latencia ............................................................................................................. 85 Anexo 2. Código fuente del programa ................................................................... 88 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 13 Índice de Figuras FIGURA 2.1 INCREMENTO DE VELOCIDAD LINEAL .................................................................... 21 FIGURA 2.2 COMPARATIVO DE SPEEDUP REAL Y LINEAL ........................................................ 22 FIGURA 2.3 EJEMPLO DE EFICIENCIA REAL ................................................................................ 22 FIGURA 2.4 ARQUITECTURA DE VON NEUMANN ........................................................................ 29 FIGURA 2.5 TAXONOMÍA DE FLYNN ..............................................................................................30 FIGURA 2.6 (A) MEDIO COMPARTIDO (B) MEDIO CONMUTADO ................................................ 32 FIGURA 2.7 MULTIPROCESAMIENTO SIMÉTRICO ....................................................................... 33 FIGURA 2.8 RENDIMIENTO DE UN SISTEMA SMP ....................................................................... 34 FIGURA 2.9 MULTIPROCESAMIENTO SIMÉTRICO CON MEMORIAS CACHÉ ........................... 34 FIGURA 2.10 MULTIPROCESAMIENTO MASIVAMENTE PARALELO ........................................... 35 FIGURA 2.11 RENDIMIENTO DE UN SISTEMA MPP CONTRA EL NÚMERO DE PROCESADORES .................................................................................................................... 36 FIGURA 2.12 ARQUITECTURA DE UN CLÚSTER TIPO BEOWULF ............................................. 38 FIGURA 2.13 DISTRIBUCIÓN DE ARQUITECTURAS POR CANTIDAD DE SISTEMAS. FUENTE HTTP://WWW.TOP500.ORG .................................................................................................... 40 FIGURA 2.14 DISTRIBUCIÓN DE ARQUITECTURAS POR RENDIMIENTO. FUENTE HTTP://WWW.TOP500.ORG. ................................................................................................... 40 FIGURA 2.15 DISTRIBUCIÓN ACTUAL DE LAS ARQUITECTURAS. ............................................ 41 FIGURA 2.16 JERARQUÍA DE MEMORIA ....................................................................................... 44 FIGURA 4.1 ARQUITECTURA INTEL (FUENTE INTEL) .................................................................. 50 FIGURA 4.2 ESQUEMA DE MAPEO FÍSICO PARA PROCESADORES INTEL. ................................................... 52 FIGURA 4.3 TIEMPOS DE COMUNICACIÓN ENTRE CORES EN UN SISTEMA CLÚSTER ........ 53 FIGURA 5.1 PANTALLA DE PRESENTACIÓN DEL PROGRAMA DE OPTIMIZACIÓN .................. 63 FIGURA 5.2 PANTALLA DE EJECUCIÓN DEL PROGRAMA DE OPTIMIZACIÓN ......................... 64 FIGURA 6.1 REPRESENTACIÓN GRÁFICA DE LA INTERCOMUNICACIÓN ENTRE PROCESOS DE LA EJECUCIÓN DEL PROGRAMA DE HPL ....................................................................... 65 FIGURA 6.2 INCREMENTO EN RENDIMIENTO OBTENIDO AL MODIFICAR LA AFINIDAD EN EL PROGRAMA HPL ...................................................................................................................... 67 FIGURA 6.3 INCREMENTO DE VELOCIDAD OBTENIDO .............................................................. 71 FIGURA 6.4 REPRESENTACIÓN GRÁFICA DE LA INTERCOMUNICACIÓN ENTRE PROCESOS DE LA EJECUCIÓN DEL PROGRAMA CONTRASTSTRETCH ............................................... 72 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 14 FIGURA 6.5 TIEMPOS DE EJECUCIÓN CON DIFERENTE CONFIGURACIÓN DE AFINIDAD PARA LA APLICACIÓN DE CONTRASTSTRECH ................................................................... 73 FIGURA 6.6 REPRESENTACIÓN GRÁFICA DE LA INTERCOMUNICACIÓN ENTRE PROCESOS DE LA EJECUCIÓN DEL PROGRAMA PARA EL CÁLCULO DE PI ........................................ 75 FIGURA 6.7 TIEMPOS DE EJECUCIÓN CON DIFERENTE CONFIGURACIÓN DE AFINIDAD PARA LA APLICACIÓN DE PI ................................................................................................... 76 FIGURA ANEXO 1.1 TOPOLOGÍA DE LA INFRAESTRUCTURA UTILIZADA ................................ 82 FIGURA ANEXO 1.2 RENDIMIENTO MÁXIMO ................................................................................ 83 FIGURA ANEXO 1.3 RESULTADO DE LA APLICACIÓN DE DIAGNOSTICO PARA DETERMINAR LA LATENCIA DE LA RED DE MPI ........................................................................................... 86 FIGURA ANEXO 1.4 RESULTADO DE LA APLICACIÓN DE DIAGNOSTICO PARA DETERMINAR EL ANCHO DE BANDA DE LA RED DE MPI ............................................................................ 86 FIGURA ANEXO 1.5 RESULTADO DE LA APLICACIÓN PINGPONG PARA DETERMINAR LA LATENCIA Y EL ANCHO DE BANDA DE LA RED MPI ............................................................ 87 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 15 Índice de Tablas TABLA 2.1 CARACTERÍSTICAS DE LOS ELEMENTOS DE LA JERARQUÍA DE MEMORIA ........ 45 TABLA 3.1 REPRESENTACIÓN DE LOS FLOPS ............................................................................ 48 TABLA 4.1 FILTROS DE TRAZA ....................................................................................................... 55 TABLA 5.1 CORRELACIÓN DE OPTIMIZACIÓN DE AFINIDAD ..................................................... 59 TABLA 5.2 CORRELACIÓN DE OPTIMIZACIÓN DE NODOS ........................................................ 60 TABLA 6.1 PRUEBAS DE AFINIDAD HPL EN UN NODO ............................................................... 66 TABLA 6.2 SALIDA OBTENIDA AL EJECUTAR EL PROGRAMA HPL EN 8 CORES ..................... 67 TABLA 6.3 SALIDA OBTENIDA AL EJECUTAR EL PROGRAMA HPL EN 16 CORES ................... 68 TABLA 6.4 SALIDA OBTENIDA AL EJECUTAR EL PROGRAMA HPL EN 32 CORES ................... 70 TABLA 6.5 RESUMEN DE RESULTADOS PARA EL PROCESO DE LINPACK .............................. 70 TABLA 6.6 PRUEBA DE AFINIDAD CONTRASTSTRETCH EN UN NODO .................................... 73 TABLA 6.7 PRUEBA DE AFINIDAD PI EN UN NODO ...................................................................... 75 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 16 Capítulo 1. Introducción 1.1 Antecedentes A pesar de la velocidad vertiginosa con la que han evolucionado los sistemas de cómputo, nunca ha sido suficiente, el cómputo científico y de cálculo intensivo siempre ha estado en busca de equipos o sistemas con más poder de cómputo para resolver mejor las problemáticas presentadas en menor tiempo. Los procesadores cada vez son más rápidos, en cinco años los procesadores serán 10 veces más rápidos de lo que son ahora (ley de Moore), aunque es de suponerse (incluso el mismo Moore lo predijo) esta ley no se cumplirá en el futuro debido a límites físicos, por lo que los procesamientos en paralelos ha sido una solución muy eficiente para cubrir las necesidades de hoy en día [1]. Por otro lado, los sistemas de comunicaciones utilizadas en sistemas clúster no han evolucionado con la misma velocidad comparados con los procesadores, esto conlleva a que los procesadores desperdicien mucha de su capacidad de procesamiento en espera de datos, lo anterior es uno de los principales problemas ya que se presentan cuellos de botella en los sistemas de comunicación para las comunicaciones de MPI en los sistemas clúster de memoria distribuida, bajando de forma considerable el rendimiento global del sistema. 1.2 Objetivo de la tesis El presente trabajo pretende demostrar que a través de la optimización en la distribución de procesos, aprovechando el principio de jerarquía de memoria, se Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 17 pueden reducir los tiempos de comunicación entre los procesos, mejorando el desempeño de los sistemas clúster. 1.2.1 Objetivo General Diseñar e implementar un algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura INTEL. 1.2.2 Objetivos Particulares Desarrollar una metodología para la identificación de comunicaciones MS- MPI en procesos paralelos. Programar de una aplicación para determinar la mejor afinidad entre procesos de acuerdo al intercambio de datos. Desarrollar una metodología para la reasignación de procesos en un sistema clúster con Microsoft Windows HPC Server 2008, reduciendo los tiempos de comunicación entre procesos utilizandoel principio de jerarquía de memoria. 1.3 Justificación Uno de los principales problemas de los sistemas clúster es la latencia que existe cuando un procesador requiere datos que se encuentran físicamente en otro nodo. El principio de jerarquía de memoria no ha sido explorado en los sistemas de memoria distribuida. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 18 1.4 Propuesta de Solución La hipótesis de la presente propuesta consiste en reducir los tiempos de comunicación entre nodos optimizando la distribución de procesos utilizando la jerarquía de memoria. Con ello, además de reducir tiempos de acceso, se reduce el tráfico en la red de interconexión. Para lo anterior se desarrollarán las siguientes actividades: Evaluar la importancia del principio de jerarquía de memoria en sistemas tipo clúster conformados a partir de multiprocesadores simétricos. Medir rendimientos y tiempos de ejecución en diferentes procesos. Identificar los patrones de paso de mensajes entre nodos. Desarrollar un algoritmo para optimizar la afinidad entre procesos. Medir rendimientos y tiempos de ejecución en diferentes procesos aplicando el algoritmo de optimización. 1.5 Organización de la tesis Esta tesis se encuentra compuesta por 7 capítulos organizados de la siguiente manera: 1. El primer capítulo proporciona una introducción del trabajo a desarrollar y la importancia del mismo. Se presentan los objetivos del trabajo, la justificación del proyecto de tesis y el planteamiento del problema. 2. El segundo capítulo describe el estado del arte, en el cual se hace una investigación sobre los trabajos relacionados con el tema de esta tesis. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 19 3. El tercer capítulo describe de forma general las métricas de rendimiento y Benchmarks de sistemas paralelos. 4. El cuarto capítulo presenta las consideraciones específicas teóricas de la tesis, conteniendo los elementos o herramientas conceptuales esenciales para el desarrollo del proyecto. 5. El quinto capítulo detalla la implementación de la metodología para el desarrollo del algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura INTEL. 6. En el capítulo sexto se muestran los resultados obtenidos en las diversas pruebas realizadas a tres programas paralelos con diferentes características en cuanto a complejidad computacional e intercambio de datos entre procesos, mostrando los comparativos y porcentajes de optimización en la ejecución en diversos nodos del clúster. 7. El séptimo capítulo describe las conclusiones del trabajo haciendo énfasis en las aportaciones de esta tesis, las ventajas y casos específicos en donde se obtienen mejores resultados, así como los trabajos futuros que pueden desarrollarse tomando como base esta tesis. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 20 Capítulo 2. Arquitecturas paralelas Estado del Arte 2.1 Análisis de rendimiento 2.1.1 Aumento de velocidad (Speedup) El rendimiento constantemente es medido en términos de aumento de velocidad, esto es, que tan rápido se ejecuta un proceso paralelizado en comparación con una versión secuencial. speedup ψ Secuencial Paralelo Por ejemplo, si la versión secuencial corre en 80 minutos y la versión paralela corre en 20 minutos, tenemos un incremento de velocidad de ψ = 4. Si la versión paralela es ejecutada en 4 unidades de ejecución (core, procesador, nodo) esto significa que es un excelente resultado ya que las tareas secuenciales fueron perfectamente paralelizadas a través de los proceso distribuidos sin un retardo de comunicación importante. Esto es aplicable a paralelismo limitado solamente. Si no existen límites de recursos, un buen valor de ψ es log2p, donde p es el número de procesadores. Generalmente la meta de paralelizar una aplicación es obtener un incremento de velocidad lineal: teniendo n unidades de ejecución, la versión paralela deberá correr n veces más rápido que la versión secuencial como se ve en la Figura 2.1. Un incremento de velocidad lineal significa que la aplicación paralela utiliza todas las n unidades de ejecución de forma ideal [2]. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 21 Figura 2.1 Incremento de velocidad lineal Es poco realista pensar que encontraremos un incremento de velocidad lineal. En el caso específico de los clúster de memoria compartida es debido a la penalización que existe en la comunicación entre procesos paralelos (paso de mensajes MPI), la cual aumenta en medida que aumenta la latencia de la red de intercomunicación que se utiliza. En la Figura 2.2 se muestra el incremento de velocidad de un proceso ejecutado en el clúster desarrollado para la presente tesis. 2.1.2 Eficiencia. La eficiencia de un programa paralelo es una medición de la utilización de los procesadores. Podemos definir la eficiencia como el incremento de velocidad dividido por el número de procesadores usados: e iciencia speedupp Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 22 Figura 2.2 Comparativo de speedup real y lineal En donde 0 ≤ eficiencia ≤ 1. En el mejor de los casos, en donde el incremento de velocidad es lineal, la eficiencia podrá ser igual a 1, lo cual para situaciones prácticas no sucede debido a los tiempos de comunicación de los procesos [1]. En la Figura 2.3 se muestra el ejemplo de la eficiencia en la ejecución de un programa paralelo en el clúster desarrollado para la presente tesis, en donde se muestra que a medida que aumenta el número de unidades de procesamiento se disminuye la eficiencia de la utilización de los procesadores. Figura 2.3 Ejemplo de eficiencia real Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 23 2.1.3 Ley de Amdahl La ley de Amdahl está basada en la suposición de que se intenta resolver un problema de tamaño fijo tan rápido como sea posible. Definiendo a f como la fracción de operaciones dentro del proceso que se ejecutan de forma secuencial, y dado que 0 ≤ f ≤ 1. El máximo incremento de velocidad ψ que podemos encontrar en un proceso paralelo ejecutándose en p procesadores es [3]: ψ 1f 1 f /p 2.1.4 El efecto Amdahl Incrementando el tamaño del problema n incrementa el tiempo de procesamiento en mayor medida que aumenta el tiempo de comunicación. Por lo tanto manteniendo fijo el número de procesadores, el aumento de velocidad usualmente se incrementa en función del incremento del tamaño del problema n. A esto se le denomina el efecto Amdahl [4]. El tiempo de ejecución es una función de la complejidad computacional del programa, donde e=f(n). f(n) es usualmente un polinomio en n, de la forma O(n)=nk, k>1. Ejemplos: nlogn, n2, n3, etc. 2.1.5 Ley de Gustafson-Barsis La ley de Amdahl asume que el foco del cómputo paralelo es minimizar los tiempos de ejecución. La ley de Amdahl mantiene el tamaño del problema como una constante y demuestra como incrementando procesadores se puede reducir el tiempo de ejecución. La ley de Gustafson-Barsis establece que dado un programa paralelo que resuelve un problema de tamaño n utilizando p procesadores, en donde s denota la fracción Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 24 del tiempo total de ejecución en código serial. El máximo incremento de velocidad ψ obteniblepor este programa es [5] [6]: ψ ≤ p + (1 – p) s Mientras que la Ley de Amdahl determina el incremento de velocidad partiendo de un proceso serial y predice que tan rápido el proceso se puede ejecutar en múltiples procesadores, la Ley de Gustafson-Barsis hace lo contrario. Este inicia con un proceso paralelo y estima que tan rápido el proceso paralelo se ejecuta comparado con el mismo proceso ejecutándose en un solo procesador [1]. 2.1.6 La Métrica de Karp-Flatt Dado que la Ley de Amdahl y la Ley de Gustafson-Barsis ignoran el término del costo de comunicación en procesos paralelos, sobreestiman el valor del incremento de velocidad. Karp y Flatt han propuesto otra métrica, llamada fracción serial determinada experimentalmente, la cual puede proveer un valor más realista del rendimiento. Dado un proceso paralelo teniendo un incremento de velocidad ψ en p procesadores, en donde p > 1, la fracción serial determinada experimentalmente “e” es definida como [7]: e 1ψ 1p 1 1p La fracción serial determinada experimentalmente es una métrica muy útil por dos razones; la primera, toma en cuenta el término del costo de comunicación en procesos paralelos, y la segunda, puede ayudarnos a detectar otras fuentes de Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 25 retrasos o ineficiencias que son ignorados en los modelos simples de tiempos de ejecución paralelos. 2.1.7 Relación de Isoeficiencia Dada la definición anterior del Efecto Amdahl podemos establecer que la eficiencia esta típicamente en función del incremento del tamaño del problema, dado que la complejidad en las comunicaciones es usualmente menor que la complejidad computacional. Para mantener el mismo nivel de eficiencia cuando se agregan procesadores se debe de incrementar el tamaño del problema. La Escalabilidad de un sistema paralelo es la medida de la capacidad de incrementar el rendimiento en la misma medida en que el número de procesadores aumenta [1]. Suponiendo un sistema paralelo que exhibe una eficiencia Ɛ(n, p). Define: C ε n, p1 ε n, p y T n, p p 1 σ n pk n, p En donde: T(n,p) denota el tiempo de ejecución de un programa paralelo. σ(n) denota la porción secuencial del programa. k(n,p) denota el tiempo requerido para la comunicación entre procesos (overhead). Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 26 Para mantener el mismo nivel de eficiencia en la misma media que se incrementa el número de procesadores, n debe incrementarse en medida que se satisfaga la siguiente desigualdad [8]: T n, 1 CT n, p 2.2 Evolución del supercómputo El gobierno de los Estados Unidos ha jugado un rol clave en el desarrollo y uso de las computadoras de alto rendimiento. Durante la Segunda Guerra Mundial la armada de los Estados Unidos pagó por la construcción de ENIAC para poder acelerar el cálculo de tablas de artillerías. Las supercomputadoras son las más poderosas computadoras que pueden ser creadas [9]. El término de supercomputadora se dio por primera vez con un uso extenso con la introducción de la supercomputadora Cray-1 en 1976. La Crey-1 era un equipo de procesamiento vectorial en línea con la capacidad de ejecutar más de 100 millones de operaciones de punto flotante por segundo (FLOPS). Las supercomputadoras tenían un costo extremadamente elevado, por lo que casi exclusivamente se les encontraba en programas de investigación del gobierno de los Estados Unidos. A finales de la década de los 70’s se empezó a extender el uso de las supercomputadoras empezando a aparecer en industrias de mucho capital como la petrolera y de manufactura de automóviles. Diez años después cientos de corporaciones alrededor del mundo utilizaban supercomputadoras como apoyo para el desarrollo de sus negocios. Las velocidades de cómputo se han incrementado dramáticamente en los últimos 50 años. La ENIAC era capaz de ejecutar cerca de 350 multiplicaciones por segundo. Hoy en día las supercomputadoras son más de un billón de veces más rápidas, capaz de ejecutar trillones de operaciones de punto flotante por segundo. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 27 Los procesadores son alrededor de un millón de veces más rápidos de lo que eran hace 50 años, pero como dijimos en el párrafo anterior los sistemas de cómputo son más de un billón de veces más rápidos que hace 50 años, la gran diferencia radica en que los sistemas de hoy integran cientos de procesadores capaces de resolver problemas individuales más rápido que un solo procesador. A esto se le denomina computadora paralela. El significado de la palabra supercomputadora ha cambiado a lo largo del tiempo. En 1976 una supercomputadora hacía referencia a una Cray-1, una computadora de un solo CPU con un procesador vectorial lineal conectado a un sistema de memoria de alto rendimiento. Hoy en día supercomputadora hace referencia a un sistema paralelo con cientos de procesadores. El gran auge que han tenido los sistemas paralelos se debe en gran medida a su bajo costo de implementación. Desde mediados de la década de los 80’s los fabricantes de microprocesadores han incrementado el rendimiento de sus procesadores de punta en una tasa anual del 50 por ciento mientras que los precios se han mantenido más o menos constantes [10]. 2.3 Arquitecturas 2.3.1 Arquitectura de Von Neumann En 1945 el matemático Húngaro-Americano John Von Neumann formuló un diseño básico de arquitectura y modo de operación de computadoras que se denominó como la Máquina de Von Neumann. La arquitectura de Von Neumann se basa en una unidad de control que obtiene y analiza cada instrucción y sus datos a partir de una unidad de memoria, a esto se le ha denominado fetching, y los envía a una unidad de procesamiento para que la Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 28 instrucción sea ejecutada con sus datos, el resultado se envía nuevamente a la memoria. Las computadoras basadas en el diseño de Von Neumann constan principalmente de tres componentes: Unidad de Procesamiento Central (CPU, Central Process Unit). Es el dispositivo que interpreta y ejecuta las instrucciones, consta de cuatro elementos: Unidad Aritmética Lógica (ALU), Unidad de Control (CU), Contador de Programa (PC) y Registros. Memoria Principal. Utilizada para almacenar tanto las instrucciones como los datos. Sistema de Entrada/Salida. Permite la interacción con otros dispositivos. Las instrucciones se ejecutan de forma secuencial existiendo un bus para direcciones y uno para datos e instrucciones como medio de comunicación entre la memoria y el procesador, lo cual se ilustra en la Figura 2.4. [11]. El desempeño de una computadora basada en el arquitectura de von Neumann se ve afectada por dos factores: La tasa de ejecución de las instrucciones, directamente relacionada con las capacidades del procesador, y la velocidad a la que se puede intercambiar información entre la memoria y el procesador, la cual se le ha denominado como el cuello de botella de von Neumann. 2.3.2 Taxonomía de Flynn Michael J. Flynn en 1972 propuso una clasificación de arquitecturas de computadoras, la cual fue denominada como taxonomía de Flynn. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 29 Figura 2.4 Arquitectura de von Neumann Las computadoras operan ejecutando instrucciones sobre los datos. Un flujo de instrucciones indica a la computadora lo que tiene que hacer en cada paso. Flynn clasificó las arquitecturas de computadoras basándoseen la forma en que las computadoras relaciona sus instrucciones con los datos que se están procesando, dando origen a cuatro categorías, las cuales describen las arquitecturas paralelas más comunes: Single Instruction Single Data (SISD) Single Instruction Multiple Data (SIMD) Multiple Instruction Multiple Data (MIMD) Multiple Instruction Single Data (MISD). SISD. En esta categoría pertenecen todas las máquinas basadas en el diseño de Von Neumann, incluyendo los equipos monoprocesadores tradicionales, en los cuales existe un único flujo de instrucciones sobre un único flujo de datos. Este tipo de computadoras ejecutan algoritmos secuenciales. Asociado al procesador existe una única unidad de control, una única unidad aritmética lógica y una memoria privada. Figura 2.5 (a). SIMD. Es una máquina que consta de un arreglo de N procesadores, N flujos de datos que pueden verse como N memorias, una red de interconexión y una única unidad de control que manda instrucciones a cada procesador. Los procesadores Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 30 operan sobre distintos conjuntos de datos, obtenidos de flujos de datos distintos, en forma sincrónica. Por lo tanto cada procesador ejecuta la misma instrucción al mismo tiempo, pero con diferentes datos. En esta categoría están incluidos los procesadores vectoriales y los procesadores masivamente paralelos. Figura 2.5 (b). MISD. En estos equipos cada uno de los procesadores tiene su propia unidad de control y comparte con el resto de los procesadores una memoria común donde residen los datos. Cada procesador lleva a cabo operaciones distintas sobre el mismo dato en forma simultánea. Típicamente encontramos a los arreglos sintólicos en esta categoría. Figura 2.5 (c) UP2 UPn I(1) UP1 Dato c) MISD UP a) SISD I Dato UP2 Dato(2) UPn I Dato(n) UP1 Dato(1) b) SIMD I(2) I(n) UP2 UPn I(1) UP1 I(2) I(n) Dato(2) Dato(n)Dato(1) d) MIMD Figura 2.5 Taxonomía de Flynn Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 31 MIMD. Este tipo de máquinas corresponde a las más generales y poderosas en el paradigma de la computación paralela. En estos equipos existen múltiples procesadores, múltiples flujos de instrucciones y múltiples flujos de datos. Cada procesador está basado en el diseño de Von Neumann, con su propia unidad de control, unidad aritmética lógica y su propia memoria local. Cada procesador puede ejecutar su propio programa, con sus propios datos y contador de programa. Tenemos en esta categoría los equipos multiprocesadores incluyendo las networks of Workstations (NOW). Figura 2.5 (d) [12]. 2.4 Redes de interconexión Todas las computadoras con múltiples procesadores deben de proveer una forma de que los procesadores interactúen. En algunos sistemas los procesadores usan la red de interconexión para acceder a memoria compartida. En otros sistemas los procesadores usan la red de interconexión para mandar mensajes a cada uno de los demás. 2.4.1 Redes de interconexión fija y conmutadas Los procesadores en computadoras paralelas pueden comunicarse a través de medios de comunicación fija o conmutada. Un medio de interconexión fija puede tener un solo bus común, o más de un bus como las redes Banyan (mariposa, omega, hypercubo, etc). En el caso de un solo bus común solamente un mensaje a la vez es enviado, ver Figura 2.6(a). Los procesadores difunden sus mensajes por el medio. Cada procesador “escucha” cada mensaje y acepta solamente los mensajes que van destinados a él, Ethernet es un típico ejemplo de un medio compartido. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 32 Antes de enviar un mensaje, un procesador “escucha” hasta que el medio esta libre, entonces intenta enviar el mensaje. Si dos procesadores intentan enviar simultáneamente un mensaje, se produce una colisión y los mensajes son destruidos. Los procesadores tienen que esperar un tiempo aleatorio y entonces intentar enviar nuevamente el mensaje. La colisión de mensajes puede degradar significativamente el rendimiento de un medio compartido con alto tráfico. El medio de interconexión conmutado soporta mensajes punto a punto entre pares de procesadores, ver la Figura 2.6 (b). Cada procesador tiene su propia ruta de comunicación al switch. Los switches tienen dos importantes ventajas sobre medios compartidos. Soportan en una transmisión múltiples mensajes a través de diferentes pares de procesadores, y presentan un mayor nivel de escalamiento soportando un mayor número de procesadores [1]. Figura 2.6 (a) Medio Compartido (b) Medio Conmutado 2.5 Multiprocesamiento Simétrico (SMP) El concepto del procesamiento en paralelo establece el trabajo en forma simultánea y coordinadamente de varios procesadores en la ejecución de tareas. Dentro de las arquitecturas más utilizadas y simples para el procesamiento en paralelo encontramos el Multiprocesamiento Simétrico (Symmetric Multiprocessing / SMP). Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 33 Figura 2.7 Multiprocesamiento Simétrico El Multiprocesamiento Simétrico es una tecnología robusta y de bajo costo en donde los procesadores comparten la misma memoria principal y el bus del sistema, ilustrado en la Figura 2.7, lo cual simplifica en gran medida la programación de las aplicaciones y el diseño del sistema físico. El sistema operativo distribuye las tareas usando la memoria compartida entre los diversos procesadores, o bien es capaz de asignar toda la memoria requerida a una aplicación que la requiera. La principal desventaja del modelo de Multiprocesamiento Simétrico es la poca capacidad de crecimiento, esto se debe a que a medida que se agregan procesadores aumenta el tráfico en el bus de memoria, al momento de trabajar con ocho o más procesadores el nivel de tráfico necesario entre los procesadores y la memoria principal realizan un cuello de botella en el bus del sistema, lo cual decrementa el rendimiento del sistema a medida en que crece en procesadores, lo anterior se ilustra en la Figura 2.8. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 34 Figura 2.8 Rendimiento de un sistema SMP Una forma utilizada hasta el momento para reducir la problemática del tráfico en el bus el sistema ha sido el añadir memoria caché a cada uno de los procesadores, tal como se muestra en la Figura 2.9. P1 PnPn-1P2 Bus del Sistema Memoria Compartida Procesadores Cache 1 Cache n-1 Cache 2 Cache n Figura 2.9 Multiprocesamiento Simétrico con memorias caché Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 35 2.6 Procesamiento Masivamente Paralelo (MPP) Con el fin de solventar la problemática de saturación del bus del sistema en los sistemas SMP se desarrolló la arquitectura de Procesamiento Masivamente Paralelo (Massively Parallel Processing / MPP), la cual en lugar de utilizar una única memoria principal, utiliza una memoria lógicamente compartida, pero físicamente distribuida entre los procesadores, tal como se muestra en la Figura 2.10. Figura 2.10 Multiprocesamiento Masivamente Paralelo Los sistemas MPP son una tecnología altamente escalable, permitiendo construir sistemas de gran tamaño (cientos o miles de procesadores), Figura 2.11. Cada procesador utiliza su memoria local, lo cual disminuye el tráfico sobre el bus del sistema, en el caso de que un procesador requiera más memoria de laque cuenta localmente, tendrá que hacer uso de memoria fuera de su propia RAM, utilizando memoria libre en algún otro procesador. Para que un procesador tenga acceso a las áreas de memoria remotas utiliza un esquema de paso de mensajes. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 36 Figura 2.11 Rendimiento de un sistema MPP contra el número de procesadores 2.7 Clúster 2.7.1 Antecedentes El término y el uso de este tipo de tecnología surgen a finales de la década de los 50s y principios de los 60s, pero es hasta la década de los 80s en que los sistemas clúster toman un gran auge debido a los sistemas operativos distribuidos, el desarrollo de MPI y el incremento en poder de cómputo de las estaciones de trabajo. El primer producto comercial de tipo clúster fue ARCnet, siendo un desarrollo de la empresa DataPoint en 1977 y en 1984 la empresa Digital (ahora HP) logra tener un gran éxito con su sistema de VAXcluster y su sistema operativo propietario de VAX/VMS. Al llegar la década de los 90s se presentan factores que favorecen aún más el desarrollo y utilización de los sistemas clúster, por un lado en la parte de hardware seguimos encontrando aumento en las capacidades de las estaciones de trabajo y de las computadoras personales (PC) a costos muy accesibles, los elementos Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 37 para la interconexión en red de PC reducen sus costos significativamente. Por el lado del software con el surgimiento de LINUX como un sistema operativo libre, con las características y virtudes de los sistemas UNIX y con aportaciones de un innumerable grupo de personas alrededor del mundo y capaz de correr en estaciones de trabajo y computadoras personales. De esta forma desaparece el concepto de que el procesamiento paralelo era exclusivo de los equipos de supercomputo propietarios y de un muy elevado costo [13]. 2.7.2 Clúster Beowulf. A finales de 1993, Donald Becker y Thomas Sterling inician con el concepto para el diseño de un sistema clúster utilizando componentes de red y de cómputo comunes en el mercado, buscando una alternativa viable en costo-beneficio para los grandes y costosos equipos de supercomputo. A principios de 1994 trabajando en el Center of Excellence in Space Data and Information Sciences (CESDIS) y bajo el patrocinio del proyecto de la NASA HPCC/ESS (Earth and Space Sciences) inician el proyecto Beowulf. En la Figura 2.12 se muestra la arquitectura de un clúster tipo Beowulf. Existen diversos factores que han propiciado un gran crecimiento y desarrollo de los clústeres tipo Beowulf: Gracias al aumento en el uso de computadoras para automatización en oficinas, cómputo en el hogar, juegos y entretenimientos encontramos sistemas con componentes con una relación de costo-beneficio diferente a lo antes existente. Actualmente encontramos en el mercado equipos comunes que utilizan componentes comunes (microprocesadores, tarjetas madres, discos y tarjetas de red). Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 38 La competencia en mercados masivos ha bajado los precios y aumentado la disponibilidad de los equipos comunes. Figura 2.12 Arquitectura de un clúster tipo Beowulf La disponibilidad de software de código abierto, particularmente el sistema operativo Linux, compiladores GNU y herramientas de programación, así como bibliotecas de paso de mensajes MPI y PVM [14]. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 39 2.7.3 Manejo de memoria en los sistemas clúster Los clúster están clasificados dentro de las máquinas de memoria distribuida. A diferencia de la arquitectura SMP, en el cual se tiene un solo espacio de direccionamiento global, un clúster tiene un espacio de direccionamiento local independiente. Cada nodo tiene acceso solamente a su propia memoria local. La misma dirección de memoria en diferentes nodos hace referencia a diferentes localidades de memoria física. Sin un espacio de direcciones compartidas los procesadores interactúan con los demás a través de paso de mensajes, y por lo tanto no existe el problema de coherencia de la cache [1]. 2.8 Distribución actual En la Figura 2.13 se muestra la evolución de las arquitecturas paralelas dentro de las listas de la organización TOP500, la cual desde el año de 1993 ha realizado una identificación de los 500 sistemas de cómputo más poderosos en el mundo. En 1993 dentro de la lista de los 500 sistemas más poderosos del mundo encontramos una mayoría de sistemas SMP, seguidos por sistemas MPP, los cuales iniciaron un incremento casi continuo hasta el año 2000 en donde alcanzaron su punto más alto encontrando también en el mismo año el punto mínimo de los sistemas SMP y el inicio del crecimiento de los sistemas clúster, para el año 2002 encontramos el punto más alto de los sistemas constelación y un mayor nivel de incremento para los sistemas clúster. En la Figura 2.14 se presenta la gráfica de la evolución de las diferentes arquitecturas a lo largo del tiempo (06/1993 a 11/2009) en función del rendimiento, en donde podemos ver que hasta el año 2000 se tenía un amplio dominio con un 80% de arquitecturas MPP, a partir de este año los sistemas clúster iniciaron un incremento importante, alcanzando a mediados de 2004 su punto más alto con un 31%. A finales de 2009 tenemos un 39% para sistemas MPP y un 61% para sistemas Clúster. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 40 Figura 2.13 Distribución de arquitecturas por cantidad de sistemas. Fuente http://www.top500.org Figura 2.14 Distribución de arquitecturas por rendimiento. Fuente http://www.top500.org. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 41 Hoy en día (Noviembre 2009) tenemos un mercado principalmente dominado por los sistemas Clúster con un 83.4%, un 16.2% en sistemas MPP y tan solo un 0.4% Constelaciones, lo anterior se representa en la Figura 2.15 [14]. Figura 2.15 Distribución actual de las arquitecturas. 2.9 Sistema de Memoria Uno de los elementos fundamentales de un sistema de cómputo es la memoria, el rendimiento de ésta condiciona en gran medida el rendimiento del sistema en general. La memoria es utilizada para almacenar los programas que son ejecutados por el procesador. La memoria principal comúnmente no es capaz de almacenar todos los programas ejecutándose en un sistema de cómputo, de igual forma no toda la información en un sistema de cómputo es requerida por el procesador al mismo tiempo. Por tal motivo se utilizan dispositivos de almacenamiento de menor costo para almacenar la información que no es utilizada en ese momento por el procesador. La unidad de memoria que se comunica directamente con el procesador se denomina memoria principal, los demás dispositivos de almacenamiento de respaldo de la información son denominados la memoria auxiliar. Solamente la información que se utiliza al momento por el procesador es almacenada en la memoria principal, el resto de la Constelaciones , 0.40% MPP, 16.20% Clúster, 83.40% Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 42 información es almacenada en la memoria auxiliar y es enviada a la memoria principal de acuerdo a los requerimientos del procesador [15]. 2.9.1 Memoria cache El tiempo para ejecutar un programa depende en gran medida de la velocidad con la cual las instruccionesy los datos son leídos y escritos a la memoria principal. La memoria principal tiene la responsabilidad de almacenar toda la información que el procesador necesita en periodos de tiempos determinados. Las memorias se vuelven más lentas a medida que se incrementa su tamaño. La memoria principal es típicamente mucho más lenta que el CPU: la capacidad del procesador de ejecutar instrucciones y procesar datos supera, y por mucho, la capacidad de la memoria principal para proveerlos. Para solventar esta problemática la mayoría de los sistemas de cómputo incluyen memoria chache. Las memorias caches son de un tamaño pequeño y capaz de manejar velocidades cercanas a las del CPU y por lo tanto capaces de proveer las instrucciones y los datos que requiere el procesador a una tasa de transferencia más acorde a las demandas del CPU y así eliminar en gran medida los cuellos de botella por accesos a memoria. Solamente en los casos de que la memoria cache no contiene la información requerida se accede a la memoria principal [16]. Actualmente existen de diversos dispositivos y sistemas de almacenamiento, dada esta diversidad y acorde a sus características de costos, capacidad y velocidad podemos definir diferentes arreglos buscando las siguientes características. Disponer de la mayor cantidad de memoria disponible, dada las evoluciones de los programas de cómputo, los sistemas multiusuario y multitareas es necesario contar con una mayor cantidad de memoria en los sistemas para que esta no limite la ejecución de programas. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 43 Acceso a la información a velocidades cercanas a la velocidad de operación del procesador, evitando cuellos de botella en los accesos a memoria y tiempos muertos del procesador. Contar con sistemas de memoria rápida y alta capacidad de almacenamiento a costos bajos, utilización del concepto de jerarquía de memoria, lo cual permite trabajar con memorias con capacidades y velocidades diferentes para obtener el mejor desempeño del sistema al menor costo posible. 2.9.2 Jerarquía de memoria Con el fin de optimizar el manejo de la memoria en los sistemas de cómputo y obtener el mejor desempeño al menor costo, en lugar de utilizar un solo tipo de memoria se utiliza una combinación de diferentes tipos, lo cual nos da la flexibilidad para tener accesos de alta velocidad, mejorando el rendimiento del sistema, y contar con una gran capacidad de almacenamiento, sin que esto representen costos sumamente elevados. Para la jerarquía de memoria es necesario hacer una estructura de varios niveles de jerarquía con las siguientes consideraciones: El nivel más alto es el más cercano al procesador, en donde la memoria es rápida, de baja capacidad de almacenamiento y muy costosa. Cada nivel es más pequeño, más rápido y más caro por byte que el siguiente. Cada nivel está contenido en el siguiente. La memoria más lejana al procesador es lenta, con gran capacidad de almacenamiento y de bajo costo [17]. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 44 Figura 2.16 Jerarquía de Memoria En la Figura 2.16 se ilustra la distribución de los elementos que componen la jerarquía de memoria, así como en la Tabla 2.1 se identifican sus tamaños y velocidades. Cuando el procesador requiere de un dato lo busca en primera instancia en el nivel superior de la jerarquía (cache L1), en caso de que el dato solicitado se encuentre en este nivel es transferido al procesador con el mejor tiempo de acceso posible, si el dato no se encuentra en el primer nivel se busca en el nivel inmediato inferior de la jerarquía (cache L2), en el caso de que el dato se encuentre en cache L2 el bloque entero al cual pertenece se carga en cache L1, de lo contrario la petición pasa al siguiente nivel inferior en la jerarquía y así sucesivamente hasta encontrarlo. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 45 Tabla 2.1 Características de los elementos de la jerarquía de memoria Tipo de memoria Tamaño Tiempo de acceso Registros 512 bytes 1 ns Cache L1 32 KB 2-5 ns Cache L2 256 KB – 8 MB 15 ns Memoria principal 1 GB o + 40 ns Disco magnético 100 GB o + 10 ms Disco óptico 750 MB – 4.7 GB 300 ms Cinta magnética x GB – x TB seg-min 2.9.3 Principio de localidad de memoria. Dentro del principio de localidad de memoria podemos encontrar dos principios principales: a) Localidad Temporal (localidad en el tiempo). Establece que si se hace referencia a una instrucción o un dato, es muy probable que pronto sea referido nuevamente. Por lo tanto este principio establece el mantener los datos referidos recientemente en los niveles más altos con el fin de satisfacer rápidamente las referencias futuras. b) Localidad Espacial (localidad en el espacio). Si un objeto es requerido, habrá la tendencia de que pronto los objetos cercanos a él también sean requeridos. Por lo tanto para satisfacer referencias futuras rápidamente se llevan los datos vecinos de aquellos referidos recientemente a niveles más altos. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 46 2.9.4 Manejo de memoria Existen dos esquemas principales de manejo de memoria en esquemas de procesamiento paralelo: memoria compartida y memoria distribuida. 2.9.4.1 Memoria compartida La memoria es vista por todos los proceso como un solo bloque y cualquier proceso tiene acceso a cualquier región de la memoria, la comunicación entre los procesos se hace compartiendo datos que están en la memoria. 2.9.4.2 Memoria distribuida Los procesadores tienen asociados memoria privadas, en la cual no pueden tener acceso de forma directa los demás procesadores, la comunicación entre los procesos es a través de mensajes, las dos librerías de paso de mensajes más utilizadas son MPI (Message Passing Interface) y PVM (Parallel Virtual Machine). Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 47 Capítulo 3. Métricas de rendimiento y Benchmarks de sistemas paralelos 3.1 Modelo LogP Una arquitectura de multiprocesamiento de memoria distribuida en la cual los procesadores físicamente se comunican por mensajes punto a punto es caracterizada por cuatro parámetros descritos dentro del modelo LogP. El modelo LogP describe la configuración de una máquina abstracta en términos de cuatro parámetros de rendimiento. L: Latencia o retardo, incurre en la comunicación de un mensaje conteniendo una palabra (o un número pequeño de palabras) desde el módulo procesador/memoria fuente al destino. La latencia se presenta en cada evento de comunicación. o: overhead, definido como la longitud de tiempo que un procesador es ocupado en la transmisión o recepción de cada mensaje; durante este tiempo, el procesador no puede efectuar otra operación. El overhead se presenta por enviar y recibir procesos. g: Gap, se define como el mínimo intervalo de tiempo entre transmisiones consecutivas de mensajes o recepciones consecutivas de mensajes en un módulo; este es el tiempo que le toma a un mensaje el cursar a través del cuello de botella del ancho de banda en el sistema. P: El número de módulos de procesador/memoria. L, o y g están especificados en unidades de tiempo. Se asume que la red tiene una capacidad finita, de tal manera que al menos L/g mensajes pueden estar en tránsito de cualquier procesador o hacia cualquier procesador en un tiempo. Si un procesador intenta transmitir un mensaje más allá de este límite, queda en espera hasta que el mensajepuede ser enviado sin exceder el límite de la capacidad. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 48 La operación de comunicaciones más simple, enviando un paquete simple de una máquina a otra, requiere un tiempo de L+2o. Así, la latencia incluye el tiempo utilizado en las interfaces de red y el tiempo de tránsito a través de la red. Una operación de solicitud-respuesta, tal como una lectura o bloqueo de escritura toma un tiempo de 2L+4o. Ambos procesadores, tanto el que realiza la solicitud como el que brinda la respuesta están asociados por un tiempo 2o. El resto del tiempo puede ocuparse en procesamiento o enviando mensajes adicionales. El ancho de banda para mensajes disponible por procesador, o la taza de comunicación (mensajes por unidad de tiempo) es 1/g [18] [19]. 3.2 FLOPS Como unidad de medida del rendimiento de sistemas de cómputo, y especialmente los orientados a la realización de cálculos científicos que requieren un gran uso de operaciones de punto flotante, se utiliza el número de operaciones de punto flotante por segundo, denominados FLOPS por sus siglas en ingles (Floating point Operations Per Second). Tabla 3.1 Representación de los FLOPS Abreviatura Nombre Equivalencia MFLOPS megaFLOPS 106 FLOPS GFLOPS gigaFLOPS 109 FLOPS TFLOPS teraFLOPS 1012 FLOPS PFLOPS petaFLOPS 1015 FLOPS EFLOPS exaFLOPS 1018 FLOPS ZFLOPS zettaFLOPS 1021 FLOPS YFLOPS yottaFLOPS 1024 FLOPS XFLOPS xeraFLOPS 1027 FLOPS Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 49 Dado que el rendimiento en operaciones de punto flotante por segundo de los sistemas de cómputo actuales es muy alto, comúnmente encontramos representaciones de los FLOPS como se relaciona en la Tabla 3.1 3.3 Linpack Linpack fue desarrollado en el Argone National Laboratory por Jack Dongarra en 1976. Su utilización como programa de medición de rendimiento fue accidental, ya que originalmente fue desarrollado como un programa para resolver sistemas de ecuaciones. Linpack es una colección de subrutinas en Fortran que analizan y resuelven sistemas complejos de ecuaciones lineales. HPL (High-Performance Linpack) Es una implementación portable para pruebas de rendimiento en computadoras de memoria distribuida. HPL es un paquete de software que resuelve un sistema complejo (aleatorio) de ecuaciones lineales de aritmética de precisión doble (64 bits) en computadoras de memoria distribuida. El paquete de software HPL requiere la implementación de MPI, así como la implementación de Basic Linear Algebra Subprograms (BLAS) o Vector Signal Image Processing Library (VSIPL) [20] [21]. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 50 Capítulo 4. Consideraciones específicas. 4.1 Memoria Cache L2 en procesadores INTEL En los sistemas multi-core, el acceso a memoria puede representar un cuello de botella y afectar el rendimiento considerablemente, por lo tanto es importante tratar de aprovechar al máximo la memoria cache de nivel 2. De acuerdo a la arquitectura de los procesadores Intel Quad-Core, como se muestra en la Figura 4.1 los cores comparten la misma memoria cache L2 en pares [22]. El procesador Intel Core Duo tiene dos cores simétricos que comparten la cache de segundo nivel y una sola interface de bus (ver Figura 4.1). Dos hilos ejecutándose en dos cores en un procesador Intel Core Duo pueden tomar ventaja de compartir la cache de segundo nivel compartida, accediendo a una misma copia de los datos en cache sin necesidad de generar tráfico en el bus [23]. Figura 4.1 Arquitectura Intel (fuente INTEL) Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 51 No es posible determinar cuál Local APIC es usado en el momento de una ejecución, dado que esta información no se puede obtener en las propiedades del sistema o a través de la clase WMI de Win32_Processor. Para determinar la asociación es necesario ejecutar CPUCount, el cual está disponible en el sitio web de Intel. A continuación se muestra la salida que se obtuvo al ejecutarlo en un equipo de dos procesadores Quad-Core: Relationships between OS affinity mask, Initial APIC ID, and 3-level sub-IDs: AffinityMask = 1; Initial APIC = 0; Physical ID = 0, Core ID = 0, SMT ID = 0 AffinityMask = 2; Initial APIC = 1; Physical ID = 0, Core ID = 1, SMT ID = 0 AffinityMask = 4; Initial APIC = 2; Physical ID = 0, Core ID = 2, SMT ID = 0 AffinityMask = 8; Initial APIC = 3; Physical ID = 0, Core ID = 3, SMT ID = 0 AffinityMask = 16; Initial APIC = 4; Physical ID = 4, Core ID = 0, SMT ID = 0 AffinityMask = 32; Initial APIC = 5; Physical ID = 4, Core ID = 1, SMT ID = 0 AffinityMask = 64; Initial APIC = 6; Physical ID = 4, Core ID = 2, SMT ID = 0 AffinityMask = 128; Initial APIC = 7; Physical ID = 4, Core ID = 3, SMT ID = 0 4.2 Affinity Mask La affinity mask es una máscara de bit, la cual indica que proceso debe de ser corrido por cual procesador a través del scheduler en un sistema operativo. Existe una asociación directa entre el número de core y la affinity mask solicitada por Windows Server, y dado las referencias [22] y [23] mencionadas anteriormente sabemos que los cores comparten la memoria cache L2. En la Figura 4.2 se muestra el esquema de mapeo físico para los servidores utilizados en el clúster de prueba, los cuales constan de dos procesadores Quad- Core de Intel por nodo [24]. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 52 Figura 4.2 Esquema de mapeo físico para procesadores Intel. 4.3 Tiempos de comunicación entre cores en un sistema clúster A la comunicación establecida entre cores del mismo procesador que comparten la memoria cache L2 le denominaremos T1, llamaremos T2 a la comunicación entre cores en el mismo procesador que no comparten la memoria cache L2, así como también entre cores de diferente socket dentro del mismo equipo y T3 a la comunicación entre cores en diferentes nodos. Esto se muestra en la Figura 4.3 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 53 Figura 4.3 Tiempos de comunicación entre cores en un sistema clúster En pruebas realizadas en un nodo se aprecia que la memoria cache se comparte en pares. La velocidad de T1 se encuentra entre el rango de los 3.6 GB/s, mientras que tenemos velocidades de T2 de entre 1.3 GB/s y 1.2 GB/s para comunicación entre cores dentro del mismo socket y cores en sockets diferentes dentro del mismo nodo respectivamente. Para el caso de T3 depende en gran medida del tipo de red de interconexión entre nodos utilizado, para nuestro caso particular se obtuvo una velocidad máxima de 136.66 MB/s. Como podemos ver T1 < T2 << T3. Por lo tanto el presente trabajo de tesis pretende ordenar los procesos dentro de un programa paralelo ejecutado en un sistema clúster optimizando las comunicaciones en medida que el mayor intercambio de comunicación entre procesos se ejecute en tiempos T1 y T2. 4.4 Trazado de la ejecución de una aplicación MS-MPI Para realizar el trazado de la ejecución de una aplicación MPI bajo el sistema operativo de Microsoft Windows HPC Server 2008, se realiza a través de la utilería Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 54 de Event Tracing for Windows (ETW), la cual se encuentra integrada en la versión del sistema operativo. Al realizar el trazado podemos tener tres diferentesformatos en el registro de la traza: Formato texto. Open Trace Format (OTF). Formato CLOG2 (Formato de registro de la Argonne National Labs event- based) De igual forma podemos encontrar diferentes visualizadores para estos tipos de formatos: Jumpshot (herramienta de visualización de la Argonne National Labs). Herramientas de Visual Studio y Windows ETW. Vampir Viewer for Windows (Herramienta de visualización para el formato OTF). Para realizar la traza hay que agregar el argumento “-trace” al comando con el cual ejecutamos nuestra aplicación MPI. Por ejemplo: mpiexec –trace xhpl.exe En donde se ejecuta la aplicación xhpl.exe y se realiza una traza para todos los eventos MPI. Todos los eventos son trazados por default, pero se pueden establecer filtros con el argumento “-trace” para habilitar solamente la traza de los eventos que sean requeridos. En la Tabla 4.1 se muestra la lista completa de los filtros que se pueden aplicar con el argumento de trazado. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 55 Tabla 4.1 Filtros de traza Argumento Descripción Valor ALL All APIs and communication 0xFFFFFFFF API All APIs 0x00007FFF PT2PT Point to point APIs 0x00000001 POLL Point to point polling APIs (MPI_Iprobe, MPI_Test***) 0x00000002 COLL Collective APIs 0x00000004 RMA One sided APIs 0x00000008 COMM Comm APIs 0x00000010 ERRH Error handler APIs 0x00000020 GROUP Group APIs 0x00000040 ATTR Attribute APIs 0x00000080 DTYPE Datatype APIs 0x00000100 IO IO APIs 0x00000200 TOPO Topology APIs 0x00000400 SPAWN Dynamic processes APIs 0x00000800 INIT Initialization APIs 0x00001000 INFO Info APIs 0x00002000 MISC Misc APIs 0x00004000 INTERCONN All Interconnects Communication 0x000F8000 ICSOCK Sockets Interconnect Communication 0x00008000 ICSHM Shared Memory Interconnect Communication 0x00010000 ICND Network Direct Interconnect Communiation 0x00020000 Los archivos del registro de la traza son escritos en cada nodo en el que corre la tarea. Por default, los archivos de registro se guardan en el directorio del perfil del usuario que ejecuta la tarea. El nombre de los archivos del registro de la traza se generan de acuerdo a la siguiente nomenclatura. mpi_trace_{JobID}.{TaskID}.{TaskInstanceID}.etl En donde: JobID es el número identificador del trabajo, variable de ambiente %CCP_JOBID% de Windows HPC Server 2008. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 56 TaskID es el número identificador de la tarea, variable de ambiente %CCP_TASKID% de Windows HPC Server 2008. TaskInstanceID es el número identificador de la instancia de la tarea, variable de ambiente %CCP_TASKINSTANCEID% de Windows HPC Server 2008. Este número de instancia es utilizado por trabajos parametrizados en donde una sola tarea puede representar una serie de comandos corriendo en el clúster. Para la mayoría de los trabajos de MPI este valor será cero [25]. 4.5 Jumpshot Jumpshot es un programa de visualización gráfica para los archivos log con formato SLOG-2, el cual permite ver los eventos MPI y como se relacionan en el tiempo, además provee una estructura jerárquica para almacenar un gran número de objetos en una forma de visualización escalable y eficiente. El nivel de detalle soportado a través de la visualización gráfica provee un nivel alto de detalle sin la necesidad de leer grandes cantidades de datos en el motor de despliegue gráfico. Jumpshot también provee un convertidor de archivos log integrado para todos los formatos de traza de SLOG-2, incluyendo CLOG, CLOG-2, RLOG y UTE [26]. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 57 Capítulo 5. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura INTEL. 5.1 Definición del Problema La herramienta de administración de trabajos es la encargada de distribuir las tareas en un sistema clúster, realizando la asignación de procesos a las diferentes unidades de procesamiento (core, CPU, nodo), lo cual se realiza de forma aleatoria sin que exista un análisis de la comunicación entre procesos. 5.2 Análisis del problema El presente trabajo de tesis pretende demostrar que a través de un análisis previo de la comunicación de datos en la ejecución de un programa paralelo se puede realizar una distribución de procesos utilizando el principio de jerarquía de memoria para reducir los tiempos de latencia en las comunicaciones interprocesos y aumentar el rendimiento de los sistemas clúster de memoria distribuida al reducir el tráfico en la red de interconexión. En el caso de programas paralelos en donde existe una comunicación intensa entre procesos, la asignación de procesos de acuerdo al nivel de intercambio de datos entre ellos puede representar un incremento de rendimiento considerable. Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 58 5.3 Metodología de Solución 5.4 Propuesta 5.4.1 Procedimiento de afinidad de procesos Asumiendo que el procedimiento se ejecuta sobre dos nodos con dos procesadores y cada procesador con 8 cores, utilizando Microsoft Windows Server 2008 HPC Edition (SP2). Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 59 El procedimiento consta principalmente de dos pasos: Asignación de nodos y configuración de la afinidad de cores. Tomaremos como ejemplo la Tabla 5.1 en donde se muestra la correlación de optimización de afinidad entre procesos que deseamos ejecutar en nuestro programa paralelo. Tabla 5.1 Correlación de optimización de afinidad Core Rank 0 0 1 15 2 6 3 9 4 12 5 14 6 3 7 1 8 10 9 13 10 8 11 2 12 5 13 7 14 4 15 11 5.4.2 Asignación de nodos Para asignar el Rank al nodo apropiadamente se requiere utilizar un archivo de maquina como parámetro al mpiexec. Este archivo de maquina es un archivo en formato de texto el cual se envía a través del parámetro –machinefile al comando mpiexec. De acuerdo a la Tabla 5.1 Correlación de optimización de afinidad anterior hacemos la identificación de nodo para cada uno de los ranks, recordando que el Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 60 nodo uno ejecutará los ranks del 0 al 7 y el nodo dos del 8 al 15, quedando de la siguiente forma como se muestra en la Tabla 5.2 Tabla 5.2 Correlación de optimización de nodos Core Rank Nodo 0 0 01 1 15 02 2 6 01 3 9 02 4 12 02 5 14 02 6 3 01 7 1 01 8 10 02 9 13 02 10 8 02 11 2 01 12 5 01 13 7 01 14 4 01 15 11 02 Por lo tanto nuestro archivo de nodos quedará de la siguiente forma Node01 Node02 Node01 Node02 Node02 Node02 Node01 Algoritmo de optimización de procesos paralelos bajo el modelo de programación MS-MPI en arquitectura Intel 61 Node01 Node02 Node02 Node02 Node01 Node01 Node01 Node01 Node02 Archivo Nodos.txt Cuando se ejecutan los procesos mpi se lee este archivo y se crean los ranks en orden, para nuestro ejemplo el archivo Nodos.txt establece la siguiente relación: rank0 en nodo1, rank1 en nodo1, rank2 en nodo1, rank3 en nodo2, rank4 en nodo2, etc. Job submit /exclusive /askednodes:HPC-CIDETEC-N01, HPC- CIDETEC-N02 /numcores:16 mpiexec /machinefile \\HPC-CIDETEC- HD1\Public\linpak\Nodos.txt xhpl.exe 5.4.3 Configuración de la afinidad de cores. El segundo paso es asignar los cores físicos de acuerdo al modelo de optimización
Compartir