More Web Proxy on the site http://driver.im/

Article

Auto-vectorization of interleaved data for SIMD

Authors:

Ayal ZaksAuthors Info & Claims

PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 132 - 143

https://doi.org/10.1145/1133981.1133997

Published: 11 June 2006 Publication History

Abstract

Most implementations of the Single Instruction Multiple Data (SIMD) model available today require that data elements be packed in vector registers. Operations on disjoint vector elements are not supported directly and require explicit data reorganization manipulations. Computations on non-contiguous and especially interleaved data appear in important applications, which can greatly benefit from SIMD instructions once the data is reorganized properly. Vectorizing such computations efficiently is therefore an ambitious challenge for both programmers and vectorizing compilers. We demonstrate an automatic compilation scheme that supports effective vectorization in the presence of interleaved data with constant strides that are powers of 2, facilitating data reorganization. We demonstrate how our vectorization scheme applies to dominant SIMD architectures, and present experimental results on a wide range of key kernels, showing speedups in execution time up to 3.7 for interleaving levels (stride) as high as 8.

References

[1]

R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures - A Dependence-based Approach. Morgan Kaufmann Publishers, 2001.

Digital Library

[2]

K. Asanovic and D. Johnson. Torrent Architecture Manual. Technical report tr-96-056, Internation Computer Science Institute (ICSI), 1996.

Digital Library

[3]

L. Bachega, S. Chatterjee, K. A. Dockserz, J. A. Gunnels, M. Gupta, F. G. Gustavson, C. A. Lapkowskix, G. K. Liu, M. P. Mendell, C. D. Wait, and T. J. C. Ward. A High-performance SIMD Floating Point Unit for BlueGene/L: Architecture, Compilation, and Algorithm Design. In Proc. of the 13th International Conference on Parallel Architecture and Compilation Techniques (PACT'04), pages 85--96, September 2004.

Digital Library

[4]

A. J. C. Bik, M. Girkar, P. M. Grey, and X. Tian. Efficient exploitation of parallelism on Pentium III and Pentium 4 processor-based systems. Intel Technology J., February 2001.

[5]

A. Bik. The Software Vectorization Handbook. Applying Multimedia Extensions for Maximum Performance. Intel Press, 2004.

Digital Library

[6]

J. Corbal, R. Espasa, and M. Valero. Exploiting a New Level of DLP in Multimedia Applications. In Proc. of the 32nd annual ACM/IEEE International Symposium on Microarchitecture (Micro), pages 72--79, 1999.

Digital Library

[7]

P. D'Arcy and S. Beach. StarCore SC140: A New DSP Architecture for Portable Devices. In Wireless Symposium. Motorola, September 1999.

[8]

K. Diefendorff, P. K. Dubey, R. Hochsprung and H. Scales. Altivec Extension to PowerPC Accelerates Media Processing. IEEE Micro, Vol. 20, No. 2, pages 85--95, March-April 2000.

Digital Library

[9]

A. E. Eichenberger, P. Wu, and K. O'brien. Vectorization for SIMD Architectures with Alignment Constraints. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 82--93, June 2004.

Digital Library

[10]

R. Espasa, F. Ardanaz, J. Emer, S. Felix, J. Gago, R. Gramunt, I. Hernandez, T. Juan, G. Lowney, M. Mattina, and A. Seznec. Tarantula: A Vector Extension to the Alpha Architecture. In Proc. of the 29th Annual International Symposium on Computer Architecture (ISCA), pages 281--292, May 2002.

Digital Library

[11]

Free Software Foundation. Auto-Vectorization in GCC, http://gcc.gnu.org/projects/tree-ssa/vectorization.html.

[12]

Free Software Foundation. GCC, http://gcc.gnu.org.

[13]

G. Goff, K. Kennedy, and C. Tseng. Practical Dependence Testing. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 15--29, June 1991.

Digital Library

[14]

Texas Instruments. www.ti.com/sc/c6x, 2000.

[15]

J. A. Kahle, M. N. Day, H. P. Hofstee, C. R. Johns, T. R. Maeurer, and D. Shippy. Introduction to the Cell Multiprocessor. IBM Journal of Research and Development, 49(4), pages 589--604, July 2005.

Digital Library

[16]

A. Kudriavtsev and P. Kogge Generation of Permutations for SIMD Processors in Proc. of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems (LCTES), pages 147 -- 156, June 2005.

Digital Library

[17]

S. Larsen and S. Amarasinghe. Exploiting Superword Level Parallelism with Multimedia Instruction Sets. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 145--156, June 2000.

Digital Library

[18]

J. Lorenz, S. Kral, F. Franchetti, and C. W. Ueberhuber. Vectorization Techniques for the BlueGene/L Double FPU. IBM Journal of Research and Development, 49(2-3), pages 437--446, March/May 2005.

Digital Library

[19]

J. Merrill. Generic and Gimple: A New Tree Representation for Entire Functions. In the GCC Developer's summit, pages 171--180, June 2003.

[20]

J. H. Moreno, V. Zyuban, U. Shvadron, F. Neeser, J. Derby, M. Ware, K. Kailas, A. Zaks, A. Geva, S. Ben-David, S. Asaad, T. Fox, M. Biberstein, D. Naishlos, and H. Hunter. An Innovative Low-power High-performance Programmable Signal Processor for Digital Communications. IBM Journal of Research and Development 47(2-3), pages 299--326, March/May 2003.

Digital Library

[21]

D. Naishlos, M. Biberstein, S. Ben-David, and A. Zaks. Vectorizing for a SIMdD DSP Architecture. In Proc. of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES), pages 2--11, October 2003.

