PDF de programación - Procesamiento Paralelo en Redes Linux Utilizando MPI

Procesamiento Paralelo en Redes Linux Utilizando MPI

Alumno: Vicente F. Reyes Puerta

Director: Jose Antonio Jiménez Millán

Julio 2003

2

Resumen

El presente documento realiza un estudio de investigación que aborda el procesamiento pa-
ralelo en redes de ordenadores. De esta manera se analiza la utilización de los clusters (grupos
de ordenadores conectados en red) a modo de computador virtual paralelo como plataforma
para la ejecución de aplicaciones paralelas.

El entorno utilizado para realizar dicho estudio es el sistema operativo Linux, el cual ofrece
todas las facilidades de acceso a dispositivos y comunicación necesarias para la ejecución de
los algoritmos paralelos. Para la implementación de los algoritmos paralelos desarrollados
hemos utilizado la interfaz MPI (“Message Passing Interface”, Interfaz de Paso de Mensajes).
Dicha interfaz es un estándar que define la sintaxis y la semántica de las funciones contenidas
en una librería de paso de mensajes diseñada para ser usada en programas que exploten la
existencia de múltiples procesadores. De este modo no sólo conseguimos que el desarrollo de
los algoritmos sea más claro y sencillo, si no que además logramos que sean portables.

El estudio realizado queda dividido en tres partes diferenciadas que coinciden con la es-
tructura del documento. En un principio hacemos un estudio general sobre el procesamiento
paralelo, y establecemos una clasificación detallada sobre los distintos tipos de paralelismo
existentes en la actualidad. En la segunda parte realizamos un análisis detallado de la interfaz
de paso de mensajes MPI, ejemplificando la información ofrecida con diversos algoritmos es-
critos en C que realizan cómputos paralelos utilizando dicha interfaz. Por último generamos
un estudio de los resultados obtenidos en las ejecuciones explicando paso a paso la manera en
la que han sido cosechados.

3

4

Índice general

Objetivos

Desarrollo

I Sistemas de Procesamiento Paralelo

1. Introducción

1.1. Utilidades del Procesamiento Paralelo . . .
1.2. Definiciones Básicas
. . . . .

. . . . . .

.

1.3.1. Paralelismo Implícito o de Bajo Nivel
1.3.2. Paralelismo Explícito o de Alto Nivel

. . . . . .
. . . . . .
1.2.1. Características Físicas de la Comunicación . .
. . . . . .
1.2.2. Estándares Relacionados .
1.3. Clasificación Sistemas Paralelos .
. . . . . .
. . . . .
. . . . .
1.4. Arquitecturas Basadas en Paralelismo Implícito . . . .
. . . . . .
. . . . . .
. . . . . .
1.5. Arquitecturas Basadas en Paralelismo Explícito . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

1.5.1. Multiprocesadores
1.5.2. Multicomputadores
1.5.3. Procesadores Matriciales
1.5.4. Procesadores Vectoriales .

1.4.1. Segmentación o pipeline .
1.4.2. Tecnología SWAR . . . .
1.4.3. Procesadores Auxiliares
.

. . . .
. . .

. . . . .
. . . . .

. . . . .
. . . . .
. . . . .

. . . . .
. . . . .
. . . . .
. . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

2. Herramientas Desarrollo Software Paralelo

2.1. Modelos de Interacción entre Procesadores
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

2.1.1. Paso de Mensajes . . . . .
2.1.2. Memoria Compartida . . .
2.2. Utilidades de Desarrollo . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

2.2.1. PVM . . . . .
2.2.2. MPI
. . . . .
2.2.3. P4 . .
. . . . .
2.2.4. Express . . . .
2.2.5. Linda . . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

5

I

III

1

3
3
4
4
5
6
6
7
9
9
13
15
19
19
26
37
38

43
43
43
46
49
49
50
51
52
53

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

6

II Guía MPI

3. El Estándar MPI

ÍNDICEGENERAL

55

57
57
58
59
62
62
62
63
64
64

67
67
68
69
69
70
70
71

73
73
74
76
77
78
79
80
80
80
86

93
93
94
96
97
98

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

3.1. Origen . . . .
3.2. Historia . . .
. .
3.3. Objetivos
3.4. Usuarios
. .
3.5. Plataformas .
3.6. Versiones
. .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
3.6.1. MPI-1 . . . . . .
3.6.2. MPI-2 . . . . . .
Implementaciones . . . .

3.7.

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

4. Conceptos Básicos

