03-29-2019, 08:11 PM
Can Better Task Stealing Make Linux Faster?
<div style="margin: 5px 5% 10px 5%;"><img src="http://www.sickgaming.net/blog/wp-content/uploads/2019/03/can-better-task-stealing-make-linux-faster.png" width="624" height="202" title="" alt="" /></div><div><p><em>Oracle Linux kernel developer Steve Sistare contributes this discussion on kernel scheduler improvements.</em></p>
<h2 class="selectionShareable">Load balancing via scalable task stealing</h2>
<p class="selectionShareable">The Linux task scheduler balances load across a system by pushing waking tasks to idle CPUs, and by pulling tasks from busy CPUs when a CPU becomes idle. Efficient scaling is a challenge on both the push and pull sides on large systems. For pulls, the scheduler searches all CPUs in successively larger domains until an overloaded CPU is found, and pulls a task from the busiest group. This is very expensive, costing 10’s to 100’s of microseconds on large systems, so search time is limited by the average idle time, and some domains are not searched. Balance is not always achieved, and idle CPUs go unused.</p>
<p class="selectionShareable">I have implemented an alternate mechanism that is invoked after the existing search in idle_balance() limits itself and finds nothing. I maintain a bitmap of overloaded CPUs, where a CPU sets its bit when its runnable CFS task count exceeds 1. The bitmap is sparse, with a limited number of significant bits per cacheline. This reduces cache contention when many threads concurrently set, clear, and visit elements. There is a bitmap per last-level cache. When a CPU becomes idle, it searches the bitmap to find the first overloaded CPU with a migratable task, and steals it. This simple stealing yields a higher CPU utilization than idle_balance() alone, because the search is cheap, costing 1 to 2 microseconds, so it may be called every time the CPU is about to go idle. Stealing does not offload the globally busiest queue, but it is much better than running nothing at all.</p>
<h2 class="selectionShareable">Results</h2>
<p class="selectionShareable">Stealing improves utilization with only a modest CPU overhead in scheduler code. In the following experiment, hackbench is run with varying numbers of groups (40 tasks per group), and the delta in /proc/schedstat is shown for each run, averaged per CPU, augmented with these non-standard stats:</p>
<ul>
<li>%find – percent of time spent in old and new functions that search for idle CPUs and tasks to steal and set the overloaded CPUs bitmap.</li>
<li>steal – number of times a task is stolen from another CPU. Elapsed time improves by 8 to 36%, costing at most 0.4% more find time. </li>
</ul>
<p>CPU busy utilization is close to 100% for the new kernel, as shown by the green curve in the following graph, versus the orange curve for the baseline kernel:</p>
<p class="selectionShareable"><img alt src="http://www.sickgaming.net/blog/wp-content/uploads/2019/03/can-better-task-stealing-make-linux-faster.png"></p>
<p class="selectionShareable">Stealing improves Oracle database OLTP performance by up to 9% depending on load, and we have seen some nice improvements for mysql, pgsql, gcc, java, and networking. In general, stealing is most helpful for workloads with a high context switch rate.</p>
<h2 class="selectionShareable">The code</h2>
<p class="selectionShareable">As of this writing, this work is not yet upstream, but the latest patch series is at <a href="https://lkml.org/lkml/2018/12/6/1253">https://lkml.org/lkml/2018/12/6/1253. </a>If your kernel is built with CONFIG_SCHED_DEBUG=y, you can verify that it contains the stealing optimization using</p>
<pre>
<code> # grep -q STEAL /sys/kernel/debug/sched_features && echo Yes Yes
</code></pre>
<p class="selectionShareable">If you try it, note that stealing is disabled for systems with more than 2 NUMA nodes, because hackbench regresses on such systems, as I explain in <a href="https://lkml.org/lkml/2018/12/6/1250">https://lkml.org/lkml/2018/12/6/1250 .</a>However, I suspect this effect is specific to hackbench and that stealing will help other workloads on many-node systems. To try it, reboot with kernel parameter sched_steal_node_limit = 8 (or larger).</p>
<h2 class="selectionShareable">Future work</h2>
<p class="selectionShareable">After the basic stealing algorithm is pushed upstream, I am considering the following enhancements:</p>
<ul>
<li>If stealing within the last-level cache does not find a candidate, steal across LLC’s and NUMA nodes.</li>
<li>Maintain a sparse bitmap to identify stealing candidates in the RT scheduling class. Currently pull_rt_task() searches all run queues.</li>
<li>Remove the core and socket levels from idle_balance(), as stealing handles those levels. Remove idle_balance() entirely when stealing across LLC is supported.</li>
<li>Maintain a bitmap to identify idle cores and idle CPUs, for push balancing.</li>
</ul>
<p><em>This article originally appeared at <a href="https://blogs.oracle.com/linux/can-better-task-stealing-make-linux-faster">Oracle Developers Blog</a>.</em></p>
</div>
<div style="margin: 5px 5% 10px 5%;"><img src="http://www.sickgaming.net/blog/wp-content/uploads/2019/03/can-better-task-stealing-make-linux-faster.png" width="624" height="202" title="" alt="" /></div><div><p><em>Oracle Linux kernel developer Steve Sistare contributes this discussion on kernel scheduler improvements.</em></p>
<h2 class="selectionShareable">Load balancing via scalable task stealing</h2>
<p class="selectionShareable">The Linux task scheduler balances load across a system by pushing waking tasks to idle CPUs, and by pulling tasks from busy CPUs when a CPU becomes idle. Efficient scaling is a challenge on both the push and pull sides on large systems. For pulls, the scheduler searches all CPUs in successively larger domains until an overloaded CPU is found, and pulls a task from the busiest group. This is very expensive, costing 10’s to 100’s of microseconds on large systems, so search time is limited by the average idle time, and some domains are not searched. Balance is not always achieved, and idle CPUs go unused.</p>
<p class="selectionShareable">I have implemented an alternate mechanism that is invoked after the existing search in idle_balance() limits itself and finds nothing. I maintain a bitmap of overloaded CPUs, where a CPU sets its bit when its runnable CFS task count exceeds 1. The bitmap is sparse, with a limited number of significant bits per cacheline. This reduces cache contention when many threads concurrently set, clear, and visit elements. There is a bitmap per last-level cache. When a CPU becomes idle, it searches the bitmap to find the first overloaded CPU with a migratable task, and steals it. This simple stealing yields a higher CPU utilization than idle_balance() alone, because the search is cheap, costing 1 to 2 microseconds, so it may be called every time the CPU is about to go idle. Stealing does not offload the globally busiest queue, but it is much better than running nothing at all.</p>
<h2 class="selectionShareable">Results</h2>
<p class="selectionShareable">Stealing improves utilization with only a modest CPU overhead in scheduler code. In the following experiment, hackbench is run with varying numbers of groups (40 tasks per group), and the delta in /proc/schedstat is shown for each run, averaged per CPU, augmented with these non-standard stats:</p>
<ul>
<li>%find – percent of time spent in old and new functions that search for idle CPUs and tasks to steal and set the overloaded CPUs bitmap.</li>
<li>steal – number of times a task is stolen from another CPU. Elapsed time improves by 8 to 36%, costing at most 0.4% more find time. </li>
</ul>
<p>CPU busy utilization is close to 100% for the new kernel, as shown by the green curve in the following graph, versus the orange curve for the baseline kernel:</p>
<p class="selectionShareable"><img alt src="http://www.sickgaming.net/blog/wp-content/uploads/2019/03/can-better-task-stealing-make-linux-faster.png"></p>
<p class="selectionShareable">Stealing improves Oracle database OLTP performance by up to 9% depending on load, and we have seen some nice improvements for mysql, pgsql, gcc, java, and networking. In general, stealing is most helpful for workloads with a high context switch rate.</p>
<h2 class="selectionShareable">The code</h2>
<p class="selectionShareable">As of this writing, this work is not yet upstream, but the latest patch series is at <a href="https://lkml.org/lkml/2018/12/6/1253">https://lkml.org/lkml/2018/12/6/1253. </a>If your kernel is built with CONFIG_SCHED_DEBUG=y, you can verify that it contains the stealing optimization using</p>
<pre>
<code> # grep -q STEAL /sys/kernel/debug/sched_features && echo Yes Yes
</code></pre>
<p class="selectionShareable">If you try it, note that stealing is disabled for systems with more than 2 NUMA nodes, because hackbench regresses on such systems, as I explain in <a href="https://lkml.org/lkml/2018/12/6/1250">https://lkml.org/lkml/2018/12/6/1250 .</a>However, I suspect this effect is specific to hackbench and that stealing will help other workloads on many-node systems. To try it, reboot with kernel parameter sched_steal_node_limit = 8 (or larger).</p>
<h2 class="selectionShareable">Future work</h2>
<p class="selectionShareable">After the basic stealing algorithm is pushed upstream, I am considering the following enhancements:</p>
<ul>
<li>If stealing within the last-level cache does not find a candidate, steal across LLC’s and NUMA nodes.</li>
<li>Maintain a sparse bitmap to identify stealing candidates in the RT scheduling class. Currently pull_rt_task() searches all run queues.</li>
<li>Remove the core and socket levels from idle_balance(), as stealing handles those levels. Remove idle_balance() entirely when stealing across LLC is supported.</li>
<li>Maintain a bitmap to identify idle cores and idle CPUs, for push balancing.</li>
</ul>
<p><em>This article originally appeared at <a href="https://blogs.oracle.com/linux/can-better-task-stealing-make-linux-faster">Oracle Developers Blog</a>.</em></p>
</div>