forester/archive/RIO/others/puzzle_mod/src/sched.c

   1 /*
   2  * sched.c
   3  *
   4  *
   5  * Part of TREE-PUZZLE 5.0 (June 2000)
   6  *
   7  * (c) 1999-2000 by Heiko A. Schmidt, Korbinian Strimmer,
   8  *                  M. Vingron, and Arndt von Haeseler
   9  * (c) 1995-1999 by Korbinian Strimmer and Arndt von Haeseler
  10  *
  11  * All parts of the source except where indicated are distributed under
  12  * the GNU public licence.  See http://www.opensource.org for details.
  13  */
  14
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <math.h>
  19 #include "sched.h"
  20 /* #include "ppuzzle.h" */
  21
  22 #define STDOUT     stdout
  23 #ifndef PARALLEL             /* because printf() runs significantly faster */
  24                              /* than fprintf(stdout) on an Apple McIntosh  */
  25                              /* (HS) */
  26 #       define FPRINTF    printf
  27 #       define STDOUTFILE
  28 #else
  29 #       define FPRINTF    fprintf
  30 #       define STDOUTFILE STDOUT,
  31 #endif
  32
  33 int scinit;
  34 int ssinit;
  35 int fscinit;
  36 int gssinit;
  37 int tssinit;
  38
  39 int n, chunksize;
  40 int p;
  41
  42 #ifdef SCHEDTEST
  43    schedtype testsched;
  44 #endif
  45
  46 void printsched(schedtype sch)
  47 {
  48    FPRINTF(STDOUTFILE "Current scheduling status:\n");
  49    FPRINTF(STDOUTFILE "  truetasks=%5ld - alltasks=%5ld - numtasks=%5ld - numprocs=%5d\n",
  50           sch.truetasks, sch.alltasks, sch.numtasks, sch.numprocs);
  51    FPRINTF(STDOUTFILE "  delta    =%5d - overhead=%5d - rest    =%5d - inited  =%5d\n",
  52           sch.delta, sch.overhead, sch.rest, sch.inited);
  53    FPRINTF(STDOUTFILE "  nconst   =%5d - fconst  =%5f - lconst  =%5f - kconst  =%5f\n",
  54           sch.nconst, sch.fconst, sch.lconst, sch.kconst);
  55 }
  56
  57 void initsched(schedtype *sch, uli tasks, int procs, uli minchunk)
  58 {
  59    if (minchunk < 1) minchunk = 1;
  60    (*sch).minchunk  = minchunk;
  61    (*sch).truetasks = tasks;
  62    (*sch).rest      = (int)((*sch).truetasks % (*sch).minchunk);
  63    (*sch).alltasks  = (tasks - (*sch).rest);
  64    (*sch).numtasks  = (*sch).alltasks;
  65    (*sch).numprocs  = procs;
  66    (*sch).delta     = 0;
  67    (*sch).overhead  = 0;
  68    (*sch).nconst    = 0;
  69    (*sch).fconst    = 0;
  70    (*sch).lconst    = 0;
  71    (*sch).kconst    = 0;
  72    (*sch).inited    = 0;
  73
  74 #  ifdef PVERBOSE1
  75       printsched(*sch);
  76 #  endif /* PVERBOSE1 */
  77 }
  78
  79 /**************************************
  80 *  Static Chunking
  81 **************************************/
  82 uli sc(schedtype *sch)
  83 {
  84   uli tmp;
  85
  86   if ((*sch).inited == 0) {
  87     (*sch).overhead = (*sch).alltasks % (*sch).numprocs;
  88     (*sch).delta    = ((*sch).alltasks - (*sch).overhead) / (*sch).numprocs;
  89     (*sch).inited ++;
  90   }
  91
  92   if (!(*sch).overhead) {
  93        if ((*sch).numtasks >= (*sch).delta)
  94           tmp = (uli)(*sch).delta;
  95        else
  96           tmp = 0;
  97   } else {
  98        if ((*sch).numtasks >= ((*sch).delta + 1)) {
  99           tmp = (uli)(*sch).delta + 1;
 100           (*sch).overhead--;
 101        } else
 102           tmp = 0;
 103   }
 104
 105   /* correction */
 106   if ((tmp % (*sch).minchunk) > 0) {
 107       tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
 108   }
 109
 110   (*sch).numtasks -= tmp;
 111
 112   if ((*sch).numtasks == 0) {
 113      tmp += (uli)(*sch).rest;
 114      (*sch).rest = 0;
 115   }
 116   return tmp;
 117 }  /* SC */
 118
 119
 120 /**************************************
 121 *  Self Scheduling
 122 **************************************/
 123 uli ss(schedtype *sch)
 124 {
 125   uli tmp;
 126
 127   if ((*sch).inited == 0) {
 128      (*sch).inited ++;
 129   }
 130
 131   if ((*sch).numtasks >= 1)
 132      tmp = 1;
 133   else
 134      tmp = (*sch).numtasks;
 135
 136   /* correction */
 137   if ((tmp % (*sch).minchunk) > 0) {
 138       tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
 139   }
 140
 141   (*sch).numtasks -= tmp;
 142
 143   if ((*sch).numtasks == 0) {
 144      tmp += (uli)(*sch).rest;
 145      (*sch).rest = 0;
 146   }
 147
 148   return tmp;
 149 }  /* SS */
 150
 151
 152 /**************************************
 153 *  fixed-size chunking
 154 **************************************/
 155 int fsc()
 156 {
 157   static int R ;
 158   static int delta ;
 159   static int overhead;
 160
 161          int tmp;
 162
 163   if (fscinit == 0) {
 164     R = n;
 165     overhead = n % p;
 166     delta    = (n - overhead) / p;
 167     fscinit ++;
 168   }
 169
 170   if (!overhead) {
 171        if (R >= delta)
 172           tmp = delta;
 173        else
 174           tmp = 0;
 175   } else {
 176        if (R >= (delta + 1)) {
 177           tmp = delta + 1;
 178           overhead--;
 179        } else
 180           tmp = 0;
 181   }
 182
 183   R -= tmp;
 184   return tmp;
 185 }  /* FSC */
 186
 187
 188 /**************************************
 189 *  Guided Self Scheduling
 190 **************************************/
 191 uli gss(schedtype *sch)
 192 {
 193   uli tmp;
 194
 195   if ((*sch).inited == 0) {
 196     (*sch).inited ++;
 197   }
 198
 199   if ((*sch).numtasks >= 1) {
 200      tmp = (uli)ceil((*sch).numtasks / (*sch).numprocs);
 201      if (tmp == 0) tmp = 1;
 202   } else
 203      tmp = 0;
 204
 205   /* correction */
 206   if ((tmp % (*sch).minchunk) > 0) {
 207       tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
 208   }
 209
 210   (*sch).numtasks -= tmp;
 211
 212   if ((*sch).numtasks == 0) {
 213      tmp += (uli)(*sch).rest;
 214      (*sch).rest = 0;
 215   }
 216   return tmp;
 217 }  /* GSS */
 218
 219 /**************************************
 220 *  Smooth Guided Self Scheduling
 221 **************************************/
 222 uli sgss(schedtype *sch)
 223 {
 224   uli tmp;
 225
 226   if ((*sch).inited == 0) {
 227     (*sch).inited ++;
 228   }
 229
 230   if ((*sch).numtasks >= 1) {
 231      tmp = (uli)ceil(((*sch).numtasks / (*sch).numprocs) / 2);
 232      if (tmp == 0) tmp = 1;
 233   } else
 234      tmp = 0;
 235
 236   /* correction */
 237   if ((tmp % (*sch).minchunk) > 0) {
 238       tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
 239   }
 240
 241   (*sch).numtasks -= tmp;
 242
 243   if ((*sch).numtasks == 0) {
 244      tmp += (uli)(*sch).rest;
 245      (*sch).rest = 0;
 246   }
 247   return tmp;
 248 }  /* SGSS */
 249
 250
 251 /**************************************
 252 *  Trapezoid Self Scheduling
 253 **************************************/
 254 uli tss(schedtype *sch)
 255 {
 256   uli tmp;
 257
 258   if ((*sch).inited == 0) {
 259     (*sch).fconst = ceil((*sch).numtasks / (2*(*sch).numprocs));
 260     if ((*sch).fconst == 0) (*sch).fconst = 1;
 261     (*sch).lconst = 1;
 262     (*sch).nconst = ceil( (2*n) / ((*sch).fconst + (*sch).lconst) );
 263     (*sch).ddelta  = (((*sch).fconst - (*sch).lconst) / ((*sch).nconst - 1));
 264     (*sch).kconst = (*sch).fconst;
 265     FPRINTF(STDOUTFILE "f = n/2p = %.2f ; l = %.2f\n", (*sch).fconst, (*sch).lconst);
 266     FPRINTF(STDOUTFILE "N = 2n/(f+l) = %d ; delta = (f-l)/(N-1) = %.2f\n", (*sch).nconst, (*sch).ddelta);
 267     (*sch).inited ++;
 268   }
 269
 270   if ((*sch).kconst <= (double) (*sch).numtasks) {
 271      tmp = (uli)ceil((*sch).kconst);
 272      (*sch).kconst -= (*sch).ddelta;
 273   } else {
 274      tmp = (uli)(*sch).numtasks;
 275      (*sch).kconst = 0.0;
 276   }
 277
 278   /* correction */
 279   if ((tmp % (*sch).minchunk) > 0) {
 280       tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
 281   }
 282
 283   (*sch).numtasks -= tmp;
 284
 285   if ((*sch).numtasks == 0) {
 286      tmp += (uli)(*sch).rest;
 287      (*sch).rest = 0;
 288   }
 289   return tmp;
 290
 291 } /* TSS */
 292
 293
 294 /******************/
 295
 296
 297 #ifdef SCHEDTEST
 298    uli numquarts(int maxspc)
 299    {
 300       uli tmp;
 301       int a, b, c, d;
 302
 303       if (maxspc < 4)
 304          return (uli)0;
 305       else {
 306          maxspc--;
 307          a = maxspc-3;
 308          b = maxspc-2;
 309          c = maxspc-1;
 310          d = maxspc;
 311
 312          tmp = (uli) 1 + a +
 313                (uli) b * (b-1) / 2 +
 314                (uli) c * (c-1) * (c-2) / 6 +
 315                (uli) d * (d-1) * (d-2) * (d-3) / 24;
 316          return (tmp);
 317       }
 318    }  /* numquarts */
 319 #endif
 320
 321
 322
 323
 324 /**************************************
 325 *  main
 326 **************************************/
 327 #ifdef SCHEDTEST
 328 int main(int argc, char *argv[])
 329 {
 330   int tcount,
 331       count,
 332       lastsize,
 333       size;
 334   if ((argc > 4) || (argc < 3)) {
 335      FPRINTF(STDOUTFILE "\n\n   Usage: %s  <# species> <# processors> [<min chunk size>]\n\n", argv[0]);
 336      exit(1);
 337   }
 338
 339   chunksize = 1;
 340
 341   switch(argc) {
 342     case 4:
 343           chunksize = atoi(argv[3]);
 344     case 3:
 345           n = numquarts(atoi(argv[1]));
 346           p = atoi(argv[2]);
 347   }
 348
 349   FPRINTF(STDOUTFILE "proc=%6d\n", p);
 350   FPRINTF(STDOUTFILE "task=%6d\n", n);
 351
 352   initsched(&testsched, n, p, chunksize);
 353   printsched(testsched);
 354
 355   count=1; tcount = 0;
 356   FPRINTF(STDOUTFILE "\n\n---------------------------\n");
 357   FPRINTF(STDOUTFILE "SC(sched) - Static Chunking\n");
 358   FPRINTF(STDOUTFILE "---------------------------\n\n");
 359   do { size = sc(&testsched);
 360        if (size > 0) {FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, size , (size%chunksize) ? '!' : ' ');
 361                       tcount+=size;}
 362        else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
 363      } while (size > 0);
 364
 365
 366   initsched(&testsched, n, p, chunksize);
 367   printsched(testsched);
 368
 369   count=1; tcount = 0;
 370   FPRINTF(STDOUTFILE "\n\n---------------------------\n");
 371   FPRINTF(STDOUTFILE "SS(sched) - Self Scheduling\n");
 372   FPRINTF(STDOUTFILE "---------------------------\n\n");
 373   do { size = ss(&testsched);
 374        if (size > 0) {if (count==1) FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, size , (size%chunksize) ? '!' : ' ');
 375                       count++;
 376                       tcount+=size;
 377                       lastsize = size;}
 378        else          {FPRINTF(STDOUTFILE "      ...\n");
 379                       FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, lastsize , (lastsize%chunksize) ? '!' : ' ');
 380                       FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));}
 381      } while (size > 0);
 382
 383
 384 /**/
 385   count=1; tcount = 0;
 386   FPRINTF(STDOUTFILE "\n\n---------------------------\n");
 387   FPRINTF(STDOUTFILE "FSC() - Fixed-Size Chunking\n");
 388   FPRINTF(STDOUTFILE "---------------------------\n\n");
 389   do { size = fsc();
 390        if (size > 0) {FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, size , (size%chunksize) ? '!' : ' ');
 391                       tcount+=size;}
 392        else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
 393      } while (size > 0);
 394 /**/
 395
 396   initsched(&testsched, n, p, chunksize);
 397   printsched(testsched);
 398
 399   count=1; tcount = 0;
 400   FPRINTF(STDOUTFILE "\n\n-----------------------------------\n");
 401   FPRINTF(STDOUTFILE "GSS(sched) - Guided Self Scheduling\n");
 402   FPRINTF(STDOUTFILE "-----------------------------------\n\n");
 403   do { size = gss(&testsched);
 404        if (size > 0) {FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, size , (size%chunksize) ? '!' : ' ');
 405                       tcount+=size;}
 406        else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
 407      } while (size > 0);
 408
 409   initsched(&testsched, n, p, chunksize);
 410   printsched(testsched);
 411
 412   count=1; tcount = 0;
 413   FPRINTF(STDOUTFILE "\n\n--------------------------------------\n");
 414   FPRINTF(STDOUTFILE "TSS(sched) - Trapezoid Self Scheduling\n");
 415   FPRINTF(STDOUTFILE "--------------------------------------\n\n");
 416   do { size = tss(&testsched);
 417        if (size > 0) {FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, size , (size%chunksize) ? '!' : ' ');
 418                       tcount+=size;}
 419        else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
 420      } while (size > 0);
 421   return (0);
 422 }
 423 #endif