npsm.c

在MPI上实现并行串匹配的源代码。

# 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(); 
 }