THE PRELIMINARY ORAL EXAMINATION FOR THE DEGREE OF Ph.D. IN COMPUTER SCIENCE FOR Koyel Mukherjee

The energy costs for cooling a data center constitute a significant portion of the energy costs of running a data center. The cooling problem is exacerbated by the fact that machines are packed densely in a data center and hot spots develop due to imbalanced workloads. In order to keep cooling costs low, one solution is to do thermal aware workload scheduling; in other words assigning jobs to machines not just based on local load, but based on the thermal profile of the data center.

There are currently no formal metrics that model scheduling in a thermal aware environment. We develop scheduling policies with worst case guarantees for this new and relevant scheduling problem. The primary difference with all existing prior work in scheduling is the notion of spatial cross-interference: the heat generated by jobs running on a machine raises its own temperature as well as the temperature of nearby machines due to recirculation effects.

First we consider maximizing the number or profit of jobs that can be assigned with respect to a thermal limit on the machines. We give an approximation algorithm for the maximum number or profit of jobs assigned in the setting of a single rack with multiple machines, assuming a size restriction on jobs. The analysis of the algorithm is asymptotically tight. We then extend our model to include horizontal heat coupling between multiple racks of machines, and provide approximation algorithms for maximizing profits of jobs assigned, for three different heat coupling models assuming a size restriction.

Second we consider the minimization of the maximum temperature (or an equivalent metric), while scheduling all jobs. We analyze two approximation algorithms, the analysis of both are asymptotically tight. Both versions of the problem considered are NP-hard and at best, one can hope to get a polynomial time approximation scheme. Several interesting questions remain which we intend to address in the remainder of the dissertation. 

Examining Committee:

Dr. Samir Khuller                                   -          Chair

Dr. Amol Deshpande                             -          Dept’s Representative

Dr. Aravind Srinivasan                           -          Committee Member       

Dr. David Mount                                    -          Committee Member                               

EVERYBODY IS INVITED TO ATTEND THE PRESENTATION