Lab2-AdjDiff1/adjdiff.cpp at main · zlat1x/Lab2-AdjDiff1 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include "adjdiff.h"
#include <cmath>

namespace proj2::adjdiff {
    static volatile long double g_sink_value = 0.0L;

    template <class F>
    static double measure_ms(F&& f) {
        using clock = std::chrono::high_resolution_clock;
        auto t0 = clock::now();
        long double v = static_cast<long double>(f());
        auto t1 = clock::now();
        g_sink_value += v;
        std::chrono::duration<double, std::milli> dt = t1 - t0;
        return dt.count();
    }

    std::vector<value_t> make_random(std::size_t n, unsigned long long seed) {
        std::mt19937_64 rng = (seed == 0) ? std::mt19937_64(std::random_device{}())
                                          : std::mt19937_64(seed);
        std::vector<value_t> a(n);

        std::uniform_int_distribution<long long> dist(
            std::numeric_limits<long long>::min() / 4,
            std::numeric_limits<long long>::max() / 4
        );
        for (std::size_t i = 0; i < n; ++i) a[i] = static_cast<value_t>(dist(rng));
        return a;
    }

    static inline long double abs_diff_ll(value_t x, value_t y) {
        long double dx = static_cast<long double>(x);
        long double dy = static_cast<long double>(y);
        long double d = dy - dx;
        return (d < 0) ? -d : d;
    }

    long double max_adjacent_abs_diff_seq(const std::vector<value_t>& a) {
        if (a.size() < 2) return 0.0L;

        std::vector<long double> tmp(a.size());
        std::transform(a.begin(), a.end(), tmp.begin(),
                       [](value_t v){ return static_cast<long double>(v); });

        std::vector<long double> diffs(a.size());
        std::adjacent_difference(tmp.begin(), tmp.end(), diffs.begin());

        long double m = 0.0L;
        for (std::size_t i = 1; i < diffs.size(); ++i) {
            long double v = std::fabsl(diffs[i]);
            if (v > m) m = v;
        }
        return m;
    }

    template <class ExecPolicy>
    static long double max_adjacent_abs_diff_policy_impl(ExecPolicy&& policy, const std::vector<value_t>& a) {
        if (a.size() < 2) return 0.0L;

        auto red = [](long double x, long double y){ return (x > y) ? x : y; };
        auto tr = [](value_t x, value_t y){ return abs_diff_ll(x, y); };

        return std::transform_reduce(policy,
                                     a.begin(), a.end() - 1,
                                     a.begin() + 1,
                                     0.0L, red, tr);
    }

    long double max_adjacent_abs_diff_policy_seq(const std::vector<value_t>& a) {
        return max_adjacent_abs_diff_policy_impl(std::execution::seq, a);
    }
    long double max_adjacent_abs_diff_policy_par(const std::vector<value_t>& a) {
        return max_adjacent_abs_diff_policy_impl(std::execution::par, a);
    }
    long double max_adjacent_abs_diff_policy_unseq(const std::vector<value_t>& a) {
        return max_adjacent_abs_diff_policy_impl(std::execution::unseq, a);
    }
    long double max_adjacent_abs_diff_policy_par_unseq(const std::vector<value_t>& a) {
        return max_adjacent_abs_diff_policy_impl(std::execution::par_unseq, a);
    }

    long double max_adjacent_abs_diff_parallel_k(const std::vector<value_t>& a, int K) {
        if (a.size() < 2 || K <= 0) return 0.0L;

        const std::size_t pairs = a.size() - 1;

        const std::size_t base = pairs / static_cast<std::size_t>(K);
        const std::size_t rem  = pairs % static_cast<std::size_t>(K);

        std::vector<long double> local(static_cast<std::size_t>(K), 0.0L);
        std::vector<std::thread> threads;
        threads.reserve(static_cast<std::size_t>(K));

        std::size_t start_pair = 0;
        for (int t = 0; t < K; ++t) {
            const std::size_t take = base + (static_cast<std::size_t>(t) < rem ? 1u : 0u);
            const std::size_t end_pair = (take == 0) ? start_pair : (start_pair + take - 1);

            threads.emplace_back([&, t, start_pair, end_pair, take] {
                if (take == 0) { local[static_cast<std::size_t>(t)] = 0.0L; return; }

                std::vector<long double> diffs(take);

                std::transform(std::next(a.begin(), static_cast<std::ptrdiff_t>(start_pair)),
                               std::next(a.begin(), static_cast<std::ptrdiff_t>(start_pair + take)),
                               std::next(a.begin(), static_cast<std::ptrdiff_t>(start_pair + 1)),
                               diffs.begin(),
                               [](value_t x, value_t y){ return abs_diff_ll(x, y); });

                auto it = std::max_element(diffs.begin(), diffs.end());
                local[static_cast<std::size_t>(t)] = (it == diffs.end()) ? 0.0L : *it;
            });

            start_pair += take;
        }
        for (auto& th : threads) th.join();

        auto it = std::max_element(local.begin(), local.end());
        return (it == local.end()) ? 0.0L : *it;
    }

    std::vector<result_per_size> run_experiments(std::vector<std::size_t> sizes,
                                                 unsigned long long seed,
                                                 int k_max,
                                                 int repeats) {
        if (sizes.empty()) return {};
        if (k_max <= 0) {
            unsigned hc = std::thread::hardware_concurrency();
            if (hc == 0) hc = 8;
            k_max = static_cast<int>(hc * 2);
        }

        std::vector<result_per_size> results;
        results.reserve(sizes.size());

        for (std::size_t n : sizes) {
            std::cout << "\n=== N = " << n << " ===\n";

            auto a = make_random(n, seed);

            double t_lib = measure_ms([&]{ return max_adjacent_abs_diff_seq(a); });
            std::cout << "[lib no policy]  adjacent_difference -> " << t_lib << " ms\n";

            double t_seq = measure_ms([&]{ return max_adjacent_abs_diff_policy_seq(a); });
            double t_par = measure_ms([&]{ return max_adjacent_abs_diff_policy_par(a); });
            double t_unq = measure_ms([&]{ return max_adjacent_abs_diff_policy_unseq(a); });
            double t_pu  = measure_ms([&]{ return max_adjacent_abs_diff_policy_par_unseq(a); });

            std::cout << "[policy seq]     transform_reduce -> " << t_seq << " ms\n";
            std::cout << "[policy par]     transform_reduce -> " << t_par << " ms\n";
            std::cout << "[policy unseq]   transform_reduce -> " << t_unq << " ms\n";
            std::cout << "[policy par_unseq] transform_reduce -> " << t_pu << " ms\n\n";

            long double check = max_adjacent_abs_diff_seq(a);

            std::cout << "K\tms\n";
            int best_k = 1;
            double best_ms = std::numeric_limits<double>::infinity();
            for (int k = 1; k <= k_max; ++k) {
                double sum = 0.0;
                for (int r = 0; r < repeats; ++r) {
                    sum += measure_ms([&]{ return max_adjacent_abs_diff_parallel_k(a, k); });
                }
                double avg = sum / static_cast<double>(repeats);
                std::cout << k << "\t" << avg << "\n";
                if (avg < best_ms) { best_ms = avg; best_k = k; }
            }

            std::cout << "-> best K = " << best_k
                      << " ( " << best_ms << " ms ) "
                      << " vs hardware_concurrency = "
                      << std::thread::hardware_concurrency() << "\n\n";

            results.push_back(result_per_size{n, best_k, best_ms, check});
        }

        return results;
    }

}