Logo Studenta

Algoritmo-de-optimizaciAn-de-procesos-paralelos-bajo-el-modelo-de-programaciAn-MS-MPI-en-arquitectura-intel

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

Otros materiales