The scalable commutativity rule: designing scalable software for multicore processors

What fundamental opportunities for scalability are latent in interfaces, such as system call APIs? Can scalability opportunities be identified even before any implemen-tation exists, simply by considering interface specifica-tions? To answer these questions this paper introduces the following rule: Whenever interface operations com-mute, they can be implemented in a way that scales. This rule aids developers in building more scalable software starting from interface design and carrying on through implementation, testing, and evaluation. To help developers apply the rule, a new tool named COMMUTER accepts high-level interface models and gen-erates tests of operations that commute and hence could scale. Using these tests, COMMUTER can evaluate the scalability of an implementation. We apply COMMUTER to 18 POSIX calls and use the results to guide the im-plementation of a new research operating system kernel called sv6. Linux scales for 68 % of the 13,664 tests gen-erated by COMMUTER for these calls, and COMMUTER finds many problems that have been observed to limit application scalability. sv6 scales for 99 % of the tests.