Static and dynamic load balance strategies for a class of applications

Parallel/distributed systems offer a tremendous processing capacity. However, in order to take full advantage of it, good load distributions are needed. We study the task graph partition problem for a given parallel/distributed application which is modeled using data parallelism and is implemented in a transputer system in a mesh construction. Our approach uses domain partition to separate a given domain into a set of subdomains of equal size and each of which has at most four neighbors. We devise three methods to partition a given domain, these methods are compared based on several criteria. The impact of the number of processors used in implementation is also investigated based on several parameters, including processor speed, communication speed, and amount of computation and communication per data point. We discuss implementation of our approach in the application based on the existing features of the transputer system, and compare different versions of application through running a simulation system.