Using Read-After-Read Dependencies to Control Task-Granularity

In compiler theory, data analysis is used to exploit Instruction Level Parallelism (ILP). Three dependencies are used in modern compilers and hardware schemes efficiently and are fundamental to any code compilation. Read-after-read (RAR) has been left out, as it cannot cause a data hazard. This article introduces a novel method to use the additional dependence information contained in any code to enhance automatic parallelization. The method builds groups of arbitrary sequential instruction chains during static code analysis and introduces potential-transfers between these groups. This gives new opportunities when optimizing code to a parallel-processing hardware. The segmentation enables more information concerning the potential parallelization of the code and enhances optimization opportunities to be gained during static code analysis. The novel principle is introduced using a very simple example and then the segmentation is applied to task- and data-parallelism examples. The automatic parallelization to a multicore-platform is demonstrated using the new segmentation method. The ability to forecast the optimal distribution of the segments for a platform with two key parameters and resulting codes are compared to measured speedups.