Quantum Compiler : Automatic Vectorization Assisted by Quantum Annealer
TimeTuesday, June 23rd4:20pm - 4:25pm
DescriptionMost modern processors support vector processing or similar techniques for improving performance, assuming that compilers are capable of automatic loop vectorization. In practice, programmers sometimes need to manually optimize a loop to help compilers check if the loop is safely vectorizable. A typical example of such loop optimizations is so-called variable renaming, which is required when there is a cyclic data dependency in a loop. One difficulty is that performance depends on the variable renaming techniques used for optimization, and finding an optimal combination of renaming is an NP-hard problem whose computational time increases drastically with the number of dependence cycles. If an optimal combination, instead of its approximated one, can be obtained within a practical time, compilers would potentially perform better vectorization leading to higher performance. In this poster, therefore, we propose to find an optimal combination by using quantum annealing, which is an emerging technology to solve combinatorial optimization problems. We evaluate the optimality of solutions and execution time for a loop containing eight dependence cycles. The evaluation results clarify that the quantum annealer can find optimal combinations, even though it requires a longer time than the conventional integer programming solver. These results demonstrate the feasibility of using quantum annealer to assist automatic loop vectorization by compilers. In conclusion, as the quantum annealer is promising not only to replace a combinatorial optimization part of HPC application execution but also to help automatic compiler optimization and hereby improve the performance even on conventional HPC applications.