Home

Statically Unrolling Recursion to Improve Opportunities for Parallelism

Neil Ashish Deshpande; Stephen A. Edwards

Title:
Statically Unrolling Recursion to Improve Opportunities for Parallelism
Author(s):
Deshpande, Neil Ashish
Edwards, Stephen A.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-011-12
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
We present an algorithm for unrolling recursion in the Haskell functional language. Adapted from a similar algorithm proposed by Rugina and Rinard for imperative languages, it essentially inlines a function in itself as many times as requested. This algorithm aims to increase the available parallelism in recursive functions, with an eye toward its eventual application in a Haskell-to-hardware compiler. We first illustrate the technique on a series of examples, then describe the algorithm, and finally show its Haskell source, which operates as a plug-in for the Glasgow Haskell Compiler.
Subject(s):
Computer science
Item views:
96
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use