Task Scheduling Problem In Distributed Heterogeneous Systems

The distributed heterogeneous system has been used to solve complex applications along with the development of the computer. Distributed heterogeneous system is the coordinated use of various resources with different capabilities to satisfy the requirements of varying task mixtures. The heterogeneity of the resources and tasks in a heterogeneous system is exploited to maximize the performance or the cost-effectiveness of the system. The task scheduling algorithm plays a very important role in enhancing this system's parallel performance and maintaining its load balance. The scheduling problem has turned out to be a NPC problem and optimal solutions can not be found in polynomial time. So, many people make great efforts on finding a better algorithm to find a better solution within limited cost. At present, people often use heuristic algorithm and approximate algorithm.In this paper, we research the task scheduling in master-slave heterogeneous system. We model a collection of heterogeneous resources and the communication links between them as the nodes and edges of an undirected graph. We define and analyze the base model and its steady state operation. For a tree-shaped platform graph, we give a bandwidth-centric scheduling strategy to achieve the optimal steady state.In this paper, we give two task scheduling algorithms in the master-slave heterogeneous system. First we give a heuristic algorithm — IMM algorithm, it can be used to dynamic map independent tasks with priorities and deadline. Then we present a bandwidth-centric asymptotically optimal algorithm according to the steady state of the master-slave heterogeneous system, and we proved its optimality by theory.In this paper, we give simulations to both algorithms. The simulation proved the advantage of the algorithms further.