开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 并行计算 > 查看源码
rand_match.c
资源名称：mpi.zip　[点击查看]
上传用户：hhyinxing
上传日期：2013-09-10
资源大小：833k
文件大小：9k
源码类别：

并行计算

开发平台：

Unix_Linux

rand_match.c：源码内容
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #include <string.h>
  5. #include <math.h>
  6. #include "mpi.h"
  8. #define PiM 21
  10. /*初始化Fp矩阵*/
  11. int f[2][2][2]={{{1,0},{1,1}},{{1,1},{0,1}}};
  12. int g[2][2][2];
  13. int pdata[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,67,71,79,83};
  15. /*生成字符串*/
  16. void gen_string(int stringlen,char *String,int seed)
  17. {
  18. int i,num;
  20. srand(seed*100);
  21. for(i=0;i<stringlen;i++){
  22.      num=rand()%2;
  23.      String[i]='0'+num;
  24.    }
  25.    String[stringlen]='';
  26. }
  28. /*从素数存放数组中随机选取一个素数*/
  29. int drawp(int seed){
  30. srand(seed*100);
  31. return pdata[rand()%PiM];
  32. }
  34. /*该算法中第一个参数n是正文串的长度，第二个参数m是模式串的长度。(约束0<m,n<=128)*/
  35. main(int argc,char *argv[]){
  36.    int groupsize,myrank,n,m,p,i,j,h,tmp;
  37. int textlen;
  38.    char *Text,*Pattern;
  39.    int *MATCH;
  40.    int B[128][2][2],C[128][2][2],D[128][2][2],L[128][2][2];
  41.    int fp_pattern[2][2];
  42. MPI_Status status;
  43.   
  44.   
  45.    MPI_Init(&argc,&argv);
  46.    MPI_Comm_size(MPI_COMM_WORLD,&groupsize);
  47.    MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
  48.   
  49.    n=atoi(argv[1]);
  50.    m=atoi(argv[2]);
  52. textlen=n/groupsize;
  54. if(myrank==groupsize-1)
  55. textlen=n-textlen*(groupsize-1);
  57.    if((Text=(char *)malloc(textlen*sizeof(char)+1))==NULL){
  58.      printf("no enough memoryn");
  59.      exit(1);
  60.    }
  62.    if((Pattern=(char *)malloc(m*sizeof(char)+1))==NULL){
  63.      printf("no enough memoryn");
  64.      exit(1);
  65.    }
  66.   
  67.    if((MATCH=(int *)malloc(textlen*sizeof(int)+1))==NULL){
  68.      printf("no enough memoryn");
  69.      exit(1);
  70.    }
  72.    /*初始化Fp的逆矩阵Gp*/
  73.    g[0][0][0]=1;g[0][0][1]=0;g[0][1][0]=p-1;g[0][1][1]=1;
  74.    g[1][0][0]=1;g[1][0][1]=p-1;g[1][1][0]=0;g[1][1][1]=1;
  75.   
  76.    /*产生正文串和模式串*/
  77.    gen_string(textlen,Text,m*n*myrank);
  79. /*随机选择一个素数，对应算法14.9步骤（2）*/
  80. if(myrank==0) {
  81.    p=drawp(n/m);
  82.    gen_string(m,Pattern,p*m*n);
  83. }
  84.   
  85.    /*播送选中的素数与m给其余每个节点*/
  86. MPI_Bcast(&p,1,MPI_INT,0,MPI_COMM_WORLD);
  87.    MPI_Bcast(Pattern,m,MPI_CHAR,0,MPI_COMM_WORLD);
  88.   
  89.    printf("one node %d n=%d,m=%d,p=%dn",myrank,n,m,p);
  90.    printf("one node %d Text=%sn",myrank,Text);
  91.    printf("one node %d Pattern=%sn",myrank,Pattern);
  93.    MPI_Barrier(MPI_COMM_WORLD);
  94.     
  95. /*计算模式串的指纹函数值，对应算法14.9步骤（3）*/
  96. if(myrank==0) {
  97.    for(i=1;i<=m;i++) {
  98.      B[i][0][0]=f[Pattern[i-1]-'0'][0][0];
  99.      B[i][0][1]=f[Pattern[i-1]-'0'][0][1];
  100.      B[i][1][0]=f[Pattern[i-1]-'0'][1][0];
  101.      B[i][1][1]=f[Pattern[i-1]-'0'][1][1];
  102.    }
  104.        B[0][0][0]=(B[1][0][0]*B[2][0][0]+B[1][0][1]*B[2][1][0])%p;
  105.        B[0][0][1]=(B[1][0][0]*B[2][0][1]+B[1][0][1]*B[2][1][1])%p;
  106.        B[0][1][0]=(B[1][1][0]*B[2][0][0]+B[1][1][1]*B[2][1][0])%p;
  107.        B[0][1][1]=(B[1][1][0]*B[2][0][1]+B[1][1][1]*B[2][1][1])%p;
  109.      for(j=1;j<=m-2;j++){
  110.        B[j][0][0]=(B[j-1][0][0]*B[j+2][0][0]+B[j-1][0][1]*B[j+2][1][0])%p;
  111.        B[j][0][1]=(B[j-1][0][0]*B[j+2][0][1]+B[j-1][0][1]*B[j+2][1][1])%p;
  112.        B[j][1][0]=(B[j-1][1][0]*B[j+2][0][0]+B[j-1][1][1]*B[j+2][1][0])%p;
  113.        B[j][1][1]=(B[j-1][1][0]*B[j+2][0][1]+B[j-1][1][1]*B[j+2][1][1])%p;
  114.      }
  116.       fp_pattern[0][0]=B[m-2][0][0];
  117.       fp_pattern[0][1]=B[m-2][0][1];
  118.       fp_pattern[1][0]=B[m-2][1][0];
  119.       fp_pattern[1][1]=B[m-2][1][1];
  120.    }
  121.     
  122.    MPI_Bcast(fp_pattern,4,MPI_INT,0,MPI_COMM_WORLD);
  123.    MPI_Barrier(MPI_COMM_WORLD);
  124.     
  125.    /*计算Ni，存放在数组C中*/
  126.    for(i=1;i<=textlen;i++) {
  127.      B[i][0][0]=f[Text[i-1]-'0'][0][0];
  128.      B[i][0][1]=f[Text[i-1]-'0'][0][1];
  129.      B[i][1][0]=f[Text[i-1]-'0'][1][0];
  130.      B[i][1][1]=f[Text[i-1]-'0'][1][1];
  131.    }
  133.     C[1][0][0]=B[1][0][0];
  134.     C[1][0][1]=B[1][0][1];
  135.     C[1][1][0]=B[1][1][0];
  136.     C[1][1][1]=B[1][1][1];
  138. for(i=2;i<=textlen;i++) {
  139.        C[i][0][0]=(C[i-1][0][0]*B[i][0][0]+C[i-1][0][1]*B[i][1][0])%p;
  140.        C[i][0][1]=(C[i-1][0][0]*B[i][0][1]+C[i-1][0][1]*B[i][1][1])%p;
  141.        C[i][1][0]=(C[i-1][1][0]*B[i][0][0]+C[i-1][1][1]*B[i][1][0])%p;
  142.        C[i][1][1]=(C[i-1][1][0]*B[i][0][1]+C[i-1][1][1]*B[i][1][1])%p;
  143. }
  145. if(groupsize>1) {
  146.     if(myrank==0) {
  147. MPI_Send(&C[textlen],4,MPI_INT,myrank+1,myrank,MPI_COMM_WORLD);
  148. }
  149. else if(myrank==groupsize-1) {
  150. MPI_Recv(&C[0],4,MPI_INT,myrank-1,myrank-1,MPI_COMM_WORLD,&status);
  151. }
  152. else {
  153. MPI_Recv(&C[0],4,MPI_INT,myrank-1,myrank-1,MPI_COMM_WORLD,&status);
  155. i=textlen;
  157.        C[textlen+1][0][0]=(C[0][0][0]*C[i][0][0]+C[0][0][1]*C[i][1][0])%p;
  158.        C[textlen+1][0][1]=(C[0][0][0]*C[i][0][1]+C[0][0][1]*C[i][1][1])%p;
  159.        C[textlen+1][1][0]=(C[0][1][0]*C[i][0][0]+C[0][1][1]*C[i][1][0])%p;
  160.        C[textlen+1][1][1]=(C[0][1][0]*C[i][0][1]+C[0][1][1]*C[i][1][1])%p;
  162.     C[i][0][0]=C[textlen+1][0][0];
  163.     C[i][0][1]=C[textlen+1][0][1];
  164.     C[i][1][0]=C[textlen+1][1][0];
  165.     C[i][1][1]=C[textlen+1][1][1];
  167. MPI_Send(&C[textlen],4,MPI_INT,myrank+1,myrank,MPI_COMM_WORLD); 
  168. }
  169. }
  171.    MPI_Barrier(MPI_COMM_WORLD);
  173. if(myrank!=0) {
  174. for(i=1;i<textlen;i++) {
  175.        C[textlen+1][0][0]=(C[0][0][0]*C[i][0][0]+C[0][0][1]*C[i][1][0])%p;
  176.        C[textlen+1][0][1]=(C[0][0][0]*C[i][0][1]+C[0][0][1]*C[i][1][1])%p;
  177.        C[textlen+1][1][0]=(C[0][1][0]*C[i][0][0]+C[0][1][1]*C[i][1][0])%p;
  178.        C[textlen+1][1][1]=(C[0][1][0]*C[i][0][1]+C[0][1][1]*C[i][1][1])%p;
  179.     C[i][0][0]=C[textlen+1][0][0];
  180.     C[i][0][1]=C[textlen+1][0][1];
  181.     C[i][1][0]=C[textlen+1][1][0];
  182.     C[i][1][1]=C[textlen+1][1][1];
  183. } 
  184. }
  186.    MPI_Barrier(MPI_COMM_WORLD);
  188. if(groupsize>1) {
  189.     if(myrank==0) {
  190. MPI_Recv(&C[textlen+1],4*(m-1),MPI_INT,myrank+1,myrank,MPI_COMM_WORLD,&status);
  191. }
  192. else if(myrank==groupsize-1) {
  193. MPI_Send(&C[1],4*(m-1),MPI_INT,myrank-1,myrank-1,MPI_COMM_WORLD);
  194. }
  195. else {
  196. MPI_Recv(&C[textlen+1],4*(m-1),MPI_INT,myrank+1,myrank,MPI_COMM_WORLD,&status);
  197. MPI_Send(&C[1],4*(m-1),MPI_INT,myrank-1,myrank-1,MPI_COMM_WORLD); 
  198. }
  199. }
  201.    /*计算Ri，存放在数组D中*/
  202.    for(i=1;i<=textlen;i++) {
  203.      B[i][0][0]=g[Text[i-1]-'0'][0][0];
  204.      B[i][0][1]=g[Text[i-1]-'0'][0][1];
  205.      B[i][1][0]=g[Text[i-1]-'0'][1][0];
  206.      B[i][1][1]=g[Text[i-1]-'0'][1][1];
  207.    }
  209.     D[1][0][0]=B[1][0][0];
  210.     D[1][0][1]=B[1][0][1];
  211.     D[1][1][0]=B[1][1][0];
  212.     D[1][1][1]=B[1][1][1];
  214. for(i=2;i<=textlen;i++) {
  215.        D[i][0][0]=(B[i][0][0]*D[i-1][0][0]+B[i][0][1]*D[i-1][1][0])%p;
  216.        D[i][0][1]=(B[i][0][0]*D[i-1][0][1]+B[i][0][1]*D[i-1][1][1])%p;
  217.        D[i][1][0]=(B[i][1][0]*D[i-1][0][0]+B[i][1][1]*D[i-1][1][0])%p;
  218.        D[i][1][1]=(B[i][1][0]*D[i-1][0][1]+B[i][1][1]*D[i-1][1][1])%p;
  219. }
  221. if(groupsize>1) {
  222.     if(myrank==0) {
  223. MPI_Send(&D[textlen],4,MPI_INT,myrank+1,myrank,MPI_COMM_WORLD);
  224. }
  225. else if(myrank==groupsize-1) {
  226. MPI_Recv(&D[0],4,MPI_INT,myrank-1,myrank-1,MPI_COMM_WORLD,&status);
  227. }
  228. else {
  229. MPI_Recv(&D[0],4,MPI_INT,myrank-1,myrank-1,MPI_COMM_WORLD,&status);
  231. i=textlen;
  232.         D[textlen+1][0][0]=(D[i][0][0]*D[0][0][0]+D[i][0][1]*D[0][1][0])%p;
  233.         D[textlen+1][0][1]=(D[i][0][0]*D[0][0][1]+D[i][0][1]*D[0][1][1])%p;
  234.         D[textlen+1][1][0]=(D[i][1][0]*D[0][0][0]+D[i][1][1]*D[0][1][0])%p;
  235.         D[textlen+1][1][1]=(D[i][1][0]*D[0][0][1]+D[i][1][1]*D[0][1][1])%p;
  237.     D[i][0][0]=D[textlen+1][0][0];
  238.     D[i][0][1]=D[textlen+1][0][1];
  239.     D[i][1][0]=D[textlen+1][1][0];
  240.     D[i][1][1]=D[textlen+1][1][1];
  242. MPI_Send(&D[textlen],4,MPI_INT,myrank+1,myrank,MPI_COMM_WORLD); 
  243. }
  244. }
  246.    MPI_Barrier(MPI_COMM_WORLD);
  248. if(myrank==0) {
  249.     D[0][0][0]=1;
  250.     D[0][0][1]=0;
  251.     D[0][1][0]=0;
  252.     D[0][1][1]=1;
  253. }
  255. if(myrank!=0) {
  256. for(i=1;i<textlen;i++) {
  257.        D[textlen+1][0][0]=(D[i][0][0]*D[0][0][0]+D[i][0][1]*D[0][1][0])%p;
  258.        D[textlen+1][0][1]=(D[i][0][0]*D[0][0][1]+D[i][0][1]*D[0][1][1])%p;
  259.        D[textlen+1][1][0]=(D[i][1][0]*D[0][0][0]+D[i][1][1]*D[0][1][0])%p;
  260.        D[textlen+1][1][1]=(D[i][1][0]*D[0][0][1]+D[i][1][1]*D[0][1][1])%p;
  262.     D[i][0][0]=D[textlen+1][0][0];
  263.     D[i][0][1]=D[textlen+1][0][1];
  264.     D[i][1][0]=D[textlen+1][1][0];
  265.     D[i][1][1]=D[textlen+1][1][1];
  266. } 
  267. }
  268.   
  269.    MPI_Barrier(MPI_COMM_WORLD);
  271.   for(i=1;i<=textlen;i++)
  272.    MATCH[i]=0;
  274. /*各个处理器分别计算所分配的文本串的Li，并判别是否存在匹配位置，对应算法14.9的步骤（4）*/  
  275. if(myrank==groupsize-1) {
  276.    for(i=1;i<=textlen-m+1;i++){
  277.      L[i][0][0]=(D[i-1][0][0]*C[i+m-1][0][0]+D[i-1][0][1]*C[i+m-1][1][0])%p;      
  278.      L[i][0][1]=(D[i-1][0][0]*C[i+m-1][0][1]+D[i-1][0][1]*C[i+m-1][1][1])%p;      
  279.      L[i][1][0]=(D[i-1][1][0]*C[i+m-1][0][0]+D[i-1][1][1]*C[i+m-1][1][0])%p;      
  280.      L[i][1][1]=(D[i-1][1][0]*C[i+m-1][0][1]+D[i-1][1][1]*C[i+m-1][1][1])%p;      
  281.      if(((L[i][0][0]+p)%p==fp_pattern[0][0]) 
  282. && ((L[i][0][1]+p)%p==fp_pattern[0][1])
  283. && ((L[i][1][0]+p)%p==fp_pattern[1][0]) 
  284. && ((L[i][1][1]+p)%p==fp_pattern[1][1])) {
  285.        MATCH[i]=1;
  286. printf("on node %d match pos is %dn",myrank,i);
  287. }
  288. }
  289. }
  290. else {
  291.    for(i=1;i<=textlen;i++){
  292.      L[i][0][0]=(D[i-1][0][0]*C[i+m-1][0][0]+D[i-1][0][1]*C[i+m-1][1][0])%p;      
  293.      L[i][0][1]=(D[i-1][0][0]*C[i+m-1][0][1]+D[i-1][0][1]*C[i+m-1][1][1])%p;      
  294.      L[i][1][0]=(D[i-1][1][0]*C[i+m-1][0][0]+D[i-1][1][1]*C[i+m-1][1][0])%p;      
  295.      L[i][1][1]=(D[i-1][1][0]*C[i+m-1][0][1]+D[i-1][1][1]*C[i+m-1][1][1])%p;      
  296.      if(((L[i][0][0]+p)%p==fp_pattern[0][0]) 
  297. && ((L[i][0][1]+p)%p==fp_pattern[0][1])
  298. && ((L[i][1][0]+p)%p==fp_pattern[1][0]) 
  299. && ((L[i][1][1]+p)%p==fp_pattern[1][1])) {
  300.        MATCH[i]=1;
  301. printf("on node %d match pos is %dn",myrank,i);
  302. }
  303. }
  304. }
  306. MPI_Finalize();  
  307. }