gmm.c

MPICH是MPI的重要研究,提供了一系列的接口函数,为并行计算的实现提供了编程环境.

      else
	  printf("colours ^ columns too big (should be < %f)\n", MAX_GUESST);
  } 
  while (1)
    {
      printf("Number of tasks: ");
      fflush(stdout);
      i = scanf("%d", &numtasks);
      while(getchar() != 10);
      if (i > 0 && numtasks > 1 && numtasks <=MAXTASKS )
	break;
      else
	printf("This should be a number between 2 and %d\n", MAXTASKS);
    }
#endif

  slaves_active = numslaves;
  get_secret();
  initialize_mm(0);

  /* initial distribution of tasks */

  task_size = search_space_size/numtasks;
  if (task_size < MIN_TASK_SIZE)
      task_size = MIN_TASK_SIZE;
  task_step = numslaves*task_size;

#ifdef LOGGING
  MPE_Start_log();
#endif

  for (worker = 1; worker <= numslaves; worker++)
  {
    j=0;
    for (tsk = (worker-1)*task_size; tsk<search_space_size; tsk+=task_step)
      {
	initial_tasks[j] = tsk;
	if (tsk+task_size<=search_space_size)
	  initial_tasks[j+1] = task_size;
	else
	  initial_tasks[j+1] = search_space_size-tsk;
	j+=2;
      }

#ifdef LOGGING
  MPE_Log_event(3,0,"");
#endif
    MPI_Send(initial_tasks, j, MPI_GUESST, 
	     worker, TASK, MPI_COMM_WORLD);
#ifdef LOGGING
  MPE_Log_event(4,0,"");
#endif
  }
      
  starttime = MPI_Wtime();


  while(!game_over)
    {

#ifdef LOGGING
	MPE_Log_event(5,0,"");
#endif
	MPI_Recv(guess, MAX_MSG_LENGTH, MPI_INT, MPI_ANY_SOURCE,
		       MPI_ANY_TAG, MPI_COMM_WORLD, &status);
#ifdef LOGGING
	MPE_Log_event(6,0,"");
#endif
      source = status.MPI_SOURCE;
      switch (status.MPI_TAG)
	{
	case FINISHED:
	  printf("Slave %d finished at%8.3f, %2d%%(s%d)\n", 
		 source, MPI_Wtime()-starttime, guess[0], source);
	  slaves_active--;
	  break;
	case GUESS:
	  row_num = guess[columns];
	  done_pcnt = guess[columns+1];
	  if (row_num == next_row)
	    {
	      eval_guess(guess, secret, &bulls, &cows);

	      board[next_row][0] = bulls;
	      board[next_row][1] = cows;
	      for (i=0; i<columns; i++)
		board[next_row][i+2] = guess[i];

/*	      printf("%2d: %3d. ", source, next_row); */
	      printf("%3d. ", next_row+1); 
	      print_guess("", guess);
	      printf("(%2db %2dc)%8.3fs, %2d%%(s%d)\n", 
		     bulls, cows, MPI_Wtime()-starttime, 
		     done_pcnt, source);
	      if (bulls == columns) /* game over */
		{
		  for (i = 1; i <= numslaves; i++)
		    MPI_Send(NULL, EXIT_LENGTH, MPI_INT, i,
			     (i==source?WON:EXIT), MPI_COMM_WORLD);
		  game_over = 1;
		}
	      else
		{
		  for (i = 1; i <= numslaves; i++)
		  {
#ifdef LOGGING
		      MPE_Log_event(1,0,"");
#endif
		    if (i == source)
		      MPI_Send(&board[next_row][0], ACCEPTED_LENGTH, MPI_INT, 
			       source, ACCEPTED, MPI_COMM_WORLD);
		    else
		      {
			board[row_num][columns+2] = source;
			MPI_Send(&board[row_num][0], NEW_INFO_LENGTH, 
				 MPI_INT, i, NEW_INFO, MPI_COMM_WORLD);
		      }
#ifdef LOGGING
		      MPE_Log_event(2,0,"");
#endif
		  }
		}
#ifdef USE_GRAPHICS
	      sources[next_row] = source;
	      if (next_row < ROWS)
		{
		  draw_guess(next_row, 0, guess, source);
		  draw_score(next_row, bulls, cows);
		}
	      else /* scroll */
		for (i = next_row-ROWS+1, j = 0; i <=next_row; i++, j++)
		  {
		    draw_guess(j, 0, &board[i][2], sources[i]);
		    draw_score(j, board[i][0], board[i][1]);
		  }
	      MPE_Update(handle);
#endif
	      if (++next_row >= MAXGUESSES)
		{
		  printf("Mastermind board overflow, aborting\n");
		  for (i = 1; i <= numslaves; i++)
		    MPI_Send(NULL, EXIT_LENGTH, MPI_INT, i, EXIT, 
			     MPI_COMM_WORLD);
		  game_over = 1;
		}

	    }
	  break;
	default:
	  fprintf(stderr,"master received invalid type %d\n", 
		  status.MPI_TAG);
	}
    }
  endtime = MPI_Wtime();
  printf("MM for %2d slaves, %2d colours, %2d columns: %8.3fs, %2d guesses\n", 
	 numslaves, colours, columns, endtime - starttime, next_row);

  while(slaves_active)
    {
#ifdef LOGGING
	MPE_Log_event(3,0,"");
#endif
	MPI_Recv(guess, MAX_MSG_LENGTH, MPI_INT, MPI_ANY_SOURCE,
		       MPI_ANY_TAG, MPI_COMM_WORLD, &status);
#ifdef LOGGING
	MPE_Log_event(4,0,"");
#endif
      source = status.MPI_SOURCE;
      switch (status.MPI_TAG)
	{
	case FINISHED:
	  printf("Slave %d finished at%8.3f, %2d%%(s%d)\n", 
		 source, MPI_Wtime()-starttime, guess[0], source);
	  slaves_active--;
	  break;
	case GUESS:
	  break;
	default:
	  fprintf(stderr,"master received invalid type %d\n", 
		  status.MPI_TAG);
	}
    }

