7.4. RESOLUCIÓN DE SISTEMAS TRIANGULARES.

  1. Introducción al problema.
  2. Algoritmos secuenciales.
    1. Algoritmo secuencial de acceso por filas.
    2. Algoritmo secuencial de acceso por columnas.
  3. Algoritmos implementados con procesos.
    1. Algoritmo de acceso por filas con actualización concurrente de rangosfijos.
    2. Algoritmo de acceso por filas con actualización mediante rangos no fijos.
    3. Algoritmo de acceso por columnas con actualización concurrente.
  4. Algoritmos implementados con hilos.
    1. Algoritmo de acceso por filas con actualización concurrente de rangosfijos.
    2. Algoritmo de acceso por filas con actualización mediante rangosno fijos.
    3. Algoritmo de acceso por columnas con actualización concurrente.
  5. Comparación de las dos implementaciones.

Introducción al problema.

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

Algoritmos secuenciales.

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.

Algoritmo secuencial de acceso por filas.

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.

Algoritmo secuencial de acceso por columnas.

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




Algoritmos implementados con procesos.

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.

Algoritmo de acceso por filas con actualización concurrente de rangos fijos.

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.

Algoritmo de acceso por filas con actualización mediante rangos no fijos.

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.

Algoritmo de acceso por columnas con actualización concurrente.

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



Algoritmos implementados con hilos.

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.

Algoritmo de acceso por filas con actualización concurrente de rangos fijos.

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.

Algoritmo de acceso por filas con actualización mediante rangos no fijos.

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.

Algoritmo de acceso por columnas con actualización concurrente.

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




Comparación de las dos implementaciones.

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
1
2
3
4
5
Media
Hilos T. Usuario
580
510
540
500
580
542
Hilos T. Kernel
20
20
50
10
10
22
Hilos T. Real
595
527
591
516
591
564
Hilos Faltas Página
8
8
8
8
8
8
Proc.T. Usuario
20
0
30
30
10
18
Proc.T. Kernel
2700
2590
2600
2600
2570
2612
Proc.T. Real
4509
4255
3988
4384
3859
4199
Proc. Faltas Página
738
738
738
738
738
738

Figura 7-5 Tiempos de las dos implementaciones (primer cuadro caso 1).

El segundo cuadro comparativo se realizó con los siguientes parámetros :

MUESTRAS
1
2
3
4
5
Media
Hilos T. Usuario
10380
13580
10400
13610
12340
12062
Hilos T. Kernel
100
100
130
30
80
88
Hilos T. Real
10484
13686
10529
13645
12414
12151,6
Hilos Faltas Página
8
8
8
8
8
8
Proc.T. Usuario
100
70
130
110
70
96
Proc.T. Kernel
16210
16210
15890
15950
16230
16098
Proc.T. Real
32673
29442
35365
31698
32981
32431,8
Proc. Faltas Página
3738
3738
3738
3738
3738
3738

Figura 7-6 Tiempos de las dos implementaciones (segundo cuadro, caso 1).

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
1
2
3
4
5
Media
Hilos T. Usuario
330
460
460
400
390
408
Hilos T. Kernel
10
0
0
0
10
4
Hilos T. Real
340
459
460
402
403
412,8
Hilos Faltas Página
8
8
8
8
8
8
Proc.T. Usuario
0
0
0
0
0
0,0
Proc.T. Kernel
30
30
30
40
40
34
Proc.T. Real
485
545
511
490
485
503,2
Proc. Faltas Página
9
9
9
9
9
9

Figura 7-7 Tiempos de las dos implementaciones (caso 2).

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 :