rm.c

基于linux环境的ns2多机并行仿真补丁

/*----------------------------------------------------------------------------*/
/* Returns the communication schedule based on star pattern.                  */
/*----------------------------------------------------------------------------*/
static void compute_star_schedule
(
    int i,
    int N,
    int mx,
    int *ssize,
    int ids[],
    int rs[],
    int js[],
    int ro[]
)
{
    int ss = 0;  /* Size of the schedule returned */
    int hub = 0; /* ID of hub processor of the star pattern */

    assert( 0 <= i && i < N );
    #define CHK() do{if(ss>=mx){printf("Add more actions!\n");return;}}while(0)

    /* First receive local value from self */
    {CHK(); ids[ss]=i; rs[ss]=TRUE; js[ss]=FALSE; ro[ss]=TRUE; ss++;}

    if( i != hub )
    {
        {CHK(); ids[ss]=hub; rs[ss]=FALSE; js[ss]=FALSE;
	 ro[ss]=FALSE; ss++;} /*send to hub*/

        {CHK(); ids[ss]=hub; rs[ss]=TRUE; js[ss]=FALSE;
	 ro[ss]=FALSE; ss++;}/*recv from hub*/
    }
    else
    {
	int j = 0;
	for( j = 0; j < N; j++ )
	{
	    if( j != hub )
              {CHK(); ids[ss]=j; rs[ss]=TRUE; js[ss]=FALSE;
	       ro[ss]=TRUE; ss++;} /*recv*/
	}
	for( j = 0; j < N; j++ )
	{
	    if( j != hub )
              {CHK(); ids[ss]=j; rs[ss]=FALSE; js[ss]=FALSE;
	       ro[ss]=FALSE; ss++;}/*send*/
	}
    }

    #undef CHK

    *ssize = ss;
}

/*----------------------------------------------------------------------------*/
/* Returns the communication schedule based on butterfly pattern.             */
/*----------------------------------------------------------------------------*/
static void compute_butterfly_schedule
(
    int i,
    int N,
    int mx,
    int *ssize,
    int ids[],
    int rs[],
    int js[],
    int ro[]
)
{
    int lgm = highest_exponent_of_2_in(N); /* Largest lgm so that (2^lgm <= N)*/
    int m = highest_power_of_2_in(N);      /* Same as 2^lgm */
    int ss = 0;                            /* Size of the schedule returned */

    assert( (1<<lgm) == m );
    assert( 0 <= i && i < N );
    #define CHK() do{if(ss>=mx){printf("Add more actions!\n");return;}}while(0)

    /* First receive local value from self */
    {CHK(); ids[ss]=i; rs[ss]=TRUE; js[ss]=FALSE; ro[ss]=TRUE; ss++; }

    if( i >= m )
    {
        /* i is an outlier processor */

        {CHK(); ids[ss]=i - m; rs[ss]=FALSE; js[ss]=FALSE;
	 ro[ss]=FALSE; ss++;} /*send*/

        {CHK(); ids[ss]=i - m; rs[ss]=TRUE; js[ss]=FALSE;
	 ro[ss]=FALSE; ss++;} /*recv*/
    }
    else
    {
        int k = 0;

        /* i is a butterfly processor */
        if( i + m < N )
        {
            /*Receive from the outlier processor that i is responsible for*/

            {CHK(); ids[ss]=i + m; rs[ss]=TRUE; js[ss]=TRUE;
	     ro[ss]=TRUE; ss++;}  /*recv*/
        }

        for( k = 0; k < lgm; k++ )
        {
            int partner = i ^ (1 << k); /* i toggled in the k'th bit */

            {CHK(); ids[ss]=partner; rs[ss]=FALSE; js[ss]=FALSE;
	     ro[ss]=FALSE; ss++;}/*send*/

            {CHK(); ids[ss]=partner; rs[ss]=TRUE; js[ss]=TRUE;
	     ro[ss]=TRUE; ss++;} /*recv*/
        }

        if( i + m < N )
        {
            /*Send to the outlier processor*/

            {CHK(); ids[ss]=i + m; rs[ss]=FALSE; js[ss]=FALSE;
	     ro[ss]=FALSE; ss++;}  /*send*/
        }
    }

    #undef CHK

    *ssize = ss;
}

/*----------------------------------------------------------------------------*/
/* Returns a newly allocated duplicate of given string.                       */
/*----------------------------------------------------------------------------*/
static char *copystr( const char *orig )
{
    char *copy = (char *)malloc(strlen(orig)+1);
    strcpy( copy, orig );
    return copy;
}

