?? npsm.c
字號:
# include <malloc.h># include <sys/stat.h># include <sys/types.h># include <stdio.h># include <string.h># include <mpi.h>#define MAX(m,n) (m>n?m:n)typedef struct{ int pedlen; int psuffixlen; int pednum;}pntype;/************************************************************************//* this procedure is to analysis period of a given string and calculate its next and nextval value. input: W: pattern string patlen: length of pattern string output: nextval: nextval value pped: period information*/void Next(W,patlen,nextval,pped)char *W;int patlen;int *nextval;pntype *pped;{ int i,j,plen; int *next; if((next=(int *)malloc((patlen+1)*sizeof(int)))==NULL) { printf("no enough memory\n"); exit(1); } /* calculate next and nextval */ next[0]=nextval[0]=-1; j=1; while(j<=patlen) { i=next[j-1]; while(i!=(-1) && W[i]!=W[j-1]) i=next[i]; next[j]=i+1; if(j!=patlen) { if( W[j]!=W[i+1]) nextval[j]=i+1; else nextval[j]=nextval[i+1]; } j++; } /* end while */ pped->pedlen=patlen-next[patlen]; pped->pednum=(int)(patlen/pped->pedlen); pped->psuffixlen=patlen%pped->pedlen; free(next);}/***********************************************************************//* this procedure is a modified kmp algorithm input: T: text string W: pattern string textlen: text length patlen: pattern length nextval: nextval value pped: pattern period information prefix_flag: indicate whether to calculate the prefix 0:yes 1:no matched_num: matched pattern string length output: match: match result prefixlen: maximal pattern prefix length at the end of text*/void kmp(T,W,textlen,patlen,nextval,pped,prefix_flag,matched_num,match, prefixlen)char *T,*W;int textlen,patlen;int *nextval;pntype *pped;int prefix_flag;int matched_num;int *match,*prefixlen;{ int i,j; i=matched_num; /* i is text pointer */ j=matched_num; /* j is pattern pointer */ while(i<textlen) { if((prefix_flag==1)&&(i-j+patlen-1>=textlen)) break; while(j!=(-1) && W[j]!=T[i]) j=nextval[j]; if(j==(patlen-1)) /* match */ { /* match[i-(patlen-1)]=1;*/ if(pped->pednum+pped->psuffixlen==1) /* U */ j = -1 ; else /* UE or U(k)E */ j=patlen-1-pped->pedlen; } j++; i++; } (*prefixlen)=j;}/*************************************************/ /* Rebuild is used to reconstruct nextval and W **/ /* W is pattern string, nextval **/ /*************************************************/ void Rebuild_info(patlen,pped,nextval,W) int patlen; pntype *pped; int *nextval; char *W; { int i; if (pped->pednum == 1) memcpy(W+pped->pedlen,W,pped->psuffixlen); else { memcpy(W+pped->pedlen,W,pped->pedlen); for (i=3; i<=pped->pednum; i++){ memcpy(W+(i-1)*pped->pedlen,W,pped->pedlen); memcpy(nextval+(i-1)*pped->pedlen,nextval+pped->pedlen, pped->pedlen*sizeof(int)); } if(pped->psuffixlen!=0) { memcpy(W+(i-1)*pped->pedlen,W,pped->psuffixlen); memcpy(nextval+(i-1)*pped->pedlen,nextval+pped->pedlen, pped->psuffixlen*sizeof(int)); } } } /**********************************************************//* This procedure is to generate text string *//* input: */ /* strlen: string length *//* pedlen: period length *//* output: *//* string: string */ /**********************************************************/ void gen_string(strlen,pedlen,string)int strlen,pedlen;char *string;{ int suffixlen,num,i,j; srand(1); for(i=0;i<pedlen;i++){ num=rand()%26; string[i]='a'+num; } for(j=1;j<(int)(strlen/pedlen);j++) strncpy(string+j*pedlen,string,pedlen); if((suffixlen=strlen%pedlen)!=0) strncpy(string+j*pedlen,string,suffixlen);} void GetFile(char *filename,char **place, int *number) { FILE *fp; struct stat statbuf; /* include <sys\stat.h> */ if ((fp=fopen(filename,"rb"))==NULL) {printf ("Error open file %s\n",filename); exit(0); } fstat(fileno(fp),&statbuf); /* get file len in byte */ if(((*place)=(char *)malloc(sizeof(char)*statbuf.st_size)) == NULL) {printf ("Error alloc memory\n"); exit(1); } if (fread((*place),1,statbuf.st_size,fp)!=statbuf.st_size) {printf ("Error in reading num\n"); exit(0); } fclose (fp); (*number)=statbuf.st_size; } void PrintFile_int(filename,t,len) char *filename;int *t;int len; { FILE *fp; int i; if ((fp=fopen(filename,"a"))==NULL) {printf ("Error open file %s\n",filename); exit(0); } for (i=0; i<=len-1; i++) if(t[i]==1) fprintf (fp,"(%d) +\n",i); else fprintf (fp,"(%d) -\n",i); fclose (fp); } void PrintFile(filename,t,len) char *filename,*t;int len; { FILE *fp; int i; if ((fp=fopen(filename,"w"))==NULL) {printf ("Error open file %s\n",filename); exit(0); } for (i=0; i<=len-1; i++) fprintf (fp,"(%d) %c\n",i,t[i]); fclose (fp); } void main(argc,argv) int argc; char *argv[]; { char *T,*W; int *nextval,*match; int textlen,patlen,pedlen,nextlen_send; pntype pped; int i,myid,numprocs,prefixlen,ready; double cal_startwtime,cal_endwtime,comm_startwtime, comm_endwtime,cal_time,comm_time,total_time, start_wtime,end_wtime; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); nextlen_send=0; ready=1; cal_time=comm_time=total_time=0; textlen=atoi(argv[1]); textlen=textlen/numprocs; pedlen=atoi(argv[2]); if((T=(char *)malloc(textlen*sizeof(char)))==NULL) { printf("no enough memory\n"); exit(1); } gen_string(textlen,pedlen,T); /***************** processor 0 get pattern ****************/ if(myid==0) { FILE *fp; if ((fp=fopen("result","a"))==NULL) { printf ("Error open file %s\n"); exit(0); } fprintf(fp,"processor num = %d \n",numprocs); fprintf(fp,"textlen = %d\n",textlen*numprocs); GetFile("pattern.dat",&W,&patlen); fprintf(fp,"patlen= %d\n",patlen); if((nextval=(int *)malloc(patlen*sizeof(int)))==NULL) { printf("no enough memory\n"); exit(1); } cal_startwtime = MPI_Wtime(); Next(W,patlen,nextval,&pped); if(numprocs>1) { if (pped.pednum==1) nextlen_send = patlen; else nextlen_send = pped.pedlen*2; } cal_endwtime=MPI_Wtime(); cal_time=cal_endwtime-cal_startwtime; total_time=cal_time; fprintf(fp,"period len = %d\n",pped.pedlen); fclose(fp); } /*****************************************************************/ /**************** distribute pattern *********************/ if(numprocs>1) { MPI_Bcast(&patlen, 1, MPI_INT, 0, MPI_COMM_WORLD); /* patlen */ /* if((match=(int *)malloc(textlen*sizeof(int)))==NULL) { printf("no enough memory\n"); exit(1); }*/ if(myid!=0) if(((nextval=(int *)malloc(patlen*sizeof(int)))==NULL)|| ((W=(char *)malloc(patlen*sizeof(char)))==NULL)) { printf("no enough memory\n"); exit(1); } MPI_Barrier(MPI_COMM_WORLD); start_wtime=comm_startwtime=MPI_Wtime(); MPI_Bcast(&pped,3,MPI_INT,0,MPI_COMM_WORLD); /* period character */ MPI_Bcast(&nextlen_send,1,MPI_INT,0,MPI_COMM_WORLD); /* nextlen_send */ MPI_Bcast(nextval,nextlen_send,MPI_INT,0,MPI_COMM_WORLD); /* nextval */ MPI_Bcast(W,pped.pedlen, MPI_CHAR, 0, MPI_COMM_WORLD); /* broadcast pattern period string */ MPI_Barrier(MPI_COMM_WORLD); comm_endwtime=MPI_Wtime(); comm_time=comm_endwtime-comm_startwtime; } else { start_wtime=MPI_Wtime(); } /*********************************************************************/ /*************************** matching *******************************/ if((numprocs==1)||(patlen==1)) { MPI_Barrier(MPI_COMM_WORLD); cal_startwtime=MPI_Wtime(); kmp(T,W,textlen,patlen,nextval,&pped,1,0,match,&prefixlen); } else { MPI_Barrier(MPI_COMM_WORLD); cal_startwtime=MPI_Wtime(); if(myid!=0) Rebuild_info(patlen,&pped,nextval,W); if(myid!=numprocs-1) kmp(T,W,textlen,patlen,nextval,&pped,0,0,match+patlen-1,&prefixlen); else kmp(T,W,textlen,patlen,nextval,&pped,1,0,match+patlen-1,&prefixlen); MPI_Barrier(MPI_COMM_WORLD); cal_endwtime=MPI_Wtime(); cal_time=cal_time+cal_endwtime-cal_startwtime; comm_startwtime=MPI_Wtime(); if(myid<numprocs-1) MPI_Send(&prefixlen,1,MPI_INT,myid+1,99,MPI_COMM_WORLD); if(myid>0) MPI_Recv(&prefixlen,1,MPI_INT,myid-1,99,MPI_COMM_WORLD,&status); MPI_Barrier(MPI_COMM_WORLD); comm_endwtime=MPI_Wtime(); comm_time=comm_time+comm_endwtime-comm_startwtime; cal_startwtime=MPI_Wtime(); if((myid>0)&&(prefixlen!=0)) kmp(T-prefixlen,W,prefixlen+patlen-1,patlen,nextval,&pped, 1,prefixlen,match+patlen-1-prefixlen,&prefixlen); MPI_Barrier(MPI_COMM_WORLD); } end_wtime=cal_endwtime=MPI_Wtime(); cal_time=cal_time+cal_endwtime-cal_startwtime; total_time=total_time+end_wtime-start_wtime; /*******************************************************************/ /**************** print result **********************************//* if(myid==0) { if(patlen!=1) PrintFile_int("match_result",match+patlen-1,textlen-patlen+1); else PrintFile_int("match_result",match,textlen); if(numprocs>1) MPI_Send(&ready,1,MPI_INT,1,0,MPI_COMM_WORLD); } else { MPI_Recv(&ready,1,MPI_INT,myid-1,myid-1,MPI_COMM_WORLD,&status); PrintFile_int("match_result",match,textlen); if(myid!=numprocs-1) MPI_Send(&ready,1,MPI_INT,myid+1,myid,MPI_COMM_WORLD); } */ if(myid==0){ FILE *fp;/* double t1,t2,t3; if(numprocs>1) { MPI_Send(&ready,1,MPI_INT,1,0,MPI_COMM_WORLD); for(i=1;i<numprocs;i++) { MPI_Recv(&t1,1,MPI_DOUBLE,i,i,MPI_COMM_WORLD,&status); MPI_Recv(&t2,1,MPI_DOUBLE,i,i+1,MPI_COMM_WORLD,&status); MPI_Recv(&t3,1,MPI_DOUBLE,i,i+2,MPI_COMM_WORLD,&status); cal_time=cal_time+t1; comm_time=comm_time+t2; total_time=total_time+t3; } cal_time=cal_time/numprocs; comm_time=comm_time/numprocs; total_time=total_time/numprocs; }*/ if ((fp=fopen("result","a"))==NULL) { printf ("Error open file %s\n"); exit(0); } fprintf(fp,"calculate time = %f \n",cal_time); fprintf(fp,"communicate time = %f \n",comm_time); fprintf(fp,"total time = %f \n\n",total_time); fclose(fp); } /* else { MPI_Recv(&ready,1,MPI_INT,myid-1,myid-1,MPI_COMM_WORLD,&status); MPI_Send(&cal_time,1,MPI_DOUBLE,0,myid,MPI_COMM_WORLD); MPI_Send(&comm_time,1,MPI_DOUBLE,0,myid+1,MPI_COMM_WORLD); MPI_Send(&total_time,1,MPI_DOUBLE,0,myid+2,MPI_COMM_WORLD); if(myid!=numprocs-1) MPI_Send(&ready,1,MPI_INT,myid+1,myid,MPI_COMM_WORLD); }*/ free(T); free(W); free(nextval); /* free(match);*/ MPI_Finalize(); } ?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -