Task-parallel programming models enable programmers to extract parallelism from irregular applications.Since software-based taskparallel runtimes impose crippling overheads on fine-grain tasks, architects have designed manycores with hardware support for task management.These hardware task-parallel systems can scale challenging workloads to hundreds of cores, but fail to use conventional prefetchers due to short (100-cycle) tasks.Lacking prefetching, they often expose DRAM latency to applications, fumbling the performance gains of hardware.We present the Task-Seeded Prefetcher (TSP) and Memory Response Task Scheduler (MRS), a symbiotic pair that boost performance in general-purpose task-parallel hardware.TSP learns and prefetches the data-access pattern of each task function, seeded with its descriptor that is queued by the task scheduler.MRS augments the baseline task-to-core dispatch policy by using prefetch status from TSP to optimize core utilization.Together, TSP and MRS provide speedups of up to 3.1× (gmeans up to 1.4×) across 13 benchmarks on 256-core task-parallel systems that were already 3-60× faster than parallel software.

The Rust programming language is lauded for enabling fearless concurrency with zero cost: detecting concurrency errors at compile time. Given the enduring difficulty of parallel programming in other languages, this implied panacea warrants analysis. In particular, the efficacy of Rust across types of parallelism remains unexplored. Is parallel programming always devoid of fear with Rust? We answer this question through a case study, porting 14 benchmarks with abundant regular and irregular parallelism from C++ to Rust and reporting our experience and observations. We find that Rust, with the Rayon library, indeed delivers fearlessness for program phases comprising only regular parallelism, e.g., prefix-sum. However, for applications with any irregular parallelism, the programmer must choose between unsafe code or high-overhead dynamic checks with errors that manifest at run time, leaving the arduous task of parallel programming as scary with Rust as with its predecessors.

Many irregular algorithms converge more quickly when they execute tasks in a specific order. When this order is discovered at run time, the algorithm demands a dynamic task scheduler. Scaling a priority scheduler to large systems with many cores is challenging and while many concurrent priority schedulers (CPS) have been proposed, a general classification of their design space is still lacking. We survey prior work and propose three dimensions for the design of CPSs: the degree of synchrony, the drift of priorities, and the underlying data structure. We use this taxonomy to classify existing schedulers and evaluate their strengths and weaknesses.

Many algorithms schedule their work, or tasks, according to a priority order for correctness or faster convergence. While priority schedulers commonly implement task enqueue and dequeueMin operations, some algorithms need a priority update operation that alters the scheduling metadata for a task. Prior software and hardware systems that support scheduling with priority updates compromise on either parallelism, work-efficiency, or both, leading to missed performance opportunities. Moreover, incorrectly navigating these compromises violates correctness in those algorithms that are not resilient to relaxing priority order.