Responsive Parallelism with Dynamic and First-Class Priorities

Abstract

PriML, a language developed in recent work on responsive parallelism , extends traditional fine-grained parallel languages such as Cilk by allowing programmers to annotate threads with priorities . Programmers thus get the substantial throughput benefits of lightweight threads scheduled by a user-level runtime, while retaining the ability to use threads for responsive applications typically programmed with lower-level threading systems. PriML’s type system guarantees the absence of priority inversions , costly performance errors in which high-priority threads are delayed by low-priority threads, enabling formal bounds on throughput and responsiveness, but at the cost of expressiveness: threads may not change priority once spawned and the priority of a thread is specified as a priority literal in the code ( i.e ., priorities are not first-class). This work relaxes the two assumptions above by tracking sets of priorities using techniques drawn from the literature on refinement types. We extend the graph-based cost models of responsive parallelism to incorporate first-class and changing priorities, and prove bounds on the throughput and responsiveness of well-typed programs in our extended language. We implement our type system extensions in the PriML compiler, and demonstrate the benefits of the extension using a concurrent web server as a case study.