Optimal task allocation in distributed systems by graph matching and state space search

Abstract

We consider the problem of finding an optimal allocation of tasks onto processors of a distributed computing system. The processors need not have any particular inter-connection structure. We consider two models, one in which no precedence relations exist between tasks, and another in which there are precedence relations between tasks. Each task causes two types of costs to be incurred by the processor to which it is allocated – the execution cost of the task (which varies from processor to processor in a heterogeneous system), and communication cost when the task has to communicate with other tasks which are not allocated to the same processor.

The aim of the task allocation (problem) is to minimize the total turnaround time of all tasks put together. This problem is known to be NP-hard when there are more than three processors. We use a state space search technique – the A^* algorithm to obtain an optimal allocation. We propose a method to reduce the number of nodes generated in the state space search tree. We compare our algorithm for the optimal task allocation problem with that of similar existing algorithms, and show its effectiveness by performing extensive simulations over a wide range of parameters.

Introduction

Distributed computing systems have become very popular these days due to the rapid decline in hardware costs. There are two main reasons why one would opt for a distributed system. First, it makes good economic sense to share a number of resources among many users rather than have each of these resources be duplicated at every site. The other reason is that there are many applications which would normally take a long time to finish execution on one processor. If these applications could be divided into a number of tasks and executed in parallel on different processors, there would be a tremendous improvement in performance. However, to exploit the latter advantage, the tasks have to be assigned carefully to suitable processors. A task takes a certain amount of time to execute on a particular processor. (In a heterogeneous system, it varies from processor to processor.) It is called the execution cost of the task on a particular processor. A task also has to send intermediate data to other tasks and exchange control messages, and so a communication cost is incurred, which again varies depending on the capacities of links between processors. The task allocation problem (also referred to as task assignment problem) is concerned with allocating the tasks to processors in a cost-effective manner, i.e. the goal is to minimize the turnaround time of the processors. (By turnaround time of a processor, we mean the total time the processor takes to complete the work allotted to it. It includes both execution time and communication time.) Achieving this goal requires a balance between two conflicting criteria. Assigning all tasks to one or two processors may appear to be the best way to eliminate communication costs. But this means one processor would be heavily loaded; if the tasks are distributed on as many processors as possible, the load on each processor would be more evenly balanced, but at the same time it increases communication costs. Hence there is a trade-off involved.

Our work concentrates on determining an optimal task allocation that leads to minimum turnaround time possible. This is known to be an NP-hard problem when there are more than two processors (Stone, 1977). Solution techniques for the task allocation problem in distributed computing systems can be classified into three broad categories: graph-theoretic methods (Bokhari, 1979; Bokhari, 1981; Stone, 1977; Stone, 1978; Stone and Bokhari, 1978), integer 0–1 programming techniques (Chern et al., 1989; Chu et al., 1980) and heuristic methods (Efe, 1982; Lo, 1982). Shen and Tsai (1985) formulated task assignment as a graph-matching problem and used a state-space search method (A^* algorithm) to solve it. Their model considered communicating tasks, but did not take into account precedence relations between tasks. Wang and Tsai (1988) extended the model to include precedence relations also. Chen and Yur (1990) used the same model but better heuristics to estimate the cost of assignment at each node in the search tree. Ramakrishnan et al. (1993) proposed a hybrid strategy, incorporating max-flow/min-cut techniques used by Stone (1977) to solve the assignment problem considered by Shen and Tsai (1985). In this paper, we propose a technique whereby the state space search can be drastically reduced by allocating independent tasks last. Sinclair (1987) had followed a similar approach, but there the model had it's aim as to minimize the sum of total costs at all processors combined. In our case it is not a straightforward matter to incorporate task independence properties because our goal is to minimize the turnaround time of the maximum loaded processor. We have successfully incorporated the techniques which exploit task independence properties in both models, the one originally proposed by Shen and Tsai (1985) which does not take into account precedence relations between tasks, and also the extended model of Wang and Tsai (1988) which considers precedence relations between tasks. Henceforth the two models will be referred to as Model A and Model B, respectively. To demonstrate the effectiveness of our proposed algorithms (for Model A and Model B), extensive experimental studies were conducted and the algorithms were compared with the above mentioned algorithms (Shen and Tsai, 1985; Wang and Tsai, 1988). For Model A, the comparison was with Shen and Tsai's algorithm (Shen and Tsai, 1985) and with A^* algorithm such that h(x)=0. For Model B the comparison was with Wang and Tsai's algorithm (Wang and Tsai, 1988), the two algorithms proposed by Chen and Yur (1990), and again with $\text{A}{}^{\mathrm{\ast }}$ algorithm such that h(x)=0. Statistics were taken after varying different parameters such as number of processors, number of tasks, average execution to communication cost ratio, and shapes of the task graphs.

The remainder of this paper is organized as follows. In Section 2the assumptions are stated first and then the problem is defined, paying particular attention to the cost function. Section 3reviews graph matching and state space search using $\text{A}{}^{\mathrm{\ast }}$ algorithm. It briefly describes the existing algorithms (mentioned above) and also explains how our algorithms improve the existing algorithms. Illustrative examples are shown in Section 4. Section 5presents the experimental results. Finally, some concluding remarks are made in Section 6.