Commits

Rio Yokota committed 894c80c

Detaching sort from partition.

Comments (0)

Files changed (5)

examples/parallel.cxx

     Bounds localBounds = boundbox.getBounds(bodies);
     Bounds globalBounds = LET.allreduceBounds(localBounds);
     localBounds = LET.partition(bodies,globalBounds);
+    LET.sendBodies = sort.sortBodies(bodies);
+    bodies = LET.commBodies();
     Box box = boundbox.bounds2box(localBounds);
     tree.buildTree(bodies, cells, box);
     pass.upwardPass(cells);
 #endif
     pass.downwardPass(cells);
 
+#if 0
+    LET.unpartition(bodies);
+    LET.sendBodies = sort.sortBodies(bodies);
+    bodies = LET.commBodies();
+    for (B_iter B=bodies.begin(); B!=bodies.end(); B++) {       // Loop over bodies
+      B->ICELL = B->IBODY;                                      //  Do this to sort accroding to IPROC
+    }                                                           // End loop over bodies
+    Bodies buffer = bodies;                                     // Resize sort buffer
+    bodies = sort.sortBodies(buffer);                                // Sort bodies in ascending order
+#endif
     logger.stopPAPI();
     if (logger.printNow) std::cout << "--- Total runtime ----------------" << std::endl;
     logger.stopTimer("Total FMM",logger.printNow);

include/localessentialtree.h

   }
 
 //! Send bodies