Digital Library

[22]

D. Naishlos and R. Henderson. Multi-platform Auto-vectorization. In Proc. of the 4th Annual International Symposium on Code Generation and Optimization (CGO), March 2006.

Digital Library

[23]

H. Nguyen and L. K. John. Exploiting SIMD Parallelism in DSP and Multimedia Algorithms using the AltiVec Technology. In Intl. Conf. on Supercomputing, pages 11--20, 1999.

Digital Library

[24]

D. Novillo. Tree SSA - a New Optimization Infrastructure for GCC. In Proc. of the GCC Developers Summit, pages 181--194, June 2003.

[25]

A. Peleg and U. Weiser. MMX Technology Extension to the Intel Architecture. IEEE Micro Vol.16, No.4, pages 42--50, August 1996.

Digital Library

[26]

G. Pokam, S. Bihan, J. Simonnet, and F. Bodin. SWARP: A Retargetable Preprocessor for Multimedia Instructions In Concurrency and Computation: Practice and Experience; Special Issue: Compilers for Parallel Computers, Vol. 16, No. 2-3, pages 303 -- 318, January 2004.

Digital Library

[27]

S. Pop, G. Silber, A. Cohen, P. Clauss, and V. Loechner. Fast Recognition of Scalar Evolutions on Three-address SSA Code. Research Report A/354/CRI, CRI/ENSMP, April 2004.

[28]

S. Pop, A. Cohen, and G. Silber. Induction Variable Analysis with Delayed Abstractions. In Proc. of the First International Conference of High Performance Embedded Architectures and Compilers (HiPEAC), pages 218--232, November 2005.

Digital Library

[29]

I. Pryanishnikov, A. Krall, and N. Horspool. Pointer Alignment Analysis for Processors with SIMD Instructions. In Proc. of the 5th Workshop on Media and Streaming Processors at Micro '03, pages 50--57, December 2003.

[30]

G. Ren, P. Wu, and D. Padua. A Preliminary Study on the Vectorization of Multimedia Applications for Multimedia Extensions. In 16th International Workshop of Languages and Compilers for Parallel Computing (LCPC), pages 420 -- 435, October 2003.

Digital Library

[31]

G. Ren, P. Wu, and D. Padua. Optimizing Data Permutations for SIMD Devices. to appear in Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2006.

Digital Library

[32]

J. Shin, J. Chame, and M. W. Hall. Compiler-controlled Caching in Superword Register Files for Multimedia Extension Architectures. In Proc. of the 11th International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 45--55, September 2002.

Digital Library

[33]

J. Shin, M. Hall, and J. Chame. Superword-Level Parallelism in the Presence of Control Flow. In Proc. of International Symposium on Code Generation and Optimization (CGO), pages 165--175, March 2005.

Digital Library

[34]

K. B. Smith, A. J. Bik, and X. Tian. Support for the Intel Pentium 4 Processor with Hyper-threading Technology in Intel 8.0 Compilers. Intel Technology Journal, 8(1), pages 19--31, February 2004.

[35]

D. Talla, L. K. John, and D. Burger. Bottlenecks in Multimedia Processing with SIMD Style Extensions and Architectural Enhancements. IEEE Trans. on Computers Vol. 52, No. 8, pages 1015--1031, August 2003.

Digital Library

[36]

Crecent Bay Software. VAST-F/ALtivec: Automatic Fortran Vectorizer for PowerPC Vector Unit, http://www.crescentbaysoftware.com/docs/vastfav.pdf.

[37]

Crecent Bay Software. Vast/altivec faq: Vectorization for Altivec, http://www.crescentbaysoftware.com/altivec_FAQ.html.

[38]

M. Wolfe. High Performance Compilers for Parallel Computing. Addison Wesley, 1996.

Digital Library

[39]

