Effective parallelization techniques for non-uniform loops

Abstract

It is known that the parallelism of non-uniform dependence loops is difficult to extract and is not effectively explored by the existing parallelization methods. In this paper, we propose new techniques to transform non-uniform dependence loops efficiently, based on their irregularity, by which more parallelism can be explored directly and effectively. Several effective mechanisms, including parallelization part splitting, partial parallelization decomposition, irregular loop interchange and growing pattern rt detection are created to exploit more parallelism degree for non-uniform loop structures. Compared with other existing methods, our new approach gives better performance. When the loop bounds is increased from 5 to 50, based on our evaluations, the speedup achieves 3.25 to 19.8 times better than that of the uniformization technique; and from 1.5 to 8.33 times better than that of the minimum dependence distance tiling technique. We evaluate our mechanisms in our simulation environment for various conditions and discuss the performance of them in this paper.