gmm.c

fortran并行计算包

/*
   (C) 2001 by Argonne National Laboratory.
       See COPYRIGHT in top-level directory.
*/
#define LOGGING
#include "mpi.h"
#ifdef USE_GRAPHICS
#define MPE_GRAPHICS
#include "mpe.h"
#endif
#include <stdio.h>
#include <math.h>

/* Numeric type representing a guess: double or unsigned long */
typedef double GUESST;
/* corresponding MPI type */
#define MPI_GUESST MPI_DOUBLE
/* 1 for GUESST=unsigned, 0 for  DOUBLE */
#define GUESST_INTEGRAL 0

#if GUESS_INTEGRAL
#define MAX_GUESST 4294967295.0 /* 2^32 - 1 */
#else
#define MAX_GUESST 18014398509481984.0 /* 2^54 - 1 */
#endif

/* message tags */
#define GUESS 0
#define GUESS_LENGTH columns+2
     /* guess[0],   ..., guess[columns-1], row_num, guesses_done */
#define ACCEPTED 1
#define ACCEPTED_LENGTH 2
     /* bulls, cows */
#define NEW_INFO 2
#define NEW_INFO_LENGTH columns+3
     /* bulls, cows, guess[0],..., guess[columns-1], source*/
#define EXIT 3
#define EXIT_LENGTH 0
#define WON 4
#define WON_LENGTH 0
#define TASK 5
#define TASK_LENGTH 2
     /* task_start, task_size */
#define TASK_REQ 6
#define TASK_REQ_LENGTH 0
#define FINISHED 7
#define FINISHED_LENGTH 1
#define MAX_MSG_LENGTH NEW_INFO_LENGTH

/* further internal tags */
#define REJECTED 5
#define PROGRESS 6


#ifdef USE_GRAPHICS
/* data for graphics */
#define HDIST 35
#define VDIST 50
#define ROWS 16
#define RADIUS 10
#define SCORE_RADIUS 3
#define SCORE_VDIST 8
#define SCORE_HDIST 8
#define SCORE_ROWS 4
#define SCORE_COLS 4
#define SCORE_WIDTH SCORE_COLS*SCORE_HDIST
#define WORKER_WIDTH 10
#define WORKER_HEIGHT 10
#define WORKER_HDIST 20
#define COLOURSCALE_WIDTH 20
#define COLOURSCALE_HDIST 30
#define SUCCESS_HEIGHT 4

/* Maps slave numbers 1, ..., numprocs-1 to MPE colours */
#define WorkerColour(N) N+1 /* To exclude black which is 1 */

/* Maps peg colours 0, ..., colours-1 to MPE colours */
#define PegColour(N) N+2

#endif /* USE_GRAPHICS */

/* max size of the mastermind board */
#ifdef USE_GRAPHICS
/* limitations of the graphics: */
#define MAXCOLS  SCORE_ROWS*SCORE_COLS
#define MAXCOLOURS 14 /* black and white excluded from the 16 allowed colours*/
#else
#define MAXCOLS  20
#define MAXCOLOURS 100
#endif
#define MAXGUESSES 500

#define MAXTASKS 1000
#define MIN_TASK_SIZE 20

#define MASTER_RANK 0
#define NO_COLOUR -1 /* different from any valid peg colour */

/* global variables */
int numprocs;
int myid;
int colours, columns, numtasks;
GUESST guesses_done;
GUESST search_space_size;

int guess[MAXCOLS+2];
int secret[MAXCOLS];

/* DATA STRUCTURES */

/* the structure of the board (should better be a struct!)
   board[i][0]  [1]    [2]         ...  [columns+1]       [columns+2]
   -----------  -----  ---------        ----------------  -----------
   bulls,       cows,  guess[0],   ..., guess[columns-1], source (worker num)

*/
int board[MAXGUESSES][MAXCOLS+3];
int sources[MAXGUESSES]; /* who does the guess come from */


typedef struct task 
{
    struct task *next;
    struct task *previous;
    int guess[MAXCOLS+2];
    GUESST guess_number;
    GUESST guesses_remaining;
} TASKT;

TASKT *free_tasks, *curr_task;

#define CURR_GUESS (curr_task->guess)
#define Check_Arg(Var, Txt, Low, High) \
  if (Var > High || Var < Low)\
    {\
      if (myid == 0)\
	printf("%s: %d, should be between %d and %d. Exiting.\n",\
	       Txt, Var, Low, High);\
      MPI_Finalize();\
      return;\
    }

TASKT task_storage[MAXTASKS];

GUESST initial_tasks[MAXTASKS*2];

int next_row;
int freq_counter;
#define FREQUENCY 500

#ifdef USE_GRAPHICS
int height, width, left_col_width;
MPE_XGraph handle;
#endif

extern GUESST next_guess();

