5 * Part of TREE-PUZZLE 5.0 (June 2000)
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
11 * All parts of the source except where indicated are distributed under
12 * the GNU public licence. See http://www.opensource.org for details.
20 /* #include "ppuzzle.h" */
23 #ifndef PARALLEL /* because printf() runs significantly faster */
24 /* than fprintf(stdout) on an Apple McIntosh */
26 # define FPRINTF printf
29 # define FPRINTF fprintf
30 # define STDOUTFILE STDOUT,
46 void printsched(schedtype sch)
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);
57 void initsched(schedtype *sch, uli tasks, int procs, uli minchunk)
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;
76 # endif /* PVERBOSE1 */
79 /**************************************
81 **************************************/
82 uli sc(schedtype *sch)
86 if ((*sch).inited == 0) {
87 (*sch).overhead = (*sch).alltasks % (*sch).numprocs;
88 (*sch).delta = ((*sch).alltasks - (*sch).overhead) / (*sch).numprocs;
92 if (!(*sch).overhead) {
93 if ((*sch).numtasks >= (*sch).delta)
94 tmp = (uli)(*sch).delta;
98 if ((*sch).numtasks >= ((*sch).delta + 1)) {
99 tmp = (uli)(*sch).delta + 1;
106 if ((tmp % (*sch).minchunk) > 0) {
107 tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
110 (*sch).numtasks -= tmp;
112 if ((*sch).numtasks == 0) {
113 tmp += (uli)(*sch).rest;
120 /**************************************
122 **************************************/
123 uli ss(schedtype *sch)
127 if ((*sch).inited == 0) {
131 if ((*sch).numtasks >= 1)
134 tmp = (*sch).numtasks;
137 if ((tmp % (*sch).minchunk) > 0) {
138 tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
141 (*sch).numtasks -= tmp;
143 if ((*sch).numtasks == 0) {
144 tmp += (uli)(*sch).rest;
152 /**************************************
153 * fixed-size chunking
154 **************************************/
166 delta = (n - overhead) / p;
176 if (R >= (delta + 1)) {
188 /**************************************
189 * Guided Self Scheduling
190 **************************************/
191 uli gss(schedtype *sch)
195 if ((*sch).inited == 0) {
199 if ((*sch).numtasks >= 1) {
200 tmp = (uli)ceil((*sch).numtasks / (*sch).numprocs);
201 if (tmp == 0) tmp = 1;
206 if ((tmp % (*sch).minchunk) > 0) {
207 tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
210 (*sch).numtasks -= tmp;
212 if ((*sch).numtasks == 0) {
213 tmp += (uli)(*sch).rest;
219 /**************************************
220 * Smooth Guided Self Scheduling
221 **************************************/
222 uli sgss(schedtype *sch)
226 if ((*sch).inited == 0) {
230 if ((*sch).numtasks >= 1) {
231 tmp = (uli)ceil(((*sch).numtasks / (*sch).numprocs) / 2);
232 if (tmp == 0) tmp = 1;
237 if ((tmp % (*sch).minchunk) > 0) {
238 tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
241 (*sch).numtasks -= tmp;
243 if ((*sch).numtasks == 0) {
244 tmp += (uli)(*sch).rest;
251 /**************************************
252 * Trapezoid Self Scheduling
253 **************************************/
254 uli tss(schedtype *sch)
258 if ((*sch).inited == 0) {
259 (*sch).fconst = ceil((*sch).numtasks / (2*(*sch).numprocs));
260 if ((*sch).fconst == 0) (*sch).fconst = 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);
270 if ((*sch).kconst <= (double) (*sch).numtasks) {
271 tmp = (uli)ceil((*sch).kconst);
272 (*sch).kconst -= (*sch).ddelta;
274 tmp = (uli)(*sch).numtasks;
279 if ((tmp % (*sch).minchunk) > 0) {
280 tmp += (*sch).minchunk - (tmp % (*sch).minchunk);
283 (*sch).numtasks -= tmp;
285 if ((*sch).numtasks == 0) {
286 tmp += (uli)(*sch).rest;
298 uli numquarts(int maxspc)
313 (uli) b * (b-1) / 2 +
314 (uli) c * (c-1) * (c-2) / 6 +
315 (uli) d * (d-1) * (d-2) * (d-3) / 24;
324 /**************************************
326 **************************************/
328 int main(int argc, char *argv[])
334 if ((argc > 4) || (argc < 3)) {
335 FPRINTF(STDOUTFILE "\n\n Usage: %s <# species> <# processors> [<min chunk size>]\n\n", argv[0]);
343 chunksize = atoi(argv[3]);
345 n = numquarts(atoi(argv[1]));
349 FPRINTF(STDOUTFILE "proc=%6d\n", p);
350 FPRINTF(STDOUTFILE "task=%6d\n", n);
352 initsched(&testsched, n, p, chunksize);
353 printsched(testsched);
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) ? '!' : ' ');
362 else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
366 initsched(&testsched, n, p, chunksize);
367 printsched(testsched);
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) ? '!' : ' ');
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));}
386 FPRINTF(STDOUTFILE "\n\n---------------------------\n");
387 FPRINTF(STDOUTFILE "FSC() - Fixed-Size Chunking\n");
388 FPRINTF(STDOUTFILE "---------------------------\n\n");
390 if (size > 0) {FPRINTF(STDOUTFILE "%6d. chunk = %6d %c\n", count++, size , (size%chunksize) ? '!' : ' ');
392 else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
396 initsched(&testsched, n, p, chunksize);
397 printsched(testsched);
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) ? '!' : ' ');
406 else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));
409 initsched(&testsched, n, p, chunksize);
410 printsched(testsched);
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) ? '!' : ' ');
419 else FPRINTF(STDOUTFILE "%d tasks in %d chunks\n", tcount, (count-1));