103 void free_comm_schedule(int **sched, int npes)  in free_comm_schedule()  argument
108 	  for (i = 0; i < npes; ++i)  in free_comm_schedule()
114 void empty_comm_schedule(int **sched, int npes)  in empty_comm_schedule()  argument
117      for (i = 0; i < npes; ++i)  in empty_comm_schedule()
121 extern void fill_comm_schedule(int **sched, int npes);
127 int **make_comm_schedule(int npes)  in make_comm_schedule()  argument
132      sched = (int **) malloc(sizeof(int *) * npes);  in make_comm_schedule()
136      for (i = 0; i < npes; ++i)  in make_comm_schedule()
139      for (i = 0; i < npes; ++i) {  in make_comm_schedule()
140 	  sched[i] = (int *) malloc(sizeof(int) * 10 * (npes + 1));  in make_comm_schedule()
142 	       free_comm_schedule(sched,npes);  in make_comm_schedule()
147      empty_comm_schedule(sched,npes);  in make_comm_schedule()
148      fill_comm_schedule(sched,npes);  in make_comm_schedule()
150      if (!check_comm_schedule(sched,npes)) {  in make_comm_schedule()
151 	  free_comm_schedule(sched,npes);  in make_comm_schedule()
179 void fill_comm_schedule(int **sched, int npes)  in fill_comm_schedule()  argument
183      if (npes % 2 == 0) {  in fill_comm_schedule()
184 	  n = npes;  in fill_comm_schedule()
185 	  for (pe = 0; pe < npes; ++pe)  in fill_comm_schedule()
189 	  n = npes + 1;  in fill_comm_schedule()
192 	  add_pair_to_comm_schedule(sched, pe, npes % 2 == 0 ? npes - 1 : pe);  in fill_comm_schedule()
210 void fill1_comm_sched(int *sched, int which_pe, int npes)  in fill1_comm_sched()  argument
213      if (npes % 2 == 0) {  in fill1_comm_sched()
214 	  n = npes;  in fill1_comm_sched()
218 	  n = npes + 1;  in fill1_comm_sched()
220 	  if (npes % 2 == 0) {  in fill1_comm_sched()
221 	       if (pe == which_pe) sched[s++] = npes - 1;  in fill1_comm_sched()
222 	       else if (npes - 1 == which_pe) sched[s++] = pe;  in fill1_comm_sched()
236      if (s != npes) {  in fill1_comm_sched()
238 		  s, which_pe, npes);  in fill1_comm_sched()
245 static void sort1_comm_sched(int *sched, int npes, int sortpe, int ascending)  in sort1_comm_sched()  argument
248      sortsched = (int *) malloc(npes * sizeof(int) * 2);  in sort1_comm_sched()
249      fill1_comm_sched(sortsched, sortpe, npes);  in sort1_comm_sched()
251           for (i = 0; i < npes; ++i)  in sort1_comm_sched()
252                sortsched[npes + sortsched[i]] = sched[i];  in sort1_comm_sched()
254           for (i = 0; i < npes; ++i)  in sort1_comm_sched()
255                sortsched[2*npes - 1 - sortsched[i]] = sched[i];  in sort1_comm_sched()
256      for (i = 0; i < npes; ++i)  in sort1_comm_sched()
257           sched[i] = sortsched[npes + i];  in sort1_comm_sched()
266 static int check_schedule_deadlock(int **sched, int npes)  in check_schedule_deadlock()  argument
272      step = (int *) malloc(sizeof(int) * npes);  in check_schedule_deadlock()
276      depend = (int *) malloc(sizeof(int) * npes);  in check_schedule_deadlock()
280      visited = (int *) malloc(sizeof(int) * npes);  in check_schedule_deadlock()
287      for (pe = 0; pe < npes; ++pe)  in check_schedule_deadlock()
293 	  for (pe = 0; pe < npes; ++pe)  in check_schedule_deadlock()
297 	  for (pe = 0; pe < npes; ++pe)  in check_schedule_deadlock()
299 		    for (pe2 = 0; pe2 < npes; ++pe2)  in check_schedule_deadlock()
329 	  for (pe = 0; pe < npes; ++pe)  in check_schedule_deadlock()
344 int check_comm_schedule(int **sched, int npes)  in check_comm_schedule()  argument
348      for (pe = 0; pe < npes; ++pe) {  in check_comm_schedule()
349 	  for (comm_pe = 0; comm_pe < npes; ++comm_pe) {  in check_comm_schedule()
360 	  if (i != npes) {  in check_comm_schedule()
366      return check_schedule_deadlock(sched,npes);  in check_comm_schedule()
371 void invert_comm_schedule(int **sched, int npes)  in invert_comm_schedule()  argument
375      for (pe = 0; pe < npes; ++pe)  in invert_comm_schedule()
376 	  for (i = 0; i < npes/2; ++i) {  in invert_comm_schedule()
378 	       sched[pe][i] = sched[pe][npes-1-i];  in invert_comm_schedule()
379 	       sched[pe][npes-1-i] = dummy;  in invert_comm_schedule()
390 void sort_comm_schedule(int **sched, int npes, int sort_pe)  in sort_comm_schedule()  argument
398      for (i = 0; i < npes - 1; ++i)  in sort_comm_schedule()
399 	  for (j = i + 1; j < npes; ++j)  in sort_comm_schedule()
401 		    for (pe = 0; pe < npes; ++pe) {  in sort_comm_schedule()
410 void print_comm_schedule(int **sched, int npes)  in print_comm_schedule()  argument
414      if (npes < 10)  in print_comm_schedule()
416      else if (npes < 100)  in print_comm_schedule()
421      for (pe = 0; pe < npes; ++pe) {  in print_comm_schedule()
432      int npes = -1, sortpe = -1, steps, i;  in main()  local
435 	  npes = atoi(argv[1]);  in main()
436 	  if (npes <= 0) {  in main()
443 	  if (sortpe < 0 || sortpe >= npes) {  in main()
449      if (npes != -1) {  in main()
450 	  printf("Computing schedule for npes = %d:\n",npes);  in main()
451 	  sched = make_comm_schedule(npes);  in main()
457 	  if (steps = check_comm_schedule(sched,npes))  in main()
462 	  print_comm_schedule(sched, npes);  in main()
466 	       int *sched1 = (int*) malloc(sizeof(int) * npes);  in main()
467 	       for (i = 0; i < npes; ++i) sched1[i] = -1;  in main()
468 	       fill1_comm_sched(sched1, sortpe, npes);  in main()
470 	       for (i = 0; i < npes; ++i)   in main()
471 		    printf("  %*d", npes < 10 ? 1 : (npes < 100 ? 2 : 3),  in main()
476 	       sort_comm_schedule(sched,npes,sortpe);  in main()
478 	       if (steps = check_comm_schedule(sched,npes))  in main()
484 	       print_comm_schedule(sched, npes);  in main()
487 	       invert_comm_schedule(sched,npes);  in main()
489 	       if (steps = check_comm_schedule(sched,npes))  in main()
495 	       print_comm_schedule(sched, npes);  in main()
497 	       free_comm_schedule(sched,npes);  in main()
504 	  for (npes = 1; ; ++npes) {  in main()
505 	       int *sched1 = (int*) malloc(sizeof(int) * npes);  in main()
506 	       printf("npes = %d...",npes);  in main()
507 	       sched = make_comm_schedule(npes);  in main()
512 	       for (sortpe = 0; sortpe < npes; ++sortpe) {  in main()
513 		    empty_comm_schedule(sched,npes);  in main()
514 		    fill_comm_schedule(sched,npes);  in main()
515 		    if (!check_comm_schedule(sched,npes)) {  in main()
521 		    for (i = 0; i < npes; ++i) sched1[i] = -1;  in main()
522 		    fill1_comm_sched(sched1, sortpe, npes);  in main()
523 		    for (i = 0; i < npes; ++i)  in main()
529 		    sort_comm_schedule(sched,npes,sortpe);  in main()
530 		    if (!check_comm_schedule(sched,npes)) {  in main()
535 		    invert_comm_schedule(sched,npes);  in main()
536 		    if (!check_comm_schedule(sched,npes)) {  in main()
543 	       free_comm_schedule(sched,npes);  in main()
545 	       if (npes % 50 == 0)  in main()