mpptest.c

mpi 结合vc编程用模拟退火法算一个最小路径的值

	new[i].next = &new[i+1];
	new[i].prev = &new[i-1];
    }
    new[0].next	       = &new[1];
    new[0].prev	       = 0;
    new[nsizes-1].next = 0;
    new[nsizes-1].prev = &new[nsizes-2];
    /* Note that the last member (new[nsizes]) has null prev and next */

    return new;
}

void FreeResults( TwinResults *twin_p )
{
    free( twin_p );
}

/* Initialize the results array for a strided set of data */
void SetResultsForStrided( int first, int last, int incr, TwinResults *twin )
{
    int i = 0, len;
    for (len=first; len<=last; len += incr) {
	twin[i].len = len;
	twin[i].t   = HUGE_VAL;
	i++;
    }
    /* Fixup list */
    twin[i-1].next = 0;
    twin[i].prev   = 0;

    /* Setup to the avail list */
    twin_avail = &twin[i];
}

/* Initialize the results array of a given list of data */
void SetResultsForList( int sizelist[], int nsizes, TwinResults *twin )
{
    int i = 0;
    for (i=0; i<nsizes; i++) {
	twin[i].len = sizelist[i];
	twin[i].t   = HUGE_VAL;
    }
    /* Fixup list */
    twin[i-1].next = 0;
    twin[i].prev   = 0;

    /* Setup to the avail list */
    twin_avail = &twin[i];
}

/* Run a test for a single entry in the list. Return 1 if the test
   was accepted, 0 otherwise */
int RunTest( TwinResults *twin_p, double (*CommTest)(int,int,void *),
	     void *msgctx, double wtick )
{
    double t;

    t = (*CommTest)( twin_p->n_avg, twin_p->len, msgctx );
    /* t is the time over all (n_avg tests) */

    /* Make sure that everyone has the same time value so that
       they'll make the same decisions.  
     */
    MPI_Bcast( &t, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD );
    CheckTimeLimit();

#if DEBUG_AUTO
    printf( "test(%d) for %d iterations took %f time\n", 
	    twin_p->len, twin_p->n_avg, t );
#endif    
    /* Accept times only if they are much longer than the clock resolution */
    if (t > 100*wtick) {
	twin_p->n_loop++;
	twin_p->sum_time += t;
	twin_p->ntests   += twin_p->n_avg;
	/* Now, convert t to a per-loop time */
	t = t / twin_p->n_avg;
	if (t < twin_p->t) {
	    twin_p->t = t;
	    /* This could set only when t < (1-repsThresh) (previous value) */
	    twin_p->new_min_found = 1;
	}
	else
	    twin_p->new_min_found = 0;
	if (t > twin_p->max_time) twin_p->max_time = t;
	return 1;
    }
    return 0;
}

/* For each message length in the list, run the experiement CommTest.
   Return the number of records that were updated */
int RunTestList( TwinResults *twin_p, double (*CommTest)(int,int,void *),
		  void *msgctx )
{
    int n_trials;  /* Used to bound the number of retries when total time
		      is too small relative to gwtick */
    int n_updated = 0;  /* Number of fields that were updated with a 
			 new minimum */

    while (twin_p) {
        n_trials = 0;
        while (n_trials++ < 10 && 
	       !RunTest( twin_p, CommTest, msgctx, gwtick )) {
	    /* This run failed to pass the test on wtick (time too short).
	       Update the #n_avg and try again 
	       Special needs: must ensure that all processes are informed */
	    twin_p->n_avg *= 2;
        }
	if (twin_p->new_min_found) n_updated++;
	twin_p = twin_p->next;
    }
#if DEBUG_AUTO
    printf( "Found %d new minimums\n", n_updated );
#endif
    return n_updated;
}

/* This estimates the time at twin_p using a linear interpolation from the
   surrounding entries */
double LinearTimeEst( TwinResults *twin_p, double min_dx )
{
    return LinearTimeEstBase( twin_p->prev, twin_p, twin_p->next, min_dx );
}

double LinearTimeEstBase( TwinResults *prev, TwinResults *cur, 
			  TwinResults *next, double min_dx )
{
    double t_prev, t_next, t_est, dn_prev, dn_next;

    /* Look at adjacent times */
    if (prev) {
	t_prev  = prev->t;
	dn_prev = cur->len - prev->len;
    }
    else {
	t_prev  = cur->t;
	dn_prev = min_dx;
    }
    if (next) {
	t_next  = next->t;
	dn_next = next->len - cur->len;
    }
    else {
	t_next  = cur->t;
	dn_next = min_dx;
    }
    /* Compute linear estimate, adjusting for the possibly unequal
       interval sizes, at twin_p->len. */
    t_est = t_prev + (dn_prev/(dn_next + dn_prev))*(t_next-t_prev);

    return t_est;
}

/* Add an entry to the list half way (in length) betwen prev and next */
TwinResults *InsertElm( TwinResults *prev, TwinResults *next )
{
    TwinResults *tnew;

    tnew = twin_avail;
    twin_avail = twin_avail->next;
    if (!twin_avail) {
	/* Now we have a problem.  I'm going to generate an error message and
	   exit */
	fprintf( stderr, 
"Exhausted memory for results while refining test interval\n\
Rerun with a smaller interval or without the -auto option\n" );
	fflush( stderr );
	MPI_Abort( MPI_COMM_WORLD, 1 );
    }
    twin_avail->prev = 0;
    
    tnew->next  = next;
    tnew->prev  = prev;
    prev->next  = tnew;
    next->prev  = tnew;
    tnew->len   = (prev->len + next->len) / 2;
    tnew->n_avg = next->n_avg;
    tnew->t     = HUGE_VAL;

#if DEBUG_AUTO
    printf( "%d running test with n_avg=%d, len=%d\n", 
	    __MYPROCID, tnew->n_avg, (int)tnew->len );fflush(stdout); 
#endif

    return tnew;
}

