Lines Matching +full:cpu +full:- +full:capacity
2 Capacity Aware Scheduling
5 1. CPU Capacity
9 ----------------
13 different performance characteristics - on such platforms, not all CPUs can be
16 CPU capacity is a measure of the performance a CPU can reach, normalized against
17 the most performant CPU in the system. Heterogeneous systems are also called
18 asymmetric CPU capacity systems, as they contain CPUs of different capacities.
20 Disparity in maximum attainable performance (IOW in maximum CPU capacity) stems
23 - not all CPUs may have the same microarchitecture (µarch).
24 - with Dynamic Voltage and Frequency Scaling (DVFS), not all CPUs may be
28 performance-oriented than the LITTLE ones (more pipeline stages, bigger caches,
32 CPU performance is usually expressed in Millions of Instructions Per Second
36 capacity(cpu) = work_per_hz(cpu) * max_freq(cpu)
39 -------------------
41 Two different capacity values are used within the scheduler. A CPU's
42 ``capacity_orig`` is its maximum attainable capacity, i.e. its maximum
43 attainable performance level. A CPU's ``capacity`` is its ``capacity_orig`` to
47 Note that a CPU's ``capacity`` is solely intended to be used by the CFS class,
48 while ``capacity_orig`` is class-agnostic. The rest of this document will use
49 the term ``capacity`` interchangeably with ``capacity_orig`` for the sake of
53 ---------------------
58 Consider an hypothetical dual-core asymmetric CPU capacity system where
60 - work_per_hz(CPU0) = W
61 - work_per_hz(CPU1) = W/2
62 - all CPUs are running at the same fixed frequency
64 By the above definition of capacity:
66 - capacity(CPU0) = C
67 - capacity(CPU1) = C/2
78 +----+----+----+----+----+----+----+----+----+----+-> time
83 +----+----+----+----+----+----+----+----+----+----+-> time
85 CPU0 has the highest capacity in the system (C), and completes a fixed amount of
86 work W in T units of time. On the other hand, CPU1 has half the capacity of
92 Usually, CPUs of different capacity values also have different maximum
95 - max_freq(CPU0) = F
96 - max_freq(CPU1) = 2/3 * F
100 - capacity(CPU0) = C
101 - capacity(CPU1) = C/3
103 Executing the same workload as described in 1.3.1, which each CPU running at its
109 +----+----+----+----+----+----+----+----+----+----+-> time
115 +----+----+----+----+----+----+----+----+----+----+-> time
118 -------------------------
120 It should be noted that having a *single* value to represent differences in CPU
130 ----------------
132 Capacity aware scheduling requires an expression of a task's requirements with
133 regards to CPU capacity. Each scheduler class can express this differently, and
144 spends more time sleeping than executing. Variable CPU frequencies and
145 asymmetric CPU capacities complexify this somewhat; the following sections will
149 ------------------------
152 directly impacted by the current OPP the CPU is running at. Consider running a
155 CPU work ^
158 +----+----+----+----+----+----+----+----+----+----+-> time
164 CPU work ^
167 +----+----+----+----+----+----+----+----+----+----+-> time
175 task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu))
180 2.3 CPU invariance
181 ------------------
183 CPU capacity has a similar effect on task utilization in that running an
184 identical workload on CPUs of different capacity values will yield different
189 - capacity(CPU0) = C
190 - capacity(CPU1) = C/3
192 Executing a given periodic workload on each CPU at their maximum frequency would
198 +----+----+----+----+----+----+----+----+----+----+-> time
203 +----+----+----+----+----+----+----+----+----+----+-> time
207 - duty_cycle(p) == 25% if p runs on CPU0 at its maximum frequency
208 - duty_cycle(p) == 75% if p runs on CPU1 at its maximum frequency
210 The task utilization signal can be made CPU invariant using the following
213 task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity)
215 with ``max_capacity`` being the highest CPU capacity value in the
216 system. Applying this formula to the above example above yields a CPU
220 ------------------------------
222 Both frequency and CPU invariance need to be applied to task utilization in
223 order to obtain a truly invariant signal. The pseudo-formula for a task
224 utilization that is both CPU and frequency invariant is thus, for a given
227 curr_frequency(cpu) capacity(cpu)
228 task_util_inv(p) = duty_cycle(p) * ------------------- * -------------
229 max_frequency(cpu) max_capacity
232 if it were running on the highest-capacity CPU in the system, running at its
239 --------------------------
243 maintains a handful of CPU and task signals based on the Per-Entity Load
247 This means that while the capacity aware scheduling criteria will be written
251 3. Capacity aware scheduling requirements
254 3.1 CPU capacity
255 ----------------
257 Linux cannot currently figure out CPU capacity on its own, this information thus
262 CPU scaling data, which is derived from the capacity-dmips-mhz CPU binding; see
263 Documentation/devicetree/bindings/arm/cpu-capacity.txt.
266 ------------------------
268 As stated in 2.2, capacity-aware scheduling requires a frequency-invariant task
269 utilization. Architectures must define arch_scale_freq_capacity(cpu) for that
272 Implementing this function requires figuring out at which frequency each CPU
274 whose increment rate scale with a CPU's current frequency (APERF/MPERF on x86,
276 when the kernel is aware of the switched-to frequency (also employed by
283 whether the system exhibits asymmetric CPU capacities. Should that be the
286 - The sched_asym_cpucapacity static key will be enabled.
287 - The SD_ASYM_CPUCAPACITY flag will be set at the lowest sched_domain level that
288 spans all unique CPU capacity values.
291 cater to asymmetric CPU capacity systems. Do note however that said key is
292 *system-wide*. Imagine the following setup using cpusets::
294 capacity C/2 C
303 .. code-block:: sh
306 echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus
310 echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus
315 Since there *is* CPU capacity asymmetry in the system, the
317 hierarchy of CPUs 0-1 spans a single capacity value: SD_ASYM_CPUCAPACITY isn't
321 asymmetric CPU capacities is to:
323 - Check the sched_asym_cpucapacity static key
324 - If it is enabled, then also check for the presence of SD_ASYM_CPUCAPACITY in
326 CPU or group thereof)
328 5. Capacity aware scheduling implementation
332 -------
334 5.1.1 Capacity fitness
337 The main capacity scheduling criterion of CFS is::
339 task_util(p) < capacity(task_cpu(p))
341 This is commonly called the capacity fitness criterion, i.e. CFS must ensure a
342 task "fits" on its CPU. If it is violated, the task will need to achieve more
343 work than what its CPU can provide: it will be CPU-bound.
347 Documentation/admin-guide/cgroup-v2.rst). As its name imply, this can be used to
350 5.1.2 Wakeup CPU selection
353 CFS task wakeup CPU selection follows the capacity fitness criterion described
355 which lets userspace have more leverage over the CPU selection of CFS
356 tasks. IOW, CFS wakeup CPU selection searches for a CPU that satisfies::
358 clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu)
361 on any CPU by giving it a low uclamp.max value. Conversely, it can force a small
362 periodic task (e.g. 10% utilization) to run on the highest-performance CPUs by
367 Wakeup CPU selection in CFS can be eclipsed by Energy Aware Scheduling
368 (EAS), which is described in Documentation/scheduler/sched-energy.rst.
373 A pathological case in the wakeup CPU selection occurs when a task rarely
374 sleeps, if at all - it thus rarely wakes up, if at all. Consider::
378 capacity(CPU0) = C
379 capacity(CPU1) = C / 3
382 CPU work ^
385 +----+----+----+----+----+----+----+----+----+----+-> time
389 CPU work ^
392 +----+----+----+----+----+----+----+----+----+----+->
397 - was improperly scheduled from the start (inaccurate initial
399 - was properly scheduled from the start, but suddenly needs more
402 then it might become CPU-bound, IOW ``task_util(p) > capacity(task_cpu(p))``;
403 the CPU capacity scheduling criterion is violated, and there may not be any more
404 wakeup event to fix this up via wakeup CPU selection.
411 to a CPU with more capacity than its current one.
414 ------
416 5.2.1 Wakeup CPU selection
419 RT task wakeup CPU selection searches for a CPU that satisfies::
421 task_uclamp_min(p) <= capacity(task_cpu(cpu))
424 CPUs can satisfy this capacity criterion, then strict priority based scheduling
425 is followed and CPU capacities are ignored.
428 ------
430 5.3.1 Wakeup CPU selection
433 DL task wakeup CPU selection searches for a CPU that satisfies::
435 task_bandwidth(p) < capacity(task_cpu(p))
438 none of the candidate CPUs can satisfy this capacity criterion, then the
439 task will remain on its current CPU.