Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.12 No.2, pp.261-275 (June 1996)
Efficient Execution of Parallel Functional
Programs Using Complexity Information

Piyush Maheshwari
School of Computer Science and Engineering
The University of New South Wales
Sydney, NSW 2052, Australia

We discuss some issues of parallelism in functional programs and how to exploit parallelism efficiently by improving the granularity of such programs on a multiprocessor. When evaluating a functional program on a distributed memory system, both data and work must be sensibly located if the time spent on communication is not to dominate the time spent on computation. The major issue is how to choose an optimal grain-size for a particular host machine which can exploit useful parallelism. A program will execute efficiently if its average run-time granularity is large compared to the overhead of task creation. We present a short overview of the LAGER (Larger Grain Reduction) distributed/parallel multiprocessor model for the implementation of functional programming languages. We show how parallel programs can be run more efficiently with prior information concerning the time complexities and relative time complexities of its sub-expressions.

Keywords: functional programming, granularity, graph reduction machine, locality of data structures, parallelism, scheduling, task complexity

Received December 30, 1993; revised September 24, 1995.
Communicated by Chuan-lin Wu.