Branch data Line data Source code
1 : : // Copyright 2026 HPActor Contributors
2 : : //
3 : : // Licensed under the Apache License, Version 2.0 (the "License");
4 : : // you may not use this file except in compliance with the License.
5 : : // You may obtain a copy of the License at
6 : : //
7 : : // http://www.apache.org/licenses/LICENSE-2.0
8 : : //
9 : : // Unless required by applicable law or agreed to in writing, software
10 : : // distributed under the License is distributed on an "AS IS" BASIS,
11 : : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : : // See the License for the specific language governing permissions and
13 : : // limitations under the License.
14 : :
15 : : #pragma once
16 : :
17 : : #include <atomic>
18 : : #include <cstdint>
19 : : #include <vector>
20 : :
21 : : namespace hpactor::sched {
22 : :
23 : : // -----------------------------------------------------------------------------
24 : : // A2WS: Adaptive Two-Level Work Stealing
25 : : // -----------------------------------------------------------------------------
26 : : // Implements adaptive work-stealing with two levels:
27 : : // 1. Local level: try workers in same NUMA/pool region first
28 : : // 2. Global level: if local pool is empty, spread to other pools
29 : : //
30 : : // Each worker tracks:
31 : : // - victim_index: current victim suggestion
32 : : // - steal_attempts: number of steal attempts
33 : : // - steal_successes: number of successful steals
34 : : //
35 : : // The adaptive aspect: if a victim consistently fails (empty queue),
36 : : // the thief will switch victims. Success rate determines victim selection.
37 : : // -----------------------------------------------------------------------------
38 : : class A2WS {
39 : : public:
40 : : struct WorkerStats {
41 : : std::atomic<uint64_t> steal_attempts{0};
42 : : std::atomic<uint64_t> steal_successes{0};
43 : : std::atomic<uint64_t> local_steals{0}; // stolen from local pool
44 : : std::atomic<uint64_t> remote_steals{0}; // stolen from remote pool
45 : : };
46 : :
47 : : A2WS() = default;
48 : :
49 : : explicit A2WS(uint32_t num_workers, uint32_t pool_size = 4);
50 : :
51 : : // Get next victim to try stealing from
52 : : // Returns worker index, wraps around via round-robin
53 : : uint32_t get_victim(uint32_t thief_index);
54 : :
55 : : // Record a steal attempt (successful or not)
56 : : void record_attempt(uint32_t thief, uint32_t victim, bool success);
57 : :
58 : : // Record successful steal from victim
59 : : void record_steal(uint32_t thief, uint32_t victim);
60 : :
61 : : // Get victim pool range for a given worker
62 : : // Returns [pool_start, pool_end) exclusive
63 : : void get_victim_pool(uint32_t worker, uint32_t& start, uint32_t& end) const;
64 : :
65 : : // Number of workers
66 : 1 : uint32_t num_workers() const {
67 : 1 : return num_workers_;
68 : : }
69 : :
70 : : // Check if two workers are in the same local pool
71 : : bool same_pool(uint32_t a, uint32_t b) const;
72 : :
73 : : // Stats access
74 : 7 : const WorkerStats& stats(uint32_t worker) const {
75 : 7 : return workers_[worker];
76 : : }
77 : :
78 : : private:
79 : : uint32_t num_workers_;
80 : : uint32_t pool_size_; // workers per local pool
81 : : std::vector<WorkerStats> workers_;
82 : : std::vector<std::atomic<uint32_t>> victim_hints_; // per-thief victim
83 : : // suggestion
84 : : };
85 : :
86 : : } // namespace hpactor::sched
|
