Master-slave tasking with heterogeneous processors

摘要

In this paper, we revisit the Master-slave tasking paradigm in the context of heterogeneous computing and communication links in exclusive mode. We present a polynomial algorithm for solving this problem when initial communication before the task allocation is needed. We show that when communications are required both before and after the task processing, the problem is at least as difficult as a problem known to be open. In this case, we present a guaranteed approximation algorithm.