Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems
We present Coup, a technique to lower the cost of updates to shared data in cache-coherent systems. Coup exploits the insight that many update operations, such as additions and bitwise logical operations, are commutative: they produce the same final result regardless of the order they are performed...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/112771 https://orcid.org/0000-0003-1034-2306 |
| _version_ | 1826200748682117120 |
|---|---|
| author | Zhang, Guowei Horn, Webb H Sanchez, Daniel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Zhang, Guowei Horn, Webb H Sanchez, Daniel |
| author_sort | Zhang, Guowei |
| collection | MIT |
| description | We present Coup, a technique to lower the cost of updates to shared data in cache-coherent systems. Coup exploits the insight that many update operations, such as additions and bitwise logical operations, are commutative: they produce the same final result regardless of the order they are performed in. Coup allows multiple private caches to simultaneously hold update-only permission to the same cache line. Caches with update-only permission can locally buffer and coalesce updates to the line, but cannot satisfy read requests. Upon a read request, Coup reduces the partial updates buffered in private caches to produce the final value. Coup integrates seamlessly into existing coherence protocols, requires inexpensive hardware, and does not affect the memory consistency model.
We apply Coup to speed up single-word updates to shared data. On a simulated 128-core, 8-socket system, Coup accelerates state-of-the-art implementations of update-heavy algorithms by up to 2.4×. |
| first_indexed | 2024-09-23T11:41:09Z |
| format | Article |
| id | mit-1721.1/112771 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:41:09Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1127712022-10-01T05:17:46Z Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems Zhang, Guowei Horn, Webb H Sanchez, Daniel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Zhang, Guowei Horn, Webb H Sanchez, Daniel We present Coup, a technique to lower the cost of updates to shared data in cache-coherent systems. Coup exploits the insight that many update operations, such as additions and bitwise logical operations, are commutative: they produce the same final result regardless of the order they are performed in. Coup allows multiple private caches to simultaneously hold update-only permission to the same cache line. Caches with update-only permission can locally buffer and coalesce updates to the line, but cannot satisfy read requests. Upon a read request, Coup reduces the partial updates buffered in private caches to produce the final value. Coup integrates seamlessly into existing coherence protocols, requires inexpensive hardware, and does not affect the memory consistency model. We apply Coup to speed up single-word updates to shared data. On a simulated 128-core, 8-socket system, Coup accelerates state-of-the-art implementations of update-heavy algorithms by up to 2.4×. Center for Future Architectures Research National Science Foundation (U.S.) (CAREER-1452994) Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science (Grier Presidential Fellowship) Microelectronics Advanced Research Corporation United States. Defense Advanced Research Projects Agency 2017-12-15T22:45:02Z 2017-12-15T22:45:02Z 2015-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-4034-2 http://hdl.handle.net/1721.1/112771 Zhang, Guowei, Webb Horn, and Daniel Sanchez. “Exploiting Commutativity to Reduce the Cost of Updates to Shared Data in Cache-Coherent Systems.” Proceedings of the 48th International Symposium on Microarchitecture - MICRO-48 (2015). https://orcid.org/0000-0003-1034-2306 en_US http://dx.doi.org/10.1145/2830772.2830774 Proceedings of the 48th International Symposium on Microarchitecture (MICRO-48) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT Web Domain |
| spellingShingle | Zhang, Guowei Horn, Webb H Sanchez, Daniel Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems |
| title | Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems |
| title_full | Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems |
| title_fullStr | Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems |
| title_full_unstemmed | Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems |
| title_short | Exploiting commutativity to reduce the cost of updates to shared data in cache-coherent systems |
| title_sort | exploiting commutativity to reduce the cost of updates to shared data in cache coherent systems |
| url | http://hdl.handle.net/1721.1/112771 https://orcid.org/0000-0003-1034-2306 |
| work_keys_str_mv | AT zhangguowei exploitingcommutativitytoreducethecostofupdatestoshareddataincachecoherentsystems AT hornwebbh exploitingcommutativitytoreducethecostofupdatestoshareddataincachecoherentsystems AT sanchezdaniel exploitingcommutativitytoreducethecostofupdatestoshareddataincachecoherentsystems |