Divide-and-conquer and parallel graph reduction (Q1175201)

A transputer based parallel graph reduction system is described for the execution of functional programs following the divide-and-conquer- paradigm. The main idea is called dynamic partitioning, which refers to the maximum level of recursion up to which the system tries to solve subtasks in parallel and after which execution continues sequentially. Several experimental results on a mesh of 16 transputers are presented and discussed taking into account execution times, load balancing and task distribution. Based on the results obtained suggestions are made w.r.t. the partitioning depending on some characteristic properties of the programs.