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 implementation exists, simply by considering interface specifications? To answer these questions this paper introduces the following rule: Wh...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86882 https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X https://orcid.org/0000-0003-2700-9286 |
| _version_ | 1826211029924708352 |
|---|---|
| author | Clements, Austin T. Kaashoek, M. Frans Zeldovich, Nickolai Morris, Robert Tappan Kohler, Edward W. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Clements, Austin T. Kaashoek, M. Frans Zeldovich, Nickolai Morris, Robert Tappan Kohler, Edward W. |
| author_sort | Clements, Austin T. |
| collection | MIT |
| description | What fundamental opportunities for scalability are latent in interfaces, such as system call APIs? Can scalability opportunities be identified even before any implementation exists, simply by considering interface specifications? To answer these questions this paper introduces the following rule: Whenever interface operations commute, 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 generates 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 implementation of a new research operating system kernel called sv6. Linux scales for 68% of the 13,664 tests generated 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. |
| first_indexed | 2024-09-23T14:59:27Z |
| format | Article |
| id | mit-1721.1/86882 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:59:27Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/868822022-10-01T23:46:49Z The scalable commutativity rule: designing scalable software for multicore processors Clements, Austin T. Kaashoek, M. Frans Zeldovich, Nickolai Morris, Robert Tappan Kohler, Edward W. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Clements, Austin T. Kaashoek, M. Frans Zeldovich, Nickolai Morris, Robert Tappan What fundamental opportunities for scalability are latent in interfaces, such as system call APIs? Can scalability opportunities be identified even before any implementation exists, simply by considering interface specifications? To answer these questions this paper introduces the following rule: Whenever interface operations commute, 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 generates 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 implementation of a new research operating system kernel called sv6. Linux scales for 68% of the 13,664 tests generated 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. National Science Foundation (U.S.) (NSF award SHF-964106) National Science Foundation (U.S.) (NSF award CNS-1301934) Alfred P. Sloan Foundation (Fellowship) Microsoft Research (New Faculty Fellowship) 2014-05-08T19:49:11Z 2014-05-08T19:49:11Z 2013 Article http://purl.org/eprint/type/ConferencePaper 9781450323888 http://hdl.handle.net/1721.1/86882 Clements, Austin T., M. Frans Kaashoek, Nickolai Zeldovich, Robert T. Morris, and Eddie Kohler. “The Scalable Commutativity Rule: designing scalable software for multicore processors.” Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles - SOSP ’13 (2013). Nov. 3–6, 2013, Farmington, Pennsylvania, USA. p.2-17. https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X https://orcid.org/0000-0003-2700-9286 en_US http://dx.doi.org/10.1145/2517349.2522712 Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles - SOSP '13 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Clements, Austin T. Kaashoek, M. Frans Zeldovich, Nickolai Morris, Robert Tappan Kohler, Edward W. The scalable commutativity rule: designing scalable software for multicore processors |
| title | The scalable commutativity rule: designing scalable software for multicore processors |
| title_full | The scalable commutativity rule: designing scalable software for multicore processors |
| title_fullStr | The scalable commutativity rule: designing scalable software for multicore processors |
| title_full_unstemmed | The scalable commutativity rule: designing scalable software for multicore processors |
| title_short | The scalable commutativity rule: designing scalable software for multicore processors |
| title_sort | scalable commutativity rule designing scalable software for multicore processors |
| url | http://hdl.handle.net/1721.1/86882 https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X https://orcid.org/0000-0003-2700-9286 |
| work_keys_str_mv | AT clementsaustint thescalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT kaashoekmfrans thescalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT zeldovichnickolai thescalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT morrisroberttappan thescalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT kohleredwardw thescalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT clementsaustint scalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT kaashoekmfrans scalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT zeldovichnickolai scalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT morrisroberttappan scalablecommutativityruledesigningscalablesoftwareformulticoreprocessors AT kohleredwardw scalablecommutativityruledesigningscalablesoftwareformulticoreprocessors |