Load balancing grid decomposition for PUGH.

Contributed by Matei Ripeneau


Here are his notes (hopefully there will soon be PUGH docs to add them to):


1. Purpose

Allow manual (user specified) grid partitioning


2. Parameters

I've added the following parameters to ./PUGH/param.ccl

KEYWORD partition "Is the partition manual/automatic"
{
 "automatic"    :: "even implicit partition"
 "manual"       :: "specified by partition_#d_XYZ .."
} "automatic"

STRING partition_1d_X "Tells how to partition on direction X"  ...
STRING partition_2d_X "Tells how to partition on direction X"  ...
STRING partition_2d_Y "Tells how to partition on direction Y"  ...
STRING partition_3d_X "Tells how to partition on direction X"  ...
STRING partition_3d_Y "Tells how to partition on direction Y"  ...
STRING partition_3d_Z "Tells how to partition on direction Z"  ...

(all these strings have default "")


How to specify a manual partition?

Simpler to explain using an example: partitioning a grid space with 30 x 30 x
30 points for a configuration with 8 processors can be specified as:

PUGH::partition = "manual"
PUGH::partition_1d_X = ""           // uses default
PUGH::partition_2d_X = "16:14"
PUGH::partition_2d_Y = "7:9:5:9"
PUGH::partition_3d_X = "16:14"
PUGH::partition_3d_Y = "12:18"
PUGH::partition_3d_Z = "17:13"

Even if PUGH::partition = "manual" an empty string like PUGH::partition_1d_X =
"" will lead to default (even) partition on that direction


git-svn-id: http://svn.cactuscode.org/arrangements/CactusPUGH/PUGH/trunk@174 b61c5cb5-eaca-4651-9a7a-d64986f99364

6 files changed, 401 insertions, 112 deletions

diff --git a/param.ccl b/param.ccl
index d4d9db7..66e7751 100644
--- a/param.ccl
+++ b/param.ccl
@@ -159,3 +159,38 @@ BOOLEAN zero_memory "Zero memory for GF's at allocation time ?"
 } yes
 
 
