计算机科学 ›› 2019, Vol. 46 ›› Issue (6): 196-200.doi: 10.11896/j.issn.1002-137X.2019.06.029

所属专题: 数据库技术

• 软件与数据库技术 • 上一篇    下一篇

基于两类寄存器互为缓存方法的DSP寄存器分配溢出处理优化算法

邱亚琼, 胡勇华, 李阳, 唐镇, 石林   

  1. (湖南科技大学计算机科学与工程学院 湖南 湘潭411201)
  • 收稿日期:2018-04-17 发布日期:2019-06-24
  • 通讯作者: 胡勇华(1981-),男,博士,教授,主要研究领域为DSP编译,E-mail:hyhyt@126.com
  • 作者简介:邱亚琼(1991-),女,硕士,主要研究领域为DSP编译;李 阳(1995-),女,硕士,主要研究领域为DSP编译;唐 镇(1994-),男,硕士,主要研究领域为DSP编译;石 林(1986-),男,主要研究领域为图形处理器与分布式计算。
  • 基金资助:
    国家自然科学基金(61308001),湖南省自然科学基金(2017JJ3087)资助。

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

摘要: 寄存器是处理器硬件中有限的宝贵资源,这使得寄存器分配成为编译器中最为关键的过程之一。影响寄存器分配效果的关键因素之一是溢出带来的访存开销。针对DSP处理器具有两类通用寄存器的情况,以图着色全局寄存器分配方法为基本方法,提出两类寄存器间的一种互补利用策略和相应的寄存器溢出优化算法。该策略改进了传统图着色方法,通过生命周期分析的结果,将同类寄存器分配候选者之间的冲突关系和不同类寄存器分配候选者之间的冲突关系区分开来,并把它们表示在一张无向图中。与传统的图着色算法相比,改进的算法能充分考虑不同类寄存器之间的相互约束关系,减少寄存器溢出时的访存操作,从而有利于提高代码的性能。

关键词: 编译器, 寄存器分配, 寄存器溢出, 图着色方法, 优化

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

中图分类号: 

  • 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] 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩.
基于分层抽样优化的面向异构客户端的联邦学习
Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients
计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263
[2] 李其烨, 邢红杰.
基于最大相关熵的KPCA异常检测方法
KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion
计算机科学, 2022, 49(8): 267-272. https://doi.org/10.11896/jsjkx.210700175
[3] 王灿, 刘永坚, 解庆, 马艳春.
基于软标签和样本权重优化的Anchor Free目标检测算法
Anchor Free Object Detection Algorithm Based on Soft Label and Sample Weight Optimization
计算机科学, 2022, 49(8): 157-164. https://doi.org/10.11896/jsjkx.210600240
[4] 陈俊, 何庆, 李守玉.
基于自适应反馈调节因子的阿基米德优化算法
Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor
计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[5] 王兵, 吴洪亮, 牛新征.
基于改进势场法的机器人路径规划
Robot Path Planning Based on Improved Potential Field Method
计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[6] 唐枫, 冯翔, 虞慧群.
基于自适应知识迁移与资源分配的多任务协同优化算法
Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation
计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184
[7] 张翀宇, 陈彦明, 李炜.
边缘计算中面向数据流的实时任务调度算法
Task Offloading Online Algorithm for Data Stream Edge Computing
计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[8] 赵冬梅, 吴亚星, 张红斌.
基于IPSO-BiLSTM的网络安全态势预测
Network Security Situation Prediction Based on IPSO-BiLSTM
计算机科学, 2022, 49(7): 357-362. https://doi.org/10.11896/jsjkx.210900103
[9] 李亚茹, 张宇来, 王佳晨.
面向超参数估计的贝叶斯优化方法综述
Survey on Bayesian Optimization Methods for Hyper-parameter Tuning
计算机科学, 2022, 49(6A): 86-92. https://doi.org/10.11896/jsjkx.210300208
[10] 康雁, 王海宁, 陶柳, 杨海潇, 杨学昆, 王飞, 李浩.
混合改进的花授粉算法与灰狼算法用于特征选择
Hybrid Improved Flower Pollination Algorithm and Gray Wolf Algorithm for Feature Selection
计算机科学, 2022, 49(6A): 125-132. https://doi.org/10.11896/jsjkx.210600135
[11] 黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文.
利用粒子滤波方法求解数据包络分析问题
Solve Data Envelopment Analysis Problems with Particle Filter
计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110
[12] 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩.
基于DBSCAN聚类的集群联邦学习方法
Clustered Federated Learning Methods Based on DBSCAN Clustering
计算机科学, 2022, 49(6A): 232-237. https://doi.org/10.11896/jsjkx.211100059
[13] 陆浩松, 胡勇华, 王书盈, 周新莲, 李慧祥.
向量DSP的混合资源启发式循环展开因子选择方法研究
Study on Hybrid Resource Heuristic Loop Unrolling Factor Selection Method Based on Vector DSP
计算机科学, 2022, 49(6A): 777-783. https://doi.org/10.11896/jsjkx.210400146
[14] 陈钧吾, 余华山.
面向无尺度图的Δ-stepping算法改进策略
Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs
计算机科学, 2022, 49(6A): 594-600. https://doi.org/10.11896/jsjkx.210400062
[15] 刘漳辉, 郑鸿强, 张建山, 陈哲毅.
多无人机使能移动边缘计算系统中的计算卸载与部署优化
Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems
计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!