/*----------------------------------------------------------------------------*/
/* Returns the communication schedule based on a "grouped" butterfly pattern. */
/*----------------------------------------------------------------------------*/
static void get_gids( const char *orig_estr, int gids[], int N )
{
    int j = 0;
    char *estr = copystr(orig_estr);

    /*Parse off gids of the form "g1 n@g2 gk ... ".*/
    /*The n@g2 is short for g2 appearing n times. */
    for( j = 0; j < N; )
    {
	int inst = 0, ninstances = 1, k = -1;
	char *blank = 0, *at = 0;

	blank = strchr( estr, ' ' );
	if(blank) *blank = 0;

	at = strchr( estr, '@' );
	if( at )
	{
	    *at = 0;
	    ninstances = atoi(estr);
	    assert( 0 <= ninstances && j+ninstances <= N );
	    estr = at+1;
	}

	k = atoi(estr);
	assert( 0 <= k && k < N );
	for( inst = 0; inst < ninstances; inst++ )
	{
	    assert( j < N );
	    gids[j++] = k;
	}

	if(blank) estr = blank+1;
    }
}

/*----------------------------------------------------------------------------*/
/* Returns the communication schedule based on a "grouped" butterfly pattern. */
/*----------------------------------------------------------------------------*/
static void compute_grouped_bfly_schedule
(
    int i,
    int N,
    int mx,
    int *ssize,
    int ids[],
    int rs[],
    int js[],
    int ro[]
)
{
    #define MAXN 4096

    int ss = 0;                            /* Size of the schedule returned */
    int j = 0, gids[MAXN];
    char *estr = getenv("RM_NODEGROUPS");

if(!estr) {compute_butterfly_schedule(i,N,mx,ssize,ids,rs,js,ro ); return;}

if(dbg>=1){printf("Using grouping info: \"%s\"\n",estr);fflush(stdout);}

    assert( !!estr );
    assert( 0 < N && N <= MAXN );
    assert( 0 <= i && i < N );

    get_gids( estr, gids, N );

    for( j = 0; j < N; j++ ) assert( gids[j] == gids[gids[j]] );

    #define CHK() do{if(ss>=mx){printf("Add more actions!\n");return;}}while(0)

    if( gids[i] != i )
    {

        /* First receive local value from self */
        {CHK(); ids[ss]=i; rs[ss]=TRUE; js[ss]=FALSE; ro[ss]=TRUE; ss++; }

        /*Then, send to & recv from this processor's group leader*/

        {CHK(); ids[ss]= gids[i]; rs[ss]=FALSE; js[ss]=FALSE;
	 ro[ss]=FALSE; ss++;} /*send*/

        {CHK(); ids[ss]= gids[i]; rs[ss]=TRUE; js[ss]=FALSE;
	 ro[ss]=FALSE; ss++;} /*recv*/
    }
    else
    {
        /*Receive from members of group this processor is head/leader of*/
        for( j = 0; j < N; j++ )
        {
	    if( j != i && gids[j] == i )
	    {
                {CHK(); ids[ss]=j; rs[ss]=TRUE; js[ss]=TRUE;
	         ro[ss]=TRUE; ss++;}  /*recv*/
	    }
        }

        /* Reduce with other group heads using butterfly schedule */
	{
	#define MAXHACTIONS 1000
        int nheads = 0, heads[MAXN], myheadid = -1, hssize = 0;
        int hids[MAXHACTIONS], hrs[MAXHACTIONS];
	int hjs[MAXHACTIONS], hro[MAXHACTIONS];
	for( j = 0; j < N; j++ )
	{
	    if( gids[j] == j )
	    {
	        heads[nheads] = j;
	        if( gids[j] == i ) myheadid = nheads;
		nheads++;
	    }
	}
	assert( 0 < nheads && nheads <= N );
	assert( 0 <= myheadid && myheadid < nheads );
        compute_schedule( RM_SCHEDULE_BUTTERFLY, myheadid, nheads,
	                  MAXHACTIONS, &hssize, hids, hrs, hjs, hro );
	#undef MAXHACTIONS
	for( j = 0; j < hssize; j++ )
	{
            {CHK(); ids[ss]=heads[hids[j]]; rs[ss]=hrs[j]; js[ss]=hjs[j];
	     ro[ss]=hro[j]; ss++;}
	}
	}

        /*Send to members of group this processor is head of*/
        for( j = 0; j < N; j++ )
        {
	    if( j != i && gids[j] == i )
	    {
                {CHK(); ids[ss]=j; rs[ss]=FALSE; js[ss]=FALSE;
	         ro[ss]=FALSE; ss++;}  /*send*/
	    }
        }
    }

    #undef CHK

    *ssize = ss;

    #undef MAXN
}

