计算机科学 ›› 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: DSP, Compiler optimization, 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] 池昊宇, 陈长波. 基于神经网络的循环分块大小预测[J]. 计算机科学, 2020, 47(8): 62-70.
[2] 邱亚琼, 胡勇华, 李阳, 唐镇, 石林. 基于两类寄存器互为缓存方法的DSP寄存器分配溢出处理优化算法[J]. 计算机科学, 2019, 46(6): 196-200.
[3] 王建中,杨璐. 高速实时系统数据采集与传输[J]. 计算机科学, 2016, 43(Z11): 604-606.
[4] 周国昌,郭宝龙,高翔,王健,闫允一. 基于分布函数的WCET快速估计[J]. 计算机科学, 2016, 43(5): 157-161.
[5] 杨琳,吴家铸,扈啸,田希. 互相关运算在银河飞腾DSP上的实现及优化[J]. 计算机科学, 2015, 42(11): 53-55.
[6] 王望,姚淑珍,谭火彬. 基于DSPN的TTE总线建模与性能分析[J]. 计算机科学, 2014, 41(7): 45-48.
[7] 葛红美,徐超,陈念,廖希密. 一种面向嵌入式系统总线的低功耗优化方法[J]. 计算机科学, 2013, 40(12): 31-36.
[8] 卞东亮 陈长兴 彭沙沙 牛德智 王博. DSP在数据链终端机安全中的应用[J]. 计算机科学, 2012, 39(Z11): 14-15.
[9] 邹修国. 一种基于蠕虫算法的并行DSP网络结构探测[J]. 计算机科学, 2011, 38(Z10): 76-77.
[10] 田祖伟,孙光. 基于谓词代码的编译优化技术研究[J]. 计算机科学, 2010, 37(5): 130-133.
[11] 苏曙光,苏月明,刘云生. 基于DSP多通道视频编码终端的设计[J]. 计算机科学, 2009, 36(9): 252-254.
[12] . 基于汇编代码的指令调度器的设计与实现[J]. 计算机科学, 2009, 36(3): 45-47.
[13] . 一种基于动态S-盒P-盒的快速分组密码算法——DSP[J]. 计算机科学, 2009, 36(2): 78-81.
[14] 陈升来,郑爱民,李涛. 基于小波编码的巡航导弹图像压缩方法研究[J]. 计算机科学, 2009, 36(12): 263-266.
[15] . 一种基于FPGA高集成化的直接数字频率合成系统的设计[J]. 计算机科学, 2007, 34(10): 299-300.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 方磊, 武泽慧, 魏强. 二进制代码相似性检测技术综述[J]. 计算机科学, 2021, 48(5): 1 -8 .
[2] 朱雨, 庞建民, 徐金龙, 陶小涵, 王军. 面向SW26010处理器的三维Stencil自适应分块参数算法[J]. 计算机科学, 2021, 48(6): 10 -18 .
[3] 冯芙蓉, 张兆功. 目标轮廓检测技术新进展[J]. 计算机科学, 2021, 48(6A): 1 -9 .
[4] 孙正, 张小雪. 生物光声成像中声反射伪影抑制方法的研究进展[J]. 计算机科学, 2021, 48(6A): 10 -14 .
[5] 周欣, 刘硕迪, 潘薇, 陈媛媛. 自然交通场景中的车辆颜色识别[J]. 计算机科学, 2021, 48(6A): 15 -20 .
[6] 黄雪冰, 魏佳艺, 沈文宇, 凌力. 基于自适应加权重复值滤波和同态滤波的MR图像增强[J]. 计算机科学, 2021, 48(6A): 21 -27 .
[7] 江妍, 马瑜, 梁远哲, 王原, 李光昊, 马鼎. 基于分数阶麻雀搜索优化OTSU肺组织分割算法[J]. 计算机科学, 2021, 48(6A): 28 -32 .
[8] 张子丞, 谭志苇, 张晨瑞, 王旋, 刘晓璇, 俞一彪. 基于高低频带对数能量谱比贝叶斯决策的语音端点检测[J]. 计算机科学, 2021, 48(6A): 33 -37 .
[9] 崔雯昊, 蒋慕蓉, 杨磊, 傅鹏铭, 朱凌霄. 结合MCycleGAN与RFCNN实现太阳斑点图高分辨重建[J]. 计算机科学, 2021, 48(6A): 38 -42 .
[10] 田洋, 毕秀丽, 肖斌, 李伟生, 马建峰. 基于离散切比雪夫变换的图像接缝裁剪篡改检测[J]. 计算机科学, 2021, 48(6A): 43 -50 .