Recursive parallel programming models such as Cilk strive to simplify the task of parallel programming by enabling a simple divide-and-conquer model of programming. This model is effective in re- cursively partitioning work into smaller parts and combining their results. However, recursive work partitioning can impose additional constraints on concurrency than is implied by the true dependences in a program. In this paper, we present a speculation-based approach to alleviate the concurrency constraints imposed by such recursive parallel programs. We design a runtime infrastructure that supports speculative execution and a predictor to accurately learn and identify opportunities to relax extraneous concurrency constraints. Experimental evaluation demonstrates that speculative relaxation of concurrency constraints can deliver gains of up to 1.6× on 30 cores over baseline Cilk.
Revised: January 20, 2016 |
Published: November 15, 2015
Citation
Aga S.D., S. Krishnamoorthy, and S. Narayanasamy. 2015.CilkSpec: Optimistic Concurrency for Cilk. In Supercomputing (SC15): Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, November 15-20, 2015, Austin, Texas, Paper No. 83. New York, New York:Association for Computing Machinery (ACM).PNNL-SA-111827.doi:10.1145/2807591.2807597