Bare-Metal Multicore Performance in a General-Purpose Operating System

A constant refrain over the decades from database, high-performance computing (HPC), and real-time developers has been: "Can't you just get the kernel out of the way?". Recent developments in the Linux kernel are paving the way to just that ideal: Linux is there whenever you need it, but if you follow a few simple rules, it is completely out of your way when you don't need it.

This adaptive-idle approach will provide bare-metal multicore performance and scalability to databases as well as to HPC and real-time applications. However, it is at the same time able to improve energy efficiency for upcoming asymmetric multicore systems, allowing these systems to better support workloads with extreme peak-to-mean utilization ratios. This talk will describe how this feat is accomplished and how it may best be used.

Transcript

1. © 2012 IBM Corporation Bare-Metal Multicore Performance in a General-Purpose Operating System Paul E. McKenney, IBM Distinguished Engineer, Linux Technology Center Member, IBM Academy of Technology Multicore World 2013, Wellington, New Zealand October 19, 2012
2. © 2009 IBM Corporation 2 Multicore World 2013 Group Effort: Acknowledgments Josh Triplett: First prototype (LPC 2009) Frederic Weisbecker: Core kernel work and x86 port Steven Rostedt: Lots of code review and comments Li Zhong: Power port Geoff Levand, Kevin Hilman: ARM port Paul E. McKenney: Read-copy update (RCU) work Thomas Gleixner, Paul E. McKenney: “Godfathers”
3. © 2009 IBM Corporation 3 Multicore World 2013 What Do Database, HPC, and RT Developers Want?
4. © 2009 IBM Corporation 4 Multicore World 2013 What Do Database, HPC, and RT Developers Want? Get The #@#$#*!!! Kernel Out Of Our #@#$#*!!! Way!!!
5. © 2009 IBM Corporation 5 Multicore World 2013 What Do Database, HPC, and RT Developers Want? But we need device drivers. Get The #@#$#*!!! Kernel Out Of Our #@#$#*!!! Way!!!
6. © 2009 IBM Corporation 6 Multicore World 2013 What Do Database, HPC, and RT Developers Want? But we need device drivers. And file systems. Get The #@#$#*!!! Kernel Out Of Our #@#$#*!!! Way!!!
7. © 2009 IBM Corporation 7 Multicore World 2013 What Do Database, HPC, and RT Developers Want? But we need device drivers. And file systems. And memory protection. Get The #@#$#*!!! Kernel Out Of Our #@#$#*!!! Way!!!
8. © 2009 IBM Corporation 8 Multicore World 2013 What Do Database, HPC, and RT Developers Want? But we need device drivers. And file systems. And memory protection. And... Get The #@#$#*!!! Kernel Out Of Our #@#$#*!!! Way!!!
9. © 2009 IBM Corporation 9 Multicore World 2013 So What Are Us Poor Kernel Developers To Do???
10. © 2009 IBM Corporation 10 Multicore World 2013 So What Are Us Poor Kernel Developers To Do??? For almost 20 years, my response was “Yeah, right, you really do want the whole kernel, just admit it already!!!”
11. © 2009 IBM Corporation 11 Multicore World 2013 So What Are Us Poor Kernel Developers To Do??? For almost 20 years, my response was “Yeah, right, you really do want the whole kernel, just admit it already!!!” My first clue to a third way was Linux's dyntick-idle system –(Used in battery-powered systems for years prior to Linux's use.)
12. © 2009 IBM Corporation 12 Multicore World 2013 Before Linux's dyntick-idle System CPU 1 CPU 0 Scheduling-Clock Interrupts Busy Period Ends But CPU Remains in High-Power State
13. © 2009 IBM Corporation 13 Multicore World 2013 Scheduling-Clock Interrupts Really Optional??? Scheduling-clock interrupt purpose: –Check for other work from time to time –Prevent a given process from monopolizing the CPU But if the CPU is idle, there is nothing for it to do anyway!!! Copyright © 2013 Melissa Broussard, CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0/us/)
14. © 2009 IBM Corporation 14 Multicore World 2013 Linux's dyntick-idle System CPU 1 CPU 0 Scheduling-Clock Interrupts Enter Dyntick-Idle Mode At End Of Busy Period Dyntick-Idle Mode Enables CPU Deep-Sleep States Very Good For Energy Efficiency!!!
15. © 2009 IBM Corporation 15 Multicore World 2013 Linux Kernel Is Now Out Of The Idle Loop's Way...
16. © 2009 IBM Corporation 16 Multicore World 2013 Linux Kernel Is Now Out Of The Idle Loop's Way... So Can We Get It Out Of The Application's Way?
17. © 2009 IBM Corporation 17 Multicore World 2013 Is The Kernel Being In The Way Really A Problem?
18. © 2009 IBM Corporation 18 Multicore World 2013 Is The Kernel Being In The Way Really A Problem? For aggressive real-time workloads, scheduling clock tick does add measurable latency –Some insane people really are getting sub-20-microsecond real-time interrupt latencies out of the Linux kernel... –And I strongly believe in encouraging that sort of insanity!!!
19. © 2009 IBM Corporation 19 Multicore World 2013 Is The Kernel Being In The Way Really A Problem? For aggressive real-time workloads, scheduling clock tick does add measurable latency –Some insane people really are getting sub-20-microsecond real-time interrupt latencies out of the Linux kernel... –And I strongly believe in encouraging that sort of insanity!!! Some HPC workloads are sensitive to “OS jitter” –Especially iterative workloads with short iterations
20. © 2009 IBM Corporation 20 Multicore World 2013 Iterative Workloads With Short Iterations: Ideal Time CPU 0 CPU 1 CPU 2 CPU 3 CPU 4 CPU 5 CPU 6 CPU 7 Work Barrier
21. © 2009 IBM Corporation 21 Multicore World 2013 Iterative Workloads With Short Iterations: OS Jitter Time CPU 0 CPU 1 CPU 2 CPU 3 CPU 4 CPU 5 CPU 6 CPU 7 Work Barrier OS Jitter OS Jitter Multiplied!!!
22. © 2009 IBM Corporation 22 Multicore World 2013 Now Try This With 800,000 CPUs In A Cluster... Time CPU 0 CPU 1 CPU 2 CPU 3 CPU 4 CPU 5 CPU 6 CPU 7 Work Barrier OS Jitter OS Jitter Multiplied!!!
23. © 2009 IBM Corporation 23 Multicore World 2013 Yes, This Is A Real Problem For Some Workloads
24. © 2009 IBM Corporation 24 Multicore World 2013 Linux Kernel Is Now Out Of The Idle Loop's Way... So Can We Get It Out Of The Application's Way?
25. © 2009 IBM Corporation 25 Multicore World 2013 Josh Triplett's First Prototype, 2009 Always turn off scheduling-clock interrupt for user code Good demonstration of feasibility and benefit –2009 Linux Plumbers Conference presentation –http://linuxplumbersconf.org/ocw/proposals/103 –See next two slides for performance comparison
26. © 2009 IBM Corporation 26 Multicore World 2013 Benchmark Results Before (Anton Blanchard)
27. © 2009 IBM Corporation 27 Multicore World 2013 Benchmark Results After (Anton Blanchard) Well worth going after...
28. © 2009 IBM Corporation 28 Multicore World 2013 But There Were A Few Small Drawbacks... No process accounting User applications can monopolize CPU RCU grace periods go forever, running system out of memory –More on this later
29. © 2009 IBM Corporation 29 Multicore World 2013 Can We Do Something About The Drawbacks? (Discussion at 2010 Linux Plumbers Conference)  User applications can monopolize CPU – But if there is only one runnable task, so what???
30. © 2009 IBM Corporation 30 Multicore World 2013 So Another Look At The Drawbacks... (Discussion at 2010 Linux Plumbers Conference)  User applications can monopolize CPU – But if there is only one runnable task, so what??? – If new task awakens, interrupt the CPU, restart scheduling-clock interrrupts – In the meantime, we have an “adaptive idle usermode” CPU  No process accounting – Use delta-based accounting, based on when process started running – One CPU retains scheduling-clock interrupts for timekeeping purposes  RCU grace periods go forever, running system out of memory – Inform RCU of adaptive-idle usermode execution so that it ignores adaptive- idle user-mode CPUs, similar to its handling of dyntick-idle CPUs  Frederic Weisbecker took on this task (for x86-64) – Geoff Levand and Kevin Hilman: Port to ARM – Li Zhong: Port to PowerPC – I was able to provide a bit of help with RCU
31. © 2009 IBM Corporation 31 Multicore World 2013 How Well Does It Work?
32. © 2009 IBM Corporation 32 Multicore World 2013 How Well Does It Work? Preliminary results look good
33. © 2009 IBM Corporation 33 Multicore World 2013 How Well Does It Work? Big Kernel Idle Usermode Small Kernel Usermode Scheduling clock interrupts Big Kernel Idle Usermode Small Kernel Usermode Adaptive Ticks Extra scheduling clock interrupts due to RCU callbacks Second task awakens One task per CPU
34. © 2009 IBM Corporation 34 Multicore World 2013 Other Than RCU, Looks Great!!! Need to fix RCU But first, what is RCU?
35. © 2009 IBM Corporation 35 Multicore World 2013 What Is RCU?
36. © 2009 IBM Corporation 36 Multicore World 2013 What Is RCU? (AKA Read-Copy Update) For an overview, see http://lwn.net/Articles/262464/ For the purposes of this presentation, think of RCU as something that defers work, with one work item per callback –Each callback has a function pointer and an argument –Callbacks are queued on per-CPU lists, invoked after grace period –Deferring the work a bit longer than needed is OK, deferring too long is bad – but failing to defer long enough is fatal –Allow extremely fast and scalable read-side access to shared data rcu_data rcu_data rcu_data rcu_data rcu_head ->next ->func rcu_head ->next ->func rcu_head ->next ->func
37. © 2009 IBM Corporation 37 Multicore World 2013 RCU: Tapping The Awesome Power of Procrastination For Two Decades!!!
38. © 2009 IBM Corporation 38 Multicore World 2013 RCU Area of Applicability Update-Mostly, Need Consistent Data (RCU is Really Unlikely to be the Right Tool For The Job, But SLAB_DESTROY_BY_RCU Is A Possibility) Read-Write, Need Consistent Data (RCU Might Be OK...) Read-Mostly, Need Consistent Data (RCU Works OK) Read-Mostly, Stale & Inconsistent Data OK (RCU Works Great!!!) Use the right tool for the job!!!
39. © 2009 IBM Corporation 39 Multicore World 2013 Applicability To The Linux Kernel
40. © 2009 IBM Corporation 40 Multicore World 2013 What Is RCU? (AKA Read-Copy Update) RCU uses a state machine driven out of the scheduling-clock interrupt to determine when it is safe to invoke callbacks Actual callback invocation is done from softirq Scheduling-Clock Interrupts softirq Callback Invocation CPU 0 Callback Queued
41. © 2009 IBM Corporation 41 Multicore World 2013 Procrastination's Dark Side
42. © 2009 IBM Corporation 42 Multicore World 2013 Procrastination's Dark Side: Eventually Must Do Work CPU 0 Callback Invoked Grace Period Likely disrupting whatever was intended to execute at about this time... call_rcu(): Queue Callback
43. © 2009 IBM Corporation 43 Multicore World 2013 Why Not Offload RCU's Callbacks?
44. © 2009 IBM Corporation 44 Multicore World 2013 Offload RCU Callbacks: Houston/Korty Approach CPU 2 Callback Invoked No disruption! CPU 0 Callback Invoked Grace Period RCU (CPU 1) call_rcu() call_rcu()
45. © 2009 IBM Corporation 45 Multicore World 2013 Offload RCU Callbacks: Houston/Korty Approach CPU 2 Callback Invoked No disruption! (But also no scalability, and Linux kernel must scale) CPU 0 Callback Invoked Grace Period RCU (CPU 1) call_rcu() call_rcu()
46. © 2009 IBM Corporation 46 Multicore World 2013 Scalable RCU Callback Offloading CPU 2 Callback Invoked Grace Period rcuo kthread No disruption! CPU 1 Callback Invoked Grace Period rcuo kthread call_rcu() call_rcu() Scheduler controls placement (or can place manually)
47. © 2009 IBM Corporation 47 Multicore World 2013 Adaptive Ticks And Callback Offloading Big Kernel Idle Usermode Small Kernel Usermode Scheduling clock interrupts Big Kernel Idle Usermode Small Kernel Usermode One task per CPU Adaptive Ticks RCU no longer causes extra scheduling clock interrupts Second task awakens
48. © 2009 IBM Corporation 48 Multicore World 2013 Where To Run RCU Callbacks???
49. © 2009 IBM Corporation 49 Multicore World 2013 Where To Run RCU Callbacks??? CPU 0 CPU 1 CPU 2 CPU 3 CPU 4 CPU 5 CPU 6 CPU 7 Interrupts, Management, Callbacks (Massive Disruption for Housekeeping) Worker Threads (HPC, Real Time) (No Disruption for Real Work) Exact Layout Depends on Workload
50. © 2009 IBM Corporation 50 Multicore World 2013 How Well Does It Work?
51. © 2009 IBM Corporation 51 Multicore World 2013 How Well Does It Work? Preliminary data looks good: also helps save energy – See later slides Some shortcomings, as always: –Adaptive-idle usermode slows user/kernel transitions slightly • Not a problem for computation-intensive workloads –One task per CPU for adaptive-idle usermode execution • Also not a problem for many computation-intensive workloads –Must reboot to reconfigure adaptive idle and RCU callback offloading –Must configure interrupts and processes manually (see next slide) –CPU 0 cannot be offloaded (future work) –At least one CPU must keep scheduling-clock interrupt (timekeeping) –Scalability likely limited to a few hundred CPUs (future work) –RCU callback-offloading kthreads (rcuo) not priority boosted • Rely on configuration restrictions leaving idle time on housekeeping CPUs –Work in progress: There are probably still a few bugs!
52. © 2009 IBM Corporation 52 Multicore World 2013 Removing Other Sources of Disturbance Interrupts: /proc/irq/*/ –One directory for each IRQ –smp_affinity file for hexadecimal specification (0x03) –smp_affinity_list for decimal CPU-list specification (0-1) –Verify via /proc/interrupts –Documentation/IRQ-affinity.txt in Linux kernel source for more info Timers: CPU hotplug remove then reinsert Processes, daemons, and kthreads: –Per-task affinity (taskset command, sched_setaffinity() syscall) –cgroups or cpusets (Documentation/cgroups/*.txt) Global TLB-flush operations –Can be caused by kernel module unloading • So don't unload kernel modules on production systems! Cache and TLB misses are still with us
53. © 2009 IBM Corporation 53 Multicore World 2013 RCU Callback Offloading: Energy Efficiency Preliminary data courtesy of Dietmar Eggemann and Robin Randhawa of ARM on early-silicon big.LITTLE system But what is big.LITTLE???
54. © 2009 IBM Corporation 54 Multicore World 2013 ARM big.LITTLE Architecture Cortex-A15 Cortex-A15 Cortex-A7 Cortex-A7 Cortex-A7 Twice as fast ~3 times more energy efficient big LITTLE
55. © 2009 IBM Corporation 55 Multicore World 2013 ARM big.LITTLE Architecture: Strategy Run on the LITTLE by default Run on big if heavy processing power is required In other words, if feasible, run on LITTLE for efficiency, but run on big if necessary to preserve user experience –This suggests that RCU callbacks should run on LITTLE CPUs
56. © 2009 IBM Corporation 56 Multicore World 2013 ARM big.LITTLE Without RCU Callback Offloading big CPU CB Grace Period LITTLE CPU Busy Busy Busy Busy call_rcu()
57. © 2009 IBM Corporation 57 Multicore World 2013 ARM big.LITTLE With RCU Callback Offloading big CPU CB Grace Period LITTLE CPU Busy Busy Busy Busy call_rcu()
58. © 2009 IBM Corporation 58 Multicore World 2013 ARM big.LITTLE With RCU Callback Offloading big CPU CB Grace Period LITTLE CPU Busy Busy Busy Busy call_rcu() CB
59. © 2009 IBM Corporation 59 Multicore World 2013 ARM big.LITTLE With RCU Callback Offloading big CPU CB Grace Period LITTLE CPU Busy Busy Busy Busy call_rcu() CB But 3x better energy efficiency
60. © 2009 IBM Corporation 60 Multicore World 2013 ARM big.LITTLE With no-CBs CPUs: Preliminary Results (Randhawa and Eggemann, ARM) Reference System: No offloading Test System: big CPUs offloaded, kthreads on LITTLE CPUs Approximate power savings: –cyclictest: 10% –andebench8: 2% –audio: 10% –bbench_with_audio: 5%
61. © 2009 IBM Corporation 61 Multicore World 2013 To Probe More Deeply Into Adaptive Idle  “The 2012 realtime minisummit” (LWN, CPU isolation discussion) – http://lwn.net/Articles/520704/  “Interruption timer périodique” (Kernel Recipes, in French) – https://kernel-recipes.org/?page_id=410  “What Is New In RCU for Real Time” (RTLWS 2012) – http://www.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf • Slides 31-32  “TODO” – https://github.com/fweisbec/linux-dynticks/wiki/TODO  “NoHZ tasks” (LWN) – http://lwn.net/Articles/420544/
62. © 2009 IBM Corporation 62 Multicore World 2013 To Probe More Deeply Into RCU Callback Offloading  “Making RCU Respect Your Device's Battery Lifetime: On-The-Job Energy- Efficiency Training For RCU Maintainers” (LCA 2013) – http://www.rdrop.com/users/paulmck/realtime/paper/RCUbattery.2013.01.30b.LCA.pdf  “Relocating RCU callbacks” by Jon Corbet –http://lwn.net/Articles/522262/  “What Is New In RCU for Real Time” (RTLWS 2012) – http://www.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf • Slides 21-on  “Getting RCU Further Out of the Way” (Plumbers 2012) – http://www.rdrop.com/users/paulmck/realtime/paper/nocb.2012.08.31a.pdf  “Cleaning Up Linux’s CPU Hotplug For Real Time and Energy Management” (ECRTS 2012) – http://www.rdrop.com/users/paulmck/realtime/paper/hotplug-ecrts.2012.06.11a.pdf
63. © 2009 IBM Corporation 63 Multicore World 2013 Summary General-purpose OS or bare-metal performance? –Why not both? –Work in progress gets us very close for CPU-bound workloads: • Adaptive idle userspace execution (work in progress) • RCU callback offloading (early version in mainline) • Interrupt, process, daemon, and kthread affinity • Timer offloading –Some restrictions: • Need to reserve CPU(s) for housekeeping • Adaptive-idle and RCU-callback-offloaded CPUs specified at boot time • One task per CPU for adaptive-idle usermode execution • Cache and TLB misses are still with us –Serendipity: Energy-efficiency benefits as well!
64. © 2009 IBM Corporation 64 Multicore World 2013 Summary General-purpose OS or bare-metal performance? –Why not both? –Work in progress gets us very close for CPU-bound workloads: • Adaptive idle userspace execution (work in progress) • RCU callback offloading (early version in mainline) • Interrupt, process, daemon, and kthread affinity • Timer offloading –Some restrictions: • Need to reserve CPU(s) for housekeeping • Adaptive-idle and RCU-callback-offloaded CPUs specified at boot time • One task per CPU for adaptive-idle usermode execution • Cache and TLB misses are still with us –Serendipity: Energy-efficiency benefits as well! Extending Linux's reach farther into extreme computing!!!
65. © 2009 IBM Corporation 65 Multicore World 2013 Legal Statement This work represents the view of the author and does not necessarily represent the view of IBM. IBM and IBM (logo) are trademarks or registered trademarks of International Business Machines Corporation in the United States and/or other countries. Linux is a registered trademark of Linus Torvalds. Other company, product, and service names may be trademarks or service marks of others.
66. © 2009 IBM Corporation 66 Multicore World 2013 Questions?