Keynote/tutorial Lectures

Mor Harchol-Balter

  • Title: New Breakthroughs in Scheduling Theory.
  • Abstract: Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis of different scheduling policies has been the focus of thousands of theoretical papers, results are limited to analyzing a relatively small number of "simple" scheduling policies. 

    In this talk, we introduce the SOAP class of scheduling policies: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in the literature as well as an infinite number of variants which have never been analyzed, or maybe even conceived. SOAP policies include the highly intractable SERPT policy (Shortest-Expected-Remaining-Processing-Time), as well as the famously complex Gittins Index policy. SOAP also includes all sorts of "combination" policies, like a policy that performs Shortest-Job-First on jobs with known size and Foreground-Background scheduling on jobs with unknown size, or a policy that is allowed to preempt jobs only when they hit certain ages. In this talk we present a stochastic response time analysis of all SOAP policies via a single universal framework. If time permits, we will also discuss some open problems in scheduling of current interest.

Bio: Mor Harchol-Balter is a Professor of Computer Science at CMU.  She received her Ph.D. from Mor_Harchol_3.jpgU.C. Berkeley in 1996.  She joined CMU in 1999, and served as the Head of the PhD program from 2008-2011.  Mor is a Fellow of the ACM and a Senior Member of IEEE.  She is a recipient of the McCandless Junior Chair, the NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award.  She has received faculty awards from a dozen companies including Google, Microsoft, IBM, EMC, Facebook, Intel, Yahoo!, and Seagate. Mor's work focuses on designing new resource allocation policies, including load balancing policies, power management policies, and scheduling policies.  Mor is heavily involved in the SIGMETRICS/PERFORMANCE research community, where she has received many best paper awards, and where she served as TPC Chair in 2007, as General Chair in 2013, and as the Keynote Speaker for 2016. She is also the author of a popular textbook, "Performance Analysis and Design of Computer Systems," published by Cambridge University Press, which bridges Operations Research and Computer Science.

Nicolas Gast

  • Title: Mean field and refined mean field approximation.
  • Abstract:  Mean field approximation is a widely used technique to study stochastic systems composed of many interacting objects with applications from theoretical physics to biological models and artificial intelligence. In computer science, mean field approximation has been successfully used to analyze the performance of many distributed algorithms, including allocation strategies in server farms, caching algorithms and wireless protocols.

    This tutorial will be composed of two parts. In the first part, I will introduce the key concepts behind the classical mean field approximation. By using some of the classical models, I will show how the method can be applied and give ideas of where it cannot be applied. In the second part, I will talk about more recent results, first, how accurate is the approximation for finite systems and second, how to use this result to define a refined approximation to make it applicable for a few tens of objects.Nicolas_Gast_2.jpg

Bio:  Nicolas Gast is a tenured research scientist at Inria (Grenoble, France) since 2014. He graduated from Ecole Normale Superieure (Paris, France) in 2007 and received a Ph.D. from the University of Grenoble in 2010. He was a research fellow at EPFL from 2010 to 2014. His research focuses on the development and the use of stochastic models and optimization methods for the design of distributed control algorithms in large-scale systems, with applications to communication networks, computing infrastructures and more recently energy networks (smart grids).

 

Benny Van Houdt (University of Antwerp)

  • Title: A queueing perspective on randomized work sharing vs work stealing
  • Abstract:  Work sharing and work stealing are two fundamental scheduling strategies for (multithreaded) computer systems.  In a work stealing scheduler, each processor maintains a queue of jobs to perform and when a processor
    runs out of jobs, it looks at the queues of other processors and steals one of their pending jobs. In case of a work sharing scheduler, a processor with pending jobs looks at the other processors to see whether there is an idle processor that can perform one of its pending jobs.

    When the load of the system is low, it is obvious that work sharing achieves low response times with low communication overhead as there are many idle processors at all times. In highly loaded systems work stealing is more effective as idle processors can easily locate other processors with pending jobs, while finding an idle processor is much more difficult. It is however unclear which strategy works best in between.

    In this tutorial lecture, we study the performance of work stealing and sharing strategies from a queueing theoretic perspective. In the first part we introduce some basic work stealing and sharing strategies and discuss how to compare their performance in a fair manner. We also present results for large scale systems with exponential job sizes that
    indicate that work sharing is superior to work stealing if the load is less than the golden ratio minus one. In second part of the lecture, we discuss how the job size distribution affects these results and discuss some open problems.

Bio: Benny Van Houdt is a professor at the department of Mathematics and Computer Science at the University of Antwerp where he also obtained his Ph.D. in 2001. He has been a post-doctoral fellow of the FWO-Flanders from October 2001 until October 2007. He is currently the Editor-in-Chief of the Performance Evaluation journal (since Jan 2018), a senior associate editor of ACM ToMPECS (since 2014) and an editorial board member of Stochastic Models (since 2016). He has been a member of the editorial board of Operations Research Letters (2007-2017) and Performance Evaluation (2011-2017).Benny_Van_Houdt_1.png

He has been Technical Program Committee (TPC) co-chair of SMCtools 2006 (Pisa, Italy), MAM8 (Kerala, India), IFIP Performance 2014 (Torino, Italy) and QEST 2016 (Quebec City, Canada) and served on a number of TPCs including ACM Sigmetrics, IFIP Performance, IEEE MASCOTS, INFORMS APS, ITC, QEST, Valuetools, ASMTA, EPEW, etc. Benny is the (co)recipient of various awards including best paper awards at ACM Sigmetrics, IFIP Performance, ITC, QEST and Valuetools. He is an elected member and officer of the IFIP working group 7.3 on Computer System Modeling and has published papers in a variety of journals such as IEEE/ACM Trans. on Networking, IEEE Trans. on Information Theory, Communications, IEEE JSAC, IEEE/OSA JOCN, Performance Evaluation, QUESTA, Journal of Applied Probability, Adv. In Applied Probability, Operations Research Letters, INFORMS JOC, EJOR, Stochastic Models, Computer Networks, Naval Research Logistics, etc.

 

Nahum Shimkin Nahum_Shimkin_3.jpg

  • Title: Dynamic Scheduling for Multiclass Many-server Queues with Abandonment: the $c\mu/\theta$ Rule and its Generalizations.
  • Abstract:  We survey in this talk several results that address the problem of server scheduling in a multiclass many-server queueing system with abandonment, with the purpose of minimizing the long-run average queue length costs and abandonment penalties. Our framework focuses on overloaded systems in the fluid regime. Assuming exponential patience distribution, we discuss the asymptotic optimality of a fixed priority rule, which modifies the standard $c\mu$ priority rule by considering the abandonment rates of the different classes. We further present recent results that address the case of non-exponential patience distribution.

Bio: Nahum Shimkin received his Ph.D. degree from the Faculty of Electrical Engineering at the Technion in 1991. Prior to re-joining the department in 1995 as a faculty member, he was a postdoctoral fellow at the Institute of Mathematics and its Applications in the University of Minnesota, and a senior research engineer in the Israeli defense industry. His research interests include stochastic control and planning, queueing systems, game theoretical analysis of multi-user systems, and reinforcement learning. He previously served as president of the Israeli Association for Automatic Control, and vice-president of the Operations Research Society of Israel. Since January 2018 he serves as Dean of the Technion’s Viterbi Faculty of Electrical Engineering.

 
 
 

 

 
Online user: 1