Research On Scheduling For Clusters

Performance is a key point for applications, and it always resorts to scheduling. With the development of computer architecture and increasing of computing demand, scheduling holds new connotation and challenge. It remains as the hotspot of the research of parallel and distributed computing. In term of partition manner, parallel applications can be divided into two types: task parallel and data parallel. DAG is the most common model for task parallel application. For data parallel, one important subtype is called divisible load application (DLA). Applications of this type have load which can be divided into arbitrary amount with arbitrary size, while each load fragment can be handled independently. This paper addresses the scheduling problem of DAG and DLA on clusters.Classical DAG model treats traditional parallel computer as its target environment, so some of its basic premises won' t continue to be valid in cluster basing on message delivery. Cluster is not so reliable as parallel computer, some even don' t have dedicated communication subsystems. So synchronous high-level communicating interface is used to hide the heterogeneity of the lower-level and improve the reliability of message delivery. Most heuristics for scheduling address asynchronous communication DAG, but they are not suitable for the synchronous ones. This paper examined the impact of synchronous communication on DAG model, and proposed PRGSC algorithm. It avoids the deadlock caused by the synchronous communication, but also it could alleviate impact of synchronous communicating delay. Simulation showed that the PRGSC algorithm has better performance than other algorithms which deal with the same type of problems.Previous researches on DLA suppose that the load fragments don' t intersect. In reality, however, the load fragments always overlap or some additional message should be transported to workers. This paper denoted these added information as control information. Divisible load scheduling with control information was considered in this paper, on the master with and without front-end respectively. We revised three efficient-proved schemes: equal allocation, LIFO and FIFO under the extended model. Closed-form solutions for the processing time of these schemes are derived. Based on these expressions, we analyzed the effect of control information on DLS scheduling strategies. We derived the necessary and sufficient condition for the best processor number. We then rigorously compared the performance of the three schemes, and proved that FIFO is always the best not as without control information whether has front-end or not.In DLA scheduling, we can also detail two strategies. One is one-round strategy, which the workers receive the whole needed load before computing. The other is multi-round strategy, which the fragment are sent to worker in different times. Due to the multi round distribution strategy, it can overlap the computing and communication phases on the same worker, thus alleviating the response time of the whole application. Whereas, multi-round strategy is more complicated, and previous research overlooked the transportation of result. This paper proposed a CAMR heuristic for the collection-aware scheduling problem. It lowered the whole responding time through transmitting input data and receiving result alternately. Experimental studies showed that CAMR has better performance than the well-known LIFO and FIFO algorithms.