VM2D 1.14
Vortex methods for 2D flows simulation
Loading...
Searching...
No Matches
Functions | Variables
knnNew Namespace Reference

Functions

unsigned int ExpandBits (unsigned int v)
 
unsigned int Morton2D (const Point2D &r)
 
void RSort_Parallel (TParticleCode *m, TParticleCode *m_temp, unsigned int n, unsigned int *s)
 Сортировка массива из мортоновский кодов
 
size_t BinSearch (const std::vector< std::pair< double, size_t > > &currentNN, double x, int low, int high)
 
void newSort (std::vector< std::pair< double, size_t > > &mass, std::vector< std::pair< double, size_t > > &dstKeys)
 
void newMerge (int iii, std::vector< std::pair< double, size_t > > &currentNN, const std::vector< std::pair< double, size_t > > &candidateNN, std::vector< size_t > &loc, std::vector< size_t > &counter, std::vector< size_t > &offset, std::vector< size_t > &counterScan, std::vector< std::pair< double, size_t > > &updateNN)
 
std::pair< bool, bool > calcCheck (const Vortex2D &vtxi, const Vortex2D &vtxk, double maxG, double cSP, double cRBP, double epsCol, int type, double &d2)
 

Variables

const int twoPowCodeLengthVar = (1 << codeLength)
 

Function Documentation

◆ BinSearch()

size_t knnNew::BinSearch ( const std::vector< std::pair< double, size_t > > &  currentNN,
double  x,
int  low,
int  high 
)
inline

Definition at line 169 of file knnCPU.cpp.

170 {
171 int mid = -1;
172
173 if (x > currentNN[high].first)
174 return high + 1;
175
176 while (low <= high) {
177 mid = (low + high) / 2;
178
179 if (currentNN[mid].first == x)
180 return mid + 1; //выход из цикла
181
182 if (currentNN[mid].first < x)
183 low = mid + 1;
184 else
185 high = mid - 1;
186 }
187 return mid;
188 }
Here is the caller graph for this function:

◆ calcCheck()

std::pair< bool, bool > knnNew::calcCheck ( const Vortex2D &  vtxi,
const Vortex2D &  vtxk,
double  maxG,
double  cSP,
double  cRBP,
double  epsCol,
int  type,
double &  d2 
)

Definition at line 264 of file knnCPU.cpp.

265 {
266 bool flagExit = false;
267 bool check = false;
268
269 //линейное увеличение радиуса коллапса
270 double mnog = std::max(1.0, /* 2.0 * */ (vtxi.r()[0] - cRBP) / cSP);
271 double r2test = (epsCol * mnog) * (epsCol * mnog);
272
273 if (type == 1)
274 r2test *= 4.0; //Увеличение радиуса коллапса в 2 раза для коллапса вихрей разных знаков
275
276 d2 = (vtxi.r() - vtxk.r()).length2();
277
278 if (d2 > r2test)
279 {
280 flagExit = true;
281 return { true, false };
282 }
283
284 const double gi = vtxi.g();
285 const double gk = vtxk.g();
286
287 if (d2 < r2test)
288 {
289 switch (type)
290 {
291 case 0:
292 check = (fabs(gi * gk) != 0.0) && (fabs(gi + gk) < (mnog * mnog) * maxG);
293 break;
294 case 1:
295 check = (gi * gk < 0.0);
296 break;
297 case 2:
298 check = (gi * gk > 0.0) && (fabs(gi + gk) < (mnog * mnog) * maxG);
299 break;
300 }
301 }//if r2 < r2_test
302
303 return { false, check };
304 }
VMlib::Vortex2D::r
HD Point2D & r()
Функция для доступа к радиус-вектору вихря
Definition Vortex2D.h:92
VMlib::Vortex2D::g
HD double & g()
Функция для доступа к циркуляции вихря
Definition Vortex2D.h:100
Here is the call graph for this function:

◆ ExpandBits()

unsigned int knnNew::ExpandBits ( unsigned int  v)

Definition at line 54 of file knnCPU.cpp.

