Optimizing data permutations for SIMD devices

Gang Ren, Peng Wu, David Padua

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The widespread presence of SIMD devices in today's microprocessors has made compiler techniques for these devices tremendously important. One of the most important and difficult issues that must be addressed by these techniques is the generation of the data permutation instructions needed for non-contiguous and misaligned memory references. These instructions are expensive and, therefore, it is of crucial importance to minimize their number to improve performance and, in many cases, enable speedups over scalar code. Although it is often difficult to optimize an isolated data reorganization operation, a collection of related data permutations can often be manipulated to reduce the number of operations. This paper presents a strategy to optimize all forms of data permutations. The strategy is organized into three steps. First, all data permutations in the source program are converted into a generic representation. These permutations can originate from vector accesses to non-contiguous and misaligned memory locations or result from compiler transformations. Second, an optimization algorithm is applied to reduce the number of data permutations in a basic block. By propagating permutations across statements and merging consecutive permutations whenever possible, the algorithm can significantly reduce the number of data permutations. Finally, a code generation algorithm translates generic permutation operations into native permutation instructions for the target platform. Experiments were conducted on various kinds of applications. The results show that up to 77% of the permutation instructions are eliminated and, as a result, the average performance improvement is 48% on VMX and 68% on SSE2. For several applications, near perfect speedups have been achieved on both platforms.

Original languageEnglish (US)
Title of host publicationPLDI 2006 - Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation
Pages118-131
Number of pages14
DOIs
StatePublished - 2006
EventPLDI 2006 - 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation - Ottawa, ON, Canada
Duration: Jun 10 2006Jun 16 2006

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
Volume2006

Other

OtherPLDI 2006 - 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation
CountryCanada
CityOttawa, ON
Period6/10/066/16/06

Keywords

  • Data Permutation
  • Optimization
  • SIMD Compilation

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Optimizing data permutations for SIMD devices'. Together they form a unique fingerprint.

Cite this