A loop parallelization method for nested loops with non-uniform dependences

This paper proposes an efficient method of partitioning nested loops with non-uniform dependences for maximizing parallelism. Our approach is based on convex hull theory, and it will divide the iteration space of the loop into three regions as two parallel regions where the iterations can be fully executed in parallel and one parallelizable region where the iterations are inherently serial, but possible parallelism can be exploited. And in order to maximize parallelism from the parallelizable region, an algorithm using integer programming which partitions a loop into variable size partitions is also proposed. In comparison with some works on partitioning, the proposed method is a simple and exact partitioning method, and it gives much better speedup and extracts more parallelism than them