Labeling Schemes for Improving Cilksan Performance
While race detection algorithms like SP-bags have provably good theoretical properties, large overheads exist in practice, which urges the need for performance optimization. In this thesis, I propose labeling schemes as a method of circumventing many of the expensive operations in Cilksan, an implem...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/157231 |
| _version_ | 1824458288562962432 |
|---|---|
| author | Holla, Satya |
| author2 | Schardl, Tao B. |
| author_facet | Schardl, Tao B. Holla, Satya |
| author_sort | Holla, Satya |
| collection | MIT |
| description | While race detection algorithms like SP-bags have provably good theoretical properties, large overheads exist in practice, which urges the need for performance optimization. In this thesis, I propose labeling schemes as a method of circumventing many of the expensive operations in Cilksan, an implementation of the SP-bags algorithm. The proposed labeling schemes give strands of a parallel program labels during the execution of Cilksan, allowing Cilksan to shortcut the processing of certain memory accesses if the label comparison allows. I describe and prove correctness for two labeling schemes, the procedure labeling scheme and the prefix labeling scheme, implement both in Cilksan, and measure their performance. While the results show that the overhead of maintaining labels is too high in my implementation, the labeling schemes manage to circumvent many of the memory access operations, suggesting the merit of a more performant implementation of the same schemes. |
| first_indexed | 2025-02-19T04:23:31Z |
| format | Thesis |
| id | mit-1721.1/157231 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2025-02-19T04:23:31Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1572312024-10-10T03:21:55Z Labeling Schemes for Improving Cilksan Performance Holla, Satya Schardl, Tao B. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science While race detection algorithms like SP-bags have provably good theoretical properties, large overheads exist in practice, which urges the need for performance optimization. In this thesis, I propose labeling schemes as a method of circumventing many of the expensive operations in Cilksan, an implementation of the SP-bags algorithm. The proposed labeling schemes give strands of a parallel program labels during the execution of Cilksan, allowing Cilksan to shortcut the processing of certain memory accesses if the label comparison allows. I describe and prove correctness for two labeling schemes, the procedure labeling scheme and the prefix labeling scheme, implement both in Cilksan, and measure their performance. While the results show that the overhead of maintaining labels is too high in my implementation, the labeling schemes manage to circumvent many of the memory access operations, suggesting the merit of a more performant implementation of the same schemes. M.Eng. 2024-10-09T18:29:51Z 2024-10-09T18:29:51Z 2024-09 2024-10-07T14:34:29.932Z Thesis https://hdl.handle.net/1721.1/157231 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Holla, Satya Labeling Schemes for Improving Cilksan Performance |
| title | Labeling Schemes for Improving Cilksan Performance |
| title_full | Labeling Schemes for Improving Cilksan Performance |
| title_fullStr | Labeling Schemes for Improving Cilksan Performance |
| title_full_unstemmed | Labeling Schemes for Improving Cilksan Performance |
| title_short | Labeling Schemes for Improving Cilksan Performance |
| title_sort | labeling schemes for improving cilksan performance |
| url | https://hdl.handle.net/1721.1/157231 |
| work_keys_str_mv | AT hollasatya labelingschemesforimprovingcilksanperformance |