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 paralelo 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 estructura 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 escritos 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

I

Desarrollo

III

I Sistemas de Procesamiento Paralelo

1

1. Introducción 1.1. Utilidades del Procesamiento Paralelo . . . . . . . 1.2. Definiciones Básicas . . . . . . . . . . . . . . . . 1.2.1. Características Físicas de la Comunicación 1.2.2. Estándares Relacionados . . . . . . . . . . 1.3. Clasificación Sistemas Paralelos . . . . . . . . . . 1.3.1. Paralelismo Implícito o de Bajo Nivel . . . 1.3.2. Paralelismo Explícito o de Alto Nivel . . . 1.4. Arquitecturas Basadas en Paralelismo Implícito . . 1.4.1. Segmentación o pipeline . . . . . . . . . . 1.4.2. Tecnología SWAR . . . . . . . . . . . . . 1.4.3. Procesadores Auxiliares . . . . . . . . . . 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 . . . . . . . . . . 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

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

. . . . . . . . .

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

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

ÍNDICE GENERAL

6

II

Guía MPI

3. El Estándar MPI 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 . . 3.7. Implementaciones

55 . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

57 57 58 59 62 62 62 63 64 64

4. Conceptos Básicos 4.1. Algoritmo ¡Hola Mundo! . . . . . . . . . 4.2. Programas MPI en General . . . . . . . . 4.3. Informándonos del Resto del Mundo . . . 4.4. El Problema de la Entrada/Salida . . . . . 4.5. Ubicación de los Procesos . . . . . . . . 4.6. Información Temporal . . . . . . . . . . 4.7. Implementación Algoritmo ¡Hola Mundo!

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

67 67 68 69 69 70 70 71

. . . . . . . . . .

73 73 74 76 77 78 79 80 80 80 86

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

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 . . . . . . . . . . . . . . . . . . . . . 5.6. Implementación Cálculo de Áreas mediante Montecarlo 5.6.1. Implementación con Mensajes Bloqueantes . . 5.6.2. Implementación con Mensajes No Bloqueantes 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 . . . . . . . 6.5. Implementación Regla del Trapecio . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

93 93 94 96 97 98

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

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

ÍNDICE GENERAL

7

7.5. Topologías . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.6. División de Rejillas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.7. Implementación Multiplicación de Matrices de Fox . . . . . . . . . . . . . . 114

III Análisis del Rendimiento

125

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 . . . . . . . . . . . . . . . . . . . . . .

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

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

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

127 127 128 128 129 129 130 130 131 132 133 135 136 140

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 . . . . . . . . . . .

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

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

143 143 144 146 147 148 148 149 149 149 149 151 154 159

. . . . . . . .

163 164 165 165 166 166 167 168 170

A. Instalación, Configuración y Manejo de MPICH A.1. Dispositivos . . . . . . . . . . . . . . . . . . A.2. Obtención . . . . . . . . . . . . . . . . . . . A.3. Compilación e Instalación . . . . . . . . . . A.4. Configuración . . . . . . . . . . . . . . . . . A.4.1. El Fichero de Máquinas . . . . . . . A.4.2. RSH . . . . . . . . . . . . . . . . . . A.4.3. SSH . . . . . . . . . . . . . . . . . A.4.4. Secure Server . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

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

. . . . . . . .

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

. . . . . . . .

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

. . . . . . . .

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

. . . . . . . .

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

. . . . . . . .

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

. . . . . . . .

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

. . . . . . . .

. . . . . . . .

. . . . . . . .

ÍNDICE GENERAL

8

A.5. Compilación y Enlace de Programas . . . . . . . . . . . . . . . . . . . . . . 171 A.6. Ejecución de Programas con mpirun . . . . . . . . . . . . . . . . . . . . . . 172 A.7. Extensión MPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 B. Manual de Referencia B.1. MPI_Bcast . . . . . . . . B.2. MPI_Cart_coords . . . . . B.3. MPI_Cart_create . . . . . B.4. MPI_Cart_rank . . . . . . B.5. MPI_Cart_sub . . . . . . . B.6. MPI_Comm_create . . . . B.7. MPI_Comm_group . . . . B.8. MPI_Comm_rank . . . . . B.9. MPI_Comm_size . . . . . B.10. MPI_Comm_split . . . . . B.11. MPI_Finalize . . . . . . . B.12. MPI_Get_processor_name B.13. MPI_Group_incl . . . . . B.14. MPI_Init . . . . . . . . . . B.15. MPI_Irecv . . . . . . . . . B.16. MPI_Isend . . . . . . . . . B.17. MPI_Recv . . . . . . . . . B.18. MPI_Reduce . . . . . . . B.19. MPI_Send . . . . . . . . . B.20. MPI_Sendrecv_replace . . B.21. MPI_Type_commit . . . . B.22. MPI_Type_struct . . . . . B.23. MPI_Type_vector . . . . . B.24. MPI_Wait . . . . . . . . . B.25. MPI_Waitall . . . . . . . . B.26. MPI_Waitany . . . . . . . B.27. MPI_Wtime . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202

Conclusiones

203

Bibliografía

208

Direcciones URL

209

Índice de figuras 1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8. 1.9. 1.10. 1.11. 1.12. 1.13. 1.14. 1.15. 1.16. 1.17. 1.18. 1.19.

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

6 7 9 10 11 12 16 19 20 21 22 27 27 27 28 30 37 40 41

2.1. Modelo Básico para Paso de Mensajes . . . . . . . . . . . . . . . . . . . . . 2.2. Modelo Básico para Memoria Compartida . . . . . . . . . . . . . . . . . . . 2.3. Esquema Básico Utilización MPI . . . . . . . . . . . . . . . . . . . . . . . .

44 47 51

3.1. Logo MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

5.1. Generación Puntos Aleatorios . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Cálculo Hipotenusa Punto Aleatorio . . . . . . . . . . . . . . . . . . . . . .

74 75

6.1. Procesos estructurados en árbol . . . . . . . . . . . . . . . . . . . . . . . . .

95

8.1. 8.2. 8.3. 8.4. 8.5.

Clasificación Paralelismo Implícito . . . . . . . . . . Clasificación Paralelismo Explícito . . . . . . . . . . Ciclo de Instrucción de 2 etapas (A) . . . . . . . . . Ciclo de Instrucción de 10 etapas . . . . . . . . . . . Ciclo de Instrucción de 2 etapas (B) . . . . . . . . . Cauce de 6 etapas . . . . . . . . . . . . . . . . . . . Procesamiento Digital de Señales . . . . . . . . . . . Esquema Multiprocesador . . . . . . . . . . . . . . Organización Básica Bus de Tiempo Compartido . . Organización Bus de Tiempo Compartido con Caché Organización Memorias Multipuerto . . . . . . . . . Topología Anillo . . . . . . . . . . . . . . . . . . . Topología Malla . . . . . . . . . . . . . . . . . . . . Topología Árbol . . . . . . . . . . . . . . . . . . . . Topología Hipercubo . . . . . . . . . . . . . . . . . Objetivo Procesamiento Paralelo en Clusters . . . . . Esquema Procesador Matricial . . . . . . . . . . . . Esquema Procesador Vectorial . . . . . . . . . . . . Cray SX-6 . . . . . . . . . . . . . . . . . . . . . . .

Gráfico Comunicación Bloqueante . . . . . . . . . Comparación Com.Bloqueante - No Bloqueante . . Comparación Com. Participativa - No Participativa Comparación Com. Solapada - No Solapada . . . . Gráfico Comunicación Colectiva . . . . . . . . . . 9

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

. . . . .

132 134 135 137 139

ÍNDICE DE FIGURAS

10 9.1. 9.2. 9.3. 9.4. 9.5. 9.6. 9.7. 9.8. 9.9. 9.10. 9.11. 9.12. 9.13.

Animación en Tiempo Real . . . . . . . . . . . . . . . . . . . Modelo Ejecución Cálculo de Áreas Bloqueante 8 Procesos . . Gráfico Tiempo Ejecución Cálculo de Áreas Bloqueante . . . Gráfico Coste Cálculo de Áreas Bloqueante . . . . . . . . . . Modelo Ejecución Cálculo de Áreas No Bloqueante 8 Procesos Gráfico Tiempo Ejecución Cálculo de Áreas No Bloqueante . Gráfico Coste Cálculo de Áreas No Bloqueante . . . . . . . . Modelo Ejecución Regla del Trapecio 8 Procesos . . . . . . . Gráfico Tiempo Ejecución Regla del Trapecio . . . . . . . . . Gráfico Coste Regla del Trapecio . . . . . . . . . . . . . . . . Comparación Tiempos de distintas Cantidades de Procesos . . Comparación Costes de distintas Cantidades de Procesos . . . Modelo Ejecución Algoritmo de Fox 9 Procesos . . . . . . . .

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

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

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

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

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

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

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

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

148 150 152 152 153 155 155 156 158 158 160 160 161

Índice de cuadros 1.1. Diámetros Topologías Hipercubo y Malla . . . . . . . . . . . . . . . . . . . 1.2. Ejemplos Computadores Vectoriales . . . . . . . . . . . . . . . . . . . . . .

28 42

5.1. Tipos de Datos MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

6.1. Operaciones de Reducción . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

7.1. Partición Matriz 6*6 en 9 Procesos . . . . . . . . . . . . . . . . . . . . . . . 106 7.2. Topología Física 3*3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.1. 9.2. 9.3. 9.4.

Evaluación Cálculo de Áreas Bloqueante . . . Evaluación Cálculo de Áreas No Bloqueante . Evaluación Regla del Trapecio . . . . . . . . Evaluación Multiplicación de Matrices de Fox

11

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

151 154 157 159

12

ÍNDICE DE CUADROS

Índice de algoritmos 4.1. 5.1. 5.2. 6.1. 7.1.

¡Hola Mundo! . . . . . . . . . . . . . . . . . . . . . . . Cálculo de Áreas mediante Montecarlo (Bloqueante) . . Cálculo de Áreas mediante Montecarlo (No Bloqueante) Regla del Trapecio . . . . . . . . . . . . . . . . . . . . Multiplicación de Matrices de Fox . . . . . . . . . . . .

13

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. 71 . 81 . 86 . 98 . 114

14

ÍNDICE DE ALGORITMOS

Objetivos El objetivo principal del presente proyecto de investigación consiste en demostrar la utilidad y potencialidad del procesamiento paralelo, concretamente en lo relativo a su aplicación en clusters (redes de computadores). Debemos probar con resultados reales y análisis gráficos la mejora en el rendimiento que produce la ejecución paralela de determinados algoritmos.

Figura 1: Objetivo Procesamiento Paralelo en Clusters

Con el objeto de delimitar el campo de estudio lo primero que debemos hacer es situar el paralelismo basado en redes dentro de la amplia variedad de sistemas dedicados al procesamiento paralelo. Propondremos una clasificación para los distintos tipos de paralelismo existentes en la actualidad, y explicaremos las características principales de cada uno de ellos. Un aspecto básico para el desarrollo de la investigación consiste en diseñar e implemetar un conjunto de algoritmos paralelos que pongan en práctica los tipos de comunicación más importantes que se dan en el procesamiento paralelo basado en redes. Para lograr este objetivo estudiaremos las caracteríticas más importantes de MPI (“Message Passing Interface”, Interfaz de Paso de Mensajes) y emplearemos dicha interfaz en el desarrollo de diversos algoritmos paralelos. Por último haremos un estudio detallado de los resultados obtenidos en las ejecuciones de los algoritmos desarrollados, explicando paso a paso la manera en la que han sido realizados. I

II

OBJETIVOS

Dichos resultados serán utilizados para la generación de gráficos que nos ayuden a entender las importantes ventajas que nos aporta el procesamiento paralelo.

Desarrollo A continuación explicaremos detenidamente el desarrollo de la investigación llevada a cabo para la realización del presente proyecto. Dicho desarrollo coincide en la práctica con la estructura del documento realizado.

Sistemas de Procesamiento Paralelo En primer lugar debemos llevar a cabo una visión general del procesamiento paralelo, para así poder valorar la importancia de este amplio campo de estudio. En el capítulo 1 se estudian los conceptos básicos relacionados con este modelo de procesamiento, y proponemos una clasificación para los distintos tipos de paralelismo existentes en la actualidad, explicando las características principales de cada uno de ellos. Nuestra clasificación divide el paralelismo de los computadores en dos grandes ramas: Paralelismo implícito o de bajo nivel Paralelismo explícito o de alto nivel La técnicas de paralelismo implícito están dirigidas al reforzamiento del nivel de concurrencia dentro de la CPU, de manera que queda oculta a la arquitectura del ordenador. Por lo tanto pueden ser vistos como sistemas de un sólo procesador.

Paralelismo Implícito

Segmentación

Múltiples ALUs

Procesadores Auxiliares

Figura 1: Clasificación Paralelismo Implícito

El paralelismo explícito o de alto nivel hace referencia a aquellos sistemas en los cuales se interconectan varios procesadores para cooperar en la ejecución de los programas de aplicación. Se trata de sistemas que ofrecen una infraestructura explícita para el desarrollo del software del sistema y aplicaciones que exploten el paralelismo. A este tipo de paralelismo dedicaremos el resto de la investigación, centrándonos concretamente en las arquitecturas MIMD con memoria distribuida. III

DESARROLLO

IV

Paralelismo Explícito

MISD

SIMD

(Procesadores Vectoriales)

(Procesadores Matriciales)

Memoria Compartida Multiprocesadores (SMP)

MIMD

Memoria Distribuida Multicomputadores (Cluster)

Figura 2: Clasificación Paralelismo Explícito

Una vez resuelto el sistema de intercomunicación física de los equipos, deben abordarse los mecanismos para lograr la coordinación entre los procesadores. En el capítulo 2 analizamos las características básicas de los dos modelos de interacción entre procesadores (paso de mensajes y memoria compartida), para luego centrarnos en las utilidades de desarrollo de software paralelo más populares que existen en la actualidad: PVM, MPI, p4, Express y Lynda.

Guía MPI La segunda parte de nuestro estudio se centra en la utilización de la interfaz MPI (“Message Passing Interface”, Interfaz de Paso de Mensajes) para el desarrollo de aplicaciones paralelas. El estudio de la interfaz MPI comienza en el capítulo 3 con una explicación sobre el origen y la motivación que promovieron la creación del estándar. Por otro lado analizamos los contenidos del estándar, sus objetivos, su funcionamiento básico y sus distintas versiones. Como vemos en la figura 3, MPI es implementado normalmente como interfaz de comunicaciones, utilizando las facilidades ofrecidas por el sistema que vayamos a usar (comunicación vía sockets, operaciones de memoria compartida, etc). MPI_Send()

MPI_Recv()

MPI

MPI

SO

SO

Figura 3: Esquema Funcionamiento MPI

A continuación en el capítulo 4 vemos los conceptos básicos sobre la utilización de MPI para el desarrollo de programas escritos en C. Todos los programas MPI comparten una serie de características. La inicialización y finalización del entorno de ejecución se llevan a cabo mediante funciones que explicaremos en este capítulo. También analizamos los métodos para

V

identificar los procesos en ejecución. Para ejemplificarlo escribiremos un sencillo programa en C que hace uso de funciones MPI para ejecutar una versión paralela del conocido algoritmo ¡Hola Mundo!. El capítulo 5 aborda la función más importante y característica del estándar MPI: el paso de mensajes. Se utiliza básicamente para el intercambio de datos entre los procesos en ejecución. En este capítulo estudiamos las características más importantes de los mensajes bloqueantes y no bloqueantes, aplicando dicha teoría a la implementación de un algoritmo diseñado para el cálculo de áreas circulares. El algoritmo Cálculo de Áreas mediante Montecarlo realiza una aproximación del área de una circunferencia con un radio determinado mediante la simulación de variables aleatorias, empleando un método estadístico (figura 4).

Figura 4: Algoritmo Cálculo de Áreas mediante Montecarlo

Las operaciones de comunicación colectiva son aquellas que se aplican al mismo tiempo a todos los procesos pertenecientes a un comunicador. Tienen una gran importancia en el estándar MPI, debido a la claridad de su sintaxis y a su eficiencia. En el capítulo 6 analizamos su utilidad y conveniencia implementando el algoritmo Regla del Trapecio de manera que haga un uso inteligente de dichas operaciones. El capítulo 7 aborda el uso de comunicadores y topologías. Esta característica hace a MPI diferente de la mayoría de los demás sistemas de paso de mensajes. En pocas palabras, un comunicador es una colección de procesos que pueden mandarse mensajes entre ellos. Una topología es una estructura impuesta en los procesos de un comunicador que permite a los procesos ser direccionados de diferentes maneras. Para ilustrar estas ideas desarrollaremos el código que implementa el algoritmo de Fox para multiplicar dos matrices cuadradas mediante su subdivisión en una serie de procesos (cuadro 1).

Análisis del Rendimiento Todo el trabajo anteriormente realizado no tendría ningún sentido si no viniera avalado por unos resultados satisfactorios en la ejecución de algoritmos paralelos. Para conseguir una cierta objetividad en el análisis de los algoritmos ejecutados en un

DESARROLLO

VI



 


Proceso   0

 

    

Proceso   3

 

     

Proceso   6

 

   


 
  
 

Proceso   1

     

Proceso   4

       

Proceso   7

      



 


Proceso  2

      

Proceso  5

      

Proceso   8

       

Cuadro 1: Subdivisión de Matrices Algoritmo de Fox

determinado sistema paralelo, lo primero que debemos hacer es medir el rendimiento de dicho sistema. Dicha medición se realiza a través de herramientas especializadas en el análisis, de modo que podemos saber fácilmente y con seguridad cuánto de apropiado es el sistema para la ejecución de determinados algoritmos paralelos. En las figuras 6 y 7 mostramos el rendimiento del sistema en la ejecución de paso de mensajes bloqueantes y operaciones de comunicación colectiva, respectivamente. Comunicacion Bloqueante 1200 Com.Bloqueante

1000

Tiempo (micro-seg)

800

600

400

200

0 0

200

400

600

800

Tamano (bytes)

Figura 6: Gráfico Comunicación Bloqueante

1000

1200

VII

Comunicacion Colectiva Op.Reduccion-Entero 160000 32 256 512 1024

140000

Tiempo (micro-seg)

120000

100000

80000

60000

40000

20000

0 0

2

4

6

8

10

12

14

16

Num.Procesos

Figura 7: Gráfico Comunicación Colectiva

El capítulo 9 aborda el estudio de los resultados obtenidos en las ejecuciones explicando paso a paso la manera en la que han sido cosechados. Dichos resultados los analizaremos más detenidamente en el apartado de conclusiones, ya que nos ayudan a demostrar el éxito del presente proyecto de investigación.

VIII

DESARROLLO

Parte I

Sistemas de Procesamiento Paralelo

1

Capítulo 1

Introducción Definimos como procesamiento paralelo al concepto de agilizar la ejecución de un programa mediante su división en fragmentos que pueden ser ejecutados simultáneamente, cada uno en un procesador. De este modo un programa que se ejecute en  procesadores podría ejecutarse  veces más rápido que usando un solo procesador, al menos en teoría...

1.1. Utilidades del Procesamiento Paralelo Aunque el uso de múltiples procesadores puede agilizar muchas operaciones, la mayoría de las aplicaciones no están diseñadas para aprovechar los beneficios del procesamiento paralelo. Básicamente el procesamiento paralelo es apropiado para: Aplicaciones con suficiente paralelismo como para hacer bueno el uso de múltiples procesadores. El problema radica en identificar las porciones de programa que puedan ser ejecutadas independiente y simultáneamente en procesadores separados; ésto en realidad es complejo, ya que encontraremos aplicaciones que podrían ser ejecutadas en paralelo y sin embargo se ralentizan al ser paralelizadas en un sistema particular. Por ejemplo, un programa que tarda 4 segundos en ser ejecutado en una sola máquina podría tardar 1 segundo de procesamiento en cada uno de los cuatro procesadores disponibles en una red, pero no lograríamos nada si la coordinación entre dichos procesadores tardase más de 3 segundos. Implementaciones de algoritmos que o bien ya son paralelos (escritos para obtener las ventajas del procesamiento paralelo) o bien esperamos paralelizar nosotros mismos, codificando de nuevo al menos alguna de sus partes. Si nos encontramos en alguno de estos casos veremos que el procesamiento paralelo puede proporcionarnos el rendimiento de un supercomputador, aplicado a algunos programas que realizan complejas operaciones u operan en grandes bloques de datos. Y lo que es más, ello se puede lograr con hardware relativamente barato. Además es posible utilizar dichos sistemas paralelos para la realización de otros trabajos cuando no estén ocupados con una tarea en paralelo. 3

4

CAPÍTULO 1. INTRODUCCIÓN

Si no es el procesamiento paralelo lo que se busca, pero queremos mejorar el rendimiento de nuestra aplicación, se pueden hacer multitud de cosas. En aplicaciones secuenciales podemos usar un procesador más rápido, añadir memoria al sistema, etc.

1.2. Definiciones Básicas Aunque el procesamiento paralelo haya sido utilizado durante muchos años en una gran variedad de sistemas, todavía no es familiar para la mayoría de los usuarios. Antes de comenzar la discusión de las varias alternativas existentes para implementar el procesamiento paralelo, es importante precisar el significado de algunos conceptos fundamentales.

1.2.1. Características Físicas de la Comunicación Velocidad de Transferencia de Datos En el campo de las redes de comunicación el intercambio de información entre ordenadores se realiza generalmente mediante transmisiones analógicas. En una transmisión analógica el ancho de banda se define como la diferencia máxima entre la frecuencia más alta y más baja de la señal sobre la que se transporta la información. Existe una relación directa entre el ancho de banda y la velocidad de transmisión: cuanto mayor es el ancho de banda de un sistema de transmisión, mayor es la velocidad a la que se pueden transmitir los datos en el medio. Podemos definir la velocidad de modulación de una señal analógica como el número de veces por segundo que la señal cambia su valor en la línea o medio de transmisión. Esta velocidad se mide en baudios. El número de baudios determina la cantidad de cambios de estado por segundo que se producen en una transmisión. Cuantos más estados, más cantidad de bits por segundo se podrán transmitir. Definimos la velocidad de transmisión como el número de bits transmitidos por segundo. Su unidad es el bps (bits por segundo). En general si el número de estados posibles de la línea  de comunicación es  , a cada estado le corresponderán  "!  bits de información. Imaginemos que en una red telefónica que funciona a 2400 baudios podemos transmitir 4 bits en cada baudio. En ese caso la velocidad de transmisión sería de 2400 baudios x 4 (bits/baudio) = 9600 bits por segundo. En la transmisión de información digital entre computadores es fundamental que aseguremos intercambios de datos libres de errores. El coste de ésto estriba en que a la propia información a transmitir se le deben añadir otras informaciones adicionales para detección/corrección de errores, para establecer y controlar la comunicación, etc. Aparece aquí un nuevo concepto de velocidad que llamaremos velocidad de transferencia de datos, y que representa la cantidad de información útil que puede transmitirse por unidad de tiempo. Latencia En un sistema de comunicación llamamos latencia al mínimo tiempo empleado en transmitir un dato, incluyendo la información de control necesaria para enviarlo o recibirlo. La latencia es muy importante en procesamiento paralelo porque determina el tamaño granular, es decir,

1.2. DEFINICIONES BÁSICAS

5

lo mínimo que debe tardar la ejecución de un segmento de código para que su ejecución en paralelo sea rentable, hablando en términos de rendimiento computacional. Básicamente si un segmento de código se ejecuta en menos tiempo del que se emplea en transmitir su resultado (latencia), entonces será más rápido ejecutar dicho segmento de código de manera secuencial en el procesador que necesita dicho resultado; de este modo la ejecución secuencial evitaría la sobrecarga en la comunicación.

