/* MaGIC.U Version of 11-11-89 This is the parallel version of MaGIC using the GETSUb and BARRIEr macros. It requires such structures as JOB to be defined in MAGIC.h and expects the large body of external variables to be declared in lid.c. */ #define TICK 100 #define DONE gm->prob_done /*** The flag DONE is recognised *** by "transref" as an interrupt *** which needs therefore to be *** in global memory. */ #include "MaGIC.h" JOB *theJob; /* Run specification */ ENV CLoCK(x) int *x; CLOCK(*x) /*** This allows CLOCk to be used by functions elsewhere. ***/ int begin_timer, end_timer; /*** For timing of serial version */ /******************************************************************** ********************************************************************/ struct g_m { short prog_done, prob_done, /* Flags */ nprobs, /* Number of cases */ nprocs, /* Processes */ bad_create, /* CREATe failed */ ready[PROBMAX], /* Case finished */ iso[PROBMAX], /* Isomorphs omitted */ tott[PROBMAX], /* Tests this job */ p_siz[PROBMAX], p_N[PROBMAX], p_index[PROBMAX]; unsigned p_ord[PROBMAX*3], p_true[PROBMAX]; /* Case specifics */ MATRIX limbo[MMAX], /* Unused matrices */ mat_buffer[MBMAX], /* Emergency supply */ *mat_list[PROBMAX]; /* The same as used */ GSDEC(GS) /* GETSUB monitor */ BARDEC(BA) /* BARRIER monitor */ LSDEC(LS) /* LIST monitor */ RSDEC(RS) /* RESULTS monitor */ MQDEC(MQ) /* MATRIX QUEUE */ } *gm; FILE *infil, /* For data input */ *outfil, /* "Real" output */ *fopen(); int offset, /* My current job */ noclear = 0, /* Suppress "clear" */ old_siz, old_negno, old_ord[SZ][SZ], /* Previous setup */ start_time; /* Clock reading */ MATRIX *mymat; /* Latest one found */ #include "lid.c" #include "TR.c" #include "setup.c" /*******************************************************************/ main(argc,argv) int argc; char *argv[]; { int i, j, option, nplocal = 2; extern char *optarg; extern int optind; while ((option = getopt (argc, argv, "x#:")) != -1) switch (option) { case 'x': noclear = 1; break; case '#': if (! isdigit (*optarg)) { fprintf (stderr, "usage: magic [-x], [-# number]\n"); fflush (stderr); exit (1); } sscanf (optarg, "%d", &nplocal); if (nplocal < 2 || nplocal > PARALLEL) { fprintf (stderr, "ERROR: number of processes must be in range 2 - %d\n", PARALLEL); fflush (stderr); exit (1); } break; } INITENV theJob = (JOB*) G_MALLOC(sizeof(JOB)); gm = (struct g_m*) G_MALLOC(sizeof(struct g_m)); GSINIT(gm->GS) BARINIT(gm->BA) LSINIT(gm->LS) RSINIT(gm->RS) MQINIT(gm->MQ) gm->prog_done = 0; gm->nprocs = nplocal; makeprocs(1); /*** *** Note that the slaves hang in a barrier until the master *** releases them for work. They then work repeatedly on *** the problems until gm->prog_done gets to be true. *** *** The slaves generate the matrices, storing what they find *** in global memory. The master looks after IO (which is *** inherently serial). ***/ job_defaults(); while ( nplocal = dialog() ) if ( nplocal > 1 ) new_nprocs(nplocal); else { printf("\n Searching.....\n"); fflush(stdout); job_start(); DONE = 0; while ( !DONE && infil ) { MONITORS_RESET read_data(); siz = old_siz; negno = old_negno; FORALL(i) FORALL(j) ord[i][j] = old_ord[i][j]; BARRIER(gm->BA,gm->nprocs) for ( offset = 0; offset < gm->nprobs && !DONE; offset++ ) transfer(); } job_stop(); /*** *** It is just possible that some slaves are hanging at this point, *** waiting for a matrix from the global pool, so: ***/ MENTER(gm->LS) CONTINUE(gm->LS,0) MEXIT(gm->LS) } /*** *** Now just ensure the slaves die gracefully. ***/ while ( !finished() ) catnap(1); /*** Lazy wait ***/ gm->prog_done = 1; gm->nprobs = 0; BARRIER(gm->BA,gm->nprocs) WAIT_FOR_END system("clear"); } /*****************************************************************/ makeprocs(already) int already; /*** Kreate enough slaves to bring the number up to gm->nprocs. The integer "already" records how many processes there are now ***/ { int i; for ( i = already; i < gm->nprocs; i++ ) { KREATE(slave,gm->bad_create); if ( gm->bad_create ) { if ( i == 1 ) { printf("\n Sorry: we failed to create any workers.\n"); paws(); exit(1); } printf("\n It appears you can't have %d processes.", gm->nprocs); printf("\n Let's settle for %d.\n\n", i); paws(); gm->nprocs = i; } } } new_nprocs(x) int x; /*** Change number of slaves to x ***/ { int i, j; while ( !finished() ) catnap(1); /*** Lazy wait ***/ gm->nprobs = 0; DONE = 1; j = gm->nprocs; gm->nprocs = x; if ( x >= j ) makeprocs(j); else { gm->prog_done = 1; BARRIER(gm->BA,0) WAIT_FOR_END /* * Now the scary bit: re-initialise the table of active processes * just as in the beginning. This is done without a lock!! */ DEAD_SLAVES /* * There. If that didn't work blame the authors of the Argonne * macros, not me! * Re-initialisation is necessary so that repeated changes of * gm->nprocs don't take the number of undead slaves over the * maximum (which is 50 by default). */ gm->prog_done = 0; makeprocs(1); } } /*****************************************************************/ finished() /*** (Boolean): barrier is full ***/ { int i; MENTER(gm->BA) i = gm->BA.count[0]; MEXIT(gm->BA) return( i == gm->nprocs-1 ); } /*****************************************************************/ catnap(x) int x; /*** Sleep for 0.1x sec. ***/ { int cn_start, cn_stop; CLOCK(cn_start); do { CLOCK(cn_stop) if ( theJob->maxtime && cn_stop > theJob->maxtime ) DONE = 1; } while ( cn_stop-cn_start < x*TICK/10 ); } /*****************************************************************/ slave() /*** Tote dat barge, lift dat bale, etc. ***/ { perm_initial(); BARRIER(gm->BA,gm->nprocs) while ( !gm->prog_done ) { subf_set(); while ( work() ) ; BARRIER(gm->BA,gm->nprocs) } } /****************************************************************/ work() /*** What slaves do ***/ { int Good_matrix(), set_poss(), i; GETSUB(gm->GS,offset,gm->nprobs-1,gm->nprocs-1) if ( offset < 0 || DONE ) return(0); initial_setup(); mymat = 0; tot = isoms = 0; LOOK(i) if ( pre_set() ) { setperm(); transref(Vlength,Good_matrix,set_poss); } gm->iso[offset] = isoms; gm->tott[offset] = tot; READY return(1); } /******************************************************************/ initial_setup() /*** Called from work() before TR ***/ { int i,j,k,m; unsigned u; siz = gm->p_siz[offset]; if ( theJob->f_n) { FORALL(i) N[i] = siz-i; for ( i = 0; i < N[i]; i++ ) ; for ( j = 1; j < gm->p_N[offset]; j++ ) { N[i-j] = i-j; N[siz-(i-j)] = siz-(i-j); } } m = gm->p_index[offset]; k = 0; FORALL(i) FORALL(j) { ord[i][j] = ((gm->p_ord[m] & (1 << k)) != 0); if ( ++k == SUI ) { m++; k = 0; } } FORALL(i) true[i] = ((gm->p_true[offset] & (1 << i)) > 0); FORaLL(i) if ( true[i]) des = i; FORALL(i) { maximal[i] = 1; for ( j = i+1; j <=siz; j++ ) maximal[i] *= !ord[i][j]; } if ( theJob->f_lat ) { FORALL(i) { for ( j = i; j <= siz; j++ ) { for ( k = j; !(ord[i][k] && ord[j][k]); k++ ) ; { A[i][j] = A[j][i] = k; } for ( k = i; !(ord[k][i] && ord[k][j]); k-- ) ; { K[i][j] = K[j][i] = k; } } } } Vlength = 0; FORALL(i) FORALL(j) if ( !( F_N && i < N[j] )) { cc[i][j] = Vlength++; if ( F_N ) cc[N[j]][N[i]] = cc[i][j]; } if ( theJob->f_t) { subf[4].val = des; if ( theJob->f_n ) subf[5].val = N[des]; } } /*****************************************************************/ store_mat() /*** Called by slave processes ***/ { int i,j,care; MATRIX *m; TAKE(m,care) FORALL(i) FORALL(j) m->MC[i][j] = C[i][j]; for ( i = 0; i < 4; i++ ) m->badval[i] = badvalue[i]; PUSHMAT(m,care) } /******************************************************************/ sep(x) int x; { if (x) { if ( theJob->tty_out==UGLY ) printf(" -1\n"); if ( theJob->fil_out==UGLY ) fprintf(outfil, " -1\n"); } } /******************************************************************/ new_case() /*** Offset has just been incremented ***/ { int i,j,k,m; unsigned u; if ( gm->p_siz[offset] > siz ) { if ( theJob->f_n ) sep(negno); siz = gm->p_siz[offset]; negno = ordno = desno = 0; *N = **ord = 0; } if ( theJob->f_n) { if ( gm->p_N[offset] != negno ) { sep(ordno); FORALL(i) N[i] = siz-i; for ( i = 0; i < N[i]; i++ ) ; for ( j = 1; j < gm->p_N[offset]; j++ ) { N[i-j] = i-j; N[siz-i+j] = siz-i+j; } ordno = desno = 0; **ord = 0; } } m = gm->p_index[offset]; k = 0; FORALL(i) FORALL(j) { u = gm->p_ord[m] & (1 << k); if ( ++k == SUI ) { m++; k = 0; } if ( !IFF(u, ord[i][j]) ) { ord[i][j] = (u != 0); sep(desno); desno = 0; } } FORALL(i) true[i] = ((gm->p_true[offset] & (1 << i)) > 0); FORaLL(i) if ( true[i]) des = i; matno = 0; } /******************************************************************/ transfer() /*** Move matrices from memory to output ***/ { int i,j; new_case(); POPMAT while ( mymat && !DONE ) { FORALL(i) FORALL(j) C[i][j] = mymat->MC[i][j]; for ( i = 0; i < 4; i++ ) badvalue[i] = mymat->badval[i]; mat_print(); GIVE POPMAT } gm->ready[offset] = 0; isoms += gm->iso[offset]; tot += gm->tott[offset]; if ( matno ) { if ( theJob->tty_out == SUMMARY ) { printf(" %d matri%s", matno, (matno>1? "ces": "x")); fflush(stdout); } if ( theJob->fil_out == SUMMARY ) fprintf(outfil, " %d matri%s", matno, (matno>1? "ces": "x")); sep(matno); } }