Graduate Exam Abstract

Kyle Tarplee

Ph.D. Preliminary

April 3, 2014, 8:00-10:00AM

ECE Conference Room

Highly Scalable Algorithms For Scheduling Tasks on Heterogeneous Computing Systems

Abstract: As high performance computing systems increase in size, new and more efficient algorithms are needed to both schedule work on the machines and to understand the performance trade-offs inherit in the system. The size of the workload and the number of machines in a high performance computing system is growing rapidly. The extreme scale of these newer systems requires unique task scheduling algorithms that are capable of handling millions of tasks and thousands of machines. A highly scalable scheduling algorithm is developed that computes high quality schedules, especially for large problem sizes, and computes bounds on the makespan. Large-scale computing systems also consume vast amounts of electricity, leading to high operating costs. System administrators are trying to simultaneously reduce operating costs and offer state- of-the-art performance. However, system run time performance and energy consumption are often conflicting objectives. Highly scalable algorithms are necessary to schedule tasks efficiently and to help system administrators gain insight into the energy/performance trade-off of the system. Through the use of intelligent resource allocation techniques, system administrators can examine this trade-off space to quantify how much a given performance level will cost in electricity, or see what kind of performance can be expected when given an energy budget. Novel algorithms are developed that efficiently compute high quality solutions for both energy and makespan. These solutions are used to tightly bound the Pareto front to easily trade-off energy and performance. These algorithms are shown to be highly scalable in terms of solution quality and computation time compared to existing algorithms. Trading-off energy and makespan is often difficult for companies because it is unclear how each affects the profit of a company. A monetary-based model of high performance computing is presented. A highly scalable algorithm is then developed to quickly find the schedule that maximizes the profit per unit time as well as bounding the quality of the solution.

Adviser: Anthony A. Maciejewski
Co-Adviser: n/a
Non-ECE Member: Dan Bates, Math Department
Member 3: Howard Jay Siegel
Addional Members: Edwin Chong

Kyle M. Tarplee, Ryan Friese, Anthony A. Maciejewski, and Howard Jay Siegel, "Efficient and Scalable Computation of the Energy and Makespan Pareto Front for Heterogeneous Computing Systems" 6th Workshop on Computational Optimization (WCO 2013), in the proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS 2013), cosponsors: Polskie Towaszystwo Informatycznq (PTI), iBS PAN, AGH University of Science and Technology, and Wroclaw University of Economics (UE), Krakow, Poland, Sep. 2013.

Kyle M. Tarplee, Ryan Friese, Anthony A. Maciejewski, and Howard Jay Siegel "Efficient and Scalable Pareto Front Generation for Energy and Makespan in Heterogeneous Computing Systems" book chapter, Studies in Computational Intelligence, Springer, to appear

Kyle M. Tarplee, Anthony A. Maciejewski, and Howard Jay Siegel, "Energy-Aware Profit Maximizing Scheduling Algorithm for Heterogeneous Computing Systems" Cluster, Cloud and Grid Computing (CCGrid), 2014 14th IEEE/ACM International Symposium, ExtremeGreen Workshop, to appear

Program of Study:
MATH 510
ECE 501
ECE 516
ECE 555
ECE 658
ECE 666