Joonseon Ahn et al. Joonseon Ahn, Taisook Han (KAIST)

Analysis of Parallelism in Recursive Functions
on Recursive Data Structures

Joonseon Ahn - Taisook Han

Computer Science Department and AITrc
Korea Advanced Institute of Science and Technology
373-1, Kusung-dong, Yusung-gu, Taejon, 305-701, Republic of Korea

jsahn@pllab.kaist.ac.kr, han@cs.kaist.ac.kr

Abstract:

In functional languages, iterative operations on data collections are naturally expressed using recursive functions on recursive data structures. In this paper, we present a method to extract data parallelism from recursive functions and generate data parallel programs.

As the parallel model for object programs, we use polytypic parallel skeletons. This model can express data parallel operations on general recursive data structures. With this model, we can extract data parallelism from recursive functions on general recursive structures such as trees and lists.

To extract appropriate computations for each parallel skeleton from an input function, we classify all subexpressions in the function body based on their conditions of parallel execution. Then, a data parallel program is generated from the classified expressions of the function. Comparing our analytical approach with previous calculational approaches, our approach can parallelize more general recursive functions with complex data flow.