network2.cpp

有限元法算光纤模式

/* This program is to calculate the network throughput and average hop of
   shuffleNet and Manhattan Street Network with hot-potato routing.*/


# include <stdlib.h>
# include <stdio.h>
# include <math.h>
# include <conio.h>


struct snode
{
     char          flag;   //if flag=1, care node, else don't care node
     unsigned int  nxt1;   //if flag=1, nxt1 is the preferred path
     unsigned int  nxt2;
} ;

struct element      // It is a structure of transition matrix element
{
    char    flag;   // if flag=1, care node
    int     i1;     // if flag=1, i1 is the preferred node, q1 and q2 are
    int     i2;     // the probability to i1 and i2 respectively
    float   q1;     // if flag=1, q1=1-p, q2=p; else q1=q2=0.5;
    float   q2;
};

struct element   T[1024];  //T is the transition probability matrix
int   dc[1024];            //It stores the number of don't care node
int   NN;  	           //The total number of nodes
int   dcn;                 //The number of care nodes

void ShuffleNet();
void MSN();
void TP(float *, float *);  //TP is the function T*P, that is matrix time vector
int mod(int x, int y);




void main()
{
   int      ch, i, j, h;
   float    pdc2, pdc1, D, g, u, a, pc, pc0, pa0, pa1, judge; //g:traffic load;
   float    P1[1024], P0[1024];   //P1 and P0 store the P(k) and P(k-1) respectivly
   FILE     *fp1, *fp2, *fp3;

   clrscr();
   gotoxy(1,5);
   printf("    -----------------------------------------------------------\n");
   printf("    |   This program is to calculate the network throughput   |\n");
   printf("    |   and average hops of ShuffleNet and Manhattan Street   |\n");
   printf("    |   Network with hot-potato routing.                      |\n");
   printf("    |   Designed by Xie  in June 1997                 |\n");
   printf("    -----------------------------------------------------------\n");

   do
   {
      printf("\nPlease choise the ShuffleNet or Manhattan Street Network");
      printf("\n1.ShuffleNet;  2.Manhattan Street Network:   ");
      scanf("%d",&ch);
   }while(ch!=1&&ch!=2);

   if(ch==1)
   {
      ShuffleNet();
      fp1=fopen("d:\\home\\xcj\\cpp\\sh64d.dat","wt");
      fp2=fopen("d:\\home\\xcj\\cpp\\sh64t.dat","wt");
      fp3=fopen("d:\\home\\xcj\\cpp\\sh64pdc.dat","wt");
      if(fp1==NULL||fp2==NULL||fp3==NULL)
      {
	 printf("\nFile shdc.dat creating fails");
	 exit(1);
      }
   }
   if(ch==2)
   {
      MSN();
      fp1=fopen("d:\\home\\xcj\\cpp\\mh64d.dat","wt");
      fp2=fopen("d:\\home\\xcj\\cpp\\mh64t.dat","wt");
      fp3=fopen("d:\\home\\xcj\\cpp\\mh64pdc.dat","wt");
      if(fp1==NULL||fp2==NULL||fp3==NULL)
      {
	 printf("\nFile msndc.dat creating fails");
	 exit(1);
      }
   }

   printf("\nPlease wait!!!");

//calculate network performance with the g
   for(g=0.05;g<=1.01;g=g+0.05)
   {
      pdc1=0.0;
      pdc2=0.0;
      pc=1.0;
      pc0=1.0;
      //calculate pdc;
      do
      {
	 pdc1=pdc2;
	 P1[0]=0.0;
	 for(i=1;i<NN;i++)
	    P1[i]=1.0/(float)(NN-1);
	 for(i=1;i<NN;i++)
	 {
	    if(T[i].flag==1)
	    {
	       T[i].q2=0.25*pc0*(1-pdc1);
	       T[i].q1=1.0-T[i].q2;
	    }
	 }

	 h=0;
	 D=0.0;
	 pdc2=0.0;
	 for(i=0;i<NN;i++)
	    P0[i]=P1[i];
	 TP(P1,P0);
	 h++;
	 D=D+(float)h*(P1[0]-P0[0]);
	 for(i=0;i<dcn;i++)
	 {
	    j=dc[i];
	    pdc2=pdc2+P0[j];
	 }

	 for(i=1;i<NN;i++)
	 {
	    if(T[i].flag==1)
	    {
	       T[i].q2=0.25*pc*(1-pdc1);
	       T[i].q1=1.0-T[i].q2;
	    }
	 }

	 do
	 {
	    for(i=0;i<NN;i++)
	       P0[i]=P1[i];
	    TP(P1,P0);
	    h++;
	    D=D+(float)h*(P1[0]-P0[0]);
	    for(i=0;i<dcn;i++)
	    {
	       j=dc[i];
	       pdc2=pdc2+P0[j];
	    }
	    judge=fabs(P1[0]-P0[0]);
	    for(i=1;i<NN;i++)
	    {
	       if(judge<fabs(P1[i]))
		  judge=fabs(P1[i]);
	    }
	 }while(judge>1.0e-8);

	 pdc2=pdc2/D;
	 a=1.0/D;
	 u=(sqrt(a*a+g*g*(1-a)*(1-a))-a)/(g*(1-a)*(1-a));
	 pc=u*(1-a)+u*a*g+(1-u)*g;
	 pa0=(1-u)*(1-u)+2*u*(1-u)*a+u*u*a*a;
	 pa1=2*u*(1-u)*(1-a)+2*u*u*a*(1-a);
	 pc0=pa1/(pa0+pa1);

      }while(fabs(pdc2-pdc1)>1.0e-4);

      //calculate the hop distribution
      pdc1=pdc2;
      P1[0]=0.0;
      for(i=1;i<NN;i++)
	 P1[i]=1.0/(float)(NN-1);
      for(i=1;i<NN;i++)
      {
	 if(T[i].flag==1)
	 {
	    T[i].q2=0.25*pc0*(1-pdc1);
	    T[i].q1=1.0-T[i].q2;
	 }
      }

      h=0;
      D=0.0;
      for(i=0;i<NN;i++)
	 P0[i]=P1[i];
      TP(P1,P0);
      h++;
      D=D+(float)h*(P1[0]-P0[0]);

      for(i=1;i<NN;i++)
      {
	 if(T[i].flag==1)
	 {
	    T[i].q2=0.25*pc*(1-pdc1);
	    T[i].q1=1.0-T[i].q2;
	 }
      }

      do
      {
	 for(i=0;i<NN;i++)
	    P0[i]=P1[i];
	 TP(P1,P0);
	 h++;
	 D=D+(float)h*(P1[0]-P0[0]);
	 judge=fabs(P1[0]-P0[0]);
	 for(i=1;i<NN;i++)
	 {
	    if(judge<fabs(P1[i]))
	       judge=fabs(P1[i]);
	 }

      }while(judge>1.0e-8);
      a=1.0/D;
      u=(sqrt(a*a+g*g*(1-a)*(1-a))-a)/(g*(1-a)*(1-a));
      fprintf(fp1,"%lf\t%lf\n",g,D);
      fprintf(fp2,"%lf\t%lf\n",g,2*NN*u/D);
      fprintf(fp3,"%lf\t%lf\n",g,pdc1);
   }

   fclose(fp1);
   fclose(fp2);
   fclose(fp3);
   printf("\nOK!!!");
}



