CSR: Medium: Collaborative Research: The Commutativity Rule for Scalable System Software

点击翻译按钮获取中文摘要

After decades of reliable improvement, processor speeds haveflattened; for the foreseeable future, computers will add processingpower by adding more processors, rather than faster ones. This is atremendous challenge for software designers. It's far too easy forsoftware using multiple processors to burn up a growing fraction ofavailable processing power on coordination overheads like locking,rather than actual work. That is, it's far too easy for software tonot scale: to get slower as processors are added. And an importantreason for this is simply that scalability is poorly understood. Someprograms don't scale because they're badly written, but others don'tscale because their goals are fundamentally impossible to accomplishin a scalable way. Programmers lack effective tools for high-levelreasoning about software scalability limitations, and thus wasteeffort on both impossible and uninteresting tasks.We will produce the first well-grounded and formal reasoning procedurefor scalability that is flexible enough to apply to an entireoperating system. Our scalability rule links commutativity andscalability. We characterize software interfaces as more or lessinherently scalable depending on the contexts in which thoseinterfaces commute: the more commutative an interface (that is, themore often the order of its function calls doesn't matter), the morescalable an implementation can be. We prove that a scalableimplementation exists for any commutative context. This idea canalready guide software designers in developing easily-scalableinterfaces, but we will also provide a set of automated tools formeasuring interface commutativity and for finding implementationscalability bottlenecks, and evaluate our ideas in a highly-scalableoperating system. The resulting tools and ideas could make scalablesoftware far easier to design and program, and thus help softwaredesigners provide the software performance on which so much of oureconomy depends.