Chris@10: /*
Chris@10:  * Copyright (c) 2003, 2007-11 Matteo Frigo
Chris@10:  * Copyright (c) 1999-2003, 2007-8 Massachusetts Institute of Technology
Chris@10:  *
Chris@10:  * This program is free software; you can redistribute it and/or modify
Chris@10:  * it under the terms of the GNU General Public License as published by
Chris@10:  * the Free Software Foundation; either version 2 of the License, or
Chris@10:  * (at your option) any later version.
Chris@10:  *
Chris@10:  * This program is distributed in the hope that it will be useful,
Chris@10:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
Chris@10:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Chris@10:  * GNU General Public License for more details.
Chris@10:  *
Chris@10:  * You should have received a copy of the GNU General Public License
Chris@10:  * along with this program; if not, write to the Free Software
Chris@10:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
Chris@10:  *
Chris@10:  */
Chris@10: 
Chris@10: /**********************************************************************/
Chris@10: /* This is a modified and combined version of the sched.c and
Chris@10:    test_sched.c files shipped with FFTW 2, written to implement and
Chris@10:    test various all-to-all communications scheduling patterns.
Chris@10: 
Chris@10:    It is not used in FFTW 3, but I keep it around in case we ever want
Chris@10:    to play with this again or to change algorithms.  In particular, I
Chris@10:    used it to implement and test the fill1_comm_sched routine in
Chris@10:    transpose-pairwise.c, which allows us to create a schedule for one
Chris@10:    process at a time and is much more compact than the FFTW 2 code.
Chris@10: 
Chris@10:    Note that the scheduling algorithm is somewhat modified from that
Chris@10:    of FFTW 2.  Originally, I thought that one "stall" in the schedule
Chris@10:    was unavoidable for odd numbers of processes, since this is the
Chris@10:    case for the soccer-timetabling problem.  However, because of the
Chris@10:    self-communication step, we can use the self-communication to fill
Chris@10:    in the stalls.  (Thanks to Ralf Wildenhues for pointing this out.)
Chris@10:    This greatly simplifies the process re-sorting algorithm. */
Chris@10: 
Chris@10: /**********************************************************************/
Chris@10: 
Chris@10: #include <stdio.h>
Chris@10: #include <stdlib.h>
Chris@10: 
Chris@10: /* This file contains routines to compute communications schedules for
Chris@10:    all-to-all communications (complete exchanges) that are performed
Chris@10:    in-place.  (That is, the block that processor x sends to processor
Chris@10:    y gets replaced on processor x by a block received from processor y.)
Chris@10: 
Chris@10:    A schedule, int **sched, is a two-dimensional array where
Chris@10:    sched[pe][i] is the processor that pe expects to exchange a message
Chris@10:    with on the i-th step of the exchange.  sched[pe][i] == -1 for the
Chris@10:    i after the last exchange scheduled on pe.
Chris@10: 
Chris@10:    Here, processors (pe's, for processing elements), are numbered from
Chris@10:    0 to npes-1.
Chris@10: 
Chris@10:    There are a couple of constraints that a schedule should satisfy
Chris@10:    (besides the obvious one that every processor has to communicate
Chris@10:    with every other processor exactly once).
Chris@10:    
Chris@10:    * First, and most importantly, there must be no deadlocks.
Chris@10:    
Chris@10:    * Second, we would like to overlap communications as much as possible,
Chris@10:    so that all exchanges occur in parallel.  It turns out that perfect
Chris@10:    overlap is possible for all number of processes (npes).
Chris@10: 
Chris@10:    It turns out that this scheduling problem is actually well-studied,
Chris@10:    and good solutions are known.  The problem is known as a
Chris@10:    "time-tabling" problem, and is specifically the problem of
Chris@10:    scheduling a sports competition (where n teams must compete exactly
Chris@10:    once with every other team).  The problem is discussed and
Chris@10:    algorithms are presented in:
Chris@10: 
Chris@10:    [1] J. A. M. Schreuder, "Constructing Timetables for Sport
Chris@10:    Competitions," Mathematical Programming Study 13, pp. 58-67 (1980).
Chris@10: 
Chris@10:    [2] A. Schaerf, "Scheduling Sport Tournaments using Constraint
Chris@10:    Logic Programming," Proc. of 12th Europ. Conf. on
Chris@10:    Artif. Intell. (ECAI-96), pp. 634-639 (Budapest 1996).
Chris@10:    http://hermes.dis.uniromal.it/~aschaerf/publications.html
Chris@10: 
Chris@10:    (These people actually impose a lot of additional constraints that
Chris@10:    we don't care about, so they are solving harder problems. [1] gives
Chris@10:    a simple enough algorithm for our purposes, though.)
Chris@10:    
Chris@10:    In the timetabling problem, N teams can all play one another in N-1
Chris@10:    steps if N is even, and N steps if N is odd.  Here, however,
Chris@10:    there is a "self-communication" step (a team must also "play itself")
Chris@10:    and so we can always make an optimal N-step schedule regardless of N.
Chris@10: 
Chris@10:    However, we have to do more: for a particular processor, the
Chris@10:    communications schedule must be sorted in ascending or descending
Chris@10:    order of processor index.  (This is necessary so that the data
Chris@10:    coming in for the transpose does not overwrite data that will be
Chris@10:    sent later; for that processor the incoming and outgoing blocks are
Chris@10:    of different non-zero sizes.)  Fortunately, because the schedule
Chris@10:    is stall free, each parallel step of the schedule is independent
Chris@10:    of every other step, and we can reorder the steps arbitrarily
Chris@10:    to achieve any desired order on a particular process.
Chris@10: */
Chris@10: 
Chris@10: void free_comm_schedule(int **sched, int npes)
Chris@10: {
Chris@10:      if (sched) {
Chris@10: 	  int i;
Chris@10: 
Chris@10: 	  for (i = 0; i < npes; ++i)
Chris@10: 	       free(sched[i]);
Chris@10: 	  free(sched);
Chris@10:      }
Chris@10: }
Chris@10: 
Chris@10: void empty_comm_schedule(int **sched, int npes)
Chris@10: {
Chris@10:      int i;
Chris@10:      for (i = 0; i < npes; ++i)
Chris@10: 	  sched[i][0] = -1;
Chris@10: }
Chris@10: 
Chris@10: extern void fill_comm_schedule(int **sched, int npes);
Chris@10: 
Chris@10: /* Create a new communications schedule for a given number of processors.
Chris@10:    The schedule is initialized to a deadlock-free, maximum overlap
Chris@10:    schedule.  Returns NULL on an error (may print a message to
Chris@10:    stderr if there is a program bug detected).  */
Chris@10: int **make_comm_schedule(int npes)
Chris@10: {
Chris@10:      int **sched;
Chris@10:      int i;
Chris@10: 
Chris@10:      sched = (int **) malloc(sizeof(int *) * npes);
Chris@10:      if (!sched)
Chris@10: 	  return NULL;
Chris@10: 
Chris@10:      for (i = 0; i < npes; ++i)
Chris@10: 	  sched[i] = NULL;
Chris@10: 
Chris@10:      for (i = 0; i < npes; ++i) {
Chris@10: 	  sched[i] = (int *) malloc(sizeof(int) * 10 * (npes + 1));
Chris@10: 	  if (!sched[i]) {
Chris@10: 	       free_comm_schedule(sched,npes);
Chris@10: 	       return NULL;
Chris@10: 	  }
Chris@10:      }
Chris@10:      
Chris@10:      empty_comm_schedule(sched,npes);
Chris@10:      fill_comm_schedule(sched,npes);
Chris@10: 
Chris@10:      if (!check_comm_schedule(sched,npes)) {
Chris@10: 	  free_comm_schedule(sched,npes);
Chris@10: 	  return NULL;
Chris@10:      }
Chris@10: 
Chris@10:      return sched;
Chris@10: }
Chris@10: 
Chris@10: static void add_dest_to_comm_schedule(int **sched, int pe, int dest)
Chris@10: {
Chris@10:      int i;
Chris@10:      
Chris@10:      for (i = 0; sched[pe][i] != -1; ++i)
Chris@10: 	  ;
Chris@10: 
Chris@10:      sched[pe][i] = dest;
Chris@10:      sched[pe][i+1] = -1;
Chris@10: }
Chris@10: 
Chris@10: static void add_pair_to_comm_schedule(int **sched, int pe1, int pe2)
Chris@10: {
Chris@10:      add_dest_to_comm_schedule(sched, pe1, pe2);
Chris@10:      if (pe1 != pe2)
Chris@10: 	  add_dest_to_comm_schedule(sched, pe2, pe1);
Chris@10: }
Chris@10: 
Chris@10: /* Simplification of algorithm presented in [1] (we have fewer
Chris@10:    constraints).  Produces a perfect schedule (npes steps).  */
Chris@10: 
Chris@10: void fill_comm_schedule(int **sched, int npes)
Chris@10: {
Chris@10:      int pe, i, n;
Chris@10: 
Chris@10:      if (npes % 2 == 0) {
Chris@10: 	  n = npes;
Chris@10: 	  for (pe = 0; pe < npes; ++pe)
Chris@10: 	       add_pair_to_comm_schedule(sched,pe,pe);
Chris@10:      }
Chris@10:      else
Chris@10: 	  n = npes + 1;
Chris@10: 
Chris@10:      for (pe = 0; pe < n - 1; ++pe) {
Chris@10: 	  add_pair_to_comm_schedule(sched, pe, npes % 2 == 0 ? npes - 1 : pe);
Chris@10: 	  
Chris@10: 	  for (i = 1; i < n/2; ++i) {
Chris@10: 	       int pe_a, pe_b;
Chris@10: 
Chris@10: 	       pe_a = pe - i;
Chris@10: 	       if (pe_a < 0)
Chris@10: 		    pe_a += n - 1;
Chris@10: 
Chris@10: 	       pe_b = (pe + i) % (n - 1);
Chris@10: 
Chris@10: 	       add_pair_to_comm_schedule(sched,pe_a,pe_b);
Chris@10: 	  }
Chris@10:      }
Chris@10: }
Chris@10: 
Chris@10: /* given an array sched[npes], fills it with the communications
Chris@10:    schedule for process pe. */
Chris@10: void fill1_comm_sched(int *sched, int which_pe, int npes)
Chris@10: {
Chris@10:      int pe, i, n, s = 0;
Chris@10:      if (npes % 2 == 0) {
Chris@10: 	  n = npes;
Chris@10: 	  sched[s++] = which_pe;
Chris@10:      }
Chris@10:      else
Chris@10: 	  n = npes + 1;
Chris@10:      for (pe = 0; pe < n - 1; ++pe) {
Chris@10: 	  if (npes % 2 == 0) {
Chris@10: 	       if (pe == which_pe) sched[s++] = npes - 1;
Chris@10: 	       else if (npes - 1 == which_pe) sched[s++] = pe;
Chris@10: 	  }
Chris@10: 	  else if (pe == which_pe) sched[s++] = pe;
Chris@10: 
Chris@10: 	  if (pe != which_pe && which_pe < n - 1) {
Chris@10: 	       i = (pe - which_pe + (n - 1)) % (n - 1);
Chris@10: 	       if (i < n/2)
Chris@10: 		    sched[s++] = (pe + i) % (n - 1);
Chris@10: 	       
Chris@10: 	       i = (which_pe - pe + (n - 1)) % (n - 1);
Chris@10: 	       if (i < n/2)
Chris@10: 		    sched[s++] = (pe - i + (n - 1)) % (n - 1);
Chris@10: 	  }
Chris@10:      }
Chris@10:      if (s != npes) {
Chris@10: 	  fprintf(stderr, "bug in fill1_com_schedule (%d, %d/%d)\n", 
Chris@10: 		  s, which_pe, npes);
Chris@10: 	  exit(EXIT_FAILURE);
Chris@10:      }
Chris@10: }
Chris@10: 
Chris@10: /* sort the communication schedule sched for npes so that the schedule
Chris@10:    on process sortpe is ascending or descending (!ascending). */
Chris@10: static void sort1_comm_sched(int *sched, int npes, int sortpe, int ascending)
Chris@10: {
Chris@10:      int *sortsched, i;
Chris@10:      sortsched = (int *) malloc(npes * sizeof(int) * 2);
Chris@10:      fill1_comm_sched(sortsched, sortpe, npes);
Chris@10:      if (ascending)
Chris@10:           for (i = 0; i < npes; ++i)
Chris@10:                sortsched[npes + sortsched[i]] = sched[i];
Chris@10:      else
Chris@10:           for (i = 0; i < npes; ++i)
Chris@10:                sortsched[2*npes - 1 - sortsched[i]] = sched[i];
Chris@10:      for (i = 0; i < npes; ++i)
Chris@10:           sched[i] = sortsched[npes + i];
Chris@10:      free(sortsched);
Chris@10: }
Chris@10: 
Chris@10: /* Below, we have various checks in case of bugs: */
Chris@10: 
Chris@10: /* check for deadlocks by simulating the schedule and looking for
Chris@10:    cycles in the dependency list; returns 0 if there are deadlocks
Chris@10:    (or other errors) */
Chris@10: static int check_schedule_deadlock(int **sched, int npes)
Chris@10: {
Chris@10:      int *step, *depend, *visited, pe, pe2, period, done = 0;
Chris@10:      int counter = 0;
Chris@10: 
Chris@10:      /* step[pe] is the step in the schedule that a given pe is on */
Chris@10:      step = (int *) malloc(sizeof(int) * npes);
Chris@10: 
Chris@10:      /* depend[pe] is the pe' that pe is currently waiting for a message
Chris@10: 	from (-1 if none) */
Chris@10:      depend = (int *) malloc(sizeof(int) * npes);
Chris@10: 
Chris@10:      /* visited[pe] tells whether we have visited the current pe already
Chris@10: 	when we are looking for cycles. */
Chris@10:      visited = (int *) malloc(sizeof(int) * npes);
Chris@10: 
Chris@10:      if (!step || !depend || !visited) {
Chris@10: 	  free(step); free(depend); free(visited);
Chris@10: 	  return 0;
Chris@10:      }
Chris@10: 
Chris@10:      for (pe = 0; pe < npes; ++pe)
Chris@10: 	  step[pe] = 0;
Chris@10: 
Chris@10:      while (!done) {
Chris@10: 	  ++counter;
Chris@10: 
Chris@10: 	  for (pe = 0; pe < npes; ++pe)
Chris@10: 	       depend[pe] = sched[pe][step[pe]];
Chris@10: 	  
Chris@10: 	  /* now look for cycles in the dependencies with period > 2: */
Chris@10: 	  for (pe = 0; pe < npes; ++pe)
Chris@10: 	       if (depend[pe] != -1) {
Chris@10: 		    for (pe2 = 0; pe2 < npes; ++pe2)
Chris@10: 			 visited[pe2] = 0;
Chris@10: 
Chris@10: 		    period = 0;
Chris@10: 		    pe2 = pe;
Chris@10: 		    do {
Chris@10: 			 visited[pe2] = period + 1;
Chris@10: 			 pe2 = depend[pe2];
Chris@10: 			 period++;
Chris@10: 		    } while (pe2 != -1 && !visited[pe2]);
Chris@10: 
Chris@10: 		    if (pe2 == -1) {
Chris@10: 			 fprintf(stderr,
Chris@10: 				 "BUG: unterminated cycle in schedule!\n");
Chris@10: 			 free(step); free(depend);
Chris@10: 			 free(visited);
Chris@10: 			 return 0;
Chris@10: 		    }
Chris@10: 		    if (period - (visited[pe2] - 1) > 2) {
Chris@10: 			 fprintf(stderr,"BUG: deadlock in schedule!\n");
Chris@10: 			 free(step); free(depend);
Chris@10: 			 free(visited);
Chris@10: 			 return 0;
Chris@10: 		    }
Chris@10: 
Chris@10: 		    if (pe2 == pe)
Chris@10: 			 step[pe]++;
Chris@10: 	       }
Chris@10: 
Chris@10: 	  done = 1;
Chris@10: 	  for (pe = 0; pe < npes; ++pe)
Chris@10: 	       if (sched[pe][step[pe]] != -1) {
Chris@10: 		    done = 0;
Chris@10: 		    break;
Chris@10: 	       }
Chris@10:      }
Chris@10: 
Chris@10:      free(step); free(depend); free(visited);
Chris@10:      return (counter > 0 ? counter : 1);
Chris@10: }
Chris@10: 
Chris@10: /* sanity checks; prints message and returns 0 on failure.
Chris@10:    undocumented feature: the return value on success is actually the
Chris@10:    number of steps required for the schedule to complete, counting
Chris@10:    stalls. */
Chris@10: int check_comm_schedule(int **sched, int npes)
Chris@10: {
Chris@10:      int pe, i, comm_pe;
Chris@10:      
Chris@10:      for (pe = 0; pe < npes; ++pe) {
Chris@10: 	  for (comm_pe = 0; comm_pe < npes; ++comm_pe) {
Chris@10: 	       for (i = 0; sched[pe][i] != -1 && sched[pe][i] != comm_pe; ++i)
Chris@10: 		    ;
Chris@10: 	       if (sched[pe][i] == -1) {
Chris@10: 		    fprintf(stderr,"BUG: schedule never sends message from "
Chris@10: 			    "%d to %d.\n",pe,comm_pe);
Chris@10: 		    return 0;  /* never send message to comm_pe */
Chris@10: 	       }
Chris@10: 	  }
Chris@10: 	  for (i = 0; sched[pe][i] != -1; ++i)
Chris@10: 	       ;
Chris@10: 	  if (i != npes) {
Chris@10: 	       fprintf(stderr,"BUG: schedule sends too many messages from "
Chris@10: 		       "%d\n",pe);
Chris@10: 	       return 0;
Chris@10: 	  }
Chris@10:      }
Chris@10:      return check_schedule_deadlock(sched,npes);
Chris@10: }
Chris@10: 
Chris@10: /* invert the order of all the schedules; this has no effect on
Chris@10:    its required properties. */
Chris@10: void invert_comm_schedule(int **sched, int npes)
Chris@10: {
Chris@10:      int pe, i;
Chris@10: 
Chris@10:      for (pe = 0; pe < npes; ++pe)
Chris@10: 	  for (i = 0; i < npes/2; ++i) {
Chris@10: 	       int dummy = sched[pe][i];
Chris@10: 	       sched[pe][i] = sched[pe][npes-1-i];
Chris@10: 	       sched[pe][npes-1-i] = dummy;
Chris@10: 	  }
Chris@10: }
Chris@10: 
Chris@10: /* Sort the schedule for sort_pe in ascending order of processor
Chris@10:    index.  Unfortunately, for odd npes (when schedule has a stall
Chris@10:    to begin with) this will introduce an extra stall due to
Chris@10:    the motion of the self-communication past a stall.  We could
Chris@10:    fix this if it were really important.  Actually, we don't
Chris@10:    get an extra stall when sort_pe == 0 or npes-1, which is sufficient
Chris@10:    for our purposes. */
Chris@10: void sort_comm_schedule(int **sched, int npes, int sort_pe)
Chris@10: {
Chris@10:      int i,j,pe;
Chris@10: 
Chris@10:      /* Note that we can do this sort in O(npes) swaps because we know
Chris@10: 	that the numbers we are sorting are just 0...npes-1.   But we'll
Chris@10: 	just do a bubble sort for simplicity here. */
Chris@10: 
Chris@10:      for (i = 0; i < npes - 1; ++i)
Chris@10: 	  for (j = i + 1; j < npes; ++j)
Chris@10: 	       if (sched[sort_pe][i] > sched[sort_pe][j]) {
Chris@10: 		    for (pe = 0; pe < npes; ++pe) {
Chris@10: 			 int s = sched[pe][i];
Chris@10: 			 sched[pe][i] = sched[pe][j];
Chris@10: 			 sched[pe][j] = s;
Chris@10: 		    }
Chris@10: 	       }
Chris@10: }
Chris@10: 
Chris@10: /* print the schedule (for debugging purposes) */
Chris@10: void print_comm_schedule(int **sched, int npes)
Chris@10: {
Chris@10:      int pe, i, width;
Chris@10: 
Chris@10:      if (npes < 10)
Chris@10: 	  width = 1;
Chris@10:      else if (npes < 100)
Chris@10: 	  width = 2;
Chris@10:      else
Chris@10: 	  width = 3;
Chris@10: 
Chris@10:      for (pe = 0; pe < npes; ++pe) {
Chris@10: 	  printf("pe %*d schedule:", width, pe);
Chris@10: 	  for (i = 0; sched[pe][i] != -1; ++i)
Chris@10: 	       printf("  %*d",width,sched[pe][i]);
Chris@10: 	  printf("\n");
Chris@10:      }
Chris@10: }
Chris@10: 
Chris@10: int main(int argc, char **argv)
Chris@10: {
Chris@10:      int **sched;
Chris@10:      int npes = -1, sortpe = -1, steps, i;
Chris@10: 
Chris@10:      if (argc >= 2) {
Chris@10: 	  npes = atoi(argv[1]);
Chris@10: 	  if (npes <= 0) {
Chris@10: 	       fprintf(stderr,"npes must be positive!");
Chris@10: 	       return 1;
Chris@10: 	  }
Chris@10:      }
Chris@10:      if (argc >= 3) {
Chris@10: 	  sortpe = atoi(argv[2]);
Chris@10: 	  if (sortpe < 0 || sortpe >= npes) {
Chris@10: 	       fprintf(stderr,"sortpe must be between 0 and npes-1.\n");
Chris@10: 	       return 1;
Chris@10: 	  }
Chris@10:      }
Chris@10: 
Chris@10:      if (npes != -1) {
Chris@10: 	  printf("Computing schedule for npes = %d:\n",npes);
Chris@10: 	  sched = make_comm_schedule(npes);
Chris@10: 	  if (!sched) {
Chris@10: 	       fprintf(stderr,"Out of memory!");
Chris@10: 	       return 6;
Chris@10: 	  }
Chris@10: 	  
Chris@10: 	  if (steps = check_comm_schedule(sched,npes))
Chris@10: 	       printf("schedule OK (takes %d steps to complete).\n", steps);
Chris@10: 	  else
Chris@10: 	       printf("schedule not OK.\n");
Chris@10: 
Chris@10: 	  print_comm_schedule(sched, npes);
Chris@10: 	  
Chris@10: 	  if (sortpe != -1) {
Chris@10: 	       printf("\nRe-creating schedule for pe = %d...\n", sortpe);
Chris@10: 	       int *sched1 = (int*) malloc(sizeof(int) * npes);
Chris@10: 	       for (i = 0; i < npes; ++i) sched1[i] = -1;
Chris@10: 	       fill1_comm_sched(sched1, sortpe, npes);
Chris@10: 	       printf("  =");
Chris@10: 	       for (i = 0; i < npes; ++i) 
Chris@10: 		    printf("  %*d", npes < 10 ? 1 : (npes < 100 ? 2 : 3),
Chris@10: 			   sched1[i]);
Chris@10: 	       printf("\n");
Chris@10: 
Chris@10: 	       printf("\nSorting schedule for sortpe = %d...\n", sortpe);
Chris@10: 	       sort_comm_schedule(sched,npes,sortpe);
Chris@10: 	       
Chris@10: 	       if (steps = check_comm_schedule(sched,npes))
Chris@10: 		    printf("schedule OK (takes %d steps to complete).\n", 
Chris@10: 			   steps);
Chris@10: 	       else
Chris@10: 		    printf("schedule not OK.\n");
Chris@10: 
Chris@10: 	       print_comm_schedule(sched, npes);
Chris@10: 
Chris@10: 	       printf("\nInverting schedule...\n");
Chris@10: 	       invert_comm_schedule(sched,npes);
Chris@10: 	       
Chris@10: 	       if (steps = check_comm_schedule(sched,npes))
Chris@10: 		    printf("schedule OK (takes %d steps to complete).\n", 
Chris@10: 			   steps);
Chris@10: 	       else
Chris@10: 		    printf("schedule not OK.\n");
Chris@10: 
Chris@10: 	       print_comm_schedule(sched, npes);
Chris@10: 	       
Chris@10: 	       free_comm_schedule(sched,npes);
Chris@10: 
Chris@10: 	       free(sched1);
Chris@10: 	  }
Chris@10:      }
Chris@10:      else {
Chris@10: 	  printf("Doing infinite tests...\n");
Chris@10: 	  for (npes = 1; ; ++npes) {
Chris@10: 	       int *sched1 = (int*) malloc(sizeof(int) * npes);
Chris@10: 	       printf("npes = %d...",npes);
Chris@10: 	       sched = make_comm_schedule(npes);
Chris@10: 	       if (!sched) {
Chris@10: 		    fprintf(stderr,"Out of memory!\n");
Chris@10: 		    return 5;
Chris@10: 	       }
Chris@10: 	       for (sortpe = 0; sortpe < npes; ++sortpe) {
Chris@10: 		    empty_comm_schedule(sched,npes);
Chris@10: 		    fill_comm_schedule(sched,npes);
Chris@10: 		    if (!check_comm_schedule(sched,npes)) {
Chris@10: 			 fprintf(stderr,
Chris@10: 				 "\n -- fill error for sortpe = %d!\n",sortpe);
Chris@10: 			 return 2;
Chris@10: 		    }
Chris@10: 
Chris@10: 		    for (i = 0; i < npes; ++i) sched1[i] = -1;
Chris@10: 		    fill1_comm_sched(sched1, sortpe, npes);
Chris@10: 		    for (i = 0; i < npes; ++i)
Chris@10: 			 if (sched1[i] != sched[sortpe][i])
Chris@10: 			      fprintf(stderr,
Chris@10: 				      "\n -- fill1 error for pe = %d!\n",
Chris@10: 				      sortpe);
Chris@10: 
Chris@10: 		    sort_comm_schedule(sched,npes,sortpe);
Chris@10: 		    if (!check_comm_schedule(sched,npes)) {
Chris@10: 			 fprintf(stderr,
Chris@10: 				 "\n -- sort error for sortpe = %d!\n",sortpe);
Chris@10: 			 return 3;
Chris@10: 		    }
Chris@10: 		    invert_comm_schedule(sched,npes);
Chris@10: 		    if (!check_comm_schedule(sched,npes)) {
Chris@10: 			 fprintf(stderr,
Chris@10: 				 "\n -- invert error for sortpe = %d!\n",
Chris@10: 				 sortpe);
Chris@10: 			 return 4;
Chris@10: 		    }
Chris@10: 	       }
Chris@10: 	       free_comm_schedule(sched,npes);
Chris@10: 	       printf("OK\n");
Chris@10: 	       if (npes % 50 == 0)
Chris@10: 		    printf("(...Hit Ctrl-C to stop...)\n");
Chris@10: 	       free(sched1);
Chris@10: 	  }
Chris@10:      }
Chris@10: 
Chris@10:      return 0;
Chris@10: }