#ifdef USE_GRAPHICS
  /* just testing */
  MPE_Draw_string (handle, 15, 15, MPE_BLACK, "Hello, world!" );
  /*  */

  printf("Any key to exit\n");
  scanf("%c",&i);
#endif
}

GUESST next_guess(col)
     int col;
{
  int i;
  GUESST pos = 1, cnt = 0;
  for (i = columns-1; i>=col+1; i--)
    {
      cnt += CURR_GUESS[i]*pos;   
      CURR_GUESS[i] = 0;
      pos *= colours;
    }

  for (i = col; i>=0; i--)
    if (CURR_GUESS[i] < colours-1)
      {
	CURR_GUESS[i]++;
	break;
      }
    else /* CURR_GUESS[i] == colours-1 */
      CURR_GUESS[i] = 0;

  return pos - cnt;
}
	  

eval_guess(guess, code, bulls, cows)
     int guess[], code[];
     int *bulls, *cows;
{
  int i,j;
  int tmp[MAXCOLS];

  for (i=0; i<columns; i++)
    tmp[i] = guess[i];

  *bulls = 0;
  *cows = 0;
  for (i=0; i<columns; i++)
    if (guess[i] == code[i])
      (*bulls)++;
  for (i=0; i<columns; i++)
    for (j=0; j<columns; j++)
      if (code[i] == tmp[j])
	{
	  (*cows)++;
	  tmp[j] = -1; /* nonexistent colour */
	  break;
	}
  *cows -= *bulls;
}

/*
   col is initially set to 'columns', i.e. the column after the last one
   (columns being numbered from 0 to columns-1).

   When an inconsistency with a row of the board is found, col is set to
   the column where the inconsistency is detected.

   After an inconsistency has been found, we still keep checking the board,
   so that further rows of the board can cause col to move leftwards (I
   don't know if this pays off, perhaps worth profiling).

   If all rows tested and col still points to 'columns', than the guess is
   found to be consistent with the board.

   Otherwise the guess is inconsistent and col is returned as the leftmost
   col_to_change.

  */

