La resolución de sistemas de ecuaciones lineales es un problema muy común, que se presenta en un gran número de situaciones, sobre todo en aplicaciones científicas y de cálculo. Existes numerosos métodos para su resolución, bien por métodos directos o por métodos iterativos. En el caso que se presenta nos centraremos en una situación muy particular que suele aparecer en ocasiones, y cuya resolución se puede abordar mediante un algoritmo particular.
El problema que se plantea es la resolución de sistemas de ecuaciones lineales en los que la matriz de coeficientes presenta una estructura triangular (matriz L).
Sea el sistema : L . x = b
En muchas ocasiones es necesario resolver m sistemas
de ecuaciones lineales con la misma matriz de coeficientes L.
En estos casos el problema se puede plantear igualmente como :
L . x = b que expresado en forma matricial :
a11 0 0 ... 0 x11 ... x1n b11 ... b1m
a21 a22 0 ... 0 x21 ... x2n b21 ... b2m
a31 a32 a33 ... 0 * x31 ... x3n = b31 ... b3m
... ... ... ... 0 ... ... ... ... ... ...
an1 an2 an3 ...
ann xn1 ... xnm bn1
... bnm
En este sistema :
A continuación vamos a presentar una serie
de algoritmos que permitirán resolver este problema tan
particular de resolución de sistemas triangulares.
1) Algoritmo de acceso por filas :
Para resolver de forma sistemática los m sistemas
de estos casos, existe un algoritmo secuencial muy simple, en
el que lo que se hace es un recorrido de cada una de las filas.
Una vez fijada la fila i, procedemos a calcular la solución
de dicha fila para cada uno de los m sistemas. A continuación
actualizamos los términos independientes para el resto
de las filas, de nuevo para cada uno de los m sistemas. El acceso
a las matrices se realiza por filas. El algoritmo es el siguiente :
- Para i=1 hasta n hacer /* Bucle recorriendo las n filas */
- Para j=1 hasta m hacer /* Bucle recorriendo los m sistemas */
xij = bij / Lii /* cálculo de la solución de la fila i para cada sistema j */
- Fin_para
- Para k=i+1 hasta n hacer /* Actualización de term.indep. del resto de filas */
- Para j=1 hasta m hacer /* para cada uno de los m sistemas */
bkj = bkj - Lki * xij
- Fin_para
- Fin_para
- Fin_para
2) Algoritmo de acceso por columnas :
Una variación del algoritmo consiste en realizar
el acceso por columnas. Así se procede a realizar la resolución
de un sistema de ecuaciones triangular inferior para cada uno
de los m sistemas. Fijado el sistema j, recorremos cada una de
las n filas, calculando la solución de la fila i, para
después actualizar los términos independientes del
resto de las filas. De esta forma el acceso a las matrices se
realiza por columnas, y el algoritmo parece más intuitivo,
sin que además sea más costoso.
- Para j=1 hasta m hacer /* Bucle recorriendo los m sistemas */
- Para i=1 hasta n hacer /* Bucle recorriendo las n filas para cada sistema j */
xij = bij / Lii /* cálculo de la solución de la fila i para el sistema j */
- Para k=i+1 hasta n hacer /* Actualización de term.indep. del resto de filas */
bkj = bkj - Lki * xij /* del sistema j */
- Fin_para
- Fin_para
- Fin_para
3) Algoritmo de acceso por filas con actualización concurrente de rangos fijos :
Veamos ahora como podemos introducir una versión
paralela del algoritmo 1. Una primera forma sería distribuyendo
el trabajo entre procesos por rangos de filas, de tal forma que
tendremos un proceso central que realiza el algoritmo 1, pero
con la variante de que la actualización de los términos
independientes se realiza por rangos. Se crea un proceso que trabaja
en un rango, actualizando los términos independientes de
dicho rango. Los procesos pueden trabajar de forma concurrente.
El proceso principal espera a que finalicen, antes de continuar
con el tratamiento de la siguiente fila. En este algoritmo el
trabajo es distribuido de forma estática, a priori, en
un número de procesos, con rangos fijos. El algoritmo sería
el siguiente :
- FilasTrabajo = n / num_procesos /* Rango de trabajo */
- Para i=1 hasta n hacer /* Bucle recorriendo las n filas */
- Para j=1 hasta m hacer /* Bucle recorriendo los m sistemas */
xij = bij / Lii /* cálculo de la solución de la fila i para cada sistema j */
- Fin_para
- t = 0
- Para kb=i+1 hasta n con incremento de FilasTrabajo hacer
- t = t + 1
- Crear Proceso t que ejecuta ProcesoCalculo(i, kb)
- Fin_para
- Esperar la finalización de los procesos : sincronización.
- Fin_para
ProcesoCalculo(i, kb) :
/* Actualización de los term.indep. del rango de filas [kb ... kb+FilasTrabajo] */
- Para k = kb hasta kb+FilasTrabajo ó n hacer
- Para j=1 hasta m hacer /* para cada uno de los m sistemas */
bkj = bkj - Lki * xij
- Fin_para
- Fin_para
4) Algoritmo de acceso por filas con actualización concurrente de rangos dinámicos :
A continuación presentamos un algoritmo semejante
al algoritmo 4 de acceso por filas, salvo que la actualización
de los rangos es dinámica, y los rangos de trabajo de cada
proceso no son fijos a priori. Las variaciones del algoritmo se
basan en la sincronización entre procesos, de tal forma
que el trabajo se distribuya uniformemente entre los procesos
libres. En este algoritmo el trabajo es distribuido de forma dinámica,
en un número de procesos, con rangos no fijos. El algoritmo
sería el siguiente :
- np = Numero de procesos.
- FilasTrabajo = n / np /* Rango de trabajo */
- Para i=1 hasta np hacer
- Bloquear acceso a bi
- Bloquear acceso a xi
- Crear Proceso i que ejecuta ProcesoCalculo(i)
- Fin_para
- Para i=1 hasta n hacer /* Bucle recorriendo las n filas */
- Para j=1 hasta m hacer /* Bucle recorriendo los m sistemas */
xij = bij / Lii /* cálculo de la solución de la fila i para cada sistema j */
- Fin_para
- Para j=1 hasta n hacer /* Bucle recorriendo las n filas */
Liberar el acceso a bj
- Fin_para
- Para j=1 hasta n hacer /* Bucle recorriendo las n filas */
Liberar el acceso a xj
- Fin_para
- Fin_para
- Esperar la finalización de los procesos :
sincronización.
ProcesoCalculo(h) :
/* Actualización de los term.indep. de forma dinámica */
- Para i = 1 hasta n hacer
- Solicitar acceso a bh
- Si h == 0
tmp = max_iter = n - i - (np-1)*((n-i)/np) - 1
k = i + 1
- sino
tmp = max_iter = (n - i) / np
k = i+1+n-i - (np-1)*((n-i)/np) -1 + (h-1)*((n-i)/np)
- Si max_iter == 0
Liberar acceso a xh
- sino
/* Actualizar términos independientes en el rango dinámico */
- Mientras max_iter>0 hacer
- Para j=1 hasta m hacer /* para cada uno de los m sistemas */
bkj = bkj - Lki * xij
- Fin_para
- Si max_iter == tmp
Liberar acceso a xh
k = k +1
max_iter = max_iter - 1
- Fin_para
Liberar acceso a xh
5) Algoritmo de acceso por columnas con actualización concurrente :
En este algoritmo la forma de distribución
del trabajo varía considerablemente. Para cada sistema
a resolver se crear un proceso diferente. De esta forma los procesos
trabajan de forma concurrente, cada uno resolviendo uno de los
m sistemas. Este algoritmo parece, también, bastante intuitivo
y fácil de entender, ya que es la extrapolación
natural del problema, aprovechando el paralelismo. El algoritmo
sería el siguiente :
- Para j=1 hasta m hacer /* Bucle recorriendo los m sistemas */
- Crear Proceso j que ejecuta ProcesoCalculo(j)
- Fin_para
- Esperar la finalización de los procesos :
sincronización.
ProcesoCalculo(j) :
/* Resolución del sistema j */
- Para i=0 hasta n hacer /* Recorrido de todas las filas del sistam j */
xij = bij / Aii /* Cálculo de la solución de la fila i */
- Para k=i+1 hasta n hacer /* Actualización de term.indep. del resto de filas*/
bkj = bkj - Aki * xij /* del sistema j */
- Fin_para
- Fin_para
A continuación se presentan dos ejemplos codificados en lenguaje C de resolución de matrices triangulares que corresponden a los algoritmos secuenciales 1 y 2 de acceso por filas y por columnas, respectivamente.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo secuencial de acceso por filas para la resolución de sistemas triangulares inferiores.
La función init_data, establece el valor del sistema a resolver, que en nuestro ejemplo es un sistema en el que aij = 2.5 para i<=j, y aij = 0.0 para i>j, mientras que b es una matriz creada mediante un sencillo cálculo. El sistema es un ejemplo simplemente demostrativo, aunque podría ser cualquier otro ejemplo, ya que esto no influye en la velocidad del algoritmo.
La sintaxis del programa es la siguiente :
tse [-?|-h] [tam_sistema [num_sistemas]] siendo :
El código para este caso se presenta a continuación :
TSE.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES (Alg. secuencial) Aplicacion: tse Version: 1.0h Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de sistemas triangulares de ecuaciones mediante un algoritmo secuencial. Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tse 1.0h - Solucion de sistemas triangulares (vers. secuencial)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [tam_sistema [num_sistemas]]\n"; #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" #ifndef HILOS /* Compilacion uniproceso, equivalente a los hilos */ #define HILOS #endif /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { int i,j,k; /* Variables temporales */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ /* Obtencion de argumentos */ GetArgs(argc, argv, &n, &nsist); /* Crear memoria compartida */ Datos = CrearMemoria(NULL, n, nsist); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* PROCEDIMIENTO DE CALCULO */ /* Bucle de filas */ for (i = 0; i<n; i++) { /* Calculo de la solucion de la fila i para cada sistema */ for (j = 0; j<nsist; j++) Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); /* Actualiza los terminos independientes para el resto de las filas */ for (k = i+1; k<n; k++) /* para cada uno de los sistemas */ for (j = 0; j<nsist; j++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria compartida */ DestruirMemoria(NULL, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); }
Este programa necesita también los ficheros de
cabecera GETARGS.H, GETSTATS.H, ERROR.H, PARAM.H
y los ficheros fuente GETARGS.C, GETSTATS.C y ERROR.C,
empleados también en otros ejemplos, y que se encuentran
en la biblioteca de rutinas empleada por los ejemplos.
El fichero Makefile necesario para compilación se presenta en el siguiente ejemplo, ya que es válido para ambos casos.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo secuencial de acceso por columnas para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar al ejemplo anterior. El sistema es un ejemplo simplemente demostrativo, aunque podría ser cualquier otro ejemplo, ya que esto no influye en la velocidad del algoritmo.
La sintaxis del programa es la siguiente :
tse_sm [-?|-h] [tam_sistema [num_sistemas]] siendo :
El código para este caso se presenta a continuación :
TSE_SM.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES (Alg. secuencial) Aplicacion: tse_sm Version: 1.0h Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de sistemas triangulares de ecuaciones mediante un algoritmo secuencial. Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tse_sm 1.0h - Solucion de sistemas triangulares (vers. secuencial)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [tam_sistema [num_sistemas]]\n"; #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" #ifndef HILOS /* Compilacion uniproceso, equivalente a los hilos */ #define HILOS #endif /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { int i,j,k; /* Variables temporales */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ /* Obtencion de argumentos */ GetArgs(argc, argv, &n, &nsist); /* Crear memoria compartida */ Datos = CrearMemoria(NULL, n, nsist); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* PROCEDIMIENTO DE CALCULO */ /* Bucle de sistemas */ for (j = 0; j<nsist; j++) { /* Bucle de filas, para cada sistema j */ for (i = 0; i<n; i++) { Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); for (k = i+1; k<n; k++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); } } /* Obtener tiempos finales */ getestad(&estad[1]); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria compartida */ DestruirMemoria(NULL, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); }
Además este programa necesita de los ficheros
de cabecera PARAM.H, ERROR.H, GETARGS.H y GETSTATS.H,
junto con los ficheros fuente ERROR.C, GETARGS.C y
GETSTATS.C empleados en ejemplos anteriores,
y que se encuentra en la biblioteca de rutinas.
El fichero Makefile, necesario para la compilación de los dos ejemplos correspondientes a los algoritmos secuenciales anteriores, es el siguiente :
############## ## Makefile ## ############## #DEFS=-DDEBUG -DWITH_TIMES -DHILOS DEFS=-DHILOS INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libproc OBJ=$(OBJDIR)/getstats.o $(OBJDIR)/getargsh.o $(OBJDIR)/error.o CC=gcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) #Definicion de dependencias all: tse tse_sm .c.o: $(CC) $(CFLAGS) -c $< tse: tse.o $(CC) $(LINK) tse.o -o tse tse_sm: tse_sm.o $(CC) $(LINK) tse_sm.o -o tse_sm
A continuación se presentan las versiones codificadas en lenguaje C de los algoritmos de resolución de sistemas triangulares inferiores anteriormente presentados, en su versión paralela, codificados empleando programación multiproceso.
En todos los ejemplos se emplea memoria compartida (gestionada por el núcleo) según la especificación de UNIX System V, y en esta memoria se almacenan todos los datos de los sistemas : matrices A, x y b del sistema triangular A.x=b.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo paralelo de acceso por filas con actualización mediante rangos fijos, para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar a los ejemplos anteriores, aunque ahora podemos indicar el número de procesos entre los que vamos a repartir el trabajo de actualización de los términos independientes. A cada proceso hijo se le asigna un rango de filas de trabajo proporcional : FilasTrabajo = n/num_hijos. Los procesos hijos se crean mediante la primitiva fork() de UNIX, y ejecutan la rutina de actualización. Los procesos se ejecutan de forma concurrente. En cada iteración de una fila, se crean los procesos de trabajo, se espera a que finalicen y se continua con una nueva iteración. El sistema es un ejemplo simplemente demostrativo.
La sintaxis del programa es la siguiente :
tsep_pb [-?|-h] [num_hijos [tam_sistema [num_sistemas]]] siendo :
El código para este caso se presenta a continuación :
TSEP_PB.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES (ver.Procesos) Aplicacion: tsep_pb Version: 1.0p Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de un sistema triangular de ecuaciones. Se crea un proceso hijo por cada uno de los tramos para actualizar los term.indep. Implementacion empleando procesos. Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tsep_pb 1.0p - Solucion de sistemas triangulares (vers. procesos)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [num_hijos [tam_sistema [num_sistemas]]]\n"; #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; /* Funcion de calculo para cada hijo */ void *CalcularProducto(void *arg); int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ int FilasTrabajo; /* Filas de trabajo para cada hijo */ int nhijos; /* Numero de hijos de trabajo */ /* Estructura de datos de los argumentos para el calculo */ typedef struct s_arg_t { int fila; /* Fila de trabajo para el hijo */ int ambito; /* Longitud del trabajo para el hijo */ } arg_t; /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pid_t *hijo_id; /* Vector de Identificadores de los hijos */ arg_t *argh; /* Vector de argumentos para los hijos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int ch; /* Contador de hijos */ int i,j,k; /* Variables temporales */ int kb; /* Variable temporal */ int shmem_id[4]; /* Identif. para la zona de memoria compartida */ /* Obtencion de argumentos */ GetArgs2(argc, argv, &n, &nsist, &nhijos); FilasTrabajo = n/nhijos; /* Crear memoria compartida */ Datos = CrearMemoria(shmem_id, n, nsist); /* Crear memoria para los identificadores y argumentos de los hijos */ if ( (hijo_id = (pid_t *) malloc(nhijos*sizeof(pid_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los hijos"); if ( (argh = (arg_t *) malloc(nhijos*sizeof(arg_t))) == NULL ) ErrorFatal("No hay memoria para crear los argumentos de los hijos"); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* PROCEDIMIENTO DE CALCULO */ /* Bucle sobre las filas */ for (i = 0; i<n; i++) { /* Calculo de la solucion de la fila i, para cada uno de los sistemas */ for (j = 0; j<nsist; j++) Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); /* Creamos un proceso de trabajo por cada tramo FilasTrabajo, para actualizar los terminos independientes del resto de la filas */ for (kb = i+1, ch=0; kb<n; kb += FilasTrabajo, ch++ ) { argh[ch].fila = i; argh[ch].ambito = kb; switch ( (hijo_id[ch] = fork()) ) { /* No se pudo crear hijo */ case -1: ErrorFatal("No se pudo crear hijo para realizar la tarea"); break; /* Proceso HIJO */ case 0: CalcularProducto( (void *)&argh[ch] ); exit(0); break; /* Proceso PADRE */ default: break; } } /* Esperamos la finalizacion del trabajo */ for (kb = i+1, ch=0; kb<n; kb += FilasTrabajo, ch++ ) if (waitpid(hijo_id[ch], NULL, 0)<0) ErrorFatal("Error en la espera de un hijo de trabajo"); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria de los identificadores y argumentos de los hijos */ free((void *)hijo_id); free((void *)argh); /* Destruir memoria compartida */ DestruirMemoria(shmem_id, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); } /* Procedimiento para la actualizacion de term.indep. del rango de trabajo */ void *CalcularProducto(void *arg) { int i = ((arg_t *)arg)->fila; int kb = ((arg_t *)arg)->ambito; int j, k; for (k = kb; k<kb+FilasTrabajo && k<n; k++) { /* Para cada sistema se actualiza el termino independiente */ for (j = 0; j<nsist; j++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); } return ((void *)0); }
Además este programa necesita de los ficheros de cabecera PARAM.H, ERROR.H, GETARGS.H y GETSTATS.H, junto con los ficheros fuente ERROR.C, GETARGS.C y GETSTATS.C empleados en ejemplos anteriores, y que pertenecen a la biblioteca de rutinas que acompaña a los ejemplos.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo paralelo de acceso por filas con actualización mediante rangos no fijos, para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar al ejemplo anterior, excepto que los procesos necesitan sincronización, que se consigue mediante mútex, implementados mediante semáforos como se ha visto en otros ejemplos. Sin embargo, ya que los semáforos no son totalmente seguros, la ejecución correcta de la aplicación no está garantizada. Los procesos hijos se crean mediante la primitiva fork() de UNIX, y ejecutan la rutina de actualización. Los procesos se ejecutan de forma concurrente.
La sintaxis del programa es la siguiente :
tsep_procs [-?|-h] [num_hijos [tam_sistema [num_sistemas]]] siendo :
El código para este caso se presenta a continuación :
TSEP_PROCS.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES (vers.Procesos) Aplicacion: tse_procs Version: 1.0p Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de un sistema triangular de ecuaciones empleando hijos y sincronizacion. Implementacion empleando procesos. Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tsep_procs 1.0p - Solucion de sistemas triangulares (vers. Procesos-mutex)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [num_hijos [tam_sistema [num_sistemas]]]\n"; #include <stdio.h> #include <math.h> #include "mutex.h" #include "error.h" #include "getargs.h" #include "getstats.h" /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; /* Funcion de calculo para cada hijo */ void *Calcular(void *arg); int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ int FilasTrabajo; /* Filas de trabajo para cada hijo */ int nhijos; /* Numero de hijos de trabajo */ /* Definicion de identificadores de recursos del sistema */ #define SHMEM_MUTEX0_KEY ((key_t)188860L) #define SHMEM_MUTEX1_KEY ((key_t)188861L) #define SHMEM_MUTEX2_KEY ((key_t)188862L) #define MUTEX_BASE_KEY ((key_t)188863L) /* Estructura de datos de memoria compartida sobre mutex de acceso */ typedef struct s_datosm_t { mutex_t *mutex_b; /* Vector de mutex de acceso a la matriz b */ mutex_t *mutex_x; /* Vector de mutex de acceso a la matriz x */ } datosm_t; /* Datos sobre mutex en memoria compartida */ datosm_t *Datosm; /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { int i,j,k; /* Variables temporales */ pid_t *hijo_id; /* Vector de Identificadores de los hijos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int shmem_id[4]; /* Identif. para la zona de memoria compartida */ int shmem_idm[3]; /* Identificador para memoria compartida de mutex */ /* Obtencion de argumentos */ GetArgs2(argc, argv, &n, &nsist, &nhijos); FilasTrabajo = n/nhijos; /* Crear memoria compartida */ Datos = CrearMemoria(shmem_id, n, nsist); /* Crear memoria para los identificadores de los hijos */ if ( (hijo_id = (pid_t *) malloc(nhijos * sizeof(pid_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los hijos"); /* Crear memoria compartida para mutex */ if ((shmem_idm[0] = shmget(SHMEM_MUTEX0_KEY, sizeof(datosm_t), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida"); if ((Datosm = (datosm_t *) shmat(shmem_idm[0], (char *)0, 0)) == (datosm_t *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); if ((shmem_idm[1] = shmget(SHMEM_MUTEX1_KEY, nhijos*sizeof(mutex_t), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida"); if ((Datosm->mutex_b = (mutex_t *) shmat(shmem_idm[1], (char *)0, 0)) == (mutex_t *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); if ((shmem_idm[2] = shmget(SHMEM_MUTEX2_KEY, nhijos*sizeof(mutex_t), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida"); if ((Datosm->mutex_x = (mutex_t *) shmat(shmem_idm[2], (char *)0, 0)) == (mutex_t *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* Creacion de hijos e inicializacion de mutex */ for (i = 0; i<nhijos; i++) { mutex_init(&Datosm->mutex_b[i], MUTEX_BASE_KEY+i); mutex_lock(&Datosm->mutex_b[i]); mutex_init(&Datosm->mutex_x[i], MUTEX_BASE_KEY+nhijos+i); mutex_lock(&Datosm->mutex_x[i]); switch ( (hijo_id[i] = fork()) ) { /* No se pudo crear hijo */ case -1: ErrorFatal("No se pudo crear hijo para realizar la tarea"); break; /* Proceso HIJO */ case 0: Calcular( (void *)i ); exit(0); break; /* Proceso PADRE */ default: break; } } /* PROCEDIMIENTO DE CALCULO */ /* Bucle sobre las filas */ for (i = 0; i<n; i++) { /* Calculo de la solucion de la fila i, para cada uno de los sistemas */ for (j = 0; j<nsist; j++) Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); /* Liberamos los mutex de acceso a b para cada hijo */ for (j = 0; j<nhijos; j++) if (mutex_unlock(&Datosm->mutex_b[j])<0) ErrorFatal("Error en el desbloqueo del mutex_b"); /* Bloqueamos el acceso a x para cada hijo */ for (j = 0; j<nhijos; j++) if (mutex_lock(&Datosm->mutex_x[j])<0) ErrorFatal("Error en el bloqueo del mutex_x"); } /* Esperamos la finalizacion de los trabajos */ for (i = 0; i<nhijos; i++) if (waitpid(hijo_id[i], NULL, 0)<0) ErrorFatal("Error en la espera de un hijo"); /* Obtener tiempos finales */ getestad(&estad[1]); /* Destruccion de recursos */ for (i = 0; i<nhijos; i++) { mutex_destroy(&Datosm->mutex_b[i]); mutex_destroy(&Datosm->mutex_x[i]); } /* Destruir memoria compartida */ if ( shmdt((char *)Datosm->mutex_x) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_idm[2], IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); if ( shmdt((char *)Datosm->mutex_b) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_idm[1], IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); if ( shmdt((char *)Datosm) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_idm[0], IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria de los identificadores de los hijos */ free((void *)hijo_id); /* Destruir memoria compartida */ DestruirMemoria(shmem_id, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); } /* Procedimiento para actualizacion de los term.indep. del rango de trabajo */ void *Calcular(void *arg) { int i, j, k; int max_iter, tmp; int nhijo = (int)arg; /* Para cada una de las filas */ for (i = 0; i<n; i++) { /* Bloqueo el acceso al termino independiente b */ if (mutex_lock(&Datosm->mutex_b[nhijo])<0) ErrorFatal("Error en el bloqueo del mutex_b"); if (nhijo == 0) { tmp = max_iter = n - i - (nhijos-1)*((n-i)/nhijos) - 1; k = i + 1; } else { tmp = max_iter = (n - i) / nhijos; k = i+1+n-i - (nhijos-1)*((n-i)/nhijos) -1 + (nhijo-1)*((n-i)/nhijos); } if (max_iter == 0) { if (mutex_unlock(&Datosm->mutex_x[nhijo])<0) ErrorFatal("Error en el desbloqueo del mutex_x"); } else { for (; max_iter>0; k++, max_iter--) { for (j = 0; j<nsist; j++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); if (max_iter == tmp) if (mutex_unlock(&Datosm->mutex_x[nhijo])<0) ErrorFatal("Error en el desbloqueo del mutex_x"); } } } /* Libero el acceso a la matriz x */ if (mutex_unlock(&Datosm->mutex_x[nhijo])<0) ErrorFatal("Error en el desbloqueo del mutex_x"); return((void *)0); }
Además este programa necesita de los ficheros de cabecera PARAM.H, ERROR.H, GETARGS.H, GETSTATS.H, MUTEX.H y SEMAFORO.H, junto con los ficheros fuente ERROR.C, GETARGS.C, GETSTATS.C, MUTEX.C y SEMAFORO.C empleados en ejemplos anteriores y que se encuentran en la biblioteca de rutinas comunes a todos los ejemplos.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo paralelo de acceso por columnas con actualización concurrente, para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar al ejemplo anterior. Se crea un proceso hijo por cada uno de los sistemas a resolver. Los procesos hijos se crean mediante la primitiva fork() de UNIX, y ejecutan la rutina de actualización. Los procesos se ejecutan de forma concurrente.
La sintaxis del programa es la siguiente :
tsep_m [-?|-h] [tam_sistema [num_sistemas]] siendo :
El código para este caso se presenta a continuación :
TSEP_M.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES (ver. Procesos) Aplicacion: tsep_m Version: 1.0p Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de un sistema triangular de ecuaciones mediante un algoritmo secuencial. Se crea un proceso por cada uno de los sistemas a resolver. Implementacion empleando procesos. Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tsep_m 1.0p - Solucion de sistemas triangulares (vers.procesos)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [tam_sistema [num_sistemas]]\n"; #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; /* Funcion de calculo para cada hilo */ void *CalcularSistema(void *arg); int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pid_t *hijo_id; /* Vector de Identificadores de los hijos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int i,j,k; /* Variables temporales */ int shmem_id[4]; /* Identif. para la zona de memoria compartida */ /* Obtencion de argumentos */ GetArgs(argc, argv, &n, &nsist); /* Crear memoria compartida */ Datos = CrearMemoria(shmem_id, n, nsist); /* Crear memoria para los identificadores de los hijos */ if ( (hijo_id = (pid_t *) malloc(nsist*sizeof(pid_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los hijos"); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* PROCEDIMIENTO DE CALCULO */ /* Para cada sistema creamos un hijo de trabajo */ for (j = 0; j<nsist; j++) { switch ( (hijo_id[j] = fork()) ) { /* No se pudo crear hijo */ case -1: ErrorFatal("No se pudo crear hijo para realizar la tarea"); break; /* Proceso HIJO */ case 0: CalcularSistema( (void *)j ); exit(0); break; /* Proceso PADRE */ default: break; } } /* Esperamos la finalizacion del trabajo */ for (j = 0; j<nsist; j++ ) { if (waitpid(hijo_id[j], NULL, 0)<0) ErrorFatal("Error en la espera de un hijo de trabajo"); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria de los identificadores de los hijos */ free((void *)hijo_id); /* Destruir memoria compartida */ DestruirMemoria(shmem_id, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); } /* Procedimiento para la resolucion del sistema j */ void *CalcularSistema(void *arg) { int j = (int)arg; int i, k; for (i = 0; i<n; i++) { Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); for (k = i+1; k<n; k++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); } return ((void *)0); }
Además este programa necesita de los ficheros
de cabecera PARAM.H, ERROR.H, GETARGS.H y GETSTATS.H,
junto con los ficheros fuente ERROR.C, GETARGS.C y
GETSTATS.C empleados en ejemplos anteriores,
y que pertenecen a la biblioteca de rutinas comunes a los ejemplos.
Finalmente, a continuación se presenta el fichero Makefile que permite la compilación de los ejemplos anteriores de resolución de sistemas triangulares mediante procesos :
############## ## Makefile ## ############## #DEFS=-DDEBUG -DWITH_TIMES INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libproc OBJ=$(OBJDIR)/getstats.o $(OBJDIR)/getargs.o $(OBJDIR)/error.o OBJP=$(OBJDIR)/semaforo.o $(OBJDIR)/mutex.o CC=gcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) LINKP=$(LINK) $(OBJP) #Definicion de dependencias all: tsep_pb tsep_procs tsep_m .c.o: $(CC) $(CFLAGS) -c $< tsep_pb: tsep_pb.o $(CC) $(LINK) tsep_pb.o -o tsep_pb tsep_procs: tsep_procs.o $(CC) $(LINKP) tsep_procs.o -o tsep_procs tsep_m: tsep_m.o $(CC) $(LINK) tsep_m.o -o tsep_m tsep_pb.o: tsep_pb.c tsep_procs.o: tsep_procs.c tsep_m.o: tsep_m.c
A continuación se presentan las versiones codificadas en lenguaje C de los algoritmos de resolución de sistemas triangulares inferiores anteriormente presentados, en su versión paralela, codificados empleando programación multihilo.
Este ejemplo es prácticamente el mismo que
el caso anterior, excepto que ahora se han implementado los programas
mediante hilos en vez de procesos. Para ello se ha utilizado la
librería Pthreads del paquete de hilos de Chris Provenzano,
como en los ejemplos anteriores, aunque es muy posible que el
programa funcione igualmente con cualquier otro paquete que siga
el estándar POSIX.1c sobre hilos, ya que solo se han empleado
funciones del estándar. El programa ha sido compilado y
ejecutado con dicho paquete instalado bajo el sistema operativo
Linux 1.2 y 2.0.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo paralelo de acceso por filas con actualización mediante rangos fijos, para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar a los ejemplos anteriores, y de esta forma podemos indicar el número de hilos entre los que vamos a repartir el trabajo de actualización de los términos independientes. A cada hilo de trabajo se le asigna un rango de filas de trabajo proporcional : FilasTrabajo = n/num_hilos. Los hilos se crean mediante la primitiva pthread_create(), y ejecutan la rutina de actualización. Los hilos se ejecutan de forma concurrente, y comparten el espacio de direcciones con sus variables globales. En cada iteración de una fila, se crean los hilos de trabajo, se espera a que finalicen y se continua con una nueva iteración. El sistema es un ejemplo simplemente demostrativo.
La sintaxis del programa es la siguiente :
tse_pb [-?|-h] [num_hilos [tam_sistema [num_sistemas]]] siendo :
El código para este caso se presenta a continuación :
TSE_PB.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES Aplicacion: tse_pb Version: 1.0h Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de un sistema triangular de ecuaciones. Se crea un hilo por cada uno de los tramos fijo para actualizar los term.indep. El programa emplea las rutinas de la libreria Pthreads, que es compatible POSIX.1c Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tse_pb 1.0h - Solucion de sistemas triangulares (vers. hilos)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [num_hilos [tam_sistema [num_sistemas]]]\n"; #include <pthread.h> #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; /* Funcion de calculo para cada hilo */ void *CalcularProducto(void *arg); int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ int FilasTrabajo; /* Filas de trabajo para cada hilo */ int nhilos; /* Numero de hilos de trabajo */ /* Estructura de datos de los argumentos para el calculo */ typedef struct s_arg_t { int fila; /* Fila de trabajo para el hilo */ int ambito; /* Longitud del trabajo para el hilo */ } arg_t; /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pthread_t *hilo_id; /* Vector de Identificadores de los hilos */ arg_t *argh; /* Vector de argumentos para los hilos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int ch; /* Contador de hilos */ int i,j,k; /* Variables temporales */ int kb; /* Obtencion de argumentos */ GetArgs2(argc, argv, &n, &nsist, &nhilos); FilasTrabajo = n/nhilos; /* Crear memoria compartida */ Datos = CrearMemoria(NULL, n, nsist); /* Crear memoria para los identificadores y argumentos de los hilos */ if ( (hilo_id = (pthread_t *) malloc(nhilos*sizeof(pthread_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los hilos"); if ( (argh = (arg_t *) malloc(nhilos*sizeof(arg_t))) == NULL ) ErrorFatal("No hay memoria para crear los argumentos de los hilos"); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* PROCEDIMIENTO DE CALCULO */ /* Bucle sobre las filas */ for (i = 0; i<n; i++) { /* Calculo de la solucion de la fila i, para cada uno de los sistemas */ for (j = 0; j<nsist; j++) Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); /* Creamos un hilo de trabajo por cada tramo FilasTrabajo, para actualizar los terminos independientes del resto de la filas */ for (kb = i+1, ch=0; kb<n; kb += FilasTrabajo, ch++ ) { argh[ch].fila = i; argh[ch].ambito = kb; if (pthread_create(&hilo_id[ch], NULL, CalcularProducto, (void *)&argh[ch] )<0) ErrorFatal("Error en la creacion de un hilo de trabajo"); } /* Esperamos la finalizacion del trabajo */ for (kb = i+1, ch=0; kb<n; kb += FilasTrabajo, ch++ ) if (pthread_join(hilo_id[ch], NULL)<0) ErrorFatal("Error en la espera de un hilo de trabajo"); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria de los identificadores y argumentos de los hijos */ free((void *)hilo_id); free((void *)argh); /* Destruir memoria compartida */ DestruirMemoria(NULL, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); } /* Procedimiento para actualizacion de los term.indep. del rango de trabajo */ void *CalcularProducto(void *arg) { int i = ((arg_t *)arg)->fila; int kb = ((arg_t *)arg)->ambito; int j, k; for (k = kb; k<kb+FilasTrabajo && k<n; k++) { /* Para cada sistema se actualiza el termino independiente */ for (j = 0; j<nsist; j++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); } pthread_exit(0); }
Además este programa necesita de los ficheros
de cabecera PARAM.H, ERROR.H, GETARGS.H y GETSTATS.H,
junto con los ficheros fuente ERROR.C, GETARGS.C y
GETSTATS.C empleados en ejemplos anteriores,
y que se encuentran en la biblioteca de rutinas comunes a todos
los ejemplos.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo paralelo de acceso por filas con actualización mediante rangos no fijos, para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar al ejemplo anterior, excepto que los hilos necesitan sincronización, que se consigue mediante mutex, implementados mediante la librería Pthread. Los hilos se ejecutan de forma concurrente.
La sintaxis del programa es la siguiente :
tse_procs [-?|-h] [num_hilos [tam_sistema [num_sistemas]]] siendo :
El código para este caso se presenta a continuación :
TSE_PROCS.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES Aplicacion: tse_procs Version: 1.0h Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de un sistema triangular de ecuaciones empleando hilos y sincronizacion. El programa emplea las rutinas de la libreria Pthreads, que es compatible POSIX.1c Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tse_procs 1.0h - Solucion de sistemas triangulares (vers. hilos-mutex)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [num_hilos [tam_sistema [num_sistemas]]]\n"; #include <pthread.h> #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; /* Funcion de calculo para cada hilo */ void *Calcular(void *arg); int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ int FilasTrabajo; /* Filas de trabajo para cada hilo */ int nhilos; /* Numero de hilos de trabajo */ pthread_mutex_t *mutex_b; /* Vector de mutex de acceso a la matriz b */ pthread_mutex_t *mutex_x; /* Vector de mutex de acceso a la matriz x */ /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pthread_t *hilo_id; /* Vector de Identificadores de los hilos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int i,j,k; /* Variables temporales */ /* Obtencion de argumentos */ GetArgs2(argc, argv, &n, &nsist, &nhilos); FilasTrabajo = n/nhilos; /* Crear memoria compartida */ Datos = CrearMemoria(NULL, n, nsist); /* Crear memoria para los identificadores de los hilos */ if ( (hilo_id = (pthread_t *) malloc(nhilos * sizeof(pthread_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los hilos"); /* Creacion de recursos */ if ((mutex_b = (pthread_mutex_t *) malloc(nhilos * sizeof(pthread_mutex_t)))== NULL) ErrorFatal("No existe memoria suficiente para los mutex_b"); if ((mutex_x = (pthread_mutex_t *) malloc(nhilos * sizeof(pthread_mutex_t)))== NULL) ErrorFatal("No existe memoria suficiente para los mutex_x"); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* Creacion de hilos e inicializacion de mutex */ for (i = 0; i<nhilos; i++) { pthread_mutex_init(&mutex_b[i], NULL); pthread_mutex_lock(&mutex_b[i]); pthread_mutex_init(&mutex_x[i], NULL); pthread_mutex_lock(&mutex_x[i]); if (pthread_create(&hilo_id[i], NULL, Calcular, (void *)i)<0) ErrorFatal("Error en la creacion de un hilo de trabajo"); } /* PROCEDIMIENTO DE CALCULO */ /* Bucle sobre las filas */ for (i = 0; i<n; i++) { /* Calculo de la solucion de la fila i, para cada uno de los sistemas */ for (j = 0; j<nsist; j++) Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); /* Liberamos los mutex de acceso a b para cada hilo */ for (j = 0; j<nhilos; j++) if (pthread_mutex_unlock(&mutex_b[j])<0) ErrorFatal("Error en el desbloqueo del mutex_b"); /* Bloqueamos el acceso a x para cada hilo */ for (j = 0; j<nhilos; j++) if (pthread_mutex_lock(&mutex_x[j])<0) ErrorFatal("Error en el bloqueo del mutex_x"); } /* Esperamos la finalizacion de los trabajos */ for (i = 0; i<nhilos; i++) if (pthread_join(hilo_id[i], NULL)<0) ErrorFatal("Error en la espera de un hilo"); /* Obtener tiempos finales */ getestad(&estad[1]); /* Destruccion de recursos */ for (i = 0; i<nhilos; i++) { pthread_mutex_destroy(&mutex_b[i]); pthread_mutex_destroy(&mutex_x[i]); } free((void *)mutex_b); free((void *)mutex_x); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria de los identificadores de los hijos */ free((void *)hilo_id); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); } /* Procedimiento para actualizacion de los term.indep. del rango de trabajo */ void *Calcular(void *arg) { int i, j, k; int max_iter, tmp; int nhilo = (int)arg; /* Para cada una de las filas */ for (i = 0; i<n; i++) { /* Bloqueo el acceso al termino independiente b */ if (pthread_mutex_lock(&mutex_b[nhilo])<0) ErrorFatal("Error en el bloqueo del mutex_b"); if (nhilo == 0) { tmp = max_iter = n - i - (nhilos-1)*((n-i)/nhilos) - 1; k = i + 1; } else { tmp = max_iter = (n - i) / nhilos; k = i+1+n-i - (nhilos-1)*((n-i)/nhilos) -1 + (nhilo-1)*((n-i)/nhilos); } if (max_iter == 0) { if (pthread_mutex_unlock(&mutex_x[nhilo])<0) ErrorFatal("Error en el desbloqueo del mutex_x"); } else { for (; max_iter>0; k++, max_iter--) { for (j = 0; j<nsist; j++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); if (max_iter == tmp) if (pthread_mutex_unlock(&mutex_x[nhilo])<0) ErrorFatal("Error en el desbloqueo del mutex_x"); } } } /* Libero el acceso a la matriz x */ if (pthread_mutex_unlock(&mutex_x[nhilo])<0) ErrorFatal("Error en el desbloqueo del mutex_x"); pthread_exit(0); }
Además este programa necesita de los ficheros
de cabecera PARAM.H, ERROR.H, GETARGS.H, GETSTATS.H,
junto con los ficheros fuente ERROR.C, GETARGS.C, y
GETSTATS.C empleados en ejemplos anteriores,
y que como siempre se pueden encontrar en la biblioteca de rutinas
comunes a todos los ejemplos.
Este ejemplo corresponde a la codificación en lenguaje C del algoritmo paralelo de acceso por columnas con actualización concurrente, para la resolución de sistemas triangulares inferiores.
El funcionamiento del programa es similar al ejemplo anterior. Se crea un proceso hijo por cada uno de los sistemas a resolver. Los procesos hijos se crean mediante la primitiva fork() de UNIX, y ejecutan la rutina de actualización. Los procesos se ejecutan de forma concurrente.
La sintaxis del programa es la siguiente :
tse_m [-?|-h] [tam_sistema [num_sistemas]] siendo :
El código para este caso se presenta a continuación :
TSE_M.C :
/**************************************************************************** EJEMPLO DE SOLUCION DE UN SISTEMA TRIANGULAR DE ECUACIONES Aplicacion: tse_m Version: 1.0h Fecha: 10/12/1996 Descripcion: Programa demostrativo de la resolucion de un sistema triangular de ecuaciones mediante un algoritmo secuencial. Se crea un hilo por cada uno de los sistemas a resolver. El programa emplea las rutinas de la libreria Pthreads, que es compatible POSIX.1c Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="tse_m 1.0h - Solucion de sistemas triangulares (vers. hilos)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [tam_sistema [num_sistemas]]\n"; #include <pthread.h> #include <stdio.h> #include <math.h> #include "error.h" #include "getargs.h" #include "getstats.h" /* Datos compartidos de los sistemas para todos los procesos */ datos_t *Datos; /* Funcion de calculo para cada hilo */ void *CalcularSistema(void *arg); int n, nsist; /* Tamano del sistema y no. de sistemas a resolver */ /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pthread_t *hilo_id; /* Vector de Identificadores de los hilos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int i,j,k; /* Variables temporales */ /* Obtencion de argumentos */ GetArgs(argc, argv, &n, &nsist); /* Crear memoria compartida */ Datos = CrearMemoria(NULL, n, nsist); /* Crear memoria para los identificadores de los hilos */ if ( (hilo_id = (pthread_t *) malloc(nsist*sizeof(pthread_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los hilos"); /* Inicializacion de los datos del sistema */ init_data(Datos, n, nsist); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* PROCEDIMIENTO DE CALCULO */ /* Para cada sistema creamos un hilo de trabajo */ for (j = 0; j<nsist; j++) { if (pthread_create(&hilo_id[j], NULL, CalcularSistema, (void *)j) <0 ) ErrorFatal("Error en la creacion de un hilo de trabajo"); } /* Esperamos la finalizacion del trabajo */ for (j = 0; j<nsist; j++ ) { if (pthread_join(hilo_id[j], NULL)<0) ErrorFatal("Error en la espera de un hilo de trabajo"); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Imprimir las soluciones */ PrintSolucion(Datos, n, nsist); /* Destruir memoria de los identificadores de los hilos */ free((void *)hilo_id); /* Destruir memoria compartida */ DestruirMemoria(NULL, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); } /* Procedimiento para la resolucion del sistema j */ void *CalcularSistema(void *arg) { int j = (int)arg; int i, k; for (i = 0; i<n; i++) { Datos->x(i,j) = Datos->b(i,j)/Datos->A(i,i); for (k = i+1; k<n; k++) Datos->b(k,j) -= Datos->A(k,i) * Datos->x(i,j); } pthread_exit(0); }
Además este programa necesita de los ficheros
de cabecera PARAM.H, ERROR.H, GETARGS.H, GETSTATS.H,
junto con los ficheros fuente ERROR.C, GETARGS.C y
GETSTATS.C empleados en ejemplos anteriores.
Finalmente, a continuación se presenta el fichero Makefile que permite la compilación de los ejemplos de resolución de sistemas triangulares mediante hilos :
############## ## Makefile ## ############## #DEFS=-DDEBUG -DWITH_TIMES -DHILOS DEFS=-DHILOS INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libpthread OBJ=$(OBJDIR)/getstats.o $(OBJDIR)/getargs.o $(OBJDIR)/error.o CC=pgcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) #Definicion de dependencias all: tse_pb tse_procs tse_m .c.o: $(CC) $(CFLAGS) -c $< tse_pb: tse_pb.o $(CC) $(LINK) tse_pb.o -o tse_pb tse_procs: tse_procs.o $(CC) $(LINK) tse_procs.o -o tse_procs tse_m: tse_m.o $(CC) $(LINK) tse_m.o -o tse_m tse_pb.o: tse_pb.c tse_procs.o: tse_procs.c tse_m.o: tse_m.c
Las dos implementaciones (procesos e hilos) de los
algoritmos paralelos para la resolución de sistemas de
ecuaciones lineales con matriz de coeficientes triangular inferior,
son prácticamente idénticas, como se habrá
observado en los listados del código fuente, no solo conceptualmente
sino a nivel de programación.
Como referencia para discutir las ventajas e inconvenientes
de las diferentes implementaciones : multihilo y procesos,
se indican los siguientes tiempos de ejecución obtenidos
como muestra en un sistema formado por una CPU Intel 486-66Mhz
- 9Mb RAM - Linux 1.2.13, y con carga mínima en el sistema.
En el sistema se ejecutaron las dos versiones de cada programa,
repitiendo la prueba en 5 ocasiones para cada uno de los programas.
Todos los tiempos están expresados en milisegundos.
1) Para el caso de los
programas correspondientes al algoritmo de acceso por filas con
actualización concurrente de rangos fijos, se ha realizado
la comparativa siguiente entre la versión de procesos (TSEP_PB)
y la versión multihilo (TSE_PB).
El primer cuadro comparativo se realizó con los siguientes parámetros :
MUESTRAS | ||||||
Hilos T. Usuario | ||||||
Hilos T. Kernel | ||||||
Hilos T. Real | ||||||
Hilos Faltas Página | ||||||
Proc.T. Usuario | ||||||
Proc.T. Kernel | ||||||
Proc.T. Real | ||||||
Proc. Faltas Página |
El segundo cuadro comparativo se realizó con los siguientes parámetros :
MUESTRAS | ||||||
Hilos T. Usuario | ||||||
Hilos T. Kernel | ||||||
Hilos T. Real | ||||||
Hilos Faltas Página | ||||||
Proc.T. Usuario | ||||||
Proc.T. Kernel | ||||||
Proc.T. Real | ||||||
Proc. Faltas Página |
En ambos cuadros se observa que la versión multihilo produce
un número de faltas de página considerablemente
inferior a la versión de procesos. Además se observa
una gran diferencia en el tiempo de programa en modo usuario y
en modo sistema entre ambas versiones, que entre otras cosas puede
deberse a la utilización de memoria compartida, gestionada
por el kernel, en la versión de procesos. Sin duda parece
claro que la versión multihilo es bastante más rápida
en ejecución que la versión de procesos.
2) Para el caso de los programas correspondientes al algoritmo
de acceso por columnas con actualización concurrente, se
ha realizado la comparativa siguiente entre la versión
de procesos (TSEP_M) y la versión multihilo (TSE_M).
El cuadro comparativo se realizó con los siguientes parámetros :
MUESTRAS | ||||||
Hilos T. Usuario | ||||||
Hilos T. Kernel | ||||||
Hilos T. Real | ||||||
Hilos Faltas Página | ||||||
Proc.T. Usuario | ||||||
Proc.T. Kernel | ||||||
Proc.T. Real | ||||||
Proc. Faltas Página |
En este caso se puede observar que ambas versiones producen un número de faltas de página similar. Sin embargo se sigue observando una gran diferencia en el tiempo de programa en modo usuario y en modo sistema entre ambas versiones, que entre otras cosas puede deberse a la utilización de memoria compartida, gestionada por el kernel, en la versión de procesos. Por otro lado aunque la versión multihilo es ligeramente más rápida en ejecución que la versión de procesos, las diferencias de velocidad no son tan notables.
Sí parece claro que en todo caso, la versión multihilo,
logra disminuir de forma considerable el tiempo del proceso en
modo kernel, lo cual siempre es importante.
Inconvenientes de la versión de procesos :
Ventajas de la versión de procesos :
Inconvenientes de la versión multihilo :
Ventajas de la versión multihilo :