Computer Science Department
School of Computer Science, Carnegie Mellon University


Responsive Parallel Computation:
Bridging Competitive and Cooperative Threading

Stefan K. Muller, Umut A. Acar, Robert Harper

June 2017


A version of this work appears in the
Proceedings of the ACM SIGPLAN
Conference on Programming Language Design and Implementation (PLDI 2017)

Keywords: Parallelism, Cost Models, Cost Semantics, Operational Semantics, Scheduling

Competitive and cooperative threading are widely used abstractions in computing. In competitive threading, threads are scheduled preemptively with the goal of minimizing response time, usually of interactive applications. In cooperative threading, threads are scheduled non-preemptively with the goal of maximizing throughput or minimizing the completion time, usually in compute-intensive applications, e.g. scientific computing, machine learning and AI.

Although both of these forms of threading rely on the same abstraction of a thread, they have, to date, remained largely separate forms of computing. Motivated by the recent increase in the mainstream use of multicore computers, we propose a threading model that aims to unify competitive and cooperative threading. To this end, we extend the classic graph-based cost model for cooperative threading to allow for competitive threading, and describe how such a cost model may be used in a programming language by presenting a language and a corresponding cost semantics. Finally, we show that the cost model and the semantics are realizable by presenting an operational semantics for the language that specifies the behavior of an implementation, as well as an implementation and a small empirical evaluation.

44 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by