Abstract for Kreaseck, Tullsen, Calder "Limits of Task-Based Parallelism in Irregular Applications"

Traditional parallel compilers do not effectively parallelize irregular applications because they contain little loop-level parallelism. We explore Speculative Task Parallelism (STP), where tasks are full procedures and entire natural loops. Through profiling and compiler analysis, we find tasks that are speculatively memory- and control-independent of their neighboring code. Via speculative futures, these tasks may be executed in parallel with preceding code when there is a high probability of independence. We estimate the amount of STP in irregular applications by measuring the number of memory-independent instructions these tasks expose. 7 to 22% of dynamic instructions are found to be within memory-independent tasks, depending on assumptions.