1.2.2. Estándares Relacionados IA32 El modelo IA32 (“Intel Architecture, 32-bit”) es una especificación para microprocesadores que define su arquitectura y funcionalidad, o lo que es lo mismo, su comportamiento desde el punto de vista del software. Dicha especificación define entre otros elementos las siguientes características de los microprocesadores: Los modos de operación La organización de la memoria La estructura de los registros El direccionamiento de los operandos Los tipos de datos El conjunto de instrucciones Interrupciones y excepciones Todos los microprocesadores Intel x86 (a partir del 80386) siguen el modelo IA32, incluidos los más recientes: Pentium, P6, Pentium 4, Pentium M y Xeon. AMD y Cyrix también desarrollan multitud de procesadores compatibles con la arquitectura IA32. Dado que Linux se desarrolló en principio en procesadores IA32, y dado que ésta fue la manera en que se centró en el mercado, es conveniente usar dicha denominación IA32 para distinguir este tipo de procesadores de los PowerPC, Alpha, PA-RISC, MIPS, SPARC, etc. RAID Como en otras áreas de rendimiento en los computadores, los diseñadores de memorias de disco reconocen que si uno de los componentes sólo puede alcanzar un determinado límite, se puede conseguir una ganancia en prestaciones adicional usando varios de esos componentes en paralelo. En el caso de las memorias de disco, esto conduce al desarrollo de conjuntos de discos que operen independientemente y en paralelo. Siguiendo este principio, el esquema RAID (“Redundant Array of Independent Disks”, Conjunto Redundante de Discos Independientes) es una tecnología sencilla para mejorar tanto el ancho de banda como la fiabilidad de la E/S a disco. Consta de 6 niveles independientes, desde 0 hasta 5. Estos niveles no implican una relación jerárquica, pero designan diseños de arquitecturas diferentes que poseen tres características comunes:

CAPÍTULO 1. INTRODUCCIÓN

6

Paralelismo Implícito

Segmentación

Múltiples ALUs

Procesadores Auxiliares

Figura 1.1: Clasificación Paralelismo Implícito 1.

RAID es un conjunto de unidades físicas de disco vistas por el sistema operativo como una única unidad lógica.

2.

Los datos se distribuyen a través de las unidades físicas de un conjunto.

3.

La capacidad de los discos redundantes se usa para almacenar información de paridad, que garantice la recuperación de los datos en caso de fallo de disco.

Los detalles de la característica segunda y tercera cambian según los distintos niveles de RAID. RAID 0 no soporta la tercera característica. Linux soporta los estándares RAID 0, 1, 4 y 5 además de hardware RAID especializado.

1.3. Clasificación Sistemas Paralelos En general, se puede dividir el paralelismo de los computadores en dos grandes ramas: Paralelismo implícito o de bajo nivel Paralelismo explícito o de alto nivel

1.3.1. Paralelismo Implícito o de Bajo Nivel La técnicas de paralelismo implícito están dirigidas al reforzamiento del nivel de concurrencia dentro de la CPU, de manera que queda oculta a la arquitectura del ordenador. Por lo tanto pueden ser vistos como sistemas de un sólo procesador. Como ejemplos de paralelismo de bajo nivel están: Segmentación o pipeline: La ejecución de cada instrucción se divide en una secuencia de etapas, de forma que varias instrucciones pueden ejecutarse en paralelo, cada una en una etapa distinta de su ejecución. Múltiples Unidades Funcionales en el Procesador: La repetición de ALUs permite una aproximación superescalar, con la ejecución paralela de varias instrucciones, todas en la misma etapa de su ejecución. Un procesador superescalar es aquel en el que las instrucciones comunes (aritmética entera y en punto flotante, cargas, almacenamientos y bifurcaciones condicionales) pueden iniciar su ejecución simultáneamente y ejecutarse de manera independiente. Estas implementaciones plantean problemas complejos de

1.3. CLASIFICACIÓN SISTEMAS PARALELOS

7

Paralelismo Explícito

MISD

SIMD

(Procesadores Vectoriales)

(Procesadores Matriciales)

Memoria Compartida Multiprocesadores (SMP)

MIMD

Memoria Distribuida Multicomputadores (Cluster)

Figura 1.2: Clasificación Paralelismo Explícito diseño relacionados con el cauce de instrucciones. En esta línea, la tecnología SWAR consiste en agilizar las operaciones en registros de enteros mediante la división de dichos registros en una serie de campos de igual longitud, asignando una ALU a cada uno de los campos y realizando la ejecución paralelamente. En este caso se ejecuta la misma instrucción sobre distintos datos en paralelo. Procesadores Auxiliares (“Attached Processors”): Los procesadores auxiliares son esencialmente computadores de propósito específico que se conectan a un sistema host o servidor para acelerar determinados tipos de cómputo. El ejemplo más común es el uso de procesadores de E/S, que liberan a la CPU de la responsabilidad del control detallado de las operaciones de E/S.

1.3.2. Paralelismo Explícito o de Alto Nivel El paralelismo explícito o de alto nivel hace referencia a aquellos sistemas en los cuales se interconectan varios procesadores para cooperar en la ejecución de los programas de aplicación. Se trata de sistemas que ofrecen una infraestructura explícita para el desarrollo del software del sistema y aplicaciones que exploten el paralelismo. La forma más común de clasificar los sistemas de procesadores paralelos fue la introducida por Flynn, la cual establece las siguientes categorías de computadores: SISD (“Single Instruction Single Data”, Flujo de instrucciones único y flujo de datos único): Un procesador interpreta una secuencia de instrucciones para operar con los datos almacenados en una memoria. De este modo en cualquier momento sólo se está ejecutando una única instrucción. Esta categoría responde a la arquitectura de Von Neumann, también llamados computadores serie escalares. SIMD (“Single Instruction Multiple Data”, Flujo de instrucciones único y flujo de datos múltiple): Una única instrucción es aplicada sobre diferentes datos al mismo tiempo. En las máquinas de este tipo un cierto número de elementos procesadores son controlados y sincronizados mediante una unidad de control. Cada elemento procesador tiene una memoria asociada, de manera que cada instrucción es ejecutada simultáneamente por

8

CAPÍTULO 1. INTRODUCCIÓN todos los elementos procesadores pero sobre un conjunto de datos diferentes. Debido a su utilidad en el procesamiento de matrices, a este tipo de máquinas se les llama procesadores matriciales.

MISD (“Multiple Instruction Single Data”, Flujo de instrucciones múltiple y flujo de datos único): Varias instrucciones actúan simultáneamente sobre un único trozo de datos. Este tipo de máquinas se pueden interpretar de dos maneras. En principio, podemos considerarlas como máquinas formadas por varias unidades de procesamiento, las cuales reciben instrucciones distintas que operan sobre los mismos datos. Esta clase de arquitectura ha sido clasificada por numerosos arquitectos de computadores como impracticable o imposible, y en estos momentos no existen ejemplos que funcionen siguiendo este modelo. Otra forma de interpretar el modelo MISD es considerarlo como una clase de máquinas donde un mismo flujo de datos fluye a través de numerosas unidades de procesamiento. Arquitecturas altamente segmentadas, como la que poseen los arrays sistólicos o los procesadores vectoriales, son clasificadas a menudo bajo esta categoría. Estas arquitecturas realizan el procesamiento vectorial a través de una serie de etapas, cada una ejecutando una función particular produciendo un resultado intermedio. La razón por la cual dichas arquitecturas son clasificadas como MISD es que los elementos de un vector pueden ser considerados como pertenecientes al mismo dato, y todas las etapas del cauce representan múltiples instrucciones que son aplicadas sobre ese vector.

MIMD (“Multiple Instruction Multiple Data”, Flujo de instrucciones múltiple y flujo de datos múltiple): Un conjunto de unidades de procesamiento ejecuta simultáneamente diferentes secuencias de instrucciones sobre conjuntos de datos diferentes. Es la organización que poseen los sistemas multiprocesadores y multicomputadores en general. SPMD es una versión restringida de MIMD en la cual todos los procesadores ejecutan el mismo programa. Al contrario que SIMD, cada procesador ejecuta una secuencia de instrucciones diferente.

En la organización MIMD, los procesadores son de uso general, puesto que deben ser capaces de procesar todas las instrucciones necesarias para realizar las transformaciones apropiadas de los datos. Las arquitecturas MIMD se pueden subdividir además según la forma que tienen los procesadores para comunicarse (figura 1.2). Si los procesadores comparten una memoria común, entonces cada procesador accede a los programas y datos almacenados en la memoria compartida, y los procesadores se comunican unos con otros a través de esa memoria. Este tipo de sistemas se conocen como multiprocesadores fuertemente acoplados o simplemente multiprocesadores. Si cada procesador tiene una memoria dedicada, entonces cada elemento de proceso es en sí mismo un computador. La comunicación entre los computadores se realiza a través de caminos fijos o mediante algún mecanismo de conmutación de mensajes. Este tipo de sistemas se conocen como multiprocesadores débilmente acoplados o multicomputadores.

1.4. ARQUITECTURAS BASADAS EN PARALELISMO IMPLÍCITO Istrucción

Captación

Istrucción

Ejecución

9 Resultado

Figura 1.3: Ciclo de Instrucción de 2 etapas (A)

1.4. Arquitecturas Basadas en Paralelismo Implícito 1.4.1. Segmentación o pipeline Desde 1960 esta arquitectura ha recibido una gran atención debido a la considerable mejora que ha producido en la velocidad de proceso sin que ello aumente, en la misma medida, el coste del sistema. La segmentación de instrucciones es similar al uso de una cadena de montaje en una fábrica. Una cadena de montaje saca partido al hecho de que el producto pasa a través de varias etapas de producción. De esta manera se puede trabajar sobre los productos en varias etapas simultáneamente. A este proceso se le llama segmentación (“pipelining”) porque, como en una tubería o cauce (“pipeline”), en un extremo se aceptan nuevas entradas antes de que algunas entradas aceptadas anteriormente aparezcan como salidas en el otro extremo. Para aplicar este concepto a la ejecución de instrucciones debemos darnos cuenta de que en realidad una instrucción tiene varias etapas. La figura 1.4 muestra, por ejemplo, una partición del ciclo de instrucción en 10 etapas que tienen lugar secuencialmente. Claramente puede pensarse en la utilización de la segmentación. Como una aproximación sencilla consideremos la subdivisión del procesamiento de una instrucción en dos etapas: captación de instrucción y ejecución de instrucción. Hay períodos en la ejecución de una instrucción en los que no se accede a memoria principal. Este tiempo podría utilizarse para captar la siguiente instrucción en paralelo con la ejecución de la actual. La figura 1.3 representa esta aproximación. El cauce tiene dos etapas independientes. La primera etapa capta una instrucción y la almacena en un buffer. Cuando la segunda etapa está libre la primera le pasa la instrucción almacenada. Mientras que la segunda etapa ejecuta la instrucción, la primera etapa utiliza algún ciclo de memoria no usado para captar y almacenar la siguiente instrucción. A ésto se le llama prebúsqueda o precaptación de la instrucción (“instruction prefetch”) o solapamiento de la captación (“fetch overlap”). Debería estar claro que ese proceso acelerará la ejecución de instrucciones.

10

Captación de instrucción

Solicitud de instrucción

Cálculo de la dirección de la instrucción

Indirección

Indirección

Captación del operando

Almacenamiento del operando

Solicitud de operando

Decodificación de la operación de la instrucción

Cálculo de la dirección del operando

Más de un resultado

Operación con los datos

Cálculo de la dirección del operando

Cadena o vector

Figura 1.4: Ciclo de Instrucción de 10 etapas

Chequeo de interrupciones

No interrupción

Interrupción

CAPÍTULO 1. INTRODUCCIÓN

Siguiente instrucción

Más de un operando

1.4. ARQUITECTURAS BASADAS EN PARALELISMO IMPLÍCITO Esperar

Istrucción

Nueva dirección

Captación

Istrucción

11

Esperar

Ejecución

Resultado

Descartar

Figura 1.5: Ciclo de Instrucción de 2 etapas (B) Si las etapas de captación y ejecución fueran de igual duración, el tiempo de ciclo de instrucción se reduciría a la mitad. Sin embargo si miramos más atentamente el cauce de la figura 1.5 veremos que la duplicación de la velocidad de ejecución es poco probable por dos razones: 1.

El tiempo de ejecución será generalmente más largo que el tiempo de captación. La ejecución implicará la lectura y almacenamiento de los operandos y la realización de alguna operación. De este modo la etapa de captación puede tener que esperar algún tiempo antes de que pueda vaciar su buffer.

2.

Una instrucción de bifurcación condicional hace que la dirección de la siguiente instrucción a captar sea desconocida. De este modo, la etapa de captación debe esperar hasta que reciba la dirección de la siguiente instrucción desde la etapa de ejecución. La etapa de ejecución puede entonces tener que esperar mientras se capta la siguiente instrucción.

La pérdida de tiempo debida a la segunda razón puede reducirse haciendo una estimación. Una regla simple es la siguiente: cuando una instrucción de bifurcación condicional pasa de la etapa de captación a la de ejecución, la etapa de captación capta la instrucción de memoria que sigue a la instrucción de salto. Entonces si el salto no se produce no se pierde tiempo. Si el salto se produce debe desecharse la instrucción captada y captar una nueva instrucción. Aunque estos factores reduzcan la efectividad potencial del cauce de dos etapas, se produce alguna aceleración. Para conseguir una mayor aceleración, el cauce debe tener más etapas. Consideremos la siguiente descomposición del procesamiento de una instrucción: Captar Instrucción (“Fetch Instruction”, FI): Leer la supuesta siguiente instrucción en un buffer. Decodificar Instrucción (“Decode Instruction”, DI): Determinar el código de operación y los campos del operando. Calcular Operandos (“Calculate Operands”, CO): Calcular la dirección efectiva de cada operando fuente. Esto puede involucrar varios modos de direccionamiento: mediante desplazamiento, indirecto a través de registro, indirecto u otros. Captar Operandos (“Fetch Operands”, FO): Captar cada operando de memoria. Los operandos en registros no tienen que ser captados.

CAPÍTULO 1. INTRODUCCIÓN

12

Instrucción 1 Instrucción 2 Instrucción 3 Instrucción 4 Instrucción 5 Instrucción 6 Instrucción 7 Instrucción 8 Instrucción 9

1

2

3

4

5

6

7

8

9

10

11

12

13

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

EO WO

FI

DI

CO

FO

14

EO WO

EO WO

Figura 1.6: Cauce de 6 etapas Ejecutar Instrucción (“Execute Instruction”, EI): Realizar la operación indicada y almacenar el resultado, si lo hay, en la posición de operando destino especificada. Escribir Operando (“Write Operand”, WO): Almacenar el resultado en memoria. Con esta descomposición las diversas etapas tienen casi igual duración. Por motivos de claridad asumamos que tienen igual duración. La figura 1.6 muestra cómo un cauce de 6 etapas puede reducir el tiempo de ejecución de 9 instrucciones de 54 a 14 unidades de tiempo. En realidad dicha simulación es demasiado idealista. Para empezar no todas las instrucciones recorren las 6 etapas del cauce; por ejemplo, una instrucción de carga no necesita la etapa WO. Ello complica el hardware del cauce. Además la mayoría de los sistemas no permiten varios accesos a memoria simultáneos, por lo que las etapas FI, FO y WO no podrían ejecutarse al mismo tiempo. Otros factores como la dificultad en la ejecución de la bifurcación condicional ya comentada, o la espera que se produce en ciertas etapas cuando no todas las etapas son de igual duración (lo cual es lo más común), complican el diseño y limitan la mejora de las prestaciones. Según toda esta discusión precedente, puede parecer que cuanto mayor sea el número de etapas en el cauce, más rápida será la velocidad de ejecución. Algunos diseñadores del IBM S/360 observaron dos factores que frustran este aparente sencillo patrón de diseño de altas prestaciones, y que siguen siendo ciertos hoy día: 1.

En cada etapa, hay algún gasto extra debido a la transferencia de datos de buffer a buffer y a la realización de varias funciones de preparación y distribución.

1.4. ARQUITECTURAS BASADAS EN PARALELISMO IMPLÍCITO 2.

13

La cantidad de control lógico necesario para manejar dependencias de memoria y registros y para optimizar el uso del cauce aumenta enormemente con el número de etapas.

En definitiva, la segmentación de instrucciones es una poderosa técnica para aumentar las prestaciones pero requiere un diseño cuidadoso si se quieren obtener resultados óptimos con una complejidad razonable. La emergencia de la segmentación y su temprana evolución se produjo en la primera línea de supercomputadores IBM. El modelo IBM 7030 (llamado computador “a toda mecha”) superó en 100 veces la velocidad del computador más rápido en producción de aquella época, el IBM 704. Dicho logro sólo se pudo alcanzar mediante la segmentación de instrucciones. Luego vinieron otros éxitos como el IBM 360/91, el procesador 6502, y un largo etc. Hoy día todas las compañías implementan es sus procesadores este tipo de arquitectura.

1.4.2. Tecnología SWAR SWAR (“SIMD Within A Register”, Paralelismo SIMD Dentro de un Registro) es el término genérico aplicado a un tipo de paralelismo interno al procesador. La idea consiste en agilizar las operaciones en registros de enteros mediante la división de dichos registros en una serie de campos de igual longitud, asignando una unidad de procesamiento (una ALU en definitiva) a cada uno de los campos y realizando la ejecución paralelamente. Dada una máquina con registros de # bits y  ALUs, se puede lograr que sus operaciones sobre registros funcionen como operaciones paralelas SIMD en  campos de #%$& bits. De todas formas sólo con el empuje de las tecnologías multimedia, que han conseguido acelerar las operaciones en un rango de 2x hasta 8x, se ha llegado a la popularidad e importancia de dicha tecnología. Ya en 1997 la mayoría de los microprocesadores incorporaban soporte de hardware para SWAR: Intel Pentium II & Pentium with MMX (“MultiMedia eXtensions”, Extensiones Multimedia) AMD K6 MMX (“MultiMedia eXtensions”, Extensiones Multimedia) Cyrix M2 MMX (“MultiMedia eXtensions”, Extensiones Multimedia) Digital Alpha MAX (“MultimediA eXtensions”, Extensiones Multimedia) HewlettPackard PARISC MAX (“Multimedia Acceleration eXtensions”, Extensiones de Aceleración Multimedia) Microunity Mediaprocessor SIGD (“Single Instruction on Groups of Data”, Instrucciones Únicas en Grupos de Datos) MDMX, pronunciado Mad Max (“MIPS Digital Media eXtension”, Extensiones Media Digital MIPS) Sun SPARC V9 VIS (“Visual Instruction Set”, Juego de Instrucciones Visuales)

CAPÍTULO 1. INTRODUCCIÓN

14

A diferencia de lo que sucede con las tres firmas que aceptaron las primitivas MMX (Intel/AMD/Cyrix), todos los los demás conjuntos de instrucciones son difícilmente comparables, y mutuamente incompatibles. Con el paso del tiempo las MMX también evolucionaron, generandose nuevas extensiones como las EMMX de Cyrix, las 3DNow! de AMD o las SSE y SSE2 de Intel, entre otras. 1.4.2.1.

Utilidades de SWAR

Aunque todos los procesadores actuales son capaces de ejecutar al menos algún tipo de paralelismo basado en la tecnología SWAR, la realidad es que ni siquiera los juegos de instrucciones SWAR más desarrollados soportan paralelismo de carácter general. De hecho, muchos piensan que la diferencia de rendimiento entre un procesador Pentium y un Pentium MMX se debe más a factores como el mayor tamaño de la caché que a la aparición de las MMX. Así pues... ¿para qué es realmente buena la tecnología SWAR? Operaciones sobre datos de tipo entero, cuanto más pequeños mejor. Dos valores de 32 bits caben en un registro MMX de 64 bits, pero también lo hacen ocho caracteres de un byte o incluso un tablero de ajedrez con valores de un bit. Cuando un dato ocupa varios campos de un registro, determinadas operaciones (llamadas operaciones particionadas) se ven afectadas por interacciones entre los campos debido al acarreo/resto, etc. Por ello, cuanto menor sea el tamaño de dichos enteros, más limpias serán las operaciones y por lo tanto mejor aprovecharemos el parelismo generado por la repetición de ALUs. Nota: En los juegos de instrucciones más actuales, como lal EMMX, las 3DNow! o las SSE2, también se admiten operaciones sobre datos de tipo flotante. Paralelismo SIMD o de vectores, en el cual la misma operación es aplicada a todos los campos simultáneamente. Hay maneras de anular la operación en algunos campos seleccionados (enmascaramiento), pero ello complica el código y disminuye el rendimiento. Referencias a memoria localizadas y regulares. SWAR en general y MMX en particular no obtienen buenos resultados utilizando accesos aleatorios. Reunir con dichos accesos un vector x[y] (donde y es un índice de dicho vector) resulta demasiado costoso. Es cierto que todas éstas son restricciones muy duras, pero también es cierto que dicho tipo de paralelismo se da en muchos algoritmos paralelos (no sólo en aplicaciones multimedia). Enfocada al tipo de paralelismo adecuado, la tecnología SWAR puede ser más eficiente que utilizar SMPs o Clusters... y no cuesta nada utilizarla. 1.4.2.2.

Soporte MMX Bajo Linux

Bajo Linux los procesadores IA32 son nuestro principal interés. Lo bueno es que tanto los AMD, como los Cyrix y los Intel tienen una base común, las instrucciones MMX. Sin embargo el rendimiento de dichas instrucciones varía, y además, actualmente cada firma tiene sus propias extensiones; por lo tanto programar un soporte para dichas instrucciones puede resultar algo engorroso. Existen tres métodos para utilizar MMX en SWAR:

1.4. ARQUITECTURAS BASADAS EN PARALELISMO IMPLÍCITO

15

1.

Utilizar una librería de funciones MMX ya desarrollada. En la Universidad de Purdue existe un grupo de trabajo (URL [15]) que ha desarrollado librerías adaptadas a varios juegos de instrucciones determinados. Así, tenemos la librería libmmx diseñada para las instrucciones MMX en general, la librería libxmmx para las Cyrix EMMX y la librería libsse para las Intel SSE. También existe una librería un tanto curiosa, MMX Emulator (URL [7]), diseñada para ejecutar programas que usen instrucciones MMX en procesadores que no tengan soporte para ellas. Así, afirman tener un 386 MMX... como sus realizadores apuntan, es lento pero funciona.

2.

Usar las instrucciones MMX directamente. Esto es algo complicado por dos razones. El primer problema es la portabilidad: no podremos ejecutar un programa así implementado en procesadores que no tengan soporte para MMX. El segundo problema es que el ensamblador para IA32 que utilicemos en Linux podría no soportar dichas instrucciones MMX.

3.

Utilizar un lenguage de alto nivel o un compilador que genere directamente las instrucciones MMX apropiadas. En este sentido, en la Universidad de Purdue (URL [15]) se ha desarrollado un lenguaje llamado SWARC y su compilador, el Scc, el cual está en permanente fase experimental, aunque disponible. Como sus autores señalan, Scc no pretende ser un producto de alta calidad en términos de eficiencia; en cambio proporciona una implementación básica del modelo SWAR. Por otro lado tenemos los compiladores de Intel (URL [4]) de C++ y Fortran para Linux, los cuales generan las instrucciones MMX deseadas de manera optimizada.

1.4.3. Procesadores Auxiliares Los procesadores auxiliares son esencialmente computadores de propósito específico que se conectan a un sistema host o servidor para acelerar determinados tipos de cómputo. Por ejemplo, muchas tarjetas de vídeo y audio para PCs contienen procesadores auxiliares diseñados, respectivamente, para acelerar operaciones sobre gráficos y audio. Aunque esta técnica ya no está en auge, es muy difícil que otros métodos de procesamiento paralelo alcancen su bajo coste y alto rendimiento. Una buena manera de sacarle partido a estos procesadores es utilizar un PC bajo Linux como servidor. El problema es que no existe mucho software de soporte disponible, por lo que en ocasiones tendremos que trabajar por nuestra cuenta desarrollándolo nosotros mismos. 1.4.3.1.

Beneficios de los PCs bajo Linux como Servidor

Antes de que nos desanime el hecho de trabajar por nuestra cuenta, es útil entender que, aunque pueda ser dificultoso hacer que un PC bajo Linux actúe como servidor de un determinado sistema, es una de las pocas plataformas adecuadas para este tipo de uso. Los PCs son buenos servidores por dos razones principalmente. La primera es su capacidad de ampliación, de manera fácil y barata. Recursos como la memoria, discos, redes, etc. son añadidos a un PC de manera trivial. La segunda es su facilidad de interconexión a otros dispositivos a través de sus interfaces estándar. No sólo están ampliamente disponibles los prototipos de los buses ISA y PCI si no que además disponemos del puerto paralelo, el cual

CAPÍTULO 1. INTRODUCCIÓN

16