main(argc, argv)
int argc;
char *argv[];
{

  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
  MPI_Comm_rank(MPI_COMM_WORLD, &myid);


#ifdef LOGGING
  MPE_Init_log();
  MPE_Stop_log();
  if (myid == 0) {
    MPE_Describe_state(1, 2, "Send",      "green:light_gray");
    MPE_Describe_state(3, 4, "Admin",     "blue:gray3");
    MPE_Describe_state(5, 6, "Receive",   "red:vlines3");
  }
#endif


#ifndef INTERACTIVE
  if (argc < 3)
    {
      if (myid == 0)
	fprintf(stderr, "usage: %s colours columns [tasks]\n", argv[0]);
      exit(1);
    }

  colours = atoi(argv[1]);
  columns = atoi(argv[2]);

  if (argc == 3)
    numtasks = 997;
  else
    numtasks = atoi(argv[3]);

  Check_Arg(colours, "Colours", 2, MAXCOLOURS);
  Check_Arg(columns, "Columns", 2, MAXCOLS);
  Check_Arg(numtasks,"Tasks",   1, MAXTASKS);
#endif

#ifdef USE_GRAPHICS
  Check_Arg(numprocs, "Processors", 2, ROWS+1);
#endif

  if (myid == 0)
    master();
  else
    slave();


#ifdef LOGGING
  MPE_Finish_log("gmm.log");
#endif


#ifdef USE_GRAPHICS
  MPE_Close_graphics(&handle);
#endif
  MPI_Finalize();
}

