On Optimizing the Longest Common Subsequence Problem by Loop Unrolling Along Wavefronts

摘要

Loop unrolling is a loop transformation where a few loop iterations are grouped as a super iteration for exploring more independent instructions and to decrease the total loop overhead. This paper characterizes loop unrolling by the unrolling factor, the number of iterations in a super iteration and the unrolling direction, the choice of iterations to be grouped to form the super iteration. We use loop unrolling for maximizing instruction-level parallelism in the longest common subsequence problem. To increase the number of independent instructions in the super iteration, we use a linear schedule to group iterations on the same wave front, a hyper plane in the loop iteration space. Then, the loop is unrolled along the wave front which guarantees all iterations in the same super iteration are independent. The selection of the optimal unrolling factor is based on the assumption that if all the pipelines are saturated, the performance should not be bad. Two necessary conditions and a sufficient condition for optimality are presented and used to find the optimal unrolling factor. The total execution time is expressed as a function of algorithm parameters, architecture parameters and the unrolling factor. A benchmark of the technique scores a 1.475 speed-up over traditional methods.