AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

A Clustering Heuristic for Multiprocessor Environments Using Computation and Communication Loads of Modules


Affiliations
1 Department of Computer Science, Banaras Hindu University, Varanasi, India
2 Department of Computer Science, School of Management Sciences, Varanasi, India
3 Department of Computer Engineering, Institute of Technology, Banaras Hindu University, Varanasi, India
 

In this paper, we have developed a heuristic for the task allocation problem on a fully connected homogeneous multiprocessor environment. Our heuristic is based on a value associated with the modules called the Computation-Communication-Load (CCLoad). This value is dependent on the computation and the communication times associated with the module. Using the concept of CCLoad, we propose a clustering algorithm of complexity O(|V|2(|V|+|E|)log(|V|+|E|)), and demonstrate its superiority over a generic version of Sarkar's algorithm.

Keywords

Clustering, Distributed Computing, Homogeneous Systems, Task Allocation.
User
Notifications
Font Size

Abstract Views: 528

PDF Views: 226




  • A Clustering Heuristic for Multiprocessor Environments Using Computation and Communication Loads of Modules

Abstract Views: 528  |  PDF Views: 226

Authors

Pramod Kumar Mishra
Department of Computer Science, Banaras Hindu University, Varanasi, India
Kamal Sheel Mishra
Department of Computer Science, School of Management Sciences, Varanasi, India
Abhishek Mishra
Department of Computer Engineering, Institute of Technology, Banaras Hindu University, Varanasi, India

Abstract


In this paper, we have developed a heuristic for the task allocation problem on a fully connected homogeneous multiprocessor environment. Our heuristic is based on a value associated with the modules called the Computation-Communication-Load (CCLoad). This value is dependent on the computation and the communication times associated with the module. Using the concept of CCLoad, we propose a clustering algorithm of complexity O(|V|2(|V|+|E|)log(|V|+|E|)), and demonstrate its superiority over a generic version of Sarkar's algorithm.

Keywords


Clustering, Distributed Computing, Homogeneous Systems, Task Allocation.