PDF de programación - Acceso a recursos ejecutables por Internet del Laboratorio de Paralelismo

Centro de Investigación y Estudios Avanzados

del Instituto Politécnico Nacional

Departamento de Ingeniería Eléctrica

Sección Computación



Acceso a recursos ejecutables por Internet

del Laboratorio de Paralelismo



Tesis que presenta:
Optando por el grado de: Maestro en Ciencias
Ingeniería Eléctrica
Especialidad:
Opción:

Computación

Armando Flores Ibarra



Asesor:

Dr. Arturo Díaz Pérez
Sección de Computación

México, D.F. a 5 de Julio del año 2002



Este trabajo fue parcialmente financiado mediante los proyectos CONACyT 31892A: Algoritmos y
arquitecturas de computadoras con dispositivos reconfigurables y CONACYT-CINVESTAV REDII
correspondiente al año 2000.

Agradecimientos



A mi madre

Loly Ibarra Caballero


A mis hermanas

Andrea Flores Ibarra
Laura Leticia Flores Ibarra


A mis tíos

Alma Pérez Méndez
Cecilia Ibarra Caballero
Jorge Ibarra Caballero
Karina Bringas Nosti
René Ibarra Caballero


A todos mis familiares por su apoyo y comprensión

A mi asesor

Dr. Arturo Díaz Pérez


A todo el cuerpo de profesores de la Sección de Computación



Contenido



Introducción

1. Tecnologías para la Construcción de Aplicaciones Cliente/Servidor en Internet
1.1 Ingeniería de los Sistemas Cliente/Servidor
1.2 Tendencias en el diseño de Páginas Web
1.2.1 CGI: Common Gateway Interface
1.2.1.1 CGI y Bases de Datos
1.2.2 Java Servlets
1.2.3 Active Server Pages
1.2.3.1 ASP y Bases de Datos
1.2.4 JavaServer Pages (JSP)
1.2.4.1 Java Database Connectivity (JDBC)
1.2.5 PHP
1.2.5.1 PHP vs. ASP
1.2.5.2 PHP vs. Cold Fusion
1.2.5.3 PHP vs. Perl
1.2.6 Comparación cualitativa entre CGIs, Servlets, JSP, y ASP
1.3 Recursos específicos
1.3.1 Bases de datos y ODBC
1.3.2 Comercio Electrónico
1.3.2.1 Fases del Comercio Electrónico
1.3.3 Bibliotecas Digitales
1.3.4 Laboratorios Virtuales
1.3.5 Laboratorio de Paralelismo

Capítulo 2 Laboratorio de Paralelismo
2.1 Arquitecturas Paralelas
2.1.1 Espacio de Direccionamiento Compartido
2.1.2 Memoria distribuida
2.2 Programación Paralela
2.2.1 Diseño de Algoritmos Paralelos
2.3 MPI
2.3.1 Implementaciones MPI
2.3.2 MPICH
2.3.3 Aplicaciones MPI
2.4 Laboratorio de Paralelismo
2.4.1 Pruebas de Rendimiento

Capítulo 3 Invocación Remota de Recursos Ejecutables del Laboratorio de Paralelismo
3.1 Descripción General
3.2 Registro y Selección de Aplicaciones
3.2.1 Formas HTML
3.2.2 Lista de Usuarios
3.2.3 Lista de Aplicaciones
3.2.4 Agregando una Aplicación
3.3 Ejecución de las Aplicaciones
3.4 Resultados
3.5 Trayectorias importantes de la distribución

Página

1

7
7
15
16
18
19
21
22
23
24
25
25
26
27
27
28
29
30
30
31
34
36

39
39
41
43
46
49
49
51
53
55
57
58

69
69
70
72
74
75
77
77
79
80



i