4.1. Algoritmo ¡Hola Mundo! . . . . .
4.2. Programas MPI en General . . . .
4.3.
4.4. El Problema de la Entrada/Salida .
. . . .
4.5. Ubicación de los Procesos
4.6.
.
. . . . .
4.7.

. . . . . .
. . . . . .
Informándonos del Resto del Mundo . . . . .
. . . . . .
. . . . . .
. . . . . .
Información Temporal
Implementación Algoritmo ¡Hola Mundo! . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

5. Paso de Mensajes

. . . . .

. . . . . .
5.1. Algoritmo Cálculo de Áreas mediante Montecarlo . . .
. . . . . .
. . . . .
5.2. El Entorno del Mensaje .
. . . . . .
. . . . . .
5.3. Funciones de Paso de Mensajes Bloqueantes .
. . . . .
. . . . . .
5.4. Funciones de Paso de Mensajes No Bloqueantes . . . .
. . . . . .
5.5. Agrupaciones de Datos .
. . . . .
. . . . . .
. . . . .
5.5.1. Tipos Derivados
5.5.2. Vectores . . . . .
. . . . . .
. . . . .
Implementación Cálculo de Áreas mediante Montecarlo . . . . . .
Implementación con Mensajes Bloqueantes . .
5.6.1.
. . . . . .
5.6.2.
Implementación con Mensajes No Bloqueantes . . . . . .

. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .

5.6.

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

6. Comunicación Colectiva

6.1. Algoritmo Regla del Trapecio . .
. . . . . .
6.2. Distribución y Recolección de los Datos . . .
6.3. Operaciones de Comunicación Colectiva . . .
6.4. Operaciones de Reducción . . . .
. . . . . .
Implementación Regla del Trapecio . . . . .
6.5.

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

7. Comunicadores y Topologías

7.1. Algoritmo Multiplicación de Matrices de Fox . . . . .
7.2. Comunicadores . . . . .
. . . . .
7.3. Trabajando con Grupos, Contextos y Comunicadores .
7.4. Particionamiento de los Comunicadores . . .
. . . . .

. . . . . .

. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .

105
. 105
. 106
. 107
. 110

ÍNDICEGENERAL

. . . . .
7.5. Topologías . .
7.6. División de Rejillas . .
7.7.

. . . . . .
. . . . . .
Implementación Multiplicación de Matrices de Fox . .

. . . . . .
. . . . . .

. . . . .
. . . . .

7

. . . . .
. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .

. 111
. 113
. 114

III Análisis del Rendimiento

8. Evaluación del Sistema

8.1. Utilidad mpptest . . . .

. . . . . .
8.1.1. Compilación y Ejecución .
8.1.2. Formatos de Salida . . . .
. . . . . .
8.1.3. Visualización .
8.1.4. Gráficos . . . .
. . . . . .
. . . . . .
8.1.5. Operaciones . .
8.2. Pruebas Realizadas . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
8.2.1. Comunicación Bloqueante . . . . .
. . . . .
8.2.2. Comunicación No Bloqueante . . .
8.2.3. Participación Total de los Procesos .
. . . . .
8.2.4. Solapamiento entre Comunicación y Procesamiento . . .
8.2.5. Comunicación Colectiva .
. . . . .
. . . . .
. . . . . .
8.2.6. Fiabilidad . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . . .
. . . . . .

. . . . .
. . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

9. Evaluación de los Algoritmos

9.1. Herramientas de Monitorización .
9.1.1. Ficheros de Recorrido . .
9.1.2. Trazado de la Ejecución .
9.1.3. Animación en Tiempo Real
9.2. Criterios de Evaluación . . . . . .
9.2.1. Tiempo de Ejecución . . .
9.2.2. Número de Procesadores .
9.2.3. Coste . . . . .
. . . . . .
. . . . . .
9.3. Resultados Obtenidos .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
9.3.1. Algoritmo Cálculo de Áreas mediante Montecarlo Bloqueante . . .
9.3.2. Algoritmo Cálculo de Áreas mediante Montecarlo No Bloqueante .
. . . . . .
9.3.3. Algoritmo Regla del Trapecio . . .
. . . . . .
. . . . . .
9.3.4. Algoritmo Multiplicación de Matrices de Fox .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . .
. . . . .
. . . . .
. . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . .
. . . . .

. . . . .
. . . . .

A. Instalación, Configuración y Manejo de MPICH
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

. . . . . .
A.1. Dispositivos .
A.2.