Managing performance vs. accuracy trade-offs with loop perforation
Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the com...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72440 https://orcid.org/0000-0003-0313-9270 https://orcid.org/0000-0001-8095-8523 |
| _version_ | 1826208342870065152 |
|---|---|
| author | Sidiroglou, Stelios Misailovic, Sasa Hoffmann, Henry Christian Rinard, Martin C. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Sidiroglou, Stelios Misailovic, Sasa Hoffmann, Henry Christian Rinard, Martin C. |
| author_sort | Sidiroglou, Stelios |
| collection | MIT |
| description | Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the computation at hand. Loop perforation provides a general technique to trade accuracy for performance by transforming loops to execute a subset of their iterations. A criticality testing phase filters out critical loops (whose perforation produces unacceptable behavior) to identify tunable loops (whose perforation produces more efficient and still acceptably accurate computations). A perforation space exploration algorithm perforates combinations of tunable loops to find Pareto-optimal perforation policies. Our results indicate that, for a range of applications, this approach typically delivers performance increases of over a factor of two (and up to a factor of seven) while changing the result that the application produces by less than 10%. |
| first_indexed | 2024-09-23T14:04:15Z |
| format | Article |
| id | mit-1721.1/72440 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:04:15Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/724402022-10-01T18:57:53Z Managing performance vs. accuracy trade-offs with loop perforation Sidiroglou, Stelios Misailovic, Sasa Hoffmann, Henry Christian Rinard, Martin C. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Rinard, Martin C. Sidiroglou, Stelios Misailovic, Sasa Hoffmann, Henry Christian Rinard, Martin C. Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the computation at hand. Loop perforation provides a general technique to trade accuracy for performance by transforming loops to execute a subset of their iterations. A criticality testing phase filters out critical loops (whose perforation produces unacceptable behavior) to identify tunable loops (whose perforation produces more efficient and still acceptably accurate computations). A perforation space exploration algorithm perforates combinations of tunable loops to find Pareto-optimal perforation policies. Our results indicate that, for a range of applications, this approach typically delivers performance increases of over a factor of two (and up to a factor of seven) while changing the result that the application produces by less than 10%. 2012-08-29T20:02:19Z 2012-08-29T20:02:19Z 2011-09 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0443-6 http://hdl.handle.net/1721.1/72440 Stelios Sidiroglou-Douskos, Sasa Misailovic, Henry Hoffmann, and Martin Rinard. 2011. Managing performance vs. accuracy trade-offs with loop perforation. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering (ESEC/FSE '11). ACM, New York, NY, USA, 124-134. https://orcid.org/0000-0003-0313-9270 https://orcid.org/0000-0001-8095-8523 en_US http://dx.doi.org/10.1145/2025113.2025133 Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering (ESEC/FSE '11) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Sidiroglou, Stelios Misailovic, Sasa Hoffmann, Henry Christian Rinard, Martin C. Managing performance vs. accuracy trade-offs with loop perforation |
| title | Managing performance vs. accuracy trade-offs with loop perforation |
| title_full | Managing performance vs. accuracy trade-offs with loop perforation |
| title_fullStr | Managing performance vs. accuracy trade-offs with loop perforation |
| title_full_unstemmed | Managing performance vs. accuracy trade-offs with loop perforation |
| title_short | Managing performance vs. accuracy trade-offs with loop perforation |
| title_sort | managing performance vs accuracy trade offs with loop perforation |
| url | http://hdl.handle.net/1721.1/72440 https://orcid.org/0000-0003-0313-9270 https://orcid.org/0000-0001-8095-8523 |
| work_keys_str_mv | AT sidirogloustelios managingperformancevsaccuracytradeoffswithloopperforation AT misailovicsasa managingperformancevsaccuracytradeoffswithloopperforation AT hoffmannhenrychristian managingperformancevsaccuracytradeoffswithloopperforation AT rinardmartinc managingperformancevsaccuracytradeoffswithloopperforation |