Limits of Task-based Parallelism in Irregular Applications

Barbara Kreaseck, Dean Tullsen, and Brad Calder

In the proceedings of the 3rd International Symposium on High Performance Computing (ISHPC2K), October 2000


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. We find that 7 to 22% of dynamic instructions are within memory-independent tasks, depending on assumptions.