JISE


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


Journal of Information Science and Engineering, Vol. 12 No. 2, pp. 261-275


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

  Retrieve PDF document (JISE_199602_05.pdf)