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 ``original capacity`` is its maximum attainable capacity, i.e. its maximum
43 attainable performance level. This original capacity is returned by
44 the function arch_scale_cpu_capacity(). A CPU's ``capacity`` is its ``original
45 capacity`` to which some loss of available performance (e.g. time spent
48 Note that a CPU's ``capacity`` is solely intended to be used by the CFS class,
49 while ``original capacity`` is class-agnostic. The rest of this document will use
50 the term ``capacity`` interchangeably with ``original capacity`` for the sake of
54 ---------------------
59 Consider an hypothetical dual-core asymmetric CPU capacity system where
61 - work_per_hz(CPU0) = W
62 - work_per_hz(CPU1) = W/2
63 - all CPUs are running at the same fixed frequency
65 By the above definition of capacity:
67 - capacity(CPU0) = C
68 - capacity(CPU1) = C/2
79 +----+----+----+----+----+----+----+----+----+----+-> time
84 +----+----+----+----+----+----+----+----+----+----+-> time
86 CPU0 has the highest capacity in the system (C), and completes a fixed amount of
87 work W in T units of time. On the other hand, CPU1 has half the capacity of
93 Usually, CPUs of different capacity values also have different maximum
96 - max_freq(CPU0) = F
97 - max_freq(CPU1) = 2/3 * F
101 - capacity(CPU0) = C
102 - capacity(CPU1) = C/3
104 Executing the same workload as described in 1.3.1, which each CPU running at its
110 +----+----+----+----+----+----+----+----+----+----+-> time
116 +----+----+----+----+----+----+----+----+----+----+-> time
119 -------------------------
121 It should be noted that having a *single* value to represent differences in CPU
131 ----------------
133 Capacity aware scheduling requires an expression of a task's requirements with
134 regards to CPU capacity. Each scheduler class can express this differently, and
145 spends more time sleeping than executing. Variable CPU frequencies and
146 asymmetric CPU capacities complexify this somewhat; the following sections will
150 ------------------------
153 directly impacted by the current OPP the CPU is running at. Consider running a
156 CPU work ^
159 +----+----+----+----+----+----+----+----+----+----+-> time
165 CPU work ^
168 +----+----+----+----+----+----+----+----+----+----+-> time
176 task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu))
181 2.3 CPU invariance
182 ------------------
184 CPU capacity has a similar effect on task utilization in that running an
185 identical workload on CPUs of different capacity values will yield different
190 - capacity(CPU0) = C
191 - capacity(CPU1) = C/3
193 Executing a given periodic workload on each CPU at their maximum frequency would
199 +----+----+----+----+----+----+----+----+----+----+-> time
204 +----+----+----+----+----+----+----+----+----+----+-> time
208 - duty_cycle(p) == 25% if p runs on CPU0 at its maximum frequency
209 - duty_cycle(p) == 75% if p runs on CPU1 at its maximum frequency
211 The task utilization signal can be made CPU invariant using the following
214 task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity)
216 with ``max_capacity`` being the highest CPU capacity value in the
217 system. Applying this formula to the above example above yields a CPU
221 ------------------------------
223 Both frequency and CPU invariance need to be applied to task utilization in
224 order to obtain a truly invariant signal. The pseudo-formula for a task
225 utilization that is both CPU and frequency invariant is thus, for a given
228 curr_frequency(cpu) capacity(cpu)
229 task_util_inv(p) = duty_cycle(p) * ------------------- * -------------
230 max_frequency(cpu) max_capacity
233 if it were running on the highest-capacity CPU in the system, running at its
240 --------------------------
244 maintains a handful of CPU and task signals based on the Per-Entity Load
248 This means that while the capacity aware scheduling criteria will be written
252 3. Capacity aware scheduling requirements
255 3.1 CPU capacity
256 ----------------
258 Linux cannot currently figure out CPU capacity on its own, this information thus
262 The arm, arm64, and RISC-V architectures directly map this to the arch_topology driver
263 CPU scaling data, which is derived from the capacity-dmips-mhz CPU binding; see
264 Documentation/devicetree/bindings/cpu/cpu-capacity.txt.
267 ------------------------
269 As stated in 2.2, capacity-aware scheduling requires a frequency-invariant task
270 utilization. Architectures must define arch_scale_freq_capacity(cpu) for that
273 Implementing this function requires figuring out at which frequency each CPU
275 whose increment rate scale with a CPU's current frequency (APERF/MPERF on x86,
277 when the kernel is aware of the switched-to frequency (also employed by
284 whether the system exhibits asymmetric CPU capacities. Should that be the
287 - The sched_asym_cpucapacity static key will be enabled.
288 - The SD_ASYM_CPUCAPACITY_FULL flag will be set at the lowest sched_domain
289 level that spans all unique CPU capacity values.
290 - The SD_ASYM_CPUCAPACITY flag will be set for any sched_domain that spans
294 cater to asymmetric CPU capacity systems. Do note however that said key is
295 *system-wide*. Imagine the following setup using cpusets::
297 capacity C/2 C
306 .. code-block:: sh
309 echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus
313 echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus
318 Since there *is* CPU capacity asymmetry in the system, the
320 hierarchy of CPUs 0-1 spans a single capacity value: SD_ASYM_CPUCAPACITY isn't
324 asymmetric CPU capacities is to:
326 - Check the sched_asym_cpucapacity static key
327 - If it is enabled, then also check for the presence of SD_ASYM_CPUCAPACITY in
329 CPU or group thereof)
331 5. Capacity aware scheduling implementation
335 -------
337 5.1.1 Capacity fitness
340 The main capacity scheduling criterion of CFS is::
342 task_util(p) < capacity(task_cpu(p))
344 This is commonly called the capacity fitness criterion, i.e. CFS must ensure a
345 task "fits" on its CPU. If it is violated, the task will need to achieve more
346 work than what its CPU can provide: it will be CPU-bound.
350 Documentation/admin-guide/cgroup-v2.rst). As its name imply, this can be used to
353 5.1.2 Wakeup CPU selection
356 CFS task wakeup CPU selection follows the capacity fitness criterion described
358 which lets userspace have more leverage over the CPU selection of CFS
359 tasks. IOW, CFS wakeup CPU selection searches for a CPU that satisfies::
361 clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu)
364 on any CPU by giving it a low uclamp.max value. Conversely, it can force a small
365 periodic task (e.g. 10% utilization) to run on the highest-performance CPUs by
370 Wakeup CPU selection in CFS can be eclipsed by Energy Aware Scheduling
371 (EAS), which is described in Documentation/scheduler/sched-energy.rst.
376 A pathological case in the wakeup CPU selection occurs when a task rarely
377 sleeps, if at all - it thus rarely wakes up, if at all. Consider::
381 capacity(CPU0) = C
382 capacity(CPU1) = C / 3
385 CPU work ^
388 +----+----+----+----+----+----+----+----+----+----+-> time
392 CPU work ^
395 +----+----+----+----+----+----+----+----+----+----+->
400 - was improperly scheduled from the start (inaccurate initial
402 - was properly scheduled from the start, but suddenly needs more
405 then it might become CPU-bound, IOW ``task_util(p) > capacity(task_cpu(p))``;
406 the CPU capacity scheduling criterion is violated, and there may not be any more
407 wakeup event to fix this up via wakeup CPU selection.
414 to a CPU with more capacity than its current one.
417 ------
419 5.2.1 Wakeup CPU selection
422 RT task wakeup CPU selection searches for a CPU that satisfies::
424 task_uclamp_min(p) <= capacity(task_cpu(cpu))
427 CPUs can satisfy this capacity criterion, then strict priority based scheduling
428 is followed and CPU capacities are ignored.
431 ------
433 5.3.1 Wakeup CPU selection
436 DL task wakeup CPU selection searches for a CPU that satisfies::
438 task_bandwidth(p) < capacity(task_cpu(p))
441 none of the candidate CPUs can satisfy this capacity criterion, then the
442 task will remain on its current CPU.