Research on parallel computing has historically revolved around compute-intensive applications drawn from traditional areas such as high-performance computing. With the growing availability and usage of multicore chips, applications of parallel computing now include interactive parallel applications that mix compute-intensive tasks with interaction, e.g., with the user or more generally with the external world. Recent theoretical work on responsive parallelism presents abstract cost models and type systems for ensuring and reasoning about responsiveness and throughput of such interactive parallel programs.
In this paper, we extend prior work by considering a crucial metric: fairness. To express rich interactive parallel programs, we allow programmers to assign priorities to threads and instruct the scheduler to obey a notion of fairness. We then propose the fairly prompt scheduling principle for executing such programs; the principle specifies the schedule for multithreaded programs on multiple processors. For such schedules, we prove theoretical bounds on the execution and response times of jobs of various priorities. In particular, we bound the amount, i.e., stretch, by which a low-priority job can be delayed by higher-priority work. We also present an algorithm designed to approximate the fairly prompt scheduling principle on modern multicore computers, implement the algorithm by extending the Standard ML language, and present an empirical evaluation.
Mon 19 AugDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
10:30 - 12:00
|Rebuilding Racket on Chez Scheme (Experience Report)
Matthew Flatt University of Utah, Caner Derici Indiana University, R. Kent Dybvig Cisco Systems, Inc, Andy Keep Cisco Systems, Inc, Gustavo E. Massaccesi Universidad de Buenos Aires, Sarah Spall Indiana University, Sam Tobin-Hochstadt Indiana University, Jon ZeppieriLink to publication DOI
|Compiling with Continuations, or without? Whatever.
|Lambda Calculus with Algebraic Simplification for Reduction Parallelization by Equational Reasoning
Akimasa Morihata University of Tokyo
|Fairness in Responsive Parallelism