/*----------------------------------------------------------------------------*/
/* Returns the communication schedule based on a "phase" butterfly pattern.   */
/* Added by Alfred Park <[e-mail]> 09 Dec 2002                      */
/*----------------------------------------------------------------------------*/
static void compute_phase_bfly_schedule
(
    int i,
    int N,
    int mx,
    int *ssize,
    int ids[],
    int rs[],
    int js[],
    int ro[]
)
{
    #define MAXN 4096

    int ss = 0;                            /* Size of the schedule returned */
    int j = 0, gids[MAXN], k, first, last, span;
    char *estr = getenv("RM_NODEGROUPS");

    int lgm, m;

    if (dbg>0) printf("N: %d, i: %d\n", N, i);

if(!estr) {compute_butterfly_schedule(i,N,mx,ssize,ids,rs,js,ro ); return;}

if(dbg>=1){printf("Using grouping info: \"%s\"\n",estr);fflush(stdout);}

    assert( !!estr );
    assert( 0 < N && N <= MAXN );
    assert( 0 <= i && i < N );

    get_gids( estr, gids, N );

    for( j = 0; j < N; j++ ) assert( gids[j] == gids[gids[j]] );

    /* find grouping for this processor */
    first = -1;
    last = -1;
    for( j = 0; j < N; j++ ) {
      if( gids[j] == gids[i] ) {
	if( first == -1 )
	  first = j;
      } else if( first != -1 ) {
	break;
      }
    }
    last = j - 1;
    span = last - first + 1;
    lgm = highest_exponent_of_2_in(span);
    m = highest_power_of_2_in(span);
    
if (dbg>0) printf("lgm = %d, m = %d, first = %d, last = %d\n", lgm, m, first, last);

    #define CHK() do{if(ss>=mx){printf("Add more actions!\n");return;}}while(0)


    /* First receive local value from self */
    {CHK(); ids[ss]=i; rs[ss]=TRUE; js[ss]=FALSE; ro[ss]=TRUE; ss++; }

    /* i is an outlier processor */
    if ( i - first >= m ) {
      {CHK(); ids[ss]=i - m; rs[ss]=FALSE; js[ss]=FALSE;
      ro[ss]=FALSE; ss++;} /*send*/	  
      
      {CHK(); ids[ss]=i - m; rs[ss]=TRUE; js[ss]=FALSE;
      ro[ss]=FALSE; ss++;} /*recv*/
    } else {
      /* i is a butterfly processor */
      if (i - first + m < span) {
	/* recv from outlier */
	{CHK(); ids[ss]=i + m; rs[ss]=TRUE; js[ss]=TRUE;
	ro[ss]=TRUE; ss++;}
      }
      for( k = first; k < (first + lgm); k++ ) {
	int partner = i ^ (1 << (k - first));
	
	if (dbg>0) printf("i = %d, k = %d, partner = %d\n", i,k,partner);
	
	{CHK(); ids[ss]=partner; rs[ss]=FALSE; js[ss]=FALSE;
	ro[ss]=FALSE; ss++;} /*send*/
	
	{CHK(); ids[ss]=partner; rs[ss]=TRUE; js[ss]=TRUE;
	ro[ss]=TRUE; ss++;} /*recv*/
      }
    }

    if ( i - first + m < span ) {
      /* send to outlier */
      {CHK(); ids[ss]=i + m; rs[ss]=FALSE; js[ss]=FALSE;
      ro[ss]=FALSE; ss++;} /*send*/
    }


    if( gids[i] == i ) {

        /* Reduce with other group heads using butterfly schedule */
	{
	#define MAXHACTIONS 1000
        int nheads = 0, heads[MAXN], myheadid = -1, hssize = 0;
        int hids[MAXHACTIONS], hrs[MAXHACTIONS];
	int hjs[MAXHACTIONS], hro[MAXHACTIONS];
	for( j = 0; j < N; j++ )
	{
	    if( gids[j] == j )
	    {
	        heads[nheads] = j;
	        if( gids[j] == i ) myheadid = nheads;
		nheads++;
	    }
	}
	assert( 0 < nheads && nheads <= N );
	assert( 0 <= myheadid && myheadid < nheads );
        compute_schedule( RM_SCHEDULE_BUTTERFLY, myheadid, nheads,
	                  MAXHACTIONS, &hssize, hids, hrs, hjs, hro );
	#undef MAXHACTIONS
	for( j = 1; j < hssize; j++ ) /* HACK alert: Ignore 0th position */
	{
            {CHK(); ids[ss]=heads[hids[j]]; rs[ss]=hrs[j]; js[ss]=hjs[j];
	     ro[ss]=hro[j]; ss++;}
	}
	}

        /*Send to members of group this processor is head of*/
        for( j = 0; j < N; j++ )
        {
	    if( j != i && gids[j] == i )
	    {
                {CHK(); ids[ss]=j; rs[ss]=FALSE; js[ss]=FALSE;
	         ro[ss]=FALSE; ss++;}  /*send*/
	    }
        }
    } else {
      /* each group memeber needs to get new value from leader */
      {CHK(); ids[ss]=gids[i]; rs[ss]=TRUE; js[ss]=FALSE;
      ro[ss]=FALSE; ss++;} /*recv*/
    }

    #undef CHK

    *ssize = ss;

    #undef MAXN
}