guess_consistent(col_to_change)
     int *col_to_change;
{
  int bulls, bullscows, col, row, peg;
  int *board_row;
  int i,j;
  int tmp[MAXCOLS];

  col = columns;

  for (row = 0; row < next_row; row++)
    {
      board_row = &board[row][2];
      bulls = board[row][0];
      bullscows = board[row][1]+bulls;

      for (i=0; i<columns; i++)
	tmp[i] = board_row[i];

      for (i=0; i < col; i++)
	{
	  if (CURR_GUESS[i] == board_row[i]) /* bull */
	    {
	      if ((bulls--) <= 0)       /* too many bulls */
	      break;
	    }
	  j = 0;
	  peg = CURR_GUESS[i];
	  while ( j < columns && peg != tmp[j])
	    j++;
	  if (j < columns )             /* bull or cow */
	    if (bullscows-- <= 0)       /* too many bulls or cows */
	      break;
	    else
	      tmp[j] = NO_COLOUR;
	  if (bullscows >= columns-i)   /* too few bulls of cows */
	    break;
	}
      col = i;
    }

  if (col == columns)
    return 1;
  
  *col_to_change = col;
  return 0;      
}

print_guess(text, guess)
     char *text;
     int guess[];
{
  int i;

  printf("%s", text);
  for (i=0; i<columns; i++)
    {
      printf("%2d ", guess[i]);
    }
}

#ifdef USE_GRAPHICS
draw_guess(row, col, guess, id)
     int row, col, id;
     int guess[];
{
  int i;
  int hpos = left_col_width*col+HDIST+WORKER_HDIST;
  int vpos = (row+2)*VDIST;
  
  MPE_Fill_rectangle(handle, hpos-(HDIST-2*RADIUS+WORKER_WIDTH), 
		     (int)(vpos-WORKER_HEIGHT/2), WORKER_WIDTH, WORKER_HEIGHT,
		     WorkerColour(id));

  for (i=0; i<columns; i++)
    {
      MPE_Fill_circle( handle, hpos, vpos, RADIUS, PegColour(guess[i]) );
      hpos += HDIST;
    }
}

draw_score(row, bulls, cows)
     int row, bulls, cows;
{
  int r,c, i;
  int vpos = (row+2)*VDIST-RADIUS+SCORE_RADIUS;
  int hpos = left_col_width-HDIST-SCORE_WIDTH;

  for (r=0; r<SCORE_ROWS; r++)
    for (c=0; c<SCORE_COLS; c++)
      {
	i = SCORE_COLS*r+c;
	if (i < bulls)
	  MPE_Fill_circle( handle, hpos+SCORE_HDIST*c, 
			  vpos+SCORE_VDIST*r, SCORE_RADIUS, MPE_BLACK);
	else if (i < bulls+cows)
	  MPE_Draw_circle( handle, hpos+SCORE_HDIST*c, 
			  vpos+SCORE_VDIST*r, SCORE_RADIUS, MPE_BLACK);
	else
	  break;
      }
}

draw_progress(row, type, source)
     int row, type, source;
{
  int hpos = left_col_width+HDIST+WORKER_HDIST-RADIUS;
  int vpos = (row+2)*VDIST+2*RADIUS;
  int length;

  length = (int)((((double) guesses_done)/search_space_size)
		 * ((columns-1)*HDIST+2*RADIUS));

  MPE_Draw_line(handle, hpos, vpos, hpos+length, vpos, MPE_BLACK);

  switch (type)
    {
    case PROGRESS:
            break;
    case ACCEPTED:
	    MPE_Draw_line(handle, hpos+length, vpos, hpos+length, 
			  vpos-2*SUCCESS_HEIGHT, WorkerColour(myid));
	    break;
    case REJECTED:
	    MPE_Draw_line(handle, hpos+length, vpos, hpos+length, 
			  vpos+SUCCESS_HEIGHT, MPE_BLACK);
    case NEW_INFO:
	    MPE_Draw_line(handle, hpos+length, vpos, hpos+length, 
			  vpos-SUCCESS_HEIGHT, WorkerColour(source));
	    break;
    }
}

