source: branches/items/GDE/TREEPUZZLE/src/sched.c

Last change on this file was 191, checked in by jobb, 24 years ago

treepuzzle
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.4 KB
Line 
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
33int scinit;
34int ssinit;
35int fscinit;
36int gssinit;
37int tssinit;
38
39int n, chunksize;
40int p;
41
42#ifdef SCHEDTEST
43   schedtype testsched;
44#endif
45
46void 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
57void 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**************************************/
82uli 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**************************************/
123uli 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**************************************/
155int 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**************************************/
191uli 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**************************************/
222uli 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**************************************/
254uli 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
328int 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
Note: See TracBrowser for help on using the repository browser.