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 168 of file knnCPU.cpp.

169 {
170 int mid = -1;
171
172 if (x > currentNN[high].first)
173 return high + 1;
174
175 while (low <= high) {
176 mid = (low + high) / 2;
177
178 if (currentNN[mid].first == x)
179 return mid + 1; //выход из цикла
180
181 if (currentNN[mid].first < x)
182 low = mid + 1;
183 else
184 high = mid - 1;
185 }
186 return mid;
187 }
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 263 of file knnCPU.cpp.

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

◆ ExpandBits()

unsigned int knnNew::ExpandBits ( unsigned int  v)

Definition at line 53 of file knnCPU.cpp.

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

◆ Morton2D()

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

Definition at line 85 of file knnCPU.cpp.

86 {
87 const Point2D& rscale = twoPowCodeLengthVar * r;
88 const unsigned int& xx = ExpandBits((unsigned int)(rscale[0]));
89 const unsigned int& yy = ExpandBits((unsigned int)(rscale[1]));
90 return yy | (xx << 1);
91 }
knnNew::twoPowCodeLengthVar
const int twoPowCodeLengthVar
Definition knnCPU.cpp:48
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 211 of file knnCPU.cpp.

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

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

◆ RSort_Parallel()

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

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

Definition at line 95 of file knnCPU.cpp.

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

Variable Documentation

◆ twoPowCodeLengthVar

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

Definition at line 48 of file knnCPU.cpp.