+KEYWORD partition "Is the partition manual"
+{
+ "automatic"    :: "even"
+ "manual"       :: "specified by partition_XYZ .."
+} "automatic"
+
+STRING partition_1d_X "Tells how to partition on direction X"
+{
+.*
+} ""
+
+STRING partition_2d_X "Tells how to partition on direction X"
+{
+.*
+} ""
+
+STRING partition_2d_Y "Tells how to partition on direction X"
+{
+.*
+} ""
+
+STRING partition_3d_X "Tells how to partition on direction X"
+{
+.*
+} ""
+
+STRING partition_3d_Y "Tells how to partition on direction X"
+{
+.*
+} ""
+
+STRING partition_3d_Z "Tells how to partition on direction X"
+{
+.*
+} ""
diff --git a/src/LoadAware.c b/src/LoadAware.c
new file mode 100644
index 0000000..2ba829e
--- /dev/null
+++ b/src/LoadAware.c
@@ -0,0 +1,181 @@
+#include <stdio.h>
+#include <ctype.h>
+
+#include "pugh.h"
+#include "cctk.h"
+#include "cctk_Parameters.h"
+
+/* #define DEBUG_LA */
+
+ /*@@                                                    
+   @routine    GetSliceSizes
+   @date       Fri Feb 21 10:21:36 2000                 
+   @author     Matei Ripeanu
+   @desc                                                                
+   Computes partition based on parameter information 
+   Return error codes:         
+	    0: OK                             
+	   -1: can not allocate memory       
+	   -2: expect data for np processors but got for more 
+	   -3: expect data for np processors but got for fewer
+	   -4: total doesn't match               
+   @enddesc                                                                
+
+   @var     np 
+   @vdesc   number of processors on this direction
+   @vtype   int
+   @vio     in
+   @vcomment 
+
+   @endvar 
+
+   @var		total
+   @vdesc	number of grid points  
+   @vtype 	int
+   @vio         in 
+   @vcomment
+
+   @endvar
+
+   @var         slicesS
+   @vdesc	line in paraleter file, format "10:10:10" 
+   @vtype       char * 
+   @vio         in 
+   @vcomment
+
+   @endvar
+
+   @var         slices
+   @vdesc       grid points foe each processor, int array
+   @vtype       int ** 
+   @vio         inout 
+   @vcomment
+
+   @endvar
+
+   @var        	manual 
+   @vdesc       manual or automatic partition                                
+   @vtype       int 
+   @vio         in 
+   @vcomment
+
+   @endvar
+
+
+@@*/                                                                   
+   /*
+   Return error codes:
+    0: OK
+   -1: can not allocate memory
+   -2: expect data for np processors but got for more
+   -3: expect data for np processors but got for fewer
+   -4: total doesn't match
+   */
+
+int GetSliceSizes(int np,int grid_points, char *slicesS, int **slices, int manual) {
+
+  int tmp, i=0, rt=0;
+  
+  if (NULL == (*slices = (int*)malloc(np * sizeof(int)))) {
+    CCTK_WARN(1,"Not enough memory");
+    return -1;
+  }
+  
+  if (manual && (strlen(slicesS) > 0)) {
+    
+    while (*slicesS != 0) {
+      if (i >= np) {
+        CCTK_WARN(1,"Wrong partition parameters: expect data for fewer processors");
+        return -2; /* expect data for np processors */
+      }
+      sscanf(slicesS, "%d", &tmp);
+      if (i == 0) (*slices)[i] = 0;
+      else (*slices)[i] = rt - 1;    
+      rt = rt + tmp;
+      i++;
+      while (isdigit(*slicesS)) slicesS++;
+      while (*slicesS != 0 && (!isdigit(*slicesS))) slicesS++;
+    }
+    
+    if (i != np) {
+      CCTK_WARN(1,"Wrong partition parameters: expect data for more processors");
+      return -3; /* expect data for np processors */
+    }
+
+    if (rt != grid_points) {
+      CCTK_WARN(1,"Wrpnf partition parameters: total number of grid points doesnt match");
+      return -4; /* total doesn't mach */
+    }
+
+  } else {
+        
+    for (i=0; i<np; i++) {
+      (*slices)[i] = rt;
+      tmp = (grid_points - rt -1) / (np - i);
+      rt = rt + tmp;
+    }
+	
+  }
+
+#ifdef DEBUB_LA
+  printf("\n");
+  for (i = 0; i<np; i++) printf( "%d :: ", (*slices)[i]);
+  printf("\n");
+#endif
+  
+  return 0;
+}
+
+
+
+int pugh_GetBounds(int dim, int **bounds, int *nprocs, int *nsize) {
+
+  DECLARE_CCTK_PARAMETERS                                                   
+
+  int dir, i;
+
+  switch (dim) {
+  case 1:
+    GetSliceSizes(nprocs[0], nsize[0], partition_1d_X, &(bounds[0]), 
+                  CCTK_Equals(partition, "manual"));
+    break;
+  case 2: 
+    GetSliceSizes(nprocs[0], nsize[0], partition_2d_X, &(bounds[0]), 
+                  CCTK_Equals(partition, "manual"));
+    GetSliceSizes(nprocs[1], nsize[1], partition_2d_Y, &(bounds[1]), 
+                  CCTK_Equals(partition, "manual"));
+    break;
+  case 3: 
+    GetSliceSizes(nprocs[0], nsize[0], partition_3d_X, &(bounds[0]), 
+                  CCTK_Equals(partition, "manual"));
+    GetSliceSizes(nprocs[1], nsize[1], partition_3d_Y, &(bounds[1]), 
+                  CCTK_Equals(partition, "manual"));
+    GetSliceSizes(nprocs[2], nsize[2], partition_3d_Z, &(bounds[2]), 
+                  CCTK_Equals(partition, "manual"));
+    break;
+  default:
+    CCTK_WARN(1,"Only 1D, 2D, and 3D supported");
+    break;
+
+  }
+
+}
+
+
+/*
+int main(void) {
+  int ret, i, *rez;
+  ret = GetSliceSizes (5, 72, "12:12:24:12:12", &rez, 1);
+  
+  if (ret != 0) 
+    printf ("Error: %d\n", ret);
+  else
+    for (i=0; i<5; i++) {   
+      printf("%d\n", rez[i]);
+    }
+}
+*/
+
+
+
+
diff --git a/src/PughUtils.c b/src/PughUtils.c
index 49c9a96..617860a 100644
--- a/src/PughUtils.c
+++ b/src/PughUtils.c
@@ -34,8 +34,11 @@ static char *rcsid = "$Header$";
 
 void pugh_Report(CCTK_CARGUMENTS)
 {
+  DECLARE_CCTK_PARAMETERS                                                   
+
   pGH *pughGH;                  /* PUGH extension handle */
   char *message;
+  int i;
 
   pughGH = pugh_pGH(cctkGH);
 
@@ -58,9 +61,24 @@ void pugh_Report(CCTK_CARGUMENTS)
     sprintf(message,"Processor topology: %d x %d x %d",
             pughGH->nproc[0], pughGH->nproc[1], pughGH->nproc[2]);
     CCTK_INFO(message);
-    sprintf(message,"Local load: %d   [%d x %d x %d]",
-            pughGH->npoints,pughGH->lnsize[0], pughGH->lnsize[1], pughGH->lnsize[2]);
-    
+
+    if (CCTK_Equals(partition, "automatic")) { 
+      sprintf(message,"Local load: %d   [%d x %d x %d]",
+              pughGH->npoints,
+              pughGH->lnsize[0], pughGH->lnsize[1], pughGH->lnsize[2]);
+      CCTK_INFO(message);                                                
+    } else { /* manual partition */
+      for (i=0; i<pughGH->nprocs; i++) { 
+        sprintf(message, 
+                "Local load on proc %d: %d [%d x %d x %d]",       
+                i,                                 
+                pughGH->rnpoints[i],                           
+                pughGH->rnsize[i][0],                          
+                pughGH->rnsize[i][1],                          
+                pughGH->rnsize[i][2]);                         
+        CCTK_INFO(message);                                                
+        }                       
+     }                                                    
 #endif
   }
   else if (cctkGH->cctk_dim == 2)
