Home

Statically Unrolling Recursion to Improve Opportunities for Parallelism

Neil Ashish Deshpande; Stephen A. Edwards; Columbia University. Computer Science

Title:
Statically Unrolling Recursion to Improve Opportunities for Parallelism
Author(s):
Deshpande, Neil Ashish; Edwards, Stephen A.; Columbia University. Computer Science
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-011-12
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:
99
Metadata:
text | xml

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