Capítulo 4 Calendarización de Programas Paralelos
4.1 Introducción al Problema de Calendarización
4.1.1 Modelos de Aplicaciones
4.1.1.1 Modelo de Precedencia de Procesos
4.1.1.2 Modelo de Comunicación de Procesos
4.1.1.3 Modelo de Procesos Independientes
4.1.2 Calendarización Estática
4.1.3 Algoritmo de Calendarización por Lista de Graham
4.1.4 Calendarización Dinámica
4.2 Descripción General del Calendarizador de Programas Paralelos
4.2.1 Modelo Un Cliente/Un Servidor
4.2.2 Modelo Varios Clientes/Un Servidor
4.3 Algoritmo para el Despachador de Corto Plazo
4.3.1 Medida de Rendimiento del Despachador de Corto Plazo
4.4 Descripción del Despachador de Mediano Plazo
4.5 Trabajo Relacionado
4.5.1 Algoritmos de Calendarización Estática
4.5.2 Herramientas para Calendarización de Procesos
4.5.2.1 Hypertool
4.5.2.2 PYRROS
4.5.2.3 Parallax
4.5.2.4 OREGAMI
4.5.2.5 PARSA
4.5.2.6 CASCH
4.5.2.7 Herramientas Comerciales

Capítulo 5 Visualización de la Ejecución Remota de Programas Paralelos
5.1 Facilidades de Visualización de Programas Paralelos
5.1.1 XPVM
5.1.2 XMPI
5.2 Descripción General de la Herramienta de Visualización
5.2.1 Archivo de Datos de las Aplicaciones Paralelas
5.2.2 Archivo de Datos de los Despachadores de Corto y Mediano Plazo
5.3 Generación de Datos, Tablas y Gráficas
5.3.1 Gnuplot

Capítulo 6 Resultados
6.1 Algoritmos de Trayectorias más Cortas
6.1.1 Resultados Obtenidos
6.2 Algoritmos de Jacobi y Gauss para la resolución sistemas de ecuaciones lineales
6.2.1 Método de Jacobi
6.2.1.1 Resultados Obtenidos
6.2.2 Eliminación Gaussiana
6.2.2.1 Resultados Obtenidos

Conclusiones
Referencias

81
81
82
83
83
83
84
86
87
87
89
90
90
92
93
95
96
97
97
98
98
99
99
100
101



103
103
104
105
106
107
108
110
112



115
115
118
120
121
123
124
127



129
131



ii

Lista de Figuras



I-1. Pasos a seguir para la resolución del problema

1.1 Arquitecturas de sistemas distribuidos y cooperativos en un entorno corporativo
1.2 Opciones de la arquitectura cliente/servidor
1.3. Invocación de un programa CGI por un usuario remoto
1.4 Acceso a una base de datos utilizando CGIs
1.5 Proceso Java Servlets
1.6 Proceso de ejecución de una página ASP
1.7 Proceso JSP
1.8 Principios para la construcción de bibliotecas digitales
1.9 Ambiente distribuido cliente servidor

2.1 Capas de abstracción en un arquitectura paralela de computadora
2.2 Extendiendo un sistema en uno multiprocesador de memoria compartida mediante la adición de módulos
2.3 Esquemas típicos de interconexión de multiprocesadores de memoria compartida
2.4 Arquitectura de paso de mensajes
2.5 Abstracción del paso de mensajes a nivel de usuario send/receive
2.6 Primitivas de Comunicación Colectiva
2.7 Primitiva Barrier de Comunicación Colectiva
2.8 Un modelo simple de programación paralela (tarea/canal)
2.9 Las cuatro acciones básicas de una tarea
2.10 Código fuente de una aplicación MPI
2.11 Esquema general del Laboratorio de Paralelismo
2.12 Prueba de Comunicación Punto a Punto: Un Par (Presley-Presley)
2.13 Prueba de Comunicación Punto a Punto: Un Par (Presley-Presley)
2.14 Prueba de Comunicación Punto a Punto: Un Par (Presley-Presley)
2.15 Prueba de Comunicación Punto a Punto: Un Par (Presley-Presley)
2.16 Prueba de Comunicación Punto a Punto: Un Par (Elvis-Presley)
2.17 Prueba de Comunicación Punto a Punto: Un Par (Elvis-Presley)
2.18 Prueba de Comunicación Punto a Punto: Un Par (Elvis-Presley)
2.19 Prueba de Comunicación Punto a Punto: Un Par (Elvis-Presley)
2.20 Prueba de Comunicación Punto a Punto: Varios Pares (Elvis-Presley)
2.21 Prueba de Comunicación Punto a Punto: Varios Pares (Elvis-Presley)
2.22 Prueba de Comunicación Punto a Punto: Varios Pares (Elvis-Presley)
2.23 Prueba de Comunicación Punto a Punto: Varios Pares (Elvis-Presley)

