A Higher Order Parallel Abstraction for Fixed Degree Divide and Conquer Problem Solving Strategy

In this paper, we present, an algorithmic frame work for the Fixed Degree Divide & Conqrrer(FDDC) problem solving strategy, that adapts the divide and conquer algorithm for parallel computations. We capture the notion of a thread of execution in a:) sc-tive task object which are instances of a data type called the tasktype and propose a higher order tasking abstraction called maptask till that takes as its arguments, a tasktype, the (fixed) degree of the runtime task hierarchy and the arguments for the tasks. We have implemented the above abstraction by extending C with task-type and maptask in a package called the CT Kernel that currently executes tasks in a distributed environment consisting of 10 networked VAXstations. Using the above abstractions we have implemented the FDDC algoritlims for merge!ort, FFT, Cubic spline bmed curve fitting, Fractals, Matxix multiplication, as well as Iterative relaxation