Super-Linear Speedup by Program Transformation

We investigate the use of repeated unfolding and simplification to achieve super-linear speedup in sequential programs. Our technique of repeated recursion unfolding repeatedly unfolds a recursion with itself and simplifies it while keeping all unfolded rules. Each unfolding doubles the number of recursive steps covered. This reduces the number of recursive steps to its logarithm at the expense of introducing a logarithmic number of unfolded recursive cases to the program. Our optimization can lower the time complexity class of a program if enough simplification in the recursions is possible. The actual runtime improvement quickly reaches several orders of magnitude.

Publications

% % This file was created by the TYPO3 extension % publications % --- Timezone: CEST % Creation date: 2024-03-28 % Creation time: 18:45:42 % --- Number of references % 1 % @Article { fruehwirth2020repeated, author = {Fr\"{u}hwirth, Thom}, title = {Repeated Recursion Unfolding for Super-Linear Speedup within Bounds}, year = {2020}, month = {9}, journal = {Pre-Proceedings of the 30th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2020)}, tags = {Super-Linear Speedup}, file_url = {https://arxiv.org/abs/2009.05314} }