NAMD
Classes | Macros | Functions
SortAtoms.C File Reference
#include "SortAtoms.h"
#include "NamdTypes.h"
#include <algorithm>
#include "CudaUtils.h"

Go to the source code of this file.

Classes

struct  sortop_base
 
struct  sortop_x
 
struct  sortop_y
 
struct  sortop_z
 
struct  sortop_SOA
 

Macros

#define PARTWIDTH   32
 
#define NTH_ELEMENT(BEGIN, SPLIT, END, OP)   std::nth_element(BEGIN,SPLIT,END,OP)
 
#define NORMAL_SPLIT   32
 
#define FINAL_SPLIT   8
 
#define NTH_ELEMENT(BEGIN, SPLIT, END, OP)   std::nth_element(BEGIN,SPLIT,END,OP)
 

Functions

static void partition (int *order, const FullAtom *atoms, int begin, int end)
 
void sortAtomsForCUDA (int *order, const FullAtom *atoms, int nfree, int n)
 
void sortAtomsForPatches (int *order, int *breaks, const FullAtom *atoms, int nmgrps, int natoms, int ni, int nj, int nk)
 
static void partition_SOA (int *__restrict order, const double *__restrict ax, const double *__restrict ay, const double *__restrict az, int begin, int end)
 
void sortAtomsForCUDA_SOA (int *__restrict order, int *__restrict unorder, const double *__restrict ax, const double *__restrict ay, const double *__restrict az, int nfree, int n)
 

Macro Definition Documentation

◆ FINAL_SPLIT

#define FINAL_SPLIT   8

Definition at line 208 of file SortAtoms.C.

Referenced by partition_SOA().

◆ NORMAL_SPLIT

#define NORMAL_SPLIT   32

Definition at line 204 of file SortAtoms.C.

Referenced by partition_SOA().

◆ NTH_ELEMENT [1/2]

#define NTH_ELEMENT (   BEGIN,
  SPLIT,
  END,
  OP 
)    std::nth_element(BEGIN,SPLIT,END,OP)

Referenced by partition(), and partition_SOA().

◆ NTH_ELEMENT [2/2]

#define NTH_ELEMENT (   BEGIN,
  SPLIT,
  END,
  OP 
)    std::nth_element(BEGIN,SPLIT,END,OP)

◆ PARTWIDTH

#define PARTWIDTH   32

Referenced by partition().

Function Documentation

◆ partition()

static void partition ( int *  order,
const FullAtom *  atoms,
int  begin,
int  end 
)
static

Definition at line 45 of file SortAtoms.C.

References NTH_ELEMENT, order, PARTWIDTH, CompAtom::position, split(), Vector::x, Vector::y, and Vector::z.

Referenced by Sequencer::calcKineticEnergy(), HomePatch::hardWallDrude(), Sequencer::langevinVelocities(), Sequencer::langevinVelocitiesBBK2(), ComputeHomeTuples< TholeElem, Thole, TholeValue >::loadTuples(), Sequencer::multigratorPressure(), HomePatch::positionsReady_SOA(), HomePatch::rattle1old(), Sequencer::reassignVelocities(), Sequencer::reinitVelocities(), sortAtomsForCUDA(), Sequencer::submitHalfstep(), and Sequencer::submitReductions().

