The Scalable Commutativity Rule: Designing Scalable Software For Multicore Processors
This newspaper was 1 of the best paper's at SOSP 13. The newspaper is opened upwardly access since SOSP paid for the opened upwardly access fees for each newspaper that appeared inwards the conference.
The scalable commutativity dominion says that "Whenever interface operations commute, they tin move implemented inwards a way that scales". In other words, whenever several operations commute at the interface-level (i.e., there's no way to distinguish their execution guild using the interface), for those operations nosotros tin possess got implementations whose retentiveness accesses are conflict-free.
(Scalable commutativity sounds similar a misnomer, shouldn't the theorem move called "commutative scalability" theorem? The destination goal is scalability, too commutativity is a tool for it. Thus "commutative" should qualify "scalability", non the other way around.)
I constitute several squeamish generalizable insights inwards the paper.
The commencement 1 is using commutativity every bit a detectable/measurable too controllable witness for concurrency. Concurrency is an abstract too specification-dependent concept. If you lot disregard security (which is defined past times the specification), you lot tin boost concurrency easily past times parallelizing aggressively, too you lot destination upwardly amongst a highly scalable arrangement total of race weather too incorrect/unsafe operations. It is hard to mensurate "safe concurrency" too boost it. By way of contrast, commutativity is good defined too easier to mensurate too control. If the lawsuit doesn't alter when you lot alter the guild of operations too so the guild is non of import too that way you lot don't demand to lock anything too you lot tin give away a lock-free/wait-free/coordination-free implementation.
The minute insight is to pose the dominion every bit a "possibility result" to guide the implementation process. It is clear that the newspaper is motivated past times practical problems too from the dry ground up. These guys are Linux core hackers, they are trying to modify Linux to run on multicore machines inwards a to a greater extent than efficient/scalable manner. As purpose of their move to brand Linux to a greater extent than scalable, they move at the trenches too prepare a lot of tricks too hacks. But they didn't know when to quit too when to persist: "Before the rule, nosotros tried to decide if these operations could scale past times analyzing all of the implementations nosotros could recall of. This procedure was difficult, unguided, too itself did non scale to complex interfaces, which motivated our goal of reasoning virtually scalability inwards price of interfaces." When operations commute at the specification level, this dominion tells them that they should persist because scalable implementations exist. When operations don't commute, this dominion tells them to quit because a scalable implementation may non be amongst this specifications.
Finally this dominion tin move used to guide the blueprint every bit well. When a scalable implementation may non move available amongst the electrical flow specifications of the operations (i.e., the operations create non commute at the interface level), the developers may visit changing the operations slightly to give away a blueprint where operations commute (where it is guaranteed to give away scalable implementations). To brand the operations commute, the operations may move designed to exercise dissimilar parameters or relax the guarantees on the returned result. For example, inwards the instance of a file operation, don't render the smallest unused file descriptor FD, but render an unused FD. If you lot alter the specification this way, too so you lot preclude the tilt on the smallest unused FD. In a feel this is moving away from a queue semantic (which is guild sensitive) to a laid upwardly semantic (which is guild insensitive, a.k.a. commutative). The essence of push clit a fast 1 on has been used to modify operations to commute too make conflict-free implementations.
The newspaper is a tour de force. The authors developed a tool called COMMUTER that accepts high-level interface models too generates tests of operations that commute too thence could scale. The tool uses a combination of symbolic too concolic execution, too generates examine cases for an arbitrary implementation based on a model of that implementation's interface.
"First, ANALYZER takes a symbolic model of an interface too computes precise weather nether which that interface’s operations commute. Second, TESTGEN takes these weather too generates concrete examine cases of sets of operations that commute according to the interface model, too thus should possess got a conflict-free implementation according to the commutativity rule. Third, MTRACE checks whether a detail implementation is conflict-free for each examine case."
The evaluation of the newspaper is also exhaustive. They modeled several POSIX file arrangement too virtual retentiveness calls inwards COMMUTER, too so used this both to evaluate Linux's scalability too to prepare a scalable file too virtual retentiveness arrangement for their sv6 enquiry kernel. I loved Figure 6, it shows a lot of things without overwhelming the viewer.
To demo how the results inwards Figure six interpret to scalability on existent hardware they evaluated amongst to a greater extent than or less microbenchmarks too a postal service server application.
A: The newspaper avoids this enquiry too doesn't possess got an response to this. My gauge is the inverse would dot exclusively a relative unscalability, non an absolute one. And it is hard to quantify the relative unscalability. But the master copy theorem is clean, it provides an absolute result: an implementation amongst conflict-free retentiveness accesses, i.e., full-scalability is possible.
Question: Is this dominion is applicable to the full general distributed systems too non only multicore systems?
A: The newspaper claims this is the instance inwards the related move but doesn't elaborate to a greater extent than on that. Yes, this should move but in that location are assumptions. The functioning should possess got invocation too response parts. The high grade specification of the operations should instruct far clear what the functioning does so you lot tin perform the commutativity tests.
Question: What are the tradeoffs when coming upwardly amongst variants of operations to brand them commute?
A: Instead of a big operation, you lot may separate it into ii pocket-size operations to ameliorate commutativity. But did this brand the undertaking of the developers harder. Well maybe, but it is worth it if you lot made it conflict-free on multicores. And at 1 time instead of crossing the core boundary once, you lot may move crossing the core boundary twice because you lot possess got replaced 1 functioning amongst ii operations. So you lot pay overhead, but it is OK if you lot had improved the commutativity too scalability of the operations.
http://www.srl.inf.ethz.ch/
It was also profiled inwards Linux Weekly: http://lwn.net/Articles/
The scalable commutativity dominion says that "Whenever interface operations commute, they tin move implemented inwards a way that scales". In other words, whenever several operations commute at the interface-level (i.e., there's no way to distinguish their execution guild using the interface), for those operations nosotros tin possess got implementations whose retentiveness accesses are conflict-free.
(Scalable commutativity sounds similar a misnomer, shouldn't the theorem move called "commutative scalability" theorem? The destination goal is scalability, too commutativity is a tool for it. Thus "commutative" should qualify "scalability", non the other way around.)
I constitute several squeamish generalizable insights inwards the paper.
The commencement 1 is using commutativity every bit a detectable/measurable too controllable witness for concurrency. Concurrency is an abstract too specification-dependent concept. If you lot disregard security (which is defined past times the specification), you lot tin boost concurrency easily past times parallelizing aggressively, too you lot destination upwardly amongst a highly scalable arrangement total of race weather too incorrect/unsafe operations. It is hard to mensurate "safe concurrency" too boost it. By way of contrast, commutativity is good defined too easier to mensurate too control. If the lawsuit doesn't alter when you lot alter the guild of operations too so the guild is non of import too that way you lot don't demand to lock anything too you lot tin give away a lock-free/wait-free/coordination-free implementation.
The minute insight is to pose the dominion every bit a "possibility result" to guide the implementation process. It is clear that the newspaper is motivated past times practical problems too from the dry ground up. These guys are Linux core hackers, they are trying to modify Linux to run on multicore machines inwards a to a greater extent than efficient/scalable manner. As purpose of their move to brand Linux to a greater extent than scalable, they move at the trenches too prepare a lot of tricks too hacks. But they didn't know when to quit too when to persist: "Before the rule, nosotros tried to decide if these operations could scale past times analyzing all of the implementations nosotros could recall of. This procedure was difficult, unguided, too itself did non scale to complex interfaces, which motivated our goal of reasoning virtually scalability inwards price of interfaces." When operations commute at the specification level, this dominion tells them that they should persist because scalable implementations exist. When operations don't commute, this dominion tells them to quit because a scalable implementation may non be amongst this specifications.
Finally this dominion tin move used to guide the blueprint every bit well. When a scalable implementation may non move available amongst the electrical flow specifications of the operations (i.e., the operations create non commute at the interface level), the developers may visit changing the operations slightly to give away a blueprint where operations commute (where it is guaranteed to give away scalable implementations). To brand the operations commute, the operations may move designed to exercise dissimilar parameters or relax the guarantees on the returned result. For example, inwards the instance of a file operation, don't render the smallest unused file descriptor FD, but render an unused FD. If you lot alter the specification this way, too so you lot preclude the tilt on the smallest unused FD. In a feel this is moving away from a queue semantic (which is guild sensitive) to a laid upwardly semantic (which is guild insensitive, a.k.a. commutative). The essence of push clit a fast 1 on has been used to modify operations to commute too make conflict-free implementations.
The newspaper is a tour de force. The authors developed a tool called COMMUTER that accepts high-level interface models too generates tests of operations that commute too thence could scale. The tool uses a combination of symbolic too concolic execution, too generates examine cases for an arbitrary implementation based on a model of that implementation's interface.
"First, ANALYZER takes a symbolic model of an interface too computes precise weather nether which that interface’s operations commute. Second, TESTGEN takes these weather too generates concrete examine cases of sets of operations that commute according to the interface model, too thus should possess got a conflict-free implementation according to the commutativity rule. Third, MTRACE checks whether a detail implementation is conflict-free for each examine case."
The evaluation of the newspaper is also exhaustive. They modeled several POSIX file arrangement too virtual retentiveness calls inwards COMMUTER, too so used this both to evaluate Linux's scalability too to prepare a scalable file too virtual retentiveness arrangement for their sv6 enquiry kernel. I loved Figure 6, it shows a lot of things without overwhelming the viewer.
To demo how the results inwards Figure six interpret to scalability on existent hardware they evaluated amongst to a greater extent than or less microbenchmarks too a postal service server application.
Discussion
Question: The scalable commutativity dominion says: If interface operations commute, too so they tin move implemented inwards a way that scales. Is in that location a argue why you lot don't claim the inverse: If interface operations don't commute, too so they cannot move implemented inwards a way that scales. If the inverse is true, too so this dominion volition possess got stronger implications for interface design.A: The newspaper avoids this enquiry too doesn't possess got an response to this. My gauge is the inverse would dot exclusively a relative unscalability, non an absolute one. And it is hard to quantify the relative unscalability. But the master copy theorem is clean, it provides an absolute result: an implementation amongst conflict-free retentiveness accesses, i.e., full-scalability is possible.
Question: Is this dominion is applicable to the full general distributed systems too non only multicore systems?
A: The newspaper claims this is the instance inwards the related move but doesn't elaborate to a greater extent than on that. Yes, this should move but in that location are assumptions. The functioning should possess got invocation too response parts. The high grade specification of the operations should instruct far clear what the functioning does so you lot tin perform the commutativity tests.
Question: What are the tradeoffs when coming upwardly amongst variants of operations to brand them commute?
A: Instead of a big operation, you lot may separate it into ii pocket-size operations to ameliorate commutativity. But did this brand the undertaking of the developers harder. Well maybe, but it is worth it if you lot made it conflict-free on multicores. And at 1 time instead of crossing the core boundary once, you lot may move crossing the core boundary twice because you lot possess got replaced 1 functioning amongst ii operations. So you lot pay overhead, but it is OK if you lot had improved the commutativity too scalability of the operations.
Updates:
Martin Vechev emailed me virtually my commencement question, too he had this to say: " we had an before POPL'11 newspaper that shows 1 purpose of the inverse enquiry you lot are asking, that if you lot possess got rigid non-commutativity you lot demand expensive instructions:http://www.srl.inf.ethz.ch/
It was also profiled inwards Linux Weekly: http://lwn.net/Articles/
0 Response to "The Scalable Commutativity Rule: Designing Scalable Software For Multicore Processors"
Post a Comment