-  void commBodies() {
+  Bodies commBodies() {
     startTimer("Comm bodies");                                  // Start timer
     alltoall(sendBodies);                                       // Send body count
     alltoallv(sendBodies);                                      // Send bodies
     stopTimer("Comm bodies",printNow);                          // Stop timer
+    return recvBodies;                                          // Return received bodies
   }
 
 //! Send cells

include/partition.h

 #define partition_h
 #include "mympi.h"
 #include "logger.h"
-#include "sort.h"
 
 //! Handles all the partitioning of domains
-class Partition : public MyMPI, public Logger, public Sort {
+class Partition : public MyMPI, public Logger {
  protected:
-  Bodies sendBodies;                                            //!< Send buffer for bodies
   Bodies recvBodies;                                            //!< Receive buffer for bodies
   int * sendBodyCount;                                          //!< Send count
   int * sendBodyDispl;                                          //!< Send displacement
   int * recvBodyCount;                                          //!< Receive count
   int * recvBodyDispl;                                          //!< Receive displacement
 
- private:
-//! Set partition of global domain
-  Bounds setPartition(Bodies &bodies, Bounds global) {
-    startTimer("Partition");                                    // Start timer
-    int mpisize = MPISIZE;                                      // Initialize MPI size counter
-    vec<3,int> Npartition = 1;                                  // Number of partitions in each direction
-    int d = 0;                                                  // Initialize dimension counter
-    while (mpisize != 1) {                                      // Divide domain while counter is not one
-      Npartition[d] <<= 1;                                      //  Divide this dimension
-      d = (d+1) % 3;                                            //  Increment dimension
-      mpisize >>= 1;                                            //  Right shift the bits of counter
-    }                                                           // End while loop for domain subdivision
-    vec3 Xpartition;                                            // Size of partitions in each direction
-    for (d=0; d<3; d++) {                                       // Loop over dimensions
-      Xpartition[d] = (global.Xmax[d] - global.Xmin[d]) / Npartition[d];//  Size of partition in each direction
-    }                                                           // End loop over dimensions
-    int ix[3];                                                  // Index vector
-    ix[0] = MPIRANK % Npartition[0];                            // x index of partition
-    ix[1] = MPIRANK / Npartition[0] % Npartition[1];            // y index
-    ix[2] = MPIRANK / Npartition[0] / Npartition[1];            // z index
-    Bounds local;                                               // Local bounds
-    for (d=0; d<3; d++) {                                       // Loop over dimensions
-      local.Xmin[d] = global.Xmin[d] + ix[d] * Xpartition[d];   // Xmin of local domain at current rank
-      local.Xmax[d] = global.Xmin[d] + (ix[d] + 1) * Xpartition[d];// Xmax of local domain at current rank
-    }                                                           // End loop over dimensions
-    for (B_iter B=bodies.begin(); B!=bodies.end(); B++) {       // Loop over bodies
-      for (d=0; d<3; d++) {                                     //  Loop over dimensions
-        ix[d] = int((B->X[d] - global.Xmin[d]) / Xpartition[d]);//   Index vector of partition
-      }                                                         //  End loop over dimensions
-      B->IPROC = ix[0] + Npartition[0] * (ix[1] + ix[2] * Npartition[1]);//  Set send rank
-      B->ICELL = B->IPROC;                                      //  Do this to sort accroding to IPROC
-    }                                                           // End loop over bodies
-    Bodies buffer = bodies;                                     // Sort buffer
-    stopTimer("Partition",printNow);                            // Stop timer
-    sortBodies(bodies,buffer);                                  // Sort bodies in ascending order of ICELL
-    return local;
-  }
+ public:
+  Bodies sendBodies;                                            //!< Send buffer for bodies
 
  protected:
 //! Exchange send count for bodies
 
 //! Partition bodies
   Bounds partition(Bodies &bodies, Bounds global) {
-    Bounds local = setPartition(bodies, global);                // Set partitioning strategy
-    startTimer("Partition comm");                               // Start timer
-    alltoall(bodies);                                           // Alltoall send count
-    alltoallv(bodies);                                          // Alltoallv bodies
-    bodies = recvBodies;                                        // Copy receive buffer to bodies
-    stopTimer("Partition comm",printNow);                       // Stop timer
+    startTimer("Partition");                                    // Start timer
+    int mpisize = MPISIZE;                                      // Initialize MPI size counter
+    vec<3,int> Npartition = 1;                                  // Number of partitions in each direction
+    int d = 0;                                                  // Initialize dimension counter
+    while (mpisize != 1) {                                      // Divide domain while counter is not one
+      Npartition[d] <<= 1;                                      //  Divide this dimension
+      d = (d+1) % 3;                                            //  Increment dimension
+      mpisize >>= 1;                                            //  Right shift the bits of counter
+    }                                                           // End while loop for domain subdivision
+    vec3 Xpartition;                                            // Size of partitions in each direction
+    for (d=0; d<3; d++) {                                       // Loop over dimensions
+      Xpartition[d] = (global.Xmax[d] - global.Xmin[d]) / Npartition[d];//  Size of partition in each direction
+    }                                                           // End loop over dimensions
+    int ix[3];                                                  // Index vector
+    ix[0] = MPIRANK % Npartition[0];                            // x index of partition
+    ix[1] = MPIRANK / Npartition[0] % Npartition[1];            // y index
+    ix[2] = MPIRANK / Npartition[0] / Npartition[1];            // z index
+    Bounds local;                                               // Local bounds
+    for (d=0; d<3; d++) {                                       // Loop over dimensions
+      local.Xmin[d] = global.Xmin[d] + ix[d] * Xpartition[d];   // Xmin of local domain at current rank
+      local.Xmax[d] = global.Xmin[d] + (ix[d] + 1) * Xpartition[d];// Xmax of local domain at current rank
+    }                                                           // End loop over dimensions
+    for (B_iter B=bodies.begin(); B!=bodies.end(); B++) {       // Loop over bodies
+      for (d=0; d<3; d++) {                                     //  Loop over dimensions
+        ix[d] = int((B->X[d] - global.Xmin[d]) / Xpartition[d]);//   Index vector of partition
+      }                                                         //  End loop over dimensions
+      B->IPROC = ix[0] + Npartition[0] * (ix[1] + ix[2] * Npartition[1]);//  Set send rank
+      B->ICELL = B->IPROC;                                      //  Do this to sort accroding to IPROC
+    }                                                           // End loop over bodies
+    stopTimer("Partition",printNow);                            // Stop timer
     return local;
   }
 
   void unpartition(Bodies &bodies) {
     startTimer("Unpartition");                                  // Start timer
     for (B_iter B=bodies.begin(); B!=bodies.end(); B++) {       // Loop over bodies
-      B->ICELL = B->IPROC;                                      //  Do this to sort accroding to IPROC
+      B->ICELL = B->IPROC;                                      //  Do this to sortaccroding to IPROC
     }                                                           // End loop over bodies
-    Bodies buffer = bodies;                                     // Resize sort buffer
     stopTimer("Unpartition", printNow);                         // Stop timer
-    sortBodies(bodies, buffer);                                 // Sort bodies in ascending order
-    startTimer("Unpartition comm");                             // Start timer
-    alltoall(bodies);                                           // Alltoall send count
-    alltoallv(bodies);                                          // Alltoallv bodies
-    bodies = recvBodies;                                        // Copy receive buffer to bodies
-    stopTimer("Unpartition comm", printNow);                    // Stop timer
-    for (B_iter B=bodies.begin(); B!=bodies.end(); B++) {       // Loop over bodies
-      B->ICELL = B->IBODY;                                      //  Do this to sort accroding to IPROC
-    }                                                           // End loop over bodies
-    buffer = bodies;                                            // Resize sort buffer
-    sortBodies(bodies, buffer);                                 // Sort bodies in ascending order
   }
 };
 #endif
 //! Custom bucket sort for body and structures
 class Sort {
  private:
+  typedef Bodies::reverse_iterator B_ritr;                      //!< Reverse iterator for Bodies
   std::vector<int> bucket;                                      //!< Bucket for sorting
 
-//! Get bucket size for sorting
-  template<typename T>
-  void getBucketSize(T &values, int begin, int end, int &Imin, int &numBucket) {
-    typename T::iterator V0 = values.begin()+begin;             // Get begin iterator
-    typename T::iterator VN = values.begin()+end;               // Get end iterator
-    Imin = V0->ICELL;                                           // Initialize minimum index
-    int Imax = V0->ICELL;                                       // Initialize maximum index
-    for (typename T::iterator V=V0; V!=VN; V++) {               // Loop over vector
-      if      (V->ICELL < Imin) Imin = V->ICELL;                //  Set minimum index
-      else if (V->ICELL > Imax) Imax = V->ICELL;                //  Set maximum index
+ public:
+//! Sort input accoring to cell index
+  Bodies sortBodies(Bodies &input) {
+    int Imin = input[0].ICELL;                                  // Initialize minimum index
+    int Imax = input[0].ICELL;                                  // Initialize maximum index
+    for (B_iter B=input.begin(); B!=input.end(); ++B) {        // Loop over vector
+      if      (B->ICELL < Imin) Imin = B->ICELL;                //  Set minimum index
+      else if (B->ICELL > Imax) Imax = B->ICELL;                //  Set maximum index
     }                                                           // End loop over vector
-    numBucket = Imax - Imin + 1;                                // Use range of indices as bucket size
+    int numBucket = Imax - Imin + 1;                            // Use range of indices as bucket size
     if( numBucket > int(bucket.size()) ) {                      // If bucket size needs to be enlarged
       bucket.resize(numBucket);                                 //  Resize bucket vector
     }                                                           // Endif for resize
-  }
-
-//! Bucket sort for small indices
-  template<typename T>
-  void sortICELL(T &values, T &buffer, int Imin,
-                 int numBucket, bool ascend, int begin, int end) {
+    Bodies output(input.size());                                // Initialize output
     for (int i=0; i<numBucket; i++) bucket[i] = 0;              // Initialize bucket
-    for (int i=begin; i<end; i++) bucket[values[i].ICELL-Imin]++;// Fill bucket
+    for (B_iter B=input.begin(); B!=input.end(); ++B) bucket[B->ICELL-Imin]++;// Fill bucket
     for (int i=1; i<numBucket; i++) bucket[i] += bucket[i-1];   // Scan bucket
-    for (int i=end-1; i>=begin; i--) {                          // Loop over data backwards
-      bucket[values[i].ICELL-Imin]--;                           //  Empty bucket
-      int inew = bucket[values[i].ICELL-Imin]+begin;            //  Permutation index
-      buffer[inew] = values[i];                                 //  Fill buffer
+    for (B_ritr B=input.rbegin(); B!=input.rend(); ++B) {       // Loop over data backwards
+      bucket[B->ICELL-Imin]--;                                  //  Empty bucket
+      int inew = bucket[B->ICELL-Imin];                         //  Permutation index
+      output[inew] = *B;                                        //  Fill output
     }                                                           // End loop over data
-    if (ascend) {                                               // If sorting in ascending order
-      for (int i=begin; i<end; i++) values[i] = buffer[i];      //  Copy back bodiess in order
-    } else {                                                    // If sorting in descending order
-      for (int i=begin; i<end; i++) values[end-i+begin-1] = buffer[i];// Copy back bodiess in reverse order
-    }                                                           // Endif for sorting order
-  }
-
- public:
-//! Sort bodies accoring to cell index
-  void sortBodies(Bodies &bodies, Bodies &buffer, bool ascend=true, int begin=0, int end=0) {
-    if (bodies.size() == 0) return;                             // Don't do anything if vector is empty
-    if (end == 0) end = bodies.size();                          // Default range is the whole vector
-    int numBucket = 0;                                          // Initialize bucket size
-    int Imin = 0;                                               // Initialize minimum index
-    getBucketSize(bodies,begin,end,Imin,numBucket);             // Get bucket size for sorting
-    sortICELL(bodies,buffer,Imin,numBucket,ascend,begin,end);   // Call bucket sort for small indices
+    return output;                                              // Return output
   }
 };
 #endif
 };
 typedef AlignedAllocator<Body,SIMD_BYTES>         BodyAllocator;//!< Body alignment allocator
 typedef std::vector<Body,BodyAllocator>           Bodies;       //!< Vector of bodies
-typedef std::vector<Body,BodyAllocator>::iterator B_iter;       //!< Iterator of body vector
+typedef Bodies::iterator                          B_iter;       //!< Iterator of body vector
 
 //! Structure of cells
 struct Cell {