45  {
46 
47  // Applies orthogonal recursive bisection with splittings limited
48  // to multiples of WARPSIZE for warps and a final split on multiples of WARPSIZE/2.
49 
50 #ifdef NAMD_AVXTILES
51 #define PARTWIDTH 16
52 #else
53 #define PARTWIDTH 32
54 #endif
55 
56  int split;
57  // must be a multiple of 32 or 16 between begin and end to split at
58  if ( begin/PARTWIDTH < (end-1)/PARTWIDTH ) {
59  // find a multiple of 32 near the median
60  split = ((begin + end + PARTWIDTH) / (PARTWIDTH*2)) * PARTWIDTH;
61  } else if ( begin/(PARTWIDTH/2) < (end-1)/(PARTWIDTH/2) ) {
62  // find a multiple of 16 near the median
63  split = ((begin + end + (PARTWIDTH/2)) / PARTWIDTH) * (PARTWIDTH/2);
64  } else {
65  return;
66  }
67 
68  BigReal xmin, ymin, zmin, xmax, ymax, zmax;
69  {
70  const Position &pos = atoms[order[begin]].position;
71  xmin = pos.x;
72  ymin = pos.y;
73  zmin = pos.z;
74  xmax = pos.x;
75  ymax = pos.y;
76  zmax = pos.z;
77  }
78  for ( int i=begin+1; i<end; ++i ) {
79  const Position &pos = atoms[order[i]].position;
80  if ( pos.x < xmin ) { xmin = pos.x; }
81  if ( pos.y < ymin ) { ymin = pos.y; }
82  if ( pos.z < zmin ) { zmin = pos.z; }
83  if ( pos.x > xmax ) { xmax = pos.x; }
84  if ( pos.y > ymax ) { ymax = pos.y; }
85  if ( pos.z > zmax ) { zmax = pos.z; }
86  }
87  xmax -= xmin;
88  ymax -= ymin;
89  zmax -= zmin;
90 
91 #define NTH_ELEMENT(BEGIN,SPLIT,END,OP) std::nth_element(BEGIN,SPLIT,END,OP)
92 #if (defined(NAMD_CUDA) || defined(NAMD_HIP)) && defined(__GNUC_PATCHLEVEL__)
93 #if __GNUC__ == 4 && __GNUC_MINOR__ == 8 && __GNUC_PATCHLEVEL__ == 2
94 #define NTH_ELEMENT(BEGIN,SPLIT,END,OP) std::sort(BEGIN,END,OP)
95 #warning gcc 4.8.2 std::nth_element would segfault (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800)
96 #endif
97 #endif
98 
99  if ( xmax >= ymax && xmax >= zmax ) {
100  NTH_ELEMENT(order+begin, order+split, order+end, sortop_x(atoms));
101  } else if ( ymax >= xmax && ymax >= zmax ) {
102  NTH_ELEMENT(order+begin, order+split, order+end, sortop_y(atoms));
103  } else {
104  NTH_ELEMENT(order+begin, order+split, order+end, sortop_z(atoms));
105  }
106 
107  if ( split & PARTWIDTH/2 ) return;
108 
109 #undef PARTWIDTH
110 
111  // recursively partition before and after split
112  partition(order, atoms, begin, split);
113  partition(order, atoms, split, end);
114 
115 }
sortop_x
Definition: SortAtoms.C:23
partition
static void partition(int *order, const FullAtom *atoms, int begin, int end)
Definition: SortAtoms.C:45
Vector
Definition: Vector.h:72
Vector::z
BigReal z
Definition: Vector.h:74
CompAtom::position
Position position
Definition: NamdTypes.h:77
NTH_ELEMENT
#define NTH_ELEMENT(BEGIN, SPLIT, END, OP)
order
#define order
Definition: PmeRealSpace.C:235
PARTWIDTH
#define PARTWIDTH
Vector::x
BigReal x
Definition: Vector.h:74
split
std::vector< std::string > split(const std::string &text, std::string delimiter)
Definition: MoleculeQM.C:74
sortop_z
Definition: SortAtoms.C:37
Vector::y
BigReal y
Definition: Vector.h:74
sortop_y
Definition: SortAtoms.C:30
BigReal
double BigReal
Definition: common.h:123

◆ partition_SOA()

static void partition_SOA ( int *__restrict  order,
const double *__restrict  ax,
const double *__restrict  ay,
const double *__restrict  az,
int  begin,
int  end 
)
static

Definition at line 210 of file SortAtoms.C.

References FINAL_SPLIT, NORMAL_SPLIT, NTH_ELEMENT, order, split(), Vector::x, Vector::y, and Vector::z.

Referenced by sortAtomsForCUDA_SOA().

