Computer Science ›› 2018, Vol. 45 ›› Issue (9): 220-223.doi: 10.11896/j.issn.1002-137X.2018.09.036

• Software & Database Technology • Previous Articles     Next Articles

Vectorization Methods for Indirect Array Index

YAO Jin-yang, ZHAO Rong-cai, WANG Qi, LI Ying-ying   

  1. State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001,China
  • Received:2017-11-07 Online:2018-09-20 Published:2018-10-10

Abstract: Indirect array index cannot bevectorized efficiently in the existing compiler.It makes the program which contains the indirect array index cannot take advantage of SIMD extension parts.It is a hot topic in research on procedure vectorization.In order to utilize the SIMD extension parts efficiently and excavate the vectorization potential in the program fully,a new vectorization method for indirect array index was proposed in this paper.The performance income method was provided so as to analyze the performance benefits for various indirect arrays index.The experimental results show that the vectorization method can significantly improve the efficiency of the execution of program.

Key words: Cost-benefit analysis, Indirect array index, Temporary array, Vectorization

CLC Number: 

  • TP311
[1]GAO W,ZHAO R C,HAN L,et al.Research on SIMD auto-vectorization compiling optimization[J].Journal of Software,2015,26(6):1265-1284.(in Chinese)
高伟,赵荣彩,韩林,等.SIMD自动向量化编译优化概述[J].软件学报,2015,26(6):1265-1284.
[2]BIK A J C,GIRKAR M,GREY P M,et al.Automatic Intra-Register Vectorization for the Intel® Architecture[J].International Journal of Parallel Programming,2002,30(2):65-98.
[3]ZHU Q S.Improving Program Performance via Auto-Vectorization of Loops with Conditional Statements with GCC Compiler Setting[J].Applied Mechanics & Materials,2013,433-435:1410-1414.
[4]YIU J.Getting Started with the ARM RealView Development
Suite[M]∥The Definitive Guide to the ARM Cortex-M0.Elsevier Inc.,2011:361-384.
[5]KANSAL R,KUMAR S.A vectorization framework for con-stant and linear gradient filled regions[J].The Visual Compu-ter,2015,31(5):717-732.
[6]CHEN J Z,LEI Q,MIAO Y W,et al.Vectorization of line dra-wing image based on junction analysis[J].Science China Information Sciences,2015,58(7):1-14.
[7]SUI Y,FAN X,ZHOU H,et al.Loop-oriented array-and field-sensitive pointer analysis for automatic SIMD vectorization[J].Acm Sigplan Notices,2016,51(5):41-51.
[8]WEINHARDT M,LUK W.Pipeline vectorization[J].IEEE
Transactions on Computer-aided Design of Integrated Circuits and Systems,2001,20(2):234-248.
[9]KENNEDY K,ALLEN J R.Optimizing compilers for modern architectures:a dependence-based approach[M]∥Optimizing compilers for modern architectures.Morgan Kaufmann Publi-shers,2002.
[10]CHANG H,SUNG W.Efficient vectorization of SIMD programs with non-aligned and irregular data access hardware[C]∥Proceedings of the 2008 International Conference on Compilers,Architectures and Synthesis for Embedded Systems.ACM,2008:107-176.
[11]LI P,ZHAO R,ZHANG Q,et al.An SIMD Code Generation
Technology for Indirect Array[J].International Journal of Computer Theory and Engineering,2016,8(3):218-222.
[12]ALEEN F,ZAKHARIN V P,KRISHANIYER R,et al.Automated compiler optimization of multiple vector loads/stores[J].International Journal of Parallel Programming,2018,46(2):47-503.
[13]KIM S,HAN H.Efficient SIMD code generation for irregular
kernels[J].Acm Sigplan Notices,2012,47(8):55-64.
[14]WEI S,ZHAO R C,YAO Y,et al.Data Regroup Alignment Optimization Based on SIMD [J].Chinese Journal of Computers,2012,39(2):305-310.(in Chinese)
魏帅,赵荣彩,姚远,等.面向SIMD的数组重组和对齐优化[J].计算机科学,2012,39(2):305-310.
[15]YU H N,HAN L,LI P Y,et al.Structure Optimization for Automatic Vectorization [J].Chinese Journal of Computers,2016,43(2):210-215.(in Chinese)
于海宁,韩林,李鹏远,等.面向自动向量化的结构体优化[J].计算机科学,2016,43(2):210-215.
[16]LARSEN S,AMARASINGHE S.Exploiting superword level
parallelism with multimedia instruction sets[J].Acm Sigplan Notices,2000,35(5):145-156.
[17]NUZMAN D.loop aware SLP in GCC[C]∥GCC Developers Summit.2007.
[1] XU Qi-ze, HAN Wen-ting, CHEN Jun-shi, AN Hong. Optimization of Breadth-first Search Algorithm Based on Many-core Platform [J]. Computer Science, 2019, 46(1): 314-319.
[2] ZHAO Cheng, CHEN Jun-xin, YAO Ming-hai. XSS Attack Detection Technology Based on SVM Classifier [J]. Computer Science, 2018, 45(11A): 356-360.
[3] LI Rui-long, LIANG Yuan and ZHANG Song-hai. Cartoon Animations Segmentation and Vectorization Based on Canny Optimization [J]. Computer Science, 2017, 44(8): 27-30.
[4] HAN Lin, XU Jin-long, LI Ying-ying and WANG Yang. Method of Loop Distribution and Aggregation for Partial Vectorization [J]. Computer Science, 2017, 44(2): 70-74.
[5] CHEN Yong and XU Chao. Symbolic Execution and Human-Machine Interaction Based Auto Vectorization Method [J]. Computer Science, 2016, 43(Z6): 461-466.
[6] YU Hai-ning, HAN Lin and LI Peng-yuan. Structure Optimization for Automatic Vectorization [J]. Computer Science, 2016, 43(2): 210-215.
[7] XU Jin-long ZHAO Rong-cai ZHAO Bo. Research on Non-full Length Usage of SIMD Vector Instruction [J]. Computer Science, 2015, 42(7): 229-233.
[8] LI Peng-yuan, ZHAO Rong-cai, GAO Wei and ZHANG Qing-hua. Effective Vectorization Technique for Interleaved Data with Constant Strides [J]. Computer Science, 2015, 42(5): 194-199.
[9] LIU Peng, ZHAO Rong-cai and LI Peng-yuan. Dynamic Pointer Alias Analysis Framework for Vectorization [J]. Computer Science, 2015, 42(3): 26-30.
[10] XU Jin-long, ZHAO Rong-cai and XU Xiao-yan. Memory Access Optimization for Vector Program of SIMD Form [J]. Computer Science, 2015, 42(12): 18-22.
[11] SUN Hui-hui, ZHAO Rong-cai, GAO Wei and LI Yan-bing. Control Flow Vectorization Based on Conditions Classification [J]. Computer Science, 2015, 42(11): 240-247.
[12] XU Ying,LI Chun-jiang,DONG Yu-shan and ZHOU Si-qi. Implementation of Auto-vectorization Based on Directives in GCC [J]. Computer Science, 2014, 41(Z11): 364-367.
[13] LIU Peng,ZHAO Rong-cai,ZHAO Bo and GAO Wei. Unified Vectorization Framework for SIMD Extensions [J]. Computer Science, 2014, 41(9): 28-31.
[14] LI Chun-jiang,HUANG Juan-juan,XU Ying,DU Yun-fei and CHEN Juan. Evaluation and Analysis of Effects of Auto-vectorization in Typical Compilers [J]. Computer Science, 2013, 40(4): 41-46.
[15] . Parallelism and Research on Functions with Continuously Independent Data and Intensive Memory Access Using OpenCL [J]. Computer Science, 2013, 40(3): 111-115.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!