55 {
56 // вставит 1 нуль
57 v = (v | (v << 8)) & 0x00FF00FF; // 00000000`00000000`abcdefgh`ijklmnop
58 // | 00000000`abcdefgh`ijklmnop`00000000
59 // = 00000000`abcdefgh`XXXXXXXX`ijklmnop
60 // & 00000000`11111111`00000000`11111111
61 // = 00000000`abcdefgh`00000000`ijklmnop
62
63 v = (v | (v << 4)) & 0x0F0F0F0F; // 00000000`abcdefgh`00000000`ijklmnop
64 // | 0000abcd`efgh0000`0000ijkl`mnop0000
65 // = 0000abcd`XXXXefgh`0000ijkl`XXXXmnop
66 // & 00001111`00001111`00001111`00001111
67 // = 0000abcd`0000efgh`0000ijkl`0000mnop
68
69 v = (v | (v << 2)) & 0x33333333; // 0000abcd`0000efgh`0000ijkl`0000mnop
70 // | 00abcd00`00efgh00`00ijkl00`00mnop00
71 // = 00abXXcd`00efXXgh`00ijXXkl`00mnXXop
72 // & 00110011`00110011`00110011`00110011
73 // = 00ab00cd`00ef00gh`00ij00kl`00mn00op
74
75 v = (v | (v << 1)) & 0x55555555; // 00ab00cd`00ef00gh`00ij00kl`00mn00op
76 // | 0ab00cd0`0ef00gh0`0ij00kl0`0mn00op0
77 // = 0aXb0cXd`0eXf0gXh`0iXj0kXl`0mXn0oXp
78 // & 01010101`01010101`01010101`01010101
79 // = 0a0b0c0d`0e0f0g0h`0i0j0k0l`0m0n0o0p
80 return v;
81 }
Here is the caller graph for this function:

◆ Morton2D()

unsigned int knnNew::Morton2D ( const Point2D &  r)

Definition at line 86 of file knnCPU.cpp.

87 {
88 const Point2D& rscale = twoPowCodeLengthVar * r;
89 const unsigned int& xx = ExpandBits((unsigned int)(rscale[0]));
90 const unsigned int& yy = ExpandBits((unsigned int)(rscale[1]));
91 return yy | (xx << 1);
92 }
knnNew::twoPowCodeLengthVar
const int twoPowCodeLengthVar
Definition knnCPU.cpp:49
Here is the call graph for this function:

◆ newMerge()

void knnNew::newMerge ( int  iii,
std::vector< std::pair< double, size_t > > &  currentNN,
const std::vector< std::pair< double, size_t > > &  candidateNN,
std::vector< size_t > &  loc,
std::vector< size_t > &  counter,
std::vector< size_t > &  offset,
std::vector< size_t > &  counterScan,
std::vector< std::pair< double, size_t > > &  updateNN 
)

Definition at line 212 of file knnCPU.cpp.

221 {
222 const size_t k = candidateNN.size() / 2; //количество ближайших соседей
223
224 for (size_t j = 0; j < 2 * k; ++j)
225 loc[j] = BinSearch(currentNN, candidateNN[j].first, 0, (int)k - 1);
226
227 for (size_t j = 0; j < 2 * k; ++j)
228 counter[j] = j & 1;
229
230 for (size_t j = 0; j < 2 * k; ++j)
231 {
232 if ((loc[j] > 0) && ((loc[j] == k) || (candidateNN[j].second == currentNN[loc[j] - 1].second)))
233 offset[j] = k + 1;
234 else
235 offset[j] = counter[2 * loc[j]]++;
236 }
237
238 counterScan[0] = 0;
239 for (size_t j = 1; j < 2 * k; ++j)
240 counterScan[j] = counterScan[j - 1] + counter[j - 1];
241
242 size_t index;
243 for (size_t j = 0; j < k; ++j)
244 {
245 index = counterScan[2 * j + 1];
246 if (index < k)
247 updateNN[index] = currentNN[j];
248 }
249
250 for (size_t j = 0; j < 2 * k; ++j)
251 {
252 if (2 * loc[j] < 2 * k)
253 {
254 index = counterScan[2 * loc[j]] + offset[j];
255 if (index < k)
256 updateNN[index] = candidateNN[j];
257 }
258 }
259
260 currentNN.swap(updateNN);
261 }
knnNew::BinSearch
size_t BinSearch(const std::vector< std::pair< double, size_t > > &currentNN, double x, int low, int high)
Definition knnCPU.cpp:169
Here is the call graph for this function:

