Give


Graduate Exam Abstract


Kyle Tarplee

Ph.D. Final

April 16, 2015, 9:00 am - 11:00 am

ECE Conference Room

Highly Scalable Algorithms For Scheduling Tasks and Provisioning Machines on Heterogeneous Computing Systems


Abstract: As high performance computing systems increase in size, new and more efficient algorithms are needed to schedule work on the machines, understand the performance trade-offs inherit in the system, and determine which machines to provision. 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. Large-scale computing systems also consume vast amounts of electricity, leading to high operating costs. Through the use of novel 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 that can be expected when given an energy budget. Trading-off energy and makespan is often difficult for companies because it is unclear how each affects the profit. A monetary- based model of high performance computing is presented and a highly scalable algorithm is developed to quickly find the schedule that maximizes the profit per unit time. Cloud computing has made it possible to provision machines that are best suited to a particular workload. An algorithm is designed to find the best set of computing resources to allocate to the workload that takes into account the uncertainty in the task arrival rates, task execution times, and power consumption. Reward rate, cost, failure rate, and power consumption can be optimized, as desired, to optimally trade- off these conflicting objectives.

Adviser: Anthony A. Maciejewski
Co-Adviser:
Non-ECE Member: Dan Bates, Mathematics
Member 3: Howard Jay Siegel
Addional Members: Edwin Chong

Publications:
Efficient and Scalable Computation of the Energy and Makespan Pareto Front for Heterogeneous Computing Systems.
Kyle M. Tarplee, Ryan Friese, Anthony A. Maciejewski, and Howard Jay Siegel,
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.

Energy-Aware Profit Maximizing Scheduling Algorithm for Heterogeneous Computing Systems.
Kyle M. Tarplee, Anthony A. Maciejewski, and Howard Jay Siegel,
Extreme Green and Energy Efficiency in Large Scale Distributed Systems Workshop (ExtremeGreen 2014), cosponsors: IEEE Computer Society and the ACM, in the proceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2014), Chicago, IL, May 2014

Efficient and Scalable Pareto Front Generation for Energy and Makespan in Heterogeneous Computing Systems.
Kyle M. Tarplee, Ryan Friese, Anthony A. Maciejewski, and Howard Jay Siegel,
in Recent Advances in Computational Optimization, Studies in Computational Intelligence Series, Springer, 2015

Kyle M. Tarplee, Ryan Friese, Anthony A. Maciejewski, and Howard Jay Siegel. Scalable linear programming based resource allocation for makespan minimization in heterogeneous computing systems. under journal review, Submitted 2014.

Kyle M. Tarplee, Ryan Friese, Anthony A. Maciejewski, and Howard Jay Siegel. Energy and makespan tradeoffs in heterogeneous computing systems using efficient linear programming techniques. under journal review, 2014.

Kyle M. Tarplee, Anthony A. Maciejewski, and Howard Jay Siegel. Robust performance-based resource provisioning using a steady state model for multi-objective stochastic programming. under journal review, 2015


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