  We propose a novel job scheduling approach for homogeneous cluster computing
platforms. Its key feature is the use of virtual machine technology to share
fractional node resources in a precise and controlled manner. Other VM-based
scheduling approaches have focused primarily on technical issues or on
extensions to existing batch scheduling systems, while we take a more
aggressive approach and seek to find heuristics that maximize an objective
metric correlated with job performance. We derive absolute performance bounds
and develop algorithms for the online, non-clairvoyant version of our
scheduling problem. We further evaluate these algorithms in simulation against
both synthetic and real-world HPC workloads and compare our algorithms to
standard batch scheduling approaches. We find that our approach improves over
batch scheduling by orders of magnitude in terms of job stretch, while leading
to comparable or better resource utilization. Our results demonstrate that
virtualization technology coupled with lightweight online scheduling strategies
can afford dramatic improvements in performance for executing HPC workloads.
