Multiple Objective Scheduling of HPC Workloads through Dynamic Prioritization

We have developed a very efficient single queue scheduling system that utilizes a greedy knapsack algorithm with dynamic job priorities that satisfies high level objectives while maintaining high utilization of the HPC system or collection of distributed resources such as a computational GRID. We provide simulation analysis of our approach in contrast with scheduling strategies of shortest job first; longest waiting jobs first and large jobs first. Further, we look at the effects of system size on the total workload response time and find that for real work loads, the relationship between response time and system size follows an inverse power law. Further, our approach does not require system administrators or users to identify a specific priority queue for each of their jobs. Our proposed scheduler performs an exhaustive parameter search for a, per job, priority calculation to balance high level objectives and provides guaranteed performance for four classes of jobs in a workload. The system administrator needs only tune the prioritization parameters (knobs) and the system scheduler will behave accordingly,such as reducing wait time for jobs that are above average size with small runtimes. We demonstrate that our approach works very well on workloads that have many independent tasks. We evaluate our scheduler on a realistic scientific data processing mixed workload and realistic HPC workload trace from the parallel workloads archive.