Changeset 2543 in /cluster/svnroot


Ignore:
Timestamp:
Jul 24, 2010 4:27:00 PM (10 years ago)
Author:
skylar
Message:

merging in life fixes (#427)

Location:
bccd-ng/branches/skylar-devel/trees/home/bccd/Life
Files:
4 edited
4 copied

Legend:

Unmodified
Added
Removed
  • bccd-ng/branches/skylar-devel/trees/home/bccd/Life/Defaults.h

    r2396 r2543  
    1111
    1212#include <stdbool.h>
     13#include <getopt.h>
     14
     15static const char * opts = "c:r:g:i:o:t::xh?";
     16static const struct option long_opts[] = {
     17        { "columns", required_argument, NULL, 'c' },
     18        { "rows", required_argument, NULL, 'r' },
     19        { "gens", required_argument, NULL, 'g' },
     20        { "no-display", no_argument, NULL, 0 },
     21        { "display", no_argument, NULL, 'x' },
     22        { "output", required_argument, NULL, 'o' },
     23        { "input", required_argument, NULL, 'i' },
     24        { "throttle", optional_argument, NULL, 't' },
     25        { "help", no_argument, NULL, 'h' },
     26        { NULL, no_argument, NULL, 0 }
     27};
    1328
    1429// Default parameters for the simulation
    15 const int  DEFAULT_SIZE = 105;
    16 const int  DEFAULT_GENS = 1000;
    17 const bool DEFAULT_DISP = true;
    18 const double  INIT_PROB = 0.25;
     30const int DEFAULT_THROTTLE = 60;
     31const int     DEFAULT_SIZE = 105;
     32const int     DEFAULT_GENS = 1000;
     33const double     INIT_PROB = 0.25;
     34#ifndef NO_X11
     35const bool    DEFAULT_DISP = true;
     36#else
     37const bool    DEFAULT_DISP = false;
     38#endif
    1939
    2040// Size, in pixels, of the X window(s)
     
    4666        int  rank;
    4767        int  size;
     68        int  throttle;
    4869        int  ncols;
    4970        int  nrows;
     
    5273        bool do_display;
    5374        int  generations;
     75        char * infile;
     76        char * outfile;
    5477
    5578        struct display_t disp;
  • bccd-ng/branches/skylar-devel/trees/home/bccd/Life/Life.c

    r1966 r2543  
    1 ////////////////////////////////////////////
    2 // MPI Life 0.9
    3 // Copyright 2002, David Joiner and
    4 //   The Shodor Education Foundation, Inc.
    5 ////////////////////////////////////////////
     1/*******************************************
     2MPI Life 1.0
     3Copyright 2002, David Joiner and
     4  The Shodor Education Foundation, Inc.
     5Updated 2010, Andrew Fitz Gibbon and
     6  The Shodor Education Foundation, Inc.
    67
    7 #include <stdlib.h>
    8 #include <stdio.h>
     8A C implementation of Conway's Game of Life.
     9
     10To run:
     11./Life [Rows] [Columns] [Generations] [Display]
     12
     13See the README included in this directory for
     14more detailed information.
     15*******************************************/
     16
    917#include "Life.h"
    10 #include "mpi.h"
    11 #include <time.h>
    12 
    13 #include <X11/Xlib.h> // Every Xlib program must include this
    14 #include <X11/Xutil.h>
    15 #include <assert.h>   // I include this to test return values the lazy way
    16 #include <unistd.h>   // So we got the profile for 10 seconds
    17 #define NIL (0)       // A name for the void pointer
    18 
    19 typedef unsigned int bool;
    20 #define false 0;
    21 #define true 1;
    22 
    23 #define MPI_TORIGHT 0
    24 #define MPI_TOLEFT 1
    25 
    26 MPI_Status mpi_status;
     18#include "Defaults.h" // For Life's constants
    2719
    2820int main(int argc, char ** argv) {
    29     int size;
    30     int rank;
    31     int ngrid;
    32     int ncols;
    33     int nrows;
    34     int max_count;
    35     int do_display;
    36     int count;
    37     int i,j;
    38     int ** grid;
    39     int ** next_grid;
     21       
     22#ifdef PETAKIT
     23        startTimer();
     24#endif
     25        int count;
     26        struct life_t life;
    4027
    41     // Set up MPI
    42     MPI_Init(&argc,&argv);
    43     MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    44     MPI_Comm_size(MPI_COMM_WORLD,&size);
     28        init(&life, &argc, &argv);
    4529
    46     random_initByTime(rank);
     30        for (count = 0; count < life.generations; count++) {
     31                if (life.do_display)
     32                        do_draw(&life);
    4733
    48     // defaults
    49     ngrid=105;
    50     ncols=ngrid;
    51     nrows=ngrid;
    52     max_count=1000;
    53     do_display=1;
    54    
    55     // command line arguments
    56     if (argc > 1) {
    57         sscanf(argv[1],"%d",&nrows);
    58     }
    59     if (argc > 2) {
    60         sscanf(argv[2],"%d",&ncols);
    61     }
    62     if (argc > 3) {
    63         sscanf(argv[3],"%d",&max_count);
    64     }
    65     if (argc > 4) {
    66         sscanf(argv[4],"%d",&do_display);
    67     }
    68     if (do_display!=0) do_display=1;
     34                copy_bounds(&life);
    6935
     36                eval_rules(&life);
    7037
    71     allocate_grid(ncols, nrows, &grid);
    72     allocate_grid(ncols, nrows, &next_grid);
    73     randomize_grid(ncols, nrows, grid, 0.25);
    74     if (do_display==1)
    75         setupWindow(ncols, nrows);
    76     if (do_display==1)
    77         moveWindow(rank,size,ncols,nrows);
     38                update_grid(&life);
    7839
    79 
    80     bool done=false;
    81     count=0;
    82     while(!done) {
    83         if (count++>max_count) done=true;
    84         // output
    85         if (count%1==0&&do_display==1) doDraw(rank,ncols,nrows,grid);
    86         do_step(rank,size,ncols,nrows,grid,next_grid);
    87         //doDraw(rank,ncols,nrows,next_grid);
    88         //do_step(ncols,nrows,next_grid,grid);
    89         for (i=0;i<ncols+2;i++) {
    90             for (j=0;j<nrows+2;j++) {
    91                 grid[i][j]=next_grid[i][j];
    92             }
    93         }
    94     }
    95    
    96    
    97 
    98     cleanup_grid(ncols, nrows, &grid);
    99     cleanup_grid(ncols, nrows, &next_grid);
    100     if(do_display==1) free_video();
    101     MPI_Finalize();
    102 
    103 
    104 }
    105 
    106 void do_step(int rank, int size, int ncols, int nrows, int ** grid,
    107         int ** next_grid) {
    108     int i,j,k,l,neighbors;
    109    
    110     // side by side grid
    111     // top and bottom we get from current cell.
    112     //left right and corners we get from neighboring grids.
    113     // start off with non blocking sends of each "row"
    114     // left is rank - 1 % size, right is rank + 1 % size.
    115 
    116     // copy sides
    117     int left_rank = (rank-1+size)%size;
    118     int right_rank = (rank+1)%size;
    119    
    120     if (left_rank>=rank) {
    121         MPI_Send(grid[1],nrows+2,MPI_INT,left_rank,MPI_TOLEFT,
    122             MPI_COMM_WORLD);
    123         MPI_Recv(grid[ncols+1],nrows+2,MPI_INT,right_rank,
    124             MPI_TOLEFT,
    125             MPI_COMM_WORLD, &mpi_status);
    126     } else {
    127         MPI_Recv(grid[ncols+1],nrows+2,MPI_INT,right_rank,
    128             MPI_TOLEFT,MPI_COMM_WORLD, &mpi_status);
    129         MPI_Send(grid[1],nrows+2,MPI_INT,left_rank,MPI_TOLEFT,
    130             MPI_COMM_WORLD);
    131     }
    132    
    133     if (right_rank>=rank) {
    134         MPI_Send(grid[ncols],nrows+2,MPI_INT,right_rank,MPI_TORIGHT,
    135             MPI_COMM_WORLD);
    136         MPI_Recv(grid[0],nrows+2,MPI_INT,left_rank,
    137             MPI_TORIGHT,
    138             MPI_COMM_WORLD, &mpi_status);
    139     } else {
    140         MPI_Recv(grid[0],nrows+2,MPI_INT,left_rank,
    141             MPI_TORIGHT,
    142             MPI_COMM_WORLD, &mpi_status);
    143         MPI_Send(grid[ncols],nrows+2,MPI_INT,right_rank,MPI_TORIGHT,
    144             MPI_COMM_WORLD);
    145     }
    146    
    147     // copy corners
    148         grid[0][0]=grid[0][nrows];
    149         grid[0][nrows+1]=grid[0][1];
    150         grid[ncols+1][0]=grid[ncols+1][nrows];
    151         grid[ncols+1][nrows+1]=grid[ncols+1][1];
    152        
    153         //copy top and bottom
    154         for (i=1;i<=ncols;i++) {
    155                 grid[i][0]=grid[i][nrows];
    156                 grid[i][nrows+1]=grid[i][1];
     40                throttle(&life);
    15741        }
    15842
     43        cleanup(&life);
    15944
    160         //update
    161         for (i=1;i<=ncols;i++) {
    162                 for (j=1;j<=nrows;j++) {
    163                         neighbors=0;
    164                         for (k=i-1;k<=i+1; k++) {
    165                                 for (l=j-1;l<=j+1; l++) {
    166                                         if (!(k==i&&l==j)&&grid[k][l]>0) {
    167                                                 neighbors++;
    168                                         }
    169                                 }
    170                                 if (neighbors>3) continue;
    171                         }
    172                         if (neighbors<2||neighbors>3) {
    173                                 next_grid[i][j]=0;
    174                         } else if (grid[i][j]>0||neighbors==3) {
    175                                 next_grid[i][j]=grid[i][j]+1;
    176                         }
    177                 }
    178         }
     45#ifdef PETAKIT
     46        printStats("Life",life.size,"mpi",life.ncols * life.nrows, "1.3",0, 3, "iCOLUMNS", (long long int) life.ncols, "iROWS", (long long int)life.nrows, "iGENERATIONS", (long long int)life.generations);
     47#endif
     48
     49        exit(EXIT_SUCCESS);
    17950}
    180 
    181 typedef int * intarray;
    182 
    183 void allocate_grid(int ncols, int nrows, int *** grid){
    184     int i,j;
    185     (*grid) = (int **) malloc(sizeof(intarray)*(ncols+2));
    186     for (i=0; i<ncols+2;i++) {
    187         (*grid)[i] = (int *) malloc(sizeof(int)*(nrows+2));
    188         for (j=0;j<nrows+2;j++) {
    189             (*grid)[i][j]=0;
    190         }
    191     }
    192 }
    193 void cleanup_grid(int ncols, int nrows, int *** grid){
    194     int i;
    195     for (i=0;i<ncols+2;i++) {
    196         free((*grid)[i]);
    197     }
    198     free(*grid);
    199 }
    200 void randomize_grid(int ncols, int nrows, int ** grid, double prob){
    201     int i,j;
    202     for (i=1;i<=ncols;i++) {
    203         for (j=1;j<=nrows;j++) {
    204             if (rand_double()<prob) {
    205                 grid[i][j]=1;
    206             }
    207         }
    208     }
    209 }
    210 
    211 double rand_double() {
    212     return (double)rand()/(double)RAND_MAX;
    213 }
    214 
    215 
    216 
    217 // X information, at some point this should be cleaned up so
    218 // that it does not use global variables
    219 
    220 // setupWindow modified from the tutorial on
    221 // http://tronche.com/gui/x/xlib-tutorial/
    222 // by Christophe Tronche
    223 
    224 
    225 Display *dpy;
    226 int blackColor;
    227 int whiteColor;
    228 Window w;
    229 GC gc;
    230 Pixmap buffer;
    231 Colormap theColormap;
    232 int numXGrayscale=10;
    233 XColor Xgrayscale[10];
    234 int IMAGE_WIDTH=LIFE_IMAGE_WIDTH;
    235 int IMAGE_HEIGHT=LIFE_IMAGE_HEIGHT;
    236 
    237 void free_video() {
    238      XCloseDisplay(dpy);
    239 }
    240 
    241 void moveWindow(int rank,int size,int ncols, int nrows) {
    242       int posx, posy;
    243       posx = 50+(int)((double)rank/(double)size*(double)LIFE_IMAGE_WIDTH);
    244       posy = 50;
    245       XMoveWindow(dpy, w, posx, posy);
    246 }
    247 
    248 
    249 void setupWindow(int ncols, int nrows) {
    250       int i;
    251       XTextProperty xtp;
    252         Status xst;
    253 
    254         // Generate name object
    255         char *name="Life";
    256         xst = XStringListToTextProperty(&name,1,&xtp);
    257         assert(xst != 0);
    258 
    259       // Open the display
    260 
    261       dpy = XOpenDisplay(NIL);
    262       assert(dpy);
    263 
    264       // Get some colors
    265 
    266       blackColor = BlackPixel(dpy, DefaultScreen(dpy));
    267       whiteColor = WhitePixel(dpy, DefaultScreen(dpy));
    268 
    269       // Create the window
    270       if (nrows>ncols) {
    271          IMAGE_WIDTH = (int)((double)LIFE_IMAGE_WIDTH*(double)ncols/(double)nrows);
    272          IMAGE_HEIGHT = LIFE_IMAGE_HEIGHT;
    273       } else {
    274          IMAGE_HEIGHT = (int)((double)LIFE_IMAGE_HEIGHT*(double)nrows/(double)ncols);
    275          IMAGE_WIDTH = LIFE_IMAGE_WIDTH;
    276       }
    277      
    278 
    279       w = XCreateSimpleWindow(dpy, DefaultRootWindow(dpy), 0, 0,
    280                                      IMAGE_WIDTH, IMAGE_HEIGHT, 0, blackColor,
    281                                      blackColor);
    282         XSetWMProperties(dpy,w,&xtp,NULL,NULL,0,NULL,NULL,NULL);
    283       buffer = XCreatePixmap(dpy,DefaultRootWindow(dpy),
    284           IMAGE_WIDTH,IMAGE_HEIGHT,DefaultDepth(dpy,
    285           DefaultScreen(dpy)));
    286          
    287       theColormap = XCreateColormap(dpy, DefaultRootWindow(dpy),
    288           DefaultVisual(dpy,DefaultScreen(dpy)), AllocNone);
    289          
    290       for (i=0;i<numXGrayscale;i++) {
    291           int color = (int)((double)i*35535.0/(double)numXGrayscale)+30000;
    292           Xgrayscale[i].red=color;
    293           Xgrayscale[i].green=color;
    294           Xgrayscale[i].blue=color;
    295           XAllocColor(dpy,theColormap,&(Xgrayscale[i]));
    296       }
    297 
    298       // We want to get MapNotify events
    299 
    300       XSelectInput(dpy, w, StructureNotifyMask);
    301 
    302       // "Map" the window (that is, make it appear on the screen)
    303 
    304       XMapWindow(dpy, w);
    305 
    306       // Create a "Graphics Context"
    307 
    308       gc = XCreateGC(dpy, w, 0, NIL);
    309 
    310       // Tell the GC we draw using the white color
    311 
    312       XSetForeground(dpy, gc, whiteColor);
    313 
    314       // Wait for the MapNotify event
    315 
    316       for(;;) {
    317             XEvent e;
    318             XNextEvent(dpy, &e);
    319             if (e.type == MapNotify)
    320                   break;
    321       }
    322 
    323 }
    324 
    325 void doDraw(int rank, int ncols, int nrows, int ** grid) {
    326 
    327     int x1,x2,y1,y2;
    328     int i,j;
    329     char string[2];
    330     sprintf(string,"%d",rank);
    331    
    332     XSetForeground(dpy, gc, blackColor);
    333     XFillRectangle(dpy,buffer,gc,0,0,IMAGE_WIDTH,IMAGE_HEIGHT);
    334     int rect_width=(int)((double)IMAGE_WIDTH/(double)(ncols+1));
    335     int rect_height=(int)((double)IMAGE_HEIGHT/(double)(nrows+1));
    336     for (i=1;i<=ncols;i++) {
    337         x1 = (int)((double)(i-1)/(double)(ncols+1)*(double)IMAGE_WIDTH);
    338         for (j=1;j<=nrows;j++) {
    339             y1 = (int)((double)(j-1)/(double)(nrows+1)*
    340                 (double)IMAGE_HEIGHT);
    341             if (grid[i][j]>0) {
    342                 int life =grid[i][j];
    343                 if (life>numXGrayscale-1) life=numXGrayscale-1;
    344                 XSetForeground(dpy, gc, Xgrayscale[life].pixel);
    345             } else {
    346                 XSetForeground(dpy, gc, blackColor);
    347             }
    348             XFillRectangle(dpy,buffer,gc,x1,y1,rect_width,rect_height);
    349          }
    350      }
    351      XSetForeground(dpy,gc,blackColor);
    352      XFillRectangle(dpy,buffer,gc,10,10,15,15);
    353      XSetForeground(dpy,gc,whiteColor);
    354      XDrawRectangle(dpy,buffer,gc,10,10,15,15);
    355      XDrawString(dpy,buffer,gc,12,23,string,2);
    356      
    357      XCopyArea(dpy, buffer, w, gc, 0, 0,
    358          IMAGE_WIDTH, IMAGE_HEIGHT,  0, 0);
    359      XFlush(dpy);
    360          
    361 }
    362 
    363 void random_initByTime(int rank) {
    364     time_t ltime;
    365 
    366     time(&ltime);
    367     srand((unsigned) ltime + 100*rank);
    368 }
  • bccd-ng/branches/skylar-devel/trees/home/bccd/Life/Life.h

    r1879 r2543  
    1 ////////////////////////////////////////////
    2 // MPI Life 0.9
    3 // Copyright 2002, David Joiner and
    4 //   The Shodor Education Foundation, Inc.
    5 ////////////////////////////////////////////
    6 
    7 
    8 #define LIFE_IMAGE_WIDTH 500
    9 #define LIFE_IMAGE_HEIGHT 500
    10 
    11 void allocate_grid(int ncols, int nrows, int *** grid);
    12 void cleanup_grid(int ncols, int nrows, int *** grid);
    13 void free_video();
    14 void randomize_grid(int ncols, int nrows, int ** grid, double prob);
    15 double rand_double();
    16 
    17 void setupWindow(int , int);
    18 void moveWindow(int rank,int size,int ncols, int nrows) ;
    19 void doDraw(int rank, int ncols, int nrows, int ** grid);
    20 void do_step(int rank,int size,int ncols,int nrows,int ** grid,int ** next_grid);
    21 
    22 void random_initByTime(int rank) ;
    23 
    24 
     1/*******************************************
     2MPI Life 1.0
     3Copyright 2002, David Joiner and
     4  The Shodor Education Foundation, Inc.
     5Updated 2010, Andrew Fitz Gibbon and
     6  The Shodor Education Foundation, Inc.
     7*******************************************/
     8
     9#ifndef BCCD_LIFE_H
     10#define BCCD_LIFE_H
     11
     12#ifdef MPI
     13#include <mpi.h>
     14#endif
     15
     16#include "XLife.h"    // For display routines
     17#include "Defaults.h" // For Life's constants
     18#ifdef PETAKIT
     19#include "pkit.h"       // For PetaKit output
     20#endif
     21
     22#include <time.h>     // For seeding random
     23#include <stdlib.h>   // For malloc et al.
     24#include <stdbool.h>  // For true/false
     25#include <getopt.h>   // For argument processing
     26#include <stdio.h>    // For file i/o
     27
     28int        init (struct life_t * life, int * c, char *** v);
     29void       eval_rules (struct life_t * life);
     30void       copy_bounds (struct life_t * life);
     31void       update_grid (struct life_t * life);
     32void          throttle (struct life_t * life);
     33void    allocate_grids (struct life_t * life);
     34void        init_grids (struct life_t * life);
     35void        write_grid (struct life_t * life);
     36void        free_grids (struct life_t * life);
     37double     rand_double ();
     38void    randomize_grid (struct life_t * life, double prob);
     39void       seed_random (int rank);
     40void           cleanup (struct life_t * life);
     41void        parse_args (struct life_t * life, int argc, char ** argv);
     42void             usage ();
     43
     44/*
     45        init_env()
     46                Initialize runtime environment.
     47*/
     48int init (struct life_t * life, int * c, char *** v) {
     49        int argc          = *c;
     50        char ** argv      = *v;
     51        life->rank        = 0;
     52        life->size        = 1;
     53        life->throttle    = -1;
     54        life->ncols       = DEFAULT_SIZE;
     55        life->nrows       = DEFAULT_SIZE;
     56        life->generations = DEFAULT_GENS;
     57        life->do_display  = DEFAULT_DISP;
     58        life->infile      = NULL;
     59        life->outfile     = NULL;
     60
     61        #ifdef MPI
     62        MPI_Init(&argc, &argv);
     63        MPI_Comm_rank(MPI_COMM_WORLD, &life->rank);
     64        MPI_Comm_size(MPI_COMM_WORLD, &life->size);
     65        #endif
     66
     67        #ifdef OMP
     68        omp_set_num_threads(omp_get_num_procs());
     69        #endif
     70
     71        seed_random(life->rank);
     72
     73        parse_args(life, argc, argv);
     74
     75        init_grids(life);
     76
     77        if (life->do_display) {
     78                setupWindow(life);
     79                moveWindow(life);
     80        }
     81}
     82
     83/*
     84        eval_rules()
     85                Evaluate the rules of Life for each cell; count
     86                neighbors and update current state accordingly.
     87*/
     88void eval_rules (struct life_t * life) {
     89        int i,j,k,l,neighbors;
     90
     91        int ncols = life->ncols;
     92        int nrows = life->nrows;
     93
     94        int ** grid      = life->grid;
     95        int ** next_grid = life->next_grid;
     96
     97        #ifdef OMP
     98        #pragma omp parallel for private(neighbors,j,k,l)
     99        #endif
     100        for (i = 1; i <= ncols; i++) {
     101                for (j = 1; j <= nrows; j++) {
     102                        neighbors = 0;
     103
     104                        // count neighbors
     105                        for (k = i-1; k <= i+1; k++) {
     106                                for (l = j-1; l <= j+1; l++) {
     107                                        if (!(k == i && l == j) && grid[k][l] != DEAD)
     108                                                neighbors++;
     109                                }
     110                        }
     111
     112                        // update state
     113                        if (neighbors < LOWER_THRESH || neighbors > UPPER_THRESH)
     114                                next_grid[i][j] = DEAD;
     115                        else if (grid[i][j] != DEAD || neighbors == SPAWN_THRESH)
     116                                next_grid[i][j] = grid[i][j]+1;
     117                }
     118        }
     119}
     120
     121/*
     122        copy_bounds()
     123                Copies sides, top, and bottom to their respective locations.
     124                All boundaries are considered periodic.
     125
     126                In the MPI model, processes are aligned side-by-side.
     127                Left and right sides are sent to neighboring processes.
     128                Top and bottom are copied from the process's own grid.
     129*/
     130void copy_bounds (struct life_t * life) {
     131        int i,j;
     132
     133        int rank  = life->rank;
     134        int size  = life->size;
     135        int ncols = life->ncols;
     136        int nrows = life->nrows;
     137
     138        int ** grid = life->grid;
     139
     140        #ifdef MPI
     141        MPI_Status status;
     142        int left_rank  = (rank-1+size) % size;
     143        int right_rank = (rank+1) % size;
     144
     145        enum TAGS {
     146                TOLEFT,
     147                TORIGHT
     148        };
     149
     150        // Some MPIs deadlock if a single process tries to communicate
     151        // with itself
     152        if (size != 1) {
     153                // copy sides to neighboring processes
     154                MPI_Sendrecv(grid[1], nrows+2, MPI_INT, left_rank, TOLEFT,
     155                        grid[ncols+1], nrows+2, MPI_INT, right_rank, TOLEFT,
     156                        MPI_COMM_WORLD, &status);
     157
     158                MPI_Sendrecv(grid[ncols], nrows+2, MPI_INT, right_rank,
     159                        TORIGHT, grid[0], nrows+2, MPI_INT, left_rank,
     160                        TORIGHT, MPI_COMM_WORLD, &status);
     161        }
     162        #endif
     163
     164        // Copy sides locally to maintain periodic boundaries
     165        // when there's only one process
     166        if (size == 1) {
     167                for (j = 0; j < nrows+2; j++) {
     168                        grid[ncols+1][j] = grid[1][j];
     169                        grid[0][j] = grid[ncols][j];
     170                }
     171        }
     172
     173        // copy corners
     174        grid[0][0]             = grid[0][nrows];
     175        grid[0][nrows+1]       = grid[0][1];
     176        grid[ncols+1][0]       = grid[ncols+1][nrows];
     177        grid[ncols+1][nrows+1] = grid[ncols+1][1];
     178
     179        // copy top and bottom
     180        for (i = 1; i <= ncols; i++) {
     181                grid[i][0]       = grid[i][nrows];
     182                grid[i][nrows+1] = grid[i][1];
     183        }
     184}
     185
     186/*
     187        update_grid()
     188                Copies temporary values from next_grid into grid.
     189*/
     190void update_grid (struct life_t * life) {
     191        int i,j;
     192        int ncols = life->ncols;
     193        int nrows = life->nrows;
     194        int ** grid      = life->grid;
     195        int ** next_grid = life->next_grid;
     196
     197        #ifdef OMP
     198        #pragma omp parallel for private(j)
     199        #endif
     200        for (i = 0; i < ncols+2; i++)
     201                for (j = 0; j < nrows+2; j++)
     202                        grid[i][j] = next_grid[i][j];
     203}
     204
     205/*
     206        throttle()
     207                Slows down the simulation to make X display easier to watch.
     208                Has no effect when run with --no-display.
     209*/
     210void throttle (struct life_t * life) {
     211        unsigned int delay;
     212        int t = life->throttle;
     213
     214        if (life->do_display && t != -1) {
     215                delay = 1000000 * 1/t;
     216                usleep(delay);
     217        }
     218}
     219
     220/*
     221        allocate_grids()
     222                Allocates memory for a 2D array of integers.
     223*/
     224void allocate_grids (struct life_t * life) {
     225        int i,j;
     226        int ncols = life->ncols;
     227        int nrows = life->nrows;
     228
     229        life->grid      = (int **) malloc(sizeof(int *) * (ncols+2));
     230        life->next_grid = (int **) malloc(sizeof(int *) * (ncols+2));
     231
     232        for (i = 0; i < ncols+2; i++) {
     233                life->grid[i]      = (int *) malloc(sizeof(int) * (nrows+2));
     234                life->next_grid[i] = (int *) malloc(sizeof(int) * (nrows+2));
     235        }
     236}
     237
     238/*
     239        init_grids()
     240                Initialize cells based on input file, otherwise all cells
     241                are DEAD.
     242*/
     243void init_grids (struct life_t * life) {
     244        FILE * fd;
     245        int i,j;
     246
     247        if (life->infile != NULL) {
     248                if ((fd = fopen(life->infile, "r")) == NULL) {
     249                        perror("Failed to open file for input");
     250                        exit(EXIT_FAILURE);
     251                }
     252
     253                if (fscanf(fd, "%d %d\n", &life->ncols, &life->nrows) == EOF) {
     254                        printf("File must at least define grid dimensions!\nExiting.\n");
     255                        exit(EXIT_FAILURE);
     256                }
     257        }
     258
     259        allocate_grids(life);
     260
     261        for (i = 0; i < life->ncols+2; i++) {
     262                for (j = 0; j < life->nrows+2; j++) {
     263                        life->grid[i][j]      = DEAD;
     264                        life->next_grid[i][j] = DEAD;
     265                }
     266        }
     267
     268        if (life->infile != NULL) {
     269                while (fscanf(fd, "%d %d\n", &i, &j) != EOF) {
     270                        life->grid[i][j]      = ALIVE;
     271                        life->next_grid[i][j] = ALIVE;
     272                }
     273               
     274                fclose(fd);
     275        } else {
     276                randomize_grid(life, INIT_PROB);
     277        }
     278}
     279
     280/*
     281        write_grid()
     282                Dumps the current state of life.grid to life.outfile.
     283                Only outputs the coordinates of !DEAD cells.
     284*/
     285void write_grid (struct life_t * life) {
     286        FILE * fd;
     287        int i,j;
     288        int ncols   = life->ncols;
     289        int nrows   = life->nrows;
     290        int ** grid = life->grid;
     291
     292        if (life->outfile != NULL) {
     293                if ((fd = fopen(life->outfile, "w")) == NULL) {
     294                        perror("Failed to open file for output");
     295                        exit(EXIT_FAILURE);
     296                }
     297
     298                fprintf(fd, "%d %d\n", ncols, nrows);
     299
     300                for (i = 1; i <= ncols; i++) {
     301                        for (j = 1; j <= nrows; j++) {
     302                                if (grid[i][j] != DEAD)
     303                                        fprintf(fd, "%d %d\n", i, j);
     304                        }
     305                }
     306
     307                fclose(fd);
     308        }
     309}
     310
     311/*
     312        free_grids()
     313                Frees memory used by an array that was allocated
     314                with allocate_grids().
     315*/
     316void free_grids (struct life_t * life) {
     317        int i;
     318        int ncols = life->ncols;
     319
     320        for (i = 0; i < ncols+2; i++) {
     321                free(life->grid[i]);
     322                free(life->next_grid[i]);
     323        }
     324
     325        free(life->grid);
     326        free(life->next_grid);
     327}
     328
     329/*
     330        rand_double()
     331                Generate a random double between 0 and 1.
     332*/
     333double rand_double() {
     334        return (double)random()/(double)RAND_MAX;
     335}
     336
     337/*
     338        randomize_grid()
     339                Initialize a Life grid. Each cell has a [prob] chance
     340                of starting alive.
     341*/
     342void randomize_grid (struct life_t * life, double prob) {
     343        int i,j;
     344        int ncols = life->ncols;
     345        int nrows = life->nrows;
     346
     347        for (i = 1; i <= ncols; i++) {
     348                for (j = 1; j <= nrows; j++) {
     349                        if (rand_double() < prob)
     350                                life->grid[i][j] = ALIVE;
     351                }
     352        }
     353}
     354
     355/*
     356        seed_random()
     357                Seed the random number generator based on the
     358                process's rank and time. Multiplier is arbitrary.
     359*/
     360void seed_random (int rank) {
     361        srandom(time(NULL) + 100*rank);
     362}
     363
     364/*
     365        cleanup()
     366                Prepare process for a clean termination.
     367*/
     368void cleanup (struct life_t * life) {
     369        write_grid(life);
     370        free_grids(life);
     371
     372        if (life->do_display)
     373                free_video(life);
     374
     375        #ifdef MPI
     376        MPI_Finalize();
     377        #endif
     378}
     379
     380/*
     381        usage()
     382                Describes Life's command line option
     383*/
     384void usage () {
     385        printf("\nUsage: Life [options]\n");
     386        printf("  -c|--columns number   Number of columns in grid. Default: %d\n", DEFAULT_SIZE);
     387        printf("  -r|--rows number      Number of rows in grid. Default: %d\n", DEFAULT_SIZE);
     388        printf("  -g|--gens number      Number of generations to run. Default: %d\n", DEFAULT_GENS);
     389        printf("  -i|--input filename   Input file. See README for format. Default: none.\n");
     390        printf("  -o|--output filename  Output file. Default: none.\n");
     391        printf("  -h|--help             This help page.\n");
     392        printf("  -t[N]|--throttle[=N]  Throttle display to N generations/second. Default: %d\n",
     393                DEFAULT_THROTTLE);
     394        printf("  -x|--display          Use a graphical display.\n");
     395        printf("  --no-display          Do not use a graphical display.\n");
     396        printf("     Default: %s\n",
     397                (DEFAULT_DISP ? "do display" : "no display"));
     398        printf("\nSee README for more information.\n\n");
     399
     400        exit(EXIT_FAILURE);
     401}
     402
     403/*
     404        parse_args()
     405                Make command line arguments useful
     406*/
     407void parse_args (struct life_t * life, int argc, char ** argv) {
     408        int opt       = 0;
     409        int opt_index = 0;
     410        int i;
     411
     412        for (;;) {
     413                opt = getopt_long(argc, argv, opts, long_opts, &opt_index);
     414
     415                if (opt == -1) break;
     416
     417                switch (opt) {
     418                        case 0:
     419                                if (strcmp("no-display", long_opts[opt_index].name) == 0)
     420                                        life->do_display = false;
     421                                break;
     422                        case 'c':
     423                                life->ncols = strtol(optarg, (char**) NULL, 10);
     424                                break;
     425                        case 'r':
     426                                life->nrows = strtol(optarg, (char**) NULL, 10);
     427                                break;
     428                        case 'g':
     429                                life->generations = strtol(optarg, (char**) NULL, 10);
     430                                break;
     431                        case 'x':
     432                                life->do_display = true;
     433                                break;
     434                        case 'i':
     435                                life->infile = optarg;
     436                                break;
     437                        case 'o':
     438                                life->outfile = optarg;
     439                                break;
     440                        case 't':
     441                                if (optarg != NULL)
     442                                        life->throttle = strtol(optarg, (char**) NULL, 10);
     443                                else
     444                                        life->throttle = DEFAULT_THROTTLE;
     445                                break;
     446                        case 'h':
     447                        case '?':
     448                                usage();
     449                                break;
     450
     451                        default:
     452                                break;
     453                }
     454        }
     455
     456        // Backwards compatible argument parsing
     457        if (optind == 1) {
     458                if (argc > 1)
     459                        life->nrows       = strtol(argv[1], (char**) NULL, 10);
     460                if (argc > 2)
     461                        life->ncols       = strtol(argv[2], (char**) NULL, 10);
     462                if (argc > 3)
     463                        life->generations = strtol(argv[3], (char**) NULL, 10);
     464                if (argc > 4)
     465                        // 0 interpreted as false, all other values true
     466                        life->do_display  = strtol(argv[4], (char**) NULL, 10);
     467        }
     468}
     469
     470#endif
  • bccd-ng/branches/skylar-devel/trees/home/bccd/Life/Makefile

    r2474 r2543  
    1 
    2 CC        = mpicc
     1###############################################################################
     2# Makefile for the Game of Life as included on the BCCD (http://bccd.net)
     3#
     4# By default, build only the serial version and include X display.
     5#
     6# Add OMP=1 or MPI=1 to build OpenMP or MPI versions respectively.
     7# Add NO_X11=1 to omit X libraries.
     8###############################################################################
    39
    410#
    5 # Modify TOPDIR if you use your own include files and library files
     11# Variables and Flags
    612#
    713
    8 LIBS      = -lX11 -lm -m32
     14CC        = gcc
    915
     16ifdef OMP
     17# If gcc, must have version >= 4.2
     18CC        = gcc
     19CFLAGS   += -fopenmp -DOMP
     20endif
    1021
    11 CFLAGS    =
    12 LDFLAGS   = -L/usr/X11R6/lib $(LIBS)
     22# MPI must be after OMP to ensure mpicc in hybrid OMP/MPI
     23ifdef MPI
     24CC        = mpicc
     25CFLAGS   += -DMPI
     26endif
     27
     28ifndef NO_X11
     29LIBS     += -lX11
     30LDFLAGS  += -L/usr/X11R6/lib
     31else
     32CFLAGS   += -DNO_X11
     33endif
     34
     35LIBS     += -lm
     36CFLAGS   +=
     37LDFLAGS  += $(LIBS)
    1338
    1439PROGRAM   = Life
    15 SRCS      = Life.c
     40SRCS      = Life.c pkit.o
    1641OBJS      = $(SRCS:.c=.o)               # object file
    17 
    18 #
    19 # Rules
    20 #
    21 
    22 .SUFFIXES: .c .o
    23 
    24 .cpp.o:
    25         $(CC) -c $(CFLAGS) $<
    2642
    2743#
  • bccd-ng/branches/skylar-devel/trees/home/bccd/Life/README

    r1879 r2543  
    1 Life
     1DESCRIPTION
    22
    3 This is a parallel version of Life which breaks up the domain
    4 of the program into side by side grids.
     3  This application is an implementation of Conway's Game of Life,
     4  written in C. The Game of Life is an iterative process set up on a
     5  2-dimensional grid. Cells on the grid are either "alive" or "dead"
     6  and follow the following rules:
    57
    6 Usage:
     8    - If a cell is empty ("dead") and has exactly 3 neighbors, it has
     9      enough resources to be born without being overcrowded, and the
     10      next turn will be "alive"
    711
    8 mpirun Life 100 100 1000 1
    9 (nrows) (ncols) (iterations) (do_display)
     12    - If a cell is alive and has 2 or 3 neighbors, it has resources
     13      without being overcrowded and will stay "alive".
     14
     15    - If a cell has less than 2 neighbors, it cannot get enough
     16      resources to survive and the next turn will be "dead".
     17
     18    - If a cell has more than 3 neighbors, it will be overcrowded and
     19      the next turn will be dead.
     20
     21  There are four different ways to compile and run this Game of Life
     22  code:
     23
     24  (1) Traditional single-process implementation; no communication or
     25      synchronization is done.
     26
     27  (2) Shared memory implementation using OpenMP. OpenMP is used to
     28      create a number of threads equal to the number of cores on the
     29      node and parallelize a handful of for loops.
     30
     31  (3) Distributed implementation using MPI. Each MPI process has its
     32      own grid, sharing left and right boundaries with neighboring
     33      processes.
     34
     35  (4) Hybrid implementation, combining OpenMP and MPI.
     36
     37COMPILING
     38
     39  A Makefile is included with this project to ease the compiling
     40  process. In all cases, a binary named "Life" will be created.
     41
     42  By default, running "make" with no options will compile the serial
     43  implementation with full graphical support via X11 libraries.
     44
     45  Any of the following options can be added to make to achieve different
     46  behavior. All combinations are valid.
     47
     48    "OMP=1"     Compile with OpenMP pragmas
     49    "MPI=1"     Compile with MPI calls
     50    "NO_X11=1"  Compile without X11 libraries
     51
     52OPTIONS
     53
     54  This version of Life takes the following arguments:
     55
     56    -c|--columns number   Number of columns in grid.
     57    -r|--rows number      Number of rows in grid.
     58    -g|--gens number      Number of generations to run.
     59    -i|--input filename   Input file. See README for format.
     60    -o|--output filename  Output file.
     61    -h|--help             This help page.
     62    -t[N]|--throttle[=N]  Throttle graphical display. (N generations per second)
     63    -x|--display          Use a graphical display.
     64    --no-display          Do not use a graphical display.
     65
     66  If none of these are given, the following defaults are used:
     67    Rows:        105
     68    Columns:     105
     69    Generations: 1000
     70    Input file:  None
     71    Output file: None
     72    Throttle:    No
     73    Display:     Yes
     74
     75  Note: --throttle has no effect if --no-display is given or NO_X11
     76  is specified at compile time. If --throttle or -t are given without
     77        a value, a default value of 60 generations/second will be used.
     78
     79  The input file should contain space-separated values, two per line. The
     80  first line specifies the dimensions, columns and rows respectfully. Each
     81  subsequent line gives the column,row for a living cell. Order has no effect.
     82  Any coordinate not given is assumed to contain a dead cell.
     83
     84  For example, a 5x5 grid with three living cells:
     85    5 5
     86    1 2
     87    2 2
     88    3 5
     89
     90RUNNING
     91
     92  Each implementation is run a little differently:
     93
     94    Serial and OpenMP:
     95      $ ./Life
     96
     97    MPI: (where <N> is the desired number of processes)
     98      $ mpirun -np <N> ./Life
     99
     100    Hybrid MPI/OpenMP:
     101      In order to properly gain benefits from the hybrid implementation,
     102      you must ensure that MPI only creates one process per node. The
     103      methods for doing this differ with each type of MPI. Check which
     104      you're using with `module list`.
     105
     106      If OpenMPI:
     107        $ mpirun -np <N> -bynode ./Life
     108      If MPICH2:
     109        Edit your machines file so that each node's name has ":1". Then
     110        run as if compiled with just MPI.
     111
Note: See TracChangeset for help on using the changeset viewer.