A clustering algorithm for multiprocessor environments using dynamic priority of modules

Abstract

In this paper, we propose a task allocation algorithm on a fully connected homogeneous multiprocessor environment using dynamic priority of modules. This is a generalization of our earlier work in which we used static priority of modules. Priority of modules is dependent on the computation and the communication times associated with the module as well as the current allocation. Initially the modules are allocated in a single cluster. We take out the modules in decreasing order of priority and recalculate their priorities. In this way we propose a clustering algorithm of complexity O(|V| 2(|V|+|E|)log(|V|+|E|)), and compare it with Sarkar's algorithm.