New Algorithms for SIMD Alignment [abstract]
Liza Fireman, Erez Petrank, and Ayal Zaks
Proceedings of the 16th International Conference on Compiler
Construction (CC), March 2007.
Optimizing programs for modern multiprocessor or vector platforms
is a major important challenge for compilers today. In this work, we focus on one
challenging aspect: the SIMD ALIGNMENT problem. Previously, only heuristics
were used to solve this problem, without guarantees on the number of shifts in the
obtained solution. We study two interesting and realistic special cases of the SIMD
ALIGNMENT problem and present two novel and efficient algorithms that provide
optimal solutions for these two cases. The new algorithms employ dynamic programming
and a MIN-CUT/MAX-FLOW algorithm as subroutines. We also discuss
the relation between the SIMD ALIGNMENT problem and the MULTIWAY CUT and
NODE MULTIWAY CUT problems; and we show how to derive an approximated
solution to the SIMD ALIGNMENT problem based on approximation algorithms
to these two known problems.