On finding optimal clusterings of task graphs

Currently, many parallel algorithms are defined for shared-memory architectures. The preferred machine model is the PRAM. But, this model does not take into account properties of existing architectures that have a distributed memory and an asynchronous execution model. A transformation of PRAM programs into distributed, asynchronous ones is known. In order to produce not only correct but also efficient code the tasks have to be clustered. We introduce a parallel algorithm producing an optimal clustering for coarse grained task graphs with respect to the execution time on an asynchronous distributed random access machine, the A-DRAM. This machine model assumes distributed memory, asynchronous execution of tasks, computation costs, and communication delay. 1 Introduction The PRAM-model consists of a shared memory and a number of processors with local memory. Processors only communicate via their shared memory. The computation steps are performed in a synchronous lockstep manner. Memory ...