Size-Based Scheduling: From Theory To Practice, And Back

Type of event: 
SophiaTech networks seminar
Matteo Dell'Amico
Speaker's affiliation: 
Thu, 2014-04-24 14:30 - 15:30
EURECOM, room 101
Refreshments/coffee will be served after the talk. The SophiaTech Networks seminar is sponsored by the labex UCN@Sophia.

The proof that the best response time in queuing systems is obtained by scheduling the jobs with the shortest remaining processing time dates back to 1966; since then, other size-based scheduling protocols that pair near-optimal response times with strong fairness guarantees have been proposed. Yet, despite these very desirable properties, size-based scheduling policies are almost never used in practice: a key reason is that, in real systems, it is prohibitive to know a priori exact job sizes.
In this talk, I will first describe our efforts to put in practice concepts coming from theory, developing HFSP: a size-based scheduler for Hadoop MapReduce that uses estimations rather than exact size information. We obtained results that were surprisingly good even with very inaccurate size estimations: this motivated us to return to theory, and perform an in-depth study of scheduling based on estimated sizes. We obtained very promising results: for a large class of workloads, size-based scheduling performs well even with very rough size estimations; for the other workloads, simple modifications to the existing scheduling protocols are sufficient to greatly enhance performance.
Speaker's bio:
Matteo Dell'Amico is a researcher at EURECOM. His research interests cover "big-data" scalable computing, peer-to-peer systems, recommender systems, computer security, and distributed systems in general.

Google calendar information:
All events (since Nov. 2013) are added to the Sophia-networking google calendar (public). Add it to your calendar by copy-pasting the xml feed address or the iCal address into your favorite software!