Run-time parallelization for loops

Current parallelizing compilers cannot extract a significant fraction of the available parallelism in a loop if it has a complex and/or statically insufficiently defined access pattern. In this paper, a run-time technique based on insp/exec scheme (inspector phase and executor phase) is proposed for finding parallelism in loops. Our inspector can determine the wavefronts of a loop with any complex indirected array indexing pattern by building DEF-USE table. Experimental results show that the new method can handle any complex data dependence pattern that cannot be handled by the previous research, and also reveals that if the input loop workload is not uniform, an appropriate loop scheduling should be considered for achieving high parallelism