Multi-threaded programs have traditionally fallen into one of two domains: cooperative and competitive. These two domains have traditionally remained mostly disjoint, with cooperative threading used for increasing throughput in compute-intensive applications such as scientific workloads and cooperative threading used for increasing responsiveness in interactive applications such as GUIs and games. As multicore hardware becomes increasingly mainstream, there is a need for bridging these two disjoint worlds, because many applications mix interaction and computation and would benefit from both cooperative and competitive threading.
In this paper, we present techniques for programming and reasoning about parallel interactive applications that can use both cooperative and competitive threading. Our techniques enable the programmer to write rich parallel interactive programs by creating and synchronizing with threads as needed, and by assigning threads user-defined and partially ordered priorities. To ensure important responsiveness properties, we present a modal type system analogous to S4 modal logic that precludes low-priority threads from delaying high-priority threads, thereby statically preventing a crucial set of priority-inversion bugs. We then present a cost model that allows reasoning about responsiveness and completion time of well-typed programs. The cost model extends the traditional work-span model for cooperative threading to account for competitive scheduling decisions needed to ensure responsiveness. Finally, we show that our proposed techniques are realistic by implementing them as an extension to the Standard ML language.
Tue 25 SepDisplayed time zone: Guadalajara, Mexico City, Monterrey change
10:30 - 12:00
|Competitive Parallelism: Getting Your Priorities Right
|Static Interpretation of Higher-Order Modules in Futhark: Functional GPU Programming in the Large
Martin Elsman University of Copenhagen, Denmark, Troels Henriksen University of Copenhagen, Denmark, Danil Annenkov Department of Computer Science, University of Copenhagen, Cosmin Oancea University of Copenhagen, DenmarkLink to publication DOI
|Finitary Polymorphism for Optimizing Type-Directed Compilation
Atsushi Ohori Tohoku University, Japan, Katsuhiro Ueno Tohoku University, Hisayuki Mima Tohoku UniversityDOI
|Fault Tolerant Functional Reactive Programming (Functional Pearl)
Ivan Perez National Institute of Aerospace, USADOI