Researching On Multi-processor Job Scheduling In Network Parallel Computing Systems

As the advance of the network technology and parallel computing technology, the network parallel computing technology has been founded, and has been developed rapidly for its more eminent properities such as intensive scope, high performance and cheap price etc. At present, the typical example is the cluster based on the local area network and grid based on the wide area network. Through the speedy network, they integrated all shared resources including CPU, storage and database etc. located in different geographic places, and as the result the high performance computing, management and service have been provided. Network parallel computing (NPC) has become an important development direction in the field of parallel computing. With the application and popularization of the NPC system, and the increasing requirement and complexity of heterogeneous environment, a series of challenges has been raised for the workers in the field.This paper has made the research thoroughly on the job schedule policy and algorithm in the NPC system. Firstly, introduced the schedule model based on multiprocessor job in the NPC system. The article has made some exploration and innovation based on the prevoius works, and established and developed some new results. The innovative works of the author have been laid down:1. In the overall scheduling, NPC system has been considered with the heterogeneous multi-processor system. According to the computing capability of processor, communication relation among the processors and the different requirement of the every job, the multiprocessor jobs have been defined. So as to the multiprocessor job scheduling model Pm|set|Cmax has been got in NPC system. Approximation optimizing problem of this scheduling model has also been discussed theoretically.Based on the strong NP-hard problem, the article has proofed it impossible to get a polynomial schedule algorithm with constant number of the approximation ratio. At the same time, through the analysis of the parallel relation among the multiprocessor parallel job, the low bound of the optimal schedule has been provided.2. The normal scheduling in the 3-processor system has been researched. Through the compare the time-length relation of the six normal job, a simplest schedule algorithm appeared, its schedule makespan did not exceeded the 5/4 of the optimal schedule, and proofed it to be the practicable optimal normal scheduling. And then, on the base of the normal scheduling, through the method of the Partition and Semi-normal scheduling, improved the best result 7/6 hold by Goeman's for many years in the 3-processor system to 9/8.3. Researching the normal scheduling in 4-processor system. Based on the Group Scheduling, improving the gaps combination among processors, fully using gaps to the partial schedule, constructting a series of linear algorithm. The continuous improvement of normal scheduling in 4-processor system, and getting the approximately ratio:2, 5/3 , 3/2 and 4/3 repectively. And proofed 4/3 is the optimal normal scheduling result by practice.4. Researching the schedule based on the multiprocessor parallel job in the more processors NPC system. Providing the simple and feasible processor assignment method, and three heuristic schedule algorithms with polynomial time: LLF, LWF and LAF, whose strengths and weaknesses have been described by the simulation experiment.