Implicit Data Permutation for SIMD Devices

SIMD extension is one of the most effective ways to exploit data level parallelism in current microprocessor design. But limited by some constraints, such as memory address alignment and in consecutive memory access, data permutation operations are usually needed before SIMD calculations, which impede us to exploit more parallelism. In this paper, an implicit data permutation mechanism is proposed. With our approach, original explicit data permutation can be split into two stages: explicit pattern setting and implicit data reorganization. The first stage is performed by scalar instructions and the second one is triggered implicitly when a vector register is read. It provides new chance for further optimization. To make this mechanism programmable, several new scalar instructions are extended and corresponding compilation strategies are also proposed. Experimental results show that oriented to multimedia benchmarks, 1.18x speedup can be achieved over current SIMD optimization techniques on average.