ABSTRACT: A fundamental characteristic of existing job schedulers for supercomputers is that they are static, i.e., once a job is allocated a set of processors, it continues to use those processors until it finishes execution. Under static scheduling, jobs will not be scheduled for execution until the number of processors requested by that job is available. This commonly leads to jobs stuck in the queue because they require slightly more processors than are currently available. A more flexible scheduler is to expand or contract the number of processors used at runtime to eliminate this frequent scenario. This is the broad them of the research described in this poster presentation, namely dynamically reconfiguring or resizing parallel applications.
The present project builds on a scheduler and runtime library know as ReSHAPE. Under this framework, a scheduler may change the number of processors assigned to certain resizable (or “malleable”) applications. The contribution of the research described in this presentation is twofold: 1) to examine the characteristics of real workload, gathered from a production supercomputer cluster; and 2) to predict the potential impact on cluster utilization and individual job turnaround times if ReSHAPE were applied to such workloads.
System X Data Set
In order to evaluate the potential of dynamic resizing in a realistic setting, we gathered data from an entire year of jobs submitted to System X, a large production cluster at Virginia Tech. We focus most closely on a subset of the data, corresponding to a “steady state,” i.e., avoiding downtimes, as well as cool-down and warm-up periods before and after downtimes, respectively. Our main data set consists of 1811 jobs submitted over a 49 day period from August 12 to September 29, 2009. We summarize the properties of this workload in terms of job size (number of processors requested, predicted running time, actual running time) and with respect to arrival rates and patterns. Although overall utilization of the cluster during this period was almost 90%, we find that there are still noticeable opportunities to harvest substantial numbers of unused processors, if a system like ReSHAPE were in place.
Potential Impact of Resizing
To evaluate the potential of ReSHAPE on the System X data set, we implemented a simulator that predicts performance on the given workload, under various assumptions about resizability. The simulator uses a simple “FIFO plus backfill” scheduling scenario, and allows us to experiment with various factors that affect the performance of jobs scheduled by a ReSHAPE-enabled scheduler. The three factors we focus on here are the policy used (e.g., favoring resizing of running jobs or favoring scheduling new jobs from the queue), the percentage r of jobs that are potentially resizable, and the factor by which resized applications can effectively use additional processors.
Our results show that cluster utilization steadily grows, as expected, with increasing r from 90.7% to 97.5% as r is increased from 0 to 100. Furthermore, with small values of r, the improvements in running time for the resizable jobs are significant. For example, with r = 10, the mean execution time for the resizable subset of the largest 954 jobs drops by 23.3% as compared to the time with no resizing in place. At the same time, the negative impact on the non-resizable jobs is small. For example, in the r = 10 case, the wait time for the non-resizable jobs increases by 6.9%, and the total turnaround time for these jobs increases by only 1.7%. However, under realistic assumptions about the parallel efficiency of applications run on larger sets of processors, we see that the queue waiting time and hence the overall turnaround time of most jobs starts to deteriorate as r increases. This is not surprising, since “too much” resizing means that the scheduler is more often giving extra processors to jobs that may not be able to use them well. Our results show that resizing only a small percentage of jobs (e.g., 10-25%), and resizing only relatively large jobs (e.g., ones whose cpu*time product exceeds some threshold) yield the best results.
We also present results that measure the impact of varying the scheduling scenario to favor running jobs over queued jobs (our default scenario only gives extra processes to running jobs if no waiting jobs can be scheduled). We find that this approach improves the turnaround time for a small subset of large jobs, but only by about 2%. The benefits are greater if the resized jobs can use additional processes more efficiently, e.g., embarrassingly parallel jobs. We quantify the sensitivity of our results with respect to this parameter.
Our results show that even with simple scheduling policies, resizing with the ReSHAPE framework can lead to significant gains without substantially hurting non-resizable jobs. Many factors influence the size of these gains, but reasonable restrictions lead to favorable results.