Figura 1.7: Procesamiento Digital de Señales ofrece un rendimiento razonable en un iterfaz independiente. Además la separación del espacio de E/S en los microprocesadores IA32 facilita la interconexión, proporcionando una protección hardware de las direcciones de E/S. Por otra parte Linux es un buen sistema operativo para crear un servidor. La disponibilidad de todo el código fuente y la extensa documentación existente son una ayuda tremenda, obviamente. Además Linux proporciona una planificación cercana al tiempo real, e incluso existe una versión de Linux en tiempo real desarrollada por FSMLabs (URL [3]). Pero lo que quizás es más importante es el hecho de que a la vez que proporciona un entorno UNIX completo, Linux soporta herramientas de desarrollo que están diseñadas para ser ejecutadas bajo Microsoft DOS o Windows. Los programas MSDOS pueden ser ejecutados en Linux usando dosemu, el cual proporciona una máquina virtual protegida que ejecuta MSDOS. El soporte de Linux para los programas diseñados para Windows 3.xx es aún más directo: software libre como wine. Este software (URL [21]) simula Windows 3.xx y Win32 lo suficientemente bien como para que la mayoría de los programas se ejecuten correcta y eficientemente en un entorno UNIX/X. Las siguientes dos secciones arrojan ejemplos de sistemas paralelos que utilizan esta arquitectura que podrían ser soportados bajo Linux. 1.4.3.2.

Procesadores DSP

Un DSP (“Digital Signal Processor”, Procesador de Señales Digitales) es un tipo de microprocesador muy rápido y potente. Un DSP procesa los datos en tiempo real. Esta capacidad de tiempo real hace de los DSPs perfectos para aplicaciones que no pueden tolerar demoras. Así, suelen emplearse en el Procesamiento Digital de Señales, un método de procesamiento de señales del mundo real que utiliza técnicas matemáticas para realizar transformaciones o extraer información, como se muestra en la figura 1.7. Aquí tenemos algunas de las ventajas de dichos procesadores: Operaciones de multiplicación y suma en un sólo ciclo Funcionamiento en tiempo real, simulación y emulación Flexibilidad Fiabilidad Aumenta rendimiento del sistema

1.4. ARQUITECTURAS BASADAS EN PARALELISMO IMPLÍCITO

17

Disminuye costes Existe un próspero mercado para estos procesadores. Aunque estos chips fueron generalmente diseñados para ser utilizados en sistemas de aplicación específica, también pueden ser utilizados como magníficos computadores paralelos auxiliares. Estos son los beneficios de utilizar dichos procesadores como computadores paralelos auxiliares: Muchos de ellos, como los Texas Instruments TMS320 y los Analog Devices SHARC DSP, están diseñados para construir máquinas paralelas con poca o ninguna lógica de enlace. Son económicos, especialmente por MIP o MFLOP. Incluyendo el coste de la lógica de soporte básica, suele decirse que su coste es una décima parte de lo que cuesta un procesador para PC con un rendimiento comparable. No utilizan mucha energía ni desprenden demasiado calor. Esto significa que es posible tener un grupo de estos chips alimentados por una fuente de alimentación convencional para PCs, y encerrarlos dentro del chasis del PC sin que se convierta en un horno. Existen algunos elementos en los juegos de instrucciones de los DSP que los compiladores de alto nivel no suelen usar de manera apropiada, como por ejemplo la operación “Bit Reverse Addressing”. Usando un sistema paralelo auxiliar, es posible compilar y ejecutar la mayoría del código en el servidor, ejecutando aquellos algoritmos que hacen un mayor consumo de tiempo en los DSPs. Dichos algoritmos pueden ser implementados mediante un código cuidadosamente adaptado. Los procesadores DSP no están diseñados para ejecutar un sistema operativo UNIX, y generalmente no son muy buenos como procesadores de propósito general. Por ejemplo, muchos de ellos no tienen hardware de manejo de memoria. En otras palabras, funcionan mejor como clientes de un servidor de propósito más general... como un PC bajo Linux. Muchas tarjetas de sonido y modems incluyen procesadores DSP que pueden ser accedidos mediante controladores de Linux sin ninguna dificultad. Lo difícil llega cuando utilizamos un sistema paralelo auxiliar que contenga cuatro o más procesadores DSP... y eso es exactamente lo que nos interesa. Existen dos familias de procesadores DSP utilizados ampliamente para procesamiento paralelo: Texas Instruments TMS320 Muy populares durante mucho tiempo, resulta muy sencillo construir un procesador paralelo basado en el TMS320. Existen versiones del TMS320 sólo para enteros y también para punto flotante; los diseños más antiguos usaban algún tipo inusual del formato punto flotante de precisión simple, pero los nuevos modelos soportan los formatos IEEE. El antiguo TMS320C4x consigue hasta 80 Mflops usando el formato punto flotante simple precisión específico de Texas Instruments; en constraste, el TMS320C67x proporciona hasta 1Gflop simple precisión o 420 Mflops doble precisión para los cálculos en formato punto flotante IEEE. No sólo es fácil configurar un grupo de estos chips como un multiprocesador, si no que además existen chips multiprocesadores, como el TMS320C8x que combina en paralelo un procesador RISC maestro con unidad de punto flotante IEEE a 100 Mflops con dos o cuatro DSPs esclavos con unidad de entero.

18

CAPÍTULO 1. INTRODUCCIÓN

Analog Devices SHARC Estos chips pueden ser utilizados como un multiprocesador de 6 procesadores con memoria compartida y sin lógica de conexionado externa. Sistemas mayores pueden ser construidos usando 6 enlaces de 4 bits por chip. Muchos de los sistemas más grandes son empleados en aplicaciones militares, y resultan económicos. En esta línea la compañía Integrated Computing Engines, llamada en la actualidad Media100, ofrece una gama de tarjetas PCI llamadas GreeICE y BlueICE, ésta última más actual. La primera versión (GreenICE) contiene una matriz de 16 procesadores SHARC y es capaz de proporcionar picos de velocidad de hasta 1,9 Gflops usando el formato IEEE simple precisión. BlueICE triplica dicha velocidad, y su coste no es elevado.

1.4.3.3.

FPGAs y Computadores de Lógica Reprogramable

Si el paralelismo consiste en conseguir la máxima velocidad, ¿por qué no construimos nuestro propio hardware? El problema es que cuesta mucho, lleva mucho tiempo su desarrollo, se vuelve inservible cuando cambiamos el algoritmo aunque sea sólo un poco, etc. Sin embargo recientes avances en los FPGAs (“Field Programmable Gate Array”, Matriz de Compuertas Lógicas Programable) eléctricamente reprogramables han anulado dichas objeciones. Ahora la densidad de compuertas es lo suficientemente alta como para un procesador simple pueda ser construido en un único FPGA. Además el tiempo de reconfiguración (reprogramación) de los FPGAs ha bajado a un nivel en el que es razonable incluso reconfigurar el FPGA cuando pasamos de una fase de un algoritmo a otra. Normalmente debemos trabajar con lenguajes de descripción de hardware como VHDL para la reconfiguración del FPGA, así como escribir código de bajo nivel que haga de interfaz con los programas del sistema host Linux. Pero el esfuerzo merece la pena, ya que el coste de los FPGAs es bajo, especialmente para algoritmos que operen con enteros de baja precisión (en realidad un subconjunto de aquellas operaciones para las que fué diseñado SWAR). Los FPGAs pueden realizar complejas operaciones tan rápido como podamos introducir los datos. Por ejemplo, sistemas basados en un único FPGA han alcanzado tiempos mejores que los supercomputadores en la búsqueda de bases de datos genéticas. Las siguientes dos compañías desarrollan hardware basado en FPGA: Virtual Computer Company Esta compañía ofrece una variedad de productos que usan FPGAs Xilinx dinámicamente reconfigurables basados en SDRAM. Destaca su tarjeta “Virtual ISA Proto Board” de 8/16 bit para el puerto ISA. Altera El ARC-PCI (“Altera Reconfigurable Computer PCI bus”, Computador Reconfigurable Altera para bus PCI) es una tarjeta del mismo tipo que la “Virtual ISA Proto Board” de Virtual Computer Company, pero utiliza FPGAs Altera y el interfaz PCI en vez del ISA. Muchas de las herramientas de diseño, lenguajes de descripción de hardware, compiladores, etc. funcionan sólo bajo Windows o DOS, por lo que podríamos utilizar dosemu o wine para ejecutarlos bajo Linux.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

CPU

CPU

19

CPU

E/S

E/S

Interconexión

E/S

Memoria Principal

Figura 1.8: Esquema Multiprocesador

1.5. Arquitecturas Basadas en Paralelismo Explícito 1.5.1. Multiprocesadores Un sistema multiprocesador es aquel que está formado por un conjunto de procesadores que comparten una memoria principal común y están bajo el control de un mismo sistema operativo. Las principales características de un procesador de este estilo son: 1.

Posee dos o más procesadores de propósito general similares y de capacidades comparables.

2.

Todos los procesadores comparten el acceso a una memoria global (común). También pueden utilizarse memorias locales (privadas).

3.

Todos los procesadores comparten el acceso a los dispositivos de E/S, bien a través de los mismos canales o bien a través de canales distintos que proporcionan caminos de acceso a los mismos dispositivos.

4.

El sistema está controlado por un sistema operativo integrado que permite la interacción entre los procesadores y los programas.

La figura 1.8 describe en términos generales la organización de un sistema multiprocesador. Hay dos o más CPUs. Cada CPU es autónoma, incluyendo una unidad de control, una

CAPÍTULO 1. INTRODUCCIÓN

20

CPU

CPU

E/S

E/S

Memoria

Memoria

Bus del Sistema

Figura 1.9: Organización Básica Bus de Tiempo Compartido ALU, registros y posiblemente una caché. Cada CPU tiene acceso a una memoria principal compartida y a los dispositivos de E/S a través de algún mecanismo de interconexión. Los procesadores pueden comunicarse entre sí a través de la memoria (mensajes de información de control almacenada en áreas comunes de datos). También es posible que las CPUs intercambien señales directamente, como indican las líneas discontinuas. La memoria a menudo se organiza de forma que sean posibles los accesos simultáneos a bloques de memoria separados. En algunas configuraciones cada CPU puede tener también su propia memoria principal privada y sus canales de E/S además de los recursos compartidos. 1.5.1.1.

Organización

La organización de un sistema multiprocesador puede clasificarse como sigue: Bus de Tiempo Compartido o Común Memoria Multipuerto Unidad de Control Central Bus de Tiempo Compartido El Bus de Tiempo Compartido es el mecanismo más simple para construir un sistema multiprocesador (figura 1.9). La estructura y las interfaces son básicamente las mismas que las de un sistema monoprocesador que utilice un bus para la interconexión. El bus consta de líneas de control, dirección y datos. Para facilitar las transferencias DMA (“Direct Memory Access”, Acceso Directo a Memoria) con los procesadores de E/S se proporcionan los siguientes elementos: Direccionamiento: Debe ser posible distinguir los módulos del bus para determinar la fuente y el destino del mensaje. Arbitraje: Cualquier módulo de E/S puede funcionar temporalmente como maestro. Se proporciona un mecanismo para arbitrar entre las peticiones que compiten por el control del bus, utilizando algún tipo de esquema de prioridad.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO CPU

CPU

Caché

E/S

E/S

Memoria

21

Memoria

Caché

Bus del Sistema

Figura 1.10: Organización Bus de Tiempo Compartido con Caché Tiempo Compartido: Cuando un módulo está controlando el bus, los demás módulos no tienen acceso al mismo y deben, si es necesario, suspender su funcionamiento hasta que dispongan del bus. Estos elementos son utilizables directamente en una configuración de multiprocesador. En este caso hay varias CPUs además de varios procesadores de E/S que intentan acceder a uno o más módulos de memoria a través del bus. La organización de Bus de Tiempo Compartido presenta diversas ventajas en comparación con otras aproximaciones: Simplicidad: Es la aproximación más sencilla para organizar el multiprocesador. La interfaz física y la lógica de cada procesador para el direccionamiento, el arbitraje, y para compartir el tiempo del bus es la misma que la de un sistema con un solo procesador. Flexibilidad: Es generalmente sencillo expandir el sistema conectando más CPUs al bus. Fiabilidad: El bus es esencialmente un medio pasivo, y el fallo de cualquiera de los dispositivos conectados no provocaría el fallo de todo el sistema. La principal desventaja de la organización de bus compartido son las prestaciones. Todas las referencias a memoria pasan por el bus. En consecuencia, la velocidad del sistema está limitada por el tiempo de ciclo. Para mejorar las prestaciones es deseable equipar a cada CPU con una memoria caché (figura 1.10). Ésta reduciría considerablemente el número de accesos. El uso de cachés introduce algunas consideraciones de diseño nuevas. Puesto que cada caché local contiene una imagen de una parte de la memoria, si se altera una palabra en una caché es posible que quede invalidada una palabra en otra caché. Para evitarlo debe avisarse a las otras CPUs de que se ha producido una actualización de la memoria. Esto por lo general complica el diseño del sistema. Memorias Multipuerto La organización de memorias multipuerto permite el acceso directo e independiente a los módulos de memoria desde cada una de las CPUs y los módulos de E/S (figura 1.11). Se necesitará un sistema de arbitraje para resolver los conflictos. El método que se utiliza a menudo para ello consiste en asignar prioridades fijas a cada puerto de memoria. Normalmente

CAPÍTULO 1. INTRODUCCIÓN

22

M1

M2

Mk

CPU1

E/S 1

CPUn

E/S m

Figura 1.11: Organización Memorias Multipuerto la interfaz física y eléctrica en cada puerto es idéntica a la que aparece en un módulo de memoria de un sólo puerto. Así, se necesitan pocas o ninguna modificación en las CPUs o en los módulos de E/S para adaptarlas a este modelo de organización. La organización de memorias multipuerto es más compleja que la organización de bus compartido, precisándose añadir al sistema una buena cantidad de lógica. No obstante se consiguen mejores prestaciones puesto que cada procesador tiene un camino específico a cada módulo de memoria. Otra ventaja del multipuerto es que permite configurar partes de la memoria como “privadas” para una o más CPUs y/o módulos de E/S. Estas características permiten incrementar la seguridad frente a accesos no autorizados y para el almacenamiento de rutinas de restablecimiento en zonas de memoria no susceptibles de ser modificadas por otros procesadores. Unidad de Control Central La unidad de control central encauza las distintas secuencias de datos entre los distintos módulos independientes: CPU, memoria, E/S. El controlador puede almacenar temporalmente peticiones y realizar las funciones de arbitraje y temporización. Además puede transmitir mensajes de estado y control entre las CPUs y alertar sobre cambios en las cachés. Puesto que toda la lógica de coordinación de la configuración de multiprocesador se concentra en la unidad de control central, las interfaces de E/S, memoria, y CPU no sufren cambios esenciales. Esto proporciona la flexibilidad y simplicidad de conexión propias de la aproximación del bus compartido. Las desventajas clave de esta aproximación son que la unidad de control es bastante compleja y que representa un cuello de botella potencial para las prestaciones.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO 1.5.1.2.

23

Multiprocesadores Simétricos (SMP)

SMP (“Symmetric Multi-Processor”, Multiprocesadores Simétricos) se refiere, en términos de sistemas operativos, al concepto de grupo de procesadores trabajando juntos como pares, de manera que cualquier parte del trabajo puede ser realizada por cualquiera de los procesadores sin diferencia alguna. Este tipo de sistemas son multiprocesadores, es decir, pertenecen al modelo MIMD con memoria compartida. En el mundo IA32, SMP significa cumplir con la norma MPS (“Intel MultiProcessor Specification”, Especificación Multiprocesador de Intel). En un SMP todos los procesadores pueden acceder a la misma memoria, generalmente mediante un bus compartido de alta velocidad. La comunicación entre los procesadores es fácil en principio. Cualquier procesador puede dejar datos o mensajes en una posición determinada y luego indicar a otro procesador la dirección en la que puede encontrar los datos. Esto es típico del multiprocesamiento; así, un computador ejecuta una o más aplicaciones que se componen de una serie de procesos secuenciales que cooperan entre sí. Este esquema se puede implementar en un sistema monoprocesador, pero también se puede implementar fácilmente en un sistema multiprocesador SMP: en cualquier momento cada uno de los múltiples procesadores está ejecutando un proceso distinto. La comunicación entre procesos se realiza mediante mensajes y señales de estado que pueden intercambiarse los procesadores a través de la memoria. En la práctica el nivel de prestaciones deseado complica la comunicación entre los procesadores. Cuando se tienen muchos procesadores rápidos compitiendo por acceder a la misma memoria a través del mismo bus, los conflictos pueden degradar seriamente el rendimiento del conjunto del sistema. La solución, como hemos visto, es añadir una caché local a cada procesador. Esta solución ocasiona el problema adicional de la coherencia de caché. La coordinación entre los procesadores que se requiere para resolver el problema origina un cuello de botella en el bus compartido. El resultado es que los multiprocesadores típicos están limitados a unas pocas decenas de procesadores. Un multiprocesador SMP con miles de procesadores no parece que sea muy práctico. 1.5.1.3.

Soporte SMP Bajo Linux

Antes de entrar a discutir aspectos más técnicos, debemos hacernos primero un par de cuestiones acerca de esta arquitectura que, si bien es una de las más extendidas en procesamiento paralelo, tiene un soporte relativamente reciente en Linux. ¿Funciona realmente SMP en Linux? Funciona. Además es una opción con una buena relación coste/rendimiento para paralelizar nuestro sistema, ya que una placa base con soporte para varios procesadores y sus correspondientes micros normalmente elevará poco el precio del sistema con respecto a un sistema uniprocesador. En la mayoría de las ocasiones para hacer que Linux se ejecute en dicho hardware sólo necesitamos realizar una instalación de Linux con soporte para un solo procesador, y luego recompilar el núcleo con la fila SMP=1 del fichero ‘Makefile’ activa. Entonces informaremos a lilo o nuestro gestor de arranque acerca del nuevo núcleo compilado, y a disfrutar. En cuanto a rendimiento y estabilidad podemos decir son sistemas bastante firmes. En resumen, SMP Linux realmente funciona.

24

CAPÍTULO 1. INTRODUCCIÓN

La siguiente cuestión es cuánto soporte de alto nivel está disponible para escribir y ejecutar programas paralelos con memoria compartida en SMP Linux. Actualmente existe bastante software dedicado a este propósito. Por ejemplo, ahora podemos contar con una librería muy completa para el manejo de hilos POSIX. Aunque el rendimiento puede ser menor que utilizando mecanismos especialmente creados para trabajar con memoria compartida, un sistema SMP Linux también puede usar la mayoría del software de procesamiento paralelo desarrollado originalmente para clusters de estaciones de trabajo. Dicho tipo de software utiliza comunicación vía sockets, y puede funcionar en un sistema SMP Linux e incluso en múltiples SMP conectados en red formando un cluster. De todas formas la comunicación vía sockets implica mucha sobrecarga innecesaria en un sistema SMP. Gran parte de esta sobrecarga se produce dentro del núcleo y en el manejo de interrupciones; ésto empeora el problema ya que SMP Linux generalmente sólo admite un procesador en el núcleo al mismo tiempo y el manejador de interrupciones está implementado de manera que sólo el procesador de arranque (“boot processor”) puede procesar interrupciones. A pesar de ello el hardware de comunicación de un SMP típico es tan superior a la mayoría de las redes de comunicación de los clusters, que el software diseñado para dichos clusters a menudo funcionará mejor en los sistemas SMP que en los clusters para los que fué creado. En el resto de esta sección estudiaremos qué tipo de sistemas SMP soporta Linux, aclararemos qué es la Especificación Multiprocesador de Intel, y haremos algunas observaciones acerca del uso de la memoria caché y la configuración del bus a utilizar. Especificación Multiprocesador de Intel Aunque los sistemas SMP han existido desde hace muchos años, hasta hace poco cada máquina tendía a implementar sus funciones básicas de manera distinta al resto, de forma que el soporte del sistema operativo no era portable. Lo que ha cambiado esta situación es la MPS (“Intel MultiProcessor Specification”, Especificación Multiprocesador de Intel). Los únicos sistemas que no cumplen la norma MPS ni la IA32 y tienen soporte bajo Linux son las máquinas multiprocesador Sun4m de SPARC. Linux tiene soporte para la mayoría de las máquinas que cumplen la norma MPS 1.1 y MPS 1.4 con hasta 16 procesadores 486DX, Pentium, Pentium Pro o superiores. Los procesadores IA32 que no tienen soporte son los procesadores Intel 386, Intel 486SX/SLC (la falta de unidad de punto flotante interfiere en los mecanismos SMP) y los procesadores AMD y Cyrix (requieren chips de soporte SMP que no parecen estar disponibles por el momento). Es importante entender que el rendimiento de los sistemas que cumplen la norma MPS puede variar ampliamente. Como era previsto, una causa de las diferencias de rendimiento es la velocidad del procesador: mayores frecuencias de reloj tienden a proporcionar sistemas más potentes, teniendo en cuenta que un procesador Pentium Pro es más rápido que un Pentium. De todas formas la norma MPS no especifica realmente cómo implementa el hardware la memoria compartida; lo que sí especifica es la manera en la que esta implementación debe funcionar desde el punto de vista del software. Esto significa que el rendimiento está también en función de cómo interactúa la implementación de la memoria compartida con las características SMP Linux y nuestro sistema particular. La principal diferencia entre los sistemas que cumplen la norma MPS es la manera en la que implementan físicamente el acceso a la memoria compartida.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

25

Aspectos sobre la Memoria Caché Algunos sistemas MPS con procesadores Pentium y todos los que llevan procesadores Pentium Pro y superiores tienen cachés L2 (“Level 2”, De Nivel 2) independientes (la memoria caché L2 va dentro del módulo que contiene el procesador). El hecho de tener cachés L2 separadas es considerado generalmente como una optimización del rendimiento; sin embargo ésto no es tan obvio bajo Linux. La principal complicación está en que el planificador de SMP Linux no intenta mantener cada proceso en el mismo procesador, siendo éste un concepto denominado afinidad con el procesador. Ésto podría cambiar pronto; recientemente se han generado discusiones sobre el tema en la comunidad SMP Linux bajo el título “Enlace con el procesador”. Sin afinidad con el procesador, el hecho de tener cachés L2 separadas podría introducir una sobrecarga importante cuando le demos ciclos de reloj a un proceso en un procesador distinto al que estaba ejecutando dicho proceso anteriormente. Muchos sistemas relativamente económicos están organizados de manera que dos procesadores Pentium comparten una memoria caché L2. Lo malo es que ésto provoca competencia entre los procesadores por el uso de la caché, degradando seriamente el rendimiento cuando se ejecutan múltiples programas secuenciales independientes. Sin embargo la mayoría de los programas paralelos se benefician de la memoria caché compartida en situaciones en las que ambos procesadores intentan acceder a la misma línea de la memoria compartida; en dichas situaciones sólo uno de los procesadores debe acceder a la caché y la competencia entre los procesadores es evitada. De este modo se crea el efecto “búsqueda compartida”. Además la falta de afinidad con el procesador provoca menos daño con una caché L2 compartida. Así, en programas paralelos no está realmente claro que la compartición de caché L2 sea tan dañina como cabe esperar. La experiencia demuestra que la caché de los sistemas SMP Linux muestran grandes diferencias en su rendimiento dependiendo del nivel de actividad del núcleo requerida. En el peor de los casos el aumento es 1.2 veces la velocidad del procesador. De todas maneras también se han observado picos de aumento de hasta 2.1 veces la velocidad del procesador, lo cual sugiere que el cómputo intensivo de código con el modelo SPMD saca provecho del efecto “búsqueda compartida”. Configuración del Bus Lo primero que hay que decir es que la mayoría de los sistemas modernos conectan los procesadores (en turnos) a uno o más buses PCI que hacen de puente hacia uno o más buses ISA/EISA. Estos puentes añaden latencia, y además los buses EISA e ISA ofrecen generalmente una menor velocidad de transferencia de datos que los PCI (ISA es el de menor velocidad), de manera que las unidades de disco, tarjetas de vídeo y otros componentes de alto rendimiento deben ser conectados al bus PCI. Aunque un sistema MPS puede alcanzar una buena velocidad en la ejecución de muchos programas paralelos de cómputo intensivo (incluso si sólo hay un bus PCI de tiempo compartido), las operaciones de E/S no se ejecutan mejor que en los sistemas uniprocesador... de hecho irán probablemente peor debido a la competencia por el bus entre los procesadores. Así, si lo que buscamos es mejorar el rendimiento de las operaciones E/S debemos emplear un sistema MPS con múltiples buses PCI independientes y controladoras E/S (por ejemplo, múltiples controladoras SCSI). Antes que nada necesitaremos estar seguros de que SMP Lin-

CAPÍTULO 1. INTRODUCCIÓN

26

