Programación Paralela

  • View
    7

  • Download
    3

Embed Size (px)

DESCRIPTION

Programacin con MPI

Transcript

Universidad de OrienteNcleo de SucreEscuela de CienciasDepartamento de MatemticasPrograma de la Licenciatura En Informtica

PARALELIZACION DEL ALGORITMO DE SUBSECUENCIA COMN MS LARGA CON MPI-C.

Tutor: Prof. Ana Fuentes Bachiller: Jess Alejandro Machado Ortiz C.I: 24877491

Cuman, enero del 2014INTRODUCCIN

La eficiencia de un computador, depende directamente del tiempo requerido para poder ejecutar una instruccin bsica y del nmero de instrucciones que pueden ser ejecutadas concurrentemente. Esta eficiencia puede ser incrementada por avances en la arquitectura y por avances tecnolgicos. Un caso de esto es la nueva gama de procesadores de INTEL y AMD. Estos avances en la arquitectura incrementa la cantidad de trabajo que se puede realizar por el manejo de instrucciones, especficamente por su capacidad de ciclo de cada procesador. Gracias a las memorias cache, memorias paralelas, canales, memoria intercalada y procesadores paralelos.

Pero a pesar de estos grandes avances, hay un problema primordial a atacar, el cual es mejorar la eficiencia de nuestros programas. Es decir, se debe cambiar la forma en la cual se nos ha enseado la programacin. Ya debera considerarse la programacin paralela como una rama primordial y activa en la incursin de nuevos programadores. Aprovechar al mximo las caractersticas hardware presente, realizar clster, mandar instrucciones a las tarjetas de video a travs de CUDA para optimizar un proceso matemtico. Solo as podramos considerar una pregunta, que es tema de debate en muchas oportunidades: Algn da el software alcanzar al mximo al hardware? Lo pasar de largo? Hay un lmite en alguno de ellos?

La aplicacin que se tratar en este proyecto de desarrollo, consiste en una mezcla de estos tres tipos de aplicaciones (de gran procesamiento de clculo, de entrada y salida de datos y de comunicacin), como se ver ms adelante. Se ir indagando con la forma ms factible de implementarla y ejecutarla satisfactoriamente. Esto con el fin de solucionar una problemtica en dicha rea de estudio, como lo es Los algoritmo de Manejo de Caracteres.

Antes de continuar, cabe a resaltar Qu es MPI? Interfaz de Pase de Mensaje, segn la [wikipedia] es un estndar de funciones contenidas en una biblioteca de paso de mensaje diseada con el fin de facilitar la explotacin de mltiples procesadores. Y el paso de mensaje en s, es una tcnica empleada en la programacin concurrente para aportar sincronizacin entre procesos y permitir la exclusin mutua (para saber ms de este tema, indague la temtica de gestin de procesos y concurrencia) de manera similar a como lo hacen los semforos, monitores entre otros.

Planteamiento

La informacin se representa normalmente a travs de palabras, que est compuesta por smbolos o caracteres. Que vienen a representar un lenguaje (espaol, ingls, alemn, entre otros), permitindonos entender y comprender a travs de un proceso cognoscitivo el mensaje. Observando esta analoga, se afirma que las computadoras realizan el mismo proceso, reciben a travs de una entrada, procesan y emiten una respuesta. Esto da pie al siguiente algoritmo, el cual analiza cadenas de caracteres para obtener informacin relevante para un propsito especfico.

En el caso que se estudiar en este trabajo, el cual deber procesar secuencias de smbolos o caracteres, que representarn una informacin y darn como respuesta La Subsecuencia Comn Ms Larga. Ahora, Qu ser la Subsecuencia Comn ms Larga? Son una forma natural para representar informacin.

Actualmente existen muchos problemas relacionados con las cadenas de caracteres, pero el que ms frecuencia se presenta es el de comparacin de secuencias. Como ejemplo, en el anlisis de secuencias biolgicas la similitud de secuencias es uno de los conceptos de mayor importancia, principalmente por el hecho de observar las posibles relaciones de evolucin compartidas por los organismos. Esta puede ser expresada como un porcentaje de identidad til para determinar las homologas entre secuencias, la cual puede ser, por ejemplo, precisar si comparten un mismo ancestro (recordando a Charles Darwin). Este porcentaje de identidad es una tasa entre el nmero de columnas con caracteres idnticos encontrados en un alineamiento y el nmero de smbolos de la secuencia ms larga.

Definicin Formal:

Navarro, Gonzalo expresa en su libro A Guided Tour To Aproximate String Matching. ACM Computing Surveys, (2001) pp. 31 -88. Dice:

En ingls Longest Common Subsequence (LCS) Sean las secuencias x y y que pertenecen a, y con una longitud M y N (M >= N) respectivamente, el LCS de la secuencias x y y consiste en encontrar una Subsecuencia de x y de y de mxima longitud posible.

Se deduce entonces como el LCS(x,y) es una Subsecuencia de x , y e igualmente, como x y y son supersecuencias de LCS(x,y). El LCS no permite la operacin de sustitucin, nicamente las operaciones de insercin y eliminacin.

Un ejemplo grafico de una LCS.