/* This is a breadth-first refinement approach.  Each call to this routine
   adds one level of refinement. */
int RefineTestList( TwinResults *twin, double (*CommTest)(int,int,void*),
		    void *msgctx, int min_dx, double autorel )
{
    double t_offset, t_center;
    double abstol = 1.0e-10;
    int do_refine, n_refined = 0;
    int n_loop, k;
    TwinResults *twin_p = twin, *tprev, *tnext;

    /* There is a dummy empty entry at the end of the list */
    if (!twin_avail->next) return 0;
    
    if (min_dx < 1) min_dx = 1;

    /* We find the next pointer and set the current and previous from
       that to ensure that we only look at values that were already
       computed, not the newly inserted values */
    tprev = 0;
    n_loop = 0;
    while (twin_p && twin_avail) {
	if (twin_p->n_loop > n_loop) n_loop = twin_p->n_loop;
        tnext = twin_p->next;
	/* Compute error estimate, adjusting for the possibly unequal
	 interval sizes.  t_center is the linear interpolation at tnew_p->len,
	 t_offset is the difference with the computed value */
	t_center = LinearTimeEstBase( tprev, twin_p, tnext, min_dx );
	t_offset = fabs(twin_p->t - t_center);
	do_refine = t_offset > (autorel * t_center + abstol);
	MPI_Bcast( &do_refine, 1, MPI_INT, 0, MPI_COMM_WORLD );
	if (do_refine) {
#ifdef DEBUG_AUTO
	    printf( "Refining at %d because predicted time %f far from %f\n",
		    twin_p->len, t_center, twin_p->t );
#endif
	    /* update the list by refining both segments */
	    if (twin_p->prev && twin_avail &&
		min_dx < twin_p->len - twin_p->prev->len) {
		(void)InsertElm( twin_p->prev, twin_p );
		n_refined ++; 
	    }
	    if (twin_p->next && twin_avail && 
		min_dx < twin_p->next->len - twin_p->len) {
		(void)InsertElm( twin_p, twin_p->next );
		n_refined ++;
	    }
	}
	tprev  = twin_p;
	twin_p = tnext;
    }
    MPI_Bcast( &n_refined, 1, MPI_INT, 0, MPI_COMM_WORLD );
    MPI_Bcast( &n_loop, 1, MPI_INT, 0, MPI_COMM_WORLD );

    /* Now, catch up the inserted elements with the rest of the results */
    for (k=0; k<n_loop; k++) {
	twin_p = twin;
	while (twin_p) {
	    if (twin_p->n_loop < n_loop) {
		int n_trials = 0;
		while (n_trials++ < 5 && 
		       !RunTest( twin_p, CommTest, msgctx, gwtick )) {
		    twin_p->n_avg *= 2;
		}
	    }
	    twin_p = twin_p->next;
	}
    }
    return n_refined;
}

/* Initialize the number of tests to run over which the average time is 
   computed. */
void SetRepsForList( TwinResults *twin_p, int n_avg )
{
    while (twin_p) {
	twin_p->n_avg = n_avg;
	twin_p        = twin_p->next;
    }
}

/* Smooth the entries in the list by looking for anomolous results and 
   rerunning those tests */
int SmoothList( TwinResults *twin, double (*CommTest)(int,int,void*),
		void *msgctx )
{
    double t_est;
    int do_test;
    TwinResults *twin_p = twin;
    int n_smoothed = 0;
    
    while (twin_p) {
	/* Look at adjacent times */
	if (__MYPROCID == 0) {
	    t_est = LinearTimeEst( twin_p, 4.0 );
	    do_test = (twin_p->t > 1.1 * t_est);
	}
	MPI_Bcast( &do_test, 1, MPI_INT, 0, MPI_COMM_WORLD );
	if (do_test) {
	    n_smoothed += RunTest( twin_p, CommTest, msgctx, gwtick );
	}
	twin_p = twin_p->next;
    }
    MPI_Bcast( &n_smoothed, 1, MPI_INT, 0, MPI_COMM_WORLD );
    return n_smoothed;
}

/* Output the results using the chosen graphics output package */
void OutputTestList( TwinResults *twin, void *outctx, int proc1, int proc2, 
		     int distance )
{
    TwinResults *twin_p = twin;
    double rate;

    while (twin_p) {
	if (twin_p->n_loop < 1 || twin_p->ntests < 1) {
	    /* Skip any tests that we could not successfully run */
	    twin_p = twin_p->next;
	    continue;
	}

	/* Compute final quantities */
	if (twin_p->t > 0) 
	    rate = ((double)twin_p->len) / twin_p->t;
	else
	    rate = 0.0;

	DataoutGraph( outctx, proc1, proc2, distance, 
		      (int)twin_p->len, twin_p->t * TimeScale,
		      twin_p->t * TimeScale, 
		      rate * RateScale, 
		      twin_p->sum_time / twin_p->ntests * TimeScale, 
		      twin_p->max_time * TimeScale );
	twin_p = twin_p->next;
    }
}

void CheckTimeLimit( void )
{
    /* Check for max time exceeded */
    if (__MYPROCID == 0 && MPI_Wtime() - start_time > max_run_time) {
	fprintf( stderr, "Exceeded %f seconds, aborting\n", max_run_time );
	MPI_Abort( MPI_COMM_WORLD, 1 );
    }
}