Supervision : Gilles MULLER

Towards More Scalable Mutual Exclusion for Multicore Architectures

The scalability of multithreaded applications on current multicore systems is hampered by the performance of lock algorithms, due to the costs of access contention and cache misses. The main contribution presented in this thesis is a new lock algorithm, Remote Core Locking (RCL), that aims to improve the performance of critical sections in legacy applications on multicore architectures. The idea of RCL is to replace lock acquisitions by optimized remote procedure calls to a dedicated hardware thread, which is referred to as the server. RCL limits the performance collapse observed with other lock algorithms when many threads try to acquire a lock concurrently and removes the need to transfer lock-protected shared data to the hardware thread acquiring the lock because such data can typically remain in the server's cache.
Other contributions presented in this thesis include a profiler that identifies the locks that are the bottlenecks in multithreaded applications and that can thus benefit from RCL, and a reengineering tool developed with Julia Lawall that transforms POSIX locks into RCL locks. Eighteen applications were used to evaluate RCL: the nine applications of the SPLASH-2 benchmark suite, the seven applications of the Phoenix 2 benchmark suite, Memcached, and Berkeley DB with a TPC-C client. Eight of these applications are unable to scale because of locks and benefit from RCL on an x86 machine with four AMD Opteron processors and 48 hardware threads. Using RCL locks, performance is improved by up to 2.5 times with respect to POSIX locks on Memcached, and up to 11.6 times with respect to Berkeley DB with the TPC-C client. On an SPARC machine with two Sun Ultrasparc T2+ processors and 128 hardware threads, three applications benefit from RCL. In particular, performance is improved by up to 1.3 times with respect to POSIX locks on Memcached, and up to 7.9 times with respect to Berkeley DB with the TPC-C client.

2011-2020 Publications

• 2020
  • R. Gouicem, D. Carver, J.‑P. Lozi, J. Sopena, B. Lepers, W. Zwaenepoel, N. Palix, J. Lawall, G. Muller : “Fewer Cores, More Hertz: Leveraging High-Frequency Cores in the OS Scheduler for Improved Application Performance”, 2020 USENIX Annual Technical Conference, Boston / Virtual, United States (2020)
  • B. Lepers, R. Gouicem, D. Carver, J.‑P. Lozi, N. Palix, M.‑V. Aponte, W. Zwaenepoel, J. Sopena, J. Lawall, G. Muller : “Provable Multicore Schedulers with Ipanema: Application to Work Conservation”, Eurosys 2020 - European Conference on Computer Systems, Heraklion / Virtual, Greece (2020)
• 2019
  • D. Carver, R. Gouicem, J.‑P. Lozi, J. Sopena, B. Lepers, W. Zwaenepoel, N. Palix, J. Lawall, G. Muller : “Fork/Wait and Multicore Frequency Scaling: a Generational Clash”, 10^th Workshop on Programming Languages and Operating Systems, Huntsville, Canada, pp. 53-59, (ACM Press) (2019)
  • R. Gouicem, J. Sopena, J. Lawall, G. Muller, B. Lepers, W. Zwaenepoel, J.‑P. Lozi, N. Palix : “Understanding scheduler performance : a feature-based approach”, Compas 2019 - Conférence d’informatique en Parallélisme, Architecture et Système, Anglet, France (2019)
• 2017
  • R. Gouicem, J. Sopena, J. Lawall, G. Muller, B. Lepers, W. Zwaenepoel, J.‑P. Lozi, N. Palix : “Ipanema : un langage dédié pour le développement d’ordonnanceurs multi-coeur sûrs”, Compas 2017: Conférence d’informatique en Parallélisme, Architecture et Système, Sophia Antipolis, France (2017)
  • B. Lepers, W. Zwaenepoel, J.‑P. Lozi, N. Palix, R. Gouicem, J. Sopena, J. Lawall, G. Muller : “Towards Proving Optimistic Multicore Schedulers”, HotOS 2017 - 16^th Workshop on Hot Topics in Operating Systems, Whistler, British Columbia, Canada, pp. 6 (2017)
• 2016
  • J.‑P. Lozi, F. David, G. Thomas, J. Lawall, G. Muller : “Fast and Portable Locking for Multicore Architectures”, ACM Transactions on Computer Systems, (Association for Computing Machinery) (2016)
• 2014
  • J.‑P. Lozi : “Vers des mécanismes d’exclusion mutuelle plus efficaces pour les architectures multi-cœur”, thesis, defence 07/16/2014, supervision Muller, Gilles (2014)
  • J.‑P. Lozi, F. David, G. Thomas, J. Lawall, G. Muller : “Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications”, ComPAS 2014 : conférence en parallélisme, architecture et systèmes, Neuchâtel, Switzerland (2014)
• 2013
  • S. Saha, J.‑P. Lozi, G. Thomas, J. Lawall, G. Muller : “Hector: Detecting resource-release omission faults in error-handling code for systems software”, DSN 2013 - 43^rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), Budapest, Hungary, pp. 1-12, (IEEE Computer Society) (2013)
  • S. Saha, J.‑P. Lozi : “EHCtor: Detecting Resource-Release Omission Faults in Error-Handling Code for Systems Software”, 9^e Conférence Française en Systèmes d'Exploitation, Grenoble, France (2013)
• 2012
  • J.‑P. Lozi, F. David, G. Thomas, Julia L. Lawall, G. Muller : “Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications”, Proceedings of the 2012 USENIX Annual Technical Conference (USENIX ATC '12), Boston, MA, United States, (ACM) (2012)
• 2011
  • J.‑P. Lozi, G. Thomas, Julia L. Lawall, G. Muller : “Efficient locking for multicore architectures”, 30 pages (2011)
  • J.‑P. Lozi : “Le Remote Core Lock (RCL) : une nouvelle technique de verrouillage pour les architectures multi-coeur”, 8^e Conférence Française en Systèmes d'Exploitation, Saint-Malo, France (2011)