216  {
217 
218  // Applies orthogonal recursive bisection with splittings limited
219  // to multiples of 32 for warps and a final split on multiples of 16.
220  int split = -1;
221  // must be a multiple of 32 or 16 between begin and end to split at
222  int split_factor = NORMAL_SPLIT;
223 #ifdef NAMD_HIP
224  if ( begin/NORMAL_SPLIT < (end-1)/NORMAL_SPLIT ) {
225  // find a multiple of 32 near the median
226  split = ((begin + end + NORMAL_SPLIT) / (NORMAL_SPLIT*2)) * NORMAL_SPLIT;
227  } else if ( begin/(NORMAL_SPLIT/2) < (end-1)/(NORMAL_SPLIT/2) ) {
228  // find a multiple of 16 near the median
229  split = ((begin + end + (NORMAL_SPLIT/2)) / NORMAL_SPLIT) * NORMAL_SPLIT/2;
230  } else {
231  return;
232  }
233 #else
234  while (split == -1) {
235  if ( begin/split_factor < (end-1)/split_factor ) {
236  split = ((begin + end + split_factor) / (split_factor*2)) * split_factor;
237  }
238  split_factor /= 2;
239  if (split_factor == 1) return;
240  }
241 #endif
242 
243  BigReal xmin, ymin, zmin, xmax, ymax, zmax;
244  {
245 #if 0
246  const Position &pos = atoms[order[begin]].position;
247  xmin = pos.x;
248  ymin = pos.y;
249  zmin = pos.z;
250  xmax = pos.x;
251  ymax = pos.y;
252  zmax = pos.z;
253 #else
254  int i = order[begin];
255  xmin = ax[i];
256  xmax = ax[i];
257  ymin = ay[i];
258  ymax = ay[i];
259  zmin = az[i];
260  zmax = az[i];
261 #endif
262  }
263  for ( int i=begin+1; i<end; ++i ) {
264 #if 0
265  const Position &pos = atoms[order[i]].position;
266  if ( pos.x < xmin ) { xmin = pos.x; }
267  if ( pos.y < ymin ) { ymin = pos.y; }
268  if ( pos.z < zmin ) { zmin = pos.z; }
269  if ( pos.x > xmax ) { xmax = pos.x; }
270  if ( pos.y > ymax ) { ymax = pos.y; }
271  if ( pos.z > zmax ) { zmax = pos.z; }
272 #else
273  int j = order[i];
274  if ( ax[j] < xmin ) { xmin = ax[j]; }
275  if ( ax[j] > xmax ) { xmax = ax[j]; }
276  if ( ay[j] < ymin ) { ymin = ay[j]; }
277  if ( ay[j] > ymax ) { ymax = ay[j]; }
278  if ( az[j] < zmin ) { zmin = az[j]; }
279  if ( az[j] > zmax ) { zmax = az[j]; }
280 #endif
281  }
282  xmax -= xmin;
283  ymax -= ymin;
284  zmax -= zmin;
285 
286 #undef NTH_ELEMENT
287 #define NTH_ELEMENT(BEGIN,SPLIT,END,OP) std::nth_element(BEGIN,SPLIT,END,OP)
288 #if (defined(NAMD_CUDA) || defined(NAMD_HIP)) && defined(__GNUC_PATCHLEVEL__)
289 #if __GNUC__ == 4 && __GNUC_MINOR__ == 8 && __GNUC_PATCHLEVEL__ == 2
290 #define NTH_ELEMENT(BEGIN,SPLIT,END,OP) std::sort(BEGIN,END,OP)
291 #warning gcc 4.8.2 std::nth_element would segfault (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800)
292 #endif
293 #endif
294 
295  if ( xmax >= ymax && xmax >= zmax ) {
296  NTH_ELEMENT(order+begin, order+split, order+end, sortop_SOA(ax));
297  } else if ( ymax >= xmax && ymax >= zmax ) {
298  NTH_ELEMENT(order+begin, order+split, order+end, sortop_SOA(ay));
299  } else {
300  NTH_ELEMENT(order+begin, order+split, order+end, sortop_SOA(az));
301  }
302 
303  if ( split & FINAL_SPLIT ) return;
304 
305  // recursively partition before and after split
306  partition_SOA(order, ax, ay, az, begin, split);
307  partition_SOA(order, ax, ay, az, split, end);
308 
309 }
partition_SOA
static void partition_SOA(int *__restrict order, const double *__restrict ax, const double *__restrict ay, const double *__restrict az, int begin, int end)
Definition: SortAtoms.C:210
Vector
Definition: Vector.h:72
Vector::z
BigReal z
Definition: Vector.h:74
sortop_SOA
Definition: SortAtoms.C:196
NTH_ELEMENT
#define NTH_ELEMENT(BEGIN, SPLIT, END, OP)
order
#define order
Definition: PmeRealSpace.C:235
FINAL_SPLIT
#define FINAL_SPLIT
Definition: SortAtoms.C:208
Vector::x
BigReal x
Definition: Vector.h:74
split
std::vector< std::string > split(const std::string &text, std::string delimiter)
Definition: MoleculeQM.C:74
NORMAL_SPLIT
#define NORMAL_SPLIT
Definition: SortAtoms.C:204
Vector::y
BigReal y
Definition: Vector.h:74
BigReal
double BigReal
Definition: common.h:123

◆ sortAtomsForCUDA()

void sortAtomsForCUDA ( int *  order,
const FullAtom *  atoms,
int  nfree,
int  n 
)

Definition at line 123 of file SortAtoms.C.

References order, and partition().

Referenced by HomePatch::positionsReady().

