Poster: co-allocation based scheduling for parallel systems

ABSTRACT

State-of-the-art supercomputers are made up of multiple types of resources. User jobs also have wide spectrum of resource requirements. Hence, a supercomputer can be thought of as a collection of heterogeneous resources with heterogeneous usage requirements from the users. Schedulers for such systems are challenged by several issues like scalability, GPU, topology and energy awareness. We view each scheduling step as solving a co-allocation problem, i.e. the problem of allocating multiple resources simultaneously to jobs. Collection of jobs can be repeatedly taken from the front of the job queue (i.e. a window of jobs) and a co-allocation problem formulated as an (integer) linear program (ILP/LP) can be solved. ILP formulations for single-type and multiple instances, a CPU-GPU and generalized systems are provided. Co-allocation solver is applied to both the window of jobs and the backfilled jobs. Simulation results show effectiveness of our approaches when compared with pure first-come-first-served schedulers.

References

1. A. Haydar Özer, C. Özturan, A Model and Heuristic Algorithms for Multi-Unit Nondiscriminatory Combinatorial Auction, Computers and Operations Research, Vol. 36, p. 196--208, 2009.
2. George B. Dantzig, Discrete-Variable Extremum Problems, Operations Research Vol. 5, No. 2, April 1957, pp. 266--288
3. Parallel Workload Archive, http://www.cs.huji.ac.il/labs/parallel/workload/logs.html
4. William TC Kramer, PERCU: A Holistic Method for Evaluating High Performance Computing Systems, Ph.D. thesis, EECS Department, University of California, Berkeley, Nov 2008.
5. Y. Georgiou, Resource and Job Management in High Performance Computing, PhD Thesis, Joseph Fourier University, France, 2010

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Scheduling