Leveraging Hardware Caches for Memoization
Memoization improves performance and saves energy by caching and reusing the outputs of repetitive computations. Prior work has proposed software and hardware memoization techniques, but both have significant drawbacks. Software memoization suffers from high runtime overheads, and is thus limited to...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128501 |
| _version_ | 1811083285079523328 |
|---|---|
| author | Zhang, Guowei 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 Sanchez, Daniel |
| author_sort | Zhang, Guowei |
| collection | MIT |
| description | Memoization improves performance and saves energy by caching and reusing the outputs of repetitive computations. Prior work has proposed software and hardware memoization techniques, but both have significant drawbacks. Software memoization suffers from high runtime overheads, and is thus limited to long computations. Conventional hardware memoization techniques achieve low overheads and can memoize short functions, but they rely on large, special-purpose memoization caches that waste significant area and energy. We propose MCACHE, a hardware technique that leverages data caches for memoization. MCACHE stores memoization tables in memory, and allows them to share cache capacity with normal program data. MCACHE introduces ISA and pipeline extensions to accelerate memoization operations, bridging the gap between software and conventional hardware techniques. Simulation results show that MCACHE improves performance by up to 21 ×, outperforms software memoization by up to 2.2 ×, and achieves similar or superior performance over conventional hardware techniques without any dedicated storage. |
| first_indexed | 2024-09-23T12:30:37Z |
| format | Article |
| id | mit-1721.1/128501 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:30:37Z |
| publishDate | 2020 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1285012022-09-28T08:11:55Z Leveraging Hardware Caches for Memoization Zhang, Guowei Sanchez, Daniel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Memoization improves performance and saves energy by caching and reusing the outputs of repetitive computations. Prior work has proposed software and hardware memoization techniques, but both have significant drawbacks. Software memoization suffers from high runtime overheads, and is thus limited to long computations. Conventional hardware memoization techniques achieve low overheads and can memoize short functions, but they rely on large, special-purpose memoization caches that waste significant area and energy. We propose MCACHE, a hardware technique that leverages data caches for memoization. MCACHE stores memoization tables in memory, and allows them to share cache capacity with normal program data. MCACHE introduces ISA and pipeline extensions to accelerate memoization operations, bridging the gap between software and conventional hardware techniques. Simulation results show that MCACHE improves performance by up to 21 ×, outperforms software memoization by up to 2.2 ×, and achieves similar or superior performance over conventional hardware techniques without any dedicated storage. 2020-11-17T15:50:08Z 2020-11-17T15:50:08Z 2017-10 2019-07-03T13:36:26Z Article http://purl.org/eprint/type/JournalArticle 1556-6056 https://hdl.handle.net/1721.1/128501 Zhang, Guowei and Daniel Sanchez. "Leveraging Hardware Caches for Memoization." IEEE Computer Architecture Letters 17, 1 (January 2018): 59-63 © 2017 IEEE en http://dx.doi.org/10.1109/lca.2017.2762308 IEEE Computer Architecture Letters Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Zhang, Guowei Sanchez, Daniel Leveraging Hardware Caches for Memoization |
| title | Leveraging Hardware Caches for Memoization |
| title_full | Leveraging Hardware Caches for Memoization |
| title_fullStr | Leveraging Hardware Caches for Memoization |
| title_full_unstemmed | Leveraging Hardware Caches for Memoization |
| title_short | Leveraging Hardware Caches for Memoization |
| title_sort | leveraging hardware caches for memoization |
| url | https://hdl.handle.net/1721.1/128501 |
| work_keys_str_mv | AT zhangguowei leveraginghardwarecachesformemoization AT sanchezdaniel leveraginghardwarecachesformemoization |