SiblingRivalry: Online Autotuning Through Local Competitions
Modern high performance libraries, such as ATLAS and FFTW, and programming languages, such as PetaBricks, have shown that autotuning computer programs can lead to significant speedups. However, autotuning can be burdensome to the deployment of a program, since the tuning process can take a long time...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/85937 https://orcid.org/0000-0002-7231-7643 |
| _version_ | 1826216276590067712 |
|---|---|
| author | Ansel, Jason Andrew Pacula, Maciej Wong, Yee Lok Chan, Cy Olszewski, Marek Krystyn O'Reilly, Una-May Amarasinghe, Saman P. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ansel, Jason Andrew Pacula, Maciej Wong, Yee Lok Chan, Cy Olszewski, Marek Krystyn O'Reilly, Una-May Amarasinghe, Saman P. |
| author_sort | Ansel, Jason Andrew |
| collection | MIT |
| description | Modern high performance libraries, such as ATLAS and FFTW, and programming languages, such as PetaBricks, have shown that autotuning computer programs can lead to significant speedups. However, autotuning can be burdensome to the deployment of a program, since the tuning process can take a long time and should be re-run whenever the program, microarchitecture, execution environment, or tool chain changes. Failure to re-autotune programs often leads to widespread use of sub-optimal algorithms. With the growth of cloud computing, where computations can run in environments with unknown load and migrate between different (possibly unknown) microarchitectures, the need for online autotuning has become increasingly important.
We present SiblingRivalry, a new model for always-on online autotuning that allows parallel programs to continuously adapt and optimize themselves to their environment. In our system, requests are processed by dividing the available cores in half, and processing two identical requests in parallel on each half. Half of the cores are devoted to a known safe program configuration, while the other half are used for an experimental program configuration chosen by our self-adapting evolutionary algorithm. When the faster configuration completes, its results are returned, and the slower configuration is terminated. Over time, this constant experimentation allows programs to adapt to changing dynamic environments and often outperform the original algorithm that uses the entire system. |
| first_indexed | 2024-09-23T16:45:08Z |
| format | Article |
| id | mit-1721.1/85937 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:45:08Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/859372022-09-29T21:13:30Z SiblingRivalry: Online Autotuning Through Local Competitions Ansel, Jason Andrew Pacula, Maciej Wong, Yee Lok Chan, Cy Olszewski, Marek Krystyn O'Reilly, Una-May Amarasinghe, Saman P. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ansel, Jason Andrew Pacula, Maciej Wong, Yee Lok Chan, Cy Olszewski, Marek Krystyn O'Reilly, Una-May Amarasinghe, Saman P. Modern high performance libraries, such as ATLAS and FFTW, and programming languages, such as PetaBricks, have shown that autotuning computer programs can lead to significant speedups. However, autotuning can be burdensome to the deployment of a program, since the tuning process can take a long time and should be re-run whenever the program, microarchitecture, execution environment, or tool chain changes. Failure to re-autotune programs often leads to widespread use of sub-optimal algorithms. With the growth of cloud computing, where computations can run in environments with unknown load and migrate between different (possibly unknown) microarchitectures, the need for online autotuning has become increasingly important. We present SiblingRivalry, a new model for always-on online autotuning that allows parallel programs to continuously adapt and optimize themselves to their environment. In our system, requests are processed by dividing the available cores in half, and processing two identical requests in parallel on each half. Half of the cores are devoted to a known safe program configuration, while the other half are used for an experimental program configuration chosen by our self-adapting evolutionary algorithm. When the faster configuration completes, its results are returned, and the slower configuration is terminated. Over time, this constant experimentation allows programs to adapt to changing dynamic environments and often outperform the original algorithm that uses the entire system. United States. Dept. of Energy (DOE Award DE-SC0005288) 2014-03-27T20:28:48Z 2014-03-27T20:28:48Z 2012-10 Article http://purl.org/eprint/type/ConferencePaper 9781450314244 1450314244 http://hdl.handle.net/1721.1/85937 Ansel, Jason, Maciej Pacula, Yee Lok Wong, Cy Chan, Marek Olszewski, Una-May O’Reilly, and Saman Amarasinghe. “Siblingrivalry: Online Autotuning Through Local Competitions.” In Proceedings of the 2012 International Conference on Compilers, Architectures and Synthesis for Embedded Systems - CASES ’12 (2012), October 7-12, 2012, Tampere, Finland. https://orcid.org/0000-0002-7231-7643 en_US http://dx.doi.org/10.1145/2380403.2380425 Proceedings of the 2012 international conference on Compilers, architectures and synthesis for embedded systems - CASES '12 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 | Ansel, Jason Andrew Pacula, Maciej Wong, Yee Lok Chan, Cy Olszewski, Marek Krystyn O'Reilly, Una-May Amarasinghe, Saman P. SiblingRivalry: Online Autotuning Through Local Competitions |
| title | SiblingRivalry: Online Autotuning Through Local Competitions |
| title_full | SiblingRivalry: Online Autotuning Through Local Competitions |
| title_fullStr | SiblingRivalry: Online Autotuning Through Local Competitions |
| title_full_unstemmed | SiblingRivalry: Online Autotuning Through Local Competitions |
| title_short | SiblingRivalry: Online Autotuning Through Local Competitions |
| title_sort | siblingrivalry online autotuning through local competitions |
| url | http://hdl.handle.net/1721.1/85937 https://orcid.org/0000-0002-7231-7643 |
| work_keys_str_mv | AT anseljasonandrew siblingrivalryonlineautotuningthroughlocalcompetitions AT paculamaciej siblingrivalryonlineautotuningthroughlocalcompetitions AT wongyeelok siblingrivalryonlineautotuningthroughlocalcompetitions AT chancy siblingrivalryonlineautotuningthroughlocalcompetitions AT olszewskimarekkrystyn siblingrivalryonlineautotuningthroughlocalcompetitions AT oreillyunamay siblingrivalryonlineautotuningthroughlocalcompetitions AT amarasinghesamanp siblingrivalryonlineautotuningthroughlocalcompetitions |