ux soporta el sistema que se desea emplear. Además debemos tener en cuenta que actualmente Linux permite sólo un procesador en el núcleo al mismo tiempo, de manera que elegiremos aquellas controladoras E/S que minimicen el tiempo requerido en el núcleo para realizar cada operación E/S. Para conseguir un alto nivel de rendimiento tendremos que considerar la posibilidad de manejar la E/S de los dispositivos directamente, sin hacer llamadas al sistema... esto no es tan difícil como parece, y tampoco debería comprometer la seguridad. Es importante hacer notar que la relación entre la velocidad del bus y la frecuencia de reloj del procesador se ha vuelto más difusa durante los últimos años. Actualmente no es extraño encontrar sistemas con mayor frecuencia de reloj en el procesador y a la vez menor frecuencia en el bus, en comparación con otros sistemas. El ejemplo clásico de ésto es el Pentium 133, el cual usa generalmente un bus más rápido que el Pentium 150, debido a la búsqueda de un mayor rendimiento en varios bancos de prueba. Estos efectos se amplifican en los sistemas SMP. De todos modos, en la mayoría de los casos es más importante tener un bus rápido.

1.5.2. Multicomputadores Un sistema multicomputador es aquel que está formado por un conjunto de sistemas relativamente autónomos, en los que cada CPU dispone de su propia memoria principal y sus canales de E/S. En este tipo de sistemas, cada procesador tiene su propio espacio de memoria privado, que no resulta visible para los otros procesadores. Según ésto los resultados y la información de coordinación debe pasarse entre los nodos a través de una red de interconexión, usualmente en forma de mensajes con un formato determinado. Una de las motivaciones principales para el desarrollo de organizaciones de multicomputador es la de superar las limitaciones de escala de los multiprocesadores; de éste modo los multicomputadores poseen una mayor escalabilidad. Se define como escalabilidad de un sistema a su capacidad para responder a cargas de trabajo crecientes. En un sistema de procesamiento paralelo, se mide mediante el número de máquinas que pueden conectarse al sistema sin que el rendimiento del sistema caiga. El objetivo es desarrollar una organización escalable que pueda dar cabida a un amplio rango de número de procesadores. Puesto que los procesadores en un multicomputador deben comunicarse mediante el intercambio de mensajes, un elemento clave en el diseño es la red de interconexión, que debe realizarse para operar lo más eficientemente posible. En general existe un compromiso entre la distancia máxima entre dos nodos y el número de conexiones físicas que se desea en cada nodo. Se han explorado varias tecnologías de interconexión para proporcionar escalabilidad y hacer posible un comportamiento eficiente. A continuación describiremos las topologías más extendidas: Anillo: Si la comunicación es bidireccional a lo largo del anillo, entonces la distancia máxima entre dos nodos cualesquiera para un anillo de  nodos es '$)( . Usualmente se utilizan paquetes de mensajes de tamaño fijo que contienen la dirección del destino deseado. Esta topología es apropiada para un número relativamente pequeño de procesadores con una comunicación de datos mínima. La figura 1.12 ilustra un anillo con cuatro nodos.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

27

Figura 1.12: Topología Anillo

