计算机科学 ›› 2021, Vol. 48 ›› Issue (6A): 587-595.doi: 10.11896/jsjkx.200600061

• 交叉&应用 • 上一篇    下一篇

基于弱约束指派的DSP寄存器偶对分配算法研究

唐镇, 胡勇华, 陆浩松, 王书盈   

  1. 湖南科技大学 湖南 湘潭411201
  • 出版日期:2021-06-10 发布日期:2021-06-17
  • 通讯作者: 胡勇华(huyh@hnust.cn)
  • 作者简介:tangzhenchina@163.com
  • 基金资助:
    湖南省自然科学基金(2017JJ3087);国家自然科学基金资(61308001,61872138)

Research on DSP Register Pairs Allocation Algorithm with Weak Assigning Constraints

TANG Zhen, HU Yong-hua, LU Hao-song, WANG Shu-ying   

  1. School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China
  • Online:2021-06-10 Published:2021-06-17
  • About author:TANG Zhen,born in 1994,postgraduate.His main research interests include DSP compilation and so on.
    HU Yong-hua,born in 1981,Ph.D,professor,supervisor.His main research interests include DSP compilation and so on.
  • Supported by:
    Hunan Provincial Natural Science Foundation of China(2017JJ3087) and National Natural Science Foundation of China(61308001,61872138).

摘要: 在现代高性能数字信号处理器(DSP)中,许多指令把寄存器偶对作为操作数。为了优化寄存器偶对的使用,文中针对寄存器偶对的使用约束条件,提出了一种基于弱约束指派的DSP寄存器偶对分配算法。该算法在寄存器指派过程中优先指派空闲寄存器偶对给符号寄存器对。如果无法指派寄存器偶对给符号寄存器对,则指派两个不能组成寄存器偶对的寄存器。为了确保目标代码中寄存器偶对操作数最终获得的寄存器偶对符合寄存器偶对的使用约束条件,提供了一种指令操作数修正方法。采用6种经典的算法作为测试用例进行实验,结果表明所提算法的实验效果较好。

关键词: DSP, 编译优化, 寄存器偶对, 全局寄存器分配, 图着色方法

Abstract: In modern high performance digital signal processors (DSP),many instructions regard register pairs as operands.To optimize register pair usage,this paper presents a register pairs allocation algorithm for DSP based on weak constraint assignment for the rules of using register pairs.In the process of register assignment,the priority of this algorithm is to assign idle register pairs to symbol register pairs.If it is not possible to assign register pairs to symbol register pairs,two registers that cannot be made up of a register pair are assigned.In order to ensure that the register pairs in the target code are consistent with the rules of register pairs,this paper provides an instruction operand correction method.This paper uses six classical algorithms as test cases.The experimental results show that the proposed algorithm is effective.

Key words: Compiler optimization, DSP, Global register allocation, Graph coloring method, Register pairs

中图分类号: 

  • TP311