#endif

get_secret()
{
  int i;

  for (i=0; i<columns; i++)
    if (i<colours)
      secret[i] = colours-1-i;
    else
      secret[i] = 0;
}

GUESST int_power(n, m)
int n,m;
{
  int i;
  GUESST pw = 1;

  for (i=0; i<m; i++)
    pw*=n;

  return pw;
}

initialize_mm()
{
  int right_col_width, colourscale_width, i;
  
  MPI_Bcast(&colours, 1, MPI_INT, 0, MPI_COMM_WORLD);
  MPI_Bcast(&columns, 1, MPI_INT, 0, MPI_COMM_WORLD);
  
  search_space_size = int_power(colours, columns);

#ifdef USE_GRAPHICS
  left_col_width = WORKER_HDIST+(columns+2)*HDIST+SCORE_WIDTH;
  right_col_width = (columns+1)*HDIST;
  colourscale_width = (colours+2)*COLOURSCALE_HDIST;
  if (right_col_width < colourscale_width)
    right_col_width = colourscale_width;
  width = left_col_width+WORKER_HDIST+right_col_width;
  height = (ROWS+2)*VDIST - VDIST/2;
  
  MPE_Open_graphics( &handle, MPI_COMM_WORLD, (char*)0, 
		    -1, -1, width, height, MPE_GRAPH_INDEPDENT);

  if (myid > 0)
    return;

  for (i=0; i<columns; i++)
    {
      MPE_Fill_circle( handle, HDIST*(i+1)+WORKER_HDIST, 
		      (int)(0.6*VDIST), RADIUS, PegColour(secret[i]) );
    }
  for (i=0; i<colours; i++)
    {
      MPE_Fill_rectangle(handle, left_col_width+HDIST+WORKER_HDIST-RADIUS
			 +i*COLOURSCALE_HDIST, (int)(0.6*VDIST)-RADIUS, 
			 COLOURSCALE_WIDTH, 2*RADIUS,
			 PegColour(i));
    }
  MPE_Draw_line(handle, 0, (int)(1.3*VDIST), width, (int)(1.3*VDIST), 
		MPE_BLACK);
  MPE_Draw_line(handle, 0, (int)(1.4*VDIST), width, (int)(1.4*VDIST), 
		MPE_BLACK);
  MPE_Draw_line(handle, (int)(left_col_width-0.3*HDIST), 0, 
		(int)(left_col_width-0.3*HDIST), height,
		MPE_BLACK);
  MPE_Draw_line(handle, (int)(left_col_width-0.4*HDIST), 0, 
		(int)(left_col_width-0.4*HDIST), height,
		MPE_BLACK);
#endif
}

trace_guess(txt1, txt2)
char *txt1, *txt2;
{
  printf("%2d: ", myid);
  print_guess(txt1, CURR_GUESS);
  printf(", guesses_done = %d%s", guesses_done, txt2);
}

init_free_task_storage(used)
int used;
{
    int i;

    if (used<MAXTASKS)
    {
	for (i=used; i < MAXTASKS-1; i++)
	{
	    task_storage[i].next = &task_storage[i+1];
	    task_storage[i+1].previous = &task_storage[i];
	}
	
	task_storage[MAXTASKS-1].next = NULL;
	task_storage[used].previous = NULL;
	free_tasks = &task_storage[used];
    }
    else
	free_tasks = NULL;
}

add_to_free_list(task)
TASKT *task;
{
    task->next = free_tasks;
    task->previous = NULL;
    free_tasks->previous = task;
    free_tasks = task;
}