@@ -74,8 +92,8 @@ void pugh_Report(CCTK_CARGUMENTS)
             pughGH->nproc[0], pughGH->nproc[1]);
     CCTK_INFO(message);
     sprintf(message,"Local load: %d   [%d x %d]",
-            pughGH->npoints,pughGH->lnsize[0], pughGH->lnsize[1]);
-
+	    pughGH->npoints,pughGH->lnsize[0], pughGH->lnsize[1]);
+    CCTK_INFO(message);
 #endif
 
   }
@@ -83,14 +101,14 @@ void pugh_Report(CCTK_CARGUMENTS)
   {
 
   sprintf(message,"Size: %d",pughGH->nsize[0]);
-    CCTK_INFO(message);
+  CCTK_INFO(message);
 
 #ifdef MPI
     sprintf(message,"Processor topology: %d",pughGH->nproc[0]);
     CCTK_INFO(message);
     sprintf(message,"Local load: %d   [%d]",
-            pughGH->npoints,pughGH->lnsize[0]);
-
+	    pughGH->npoints,pughGH->lnsize[0]);
+    CCTK_INFO(message);
 #endif
 
   }
@@ -100,7 +118,6 @@ void pugh_Report(CCTK_CARGUMENTS)
   }
     
 #ifdef MPI
-    CCTK_INFO(message);
     sprintf(message,"Maximum load skew: %f",pughGH->maxskew);
     CCTK_INFO(message);
 #endif