[1] LORENZ M,WEHMEYER L,THORSTEN D.Energy aware compilation for DSPs with SIMD instructions[C]//Proc.of the Joint Conf.on Languages,Compilers and Tools for Embedded Systems.2002,37(7):94-101.
[2] NI Y H,CHEN W W,WANG L,et al.Optimization of Register Allocation Strategy for MLC STT-RAM[J].Computer Science,2018,45(S1):562-567.
[3] EISL J,MARR S,WÜRTHINGER T,et al.Trace Register Allocation Policies:Compile-Time vs.Performance Trade-Offs[C]//Proc. of the 14th International Conf.on Managed Languages and Runtimes.2017:92-104.
[4] POLETTO M,SARKAR V.Linear scan register allocation[J].ACM Trans.on Programming Languages and Systems,1999,21(5):895-913.
[5] WIMMER C,FRANZ M.Linear scan register allocation on SSA form[C]//IEEE/ACM International symp.on Code Generation and Optimization.2010,170-179.
[6] KANANIZADEH S,KONONENKO K.Improving on LinearScan Register Allocation[J].International Journal of Automation and Computing,2018,15(2):228-238.
[7] CHAITIN G J.Register allocation and spilling via graph coloring[C]//Symp.on Compiler Construction.1982:98-105.
[8] CHAITIN G J,AUSLANDER M A,CHANDRA A K,et al.Register allocation via coloring[J].Computer Languages,1981:47-57.
[9] BRIGGS P,COOPER K D,TORCZON L.Improvements tograph coloring register allocation[J].Trans.on Programming Languages and Systems,1994,16(3):428-455.
[10] WU S N,LI S K.A Hyrid Evolutionary Algorithm for Register Allocation of Embedded Processors[J].Computer Science,2007,34(8):278-280.
[11] NICKERSON B R.Graph coloring register allocation for processors with multi-register operands[J].Programming Language Design and Implementation,1990,25(6):40-52.
[12] BRIGGS P,COOPER K D,TORCZON L.Coloring register pairs[J].ACM Letters on Programming Languages and Systems,1992,1(1):3-13.
[13] SMITH M D,HOLLOWAY G.Graph-coloring register allocation for irregular architectures[J].Submitted to PLDI,2000,1:1-8.
[14] Intel® 64 and IA-32 Architectures Software Developer's Manual.Intel Corporation[G].2019.
[15] Processor Programming Reference (PPR) for AMD Family 17h Models 01h,08h,Revision B2 Processors[G].Advanced Micro Devices.2019.
[16] YHFT-Matrix2 DSP instruction set manual[G].Institute of Microelectronics.College of Computer Science and Technology,National University of Defense Technology.2013.
[17] ARM946E-S (Rev1) System-on-Chip DSP enhanced processor Product Overview[G].ARM Limited.2000.
[1] 陆浩松, 胡勇华, 王书盈, 周新莲, 李慧祥.
向量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
[2] 胡伟方, 陈云, 李颖颖, 商建东.
基于数据重用分析的多面体循环合并策略
Loop Fusion Strategy Based on Data Reuse Analysis in Polyhedral Compilation
计算机科学, 2021, 48(12): 49-58. https://doi.org/10.11896/jsjkx.210200071
[3] 池昊宇, 陈长波.
基于神经网络的循环分块大小预测
Prediction of Loop Tiling Size Based on Neural Network
计算机科学, 2020, 47(8): 62-70. https://doi.org/10.11896/jsjkx.191200180
[4] 邱亚琼, 胡勇华, 李阳, 唐镇, 石林.
基于两类寄存器互为缓存方法的DSP寄存器分配溢出处理优化算法
Optimization Algorithm of Complementary Register Usage Between Two Register Classesin Register Spilling for DSP Register Allocation
计算机科学, 2019, 46(6): 196-200. https://doi.org/10.11896/j.issn.1002-137X.2019.06.029
[5] 王建中,杨璐.
高速实时系统数据采集与传输
Data Acquisition and Transmission in High Speed Real-time System
计算机科学, 2016, 43(Z11): 604-606. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.137
[6] 周国昌,郭宝龙,高翔,王健,闫允一.
基于分布函数的WCET快速估计
Fast Estimation of WCET Based on Distribution Function
计算机科学, 2016, 43(5): 157-161. https://doi.org/10.11896/j.issn.1002-137X.2016.05.029
[7] 杨琳,吴家铸,扈啸,田希.
互相关运算在银河飞腾DSP上的实现及优化
Realization and Optimization of Cross-correlation Based on YHFT-QDSP
计算机科学, 2015, 42(11): 53-55. https://doi.org/10.11896/j.issn.1002-137X.2015.11.009
[8] 王望,姚淑珍,谭火彬.
基于DSPN的TTE总线建模与性能分析
Modeling and Performance Analysis of TTE Bus Based on DSPN
计算机科学, 2014, 41(7): 45-48. https://doi.org/10.11896/j.issn.1002-137X.2014.07.008
[9] 葛红美,徐超,陈念,廖希密.
一种面向嵌入式系统总线的低功耗优化方法
Low Power Optimization Method Oriented to Embedded System’s Bus
计算机科学, 2013, 40(12): 31-36.
[10] 卞东亮 陈长兴 彭沙沙 牛德智 王博.
DSP在数据链终端机安全中的应用
Application of DSP in the Data Security of Data Link Terminal
计算机科学, 2012, 39(Z11): 14-15.
[11] 邹修国.
一种基于蠕虫算法的并行DSP网络结构探测
Framework Detecting in Parallel DSP Network Based on Wormhole Algorithm
计算机科学, 2011, 38(Z10): 76-77.
[12] 田祖伟,孙光.
基于谓词代码的编译优化技术研究
Research of Compiler Optimization Technology Based on Predicated Code
计算机科学, 2010, 37(5): 130-133.
[13] 苏曙光,苏月明,刘云生.
基于DSP多通道视频编码终端的设计
Design and Implement of Multichannel Video Coding Terminal Based on DSP
计算机科学, 2009, 36(9): 252-254.
[14] .
基于汇编代码的指令调度器的设计与实现

计算机科学, 2009, 36(3): 45-47.
[15] .
一种基于动态S-盒P-盒的快速分组密码算法——DSP

计算机科学, 2009, 36(2): 78-81.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!