Почему мой Radix сортирует с OpenMP+AVX неправильно, в то время как версия только OpenMP работает? ⇐ C++

[Anonymous]

Я реализую кусочек Radix Sort, чтобы сортировать массив 64-битных целых чисел без знака (

Код: Выделить всё

key_t

IS uint_fast64_t ), который представляет кодируемые точки.
У меня есть две версии алгоритма:

antingmp только - работает правильно. - создает неправильно отсортированный выход. < /P>
< /li>
< /ul>
Обе версии параллелизируются над кусками входного массива с помощью OpenMP. Проблема появляется, когда я векторизую фазу подсчета битов и перераспределение с помощью инструкций AVX.

Код: Выделить всё

template 
std::vector mySort_v1(std::vector &points,
std::optional &meta_opt, const Box &bbox) const
{

size_t n = points.size();
constexpr int BITS_PER_PASS = 8;
constexpr int NUM_BUCKETS = 1 > shift) & BUCKET_MASK;
hist[bucket]++;
}
}

// Step 2: Scan histograms to offsets
size_t offset = 0;
for (int b = 0; b < NUM_BUCKETS; b++)
{
for (int t = 0; t < nThreads; t++)
{
size_t val = localHist[t][b];
localHist[t][b] = offset;
offset += val;
}
}

// Step 3: Scatter to buffer using per-thread offsets
#pragma omp parallel
{
auto &localOffset = localHist[omp_get_thread_num()];
#pragma omp for schedule(static)
for (size_t i = 0; i < n; i++)
{
size_t bucket = (keys[i] >> shift) & BUCKET_MASK;
size_t pos = localOffset[bucket]++;
buffer[pos] = keys[i];
bufferDecoded[pos] = points[i];
if (meta_opt)
metadata_buffer[pos] = (*meta_opt)[i];
}
}

std::swap(points, bufferDecoded);
std::swap(keys, buffer);
if (meta_opt)
std::swap(*meta_opt, metadata_buffer);
}

return keys;
}

openmp + avx:
template
std::vector BasicOptimizedAVX(std::vector &points,
std::optional &meta_opt,
const Box &bbox) const
{
size_t n = points.size();
constexpr int BITS_PER_PASS = 8;
constexpr int NUM_BUCKETS = 1
__m256i shifted_right = _mm256_srli_epi64(vec, shift);

// Aplicar AND bit a bit
__m256i result_and = _mm256_and_si256(shifted_right, mask_vec);

// Store
alignas(32) uint64_t result[4];
_mm256_storeu_si256((__m256i *)result, result_and);

hist[result[0]]++;
hist[result[1]]++;
hist[result[2]]++;
hist[result[3]]++;
}
}

// Other elements
for (size_t i = (n / 4) * 4; i < n; ++i)
{
size_t bucket = (keys >> shift) & BUCKET_MASK;
localHist[0][bucket]++;
}

// Step 2: Scan histograms to offsets
size_t offset = 0;
for (int b = 0; b < NUM_BUCKETS; b++)
{
for (int t = 0; t < nThreads; t++)
{
size_t val = localHist[t];
localHist[t] = offset;
offset += val;
}
}

// Step 3: Scatter to buffer using per-thread offsets
#pragma omp parallel
{
auto &localOffset = localHist[omp_get_thread_num()];
#pragma omp for schedule(static)
for (size_t i = 0; i > shift) & BUCKET_MASK;
// Cargar datos y máscara en registros AVX
__m256i vec = _mm256_loadu_si256((__m256i*)&keys);

// Shift >>
__m256i shifted_right = _mm256_srli_epi64(vec, shift);

// Aplicar AND bit a bit
__m256i result_and = _mm256_and_si256(shifted_right, mask_vec);

// Store
alignas(32) uint64_t result[4];
_mm256_storeu_si256((__m256i *)result, result_and);

for(int j = 0; j < 4; ++j)
{
size_t bucket = result[j];
size_t pos = localOffset[bucket]++;
buffer[pos] = keys[i + j];
bufferDecoded[pos] = points[i + j];
if (meta_opt)
metadata_buffer[pos] = (*meta_opt)[i + j];
}
}
}

// Other elements
auto &localOffset_remaining = localHist[0]; // Thread 0
for (size_t i = (n / 4) * 4; i < n; ++i)
{
size_t bucket = (keys >> shift) & BUCKET_MASK;
size_t pos = localOffset_remaining[bucket]++;
buffer[pos] = keys;
bufferDecoded[pos] = points;
if (meta_opt)
metadata_buffer[pos] = (*meta_opt);
}

std::swap(points, bufferDecoded);
std::swap(keys, buffer);
if (meta_opt)
std::swap(*meta_opt, metadata_buffer);
}

return keys;
}
< /code>
Я не знаю, в чем проблема. Я уже проверил, что он прошел все точки и т. Д.>

Подробнее здесь: https://stackoverflow.com/questions/797 ... penmp-only