NDLI: Optimizing data permutations for SIMD devices

Content Provider	ACM Digital Library
Author	Wu, Peng Padua, David Ren, Gang
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.
Starting Page	118
Ending Page	131
Page Count	14
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/1133255.1133996
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	41
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Simd compilation Data permutation Optimization
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimizing data permutations for SIMD devices

Generation of permutations for SIMD processors

Optimizing compiler for shared-memory multiple SIMD architecture

Automatic SIMD vectorization for Haskell

Energy aware compilation for DSPs with SIMD instructions

Optimizing MATLAB feval with dynamic techniques

Auto-vectorization of interleaved data for SIMD

SIMD defragmenter:efficient ILP realization on data-parallel architectures (SIGP, Vol. 47, Issue. 4)

Type-preserving compilation for large-scale optimizing object-oriented compilers

Optimizing data permutations for SIMD devices

Similar Documents

Optimizing data permutations for SIMD devices

Generation of permutations for SIMD processors

Optimizing compiler for shared-memory multiple SIMD architecture

Automatic SIMD vectorization for Haskell

Energy aware compilation for DSPs with SIMD instructions

Optimizing MATLAB feval with dynamic techniques

Auto-vectorization of interleaved data for SIMD

SIMD defragmenter:efficient ILP realization on data-parallel architectures (SIGP, Vol. 47, Issue. 4)

Type-preserving compilation for large-scale optimizing object-oriented compilers

Optimizing data permutations for SIMD devices