slave()
{
  int done;
  GUESST skipped;
  MPI_Status status;
  int i, j, k, flag, count, colour;
  int col_to_change;
  int numslaves = numprocs-1;

  guesses_done = 0;
  next_row = 0;
  initialize_mm();


#ifdef LOGGING
  MPE_Start_log();
  MPE_Log_event(3,0,"");
#endif

  MPI_Recv(initial_tasks, MAXTASKS*2, MPI_GUESST, 
	       MASTER_RANK, TASK, MPI_COMM_WORLD, &status);

#ifdef LOGGING
  MPE_Log_event(4,0,"");
#endif


  MPI_Get_count(&status, MPI_GUESST, &count);
  count /= 2;

  /* Get initial tasks */

  for (i=0, j=0; i< count; i++, j+=2)
  {
      GUESST guessnum = initial_tasks[j];
      task_storage[i].guess_number = guessnum;
      task_storage[i].guesses_remaining = initial_tasks[j+1];
      task_storage[i].previous = &task_storage[i-1];
      task_storage[i].next = &task_storage[i+1];
	     
      for (k=columns-1; k>=0;  k--)
	{
#if GUESST_INTEGRAL
	  task_storage[i].guess[k] = guessnum % colours;
	  guessnum /= colours;
#else
	  colour = (int) fmod(guessnum, (double) colours);
	  task_storage[i].guess[k] = colour;
	  guessnum = floor(((guessnum-colour)/(double)colours)+.1);
#endif	  
	}
  }

  task_storage[count-1].next = &task_storage[0];
  task_storage[0].previous = &task_storage[count-1];
  curr_task = &task_storage[0];

#ifdef DEBUG
  for (i=0; i<count;i++)
    {
      printf("Task_storage[%d] (0x%x) = (num=%d, rem=%d, prev=0x%x, next=0x%x)\n",
	     i, &task_storage[i], task_storage[i].guess_number,
	     task_storage[i].guesses_remaining,
	     task_storage[i].previous,
	     task_storage[i].next);
    }
#endif

  init_free_task_storage(count);

#ifdef PRINTING
  trace_guess("STARTING: ", "\n");
#endif
  freq_counter = FREQUENCY;

  done = 0;


  while(!done)
  {
      if (freq_counter-- == 0)
      {
#ifdef USE_GRAPHICS
	  draw_guess(myid-1, 1, CURR_GUESS, myid);
	  draw_progress(myid-1, PROGRESS, 0);
	  MPE_Update(handle);
#endif
	  while (1)
	  {
	      MPI_Iprobe(0, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
	      if (flag == 1)
	      {
		  if (status.MPI_TAG == EXIT)
		  {
		      MPI_Recv(NULL, EXIT_LENGTH, MPI_INT, MASTER_RANK,
			       EXIT, MPI_COMM_WORLD, &status);
		      done = 1;
		      break;
		  }
		  else if (status.MPI_TAG == NEW_INFO)
		  {
		      MPI_Recv(&board[next_row][0], NEW_INFO_LENGTH, MPI_INT, 
			       MASTER_RANK, NEW_INFO, MPI_COMM_WORLD, &status);
#ifdef USE_GRAPHICS
		      draw_progress(myid-1, NEW_INFO,
				    board[next_row][columns+2]);  
		      MPE_Update(handle);
#endif
#ifdef PRINTING
		      printf("%2d: NEW INFO, row num: %d\n", myid, next_row); 
#endif
		      next_row++;
		  }
		  else
		      break;
	      }
	      else
		  break;
	  } 

	  freq_counter=FREQUENCY;
      }

      if (guess_consistent(&col_to_change))
      {
#ifdef DEBUG	 
	  trace_guess("sending:  ", "\n");
#endif
	  CURR_GUESS[columns] = next_row;
	  CURR_GUESS[columns+1] = 
	    (int)(guesses_done/search_space_size*numslaves*100);
#ifdef LOGGING
  MPE_Log_event(1,0,"");
#endif
	  MPI_Send(CURR_GUESS, GUESS_LENGTH, MPI_INT, MASTER_RANK,
		   GUESS, MPI_COMM_WORLD);
#ifdef LOGGING
  MPE_Log_event(2,0,"");
  MPE_Log_event(5,0,"");
#endif
	  MPI_Recv(&board[next_row][0], MAX_MSG_LENGTH, MPI_INT, MASTER_RANK,
		   MPI_ANY_TAG, MPI_COMM_WORLD, &status);
#ifdef LOGGING
  MPE_Log_event(6,0,"");
#endif
	  switch (status.MPI_TAG)
	  {
	    case EXIT: 
	      done = 1;
	      break;
	    case WON:
	      done = 1;
#ifdef USE_GRAPHICS
	      draw_progress(myid-1, ACCEPTED, 0);  
	      MPE_Update(handle);
#endif
	      break;
	    case ACCEPTED:
#ifdef USE_GRAPHICS
	      draw_progress(myid-1, ACCEPTED, 0);  
	      MPE_Update(handle);
#endif
	      for (i=0; i<columns; i++)
		  board[next_row][i+2] = CURR_GUESS[i];
	      next_row++;
	      next_guess(columns-1);
	      (curr_task->guess_number)++;
	      guesses_done++;
	      if ((--curr_task->guesses_remaining)<=0)
		  current_chunk_done(&done);
	      break;
	    case NEW_INFO:
#ifdef USE_GRAPHICS
	      draw_progress(myid-1, REJECTED,
			    board[next_row][columns+2]);
	      MPE_Update(handle);
#endif
#ifdef PRINTING
	      printf("%2d: NEW INFO, row num: %d\n", myid, next_row);
#endif
	      next_row++;
	      
	      break;
	    default:
	      fprintf(stderr,"slave %d received invalid type %d\n", 
		      myid, status.MPI_TAG);
	      done = 1;
	  }
      }
      else
      {
#ifdef DEBUG	  
	  trace_guess("inconsis: ", ", ");
	  printf("col_to_change = %d\n", col_to_change);
#endif
	  skipped = next_guess(col_to_change);
	  if ((curr_task->guesses_remaining-=skipped) > 0)
	  {
	      guesses_done+=skipped;
	      curr_task->guess_number+=skipped;
	  }
	  else
	  {
	      guesses_done+=(curr_task->guesses_remaining+skipped);
	      current_chunk_done(&done);
	  }
      }
      if (!done)
	  curr_task = curr_task->next;
    }
  
#ifdef PRINTING
  trace_guess("LAST:     ", "\n");
#endif
  
  
#ifdef USE_GRAPHICS
  draw_guess(myid-1, 1, CURR_GUESS, myid);
  draw_progress(myid-1, PROGRESS, 0);
  MPE_Update(handle);
#endif

  count = (int)(guesses_done/search_space_size*numslaves*100);

#ifdef LOGGING
  MPE_Log_event(3,0,"");
#endif
  MPI_Send(&count, FINISHED_LENGTH, MPI_INT, MASTER_RANK,
		   FINISHED, MPI_COMM_WORLD);
#ifdef LOGGING
  MPE_Log_event(4,0,"");
#endif
}

current_chunk_done(done)
int *done;
{
  TASKT *tmp;
    if (curr_task->next == curr_task)
    {
	/* run out of work */
	*done = 1;
    }
    else
    {
	curr_task->next->previous = curr_task->previous;
	curr_task->previous->next = curr_task->next;
	tmp = curr_task->previous;
	add_to_free_list(curr_task);
	curr_task = tmp;
    }
}

master()
{
  int row_num, source, worker, bulls, cows, done_pcnt, i, j;
  int numslaves = numprocs-1;
  int slaves_active;
  int game_over = 0;
  double starttime, endtime;
  MPI_Status status;
  GUESST tsk, last_guess, task_size, task_step;
  GUESST task_info[TASK_LENGTH];

#ifdef INTERACTIVE
  while (1)
  {

      while (1)
      {
	  printf("Number of colours: ");
	  fflush(stdout);
	  i = scanf("%d", &colours);
	  while(getchar() != 10);
	  if ( i > 0 && colours > 1 && colours <= MAXCOLOURS )
	      break;
	  printf("This should be a number between 2 and %d\n", MAXCOLOURS);
      }

      while (1)
      {
	  printf("Number of columns: ");
	  fflush(stdout);
	  i = scanf("%d", &columns);
	  while(getchar() != 10);
	  if (i > 0 && columns > 1 && columns <=MAXCOLS )
	      break;
	  else
	      printf("This should be a number between 2 and %d\n", MAXCOLS);
      }