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