Hierarchical Scheduling in Parallel and Cluster Systems

Parallel job scheduling has been extensively studied over the last two decades of the 20th century. Initial focus of these studies has been on small UMA architectures. More recent interest is in the cluster systems. A job scheduling policy that works effectively for small UMA systems might not work for large distributed-memory systems with thousands of processors. Thus, scalability is an important characteristic of a scheduling policy if we want to use it in large distributed-memory systems. In this book, the author presents a hierarchical scheduling policy to fit in with system size. This policy is based on the hierarchical task queue organization he introduced to organize the system run queue. The book is divided into four parts. Part I gives introduction to parallel and cluster systems. It also provides an overview of parallel job scheduling policies proposed in the literature. Part II gives details about the hierarchical task queue organization and its performance. The author shows that this organization scales well, which makes it suitable for systems with hundreds to thousands of processors.In Part III he uses this task queue organization as the basis to devise hierarchical scheduling policies for shared-memory and distributed-memory parallel systems as well as cluster systems. This part demonstrates that the hierarchical policy provides substantial performance advantages over other policies proposed in the literature. Finally, Part IV concludes the book with a brief summary and concluding remarks.