123  {
124 
125  // partition free atoms
126  // CkPrintf("%d %d\n", 0, nfree);
127  partition(order, atoms, 0, nfree);
128 
129  // partition fixed atoms
130  // CkPrintf("%d %d\n", nfree, n);
131  partition(order, atoms, nfree, n);
132 
133 }
partition
static void partition(int *order, const FullAtom *atoms, int begin, int end)
Definition: SortAtoms.C:45
order
#define order
Definition: PmeRealSpace.C:235

◆ sortAtomsForCUDA_SOA()

void sortAtomsForCUDA_SOA ( int *__restrict  order,
int *__restrict  unorder,
const double *__restrict  ax,
const double *__restrict  ay,
const double *__restrict  az,
int  nfree,
int  n 
)

Definition at line 317 of file SortAtoms.C.

References order, and partition_SOA().

Referenced by HomePatch::positionsReady_SOA().

324  {
325 
326  // partition free atoms
327  // CkPrintf("%d %d\n", 0, nfree);
328  partition_SOA(order, ax, ay, az, 0, nfree);
329 
330  // partition fixed atoms
331  // CkPrintf("%d %d\n", nfree, n);
332  partition_SOA(order, ax, ay, az, nfree, n);
333 
334  // determine mapping to unsort atoms
335  for (int i=0; i < n; i++) {
336  unorder[order[i]] = i;
337  }
338 }
partition_SOA
static void partition_SOA(int *__restrict order, const double *__restrict ax, const double *__restrict ay, const double *__restrict az, int begin, int end)
Definition: SortAtoms.C:210
order
#define order
Definition: PmeRealSpace.C:235

◆ sortAtomsForPatches()

void sortAtomsForPatches ( int *  order,
int *  breaks,
const FullAtom *  atoms,
int  nmgrps,
int  natoms,
int  ni,
int  nj,
int  nk 
)

Definition at line 135 of file SortAtoms.C.

References FullAtom::migrationGroupSize, and order.

Referenced by WorkDistrib::createAtomLists().

137  {
138 
139 //CkPrintf("sorting %d atoms in %d groups to %d x %d x %d\n",
140 // natoms, nmgrps, nk, nj, ni);
141  std::sort(order, order+nmgrps, sortop_z(atoms));
142  int pid = 0;
143  int ibegin = 0;
144  int nai = 0;
145  for ( int ip=0; ip < ni; ++ip ) {
146  int naj = nai;
147  int targi = nai + (natoms - nai - 1) / (ni - ip) + 1;
148  int iend;
149  for ( iend=ibegin; iend<nmgrps; ++iend ) {
150  int mgs = atoms[order[iend]].migrationGroupSize;
151  if (nai + mgs <= targi) nai += mgs;
152  else break;
153  }
154 //CkPrintf(" Z %d %d (%d) %d\n", ibegin, iend, iend-ibegin, nai);
155  std::sort(order+ibegin, order+iend, sortop_y(atoms));
156  int jbegin = ibegin;
157  for ( int jp=0; jp < nj; ++jp ) {
158  int nak = naj;
159  int targj = naj + (nai - naj - 1) / (nj - jp) + 1;
160  int jend;
161  for ( jend=jbegin; jend<iend; ++jend ) {
162  int mgs = atoms[order[jend]].migrationGroupSize;
163  if (naj + mgs <= targj) naj += mgs;
164  else break;
165  }
166 
167 //CkPrintf(" Y %d %d (%d) %d\n", jbegin, jend, jend-jbegin, naj);
168  std::sort(order+jbegin, order+jend, sortop_x(atoms));
169  int kbegin = jbegin;
170  for ( int kp=0; kp < nk; ++kp ) {
171  int targk = nak + (naj - nak - 1) / (nk - kp) + 1;
172  int kend;
173  for ( kend=kbegin; kend<jend; ++kend ) {
174  int mgs = atoms[order[kend]].migrationGroupSize;
175  if (nak + mgs <= targk) nak += mgs;
176  else break;
177 //CkPrintf(" atom %d %d %.2f\n", atoms[order[kend]].id, mgs,
178 // atoms[order[kend]].position.x);
179  }
180 //CkPrintf(" X %d %d (%d) %d\n", kbegin, kend, kend-kbegin, nak);
181  breaks[pid++] = kend;
182  kbegin = kend;
183  }
184  jbegin = jend;
185  }
186  ibegin = iend;
187  }
188 
189 }
sortop_x
Definition: SortAtoms.C:23
order
#define order
Definition: PmeRealSpace.C:235
FullAtom::migrationGroupSize
int32 migrationGroupSize
Definition: NamdTypes.h:220
sortop_z
Definition: SortAtoms.C:37
sortop_y
Definition: SortAtoms.C:30
Generated by   doxygen 1.8.14