#include "all/deryabin_m_hoare_sort_simple_merge/i...

#include "all/deryabin_m_hoare_sort_simple_merge/include/ops_all.hpp"

#include <oneapi/tbb/parallel_for.h>
#include <oneapi/tbb/parallel_invoke.h>

#include <algorithm>
#include <bit>
#include <boost/mpi/collectives/broadcast.hpp>
#include <cmath>
#include <cstddef>
#include <iterator>
#include <vector>

double deryabin_m_hoare_sort_simple_merge_mpi::PivotCalculation(std::vector<double>::iterator first,
std::vector<double>::iterator last) {
const auto mid = first + ((last - first) >> 1);
double pivot_value = NAN;
if (last - first < 199) {
pivot_value = *mid;
} else {
if (*first < *mid) {
if (*mid < *last) {
pivot_value = *mid;
} else {
pivot_value = std::max(*first, *last);
}
} else {
if (*first < *last) {
pivot_value = *first;
} else {
pivot_value = std::max(*mid, *last);
}
}
}
return pivot_value;
}

void deryabin_m_hoare_sort_simple_merge_mpi::SeqHoaraSort(std::vector<double>::iterator first,
std::vector<double>::iterator last) {
if (first >= last) {
return;
}
const double pivot_value = PivotCalculation(first, last);
auto left = first;
auto right = last;
do {
while (left < last && *left < pivot_value) {
left++;
}
while (right > first && *right > pivot_value) {
right--;
}
if (*left == *right && left != right) {
if (*left < *(left + 1)) {
left++;
} else {
right--;
}
}
std::iter_swap(left, right);
} while (left != right);
SeqHoaraSort(first, right);
SeqHoaraSort(left + 1, last);
}

void deryabin_m_hoare_sort_simple_merge_mpi::HoaraSort(std::vector<double>::iterator first,
std::vector<double>::iterator last) {
if (first >= last) {
return;
}
const double pivot_value = PivotCalculation(first, last);
auto left = first;
auto right = last;
do {
while (left < last && *left < pivot_value) {
left++;
}
while (right > first && *right > pivot_value) {
right--;
}
if (*left == *right && left != right) {
if (*left < *(left + 1)) {
left++;
} else {
right--;
}
}
std::iter_swap(left, right);
} while (left != right);
if (last - first < 199) {
HoaraSort(first, right);
HoaraSort(left + 1, last);
} else {
oneapi::tbb::parallel_invoke(&first, &right { HoaraSort(first, right); },
&left, &last { HoaraSort(left + 1, last); });
}
}

