Exploiting the Knowledge of Tasks Structure for Distributed Allocation

The aim of this paper is to evaluate the advantages in task allocation that derive from knowledge of the structure of a task, here modeled by an application graph. We will show how the information contained in the application graph can be embedded inside an allocator in order to guide its choices in a way that minimizes the overall response time of the task. We then propose two allocation algorithms which use knowledge of the application graph and measurement of the current system workload in a heuristic formulation and aim to minimize the task's response time. The presented algorithms, differing in the degree of detail with which they evaluate the effect of concurrence between modules allocated on the same host, have been implemented and evaluated in a real heterogeneous distributed system