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.