void ShuffleNet()
{
   int            i, j, k, r, c, r1, c1, rmax, d, base;
   struct snode   nodes[1024];

   printf("Please input paremeter k(1-7):");
   scanf("%d",&k);
   while(k<1||k>7)
   {
      printf("The k inputed is beyond the scope, please input again k(1-7):");
      scanf("%d",&k);
   }

      dcn=0;
      rmax=(int)pow(2.0,(double)k);
      NN=k*rmax;
      base=rmax-1;
      for(c=0;c<k;c++)
      {
	 for(r=0;r<rmax;r++)
	 {
	    i=c*rmax+r;
	    if(c!=0||r!=0)
	    {
	       if(c==0)
		  d=k;
	       else
		  d=mod(k-c,k);
	       r1=r<<d;
	       r1=r1&base;
	       if(r1==0)
		  nodes[i].flag=1;
	       else
	       {
		  nodes[i].flag=0;
		  dcn++;
	       }
	       c1=mod(c+1,k);
	       r1=r<<1;
	       r1=r1&base;
	       nodes[i].nxt1=c1*rmax+r1;
	       nodes[i].nxt2=nodes[i].nxt1+1;
	    }
	 }
      }
      T[0].flag=0;
      T[0].i1=0;
      T[0].i2=1;
      T[0].q1=1.0;
      T[0].q2=0.0;
      j=0;
      for(i=1;i<NN;i++)
      {
	 if(nodes[i].flag==0)
	 {
	    T[i].flag=0;
	    T[i].i1=nodes[i].nxt1;
	    T[i].i2=nodes[i].nxt2;
	    T[i].q1=0.5;
	    T[i].q2=0.5;
	    dc[j]=i;
	    j++;
	 }
	 else
	 {
	    T[i].flag=1;
	    T[i].i1=nodes[i].nxt1;
	    T[i].i2=nodes[i].nxt2;
	    T[i].q1=0.75;
	    T[i].q2=0.25;
	 }
      }
}