/*----------------------------------------------------------------------------*/
/* Returns the receive and send communication schedule for this processor     */
/*----------------------------------------------------------------------------*/
int compute_schedule
(
    RMScheduleType pattern,
    int i,
    int N,
    int mx,
    int *ssize,
    int ids[],
    int rs[],
    int js[],
    int ro[]
)
{
   int retval = 0;
   switch( pattern )
   {
     case RM_SCHEDULE_STAR:
       { compute_star_schedule(i, N, mx, ssize, ids, rs, js, ro); break; }
     case RM_SCHEDULE_ALL_TO_ALL:
       { compute_all_to_all_schedule(i, N, mx, ssize, ids, rs, js, ro); break; }
     case RM_SCHEDULE_BUTTERFLY:
       { compute_butterfly_schedule(i, N, mx, ssize, ids, rs, js, ro); break; }
     case RM_SCHEDULE_GROUPED_BFLY:
       { compute_grouped_bfly_schedule(i, N, mx, ssize, ids, rs, js, ro);break;}
   case RM_SCHEDULE_PHASE_BFLY:
     { compute_phase_bfly_schedule(i, N, mx, ssize, ids, rs, js, ro); break; }
     default:
       { printf( "compute_schedule: Unknown pattern %d\n", pattern );
	 retval = -1; break; }
   }
   return retval;
}

/*----------------------------------------------------------------------------*/
void print_schedule
(
    FILE *fp,
    int i,
    int N,
    int ssize,
    int ids[],
    int rs[],
    int js[],
    int ro[]
)
{
    int j = 0;

    fprintf( fp, "----------------------------\n" );
    fprintf( fp, "--   Reduction Schedule   --\n" );
    fprintf( fp, "----------------------------\n" );
    for( j = 0; j < ssize; j++ )
    {
        fprintf( fp, "    %3d %s %3d", i, (rs[j] ? "<--" : "-->"), ids[j] );
	fprintf( fp, "%s", ((rs[j] && js[j]) ? " js" : "") );
	fprintf( fp, "%s\n", (rs[j] ? (ro[j] ? " r" : " o") : "" ) );
    }
    fprintf( fp, "----------------------------\n" );
    fflush( fp );
}

/*----------------------------------------------------------------------------*/
int test_schedule( int ac, char *av[] )
{
    int i = 0, N = 13, sched = RM_SCHEDULE_PHASE_BFLY;
    int ssize = 0;
    int ids[MAXACTIONS], rs[MAXACTIONS], js[MAXACTIONS], ro[MAXACTIONS];

    if( ac > 1 ) N = atoi(av[1]);
    if( ac > 2 ) sched = atoi(av[2]);

    printf( "N = %d, schedule = %d\n\n", N, sched );

    for( i = 0; i < N; i++ )
    {
        compute_schedule( sched, i, N, MAXACTIONS, &ssize, ids, rs, js, ro );
        print_schedule( stdout, i, N, ssize, ids, rs, js, ro );
    }
    return 0;
}

/*----------------------------------------------------------------------------*/
#if 0
int main(int ac, char *av[]){return test_schedule(ac,av);}
#endif

/*----------------------------------------------------------------------------*/