On Friday October 17, this site was moved to a new server, https://mw.hh.se. The original address will continue to work. Whithin a week or two this site will return to the original address. /Peo HH IT-dep
WG211/M21Glueck: Difference between revisions
From WG 2.11
Jump to navigationJump to search
Created page with "The design and implementation of efficient algorithms for reversible computing systems requires an unconventional way of thinking. Memoization is a classic program optimizatio..." |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
The design and implementation of efficient algorithms for reversible computing systems requires | The design and implementation of efficient algorithms for reversible computing systems requires unconventional ways of thinking. Memoization is a classic program optimization technique that stores computation results in memory. How memoization can be made reversible without adding unbounded tracing is not immediately clear. This work-in-progress presention discusses a unconventional solution using cyclic state transition systems to memoize reversible recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama. | ||
Latest revision as of 11:59, 10 August 2022
The design and implementation of efficient algorithms for reversible computing systems requires unconventional ways of thinking. Memoization is a classic program optimization technique that stores computation results in memory. How memoization can be made reversible without adding unbounded tracing is not immediately clear. This work-in-progress presention discusses a unconventional solution using cyclic state transition systems to memoize reversible recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.