◆ newSort()

void knnNew::newSort ( std::vector< std::pair< double, size_t > > &  mass,
std::vector< std::pair< double, size_t > > &  dstKeys 
)

Definition at line 190 of file knnCPU.cpp.

190 {
191 const size_t k = mass.size();
192 size_t cnt = 0;
193
194 for (size_t i = 0; i < k; ++i)
195 {
196 double elem = mass[i].first;
197
198 cnt = 0;
199 for (size_t j = 0; j < k; ++j)
200 cnt += (mass[j].first < elem);
201
202 //Это для того, чтобы сортировка была устойчивой? Без этого никак?
203 //&&&
204 //for (size_t j = 0; j < i; ++j)
205 // cnt += (mass[j].first == elem);
206
207 dstKeys[cnt] = mass[i];
208 }
209 mass.swap(dstKeys);
210 }

◆ RSort_Parallel()

void knnNew::RSort_Parallel ( TParticleCode *  m,
TParticleCode *  m_temp,
unsigned int  n,
unsigned int *  s 
)

Сортировка массива из мортоновский кодов

Definition at line 96 of file knnCPU.cpp.

97 {
98 if (n == 0)
99 return;
100 // Количество задействованных потоков
101 unsigned char threads = omp_get_max_threads();
102 //std::cout << "threads = " << (int)threads << std::endl;
103
104#pragma omp parallel num_threads(threads)
105 {
106 TParticleCode* source = m;
107 TParticleCode* dest = m_temp;
108 unsigned int l = omp_get_thread_num();
109 unsigned int div = n / omp_get_num_threads();
110 unsigned int mod = n % omp_get_num_threads();
111 unsigned int left_index = l < mod ? (div + (mod == 0 ? 0 : 1)) * l : n - (omp_get_num_threads() - l) * div;
112 unsigned int right_index = left_index + div - (mod > l ? 0 : 1);
113
114 for (unsigned int digit = 0; digit < sizeof(m->key); ++digit)
115 {
116 unsigned int s_sum[256] = { 0 };
117 unsigned int s0[256] = { 0 };
118 unsigned char* b1 = (unsigned char*)&source[right_index].key;
119 unsigned char* b2 = (unsigned char*)&source[left_index].key;
120 while (b1 >= b2)
121 {
122 ++s0[*(b1 + digit)];
123 b1 -= sizeof(TParticleCode);
124 }
125 for (unsigned int i = 0; i < 256; i++)
126 {
127 s[i + 256 * l] = s0[i];
128 }
129
130#pragma omp barrier
131 for (unsigned int j = 0; j < threads; j++)
132 {
133 for (unsigned int i = 0; i < 256; i++)
134 {
135 s_sum[i] += s[i + 256 * j];
136 if (j < l)
137 {
138 s0[i] += s[i + 256 * j];
139 }
140 }
141 }
142
143 for (unsigned int i = 1; i < 256; ++i)
144 {
145 s_sum[i] += s_sum[i - 1];
146 s0[i] += s_sum[i - 1];
147 }
148 unsigned char* b = (unsigned char*)&source[right_index].key + digit;
149 TParticleCode* v1 = &source[right_index];
150 TParticleCode* v2 = &source[left_index];
151 while (v1 >= v2)
152 {
153 dest[--s0[*b]] = *v1--;
154 b -= sizeof(TParticleCode);
155 }
156#pragma omp barrier
157 std::swap(source, dest);
158 }
159 }
160
161 // Если ключ структуры однобайтовый, просто копируем в исходный массив
162 if (sizeof(m->key) == 1)
163 {
164 memcpy(m, m_temp, n * sizeof(TParticleCode));
165 }
166 }
VMlib::TParticleCode::key
unsigned int key
Мортоновский код частицы
Definition Point2D.h:57

Variable Documentation

◆ twoPowCodeLengthVar

const int knnNew::twoPowCodeLengthVar = (1 << codeLength)

Definition at line 49 of file knnCPU.cpp.