3.1 Visión general del sistema. El usuario solicita la ejecución de una de las aplicaciones del sistema obteniendo a la salida los
resultados obtenidos
3.2 Ciclo de ejecución de una aplicación
3.3 Proceso de registro y selección
3.4 Código HTML de una sencilla Forma HTML
3.5 Forma HTML resultante del código de la Figura 3.4
3.6 Programa de administración de la lista de usuarios del sistema
3.7 Forma HTML que muestra las aplicaciones paralelas con las que cuenta el sistema
3.8 Forma HTML para la recolección de datos de aplicación
3.9 Proceso de selección y ejecución de una aplicación
3.10 El script CGI se encarga de construir y ejecutar el comando que permite la ejecución de la aplicación en el sistema
3.11 Generación de Tablas y Gráficas de Resultados

Página

4

8
10
17
18
20
22
23
32
36

41
42
42
43
43
45
45
46
47
55
57
59
60
60
61
62
63
63
64
65
66
66
67

69

70
71
72
72
75
75
76
76
78
80



iii


4.1 Modelo de descripción de aplicaciones paralelas
4.2. Ejemplo de una gráfica de tareas (DAG)
4.3 Carta de Gant
4.4 Despachador de Corto y Mediano Plazo
4.5 Modelo Un Cliente/Un Servidor
4.6 Modelo Varios Clientes/Un Servidor
4.7 Despachador de Corto Plazo, lee y optimiza solicitudes de cliente para su ejecución
4.8 Pseudocódigo del Despachador de Corto Plazo
4.9 Creación de la Lista de Tareas por parte del Despachador de Corto Plazo
4.10 Proceso para la ejecución en el sistema de una aplicación paralela
4.11 Pseudocódigo del Despachador de Mediano Plazo

5.1 Facilidades de Visualización
5.2 XPVM
5.3 XMPI
5.4 Ventana de detalles de proceso
5.5 Herramienta de Visualización, conformada por barras de progreso y una tabla de procesos (TOP)
5.6 Cada uno de los procesadores involucrados escribe datos en el archivo rankn.dat que le corresponde
5.7 Los despachadores de corto y mediano plazo actualizan los datos de los archivos conforme se presentan nuevos eventos
5.8 Herramienta de visualización del sistema
5.9 Una vez finalizada la ejecución de la aplicación seleccionada
5.10 Ejemplo de tablas de datos y gráficas generados por el script de graficaciónel usuario manda a invocar al script CGI de
graficación
5.11 Ejemplo de un archivo de puntos de datos generados por el sistema para su graficación
5.12 Ejemplo de un script gnuplot generado por el sistema
5.13 Gráfica generada por el programa gnuplot correspondientes a los archivos de las Figuras 5.11 y 5.12
5.14 Proceso para la generación de tablas de datos y gráficas

6.1 Un sencillo grafo dirigido (G), y su matriz adyacente (A)
6.2 Pseudocódigo del algoritmo de Floyd-Warshall
6.3 Pseudocódigo del algoritmo paralelo de Floyd-Warshall
6.4 Gráfica de Resultados para el Algoritmo de Floyd-Warshall
6.5 Gráfica de Aceleración para el Algoritmo de Floyd-Warshall
6.6 Pseudocódigo paralelo del algoritmo de Jacobi
6.7 Gráfica