Figura 1.13: Topología Malla Malla: La forma más simple de una malla es una matriz bidimensional en la que cada nodo se conecta a cuatro vecinos. En una malla simple de +* nodos, la distancia máxima entre dos nodos es (-,.0/2143 . Si hay conexiones cíclicas utilizando los nodos de los bordes, la distancia máxima se reduce a (-,.'$)(53 . La organización en malla es adecuada para ejecutar algoritmos orientados a matrices. La figura 1.13 ilustra una malla de 3*3 nodos. Árbol: Las redes con topología de árbol se han investigado para ejecutar algoritmos de tipo divide-y-vencerás, tales como los de búsqueda y ordenación. La figura 1.14 ilustra

Figura 1.14: Topología Árbol

CAPÍTULO 1. INTRODUCCIÓN

28

Figura 1.15: Topología Hipercubo Número de nodos 16 256 1024 2048 16384

Malla 6 saltos 30 saltos 62 saltos 126 saltos 254 saltos

Hipercubo 4 saltos 8 saltos 10 saltos 11 saltos 16 saltos

Cuadro 1.1: Diámetros Topologías Hipercubo y Malla un árbol binario sencillo.



Hipercubos: Una topología hipercubo utiliza 6 (87 procesadores distribuidos en un hipercubo de dimensión  . Cada enlace tiene  enlaces bidireccionales a nodos adyacentes. También  representa la distacia máxima entre dos nodos de dicho hipercubo. En  (  1:9 procesadores. la figura 1.15 mostramos un hipercubo de dimensión 4, con 6 Desde la perspectiva de la implementación hardware de una topología, la topología hipercubo es la más atractiva. En el cuadro 1.1 comparamos la comunicación en el peor caso en las topologías hipercubo y malla. El hipercubo se escala bien: el diámetro del sistema crece lentamente con el número de nodos, en comparación con la malla. Recientemente ha surgido un interés creciente por pasar de topologías fijas a topologías seleccionables por el usuario y controladas por una red de enrutamiento. En lugar de conectar todos los procesadores juntos mediante enlaces directos, se conectan a una red de enrutamiento rápida que utiliza conmutadores para establecer e interrumpir las conexiones virtuales, de una forma similar a la conmutación de paquetes. Si los conmutadores se diseñan para que ocasionen retardos mínimos en los mensajes, el retardo de comunicación se incrementará ligeramente al añadir más nodos al sistema. Otra propiedad atractiva es que cada procesador necesita sólo una conexión bidireccional a la red de conmutadores.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

29

Los sistemas multicomputador pueden dividirse básicamente en dos categorías: Clusters (o agrupamientos de nodos). Estos sistemas son grupos de nodos que se comunican a través de una interfaz de red. Deben tener un buena relación coste/rendimiento, por lo que en principio sólo debemos utilizar para su montaje componentes hardware relativamente comunes. MPPs (“Massively Parallel Processors”, Procesadores Masivamente Paralelos). Estos sistemas pueden distinguirse de los anteriores por las propiedades que los hacen Masivamente Paralelos:

;

Utilización de interconexiones de muy alto rendimiento

; ;

Capacidad de E/S inmensa Tolerancia a fallos

Seguramente quedemos sorprendidos al comprobar que estos sistemas no necesitan CPUs de gama alta. La mayoría de los mejores sistemas MPPs tienen miles de CPUs, siendo más importante para el rendimiento del sistema la calidad de las interconexiones y su topología. 1.5.2.1.

Clusters o Agrupamientos de Nodos

Una de las posibilidades de mejor relación coste/rendimiento es la proporcionada por los clusters, grupos de nodos conectados a través de una interfaz de red. Dicha organización crea un sistema multicomputador, es decir, un sistema de procesamiento paralelo perteneciente al modelo MIMD con memoria distribuida. Por supuesto su tipología puede ser muy variada, así como el soporte tanto hardware como software. Afortunadamente existe mucho y variado soporte software para el procesamiento paralelo usando PCs bajo Linux, gracias a la popularidad de esta tecnología. La utilización de clusters en procesamiento paralelo supone muchas ventajas, como son: Cada una de las máquinas de un cluster puede ser un sistema completo, que puede ser utilizado para ejecutar una amplia gama de aplicaciones. Ésto lleva a pensar que el procesamiento paralelo bajo clusters no es más que una manera de aprovechar los “ciclos desperdiciados” por los usuarios de PCs. Sin embargo no es tan sencillo aprovechar estos ciclos sin ralentizar el trabajo primario para el que se utilizan dichas estaciones de trabajo, pero puede hacerse. La creciente popularidad de los sistemas en red hace que la mayoría del hardware que necesitamos para construir un cluster se fabrique a gran escala, con la correspondiente bajada de precios como resultado. También reduce el coste del sistema el hecho de que sólo necesitamos una consola (es decir, una tarjeta de vídeo, un monitor y un teclado) para todo el cluster, aunque necesitemos conectar dicha consola a cada máquina al principio para hacer una instalación inicial; una vez hecha la instalación, un PC bajo Linux no necesita una consola para funcionar. En comparación, los SMP y los Procesadores Auxiliares pertenecen a mercados mucho más restringidos, con lo que suelen tener precios más elevados.

30

CAPÍTULO 1. INTRODUCCIÓN

Figura 1.16: Objetivo Procesamiento Paralelo en Clusters Los clusters pueden llegar a formar sistemas verdaderamente amplios, no teniendo las limitaciones de escala de los SMP. Mientras que es complicado encontrar sistemas SMP compatibles con Linux con más de 4 procesadores, podemos construir un cluster de hasta 16 sistemas con casi cualquier hardware de red común. Con no mucho trabajo, cientos e incluso miles de máquinas pueden ser interconectadas. De hecho, Internet entero puede ser vista como un cluster verdaderamente gigantesco. El hecho de que sustituir un computador estropeado en un cluster sea trivial comparado con arreglar un SMP parcialmente estropeado hace que la disponibilidad sea mucho mayor en los clusters cuidadosamente diseñados. Ésto es importante no sólo en aplicaciones particulares que no toleren interrupciones en el servicio, si no que también en sistemas de uso general que contengan suficientes procesadores como para que sean muy comunes los fallos aislados. Por ejemplo, incluso cuando la media de fallo de un PC sea de dos años, en un cluster con 32 máquinas la probabilidad de que una falle en los primeros 6 meses es muy alta. La conclusión es que los clusters son económicos, que los dispositivos necesarios para construirlo están disponibles, y que se pueden construir sistemas verdaderamente amplios; pero por supuesto no todo son ventajas. También existen una serie de problemas: Excepto muy pocas excepciones, el hardware de red no está diseñado para el procesamiento paralelo. Normalmente la latencia es muy alta y la velocidad de transferencia de datos relativamente baja comparada con la proporcionada por los SMPs y los procesadores auxiliares. Por ejemplo, la latencia casi nunca supera unos pocos microsegundos en los SMPs, pero casi siempre es igual o mayor a cientos o miles de microsegundos en un cluster. La velocidad de transferencia de datos en los SMP es mayor de 100

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

31

Mbytes/seg; aunque el hardware de red más rápido (Gigabyte Ethernet) ofrece una velocidad comparable, la mayoría de las redes comunes son entre 10 y 1000 veces más lentas. El rendimiento del hardware de red puede ser suficiente si es una red aislada para cluster. Si la red no está aislada de otro tráfico, el rendimiento puede ser sustancialmente peor. Existe poco soporte de software para manejar un cluster como si se tratara de un sólo sistema. Por ejemplo, el comando ps nos informa de los procesos que concurren en un sistema Linux, pero no nos informa de todos los procesos que concurren en el cluster de sistemas Linux. Con todo ésto, podemos decir que los clusters ofrecen una gran potencia, pero dicha potencia puede ser difícil de alcanzar en la mayoría de las aplicaciones. Lo bueno es que existe una gran cantidad de software que nos puede ayudar a conseguir un alto rendimiento en programas bien adaptados a este entorno, y que existen redes diseñadas específicamente para ampliar el rango de programas que pueden alcanzar un buen rendimiento. 1.5.2.2.

Sistemas Beowulf

Un sistema Beowulf es básicamente un cluster dedicado al procesamiento paralelo. Es un sistema que usualmente consta de un nodo servidor y uno o más nodos clientes conectados vía Ethernet o algún otro tipo de red. Es un tipo de sistema que se construye empleando hardware común, como por ejemplo PCs bajo Linux, adaptadores Ethernet estándar y hubs convencionales. No contiene ningún hardware especializado y es trivialmente reproducible. Además Beowulf usa software común como Linux, PVM y MPI. El nodo servidor controla todo el cluster y ofrece ficheros a los nodos clientes. También es la consola del cluster y su conexión al exterior. Los sistemas Beowulf más grandes pueden tener más de un nodo servidor, y posiblemente otros nodos dedicados a tareas particulares, por ejemplo consolas o estaciones de monitorización. En la mayoría de los casos los nodos clientes no tienen dispositivos directos de E/S; son controlados y configurados por el nodo servidor. En una configuración de clientes sin disco, los clientes no conocen su IP ni su nombre hasta que el nodo servidor se lo envía. Una de las principales diferencias entre un Beowulf y un COW(“Cluster Of Workstations”, Cluster de Estaciones de Trabajo) es que el comportamiento de un Beowulf es más parecido al de una única máquina que al de un grupo de estaciones de trabajo. En la mayoría de los casos los clientes no tienen teclado ni monitor, y son accedidos sólo a través de login remoto o posiblemente mediante un terminal serie. Podemos pensar en los nodos de un sistema Beowulf como en paquetes CPU+Memoria que pueden ser agregados al cluster, de la misma manera que una CPU o un módulo de memoria puede ser agregado a una placa base. Beowulf no es un paquete especial de software, ni una nueva topología de red, ni la última modificación del núcleo de Linux. Beowulf es una manera de crear clusters de PCs bajo Linux para formar un supercomputador virtual paralelo. Existen muchos paquetes software como modificaciones del núcleo de Linux, librerías PVM y MPI, y herramientas de configuración que hacen la arquitectura Beowulf más rápida, fácil de configurar y útil. Sin embargo podemos construir una máquina de tipo Beowulf usando una distribución estándar Linux sin software adicional. Si tenemos dos ordenadores con Linux en red que comparten un sistema de ficheros

CAPÍTULO 1. INTRODUCCIÓN

32

‘/home’ vía NFS (“Network File System”, Sistema de Ficheros en Red) y podemos ejecutar shell remoto (rsh) desde una máquina a otra, entonces podemos argumentar que tenemos un sistema Beowulf simple de dos nodos. Clasificación Sistemas Beowulf En la práctica los sistemas Beowulf han sido construidos de distintas maneras. Debido a la búsqueda de un mayor rendimiento a veces han sido empleados componentes no comunes, como por ejemplo aquellos que son comercializados por sólo un fabricante. Para tener en cuenta los diferentes tipos de sistemas existe la siguiente clasificación. BEOWULF CLASE I: Este tipo de máquinas son construidas a base de componentes sacados del mercado común. La definición estricta es que un Beowuf CLASE I debe se ensamblado a partir de componentes que se puedan encontrar en al menos tres catálogos de publicidad nacionales o internacionales. Las ventajas de los sistemas de CLASE I son: El hardware está disponible en múltiples fuentes (bajo precio, fácil mantenimiento). Ausencia de dependencia con respecto a un único fabricante. Soporte bajo Linux garantizado en sus distribuciones más comunes. Usualmente basado en estándares (SCSI, Ethernet, etc.). Las desventajas de los sistemas de CLASE I son: Mayor rendimiento puede requerir hardware de la CLASE II. BEOWULF CLASE II: Un Beowulf de CLASE II es simplemente cualquier máquina que no pueda ser ensamblada utilizando únicamente hardware común. Ésto no es un impedimento. De hecho ésto es sólo una clasificación. Las ventajas de los sistemas de CLASE II son: El rendimiento puede llegar a ser realmente alto Las desventajas de los sistemas de CLASE II son: El soporte bajo Linux puede variar de una distribución a otra. Existencia de dependencia con respecto a un único fabricante. Suelen ser sistemas más caros que los de CLASE I. Una clase no tiene porqué ser necesariamente mejor que la otra. Todo depende de nuestras necesidades y nuestro presupuesto. Ésta clasificación sólo pretende que las discusiones sobre los sistemas Beowulf sean coherentes y detalladas.

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO 1.5.2.3.

33

Hardware de Red

Las redes de ordenadores pertenecen a un campo en pleno auge. El desarrollo de las tecnologías y la aparición de nuevos productos hacen que cada vez esté más al alcance de todos generar procesamiento paralelo a través de un cluster. Sin embargo no existe una tecnología de red que resuelva todos los problemas de la mejor manera; de hecho, la variedad de posibilidades, costes y rendimientos es tremenda. A continuación definiremos las características de algunos de los tipos de red más populares: ATM Soporte bajo Linux: controladores del núcleo, librería AAL Velocidad de Transferencia de Datos: 155 Mb/seg Latencia: 120 =@?A Disponibilidad: varios fabricantes Interfaz: PCI Estructura de Red: conexión mediante hub dedicado Al menos en parte podría decirse que la tecnología ATM (“Asynchronous Transfer Mode”, Modo de Transferencia Asíncrona) es el futuro. ATM no tiene un coste elevado y es más rápida que Fast Ethernet; además puede ser usada a través de las largas distancias que las compañías de teléfono pueden cubrir. El protocolo de red ATM está diseñado para proporcionar una interfaz software con poca sobrecarga y un manejo más eficiente de los mensajes pequeños y de las comunicaciones en tiempo real (p.ej. vídeo y audio digital). Además es una de las redes con mayor velocidad de transferencia de datos que Linux soporta actualmente. Lo malo es que no es una tecnología barata y que aún existen algunos problemas de compatibilidad entre los distintos fabricantes. Ethernet Soporte bajo Linux: controladores del núcleo Velocidad de Transferencia de Datos: 10 Mb/seg Latencia: 100 =@?A Disponibilidad: hardware común Interfaz: PCI Estructura de Red: hub dedicado o compartido, o bus multipuerto sin hub

CAPÍTULO 1. INTRODUCCIÓN

34

Durante algunos años, la Ethernet de 10 Mb/seg ha sido la tecnología estándar de red. De hecho un gran número de PCs tienen su controladora Ethernet integrada en la placa base. En redes con poca carga podemos organizar las conexiones Ethernet como un bus multipuerto sin hub; esta configuración puede servirnos para conectar hasta 200 ordenadores con un coste mínimo, pero no es apropiado para procesamiento paralelo. Añadir un hub compartido no va a mejorar el rendimiento en realidad. Sin embargo los hubs dedicados proporcionan la máxima velocidad de transferencia de datos a conexiones simultáneas y no tienen un alto coste por ordenador. Linux soporta un amplio rango de interfaces Ethernet, pero es importante recordar que las variaciones en el hardware de la interfaz pueden suponer importantes diferencias en el rendimiento. Fast Ethernet Soporte bajo Linux: controladores del núcleo Velocidad de Transferencia de Datos: 100 Mb/seg Latencia: 80 =&?BA Disponibilidad: hardware común Interfaz: PCI Estructura de Red: hub dedicado o compartido Aunque existen varias tecnologías que se llaman a sí mismas “Fast Ethernet” este término se usa principalmente para referirnos a las Ethernet de 100 Mb/seg basadas en hub que son compatibles con los dispositivos y cables utilizados para las Ethernet “10 BaseT” de 10 Mb/seg. Como podíamos esperar esta tecnología posee un enorme mercado, con lo cual su relación prestaciones/precio es bastante mejor que en otras configuraciones. Sin embargo la trampa está en que al dividir el ancho de banda de un único bus de 100 Mb/seg entre un grupo de ordenadores mediante un hub compartido, el rendimiento puede quedar por debajo del que obtendríamos al utilizar una Ethernet de 10 Mb/seg con un hub dedicado, la cual proporciona a cada ordenador una conexión completa de 10 Mb/seg. Los hubs dedicados que proporcionan 100 Mb/seg a cada computador simultáneamente son caros, aunque sus precios bajan a diario y proporcionan un rendimiento muy superior al que obtenemos utilizando los hubs compartidos. Gigabit Ethernet Soporte bajo Linux: controladores del núcleo Velocidad de Transferencia de Datos: 1000 Mb/seg Latencia: 300 =&?BA Disponibilidad: varios fabricantes Interfaz: PCI Estructura de Red: hub dedicado o FDRs

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

35

En principio Gigabit Ethernet no tiene buenas razones tecnológicas para ser llamada Ethernet. Sin embargo dicho nombre refleja la intención de que en un futuro sea una tecnología barata y destinada a un amplio mercado, con soporte nativo para IP. Sin embargo su precio actual hace que no resulte económica su utilización. Al contrario que en otras tecnologías Ethernet, Gigabit Ethernet ofrece un control a bajo nivel que aporta fiabilidad a dicho tipo de red. Los FDRs (“Full Duplex Repeaters”, Repetidores Full Duplex) multiplexan las líneas utilizando buffers y control de flujo localizado para mejorar el rendimiento. La mayoría de los hubs dedicados están siendo construidos con nuevos módulos interfaces para que sean compatibles con los dispositivos Gigabit. Existe un driver bajo Linux para la interfaz Yellowfin G-NIC de Packet Engines (URL [13]). Los primeros test bajo Linux arrojaron un ancho de banda unas 2,5 veces superior a la 100 Mb/seg Fast Ethernet; en las redes Gigabit la configuración del bus PCI es un factor crítico. FireWire (IEEE 1394) Soporte bajo Linux: no Velocidad de Transferencia de Datos: 394 Mb/seg Disponibilidad: varios fabricantes Interfaz: PCI Estructura de Red: aleatorio sin ciclos (configuración automática) FireWire (URL [2]), el estándar IEEE 1394-1995, está destinado a ser la red digital de bajo coste y alta velocidad para consumidores en general. Aunque suela promocionarse como la interfaz a la cual conectar cámaras de vídeo digitales a nuestro ordenador, FireWire está pensada para ser utilizada en aplicaciones que van desde ser el sustituto de SCSI hasta conectar los componentes de reproducción de vídeo y audio. Permite conectar hasta 64k dispositivos utilizando cualquier topología que haga uso de buses y puentes sin ciclos, y automáticamente detecta los componentes cuando son conectados o desconectados (conexión en caliente). Soporta mensajes cortos con baja latencia así como trasmisiones asíncronas al estilo ATM (usadas para mantener sincronizados los mensajes multimedia). Adaptec tiene productos FireWire que permiten la conexión de hasta 63 dispositivos a una tarjeta PCI. Aunque FireWire no será la red de mayor ancho de banda disponible dentro de un tiempo, el mercado de consumo (que puede abaratar bastante los precios) y el soporte para mensajes con baja latencia hacen de ésta una de las mejores tecnologías para construir clusters de PCs bajo Linux utilizando redes de paso de mensajes, al menos durante los próximos años. PLIP Soporte bajo Linux: controladores del núcleo Velocidad de Transferencia de Datos: 1,2 Mb/seg Latencia: 1000 =@?A Disponibilidad: hardware común

CAPÍTULO 1. INTRODUCCIÓN

36 Interfaz: SPP Estructura de Red: cable entre dos ordenadores

Sólo por el coste de un cable LapLink, PLIP (“Parallel Line Interface Protocol”, Protocolo de Interfaz de Línea Paralela) permite comunicar dos máquinas Linux a través del puerto paralelo estándar utilizando software basado en sockets. En términos de velocidad de transferencia de datos, latencia y escalabilidad, no es una tecnología de redes seria; sin embargo, su bajísimo coste y alta compatibilidad lo hacen útil. El controlador forma parte de las distribuciones estándar del núcleo de Linux. SLIP Soporte bajo Linux: controladores del núcleo Velocidad de Transferencia de Datos: 0,1 Mb/seg Latencia: 1000 =&?BA Disponibilidad: hardware común Interfaz: RS232C Estructura de Red: cable entre dos ordenadores Aunque SLIP (“Serial Line Interface Protocol”, Protocolo de Interfaz de Línea Serie) está situado al final del espectro de rendimiento, SLIP (o CSLIP o PPP) permite establecer comunicación mediante sockets entre dos ordenadores a través del puerto serie RS232 ordinario. Los puertos RS232 pueden ser conectados mediante un cable serie “null-modem” RS232 o incluso a través de un módem. En cualquier caso la latencia es alta y la velocidad de transferencia de datos baja, de manera que SLIP sólo debe ser usado cuando no exista otra alternativa disponible. Sin embargo es mejor que nada; además la mayoría de los PCs tienen dos puertos RS232, de manera que podemos crear una red conectando un grupo de ordenadores de manera linear o en topología de anillo. También existe un software de compartición llamado EQL. USB Soporte bajo Linux: controladores del núcleo Velocidad de Transferencia de Datos: 12 Mb/seg Disponibilidad: hardware común Interfaz: USB Estructura de Red: bus

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

37

UNIDAD DE CONTROL

DISTRIBUIDOR DE LA RED

PE

PE

PE

PE

PE

PE

PE

PE

PE

PE

PE

PE

ELEMENTOS PROCESADORES

Figura 1.17: Esquema Procesador Matricial USB (“Universal Serial Bus”, Bus Serie Universal) (URL [20]) es un bus serie que proporciona la velocidad de una interfaz ethernet convencional. Soporta conexión en caliente (podemos “enchufar” cualquier dispositivo USB con el ordenador encendido) y puede manejar simultáneamente hasta 127 periféricos que van desde teclados hasta cámaras de videoconferencia. En realidad no existe una especificación clara sobre la metodología a seguir para conectar varios PCs mediante este puerto; sin embargo la importancia del estándar y su comodidad hacen de esta interfaz una alternativa a tener en cuenta. Se puede decir que USB es la versión barata y de bajo rendimiento de FireWire que podemos utilizar en casi cualquier PC.

1.5.3. Procesadores Matriciales Esta arquitectura es representativa del modelo SIMD, es decir, una sola instrucción opera simultáneamente sobre múltiples datos. Un procesador matricial está formado por un conjunto de elementos procesadores (EPs) sincronizados que funcionan bajo la supervisión de una unidad de control (UC). Normalmente dicha UC es un procesador escalar que cuenta con su propia memoria para almacenar programas y datos. Además, cada EP tendrá también su propia memoria. En la figura 1.17 se muestra el esquema general de este tipo de arquitectura. El funcionamiento de este sistema es el siguiente: la UC busca y decodifica las instrucciones de la memoria central y, dependiendo del tipo de instrucción, son ejecutadas directamente en la unidad de control o bien son transmitidas a los EPs para su ejecución. Las

38

CAPÍTULO 1. INTRODUCCIÓN

instrucciones escalares y de control de flujo como saltos, etc. se ejecutan en la UC, mientras que las instrucciones aritmético-lógicas, las de enrutado de datos y otras operaciones locales son transmitidas a los EPs y ejecutadas por éstos sobre su memoria local. Respecto a los datos, los EPs tienen sus propios canales de E/S. De esta manera, la instrucción que ejecutan simultáneamente los EPs es la misma, mientras que los datos serán los de la memoria de cada EP, y por tanto serán diferentes. Por todo ello un procesador sólo requiere un único programa para controlar todos los EPs. La idea de utilización de los procesadores matriciales es la de explotar el parlalelismo en los datos de un problema más que la de paralelizar la secuencia de ejecución de las instrucciones. El problema se paraleliza dividiendo los datos en particiones sobre las que se pueden realizar las mismas operaciones. Un tipo de datos altamente particionable es el formado por vectores y matrices, siendo éste último el tipo de datos hacia el cual están más orientadas este tipo de arquitecturas. Por ello a estos procesadores se les llama matriciales. Aparte del propio paralelismo obtenido por el cálculo en paralelo sobre los elementos de un vector o matriz, la propia red de interconexión entre los EPs reduce el tiempo de ejecución en determinadas tareas. Dicha red se encarga de conectar a los EPs con sus propios vecinos. De esta manera la topología de la red de interconexión determinará qué tipo de cálculos sacan el máximo partido a determinado procesador matricial. Por ejemplo, en el tratamiento de imágenes, donde muchas operaciones son cálculos entre píxels vecinos, una arquitectura matricial con una topología adecuada paralelizaría con facilidad dichos cálculos. Un caso particular de los procesadores matriciales son los Procesadores Asociativos o “Associative Processors” cuya principal característica es la utilización de memorias asociativas. La ejecución de la misma operación sobre distintas informaciones se usa en la simulación de condiciones climatológicas, control de tráfico aéreo, operaciones con matrices, etc. Ejemplos de computadores con esta organización son el ILLIAC IV, PEPE, BSP STARAN y ICLDAP.

1.5.4. Procesadores Vectoriales En esencia los procesadores vectoriales son máquinas con unidades funcionales vectoriales segmentadas (en definitiva ALUs segmentadas) diseñadas para optimizar las operaciones con estructuras de tipo vectorial. Este tipo de paralelismo es considerado MISD por la mayoría de los científicos debido a la utilización de ALUs segmentadas. La segmentación hace posible que varias instrucciones pueden ser ejecutadas simultáneamente sobre un mismo dato (el vector). Al igual que en los procesadores matriciales el paralelismo viene de que al operar con vectores o matrices normalmente sus elementos son independientes entre sí, es decir, en general no existen dependencias entre los datos dentro de los propios vectores o matrices. Esto permite que muchas de las operaciones aplicadas a un determinado vector y todas las que se hacen entre elementos de unos vectores con otros puedan realizarse en paralelo, o al menos en distintas etapas del mismo cauce de instrucciones sin que haya un conflicto entre los datos. Un computador vectorial estará formado normalmente por un procesador escalar y un procesador vectorial diseñado específicamente para operar con vectores. Dicho procesador vectorial contendrá a su vez varias ALUs, cada una de las cuales opera sobre un vector completo. Además dichas ALUs se encuentran completamente segmentadas y pueden comenzar una nueva operación cada ciclo de reloj. De esta manera el paralelismo proviene de la repeti-

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

39

ción de ALUs y de su segmentación. Sin embargo es la segmentación la que hace que varias instrucciones puedan ser ejecutadas al mismo tiempo sobre un determinado vector. Dependiendo del tipo de procesador vectorial cada ALU será totalmente funcional o bien se encargará de realizar una función específica, como suma/resta, multiplicación, división, etc. Además debe existir una unidad de Carga/Almacenamiento encargada de leer los vectores desde la memoria y almacenarlos en ella. La diferencia entre este tipo de procesadores y los matriciales es que mientras los matriciales son comandados por las instrucciones, los vectoriales son comandados por flujos de datos continuos. Así mientras en los procesadores matriciales sólo existe un flujo de instrucciones entre la unidad de control y los elementos procesadores, en los computadores vectoriales tenemos dos flujos separados: el de instrucciones y el de datos. En este caso, el procesador escalar envía un flujo de datos continuo hacia el procesador vectorial, indicándole la operación que debe realizar mediante el flujo de instrucciones. En la figura 1.18 mostramos el diseño típico de un procesador vectorial con registros.

40

Procesador escalar Cauces funcionales escalares Procesador vectorial

Instrucciones escalares Instrucciones vectoriales

Unidad de control escalar

Unidad de control vectorial Control

Instrucciones

Datos escalares

Cauce func. vectorial

Memoria principal (Programa y datos)

Computador anfitrión

Registros vectoriales

E/S Usuario

Figura 1.18: Esquema Procesador Vectorial

Cauce func. vectorial

CAPÍTULO 1. INTRODUCCIÓN

Almacenamiento masivo

Datos vectoriales

1.5. ARQUITECTURAS BASADAS EN PARALELISMO EXPLÍCITO

41

Figura 1.19: Cray SX-6 Los procesadores vectoriales, según el método de almacenamiento de los operandos, se clasifican en: Máquinas vectoriales con registros : En una máquina de este tipo todas las operaciones vectoriales excepto las de carga y almacenamiento operan con vectores almacenados en registros. La mayoría de máquinas vectoriales modernas utilizan este tipo de arquitectura. Ejemplos: Cray Research (CRAY1, CRAY-2, X-MP, Y-MP y C90), supercomputadores japoneses (NEC SX Series, las Fujitsu VP200 y VP400 y la Hitachi S820). Máquinas vectoriales memoria-memoria : En este tipo de máquinas, todas las operaciones vectoriales son de memoria a memoria. Como la complejidad interna así como el coste son menores, es la primera arquitectura vectorial que se empleó. Ejemplo: el CDC. Los supercomputadores vectoriales empezaron con modelos monoprocesadores como el Cray 1 en 1976. Los supercomputadores vectoriales recientes ofrecen ambos modelos, el monoprocesador y el multiprocesador. La mayoría de supercomputadores de altas prestaciones modernos ofrecen multiprocesadores con hardware vectorial como una característica más de los equipos. En el cuadro 1.2 vemos algunos ejemplos de procesadores vectoriales con sus características principales.

CAPÍTULO 1. INTRODUCCIÓN

42

Computadora

Año

Hitachi S820 Cray 2 Cray Y-MP NEC SX-3 Cray C90 Cray 3

1983 1985 1988 1989 1991 1995

Ciclo Reloj (ns) 4.0 4.1 6.0 2.9 4.0 2.0

Ciclo Reloj (Mhz) 71 166 166 400 240 500

máx CPUs 1 4 8 4 16 16

Pico CPU (Mflop/s) 2000 488 333 5500 1000 2000

Cuadro 1.2: Ejemplos Computadores Vectoriales

Pico Total (Mflop/s) 2000 1952 2667 22000 16000 32000

Capítulo 2

Herramientas para el Desarrollo de Software Paralelo Una vez resuelto el sistema de intercomunicación física de los equipos, deben abordarse los mecanismos para lograr la coordinación entre los procesadores. Básicamente existen dos modelos de interacción entre procesadores: paso de mensajes y memoria compartida. Dichos modelos se pueden utilizar de varias formas. Como en todas las áreas de la programación, existen varios métodos para alcanzar el objetivo: Por un lado podemos implementar dichos modelos a bajo nivel, utilizando código máquina, ensamblador o compiladores de lenguajes no especializados. Dicha alternativa nos permite desarrollar un código más adaptado y optimizado para el hardware que vayamos a usar. Por otro lado podemos emplear utilidades de desarrollo de software paralelo, que son básicamente facilidades para la programación a alto nivel de aplicaciones distribuidas (compiladores, librerías, etc.) y herramientas para su ejecución y monitorización. Dichas utilidades de programación permiten al programador generar de manera automática comunicación mediante paso de mensajes y memoria compartida sin que deba preocuparse de los detalles. Las ventajas de emplear dichas utilidades son su facilidad de manejo y la portabilidad de los algoritmos desarrollados. A continuación estudiaremos las características básicas de los dos modelos de interacción antes mencionados, para luego centrarnos en las utilidades de desarrollo más populares que existen en la actualidad.

2.1. Modelos de Interacción entre Procesadores 2.1.1. Paso de Mensajes El paso de mensajes es un modelo de interacción entre los procesadores que forman un sistema paralelo. A grandes rasgos un mensaje es un conjunto de datos definido mediante software por un procesador y enviado a través de una red de comunicaciones hacia otro procesador, el cual debe aceptar el mensaje y actuar según su contenido. 43

44

CAPÍTULO 2. HERRAMIENTAS DESARROLLO SOFTWARE PARALELO MEMORIA CPU

MEMORIA CPU

MEMORIA CPU

MEMORIA CPU

MEMORIA CPU

Figura 2.1: Modelo Básico para Paso de Mensajes Todas las unidades de proceso pueden ser origen o destino de mensajes en cualquier momento y todas pueden intercambiar datos entre sí. El enrutamiento de mensajes se le deja al sistema operativo y el número de saltos o puntos de intercomunicación por los que el mensaje debe pasar dependerán de la topología de la máquina en uso. Este sistema puede utilizarse alcanzando un rendimiento óptimo en multicomputadores y en multiprocesadores con memoria distribuida. Aunque la sobrecarga en la comunicación (latencia) en cada paso de mensaje puede ser alta normalmente hay pocas restricciones sobre la cantidad de información que pueden contener dichos mensajes. De este modo si contamos con un ancho de banda amplio el paso de mensajes puede ser un método muy efectivo para transmitir grandes bloques de datos de entre los procesadores. Sin embargo para minimizar la necesidad de costosas operaciones de paso de mensajes los datos deben estar distribuidos entre los procesadores, de modo que el conjunto de datos referenciados por cada procesador esté en su memoria local. A ésto se le conoce como distribución de datos (“data layout”). Una gran ventaja del paso de mensajes reside en su elevada portabilidad, puesto que por lo general consiste en el protocolo de comunicaciones estándar de la red más las rutinas de sincronización y comunicación de procesos, que se ejecutan sobre dicho protocolo. Además dicho modelo puede usarse en una red de computadores heterogénea. 2.1.1.1.

Comunicación mediante Sockets

En un sistema multitarea como Linux los sockets son la base para la comunicación mediante paso de mensajes. Un socket es un punto de comunicación que se comunica con otro socket para enviarle mensajes. Son bidireccionales, los hay de varios tipos y nos permiten comunicarnos con un proceso que esté en otro ordenador o en el mismo. Cuando queremos recibir datos por un socket creamos uno y “escuchamos” por él hasta que nos lleguen datos. En caso de querer enviar datos lo que hacemos es crear un socket, cumplimentar los datos de la dirección de destino y enviar los datos al otro socket a través del nuestro. Por consiguiente para que dos procesos se comuniquen mediante sockets cada uno debe crear el suyo. Para transmitir datos entre nodos bajo Linux usaremos normalmente la familia de sockets AF_INET. Este tipo de sockets se usan principalmente en redes IP, como por ejemplo la extensa Internet. En estas redes los ordenadores se identifican mediante una dirección IP que es propia de cada nodo, o sea, no existen dos nodos con la misma dirección IP en una misma red. De esta manera los sockets pueden ser identificados unívocamente en toda la red. Ello es

2.1. MODELOS DE INTERACCIÓN ENTRE PROCESADORES

45

importante ya que, conociendo todos los datos necesarios, podemos ponernos en contacto con cualquier punto de comunicación de cualquier nodo de nuestra red. Los datos que identifican unívocamente a estos puntos de transmisión son: La dirección IP del nodo en donde reside el proceso que está usando ese punto de conexión. El número del puerto. El puerto es un número entero sin signo de 16 bits cuyo propósito es el de permitir que en un ordenador puedan existir 65536 puntos posibles de comunicación para cada tipo de socket AF_INET. Esto es suficiente para que no suponga un límite (en la práctica) para el número de puntos de comunicación diferentes que puede haber al mismo tiempo en un ordenador. Y el tipo de socket, dato que no reside en la información de direccionamiento, ya que es algo implícito al socket. Si usamos un socket de un tipo, éste sólo se comunicará con sockets del mismo tipo. Para referirnos a un socket usaremos la dirección de socket. Las direcciones de socket son diferentes según la familia. Llevan todos un primer parámetro que identifica la familia de socket y luego, según ésta, los datos correspondientes. En el caso de la familia de sockets para redes IP estos datos son la dirección del ordenador y el número de puerto. Los tipos de sockets de esta familia son dos, que se corresponden con los dos tipos transmisión de datos en una red de paquetes, y son los que definiremos a continuación. Datagramas (UDP) Es el modelo más sencillo y también el menos robusto. Consiste en enviar paquetes de datos a un destino determinado. Cada paquete que enviamos ha de llevar la dirección de destino y es guiado por la red de manera independiente. Estos paquetes con la dirección de destino incluida se llaman datagramas. Los datagramas tienen una longitud limitada, por lo que los datos que enviamos no pueden exceder de esa longitud. Además hay ciertos problemas derivados del hecho de que los paquetes transiten por una red, que se agravan cuanto más extensa sea ésta: Pérdida de paquetes. En el nivel de red y en los nodos de enrutamiento se pueden perder paquetes debido a congestión, problemas en la transmisión, etc. Orden de los paquetes. En una red de área extensa los paquetes atraviesan varios nodos para llegar a su destino. En estos nodos los algoritmos de enrutamiento no suelen ser estáticos. De este modo para llegar al mismo destino un paquete puede seguir diferentes rutas, debido a que en un momento dado un nodo puede decidir encaminar el paquete por un sitio y luego por otro. Esto obedece sobre todo a causas derivadas del control de la congestión (el congestionamiento de las líneas influye a la hora de determinar por cual de ellas se envía el paquete) y de la robustez del sistema (si un nodo se cae se encaminan los paquetes por otro sitio). La consecuencia es que dos paquetes que fueron enviados pueden llegar desordenados por haber seguido distintas rutas.

46

CAPÍTULO 2. HERRAMIENTAS DESARROLLO SOFTWARE PARALELO

Estos problemas no suceden si las transmisiones se realizan dentro de una red de área local, ya que no es necesario encaminar los paquetes. El protocolo de soporte sobre IP que sigue este esquema se llama UDP (“User Datagram Protocol”, Protocolo de Datagramas de Usuario) y por consiguiente hablaremos de UDP/IP. Comunicaciones Orientadas a Conexión (TCP) Consiste en realizar una conexión entre las dos partes. Tiene la desventaja de que se pierde tiempo en establecer la conexión, pero después la comunicación es fiable, ordenada y utiliza cabeceras más pequeñas. El protocolo de soporte sobre IP que sigue este esquema se denomina TCP (“Transfer Data Protocol”, Protocolo de Transferencia de Datos); hablaremos de flujos TCP/IP debido a que se establece un canal por donde los datos fluyen de manera continua y ordenada. El protocolo TCP es bastante más complejo que UDP e implementa segmentación, lo cual nos permite pasar datos de gran longitud. Dichos datos serán segmentados en partes más pequeñas, enviados conservando el orden y ensamblados en el destino.

2.1.2. Memoria Compartida La memoria compartida es otro modelo de interacción entre los procesadores que forman un sistema paralelo. Muchos sistemas con MultiProcesadores Simétricos (SMP) comparten físicamente una sola memoria entre sus procesadores, de manera que un dato escrito por un procesador en la memoria compartida puede ser accedido directamente por cualquier otro. En los sistemas en los que cada procesador tiene su propia memoria, la memoria compartida puede implementarse lógicamente convirtiendo cada referencia a memoria no local en una comunicación apropiada entre procesadores. Físicamente la memoria compartida puede tener una velocidad de transferencia de datos amplia y una latencia baja, pero sólo cuando los múltiples procesadores no intentan acceder al bus simultáneamente; así, la distribución de datos influye seriamente en el rendimiento, la utilización de la caché, etc. de manera que puede resultar complicado determinar qué distribución de datos es la mejor para un determinado sistema. Normalmente la idea esencial de este modelo consiste en identificar las regiones paralela y secuencial de un programa. La región secuencial se ejecuta en un solo procesador y la paralela en múltiples procesadores. La región paralela consistirá normalmente en múltiples hilos, cada uno ejecutándose de forma concurrente como se ilustra en la figura 2.2. Los hilos son esencialmente procesos “poco pesados” que son planificados de distinta manera a los procesos UNIX y, lo que es más importante, tienen acceso compartido a un mismo mapa de memoria. En muchos programas la identificación de las regiones paralela y secuencial puede ser sencillo, pero en otros es necesario indicar al compilador que realice la paralelización automática, lo cual hasta el momento es un método poco refinado y requiere intervención del programador para la mejora final del código. Aún así los sistemas de memoria compartida suelen ser más sencillos que los de paso de mensajes, y pueden desarrollarse más rápidamente. En todo caso el rendimiento dependerá del compilador que utilicemos. Un compilador para memoria compartida deberá generar código para creación de hilos, sincronización y acceso a los datos en memoria compartida. En comparación un compilador

2.1. MODELOS DE INTERACCIÓN ENTRE PROCESADORES

47

Hilo 1 Hilo 2 Hilo sencillo

Hilo sencillo Hilo 3 Hilo 4

Región secuencial

Región paralela

Región secuencial

Figura 2.2: Modelo Básico para Memoria Compartida para paso de mensajes es considerablemente más simple, pues consistirá sólo en un compilador base y las librerías para comunicaciones. La sincronización es un concepto altamente importante en este tipo de sistemas. La compartición de recursos globales está llena de riesgos. Por ejemplo, si dos procesos hacen uso al mismo tiempo de la misma variable global y ambos llevan a cabo tanto lecturas como escrituras sobre la variable, el orden en el que se ejecuten las lecturas y escrituras es crítico. Así surge el concepto de exclusión mutua. Dos o más procesos no pueden acceder a determinados recursos al mismo tiempo. Así, existen varias maneras de conseguir la exclusión mutua. Por un lado podemos hacerlo a nivel hardware, a través de instrucciones máquina especiales o de inhabilitación por interrupciones. También a nivel de sistema operativo, con la utilización de semáforos u otros mecanismos. A nivel de compilador contamos con la ayuda de los monitores. Como vemos existen varios mecanismos para conseguir la sincronización de los procesos en este tipo de sistemas. 2.1.2.1.

Todo Compartido Vs. Algo Compartido

Hay dos modelos fundamentales usados comúnmente en programación con memoria compartida: Todo Compartido y Algo Compartido. Ambos modelos permiten la comunicación entre procesadores mediante lecturas y escrituras de/en la memoria compartida; la diferencia consiste en que el modelo Todo Compartido ubica todos los datos en memoria compartida, mientras que el modelo Algo Compartido requiere que el usuario indique explícitamente qué datos pueden ser compartidos y cuáles son privados para un único procesador. ¿Qué modelo de datos debemos usar? Lógicamente debemos usar el modelo que mejor se adapte a nuestras necesidades, aunque muchas veces ésto es sólo cuestión de gustos. Mucha gente prefiere el modelo Todo Compartido porque no hay necesidad de identificar qué datos deben ser compartidos en el momento de su declaración... simplemente bloqueamos los accesos potencialmente conflictivos a objetos compartidos para asegurarnos de que sólo un procesador tenga acceso en un momento dado. De nuevo, ésto no es tan simple... por ello mucha gente prefiere la relativa seguridad del modelo Algo Compartido.

48

CAPÍTULO 2. HERRAMIENTAS DESARROLLO SOFTWARE PARALELO

Modelo Todo Compartido Lo mejor de este modelo es que fácilmente podemos analizar un programa secuencial existente y convertirlo incrementalmente en un programa paralelo bajo el modelo Todo Compartido. No hay necesidad de determinar qué datos deben ser accesibles por cada uno de los procesadores. En principio el principal problema de este modelo es que cualquier acción ejecutada por un procesador podría afectar a otros procesadores. El problema sale a la luz de dos maneras: Muchas librerías contienen estructuras de datos que simplemente no se pueden compartir. Por ejemplo, una convención UNIX es que la mayoría de las funciones retornan su código de error en una variable llamada errno; si dos procesos bajo el modelo Todo Compartido ejecutan varias llamadas, tendrían conflictos entre ellas porque en realidad comparten la misma variable errno. Aunque ahora existe una versión de la librería que corrige ésto, todavía existen otros muchos problemas similares en la mayoría de las librerías. Por ejemplo, a menos que sean tomadas precauciones especiales la librería X no funcionará si las llamadas son hechas por múltiples procesos bajo el modelo Todo Compartido. Normalmente en cualquier otro modelo de programación el peor caso para un programa con un puntero defectuoso o un error de segmentación es que el proceso que contiene el código erróneo muera. Incluso en este caso el núcleo podría generar un fichero que nos dé una pista de lo sucedido. En procesamiento paralelo bajo el modelo Todo Compartido es común que los accesos perdidos provoquen el fallecimiento de un proceso distinto al que contiene el error, haciendo casi imposible localizar y corregir el error. Ninguno de estos dos tipos de problemas son usuales cuando se emplea el modelo Algo Compartido, debido a que sólo los datos explícitamente marcados son compartidos. Además resulta obvio que el modelo Todo Compartido sólo funciona si todos los procesos tienen exáctamente la misma imagen de la memoria; de este modo no es posible usar el modelo Todo Compartido con diferentes imágenes del código (sólo se puede usar SPMD, no MIMD en general). El soporte más común en programación bajo el modelo Todo Compartido son las librerías de hilos. Los hilos son esencialmente procesos “poco pesados” que podrían no ser planificados de la misma manera que los procesos UNIX y, lo que es más importante, pueden tener acceso compartido a un mismo mapa de memoria. La primera librería que soportó paralelismo en SMP Linux es la ahora algo obsoleta bb_threads, una librería muy pequeña que utiliza la llamada clone() para crear nuevos procesos planificados independientemente que comparten un mismo espacio de direcciones. Los computadores SMP Linux pueden ejecutar múltiples hilos de este tipo en paralelo, ya que en este caso cada hilo es en realidad un proceso Linux completo; la desventaja es que no obtenemos la misma planificación optimizada que realizan otras librerías de hilos. Más recientemente ha sido desarrollada una versión de la librería de hilos POSIX. Esta librería, LinuxThreads, es claramente la librería preferida para ser usada bajo el modelo Todo Compartido bajo SMP Linux. Dicha librería de hilos POSIX está bien documentada. Ahora el principal problema es que la librería tiene muchos detalles por definir y acabar, de modo que LinuxThreads está todavía en proceso de desarrollo. Además tenemos el problema de

2.2. UTILIDADES DE DESARROLLO

49

que la librería POSIX se ha visto involucrada en el proceso de estandarización, de manera que tenemos que ser cuidadosos para no programar utilizando versiones obsoletas del estándar. Modelo Algo Compartido El modelo Algo Compartido en realidad significa “compartir sólo lo necesario”. Este planteamiento puede funcionar en MIMD de manera general (no sólo en SPMD) teniendo en cuenta que debemos ubicar los objetos compartidos en la misma posición de memoria para cada uno de los mapas de memoria de cada procesador. Y lo que es más importante, el modelo Algo Compartido hace más fácil la predicción y puesta a punto del rendimiento, el filtrado de errores, etc. Los únicos problemas son: Puede ser difícil saber de antemano qué necesita realmente ser compartido. La verdadera posición de los objetos en memoria compartida puede ser difícil de establecer, especialmente para los objetos ubicados en una pila. Por ejemplo, puede ser necesario ubicar explícitamente objetos compartidos en un segmento de memoria separado, requiriendo de este modo rutinas de ubicación en memoria separada e introduciendo punteros indirectos extra en cada referencia. Hoy día existen dos mecanismos muy parecidos para permitir a grupos de procesos de Linux tener espacios de memoria independientes, compartiendo sólo un pequeño segmento de memoria. Asumiendo que no hemos excluido el System V IPC en el momento de la configuración de nuestro sistema Linux, tendremos un mecanismo muy portable que ha venido a denominarse System V Shared Memory. La otra alternativa es una utilidad de mapeo de memoria cuya implementación varía ampliamente entre distintos sistemas UNIX: la llamada al sistema mmap().

2.2. Utilidades de Desarrollo 2.2.1. PVM PVM (“Parallel Virtual Machine”, Máquina Virtual Paralela) es una librería de paso de mensajes libre y portable, generalmente implementada por encima de los sockets. Está claramente establecida como el estándar de paso de mensajes para el procesamiento paralelo en clusters. PVM puede ser utilizado en monoprocesadores, máquinas SMP, así como clusters conectados por una red que soporte sockets (por ejemplo SLIP, PLIP, Ethernet, ATM, etc). De hecho, PVM funciona incluso en grupos de máquinas con diferentes tipos de procesadores, configuraciones, o diferentes tipos de red (clusters heterogéneos). Puede incluso tratar un grupo bastante amplio de máquinas conectadas a Internet como una sóla máquina paralela (una máquina virtual paralela, de ahí su nombre). Lo mejor de todo, PVM es desde hace tiempo una distribución libre (URL [14]), lo que ha llevado a muchos lenguajes de programación, librerías de aplicaciones, herramientas de programación y depuración de errores, etc. a utilizar PVM como su librería portable de paso de mensajes.

50

CAPÍTULO 2. HERRAMIENTAS DESARROLLO SOFTWARE PARALELO

El modelo de funcionamiento de PVM es simple pero muy general, y se acomoda a una amplia variedad de estructuras de programas de aplicación. La interfaz de programación es muy sencilla, permitiendo que las estructuras de los programas sencillos sean implementadas de manera intuitiva. El usuario escribe su aplicación como un conjunto de tareas que cooperan. Dichas tareas acceden a los recursos de PVM a través de una librería de funciones con una interfaz estándar. Estas funciones permiten la inicialización y finalización de las tareas a través de la red, así como la comunicación y la sincronización entre dichas tareas. Las operaciones de comunicación utilizan estructuras predefinidas, tanto las encargadas del envío y recepción de datos como aquellas más complejas (sincronización en barrera, suma global, broadcast, etc.). Debido a su portabilidad, su disponibilidad y su simple pero completa interfaz de programación, el sistema PVM ha ganado una amplia aceptación en la comunicad de cálculo científico de alto rendimiento.

2.2.2. MPI MPI (“Message Passing Interface”, Interfaz de Paso de Mensajes) 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. Aunque la interfaz no cambie, puede implementarse tanto en sistemas que utilicen paso de mensajes, como sistemas de memoria compartida. La primera versión de MPI fué desarrollada en 1993-1994 por un grupo de investigadores al servicio de la industria, el gobierno y el sector académico. Debido al apoyo recibido MPI es relativamente el nuevo estándar para la programación de procesadores paralelos basado en el paso de mensajes, tomando el testigo de PVM. Sin embargo existen frecuentes dudas y discusiones por parte de los usuarios acerca de cuál es el estándar a utilizar. Así pues haremos un resumen de las diferencias más características entre los sistemas más utilizados, PVM y MPI: Entorno de Ejecución: Simplemente PVM tiene uno definido, mientras que MPI no especifica cómo debe ser implementado. Así el inicio de la ejecución de un programa PVM será realizado de manera idéntica en cualquier plataforma, mientras que para MPI depende de la implementación que estemos utilizando. Soporte para Clusters Heterogéneos: PVM fué desarrollado para aprovechar ciclos de CPU de estaciones de trabajo ociosas, por lo que maneja de manera directa mezclas heterogéneas de máquinas y sistemas operativos. En contraste MPI asume que su principal objetivo son los MPPs y los clusters dedicados de estaciones de trabajo casi idénticas. Sin embargo, dependiendo de la implementación que utilicemos, tendremos un soporte más o menos adecuado. Amplitud del Campo de Estudio: PVM evidencia una unidad de propósito que MPI no tiene. Como veremos en el capítulo 3 la especificación MPI-1 centra su atención en el modelo de paso de mensajes, al igual que PVM. Sin embargo la especificación MPI-2 incluye muchas características que van

2.2. UTILIDADES DE DESARROLLO MPI_Send()

51 MPI_Recv()

MPI

MPI

SO

SO

Figura 2.3: Esquema Básico Utilización MPI más allá del modelo de paso de mensajes, como el acceso paralelo a ficheros de E/S o el acceso a memoria remota, entre otros muchos ejemplos. Diseño de Interfaz de Usuario: MPI fué diseñado después de PVM, y claramente aprendió de él. MPI ofrece una interfaz más clara y eficiente, con manejo de buffers y abstracciones de alto nivel que permiten definir las estructuras de datos a ser transmitidas por los mensajes. Importancia del Estándar: El hecho de que MPI sea respaldado por un estándar formal ampliamente apoyado significa que el uso de MPI es, en muchas instituciones, cuestión de política. MPI no está concebido para ser una infraestructura software aislada y autosuficiente para ser usada en procesamiento distribuido. MPI no necesita planificación de procesos, herramientas de configuración de la plataforma a usar, ni soporte para E/S. Como resultado MPI es implementado normalmente como interfaz de comunicaciones, utilizando las facilidades ofrecidas por el sistema que vayamos a usar, tal como se indica en la figura 2.3 (comunicación vía sockets, operaciones de memoria compartida, etc). Éste escenario es ideal para que los programas PVM sean portados a MPI, de manera que se aproveche el alto rendimiento de comunicación que ofrecen algunas compañías en sus arquitecturas. Dado que éste es el estándar en el que nos basaremos para el desarrollo del presente documento, en el capítulo 3 haremos una descripción más elaborada de sus características.

2.2.3. P4 El sistema p4 es una librería de macros y funciones desarrollada por el Argonne National Laboratory 1 destinadas a la programación de una gran variedad de máquinas paralelas. El sistema p4 soporta tanto el modelo de memoria compartida (basado en monitores) como el modelo de memoria distribuida (basado en paso de mensajes). Para el modelo de memoria compartida, p4 proporciona un conjunto de monitores así como funciones desarrolladas para crearlos y manipularlos; un monitor es un mecanismo de sincronización de procesos en sistemas con memoria compartida. Para el modelo de memoria distribuida, p4 proporciona operaciones de envío y recepción, y un método de administración 1

Desarrollador de la implementación MPICH, apéndice A

52

CAPÍTULO 2. HERRAMIENTAS DESARROLLO SOFTWARE PARALELO

de procesos basado en un fichero de configuración que describe la estructura de los grupos y procesos. Dicho fichero especifica el nombre del servidor, el fichero que será ejecutado en cada máquina, el número de procesos que serán iniciados en cada servidor (principalmente para sistemas multiprocesador) e información auxiliar. Un ejemplo de fichero de configuración es: # start one eslave on each of sun2 and sun3 local 0 sun2 1 /home/mylogin/pupgms/sr_test sun3 1 /home/mylogin/pupgms/sr_test Dos cosas son notables en lo que se refiere al mecanismo de administración de los procesos en p4. Primero, existe la noción de procesos maestros y procesos esclavos, y pueden formarse jerarquías multinivel para implementar el denominado modelo de cluster de procesamiento. Segundo, el principal modo de creación de procesos es estático, a través del fichero de configuración; la creación dinámica de procesos es posible sólo mediante procesos creados estáticamente que deben invocar una función p4 que expande un nuevo proceso en la máquina local. A pesar de estas restricciones una gran variedad de paradigmas de aplicación pueden ser implementados en el sistema p4 de una manera bastante sencilla. El paso de mensajes es conseguido en el sistema p4 a través del uso de primitivas send y receive tradicionales, con casi los mismos parámetros que los demás sistemas de paso de mensajes. Algunas variantes han sido proporcionadas por cuestiones semánticas, como el intercambio heterogéneo y las transferencias bloqueantes o no bloqueantes. Sin embargo una proporción significativa de la administración del buffer y su carga se le deja al usuario. Aparte del paso de mensajes básico, p4 ofrece también una variedad de operaciones globales incluyendo broadcast, máximo y mínimo globales, y sincronización por barrera.

2.2.4. Express En contraste con lo que sucede con otros sistemas de procesamiento paralelo descritos en esta sección, Express es una colección de herramientas que individualmente dirigen varios aspectos del procesamiento concurrente. Dicho paquete software es desarrollado y comercializado por Parasoft Corporation, una compañía creada por algunos miembros del proyecto de procesamiento concurrente de Caltech. La filosofía de Express se basa en comenzar con la versión secuencial de un algoritmo y aplicarle un ciclo de desarrollo recomendado, para así llegar a la versión paralela de dicho algoritmo de manera óptima. Los ciclos de desarrollo típicos comienzan con el uso de la herramienta VTOOL, una aplicación gráfica que permite mostrar por pantalla el progreso de los algoritmos secuenciales dinámicamente. Puede mostrar actualizaciones y referencias a estructuras de datos individuales, con la intención de demostrar la estructura de los algoritmos y proporcionar la información necesaria para su paralelización. En relación con este programa tenemos la herramienta FTOOL, que proporciona un análisis en profundidad de los programas. Dicho análisis incluye información acerca del uso de variables, la estructura de flujo de control, etc. FTOOL opera tanto en las versiones secuenciales de los algoritmos como en las paralelas. Una tercera herramienta llamada ASPAR es

2.2. UTILIDADES DE DESARROLLO

53

usada entonces; esta herramienta es un paralelizador automático que convierte programas secuenciales escritos en C o Fortran en sus versiones paralelas o distribuidas, usando los modelos de programación Express. El núcleo del sistema Express es un conjunto de librerías de comunicación, E/S y gráficos paralelos. Las primitivas de comunicación son parecidas a las encontradas en otros sistemas de paso de mensajes e incluyen una variedad de primitivas para realizar operaciones globales y de distribución de datos. Las funciones de E/S extendida permiten la E/S paralela. Un conjunto de funciones similar es proporcionado para mostrar gráficos de múltiples procesos concurrentes. Express contiene además la herramienta NDB, un depurador paralelo que utiliza comandos basados en la popular interfaz dbx.

2.2.5. Linda Linda es un modelo concurrente de programación fruto de la evolución de un proyecto de investigación de la Universidad de Yale. El concepto principal en Linda es el espacio de tuplas, una abstración a través de la cual se comunican los procesos. Este tema central de Linda ha sido propuesto como paradigma alternativo a los dos métodos tradicionales de procesamiento paralelo: el basado en memoria compartida, y el basado en paso de mensajes. El espacio de tuplas es esencialmente una abstracción de la memoria compartida/distribuida, con una diferencia importante: los espacios de tuplas son asociativos. También existen otras distinciones menores. Las aplicaciones utilizan el modelo Linda introduciendo en los programas secuenciales estructuras que manipulan el espacio de tuplas. Desde el punto de vista de las aplicaciones, Linda es un conjunto de extensiones para lenguajes de programación que facilitan la programación paralela. Proporciona una abstracción de la memoria compartida que no requiere la existencia de hardware específico que comparta memoria físicamente. El término Linda se refiere a menudo a implementaciones específicas software que soportan el modelo de programación Linda. Este tipo de software establece y mantiene espacios de tuplas, siendo utilizado en conjunción con librerías que interpretan y ejecutan primitivas Linda. Dependiendo del entorno (mutiprocesadores con memoria compartida, sistemas de paso de mensajes, etc.) el macanismo de espacio de tuplas será implementado utilizando diferentes técnicas con varios grados de eficiencia. Recientemente ha sido propuesto un nuevo esquema relacionado con el proyecto Linda. Este esquema, denominado Pirhana, propone un planteamiento revolucionario en el procesamiento concurrente: los recursos computacionales (vistos como agentes activos) eligen a los procesos basándose en su disponibilidad y conveniencia. Este esquema puede ser implementado en múltiples plataformas y es conocido como Sistema Pirhana o Sistema Linda-Pirhana.

54

CAPÍTULO 2. HERRAMIENTAS DESARROLLO SOFTWARE PARALELO

Parte II

Guía MPI

55

Capítulo 3

El Estándar MPI MPI (“Message Passing Interface”, Interfaz de Paso de Mensajes) 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. Dicha librería puede ser utilizada por una amplia variedad de usuarios para implementar programas que utilicen paso de mensajes. Desde la finalización de su primera versión en Junio de 1994, MPI ha sido ampliamente aceptado y usado. Existen implementaciones muy estables y eficientes, incluyendo algunas de dominio público. Además dichas implementaciones están disponibles para un amplia variedad de máquinas. Gracias a ello MPI ha alcanzado uno de sus principales objetivos: darle credibilidad al procesamiento paralelo. Ahora las companías y los investigadores tienen una manera sencilla y segura para desarrollar programas paralelos portables de paso de mensajes.

3.1. Origen El paso de mensajes es un paradigma de programación ampliamente utilizado en computadores paralelos, especialmente en aquellas con memoria distribuida. Aunque existen muchas variantes, el concepto básico de procesos comunicándose mediante mensajes está muy consolidado. Durante los años anteriores a la aparición del estándar MPI se percibía un progreso sustancial en proyectar aplicaciones importantes en este paradigma. De hecho, cada compañía había implementado ya su propia variante. Más recientemente algunos sistemas de dominio público habían demostrado que el paso de mensajes podía implementarse eficientemente de manera portable.

Figura 3.1: Logo MPI 57

58

CAPÍTULO 3. EL ESTÁNDAR MPI

Por todo ello comprendemos que éste era el momento apropiado para definir tanto la sintaxis como la semántica de una librería estándar de funciones que fuera útil a una amplia variedad de usuarios y que pudiera implementarse eficientemente en una amplia gama de computadores. Y de esa idea nació el estándar MPI. Los diseñadores de MPI pretendieron incorporar la mayoría de las características más atractivas de los sistemas existentes de paso de mensajes, antes que seleccionar uno de ellos y adoptarlo como el estándar. Así, en su origen MPI estuvo muy influenciado por el trabajo del Centro de Investigación T.J.Watson de IBM, el sistema NX/2 de Intel, Express, Vertex de nCUBE y PARMACS. Otras contribuciones importantes fueron las realizadas por Zipcode, Chimp, PVM, Chameleon y PICL. Los diseñadores de MPI identificaron algunos defectos críticos de los sistemas de paso de mensajes existentes en áreas como la composición de datos complejos, la modularidad y las comunicaciones seguras. Ésto permitió la introducción de nuevas características en MPI.

3.2. Historia El esfuerzo de estandarización de MPI involucró a unas 60 personas procedentes de 40 organizaciones, principalmente de EEUU y Europa. La mayoría de las principales compañías de computadores paralelos del momento estuvieron involucradas en MPI, así como investigadores provenientes de universidades, laboratorios de gobierno y la industria. El proceso de estandarización comenzó con el Seminario sobre Estándares de Paso de Mensajes en Entornos de Memoria Distribuida, patrocinado por el Centro de Investigaciones sobre Procesamiento Paralelo, mantenido durante los días 29-30 de Abril de 1992 en Williansburg, Virginia (EEUU). En este seminario se discutieron las características esenciales que debía tener una interfaz estándar de paso de mensajes y se estableció un grupo de trabajo para continuar con el proceso de estandarización. Un borrador preliminar, conocido como MPI1, fué propuesto por Dongarra, Hempel, Hey y Walker en Noviembre de 1992 y una versión revisada fué completada en Febrero de 1993. MPI1 abarcaba las características principales que fueron identificadas en el seminario de Williansburg como necesarias en un estándar de paso de mensajes. Dado que fué generado para promover la discusión, este primer borrador se centró principalmente en las comunicaciones punto-a-punto. Aunque tocaba muchos asuntos referentes a la estandarización, no incluía operaciones colectivas ni tenía en cuenta la utilización de hilos. En Noviembre de 1992 una reunión del grupo de trabajo de MPI tuvo lugar en Minneapolis, en la cual se decidió hacer el proceso de estandarización de una manera más formal, adoptando la organización y los procedimientos del “High Performance Fortran Forum” (Foro Fortran de Alto Rendimiento). Fueron formados subcomités para cada una de las principales áreas que componen el estándar, y se estableció un foro de discusión vía e-mail para cada una de ellas. De esta manera quedó conformado el Foro MPI (URL [8]), a cuyo cargo quedaría el proceso de estandarización de MPI. En dicha reunión se propuso el objetivo de presentar un borrador del estándar MPI en el otoño de 1993. Para conseguirlo el Foro MPI mantuvo reuniones cada 6 semanas durante los primeros 9 meses de 1993, presentando el borrador del estándar MPI en la conferencia Supercomputing ’93 en Noviembre de 1993. Después de un período de comentarios públicos,

3.3. OBJETIVOS

59

que resultaron en algunos cambios en MPI, la versión 1.0 de MPI fué presentada en Junio de 1994. A principios de Marzo de 1995 el Foro MPI empezó a reunirse de nuevo para considerar correcciones y extensiones al documento original del estándar MPI. El primer producto fruto de estas deliberaciones fué la versión 1.1 de MPI, presentada en Junio de 1995. En Julio de 1997 aparecen al mismo tiempo la versión 1.2 de MPI y la especificación MPI2. La versión 1.2 de MPI contiene correcciones y clarificaciones referentes a la versión 1.1. Sin embargo MPI-2 añade nuevos elementos al estándar MPI-1, definiendo la versión 2.0 de MPI. Todavía hoy continúan las discusiones acerca de las áreas hacia las cuales podría ser útil expandir el estándar MPI; sin embargo en muchas de ellas es necesario obtener más experiencia y realizar más discusiones. De todo ello se encarga un documento separado, el MPI “Journal Of Development” (Periódico de Desarrollo), que no forma parte de la especificación MPI-2. Y por supuesto el Foro MPI sigue abierto a las aportaciones que puedan realizar los usuarios del estándar, con el objetivo de mantenerlo y desarrollarlo.

3.3. Objetivos La finalidad de MPI, de manera concisa, es desarrollar un estándar para escribir programas de paso de mensajes que sea ampliamente utilizado. Para ello la interfaz debe establecer un estándar práctico, portable, eficiente, escalable, formal y flexible.

Objetivos Principales Portabilidad El principal objetivo de MPI, como ocurre en la mayoría de los estándares, es conseguir un alto grado de portabilidad entre diferentes máquinas. Esta portabilidad sería parecida a la que se consigue con lenguajes de programación como Fortran. De esta manera el mismo código fuente de paso de mensajes debería poder ser ejecutado en una variedad de máquinas tan grande como la soportada por las distintas implementaciones de MPI, aunque pueda ser necesaria una puesta a punto para obtener la máxima ventaja de las características de cada sistema. A pesar de que el paso de mensajes muchas veces es considerado algo propio de los sistemas paralelos de memoria distribuida, el mismo código podría ser ejecutado en un sistema paralelo de memoria compartida. Puede ejecutarse en clusters o incluso en un conjunto de procesos ejecutándose en una misma máquina. El hecho de saber que existen implementaciones de MPI eficientes para una amplia variedad de sistemas nos da cierto grado de flexibilidad en el desarrollo del código, la búsqueda de errores y la elección de la plataforma que finalmente utilizaremos. Heterogeneidad Otro tipo de compatibilidad ofrecido por MPI es su capacidad para ejecutarse en sistemas heterogéneos de manera transparente. Así pues, una implementación MPI debe ser capaz de extender una colección de procesos sobre un conjunto de sistemas con arquitecturas diferentes, de manera que proporcione un modelo de computador virtual que oculte las diferencias en

60

CAPÍTULO 3. EL ESTÁNDAR MPI

las arquitecturas. De este modo el usuario no se tiene que preocupar de si el código está enviando mensajes entre procesadores de la misma o distinta arquitectura. La implementación MPI hará automáticamente cualquier conversión que sea necesaria y utilizará el protocolo de comunicación adecuado. Sin embargo MPI no prohibe implementaciones destinadas a un único y homogéneo sistema, así como tampoco ordena que distintas implementaciones MPI deban tener la capacidad de interoperar. En definitiva, los usuarios que quieran ejecutar sus programas en sistemas heterogéneos deberán utilizar implementaciones MPI diseñadas para soportar heterogeneidad. Rendimiento La portabilidad es un factor importante, pero el estándar no conseguiría una amplia utilización si se consiguiera dicha portabilidad a expensas del rendimiento. Por ejemplo, el lenguaje Fortran es comúnmente usado por encima de los lenguajes ensambladores porque los compiladores casi siempre ofrecen un rendimiento aceptable comparado con la alternativa no portable que representa el lenguaje ensamblador. Un punto crucial es que MPI fué cuidadosamente diseñado de manera que permite implementaciones eficientes. Las elecciones en el diseño parecen haber sido hechas correctamente, dado que las implementaciones MPI están alcanzando un alto rendimiento en una amplia variedad de plataformas; de hecho el rendimiento alcanzado en dichas implementaciones es comparable al de los sistemas presentados por las compañías, los cuales están diseñados para arquitecturas específicas y tienen menor capacidad de portabilidad. Un objetivo importante de diseño en MPI fué el de permitir implementaciones eficientes para máquinas de diferentes características. Por ejemplo, MPI evita cuidadosamente especificar la manera en que las operaciones tienen lugar. Sólo especifica qué hace una operación lógicamente. Como resultado MPI puede ser fácilmente implementado en sistemas que tienen buffer de mensajes en el proceso emisor, en el receptor, o que no tienen buffers para nada. Las implementaciones pueden beneficiarse de las ventajas que ofrecen los subsistemas de comunicación de varias máquinas a través de sus características específicas. En máquinas con coprocesadores de comunicación inteligentes podemos cargar sobre dichos coprocesadores la mayoría del procesamiento relativo al protocolo de paso de mensajes. En otros sistemas la mayoría del código de comunicación será ejecutada por el procesador principal. Otro ejemplo es el uso de objetos opacos en MPI; por ejemplo los elementos grupo y comunicador son objetos opacos. Desde un punto de vista práctico ésto significa que los detalles de su representación interna dependen de la implementación MPI particular, y como consecuencia el usuario no puede acceder directamente a ellos. En vez de ello el usuario accede a un manejador que referencia al objeto opaco, de manera que dichos objetos opacos son manipulados por funciones MPI especiales. De esta manera cada implementación es libre de hacer lo mejor en determinadas circunstancias. Otra elección de diseño importante para la eficiencia es la manera de evitar el trabajo innecesario. MPI ha sido cuidadosamente diseñado de modo que no sea necesaria demasiada información extra con cada mensaje, ni complejas codificaciones o decodificaciones sobre las cabeceras de dichos mensajes. MPI también evita computaciones extra o tests en funciones críticas que degraden el rendimiento. Otra manera de minimizar el trabajo es reducir la repetición de computaciones previas. MPI proporciona esta capacidad a través de construcciones

3.3. OBJETIVOS

61

como peticiones de comunicación persistente o los atributos de los comunicadores. El diseño de MPI evita la necesidad de operaciones extra de copia o almacenamiento sobre los datos: en la mayoría de los casos los datos son llevados directamente de la memoria de usuario a la red, y son recibidos directamente de la red a la memoria receptora. MPI ha sido diseñado para reducir la sobrecarga en la comunicación producida por el procesamiento, utilizando agentes de comunicación inteligentes y ocultando latencias en la comunicación. Ésto se ha logrado usando llamadas no bloqueantes, que separan el inicio de la comunicación de su final. Escalabilidad La escalabilidad es otro objetivo importante del procesamiento paralelo. La escalabilidad de un sistema es su capacidad para responder a cargas de trabajo crecientes. De este modo los programas MPI deben mantener su nivel de rendimiento aunque incrementemos el número de procesos a ejecutar. MPI permite o soporta la escalabilidad a través de algunas de sus características de diseño. Por ejemplo, una aplicación puede crear subgrupos de procesos que, en turnos, puedan ejecutar operaciones de comunicación colectiva para limitar el número de procesos involucrados. Formalidad MPI, como todos los buenos estándares, es valioso debido a que define el comportamiento de las implementaciones de manera concisa. Esta característica libera al programador de tener que preocuparse de aquellos problemas que puedan aparecer. Un ejemplo de ello es la garantía de seguridad en la transmisión de mensajes que ofrece MPI. Gracias a esta característica el usuario no necesita comprobar si los mensajes son recibidos correctamente.

Resumen de Objetivos Diseñar una interfaz para la programación de aplicaciones. La interfaz debe ser diseñada para que pueda ser implementada en la mayoría de las plataformas, sin necesidad de cambios importantes en la comunicación o el software del sistema. Permitir implementaciones que puedan ser utilizadas en entornos heterogéneos. Permitir una comunicación eficiente. Asumir una interfaz de comunicación fiable: el usuario no debe preocuparse por los fallos en la comunicación. La semántica de la interfaz debe ser independiente del lenguaje. La interfaz debe permitir la utilización de hilos. Proporcionar extensiones que añadan más flexibilidad.

CAPÍTULO 3. EL ESTÁNDAR MPI

62

3.4. Usuarios El estándar MPI está pensado para ser utilizado por todo aquel que pretenda desarrollar programas de paso de mensajes codificados en Fortran 77 y C. Ésto incluye programadores de aplicaciones individuales, desarrolladores de software para máquinas paralelas y creadores de entornos y herramientas. Para que esta amplia audiencia lo considere atractivo, el estándar debe proporcionar al usuario básico una interfaz simple y fácil de manejar, que no impida el uso de las operaciones de alto rendimiento disponibles en máquinas avanzadas.

3.5. Plataformas El atractivo del paradigma de paso de mensajes proviene al menos en parte de su portabilidad. Los programas expresados de esta manera podrían ser ejecutados en multicomputadores, multiprocesadores o combinaciones de ambos. Además es posible realizar implementaciones basadas en memoria compartida. El paradigma no queda obsoleto al combinar arquitecturas de memoria distribuida con arquitecturas de memoria compartida, o al incrementar la velocidad de la red. Debe ser a la vez posible y útil implementar dicho estándar en una gran variedad de máquinas, incluyendo dichas “máquinas” que se componen de colecciones de otras máquinas, paralelas o no, conectadas por una red de comunicaciones. La interfaz es apropiada para su uso en programas MIMD y SPMD. Aunque no proporciona un soporte explícito para la ejecución de hilos la interfaz ha sido diseñada de manera que no perjudique su uso. MPI proporciona muchas características encaminadas a mejorar el rendimiento en computadores paralelos con hardware de comunicación especializado entre procesadores. De este modo es posible realizar implementaciones nativas MPI de alto rendimiento para este tipo de máquinas. Al mismo tiempo existen implementaciones MPI que utilizan los protocolos estándares de comunicación entre procesadores de Unix, las cuales proporcionan portabilidad a los clusters y redes heterogéneas.

3.6. Versiones El estándar MPI se divide básicamente en dos especificaciones, MPI-1 y MPI-2. La siguiente clasificación muestra el nivel de compatibilidad con MPI que posee una implementación dada: Mantener compatibilidad con la especificación MPI-1 significa ser compatible con la versión 1.2 de MPI. Mantener compatibilidad con la especificación MPI-2 significa proporcionar toda la funcionalidad definida por la especificación MPI-2. En todo caso la compatibilidad hacia atrás está preservada. De esta manera un programa MPI1.1 válido será un programa MPI-1.2 válido y un programa MPI-2 válido; un programa MPI1.2 válido será un programa MPI-2 válido.

3.6. VERSIONES

63

3.6.1. MPI-1 Las versiones 1.0, 1.1 y 1.2 del estándar MPI se engloban en la especificación MPI-1. Dicha especificación centra su atención en el modelo de paso de mensajes. A continuación mostramos una lista con los elementos contenidos en dicha especificación, y aquellos que quedan fuera de ella. Elementos Incluidos Comunicaciones punto a punto Operaciones colectivas Grupos de procesos Contextos de comunicación Topologías de procesos Administración del entorno Enlaces con Fortran 77 y C Interfaz para la creación de perfiles de ejecución Elementos No Incluidos Operaciones de memoria compartida Operaciones ya soportadas por el sistema operativo de manera estandarizada durante la adopción de MPI; por ejemplo, manejadores de interrupción o ejecución remota Herramientas para la construcción de programas Facilidades para la depuración de errores Soporte específico para hilos Soporte para planificación y creación de procesos Funciones de E/S paralela Como vemos MPI-1 está diseñado para aprovechar todas las facilidades ofrecidas por el sistema que vayamos a usar, tanto aquellas pertenecientes al sistema de comunicación (operaciones de memoria compartida, comunicación vía sockets, etc.) como las relativas al entorno de programación (herramientas para la construcción de programas, facilidades para la depuración de errores, etc). Como resultado MPI es implementado normalmente como interfaz de comunicaciones, utilizando dichas facilidades ofrecidas por el sistema. Existen muchas características que fueron consideradas y no se incluyeron en MPI-1. Ésto ocurrió por algunas razones: las restricciones de tiempo que se propuso el Foro MPI en acabar la especificación; el sentimiento de no tener suficiente experiencia en algunos de los

CAPÍTULO 3. EL ESTÁNDAR MPI

64

campos; y la preocupación de que el añadir más características podría retrasar la aparición de implementaciones. De todas maneras las características no incluidas siempre pueden ser añadidas como extensiones en implementaciones específicas, como es el caso de la extensión MPE dentro de la implementación MPICH (sección A.7).

3.6.2. MPI-2 La especificación MPI-2 es básicamente una extensión a MPI-1 que añade nuevos elementos al estándar. La versión 2.0 de MPI pertenece a la especificación MPI-2. Entre las nuevas funcionalidades que se añaden destacan las siguientes: Administración y Creación de Procesos Comunicaciones Unilaterales E/S Paralela Operaciones Colectivas Extendidas Enlaces con Fortran 90 y C++ La razón por la cual se creó la especificación MPI-2 fué la demanda por parte de los usuarios y desarrolladores de nuevas características en el estándar. De todos modos MPI-2 sólo añade nuevos elementos a MPI-1, pero no lo modifica.

3.7. Implementaciones Desde que se completó la primera versión del estándar en 1994 un gran número de implementaciones MPI han sido puestas a disposición de los usuarios. Esto incluye tanto algunas implementaciones portables e independientes como aquellas que han sido desarrolladas y optimizadas por las principales compañías de computadores paralelos. La alta calidad de dichas implementaciones ha sido un punto clave en el éxito de MPI. A continuación destacamos las tres implementaciones de dominio público más importantes que pueden ser utilizadas en clusters de sistemas Linux: MPICH (URL [9]) es sin duda la implementación más importante de MPI. Muchas implementaciones comerciales desarrolladas por las grandes compañías de computadores paralelos se basan en ella. La primera versión de MPICH fué escrita durante el proceso de estandarización de MPI, siendo finalmente presentada al mismo tiempo que la versión 1.0 de MPI. De hecho las experiencias de los autores de MPICH se convirtieron en una gran ayuda para el Foro MPI en el proceso de desarrollo del estándar. Su portabilidad es enorme y su rendimiento elevado. Posee compatibilidad total con MPI-1 e implementa muchos elementos de MPI-2. En el apéndice A se analizan de manera detenida sus características y se informa sobre su instalación, configuración y manejo. LAM (URL [6]) fué desarrollada originalmente en el Centro de Supercómputo de Ohio antes de que el estándar MPI fuera presentado. Cuando MPI apareció, LAM adoptó

3.7. IMPLEMENTACIONES

65

el estándar. LAM no sólo consiste en la librería MPI, si no que además contiene herramientas de depuración y monitorización. Ha sido optimizada para funcionar con clusters heterogéneos de sistemas Unix; sin embargo es muy portable, siendo utilizada en una amplia variedad de plataformas Unix, desde estaciones de trabajo a supercomputadores. LAM posee compatibilidad total con MPI-1 e implementa muchos elementos de MPI-2. CHIMP (URL [1]) fué desarrollada en el Centro de Cómputo Paralelo de Edimburgo. Como LAM, CHIMP comenzó como una infraestructura independiente de paso de mensajes que luego evolucionó hacia una implementación MPI. CHIMP es conocida principalmente por haber sido utilizada como versión optimizada de MPI para los CRAY T3D y T3E. CHIMP es portable, pudiendo ser utilizada en estaciones de trabajo de Sun, SGI, DEC, IBM y HP, en plataformas Meiko y en el Fujitsu AP 1000.

66

CAPÍTULO 3. EL ESTÁNDAR MPI

Capítulo 4

Conceptos Básicos Todos los programas MPI comparten una serie de características. La inicialización y finalización del entorno de ejecución se llevan a cabo mediante funciones que explicaremos en este capítulo. También analizaremos los métodos para identificar los procesos en ejecución. Por otro lado estudiaremos funciones para informarnos de dónde está ubicado cada proceso y el momento temporal en que nos encontramos, y explicaremos el problema de la E/S en procesadores paralelos. Para ejemplificar todo ésto implementaremos un sencillo programa que envía un mensaje de saludo e indica el número de procesos en ejecución.

4.1. Algoritmo ¡Hola Mundo! Basándonos en el primer programa que muchos de nosotros vimos en C expondremos una variante que hará uso de múltiples procesos. En MPI los procesos implicados en la ejecución de un programa paralelo se identifican por una secuencia de enteros no negativos. Si hay C procesos ejecutando un programa, éstos tendrán los identificadores DFE:1)EBGBGBG@EHC/I1 . El siguiente programa hace que el proceso 0 (encargado de la E/S, sección 4.4) imprima un mensaje de saludo e informe del número de procesos en ejecución, así como del tiempo empleado en el procesamiento. Los detalles sobre la compilación y ejecución de este programa dependen del sistema que estemos usando. De este modo debemos conocer cómo compilar y ejecutar programas paralelos que usen MPI. En la sección A.5 explicamos cómo compilarlo bajo la implementación MPICH, y en la sección A.6 se habla sobre la ejecución de programas MPI. Cuando el programa es compilado y ejecutado con dos procesos, la salida debería ser de la siguiente manera: Proceso 0 en linux.local Encargado de la E/S ¡Hola Mundo! Numero Procesos: 2 Tiempo Procesamiento: 0.000065 Si lo ejecutamos con cuatro procesos la salida sería: Proceso 0 en linux.local Encargado de la E/S 67

CAPÍTULO 4. CONCEPTOS BÁSICOS

68 ¡Hola Mundo! Numero Procesos: 4 Tiempo Procesamiento: 0.034216

Aunque los detalles de qué ocurre cuando el programa es ejecutado varían de una máquina a otra, lo esencial es lo mismo en todos los sistemas, a condición de que ejecutemos un proceso en cada procesador. 1.

El usuario manda una directiva al sistema operativo que crea una copia del programa ejecutable en cada procesador.

2.

Cada procesador comienza la ejecución de su copia del ejecutable.

3.

Diferentes procesos pueden ejecutar diferentes instrucciones bifurcando el programa a través de condicionantes. Dichos condicionantes suelen basarse, como veremos, en el identificador del proceso.

4.2. Programas MPI en General Todos los programas escritos en MPI deben contener la directiva de preprocesador #include “mpi.h” El fichero ‘mpi.h’ contiene las definiciones, macros y prototipos de función necesarios para compilar los programas MPI. Antes de que podamos llamar a cualquier otra función MPI debemos hacer una llamada a MPI_Init(); esta función sólo debe ser llamada una vez. Sus argumentos son punteros a los parámetros de la función main(), argc y argv. Dicha función permite al sistema hacer todas la configuraciones necesarias para que la librería MPI pueda ser usada. Después de que el programa haya acabado de utilizar la librería MPI debemos hacer una llamada a MPI_Finalize(). Esta función limpia todos los trabajos no finalizados dejados por MPI (por ejemplo, envíos pendientes que no hayan sido completados, etc.). Así, un programa MPI típico tiene la siguiente composición: . . . #include “mpi.h” . . . main(int argc, char** argv){ . . . /*Ninguna llamada a función MPI anterior a esta*/ MPI_Init(&argc, &argv); . . . MPI_Finalize(); /*Ninguna llamada a función MPI posterior a esta*/ . . . }/*main*/

4.3. INFORMÁNDONOS DEL RESTO DEL MUNDO

69

4.3. Informándonos del Resto del Mundo MPI ofrece la función MPI_Comm_rank(), la cual retorna el identificador de un proceso en su segundo argumento. Su sintaxis es:

int MPI_Comm_rank(MPI_Comm comunicador, int* identificador) El primer argumento es el comunicador. Esencialmente un comunicador es una colección de procesos que pueden enviarse mensajes entre sí. Normalmente para diseñar programas básicos el único comunicador que necesitaremos será MPI_COMM_WORLD. Está predefinido en MPI y consiste en todos los procesos que se ejecutan cuando el programa comienza. Muchas de las construcciones que empleamos en nuestros programas dependen también del número de procesos que se ejecutan. MPI ofrece la función MPI_Comm_size() para determinar dicho número de procesos. Su primer argumento es el comunicador. En el segundo argumento retorna el número de procesos pertenecientes a dicho comunicador. Su sintaxis es: int MPI_Comm_size(MPI_Comm comunicador, int* numprocs)

4.4. El Problema de la Entrada/Salida En nuestros algoritmos asumimos que el proceso 0 puede escribir en la salida estándar (la ventana del terminal). Prácticamente todos los procesadores paralelos proporcionan este método de E/S. De hecho la mayoría de ellos permiten a todos los procesos tanto leer de la entrada estándar como escribir en la salida estándar. Sin embargo la dificultad aparece cuando varios procesos están intentando ejecutar operaciones de E/S simultáneamente. Para comprender ésto expondremos un ejemplo. Supongamos que diseñamos un programa de manera que cada proceso intente leer los  valores , J y K añadiendo la siguiente instrucción: scanf(“ %d %d %d”, &a, &b, &c); Además supongamos que ejecutamos el programa con dos procesos y que el usuario introduce: 10 20 30 ¿Qué ocurre? ¿Obtienen ambos procesos los datos? ¿Lo hace uno sólo? O lo que es peor, ¿obtiene el proceso 0 el número 10 y el 20 mientras que el proceso 1 obtiene el 30? Si todos los procesos obtienen los datos, ¿qué ocurre cuando escribimos un programa en el que queremos que el proceso 0 obtenga el primer valor de entrada, el proceso 1 el segundo, etc.? Y si sólo un proceso obtiene los datos, ¿qué le ocurre a los demás? ¿Es razonable hacer que múltiples procesos lean de una sola terminal? Por otra parte, ¿qué ocurre si varios procesos intentan escribir datos en la terminal simultáneamente? ¿Se imprimirán antes los datos del proceso 0, después los del proceso 1, y así sucesivamente? ¿O se imprimirán dichos datos aleatoriamente? ¿O, lo que es peor, se

CAPÍTULO 4. CONCEPTOS BÁSICOS

70

mostrarán los datos de los distintos procesos todos mezclados (una línea del proceso 0, dos caracteres del proceso 1, 3 caracteres del 0, 2 líneas del 2, etc.)? Las operaciones estándar de E/S en C no proporcionan soluciones simples a dicho problema; así, la E/S sigue siendo objeto de investigación por parte de la comunidad de procesamiento paralelo. Por todo ello asumiremos que el proceso 0 puede al menos escribir en la salida estándar. También asumiremos que puede leer de la entrada estándar. En todos los casos asumiremos que sólo el proceso 0 puede interactuar con la E/S. Ésto podría parecer una debilidad, ya que como mencionamos antes la mayoría de las máquinas paralelas permiten que múltiples procesos interactuen con la E/S. Sin embargo es un método muy sólido que nos permitirá realizar un manejo limpio de la E/S en nuestros programas.

4.5. Ubicación de los Procesos La función MPI_Get_processor_name() nos permite conocer el nombre del procesador donde está ubicado cada proceso. Ésto puede ser útil para monitorizar nuestros programas en redes heterogéneas. Conocer en qué máquina concreta se está ejecutando un proceso específico puede ser determinante para explicar su comportamiento, para lo cual podemos ayudarnos con las herramientas de monitorización (sección 9.1). La sintaxis de dicha función es la siguiente:

int MPI_Get_processor_name(char* nombre, int* longnombre) El parámetro nombre es una cadena (vector de caracteres) cuyo tamaño debe ser al menos igual a la constante MPI_MAX_PROCESSOR_NAME. En dicho vector quedará almacenado el nombre del procesador. El parámetro longnombre es otro parámetro de salida que nos informa de la longitud de la cadena obtenida.

4.6. Información Temporal Con el objeto de facilitar el control y la monitorización, MPI nos ofrece funciones encaminadas a proporcionar información temporal sobre la ejecución de nuestros programas. La función MPI_Wtime() nos informa sobre el tiempo transcurrido en un determinado proceso. Dicha función no tiene parámetros; su valor de retorno es de tipo double y representa el tiempo transcurrido en segundos desde el comienzo de la ejecución del proceso. Si el atributo MPI_WTIME_IS_GLOBAL está definido y su valor es true (por defecto es así) el valor devuelto por la función estará sincronizado con todos los procesos pertenecientes al comunicador MPI_COMM_WORLD. Nosotros utilizaremos esta función para ofrecer cierta información al usuario sobre el tiempo de ejecución de nuestro programa por la salida estándar. Nos permitirá en estos casos diferenciar entre el tiempo de ejecución de un programa y el tiempo de procesamiento. Definimos el tiempo de ejecución de un programa como el tiempo que emplea para resolver un problema en un computador paralelo, desde el momento en que es generado el primer proceso hasta que acaba el último. Este tiempo no debe ser calculado con la función

4.7. IMPLEMENTACIÓN ALGORITMO ¡HOLA MUNDO!

71

MPI_Wtime() debido a que dicha función forma parte del entorno MPI, el cual debe ser finalizado antes de que el programa termine. Por lo tanto el tiempo que arrojaría es incorrecto, siempre menor al que debería; en su lugar usaremos las herramientas de monitorización para determinar el tiempo de ejecución. Por otro lado llamamos tiempo de procesamiento al tiempo que emplea el computador en calcular el resultado, eliminando el tiempo de inicialización y finalización de los procesos, y la comunicación con el usuario. De esta manera si el usuario tarda diez segundos en introducir los datos para un problema, ese tiempo no será añadido al tiempo de procesamiento pero sí al tiempo de ejecución. La función MPI_Wtime() nos ayudará a calcular el tiempo de procesamiento de un programa para después mostrarlo al usuario por la salida estándar. En el caso del algoritmo ¡Hola Mundo! el tiempo de procesamiento no es indicativo. Sin embargo es muy útil en programas donde un proceso (normalmente el proceso 0) desencadena la ejecución de los demás (normalmente al distribuir entre todos los procesos los datos que el usuario introduce por la entrada estándar). Éste será el caso más común entre los algoritmos expuestos en el presente documento.

4.7. Implementación Algoritmo ¡Hola Mundo! A continuación exponemos el código del algoritmo ¡Hola Mundo!. Como vemos dicho programa utiliza el paradigma SPMD (“Same Program Multiple Data”, Programa Único y Flujo de Datos Múltiple). Obtenemos el efecto de diferentes programas ejecutándose en distintos procesadores bifurcando la ejecución del programa. Para ello nos basamos en el identificador del proceso: las instrucciones ejecutadas por el proceso 0 son distintas de las ejecutadas por otros procesos, aunque todos los procesos estén ejecutando el mismo programa. Éste es el método más común para escribir programas MIMD. Algoritmo 4.1: ¡Hola Mundo! 1 2 3 4

/********************************************************/ /*Hola Mundo: CODIGO PROGRAMA QUE SALUDA */ /********************************************************/

5 6 7 8

# define TAMCADENA 100 # include " mpi . h " # include < s t d i o . h>

9 10 11 12 13 14 15 16 17 18 19 20 21

/**************/ /*FUNCION MAIN*/ /**************/ i n t main ( i n t argc , char argv ) { int id ; /*IDENTIFICADOR DEL PROCESO*/ i n t numprocs ; /*NUMERO DE PROCESOS*/ char nombreproc [MPI_MAX_PROCESSOR_NAME] ; /*NOMBRE PROCESADOR*/ i n t lnombreproc ; /*LONGITUD NOMBRE PROCESADOR*/ double t m p i n i c = 0 . 0 ; /*TIEMPO INICIO DE LA EJECUCION*/ double t m p f i n ; /*TIEMPO FINAL DE LA EJECUCION*/

LML

CAPÍTULO 4. CONCEPTOS BÁSICOS

72 22

/*INICIALIZAMOS EL ENTRORNO DE EJECUCION MPI*/ M P I _ I n i t (& argc ,& argv ) ;

23 24 25

/*ALMACENAMOS EL IDENTIFICADOR DEL PROCESO*/ MPI_Comm_rank (MPI_COMM_WORLD,& i d ) ;

26 27 28

/*ALMACENAMOS EL NUMERO DE PROCESOS*/ MPI_Comm_size (MPI_COMM_WORLD, & numprocs ) ;

29 30 31

/*E/S:NOMBRE DEL PROCESADOR,PROCESO 0*/ MPI_Get_processor_name ( nombreproc,& lnombreproc ) ; i f ( i d ==0){ f p r i n t f ( s t d o u t , " \ n P r o c e s o %d en %s E n c a r g a d o de l a E / S \ n \ n " , i d , nombreproc ) ; }

32 33 34 35 36 37 38

/*TIEMPO INICIAL DE LA EJECUCION */ t m p i n i c=MPI_Wtime ( ) ;

39 40 41

/*E/S:PROCESAMIENTO*/ i f ( i d ==0){ f p r i n t f ( s t d o u t , " ¡ H o l a Mundo ! \ n \ n " ) ; }

42 43 44 45 46

/*TIEMPO FINAL DE LA EJECUCION*/ t m p f i n =MPI_Wtime ( ) ;

47 48 49

/*E/S:INFORMACION SOBRE LA EJECUCION*/ i f ( i d ==0){ f p r i n t f ( s t d o u t , " Numero P r o c e s o s : %d \ n " , numprocs ) ; f p r i n t f ( s t d o u t , " Tiempo P r o c e s a m i e n t o : % f \ n \ n " , t m p f i n t m p i n i c ) ; }

50 51

N

52 53 54 55

/*FINALIZAMOS EL ENTRORNO DE EJECUCION MPI*/ MPI_Finalize ( ) ; return 0 ;

56 57 58 59

}

Capítulo 5

Paso de Mensajes El paso de mensajes es quizás la función más importante y característica del estándar MPI. Se utiliza básicamente para el intercambio de datos entre los procesos en ejecución. En este capítulo estudiaremos las características más importantes de los mensajes bloqueantes y no bloqueantes, aplicando dicha teoría a la implementación de un algoritmo diseñado para el cálculo de áreas circulares.

5.1. Algoritmo Cálculo de Áreas mediante Montecarlo El método de Montecarlo es un método numérico que permite resolver problemas matemáticos mediante la simulación de variables aleatorias. Utilizaremos dicho método para aproximar el área de un círculo con un radio determinado. Supongamos que queremos calcular el área de un círculo de radio O . Para hacerlo tomaremos un cuadrado de lado (@O y lo pondremos alrededor del círculo de radio O , de manera que quede circunscrito. A continuación generaremos un número de puntos aleatorios dentro del área del cuadrado. Algunos caerán dentro del área del círculo y otros no, como se expone en la figura 5.1. Tomaremos 6 como el número de puntos aleatorios generados dentro del cuadrado y  como de puntos que caen dentro   del círculo. Si sabemos que el área del círculo es P O y elquenúmero el área del cuadrado es ,Q(@OM3 , tendremos la siguiente igualdad:

P O    Q, (@OM3  6

Con lo cual llegamos fácilmente a que:

P

P SR *  6

Utilizando dicha aproximación de y sabiendo el radio del círculo aproximaremos fáP  cilmente su área mediante O . Lógicamente cuantas más muestras tomemos, o lo que es lo P mismo, cuantos más puntos generemos, mejor será la aproximación de . También interviene mucho la aleatoriedad de las muestras; cuanto más aleatorias sean, mejor. La cuestión ahora es determinar los puntos que caen dentro del círculo y los que caen fuera. Para explicarlo observemos la figura 5.2. Dado un punto ,.T'EU-3 podremos saber si ha caído dentro del círculo mediante la regla de Pitágoras: 73

CAPÍTULO 5. PASO DE MENSAJES

74

Figura 5.1: Generación Puntos Aleatorios

V   T XW U  Si la hipotenusa es mayor que el radio del círculo querrá decir que el punto está fuera de dicho círculo. Si la hipotenusa es menor que el radio, consideraremos que está dentro. Como podemos observar en la figura, también podemos generar puntos en sólo una cuarta parte del cuadrado y el círculo, de manera que la proporción no queda alterada. Así lo hacemos en la implementación del algoritmo Cálculo de Áreas mediante Montecarlo (sección 5.6).

5.2. El Entorno del Mensaje El paso de mensajes bloqueantes se lleva a cabo en nuestros programas por las funciones MPI_Send() y MPI_Recv() principalmente. La primera función envía un mensaje a un proceso determinado. La segunda recibe un mensaje de un proceso. Éstas son las funciones más básicas de paso de mensajes en MPI. Para que el mensaje sea comunicado con éxito, el sistema debe adjuntar alguna información a los datos que el programa intenta transmitir. Esta información adicional conforma el entorno del mensaje. En MPI el entorno contiene la siguiente información: 1.

El identificador del proceso receptor del mensaje.

2.

El identificador del proceso emisor del mensaje.

3.

Una etiqueta.

4.

Un comunicador.

Estos datos pueden ser usados por el proceso receptor para distinguir entre los mensajes entrantes. El origen puede ser usado para distinguir mensajes recibidos por distintos procesos.

5.2. EL ENTORNO DEL MENSAJE

75

(x,y)

h y

x

Figura 5.2: Cálculo Hipotenusa Punto Aleatorio

La etiqueta es un int especificado por el usuario que puede ser usado para distinguir mensajes
recibidos por un único proceso. Por ejemplo, supongamos que el proceso está enviando dos mensajes al proceso Y ; ambos mensajes contienen un número flotante. Uno de los flotantes
se emplea en un cálculo, mientras que otro debe ser impreso. Para determinar cuál es cuál,
puede usar etiquetas diferentes para cada mensaje. Si Y usa las mismas etiquetas que en las recepciones correspondientes, “sabrá” qué hacer con ellas. MPI garantiza que los enteros dentro del intervalo 0-32767 pueden ser usados como etiquetas. La mayoría de las implementaciones permiten valores mucho mayores. Como dijimos antes un comunicador es básicamente una colección de procesos que pueden mandarse mensajes entre sí. La importancia de los comunicadores se acentúa cuando los módulos de un programa han sido escritos independientemente de los demás. Por ejemplo, supongamos que queremos resolver un sistema de ecuaciones diferenciales y, en el transcurso de resolverlo, tenemos que resolver un sistema de ecuaciones lineales. Mejor que escribir la resolución del sistema de ecuaciones lineales desde el principio, podríamos usar una librería de funciones escrita por otra persona y optimizada para el sistema que estamos usando. ¿Có
mo evitamos que se confundan los mensajes que nosotros enviamos entre los procesos y Y con los mensajes enviados en la librería de funciones? Sin la ventaja de los comunicadores probablemente haríamos una partición del rango de las posibles etiquetas, haciendo que parte de ellas sólo puedan ser usadas por la librería de funciones. Ésto es tedioso y puede causarnos problemas si ejecutamos el programa en otro sistema: puede que la librería del otro sistema no haga uso del mismo rango de etiquetas. Con la ventaja de los comunicadores, simplemente creamos un comunicador para uso exclusivo en la resolución del sistema de ecuaciones lineales, y se lo pasamos a la librería encargada de hacerlo como argumento en la llamada. Comentaremos los detalles más adelante. Por ahora continuaremos utilizando el comunicador MPI_COMM_WORLD, el cual consiste en todos los procesos que se ejecutan cuando el programa comienza.

CAPÍTULO 5. PASO DE MENSAJES

76 Tipo de Datos MPI MPI_CHAR MPI_SHORT MPI_INT MPI_LONG MPI_UNSIGNED_CHAR MPI_UNSIGNED_SHORT MPI_UNSIGNED MPI_UNSIGNED_LONG MPI_FLOAT MPI_DOUBLE MPI_LONG_DOUBLE MPI_BYTE MPI_PACKED

Tipo de Datos C signed char signed short int signed int signed long int unsigned char unsigned short int unsigned int unsigned long int float double long double

Cuadro 5.1: Tipos de Datos MPI

5.3. Funciones de Paso de Mensajes Bloqueantes Para resumir detallamos la sintaxis de las dos funciones más importantes de paso de mensajes bloqueantes: int MPI_Send(void* mensaje, int contador, MPI_Datatype tipo_datos, int destino, int etiqueta, MPI_Comm comunicador) int MPI_Recv(void* mensaje, int contador, MPI_Datatype tipo_datos, int origen, int etiqueta, MPI_Comm comunicador, MPI_Status* status)

Al igual que la mayoría de las funciones de la biblioteca estándar de C, la mayoría de las funciones MPI retornan un entero como código de error. Sin embargo, como la mayoría de los programadores de C, ignoraremos esos valores de retorno en casi todos los casos. Los contenidos del mensaje son almacenados en un bloque de memoria referenciado por el argumento mensaje. Los siguientes dos argumentos, contador y tipo_datos, permiten al sistema identificar el final del mensaje: éste contiene una secuencia de contador valores, cada uno del tipo MPI datatype. Este tipo no es un tipo de C, aunque la mayoría de los tipos predefinidos corresponden a tipos de C. En el cuadro 5.1 se listan los tipos predefinidos de MPI con sus correspondientes tipos de C, si éstos existen. Los últimos dos tipos, MPI_BYTE y MPI_PACKED, no corresponden con tipos estándar de C. El tipo MPI_BYTE puede ser usado si queremos forzar que el sistema no realice conversión alguna entre las distintas representaciones de los datos (por ejemplo, en una red heterogénea de estaciones de trabajo que utilicen una representación de datos distinta).

5.4. FUNCIONES DE PASO DE MENSAJES NO BLOQUEANTES

77

Notar que la cantidad de espacio reservado para el buffer de entrada no tiene porqué coincidir con la cantidad exacta de espacio que ocupa el mensaje que estemos recibiendo. Por ejemplo, podría darse el caso de que el tamaño del mensaje que el proceso 1 envía al proceso 0 sea de 28 caracteres (strlen(mensaje)+1), aunque el proceso 0 reciba el mensaje en un buffer que tiene capacidad para 100 caracteres. Ésto tiene sentido. En general el proceso receptor no conoce el tamaño exacto del mensaje que se le está enviando. MPI permite recibir mensajes tan largos como capacidad reservada tengamos. Si no tenemos suficiente capacidad, tendremos un error de desbordamiento. Los argumentos destino y origen son los identificadores del proceso receptor y del proceso emisor, respectivamente. MPI permite que el argumento origen sea un comodín. Existe una constante predefinida llamada MPI_ANY_SOURCE que puede ser usada si un proceso está preparado para recibir un mensaje procedente de cualquier proceso. No existe comodín para destino. Como dijimos anteriormente MPI contiene dos mecanismos diseñados específicamente para “particionar el espacio de los mensajes”: las etiquetas y los comunicadores. Los argumentos etiqueta y comunicador son, respectivamente, la etiqueta y el comunicador. El argumento etiqueta es un int y, por ahora, nuestro único comunicador es MPI_COMM_WORLD, el cual, como comentamos antes, está predefinido en todos los sistemas MPI y consiste en todos los procesos que se ejecutan cuando el programa comienza. Existe un comodín, MPI_ANY_TAG, que puede ser usado en MPI_Recv() para la etiqueta. No existe un comod
ín para el comunicador. En otras palabras, para que el proceso mande un mensaje al proceso
Y el argumento comunicador que usa en MPI_Send() debe ser idéntico al argumento que Y usa en MPI_Recv(). El último argumento de MPI_Recv(), status, retorna información acerca de los datos que hemos recibido. Referencia a un registro con dos campos, uno para el origen y otro para la etiqueta. Por ejemplo, si el origen era MPI_ANY_SOURCE en la llamada a MPI_Recv(), el argumento status contendrá el identificador del proceso que envió el mensaje.

5.4. Funciones de Paso de Mensajes No Bloqueantes El rendimiento de los sistemas de paso de mensajes puede ser mejorado mediante el solapamiento entre comunicación y procesamiento en los algoritmos. Un método para realizar ésto es mediante la comunicación no bloqueante. Las funciones de envío de mensajes no bloqueantes inician el envío del mensaje, pero no lo completan; para ello se necesita una llamada a la función de finalización de envíos no bloqueantes. De la misma manera una llamada a una función de recepción de mensajes no bloqueantes no detiene la ejecución del algoritmo hasta que dicho mensaje sea realmente recibido, como ocurre con las versiones bloqueantes. De este modo podemos solapar comunicación y procesamiento en nuestros algoritmos. Las versiones no bloqueantes de las funciones de paso de mensajes son: int MPI_Isend(void* mensaje, int contador, MPI_Datatype tipo_datos, int destino, int etiqueta, MPI_Comm comunicador, MPI_Request* peticion)

CAPÍTULO 5. PASO DE MENSAJES

78

int MPI_Irecv(void* mensaje, int contador, MPI_Datatype tipo_datos, int origen, int etiqueta, MPI_Comm comunicador, MPI_Request* peticion)

A simple vista la diferencia entre estas funciones y sus versiones bloqueantes es la existencia del argumento peticion en sus llamadas. Este argumento es utilizado por las funciones de finalización de transmisiones bloqueantes para su ejecución. Las funciones de finalización de transmisiones bloqueantes son: int MPI_Wait(MPI_Request* peticion, MPI_Status* status) int MPI_Waitany(int contador, MPI_Request* vector_peticiones, int* indice, MPI_Status* status) int MPI_Waitall(int contador, MPI_Request* vector_peticiones, MPI_Status* status) La función MPI_Wait() espera a que se complete un envío o una recepción de un mensaje. Para ello le pasamos como argumento de entrada el argumento de salida que nos proporciona la función de paso de mensajes no bloqueantes en el momento de la llamada. El argumento de salida status nos proporciona información acerca de los datos que hemos recibido. Por su parte MPI_Waitany() espera a que se complete cualquiera de las peticiones que le pasamos en vector_peticiones, devolviendo en el argumento indice la posición de la petición satisfecha. MPI_Waitall() espera a que se completen todas las peticiones que le pasamos en vector_peticiones.

5.5. Agrupaciones de Datos Con la generación de máquinas actual el envío de mensajes es una operación costosa. Según esta regla, cuantos menos mensajes enviemos mejor será el rendimiento general del algoritmo. Así pues en el algoritmo Cálculo de Áreas mediante Montecarlo podríamos mejorar el rendimiento si distribuimos los datos de entrada en un solo mensaje entre los procesadores. Recordemos que las funciones de paso de mensajes tienen dos argumentos llamados contador y tipo_datos. Estos dos parámetros permiten al usuario agrupar datos que tengan el mismo tipo básico en un único mensaje. Para usarlo dichos datos deben estar almacenados en direcciones de memoria contiguas. Debido a que el lenguaje C garantiza que los elementos de un vector están almacenados en direcciones de memoria contiguas, si queremos enviar los elementos de un vector, o un subconjunto de ellos, podremos hacerlo en un solo mensaje. Desafortunadamente esto no nos ayuda en el algoritmo Cálculo de Áreas mediante Montecarlo si queremos enviar los datos de entrada a cada proceso en un solo mensaje. Ello es

5.5. AGRUPACIONES DE DATOS

79

debido a que las variables que contienen el radio y el número de muestras no tienen porqué estar alojadas en direcciones de memoria contiguas. Tampoco debemos almacenar estos datos en un vector debido a que ello restaría claridad y elegancia al código. Para lograr nuestro objetivo utilizaremos una facilidad de MPI para la agrupación de los datos.

5.5.1. Tipos Derivados Una opción razonable para conseguir nuestro objetivo podría ser almacenar el radio y el número de muestras en una estructura con dos miembros (un flotante largo y un entero largo) como se muestra a continuación: typedef struct{ long double radio; long nmuestras_local; } Tipo_Datos_Entrada;

e intentar utilizar el tipo de datos de la estructura como argumento tipo_datos en las funciones de paso de mensajes. El problema aquí es que el tipo de datos de la estructura no es un tipo de datos MPI; necesitamos construir un tipo de datos MPI a partir del tipo de datos de C. MPI propone una solución a ésto permitiendo al usuario construir tipos de datos MPI en tiempo de ejecución. Para construir un tipo de datos MPI básicamente se especifica la distribución de los datos en el tipo (los tipos de los miembros y sus direcciones relativas de memoria). Un tipo de datos MPI construido de este modo se denomina tipo de datos derivado. Para ver cómo funciona ésto expondremos la función que construye dicho tipo de datos.

void construir_tipo_derivado(Tipo_Datos_Entrada* pdatos, MPI_Datatype* pMPI_Tipo_Datos){ MPI_Datatype tipos[2]; int longitudes[2]; MPI_Aint direcc[3]; MPI_Aint desplaz[2];

/*PRIMERO ESPECIFICAMOS LOS TIPOS*/ tipos[0]=MPI_LONG_DOUBLE; tipos[1]=MPI_LONG; /*ESPECIFICAMOS EL NUMERO DE ELEMENTOS DE CADA TIPO*/ longitudes[0]=1; longitudes[1]=1; /*CALCULAMOS LOS DESPLAZAMIENTOS DE LOS MIEMBROS DE LA ESTRUCTURA RELATIVOS AL COMIENZO DE DICHA ESTRUCTURA*/ MPI_Address(pdatos,&direcc[0]); MPI_Address(&(pdatos->radio),&direcc[1]); MPI_Address(&(pdatos->nmuestras_local),&direcc[2]); desplaz[0]=direcc[1]-direcc[0];

CAPÍTULO 5. PASO DE MENSAJES

80 desplaz[1]=direcc[2]-direcc[0];

/*CREACION TIPO DATOS DERIVADO*/ MPI_Type_struct(2,longitudes,desplaz,tipos,pMPI_Tipo_Datos); /*CERTIFICARLO DE MANERA QUE PUEDA SER USADO*/ MPI_Type_commit(pMPI_Tipo_Datos); }/*construir_tipo_derivado*/

Las primeras dos sentencias especifican los tipos de los miembros del tipo de datos derivado, y las dos siguientes especifican el número de elementos de cada tipo. La función MPI_Address() nos ayuda a calcular los desplazamientos de cada uno de los miembros con respecto a la dirección inicial del primero. Con esta información ya sabemos los tipos, los tamaños y las direcciones relativas de memoria de cada uno de los miembros del tipo de datos de C, y por lo tanto ya podemos definir el tipo de datos MPI derivado del tipo de datos de C. Ésto se hace llamando a las funciones MPI_Type_struct() y MPI_Type_Commit(). El tipo de datos MPI creado puede ser usado en cualquiera de las funciones de comunicación de MPI. Para usarlo simplemente usaremos como primer argumento de las funciones la dirección inicial de la estructura a enviar, y el tipo de datos MPI creado en el argumento tipo_datos.

5.5.2. Vectores La función MPI_Type_vector() crea un tipo derivado consistente en contador elementos. int MPI_Type_vector(int contador, int longitud_bloque, int salto, MPI_Datatype tipo_datos_elem, MPI_Datatype* nuevo_tipo) Cada elemento contiene longitud_bloque elementos de tipo tipo_datos_elem. El argumento salto es el número de elementos de tipo tipo_datos_elem que hay entre los sucesivos elementos de nuevo_tipo.

5.6. Implementación Cálculo de Áreas mediante Montecarlo A continuación exponemos las versiones bloqueante y no bloqueante del algoritmo Cálculos de Áreas mediante Montecarlo.

5.6.1. Implementación con Mensajes Bloqueantes

5.6. IMPLEMENTACIÓN CÁLCULO DE ÁREAS MEDIANTE MONTECARLO

81

Algoritmo 5.1: Cálculo de Áreas mediante Montecarlo (Bloqueante) 1 2 3 4 5

/***************************************************/ /*Calculo de Areas: CODIGO APROXIMACION DE AREAS */ /*CIRCULARES MEDIANTE MONTECARLO (BLOQUEANTE) */ /***************************************************/

6 7 8 9 10

# # # #

include < s t d i o . h> include < s t d l i b . h> include < math . h> include " mpi . h "

11 12 13 14 15 16

/*DECLARACION ESTRUCTURA DATOS ENTRADA*/ typedef s t r u c t { long double r a d i o ; long n m u e s t r a s _ l o c a l ; } Tipo_Datos_Entrada ;

17 18 19 20 21 22 23 24 25 26

/*DECLARACION DE LA FUNCIONES QUE VAMOS A UTILIZAR*/ long double MonteCarlo ( i n t i d , long double r a d i o , long l o c a l _ n ) ; void o b t e n e r _dat os ( long double p r a d i o , long pnmuestras_global ) ; void d i s t r i b u i r _ d a t o s ( i n t i d , i n t numprocs , long double p r a d i o , long p n m u e s t r a s _ l oc a l ) ; void r e c o l e c t a r _ d a t o s ( i n t i d , i n t numprocs , long double p a p r o x _ l o c a l , long double p a p r o x _ g l o b a l ) ; void c o n s t r u i r _ t i p o _ d e r i v a d o ( Tipo_Datos_Entrada pdatos , MPI_Datatype pMPI_Tipo_Datos ) ;

L

L

L

L

L

L

L

L

27 28 29 30 31

/**************/ /*FUNCION MAIN*/ /**************/ i n t main ( i n t argc , char

LML

argv ) {

32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

long double PI25DIGITOS=3.141592653589793238462643; /*VALOR PI PARA CALCULAR EL ERROR*/ int id ; /*IDENTIFICADOR DEL PROCESO*/ i n t numprocs ; /*NUMERO DE PROCESOS*/ char nombreproc [MPI_MAX_PROCESSOR_NAME] ; /*NOMBRE PROCESADOR*/ i n t lnombreproc ; /*LONGITUD NOMBRE PROCESADOR*/ long double r a d i o ; /*RADIO CIRCUNFERENCIA*/ long n m u e s t r a s _global ; /*NUMERO DE MUESTRAS*/ long n m u e s t r a s _ l o c a l ; /*NUMERO DE MUESTRAS DE CADA PROCESO*/ long double a p r o x _ l o c a l ; /*APROX LOCAL DE CADA PROCESO*/ long double a p r o x _ g l o b a l ; /*APROX GENERAL (MEDIA DE TODAS LAS LOCALES)*/ int raiz =0; /*PROCESO QUE RECIBE LAS LOCALES Y LAS SUMA*/ double t m p i n i c = 0 . 0 ; /*TIEMPO INICIO DE LA EJECUCION*/ double t m p f i n ; /*TIEMPO FINAL DE LA EJECUCION */

48 49 50 51

int etiqueta =50; MPI_Status s t a t u s ; int origen ;

/*ETIQUETA MENSAJES DE PRUEBA*/ /*STATUS RECEPCION MENSAJES DE PRUEBA*/ /*PROCESO ORIGEN MENSAJES DE PRUEBA*/

52 53 54

/*INICIALIZAMOS EL ENTRORNO DE EJECUCION MPI*/

CAPÍTULO 5. PASO DE MENSAJES

82 55

M P I _ I n i t (& argc ,& argv ) ;

56 57 58

/*ALMACENAMOS EL IDENTIFICADOR DEL PROCESO*/ MPI_Comm_rank (MPI_COMM_WORLD,& i d ) ;

59 60 61

/*ALMACENAMOS EL NUMERO DE PROCESOS*/ MPI_Comm_size (MPI_COMM_WORLD,& numprocs ) ;

62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

/*E/S:NOMBRE DEL PROCESADOR,PROCESADOR 0*/ MPI_Get_processor_name ( nombreproc,& lnombreproc ) ; i f ( i d ==0){ f p r i n t f ( s t d o u t , " \ n P r o c e s o %d en %s E n c a r g a d o de l a E / S \ n " , i d , nombreproc ) ; } /*E/S:NOMBRE DEL PROCESADOR,TODOS LOS PROCESOS (PRUEBAS)*/ /*if(id==0){ * for (origen=1;origenn m u e s t r a s _ l o c a l ) , & d i r e c c [ 2 ] ) ; desplaz [ 0 ] = d i r e c c [1] d i r e c c [ 0 ] ; desplaz [ 1 ] = d i r e c c [2] d i r e c c [ 0 ] ;

275

N

276 277

N

N

278

N

279 280 281

/*CREACION TIPO DATOS DERIVADO*/ MPI_Type_struct ( 2 , l o n g i t u d e s , desplaz , t i p o s , pMPI_Tipo_Datos ) ;

282 283 284

/*CERTIFICARLO DE MANERA QUE PUEDA SER USADO*/ MPI_Type_commit ( pMPI_Tipo_Datos ) ;

285 286 287 288

} /*construir_tipo_derivado*/

5.6.2. Implementación con Mensajes No Bloqueantes Algoritmo 5.2: Cálculo de Áreas mediante Montecarlo (No Bloqueante) 1 2 3 4 5

/***************************************************/ /*Calculo de Areas: CODIGO APROXIMACION DE AREAS */ /*CIRCULARES MEDIANTE MONTECARLO (NO BLOQUEANTE) */ /***************************************************/

6 7 8

/*NUMERO MAXIMO DE PROCESOS EN EJECUCION */ # define MAX_NUM_PROCS 128

9 10 11 12 13

# # # #

include < s t d i o . h> include < s t d l i b . h> include < math . h> include " mpi . h "

14 15 16 17 18 19

/*DECLARACION ESTRUCTURA DATOS ENTRADA*/ typedef s t r u c t { long double r a d i o ; long n m u e s t r a s _ l o c a l ; } Tipo_Datos_Entrada ;

20 21 22 23 24 25 26 27 28 29

/*DECLARACION DE LA FUNCIONES QUE VAMOS A UTILIZAR*/ long double MonteCarlo ( i n t i d , long double r a d i o , long l o c a l _ n ) ; void o b t e n e r _dat os ( long double p r a d i o , long pnmuestras_global ) ; void d i s t r i b u i r _ d a t o s ( i n t i d , i n t numprocs , long double p r a d i o , long p n m u e s t r a s _ l oc a l ) ; void r e c o l e c t a r _ d a t o s ( i n t i d , i n t numprocs , long double p a p r o x _ l o c a l , long double p a p r o x _ g l o b a l ) ; void c o n s t r u i r _ t i p o _ d e r i v a d o ( Tipo_Datos_Entrada pdatos , MPI_Datatype pMPI_Tipo_Datos ) ;

L

32 33 34

L

L

L

L

L

30 31

L

/**************/ /*FUNCION MAIN*/ /**************/ i n t main ( i n t argc , char

L8L

argv ) {

L

5.6. IMPLEMENTACIÓN CÁLCULO DE ÁREAS MEDIANTE MONTECARLO

87

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

long double PI25DIGITOS=3.141592653589793238462643; /*VALOR PI PARA CALCULAR EL ERROR*/ int id ; /*IDENTIFICADOR DEL PROCESO*/ i n t numprocs ; /*NUMERO DE PROCESOS*/ char nombreproc [MPI_MAX_PROCESSOR_NAME] ; /*NOMBRE PROCESADOR*/ i n t lnombreproc ; /*LONGITUD NOMBRE PROCESADOR*/ long double r a d i o ; /*RADIO CIRCUNFERENCIA*/ long n m u e s t r a s _global ; /*NUMERO DE MUESTRAS*/ long n m u e s t r a s _ l o c a l ; /*NUMERO DE MUESTRAS DE CADA PROCESO*/ long double a p r o x _ l o c a l ; /*APROX LOCAL DE CADA PROCESO*/ long double a p r o x _ g l o b a l ; /*APROX GENERAL (MEDIA DE TODAS LAS LOCALES)*/ int raiz =0; /*PROCESO QUE RECIBE LAS LOCALES Y LAS SUMA*/ double t m p i n i c = 0 . 0 ; /*TIEMPO INICIO DE LA EJECUCION*/ double t m p f i n ; /*TIEMPO FINAL DE LA EJECUCION */

51 52 53 54

int etiqueta =50; MPI_Status s t a t u s ; int origen ;

/*ETIQUETA MENSAJES DE PRUEBA*/ /*STATUS RECEPCION MENSAJES DE PRUEBA*/ /*PROCESO ORIGEN MENSAJES DE PRUEBA*/

55 56 57 58

/*INICIALIZAMOS EL ENTRORNO DE EJECUCION MPI*/ M P I _ I n i t (& argc ,& argv ) ;

59 60 61

/*ALMACENAMOS EL IDENTIFICADOR DEL PROCESO*/ MPI_Comm_rank (MPI_COMM_WORLD,& i d ) ;

62 63 64

/*ALMACENAMOS EL NUMERO DE PROCESOS*/ MPI_Comm_size (MPI_COMM_WORLD,& numprocs ) ;

65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

/*E/S:NOMBRE DEL PROCESADOR,PROCESADOR 0*/ MPI_Get_processor_name ( nombreproc,& lnombreproc ) ; i f ( i d ==0){ f p r i n t f ( s t d o u t , " \ n P r o c e s o %d en %s E n c a r g a d o de l a E / S \ n " , i d , nombreproc ) ; } /*E/S:NOMBRE DEL PROCESADOR,TODOS LOS PROCESOS (PRUEBAS)*/ /*if(id==0){ * for (origen=1;origen