void deryabin_m_hoare_sort_simple_merge_mpi::MergeUnequalTwoParts(std::vector<double>::iterator first,
std::vector<double>::iterator mid,
std::vector<double>::iterator last) {
const auto left_end = std::upper_bound(first, mid, *mid);
const auto right_start = std::upper_bound(mid, last, (mid - 1));
const size_t overlap_len = std::min(std::distance(left_end, mid), std::distance(mid, right_start));
oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0, overlap_len),
[&left_end, &mid](const oneapi::tbb::blocked_range<size_t>& r) {
for (size_t i = r.begin(); i < r.end(); ++i) {
auto left = left_end + static_cast<long>(i);
auto right = mid + static_cast<long>(i);
if (left > right) {
std::iter_swap(left, right);
}
}
});
size_t right_len = right_start - (mid - 1);
size_t left_len = mid - left_end;
if (right_len > left_len + 1) {
size_t delta = right_len - left_len;
auto base = &(right_start - static_cast<long>(delta));
oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0, left_len),
[&base, delta](const oneapi::tbb::blocked_range<size_t>& r) {
for (size_t j = r.begin(); j < r.end(); ++j) {
double current = base - j;
for (size_t i = 0; i < delta - 1; ++i) {
if (current[i] > current[i + 1]) {
std::swap(current[i], current[i + 1]);
}
}
}
});
}
std::inplace_merge(left_end, mid, right_start);
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskSequential::PreProcessingImpl() {
input_array_A_ = reinterpret_cast<std::vector<double>*>(task_data->inputs[0])[0];
dimension_ = task_data->inputs_count[0];
chunk_count_ = task_data->inputs_count[1];
min_chunk_size_ = dimension_ / chunk_count_;
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskSequential::ValidationImpl() {
return task_data->inputs_count[0] > 2 && task_data->inputs_count[1] >= 2 &&
task_data->inputs_count[0] == task_data->outputs_count[0];
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskSequential::RunImpl() {
size_t count = 0;
while (count != chunk_count_) {
HoaraSort(input_array_A_.begin() + static_cast<long>(count * min_chunk_size_),
input_array_A_.begin() + static_cast<long>((count + 1) * min_chunk_size_) - 1);
count++;
}
size_t chunk_count = chunk_count_;
for (size_t i = 0; i < static_cast<size_t>(std::bit_width(chunk_count_)) - 1; i++) {
for (size_t j = 0; j < chunk_count; j++) {
std::inplace_merge(input_array_A_.begin() + static_cast<long>(j * min_chunk_size_ << (i + 1)),
input_array_A_.begin() + static_cast<long>((j << 1 | 1) * (min_chunk_size_ << i)),
input_array_A_.begin() + static_cast<long>((j + 1) * min_chunk_size_ << (i + 1)));
chunk_count--;
}
}
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskSequential::PostProcessingImpl() {
reinterpret_cast<std::vector<double>*>(task_data->outputs[0])[0] = input_array_A_;
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskMPI::PreProcessingImpl() {
if (world_.rank() == 0) {
input_array_A_ = reinterpret_cast<std::vector<double>*>(task_data->inputs[0])[0];
dimension_ = task_data->inputs_count[0];
chunk_count_ = world_.size();
min_chunk_size_ = dimension_ / chunk_count_;
rest_ = dimension_ % chunk_count_;
}
boost::mpi::broadcast(world_, dimension_, 0);
if (world_.rank() != 0) {
input_array_A_.resize(dimension_);
}
boost::mpi::broadcast(world_, input_array_A_.data(), static_cast<int>(dimension_), 0);
boost::mpi::broadcast(world_, chunk_count_, 0);
boost::mpi::broadcast(world_, min_chunk_size_, 0);
boost::mpi::broadcast(world_, rest_, 0);
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskMPI::ValidationImpl() {
if (world_.rank() == 0) {
return task_data->inputs_count[0] > 2 && task_data->inputs_count[0] == task_data->outputs_count[0];
}
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskMPI::HandleEvenCase(size_t world_rank, size_t step) {
if (world_rank == 0) {
return true;
}
size_t block_size = min_chunk_size_ * step;
size_t start_idx = (chunk_count_ - (world_rank + step)) * min_chunk_size_;
if (world_rank == chunk_count_ - step) {
block_size += rest_;
} else {
start_idx += rest_;
}
if (world_rank >= step) {
world_.send(static_cast<int>(world_rank - step), 0, input_array_A_.data() + start_idx,
static_cast<int>(block_size));
} else {
world_.send(0, 0, input_array_A_.data() + start_idx, static_cast<int>(block_size));
}
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskMPI::HandleOddCase(size_t world_rank, size_t step) {
const bool special_odd_case = (chunk_count_ & 1) != 0U && world_rank == 0;
size_t block_size = min_chunk_size_ * step;
size_t start_idx = special_odd_case ? (chunk_count_ - (2 * step - 1)) * min_chunk_size_
: (chunk_count_ - (world_rank + 2 * step)) * min_chunk_size_;
const size_t recv_rank = special_odd_case ? step - 1 : world_rank + step;
if (recv_rank == chunk_count_ - step) {
block_size += rest_;
} else {
start_idx += rest_;
}
world_.recv(static_cast<int>(recv_rank), 0, input_array_A_.data() + start_idx, static_cast<int>(block_size));
const auto end_idx = special_odd_case
? input_array_A_.end()
: input_array_A_.begin() + static_cast<long>(start_idx + (block_size * 2) - rest_);
if (end_idx - (input_array_A_.begin() + static_cast<long>(start_idx)) < 200) {
std::inplace_merge(input_array_A_.begin() + static_cast<long>(start_idx),
input_array_A_.begin() + static_cast<long>(start_idx + block_size), end_idx);
} else {
MergeUnequalTwoParts(input_array_A_.begin() + static_cast<long>(start_idx),
input_array_A_.begin() + static_cast<long>(start_idx + block_size), end_idx);
}
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskMPI::RunImpl() {
const size_t world_rank = world_.rank();
const auto start_iter =
input_array_A_.begin() + static_cast<long>(((chunk_count_ - world_rank - 1) * min_chunk_size_) +
(world_rank == chunk_count_ - 1 ? 0 : rest_));
const auto end_iter =
input_array_A_.begin() + static_cast<long>(((chunk_count_ - world_rank) * min_chunk_size_) + rest_) - 1;
HoaraSort(start_iter, end_iter);
const size_t iterations = std::bit_width(chunk_count_ - 1);
for (size_t i = 0; i < iterations; ++i) {
const size_t step = 1ULL << i;
if (((chunk_count_ - world_rank) & (step - 1)) == 0U || world_rank == 0) {
const bool is_even = ((chunk_count_ & 1) != 0U) ? (((chunk_count_ - world_rank + step - 1) / step) & 1) != 0U
: (((chunk_count_ - world_rank - 1) / step) & 1) == 0U;
if (is_even) {
HandleEvenCase(world_rank, step);
} else {
HandleOddCase(world_rank, step);
}
}
}
return true;
}

bool deryabin_m_hoare_sort_simple_merge_mpi::HoareSortTaskMPI::PostProcessingImpl() {
if (world_.rank() == 0) {
reinterpret_cast<std::vector<double>*>(task_data->outputs[0])[0] = input_array_A_;
}
return true;
} - 1ая программа, #include <omp.h>

#include <boost/mpi/collectives/broadcast.hpp>
#include <boost/mpi/collectives/scatter.hpp>
#include <climits>
#include <cmath>
#include <core/util/include/util.hpp>
#include <cstdlib>
#include <cstring>
#include <vector>

#include "all/kovalev_k_radix_sort_batcher_merge/include/header.hpp"

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::RadixUnsigned(unsigned long long* inp_arr,
unsigned long long* temp, unsigned int size) {
auto* masc = reinterpret_cast<unsigned char*>(inp_arr);
int count[256];
unsigned int sizetype = sizeof(unsigned long long);
for (unsigned int i = 0; i < sizetype; i++) {
Countbyte(inp_arr, count, i, size);
for (unsigned int j = 0; j < size; j++) {
temp[count[masc[(j * sizetype) + i]]++] = inp_arr[j];
}
memcpy(inp_arr, temp, sizeof(unsigned long long) * size);
}
return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::RadixSigned(unsigned int start, unsigned int size) {
auto* mas = reinterpret_cast<unsigned long long*>(loc_.data() + start);
auto* tmp = reinterpret_cast<unsigned long long*>(loc_tmp_.data() + start);
unsigned int count = 0;
bool ret = RadixUnsigned(mas, tmp, size);

while (count < size && loc_[start + count] >= 0) {
count++;
}
if (count == size) {
return ret;
}
memcpy(tmp, mas + count, sizeof(long long int) * (size - count));
memcpy(tmp + (size - count), mas, sizeof(long long int) * (count));
memcpy(mas, tmp, sizeof(long long int) * size);

return ret;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::Countbyte(unsigned long long* inp_arr, int* count,
unsigned int byte, unsigned int size) {
auto* masc = reinterpret_cast<unsigned char*>(inp_arr);
unsigned int bias = sizeof(unsigned long long);
for (unsigned int i = 0; i < 256; i++) {
count[i] = 0;
}
for (unsigned int i = 0; i < size; i++) {
count[masc[(i * bias) + byte]]++;
}
int tmp1 = count[0];
count[0] = 0;
for (unsigned int i = 1; i < 256; i++) {
int tmp2 = count[i];
count[i] = count[i - 1] + tmp1;
tmp1 = tmp2;
}
return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::OddEvenMergeOMP(long long int* tmp, long long int* l,
const long long int* r, unsigned int len) {
unsigned int iter_l = 0;
unsigned int iter_r = 0;
unsigned int iter_tmp = 0;

while (iter_l < len && iter_r < len) {
if (l[iter_l] < r[iter_r]) {
tmp[iter_tmp] = l[iter_l];
iter_l += 2;
} else {
tmp[iter_tmp] = r[iter_r];
iter_r += 2;
}

iter_tmp += 2;

}

while (iter_l < len) {
tmp[iter_tmp] = l[iter_l];
iter_l += 2;
iter_tmp += 2;
}

while (iter_r < len) {
tmp[iter_tmp] = r[iter_r];
iter_r += 2;
iter_tmp += 2;
}

for (unsigned int i = 0; i < iter_tmp; i += 2) {
l[i] = tmp[i];
}
return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::FinalMergeOMP(unsigned int n) {
unsigned int iter_even = 0;
unsigned int iter_odd = 1;
unsigned int iter_tmp = 0;

while (iter_even < n && iter_odd < n) {
if (loc_[iter_even] < loc_[iter_odd]) {
loc_tmp_[iter_tmp] = loc_[iter_even];
iter_even += 2;
} else {
loc_tmp_[iter_tmp] = loc_[iter_odd];
iter_odd += 2;
}
iter_tmp++;
}

while (iter_even < n) {
loc_tmp_[iter_tmp] = loc_[iter_even];
iter_even += 2;
iter_tmp++;
}

while (iter_odd < n) {
loc_tmp_[iter_tmp] = loc_[iter_odd];
iter_odd += 2;
iter_tmp++;
}
return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::BatcherSortOMP() {
if (static_cast<unsigned int>(ppc::util::GetPPCNumThreads()) > 2 * loc_proc_lenght_) {
bool ret = RadixSigned(0, loc_proc_lenght_);
memcpy(loc_tmp_.data(), loc_.data(), sizeof(long long int) * loc_proc_lenght_);
return ret;
}

unsigned int effective_num_threads =
static_cast<int>(std::pow(2, std::floor(std::log2(ppc::util::GetPPCNumThreads()))));
unsigned int n_by_proc =
loc_proc_lenght_ +
(((2 * effective_num_threads) - (loc_proc_lenght_ % (2 * effective_num_threads))) % (2 * effective_num_threads));
unsigned int loc_lenght = n_by_proc / effective_num_threads;

loc_.resize(n_by_proc);
loc_tmp_.resize(n_by_proc);

for (unsigned int i = loc_proc_lenght_; i < n_by_proc; i++) {
loc_[i] = LLONG_MAX;
}

bool ret1 = true;
bool ret2 = true;
#pragma omp parallel num_threads(effective_num_threads)
{ ret1 = ret1 && RadixSigned(omp_get_thread_num() * loc_lenght, loc_lenght); }

for (unsigned int i = effective_num_threads; i > 1; i /= 2) {
#pragma omp parallel num_threads(i)
{
auto stride = static_cast<unsigned int>(omp_get_thread_num() / 2);
unsigned int bias = omp_get_thread_num() % 2;
unsigned int len = loc_lenght * (effective_num_threads / i);

text
  ret2 =
      ret2 && OddEvenMergeOMP(loc_tmp_.data() + (stride * 2 * len) + bias, loc_.data() + (stride * 2 * len) + bias,
                              loc_.data() + (stride * 2 * len) + len + bias, len - bias);
}

}
FinalMergeOMP(n_by_proc);

void* ptr_tmp1 = loc_tmp_.data();
void* ptr_loc1 = loc_.data();
memcpy(ptr_loc1, ptr_tmp1, sizeof(long long int) * loc_proc_lenght_);

return (ret1 && ret2);
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::ValidationImpl() {
if (world_.rank() == 0) {
if (task_data->inputs.empty() || task_data->outputs.empty() || task_data->inputs_count[0] <= 0 ||
task_data->outputs_count[0] != n_input_ || task_data->inputs_count[0] != task_data->outputs_count[0]) {
return false;
}
}
return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::PreProcessingImpl() {
boost::mpi::broadcast(world_, n_input_, 0);

effective_num_procs_ = static_cast<int>(std::pow(2, std::floor(std::log2(world_.size()))));
auto e_n_f = static_cast<unsigned int>(effective_num_procs_);
n_ = n_input_ + (((2 * e_n_f) - n_input_ % (2 * e_n_f))) % (2 * e_n_f);
loc_proc_lenght_ = n_ / effective_num_procs_;

if (world_.rank() == 0) {
mas_.resize(n_);

text
void* ptr_input = task_data->inputs[0];
void* ptr_vec = mas_.data();
memcpy(ptr_vec, ptr_input, sizeof(long long int) * n_input_);

for (unsigned int i = n_input_; i < n_; i++) {
  mas_[i] = LLONG_MAX;
}

}

loc_.resize(loc_proc_lenght_);
loc_tmp_.resize(loc_proc_lenght_);

return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::RunImpl() {
boost::mpi::scatter(world_, mas_.data(), loc_.data(), static_cast<int>(loc_proc_lenght_), 0);

BatcherSortOMP();

bool ret = true;
for (unsigned int i = effective_num_procs_; i > 1; i /= 2) {
if (world_.rank() < static_cast<int>(i)) {
unsigned int len = loc_proc_lenght_ * (effective_num_procs_ / i);

text
  ret = ret && OddEvenMergeMPI(len);

  if (world_.rank() > 0 && world_.rank() % 2 == 0) {
    world_.send(world_.rank() / 2, 0, loc_tmp_.data(), 2 * static_cast<int>(len));
  }
  if (world_.rank() > 0 && world_.rank() < static_cast<int>(i) / 2) {
    loc_.resize(2 * len);
    world_.recv(world_.rank() * 2, 0, loc_.data(), 2 * static_cast<int>(len));
  } else if (world_.rank() == 0 && static_cast<int>(i) != 2) {
    void* ptr_tmp = loc_tmp_.data();
    void* ptr_loc = loc_.data();
    memcpy(ptr_loc, ptr_tmp, sizeof(long long int) * 2 * len);
  }
}

}

return ret;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::OddEvenMergeMPI(unsigned int len) {
if (world_.rank() % 2 == 0) {
loc_.resize(2 * len);
loc_tmp_.resize(2 * len);

text
world_.recv(world_.rank() + 1, 0, loc_.data() + len, static_cast<int>(len));

unsigned int iter_l = 0;
unsigned int iter_r = 0;
unsigned int iter_tmp = 0;

while (iter_l < len && iter_r < len) {
  if (loc_[iter_l] < loc_[len + iter_r]) {
    loc_tmp_[iter_tmp] = loc_[iter_l];
    iter_l++;
  } else {
    loc_tmp_[iter_tmp] = loc_[len + iter_r];
    iter_r++;
  }
  iter_tmp++;
}

while (iter_l < len) {
  loc_tmp_[iter_tmp] = loc_[iter_l];
  iter_l++;
  iter_tmp++;
}

while (iter_r < len) {
  loc_tmp_[iter_tmp] = loc_[len + iter_r];
  iter_r++;
  iter_tmp++;
}

} else {
world_.send(world_.rank() - 1, 0, loc_.data(), static_cast<int>(len));
}
return true;
}

bool kovalev_k_radix_sort_batcher_merge_all::TestTaskAll::PostProcessingImpl() {
if (world_.rank() == 0) {
void* ptr_output = task_data->outputs[0];
void* ptr_loc = loc_tmp_.data();
memcpy(ptr_output, ptr_loc, sizeof(long long int) * n_input_);
}
return true;
} - 2ая программа, здесь двум людям было дано задание реализовать конкретные сортировки у них не было выбора какую конкретно сортировку выбрать а каждом было дано задание реализовать именно ту версию какую им дали, кто продемонстрировал больше мастерства как программист?