An Optimal Task Allocation Model for System Cost Analysis in Heterogeneous Distributed Computing Systems: A Heuristic Approach

Distributed computing systems (DCSs), task allocation strategy is an essential phase to minimize the system cost (i.e. the sum of execution and communication costs). To utilize the capabilities of distributed computing system (DCS) for an effective parallelism, the tasks of a parallel program must be properly allocated to the available processors in the system. Inherently, task allocation problem is NP&hard in co mplexity. To overcome this problem, it is necessary to introduce heuristics for generating near optimal solution to the given problem. This paper deals with the problem of task allocation in DCS such that the system cost is minimized. This can be done by minimizing the inter&processor communication cost (IPCC). Ther efore, in this paper we have proposed an algorithm that tries to allocate the tasks to the processors, one by one on the basis of communication link sum (CLS). This type of allocation policy will reduce the inter&processor communication (IPC) and thus minimize the system cost. For an allocation purposes, execution cost of the tasks on each processor and communication cost between the tasks has been taken in the form of matrices.