Scalable Commutativity Rule for Multicore Software Design
Explore the concept of the Scalable Commutativity Rule, a framework for designing scalable software on multicore processors by evaluating scalability through interface specifications before implementation. Discover the drawbacks, benefits, and contributions of this rule in optimizing software scalability.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert T. Morris, and Eddie Kohler MIT CSAIL and Harvard University 1/27/16 EECS 582 W16 1
Outline Introduce the problem Contributions Define the rule Commuter Evaluation Conclusion EECS 582 W16 2
What is the usual way to evaluate the scalability of multicore software? Differential profile Any drawbacks? Workload Plot Fix Scalability bottleneck
Drawbacks New workloads expose new bottlenecks More cores expose new bottlenecks The real bottlenecks may be in the interface design
Question: Can scalability opportunities be identified even before any implementation exists, simply by considering interface specifications? Yes!
The Scalable Commutativity Rule Whenever interface operations commute, they can be implemented in a way that scales.
Outline Introduce the problem Contributions Define the rule Commuter Evaluation Conclusion EECS 582 W16 7
Contributions The scalable commutativity rule Formalization of the rule and proof of its correctness State-dependent, interface-based commutativity Commuter: An automated scalability testing tool Sv6: A scalable POSIX-like kernel
SIM Commutativity The formalism of the rule relies on SIM commutativity Consider a history H = X || Y (where || concatenates action sequences) * Y SI-commutes in H when given any reordering Y of Y, and any action sequence Z, X || Y || Z is a well-formed histories iff X || Y || Z is also well formed * Y SIM-commutes in H when for any prefix P of some reordering of Y, P SI-commutes in X || P
Outline Introduce the problem Contributions Define the rule Commuter Evaluation Conclusion EECS 582 W16 10
What scales on todays multicore? We say two or more operations are scalable if they are conflict-free
The intuition behind the rule Whenever interface operations commute, they can be implemented in a way that scales. Operations commute => results independent of order => communication is unnecessary => without communication, no conflicts
Outline Introduce the problem Contributions Define the rule Commuter Evaluation Conclusion EECS 582 W16 13
Commuter Implementation (e.g., Linux) Interface specification (e.g., POSIX) All scalability bottlenecks Commuter
Outline Introduce the problem Contributions Define the rule Commuter Evaluation Conclusion EECS 582 W16 16
Sv6: A scalable OS POSIX-like operating system File system and virtual memory system follow commutativity rule Implementing using standard parallel programming techniques, but guided by Commuter
Commutative operations can be made to scale
Benchmark throughput in operations per second per core with varying core counts on sv6
Outline Introduce the problem Contributions Define the rule Commuter Evaluation Conclusion EECS 582 W16 21
Conclusion Whenever interface operations commute, they can be implemented in a way that scales. This rule helps developers in building more scalable software starting from interface design and carrying on through implementation, testing, and evaluation.
