Compiler-Assisted Dynamic Scheduling for Effective Parallelization of Loop Nests on Multicore Processors

Recent advances in polyhedral compilation technology have made it feasible to automatically transform afne sequential loop nests for tiled parallel execution on multi-core processors. However, for multi-statement input programs with statements of different di-mensionalities, such as Cholesky or LU decomposition, the par-allel tiled code generated by existing automatic parallelization ap-proaches may suffer from signicant load imbalance, resulting in poor scalability on multi-core systems. In this paper, we develop a completely automatic parallelization approach for transforming input afne sequential codes into efcient parallel codes that can be executed on a multi-core system in a load-balanced manner. In our approach, we employ a compile-time technique that enables dynamic extraction of inter-tile dependences at run-time, and dy-namic scheduling of the parallel tiles on the processor cores for improved scalable execution. Our approach obviates the need for programmer intervention and re-writing of existing algorithms for efcient parallel execution on multi-cores. We demonstrate the use-fulness of our approach through comparisons using linear algebr