*/
if(myid==0) {
printf(\
于算
/*向各个处理器播送模式串的信息，对应
法14.6步骤（2）*/
if(numprocs>1) numprocs);
printf(\
textlen*numprocs);
GetFile(\ printf(\
if((nextval=(int
*)malloc(patlen*
sizeof(int)))==NULL) {
printf(\
enough
memory\\n\
exit(1); }
/*对模式串进行分析，对应于算法
14.6
步骤（1）*/
Next(W,patlen,nextval,&pped); if(numprocs>1) {
if (pped.pednum==1) nextlen_send = patlen; else
nextlen_send
=
pped.pedlen*2;
}
}
{
MPI_Bcast(&patlen, 1, MPI_INT, 0, MPI_COMM_WORLD); if(myid!=0)
if(((nextval=(int
*)malloc(patlen*
sizeof(int)))==NULL)
||((W=(char
*)malloc(patlen*
sizeof(char)))==NULL)) {
printf(\
enough
memory\\n\
exit(1);
}
MPI_Barrier(MPI_COMM_WORLD); MPI_Bcast(&pped,3,MPI_INT,0, MPI_COMM_WORLD);
MPI_Bcast(&nextlen_send,1,MPI_INT,0, MPI_COMM_WORLD);
MPI_Bcast(nextval,nextlen_send,
MPI_INT,0, MPI_COMM_WORLD);
MPI_Bcast(W,pped.pedlen,
MPI_CHAR,0, MPI_COMM_WORLD);
26
}
MPI_Barrier(MPI_COMM_WORLD);
/*调用修改过的KMP算法进行局部串匹配，
对应于算法14.6步骤（3）*/ if(numprocs==1) {
kmp(T,W,textlen,patlen,nextval,
&pped,1,0,
match+patlen-1,&prefixlen); } else { 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);
/*各个处理器进行段间匹配，对应于算
法14.6步骤（4）*/ if(myid 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); 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); } /*输出匹配结果*/ if(myid==0) { PrintFile_res(\match+patlen-1,textlen-patlen+1,0, myid); if(numprocs>1) MPI_Send(&ready,1,MPI_INT,1,0, 27 MPI_COMM_WORLD); } else { MPI_Recv(&ready,1,MPI_INT, myid-1,myid-1, MPI_COMM_WORLD,&status); PrintFile_res(\ textlen,myid*textlen-patlen+1, myid); if(myid!=numprocs-1) MPI_Send(&ready,1,MPI_INT, myid+1,myid, MPI_COMM_WORLD); } free(T); free(W); free(nextval); MPI_Finalize(); } 28 3. 运行实例 编译：gcc gen_ped.c –o gen_ped mpicc kmp.c –o kmp 运行：首先运行gen_ped生成模式串，gen_ped Strlen Pedlen Seed Pattern_File。其中Strlen代表模式串的长度，Pedlen代表模式串的最小周期长度，Seed是随机函数使用的种子数，Pattern_File是生成数据存储的文件，这里在kmp.c中固定指定的文件名为pattern.dat。本例中使用了如下的参数。 gen_ped 3 2 1 pattern.dat 之后可以使用命令 mpirun –np SIZE kmp m n来运行该串匹配程序，其中SIZE是所使用的处理器个数，m表示文本串长度，n为文本串的周期长度。本实例中使用了SIZE=3个处理器，m=18，n=3。 mpirun –np 3 kmp 18 2 运行结果： 存储于pattern.dat中的模式串为：qmq 存储于match_result中的匹配结果为： The Text on node 0 is asasas . The Text on node 1 is qmqmqm . The Text on node 2 is ypypyp . This is the match result on node 0 (0) - (1) - (2) - (3) - This is the match result on node 1 (4) - (5) - (6) + (7) - (8) + (9) - This is the match result on node 2 (10) - (11) - 29 (12) - (13) - (14) - (15) - 说明：该运行实例中，令文本串长度为18，随机产生的文本串为asasasqmqmqmypypyp，分布在3个节点上；模式串长度为3，随机产生的模式串为qmq。最后，节点1上得到两个匹配位置，由+表示出来。 30