Improving task scheduling for larger grain execution of parallel functional programs

When evaluating a parallel functional program on a distributed 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 author shows how the asymptotic complexity estimations of execution time of the task and communication costs involved in copying the data structures can help in scheduling for better parallel execution on the larger grain distributed multiprocessor machine. The overall parallel execution time of parent task can be minimized if the compiler schedules the subtasks in some particular order (priority). Oriented scheduling of the tasks, determined by the priorities based on the relative time complexities, shows further improvement on the runtime dynamic load balancing methods, and better utilization of the resources. It is shown how some parallel programs can be run more efficiently with the prior information of time complexities and relative time complexities of its subexpressions with the help of analytical reasoning and some practical examples on the larger grain distributed multiprocessor machine LAGER