Como se puede observar los comunes son los que se encuentran en ambas cadenas, esto no es al azar, hay un mtodo mediante el cual se obtiene la LCS. Para el llenado de esta tabla, nos basamos en las siguientes premisas:

EMANCHA

E0000000

M0111111

A0122222

C0122333

H0122344

A0122345

D0122345

O0122345

Y escribimos la palabra de arriba hacia abajo quedandonos:MACHA. Los marcados en rojo son los puntos dominantes para cada seccin. ALGORITMO SECUENCIALProcesamiento por Filas.#include #include #include

/* * Definimos dos funciones para buscar el maximo de dos numero * y el minimo de dos numeros tambien.*/

#define MAX(x,y) (((x) >= (y)) ? (x) : (y))#define MIN(x,y) (((x) 2147483648){printf("Ocurrio un error de desbordamiento de datos");return 0;}//Declaramos la matriz de la forma **c, para que sea dinmica.//Permitiendo manejadar filas y columnas de tamao variable.unsigned short int **c;//definimos la filaint fila;//Asignamos memoria dinamicamente, que sera igual a [tam(x) +1]

c = malloc(sizeof(unsigned short int*)*(len_X+1));for(fila = 0; fila < len_X+1; fila++){//Aqui por asignamos [tam(x) + 1][tam(y) +1] -> por eso el ciclo,//a cada [tam(x) + 1][0...tam(y)+1]c[fila] = malloc(sizeof(unsigned short int)*(len_Y+1));}LCS_procesar(X,Y,c);LCS_mostrar(c,X,len_X,len_Y);printf("\n\n");printf("El tamano de la subsecuencia comun mas larga es: %d\n",c[len_X][len_Y]);for(fila = 0; fila < len_X+1; fila++){ free(c[fila]);}free(c);free(X);free(Y); return 0;}

//Leer un archivo que contiene cadena de caracteres,//se ignoraran nuevas lineas y espacios.char* LCS_leer(char *infile){ FILE *FIN; char c = 'n'; char *S = NULL; char *T; int count = 0;

if((FIN = fopen(infile,"r"))==NULL){ printf("Ocurrio un problema abriendo el archivo: %s\n",infile); exit(0); }

while(( c = fgetc(FIN))!= EOF){ if ( c != '\n'){ count++; //se ensancha, una forma de decirlo la cadena de caracteres dinamicamente. T = (char *) realloc((void *) S, (count+1)*sizeof(char)); if(T != NULL){ S = T; S[count-1] = c; S[count]='\0'; } else{ free(S); printf("Error de (re) asignacion de memoria para guardar la cadena en %s\n",infile); exit(1); } } } fclose(FIN); return S;}

void LCS_procesar(char *x, char *y, unsigned short int **c){ int fila, columna; int len_X = (int) strlen(x); int len_Y = (int) strlen(y);

//Hacemos 0's la primera columna y la primera fila for(fila = 0; fila n, MPI_CHAR, 0, MPI_COMM_WORLD ); //Pasamos las filas a los procesadores. MPI_Bcast( &LCS_info->m, 1, MPI_INT, 0, MPI_COMM_WORLD); //Hacemos el balanceo de carga int intervalo = (totalprocesos + LCS_info->m - LCS_info->m % totalprocesos) / totalprocesos; LCS_info->x = malloc((intervalo+1)*sizeof(char)); bzero(LCS_info->x, intervalo+1); //establece los primeros n bytes del area a patir de de s a 0. //Distribuir el mismo numero de elementos a cada procesador, se requiere que sea intervalo divisible por el total de procesos. MPI_Scatter( string1, intervalo, MPI_CHAR, LCS_info->x, intervalo, MPI_CHAR, 0, MPI_COMM_WORLD); //Se toma el nuevo tamao de filas. LCS_info->m = (int) strlen(LCS_info->x); return;}void LCS_diagonal(int k, LCS_T *LCS_info){ //El core bastante igual al secuencial, solo que aqui el trabajo se realizara a traves de diagonales. //Para trabajar mejor los bloques. int i,j; int start = MAX(1,k-LCS_info->n); int finish = MIN(LCS_info->m,k-1); for( i = start; i x[i-1] == LCS_info->y[j-1]) LCS_info->c[i][j] = LCS_info->c[i-1][j-1] + 1; else { if( LCS_info->c[i-1][j] >= LCS_info->c[i][j-1] ) LCS_info->c[i][j] = LCS_info->c[i-1][j]; else LCS_info->c[i][j] = LCS_info->c[i][j-1]; } }}

void LCS_procesar(LCS_T *LCS_info, int miproc, int totalprocesos ){ int diag, col;// printf("N: %d\n", LCS_info->n); /* For each diagonal */ for(diag = 2; diag m+LCS_info->n; diag++) { /* Receive value of first row to myid+1 */ if (miproc != 0 && diag-1 n ) { MPI_Recv(&LCS_info->c[0][diag-1], 1, MPI_INT, miproc-1, 0, MPI_COMM_WORLD,&status);

} /* Populate diagonal k of process's c matrix */ LCS_diagonal(diag, LCS_info); /* Send value last row to myid-1 */ if (miproc!= totalprocesos-1 && diag > LCS_info->m ) { col = d