diff --git a/src/SetupPGV.c b/src/SetupPGV.c
index 33114fb..b0642ea 100644
--- a/src/SetupPGV.c
+++ b/src/SetupPGV.c
@@ -8,7 +8,6 @@
    @version $Header$
  @@*/
 
-
 /*#define DEBUG_PUGH*/
 
 #include <stdio.h>
@@ -1100,58 +1099,72 @@ int pugh_SetupBoundingBox(int dim,
                           int *nprocs,
                           pGExtras *this)
 {
-  int pnum,dir;
+  int pnum,dir, i;
 
-  int *step;
+  int **bounds;
   int *pos;
 
-  step = (int *)malloc(dim*sizeof(int));
+  bounds = (int **)malloc(dim*sizeof(int*));
   pos  = (int *)malloc(dim*sizeof(int));
 
-  if(step && pos)
+  if(bounds && pos)
   {
-    /* Work out the step in each direction */
-    for (dir = 0 ; dir < dim; dir++)
+    /* Work out the bounds in each direction - either from parameters 
+       file or default*/
+    pugh_GetBounds(dim, bounds, nprocs, this->nsize);
+
+    /*    for (dir = 0 ; dir < dim; dir++)
     {
       step[dir] = (this->nsize[dir]-1) / nprocs[dir];
     }
+    */
 
     for(pnum = 0; pnum < total_procs; pnum++)
     {
 
-      pugh_DecomposeIJK(dim, pnum,nprocs, pos);
+      pugh_DecomposeIJK(dim, pnum, nprocs, pos);
       
       for(dir = 0 ; dir < dim; dir++)
       {
-        if (pos[dir] == 0)
-        {
-          this->lb[pnum][dir] = 0;
-        }
-        else            
-        {
-          this->lb[pnum][dir] = pos[dir]*step[dir] +1 - nghosts[dir];
-          if(stagger == PUGH_STAGGER)
-          {
-            this->lb[pnum][dir] --;
-          }
-        }
-
-        if (pos[dir] == nprocs[dir]-1) 
-        {
-          this->ub[pnum][dir] = this->nsize[dir]-1;
-        }
-        else
-        {
-          this->ub[pnum][dir] = (pos[dir]+1)*step[dir] + this->nghostzones[dir];
-        }
+	if (pos[dir] == 0)
+	{
+	  this->lb[pnum][dir] = 0;
+	}
+	else		
+	{
+	  this->lb[pnum][dir] = bounds[dir][pos[dir]] +1 - nghosts[dir];
+	  if(stagger == PUGH_STAGGER)
+	  {
+	    this->lb[pnum][dir] --;
+	  }
+	}
+
+	if (pos[dir] == nprocs[dir]-1) 
+	{
+	  this->ub[pnum][dir] = this->nsize[dir]-1;
+	}
+	else
+	{
+	  this->ub[pnum][dir] = bounds[dir][pos[dir]+1] + this->nghostzones[dir];
+	}
       }
     }
 
   }
 
-  free(step);
+  free(bounds);
   free(pos);
 
+#ifdef DEBUG_PUGH
+  for(i=0; i<total_procs; i++) {
+    printf(" setup_Bounding_Box (%d):", i);
+    for (dir = 0 ; dir < dim; dir++)
+      printf(" (%d,%d)",
+             this->lb[i][dir], this->ub[i][dir]);               
+    printf(" \n");
+  }
+#endif
+
   return 0;
 }
 
@@ -1568,3 +1581,6 @@ void pugh_GAComm(pGA *GA, int docomm)
     
 }
 
+
+
+
diff --git a/src/make.code.defn b/src/make.code.defn
index fd3c2c3..30f1c6c 100644
--- a/src/make.code.defn
+++ b/src/make.code.defn
@@ -1,7 +1,7 @@
 # Main make.code.defn file for thorn pugh
 # : /usr/users/cactus/CCTK/lib/make/new_thorn.pl,v 1.1 1999/02/03 17:00:50 goodale Exp n
 # Source files in this directory
