Computer Science ›› 2019, Vol. 46 ›› Issue (6): 196-200.doi: 10.11896/j.issn.1002-137X.2019.06.029

Special Issue: Database Technology

Previous Articles     Next Articles

Optimization Algorithm of Complementary Register Usage Between Two Register Classesin Register Spilling for DSP Register Allocation

QIU Ya-qiong, HU Yong-hua, LI Yang, TANG Zhen, SHI Lin   

  1. (School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China)
  • Received:2018-04-17 Published:2019-06-24

Abstract: Register allocation has become one of the most important optimization techniques for compiler for that registers are limited and valuable resources in hardware architecture of computer.One of the key factors affecting the results of register allocation is the access and storage costs incurred from spilling signed registers.For DSP architectures with two classes of general-purpose registers,this paper proposed a complementary utilization strategy between the registers and a corresponding register spilling optimization algorithm on the basis of graph coloring register allocation method.Through distinguishing the interference between candidates of the same register class from those of different register classes,an undirected graph is built by improving the analysis for variables’ live ranges.Compared with the conventional graph coloring register allocation,the improved algorithm fully consideres the interferences among the register allocation candidates for two register classes,thus achiving less memory access operations in register spilling and higher code performance.

Key words: Compiler, Graph coloring algorithm, Optimization, Register allocation, Register spilling

CLC Number: 

  • TP311
[1]AHO A V,SETHI R,ULLMAN J D.Compilers,Principles, Techniques[M].Boston:Addison wesley,1986.
[2]RAU B R,LEE M,TIRUMALAI P P,et al.Register allocation for software pipelined loops[C]∥Acm Sigplan Conference on Programming Language Design & Implementation.1992:283-299.
[3]REN K,YAN X L,SUN L L,et al.ASIP register allocator based on improved graph coloring algorithm[J].Journal of Zhejiang University,2010(12):2309-2313.(in Chinese)
任坤,严晓浪,孙玲玲,等.基于改进图染色算法的 ASIP 寄存器分配器[J].浙江大学学报(工学版),2010(12):2309-2313.
[4]JIANG J,WANG C,YU H M .A Local Register Allocation Optimization Strategy[J].Computer Applications and Software,2013(12):215-217.(in Chinese)
姜军,王超,尉红梅.一种局部寄存器分配的优化策略[J].计算机应用与软件,2013(12):215-217.
[5]BRIGGS P,COOPER K D,KENNEDY K,et al.Coloring,heuristics for register allocation[J].ACM SIGPLAN Notices,1989,24(7):275-284.
[6]CHAITIN G J.Register allocation & spilling via graph coloring[J].ACM Sigplan Notices.ACM,1982,17(6):98-105.
[7]CHAITIN G J,AUSLANDER M A,CHANDRA A K,et al.Register allocation via coloring[J].Computer languages,1981,6(1):47-57.
[8]ACM Transactions on Programming Languages and Systems [M].Association for Computing Machinery,1979.
[9]BRIGGS P,COOPER K D,TORCZON L.Coloring register pairs[J].Acm Letters on Programming Languages & Systems,1992,1(1):3-13.
[10]BRIGGS P,COOPER K D,TORCZON L.Improvements to graph coloring register allocation[J].Acm Transactions on Programming Languages & Systems,1994,16(3):428-455.
[11]PENG Z S,DUAN Y Y,WANG B.Introduction of Mainstream Processor Architecture and Intel Microarchitecture Development[J].Information System Engineering,2017(3):29-31.(in Chinese)
彭圳生,段妍羽,王赟.主流处理器架构及英特尔微架构发展分析[J].信息系统工程,2017(3):29-31.
[12]WANG X,FU J W,HE H.Instruction Processing Method Based on ARM Instruction Set in General DSP[J].Microelectronics and Computers,2016,33(9):10-14.(in Chinese)
王旭,付家为,何虎.基于ARM指令集的通用DSP中指令相关处理方法[J].微电子学与计算机,2016,33(9):10-14.
[13]NICKERSON B R.Graph coloring register allocation for processors with multi-register operands[C]∥ACM Sigplan 1990 Conference on Programming Language Design and Implementation.ACM,1990:40-52.
[14]WOLFE J.Optimizing Super-compilers for Supercomputers[M]∥ Optimizing Super-compilers for Supercomputers.MIT Press Cambridge,MA,USA,1990.
[15]HUANG L,FENG X B.Combined instruction scheduling and register allocation techniques[J].Application Research of Computers,2008,25(4):979-982.(in Chinese)
黄磊,冯晓兵.结合的指令调度与寄存器分配技术[J].计算机应用研究,2008,25(4):979-982.
[16]Instruction Set Manual of YHFT-Matrix2 DSP[G].Institute of Microelectronics,National University of Defense Technology.2013.(in Chinese)
YHFT-Matrix2 DSP 指令集手册[G].国防科学技术大学计算机学院微电子所.2013.
[1] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[2] WANG Can, LIU Yong-jian, XIE Qing, MA Yan-chun. Anchor Free Object Detection Algorithm Based on Soft Label and Sample Weight Optimization [J]. Computer Science, 2022, 49(8): 157-164.
[3] CHEN Jun, HE Qing, LI Shou-yu. Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor [J]. Computer Science, 2022, 49(8): 237-246.
[4] LI Qi-ye, XING Hong-jie. KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion [J]. Computer Science, 2022, 49(8): 267-272.
[5] WANG Bing, WU Hong-liang, NIU Xin-zheng. Robot Path Planning Based on Improved Potential Field Method [J]. Computer Science, 2022, 49(7): 196-203.
[6] TANG Feng, FENG Xiang, YU Hui-qun. Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation [J]. Computer Science, 2022, 49(7): 254-262.
[7] ZHAO Dong-mei, WU Ya-xing, ZHANG Hong-bin. Network Security Situation Prediction Based on IPSO-BiLSTM [J]. Computer Science, 2022, 49(7): 357-362.
[8] LI Ya-ru, ZHANG Yu-lai, WANG Jia-chen. Survey on Bayesian Optimization Methods for Hyper-parameter Tuning [J]. Computer Science, 2022, 49(6A): 86-92.
[9] HUANG Guo-xing, YANG Ze-ming, LU Wei-dang, PENG Hong, WANG Jing-wen. Solve Data Envelopment Analysis Problems with Particle Filter [J]. Computer Science, 2022, 49(6A): 159-164.
[10] LU Hao-song, HU Yong-hua, WANG Shu-ying, ZHOU Xin-lian, LI Hui-xiang. Study on Hybrid Resource Heuristic Loop Unrolling Factor Selection Method Based on Vector DSP [J]. Computer Science, 2022, 49(6A): 777-783.
[11] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Clustered Federated Learning Methods Based on DBSCAN Clustering [J]. Computer Science, 2022, 49(6A): 232-237.
[12] CHEN Jun-wu, YU Hua-shan. Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs [J]. Computer Science, 2022, 49(6A): 594-600.
[13] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[14] FAN Xing-ze, YU Mei. Coverage Optimization of WSN Based on Improved Grey Wolf Optimizer [J]. Computer Science, 2022, 49(6A): 628-631.
[15] ZHU Xu-hui, SHEN Guo-jiao, XIA Ping-fan, NI Zhi-wei. Model Based on Spirally Evolution Glowworm Swarm Optimization and Back Propagation Neural Network and Its Application in PPP Financing Risk Prediction [J]. Computer Science, 2022, 49(6A): 667-674.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!