P. Wu, A. E. Eichenberger, and A. Wang. Efficient SIMD Code Generation for Runtime Alignment. In Proc. of the International Symposium on Code Generation and Optimization (CGO), pages 153-- 164, March 2005.

Digital Library

Cited By

de Bruin BVadivel KWijtvliet MJääskeläinen PCorporaal H(2024)R-Blocks: an Energy-Efficient, Flexible, and Programmable CGRAACM Transactions on Reconfigurable Technology and Systems10.1145/365664217:2(1-34)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3656642
Nuzman DZaks ABen-Zion ZRodríguez GSadayappan PSukumaran-Rajam A(2024)If-Convert as Early as You MustProceedings of the 33rd ACM SIGPLAN International Conference on Compiler Construction10.1145/3640537.3641562(26-38)Online publication date: 17-Feb-2024
https://dl.acm.org/doi/10.1145/3640537.3641562
Zhou HHan QShi HZhang YYao JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Boost Linear Algebra Computation Performance via Efficient VNNI UtilizationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651333(149-163)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651333
Show More Cited By

Index Terms

Auto-vectorization of interleaved data for SIMD
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Single instruction, multiple data
      2. Very long instruction word
    2. Serial architectures
      1. Complex instruction set computing
      2. Reduced instruction set computing
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Outer-loop vectorization: revisited for short SIMD architectures
PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques

Vectorization has been an important method of using data-level parallelism to accelerate scientific workloads on vector machines such as Cray for the past three decades. In the last decade it has also proven useful for accelerating multi-media and ...
Auto-vectorization of interleaved data for SIMD
Proceedings of the 2006 PLDI Conference

Most implementations of the Single Instruction Multiple Data (SIMD) model available today require that data elements be packed in vector registers. Operations on disjoint vector elements are not supported directly and require explicit data ...
Vectorizing for a SIMdD DSP architecture
CASES '03: Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems

The Single Instruction Multiple Data (SIMD) model for finegrained parallelism was recently extended to support SIMD operations on disjoint vector elements. In this paper we demonstrate how SIMdD (SIMD on disjoint data) supports e#ective vectorization of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2006

438 pages

ISBN:1595933204

DOI:10.1145/1133981

General Chair:
Michael Schwartzbach
University of Aarhus, Denmark
,
Program Chair:
Thomas Ball
Microsoft Research

ACM SIGPLAN Notices Volume 41, Issue 6
Proceedings of the 2006 PLDI Conference
June 2006
426 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1133255
Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI06

Sponsor:

PLDI06: ACM SIGPLAN Conference on Programming Language Design and Implementation 2006

June 11 - 14, 2006

Ontario, Ottawa, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

159
Total Citations
View Citations
2,597
Total Downloads

Downloads (Last 12 months)126
Downloads (Last 6 weeks)7

Reflects downloads up to 06 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

de Bruin BVadivel KWijtvliet MJääskeläinen PCorporaal H(2024)R-Blocks: an Energy-Efficient, Flexible, and Programmable CGRAACM Transactions on Reconfigurable Technology and Systems10.1145/365664217:2(1-34)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3656642
Nuzman DZaks ABen-Zion ZRodríguez GSadayappan PSukumaran-Rajam A(2024)If-Convert as Early as You MustProceedings of the 33rd ACM SIGPLAN International Conference on Compiler Construction10.1145/3640537.3641562(26-38)Online publication date: 17-Feb-2024
https://dl.acm.org/doi/10.1145/3640537.3641562
Zhou HHan QShi HZhang YYao JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Boost Linear Algebra Computation Performance via Efficient VNNI UtilizationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651333(149-163)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651333
Thomas SBornholt JTsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)Automatic Generation of Vectorizing Compilers for Customizable Digital Signal ProcessorsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624873(19-34)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624873
Guan XZhou HBao GLi HZhu LYao JGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)PresCount: Effective Register Allocation for Bank Conflict ReductionProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444841(170-181)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444841
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Mustafa DAlkhasawneh RObeidat FShatnawi A(2024)MIMD Programs Execution Support on SIMD Machines: A Holistic SurveyIEEE Access10.1109/ACCESS.2024.337299012(34354-34377)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3372990
Naithani ARoelandts JAinsworth SJones TEeckhout L(2023)Decoupled Vector RunaheadProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3614255(17-31)Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1145/3613424.3614255
Yao JZhou HZhang YLi YFeng CChen SChen JWang YHu Q(2023)High Performance and Power Efficient Accelerator for Cloud Inference2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10070941(1003-1016)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10070941
Mosaner RBarany GLeopoldseder DMössenböck HKotselidis CProkopec A(2022)Improving Vectorization Heuristics in a Dynamic Compiler with Machine Learning ModelsProceedings of the 14th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3563838.3567679(36-47)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563838.3567679
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten