M.Sc Thesis

M.Sc StudentFireman Liza
SubjectThe Complexity of SIMD Alignment
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank


Optimizing programs for modern multiprocessor or vector platforms is a major important challenge for compilers today.  Various problems in this domain are not yet thoroughly understood.  In this work, we focus on one such problem: the SIMD Alignment problem. In this problem we are given a code that includes a loop with misaligned references. Such a code requires additional realignment operations to allow parallelization on SIMD architectures because of SIMD alignment constraints. The realigning of data is achieved by shifting streams of data after reading them into the SIMD registers and before applying the SIMD operations. Shifts are executed inside the loop and therefore affect the performance significantly. The problem is to automatically reorganize data streams to satisfy the alignment requirements imposed by the hardware with a minimum number of shift executions.

Previously, only heuristics were used to solve this problem, without any 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 solve the problem optimally for these two cases. In the first case, we deal with expressions whose number of different alignments is not restricted, but their graph representation form a tree and any array appears in the expression at most once. For this special case we show a polynomial-time algorithm using dynamic programming. In the second case, the graph representation can be any DAG, but we restrict the expression to contain only two distinct predetermined alignments associated with the input and output operands. We use a Minimum-Cut/Maximum-Flow algorithm as a subroutine.

We also discuss the relation between the SIMD Alignment problem and the Multiway Cut and Node Multiway Cut problems. We show how to achieve an approximated solution to the SIMD Alignment problem based on approximation algorithms to these two known problems.