Although randomized work stealing is effective at automatically load-balancing task-parallel programs, it can waste computational resources when scheduling programs that lack sufficient parallelism to use all available threads. For such programs, threads will waste cycles attempting to steal parallel tasks when none are available. This waste can reduce the machine’s efficiency by wasting computational resources and energy and needlessly burdening the operating system.

In a randomized work-stealing scheduler, parallel speedup depends on the spawn overhead, which workers pay to allow tasks to execute in parallel, and the steal overhead, which thieves pay to start executing new work. The importance of minimizing the spawn overhead in a randomized work-stealing scheduler is first formalized by Frigo et al., coined as the work-first principle [15], which states that one should minimize spawn overhead even at the expense of a larger steal overhead. Since then, many strategies have been proposed to reduce the spawn overhead, which is dominated by maintaining a per-worker double-ended queue, or deque, to keep track of available parallel work.

Modern software is often interactive -- applications communicate frequently with the external world. For such applications, responsiveness -- how quickly they respond to requests -- is as important as throughput. Efficiently implementing these applications using traditional processes or static threads is difficult and error-prone. Task parallelism has the potential to significantly simplify the implementation of these applications -- it allows the programmer to express the high-level logical flow of the program and letting the scheduler handle the low level details of scheduling, synchronization, and asynchronous I/O operations.

Many concurrent programs assign priorities to threads to improve responsiveness. When used in conjunction with synchronization mechanisms such as mutexes and condition variables, however, priorities can lead to priority inversions, in which high-priority threads are delayed by low-priority ones. Priority inversions in the use of mutexes are easily handled using dynamic techniques such as priority inheritance, but priority inversions in the use of condition variables are not well-studied and dynamic techniques are not suitable. In this work, we use a combination of static and dynamic techniques to prevent priority inversion in code that uses mutexes and condition variables. A type system ensures that condition variables are used safely, even while dynamic techniques change thread priorities at runtime to eliminate priority inversions in the use of mutexes. We prove the soundness of our system, using a model of priority inversions based on cost models for parallel programs. To show that the type system is practical to implement, we encode it within the type systems of Rust and C++, and show that the restrictions are not overly burdensome by writing sizeable case studies using these encodings, including porting the Memcached object server to use our C++ implementation.

Motivated by the increasing shift to multicore computers, recent work has developed language support for responsive parallel applications that mix compute-intensive tasks with latency-sensitive, usually interactive, tasks. These developments include calculi that allow assigning priorities to threads, type systems that can rule out priority inversions, and accompanying cost models for predicting responsiveness. These advances share one important limitation: all of this work assumes purely functional programming. This is a significant restriction, because many realistic interactive applications, from games to robots to web servers, use mutable state, e.g., for communication between threads.

The use of futures can generate arbitrary dependences in the computation, making it difficult to detect races efficiently. Algorithms proposed by prior work to detect races on programs with futures all have to execute the program sequentially. We propose F-Order, the first known parallel race detection algorithm that detects races on programs that use futures. Given a computation with work T1 and span T∞, our algorithm detects races in time O((T1 lg k + k2)/P + T∞(k + lg r lg k)) processors, where k is the number of future operations, r is the maximum number of readers per memory location, and k is the maximum number of future operations done by a single future task, which is typically small. We have also implemented a prototype system based on the proposed algorithm and empirically demonstrates its practical efficiency and scalability.

Many modern parallel applications, such as desktop software and cloud-based web services, are service-oriented, long running, and perform frequent interactions with the external world (e.g., responding to user input). We want such interactive applications to provide fast response times because typically at the other end of the external interaction there is a user waiting for a response. Existing parallel platforms designed for multicore hardware do not work well for such interactive applications, because they are designed to maximize throughput (rather than responsiveness). Interactive applications may have a mixture of interactive and compute-intensive tasks occurring concurrently, and the scheduler must be able to discern and prioritize tasks so that tasks which require faster response are prioritized over background tasks.

The use of futures provides a flexible way to express parallelism and can generate arbitrary dependences among parallel subcomputations. The additional flexibility that futures provide comes with a cost, however. When scheduled using classic work stealing, a program with futures, compared to a program that uses only fork-join parallelism, can incur a much higher number of "deviations," a metric for evaluating the performance of parallel executions. All prior works assume a parsimonious work-stealing scheduler, however, where a worker thread (surrogate of a processor) steals work only when its local deque becomes empty.

Task parallelism research has traditionally focused on optimizing computation-intensive applications. Due to the proliferation of commodity parallel processors, there has been recent interest in supporting interactive applications. Such interactive applications frequently rely on I/O operations that may incur significant latency. In order to increase performance, when a particular thread of control is blocked on an I/O operation, ideally we would like to hide this latency by using the processing resources to do other ready work instead of blocking or spin waiting on this I/O. There has been limited prior work on hiding this latency. As far as we are aware, only one prior work exists that provides a theoretical bound for interactive applications that use I/Os. In this work, we propose a method for hiding the latency of I/O operations by using the futures abstraction. We provide better execution time guarantees using this method than prior work. We also implemented the algorithm in a practically efficient prototype library that runs on top of the Cilk-F runtime, a runtime system that supports futures within the context of the Cilk Plus language, and performed experiments that demonstrate the efficiency of our implementation.