Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Bare-Metal Multicore Performance in a General-P...

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.

Multicore World 2013

February 19, 2013
Tweet

More Decks by Multicore World 2013

Other Decks in Programming

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 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?
  16. © 2009 IBM Corporation 17 Multicore World 2013 Is The

    Kernel Being In The Way Really A Problem?
  17. © 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!!!
  18. © 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
  19. © 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
  20. © 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!!!
  21. © 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!!!
  22. © 2009 IBM Corporation 23 Multicore World 2013 Yes, This

    Is A Real Problem For Some Workloads
  23. © 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?
  24. © 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
  25. © 2009 IBM Corporation 27 Multicore World 2013 Benchmark Results

    After (Anton Blanchard) Well worth going after...
  26. © 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
  27. © 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???
  28. © 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
  29. © 2009 IBM Corporation 32 Multicore World 2013 How Well

    Does It Work? Preliminary results look good
  30. © 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
  31. © 2009 IBM Corporation 34 Multicore World 2013 Other Than

    RCU, Looks Great!!! Need to fix RCU But first, what is RCU?
  32. © 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
  33. © 2009 IBM Corporation 37 Multicore World 2013 RCU: Tapping

    The Awesome Power of Procrastination For Two Decades!!!
  34. © 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!!!
  35. © 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
  36. © 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
  37. © 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()
  38. © 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()
  39. © 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)
  40. © 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
  41. © 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
  42. © 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!
  43. © 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
  44. © 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???
  45. © 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
  46. © 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
  47. © 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()
  48. © 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()
  49. © 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
  50. © 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
  51. © 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%
  52. © 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/
  53. © 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
  54. © 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!
  55. © 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!!!
  56. © 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.