Study On Load Scheduling Problem In Parallel Systems

Parallel computing is one of the hot spots of current computer science. Parallel and distributed computing is a powerful tool to solve the variety of computing-intensive load scheduling problems. Load scheduling (including load partitioning and distributing) is the key factor of improving the performance of parallel and distributed computing. The load scheduling in parallel system is to distribute the loads with some orders to the processors so as that the total processing time is minimum. It has been proven that this is a NP-hard problem. The current research is to propose approximate algorithms and improve the efficiency of scheduling. This paper addresses on the divisible load scheduling problem without known network resources and present several new efficient algorithms. Our contributions are including:1. Proposed self-adaptive divisible load scheduling algorithms without known network resources. This algorithm presents a new self-adaptive probing technique, uses the non-predetermined probing installment, and can reduce the number of probing installment distributed to the slow nodes according to the status of current network. Compared with existing work, it has better scheduling performance.2. Proposed multiple divisible loads scheduling algorithm in bus-based system without known network resources. The situations of multiple loads appear frequently in reality. Moreover, the single divisible load scheduling can be understood as some multiple divisible load scheduling. With a multi-installment distribution strategy, the utilization of computing power in system is improved significantly.3. Proposed multiple divisible loads scheduling algorithm in single-level tree system without know network resources. The single-level tree model is used extensively in real applications. A large number of real systems can be described as single-level tree model. The proposed algorithms of heterogeneous system based on the single-level tree model can adjust the deviation of current system and invoke the probing phase automatically.The main content of this paper is: the introduction of the background of load scheduling, including parallel computing, general scheduling problems, and the usual solutions; the models of parallel heterogeneous system and current research status; the research of divisible load scheduling algorithms without known network resources; the research of multiple divisible loads scheduling algorithm in bus-based system without known network resources; the research of multiple divisible loads scheduling algorithm in single-level tree system without know network resources; the orientations of future research.