void MSN()
{
   int            m, n, rfr, cfr, r, c, rnxt, cnxt, r1, c1, i, j;
   struct snode   nodes[1024];

   printf("Please input paremeter n(n must be even 2-32):");
   scanf("%d",&n);
   while(n<2||n>32||n%2==1)
   {
      printf("The n inputed is wrong, please input again n(n must be even 2-32):");
      scanf("%d",&n);
   }

      dcn=0;
      m=n;
      NN=m*n;
      for(cfr=0;cfr<n;cfr++)
      {
	 for(rfr=0;rfr<m;rfr++)
	 {
	    if(rfr!=0||cfr!=0)
	    {
	       if(cfr%2==0)
		  rnxt=mod(rfr+1,m);
	       else
		  rnxt=mod(rfr-1,m);
	       if(rfr%2==0)
		  cnxt=mod(cfr+1,n);
	       else
		  cnxt=mod(cfr-1,n);
	       i=cfr*m+rfr;
	       r=m/2-mod(m/2+rfr,m);
	       c=n/2-mod(n/2+cfr,n);
	       r1=m/2-mod(m/2+rnxt,m);
	       c1=n/2-mod(n/2+cnxt,n);
//             judge the quadrant

	       if(r>0&&c>0)       //in Q1 quadrant
	       {
		  if(r==m/2&&c==n/2)
		  {
		     nodes[i].flag=0;
		     dcn++;
		     nodes[i].nxt1=cfr*m+rnxt;
		     nodes[i].nxt2=cnxt*m+rfr;
		  }
		  if(r==m/2&&c<n/2)
		  {
		     if(c1-c<0)
		     {
			nodes[i].flag=0;
			dcn++;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			nodes[i].flag=1;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		  }
		  if(r<m/2&&c==n/2)
		  {
		     if(r1-r<0)
		     {
			nodes[i].flag=0;
			dcn++;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			nodes[i].flag=1;
			nodes[i].nxt1=cnxt*m+rfr;
			nodes[i].nxt2=cfr*m+rnxt;
		     }
		  }
		  if(r<m/2&&c<n/2)
		  {
		     if((r1-r<0&&c1-c<0)||(r1-r>0&&c1-c>0))
		     {
			nodes[i].flag=0;
			dcn++;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			if(r1-r<0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cfr*m+rnxt;
			   nodes[i].nxt2=cnxt*m+rfr;
			}
			if(c1-c<0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cnxt*m+rfr;
			   nodes[i].nxt2=cfr*m+rnxt;
			}
		     }
		  }
	       }

	       if(r>0&&c<=0)  //in Q2 quadrant
	       {
		  if(c==0)
		  {
		     nodes[i].flag=1;
		     nodes[i].nxt1=cfr*m+rnxt;
		     nodes[i].nxt2=cnxt*m+rfr;
		  }
		  if(r==1&&c!=0)
		  {
		     nodes[i].flag=1;
		     nodes[i].nxt1=cnxt*m+rfr;
		     nodes[i].nxt2=cfr*m+rnxt;
		  }
		  if(c!=0&&r!=1)
		  {
		     if(r1==-m/2+1)  r1=r1+m;
		     if(c1==n/2)  c1=c1-n;
		     if((r1-r<0&&c1-c>0)||(r1-r>0&&c1-c<0))
		     {
			dcn++;
			nodes[i].flag=0;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			if(r1-r<0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cfr*m+rnxt;
			   nodes[i].nxt2=cnxt*m+rfr;
			}
			if(c1-c>0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cnxt*m+rfr;
			   nodes[i].nxt2=cfr*m+cnxt;
			}
		     }
		  }
	       }

	       if(r<=0&&c<=0)  //in Q3 quadrant
	       {
		  if(r==-m/2+1&&c==-n/2+1)
		  {
		     nodes[i].flag=0;
		     dcn++;
		     nodes[i].nxt1=cfr*m+rnxt;
		     nodes[i].nxt2=cnxt*m+rfr;
		  }
		  if(r==-m/2+1&&c>-n/2+1)
		  {
		     if(c1-c>0)
		     {
			nodes[i].flag=0;
			dcn++;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			nodes[i].flag=1;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		  }
		  if(r>-m/2+1&&c==-n/2+1)
		  {
		     if(r1-r>0)
		     {
			nodes[i].flag=0;
			dcn++;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			nodes[i].flag=1;
			nodes[i].nxt1=cnxt*m+rfr;
			nodes[i].nxt2=cfr*m+rnxt;
		     }
		  }
		  if(r>-m/2+1&&c>-n/2+1)
		  {
		     if((r1-r>0&&c1-c>0)||(r1-r<0&&c1-c<0))
		     {
			nodes[i].flag=0;
			dcn++;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			if(r1-r>0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cfr*m+rnxt;
			   nodes[i].nxt2=cnxt*m+rfr;
			}
			if(c1-c>0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cnxt*m+rfr;
			   nodes[i].nxt2=cfr*m+rnxt;
			}
		     }
		  }
	       }

	       if(r<=0&&c>0)    //in Q4 quadrant
	       {
		  if(r==0)
		  {
		     nodes[i].flag=1;
		     nodes[i].nxt1=cnxt*m+rfr;
		     nodes[i].nxt2=cfr*m+rnxt;
		  }
		  if(c==1&&r!=0)
		  {
		     nodes[i].flag=1;
		     nodes[i].nxt1=cfr*m+rnxt;
		     nodes[i].nxt2=cnxt*m+rfr;
		  }
		  if(r!=0&c!=1)
		  {
		     if(r1==m/2)  r1=r1-m;
		     if(c1==-n/2+1)  c1=c1+n;
		     if((r1-r>0&&c1-c<0)||(r1-r<0&&c1-c>0))
		     {
			dcn++;
			nodes[i].flag=0;
			nodes[i].nxt1=cfr*m+rnxt;
			nodes[i].nxt2=cnxt*m+rfr;
		     }
		     else
		     {
			if(r1-r>0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cfr*m+rnxt;
			   nodes[i].nxt2=cnxt*m+rfr;
			}
			if(c1-c<0)
			{
			   nodes[i].flag=1;
			   nodes[i].nxt1=cnxt*m+rfr;
			   nodes[i].nxt2=cfr*m+cnxt;
			}
		     }
		  }
	       }
	    }
	 }
      }
      T[0].flag=0;
      T[0].i1=0;
      T[0].i2=1;
      T[0].q1=1.0;
      T[0].q2=0.0;
      j=0;
      for(i=1;i<NN;i++)
      {
	 if(nodes[i].flag==0)
	 {
	    T[i].flag=0;
	    T[i].i1=nodes[i].nxt1;
	    T[i].i2=nodes[i].nxt2;
	    T[i].q1=0.5;
	    T[i].q2=0.5;
	    dc[j]=i;
	    j++;
	 }
	 else
	 {
	    T[i].flag=1;
	    T[i].i1=nodes[i].nxt1;
	    T[i].i2=nodes[i].nxt2;
	    T[i].q1=0.75;
	    T[i].q2=0.25;
	 }
      }
}



void TP(float * P1, float * P0)
{
   int i, j;

   for(i=0;i<NN;i++)
      P1[i]=0.0;
   for(i=0;i<NN;i++)
   {
      j=T[i].i1;
      P1[j]=P1[j]+T[i].q1*P0[i];
      j=T[i].i2;
      P1[j]=P1[j]+T[i].q2*P0[i];
   }
}



int mod(int x, int y)
{
   if(x<0)
      x=x%y+y;
   else
      x=x%y;
   return x;
}