-SRCS = pugh_BoundingBox.c pugh_ProcTop.c Startup.c GHExtension.c Comm.c SetupPGH.c SetupGroup.c SetupPGF.c pGF_PostSend.c pGF_PostRecv.c pGF_FinishRecv.c Reduction.c PughUtils.c SetupPGV.c PostSendGA.c PostReceiveGA.c FinishReceiveGA.c
+SRCS = pugh_BoundingBox.c pugh_ProcTop.c Startup.c GHExtension.c Comm.c SetupPGH.c SetupGroup.c SetupPGF.c pGF_PostSend.c pGF_PostRecv.c pGF_FinishRecv.c Reduction.c PughUtils.c SetupPGV.c PostSendGA.c PostReceiveGA.c FinishReceiveGA.c LoadAware.c
 
 # Subdirectories containing source files
 SUBDIRS =
diff --git a/src/pugh_BoundingBox.c b/src/pugh_BoundingBox.c
index 5dc3973..4af0049 100644
--- a/src/pugh_BoundingBox.c
+++ b/src/pugh_BoundingBox.c
@@ -10,6 +10,8 @@
 
 static char *rcsid = "$Header$";
 
+/* #define DEBUG_BB */
+
 #include <stdlib.h>
 
 #include "pugh.h"
@@ -58,89 +60,122 @@ case 0:
 
 void BoundingBox3D(pGH *GH, int *nproc, int staggertype)
 {
-  int i,j,k,idir;
-  int *step;
+  DECLARE_CCTK_PARAMETERS                                                   
 
-  step = (int *)malloc(GH->dim*sizeof(int));
-  for (idir=0;idir<GH->dim;idir++)
-  {
-    step[idir] = (GH->nsize[idir]-1) / nproc[idir];
+  int i,j,k,idir;
+  int *lX, *lY, *lZ;
+
+#ifdef DEBUG_BB                                                                
+  printf("Bounding_Box3D (%d:%d:%d)->%d\n",
+         nproc[0], nproc[1], nproc[2], GH->nprocs); 
+#endif                                                                  
+
+  if (GetSliceSizes(nproc[0], GH->nsize[0], partition_3d_X, &lX, 
+                   CCTK_Equals(partition, "manual"))) {
+#ifdef MPI 
+    MPI_Finalize();       
+#endif
+    exit(0); 
   }
-       
+                                                                           
+  if (GetSliceSizes(nproc[1], GH->nsize[1], partition_3d_Y, &lY,
+                    CCTK_Equals(partition, "manual"))) { 
+#ifdef MPI 
+    MPI_Finalize(); 
+#endif
+    exit(0);  
+  }                                                                           
+ 
+  if (GetSliceSizes(nproc[2], GH->nsize[2], partition_3d_Z, &lZ,
+                    CCTK_Equals(partition, "manual"))) {
+#ifdef MPI 
+    MPI_Finalize(); 
+#endif
+    exit(0);   
+  }                                                                           
+
   for (i=0;i<nproc[0];i++)
   {
     for (j=0;j<nproc[1];j++)
     {
       for (k=0;k<nproc[2];k++) 
       {
-        int pnum = i + nproc[0]*(j+nproc[1]*k);
-        
-        /* Bounding box information */
-        if (i == 0)
-        {
-          GH->lb[pnum][0] = 0;
-        }
-        else            
-        {
-          GH->lb[pnum][0] = i*step[0] +1 - GH->nghostzones[0];
-          if(staggertype == PUGH_STAGGER)
-          GH->lb[pnum][0] --;
-        }
-
-        if (i == nproc[0]-1) 
-        {
-          GH->ub[pnum][0] = GH->nsize[0]-1;
-        }
-        else
-        {
-          GH->ub[pnum][0] = (i+1)*step[0] + GH->nghostzones[0];
-        }
-
-        if (j == 0)
-        { 
-          GH->lb[pnum][1] = 0;
-        }
-        else
-        {            
-            GH->lb[pnum][1] = j*step[1] +1 - GH->nghostzones[1];
-            if(staggertype == PUGH_STAGGER)
-            {
-              GH->lb[pnum][1] --;
-            }
-        }
-        if (j == nproc[1]-1) 
-        {
-          GH->ub[pnum][1] = GH->nsize[1]-1;
-        }
-        else
-        {
-          GH->ub[pnum][1] = (j+1)*step[1] + GH->nghostzones[1];
-        }
-
-        if (k == 0)
-        {
-          GH->lb[pnum][2] = 0;
-        }
-        else             
-        {
-          GH->lb[pnum][2] = k*step[2] +1 - GH->nghostzones[2];
-          if(staggertype == PUGH_STAGGER)
-          {
-            GH->lb[pnum][2] --;
-          }
-        }
-        if (k == nproc[2]-1) 
-        {
-          GH->ub[pnum][2] = GH->nsize[2]-1;
-        }
-        else
-        { 
-          GH->ub[pnum][2] = (k+1)*step[2] + GH->nghostzones[2];
-        }
+	int pnum = i + nproc[0]*(j+nproc[1]*k);
+	
+	/* Bounding box information */
+	if (i == 0)
+	{
+	  GH->lb[pnum][0] = 0;
+	}
+	else            
+	{
+	  GH->lb[pnum][0] = lX[i] +1 - GH->nghostzones[0];
+	  if(staggertype == PUGH_STAGGER)
+	  GH->lb[pnum][0] --;
+	}
+
+	if (i == nproc[0]-1) 
+	{
+	  GH->ub[pnum][0] = GH->nsize[0]-1;
+	}
+	else
+	{
+	  GH->ub[pnum][0] = lX[i+1] + GH->nghostzones[0];
+	}
+
+	if (j == 0)
+	{ 
+	  GH->lb[pnum][1] = 0;
+	}
+	else
+	{            
+	    GH->lb[pnum][1] = lY[j] +1 - GH->nghostzones[1];
+	    if(staggertype == PUGH_STAGGER)
+	    {
+	      GH->lb[pnum][1] --;
+	    }
+	}
+	if (j == nproc[1]-1) 
+	{
+	  GH->ub[pnum][1] = GH->nsize[1]-1;
+	}
+	else
+	{
+	  GH->ub[pnum][1] = lY[j+1] + GH->nghostzones[1];
+	}
+
+	if (k == 0)
+	{
+	  GH->lb[pnum][2] = 0;
+	}
+	else             
+	{
+	  GH->lb[pnum][2] = lZ[k] +1 - GH->nghostzones[2];
+	  if(staggertype == PUGH_STAGGER)
+	  {
+	    GH->lb[pnum][2] --;
+	  }
+	}
+	if (k == nproc[2]-1) 
+	{
+	  GH->ub[pnum][2] = GH->nsize[2]-1;
+	}
+	else
+	{ 
+	  GH->ub[pnum][2] = lZ[k+1] + GH->nghostzones[2];
+	}
       }
     }
   }
-  
+  free(lX); free(lY); free(lZ);
+
+#ifdef DEBUG_BB                        
+  for(i=0; i<GH->nprocs; i++)                                             
+    printf(" Bounding_Box3D(%d) X(%d,%d) Y(%d,%d) Z(%d,%d)\n"
+           ,i, GH->lb[i][0], GH->ub[i][0],
+           GH->lb[i][1], GH->ub[i][1],
+           GH->lb[i][2], GH->ub[i][2]);
+#endif                                     
 }
 
 
@@ -149,6 +184,11 @@ void BoundingBox3D_local(pGH *GH, int *nproc, int staggertype)
   int i,j,k,idir;
   int *step;
 
+#ifdef DEBUG_BB                                                                 
+  printf("Bounding_Box3D_local (%d:%d:%d)->%d\n",
+	 nproc[0], nproc[1], nproc[2], GH->nprocs);                             
+#endif                                                                          
+
   step = (int *)malloc(GH->dim*sizeof(int));
   for (idir=0;idir<GH->dim;idir++)
   {