Dynamic Resource Management for Parallel Applications in an Autonomous Cluster of Workstations
Clusters of Workstations offer high performance compared to their cost. Unless specifically set up with job control, these clusters operate as autonomous systems, where each of the nodes runs its own copy of the operating system and makes its own scheduling decisions, access to machines is not controlled, and all users enjoy the same access privileges. Even though these features are desirable and reduce operating costs, they create adverse effects for parallel applications running on these clusters. Adverse effects are in the form of delays at communication or synchronization points (rendezvous points), which are caused by either load imbalance, i.e., disproportional load to resource assignment, or by scheduling skew, i.e., timing of allocated resources. While these two issues have been addressed in the past independently and in isolation, no prior study addresses these two issues simultaneously despite the fact that they are likely to occur together, particularly in multiprogrammed environments.
We present an automatic resource allocation and scheduling technique aimed at reducing wait time for parallel applications while maintaining the fairness of scheduling decisions. We use access information from the compiler along with fair and coordinated scheduling to aid the runtime system in dynamically balancing load (while maintaining locality) based on resource availability. The novelty in our approach, besides being the first to address both causes, is to introduce fairness in resource allocation. The system requires little or no programmer interaction for many classes of applications. The outcome of our techniques is not only to reduce the execution time of the parallel application, but also to increase the throughput of the cluster overall.