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.