标题: 以整数线性规划作为在混合指令集架构下之暂存器重指派方法达成程式码减量
Code Size Reduction by Integer Linear Programming for Register Reassignment in Mixed-Width ISA Processors
作者: 陈柏村
Chen, Po-Tsun
单智君
Shann, Jyh-Jiun
资讯科学与工程研究所
关键字: 程式码减量;混合指令集架构;暂存器重指派;整数线性规划;Code Size Reduction;Mixed-Width ISA;Register Reassignment;Integer Linear Programming
公开日期: 2010
摘要: 在嵌入式系统中,程式码大小是与效能一样重要的议题,特别是针对记忆体受限制之系统,因此减少记忆体使用之相关研究亦是蓬勃发展。而其中一种减少记忆体使用的方式为使用混合指令集架构。这种架构通常提供二种不同长度的指令集,一般为 16 位元的短指令及32位元的长指令。在商业化的产品中,如ARM、MIPS、Andes都提出此种指令集架构,用来减少精简指令集架构所产生之机器码过大问题。我们的研究数据显示,约有49% 的指令其指令格式需至暂存器指定完后,才能决定其指令格式为16位元短指令或32位元长短令;因此如何在混合指令架构下,妥善指派暂存器是非常重要的。暂存器重指派主要是藉由重新指定暂存器编号来达成不同目的之优化;在先前的研究中,在混合指令集架构下之暂存器重指派问题已经被证明是NP问题,因此解决的方法大多也是用Heuristic的方式来得出可行解。在此篇论文研究中,我们使用了整数线性规划来求解在混合指令架构下之暂存器重指派问题。在不考虑编译时间的条件下,我们约可减少34.4% 的机器码大小。
Code size issue for a memory constrained embedded system is as important as performance. There are many researches that devote to this issue. One way of reducing code size is to exploit compact instruction formats. A mixed-width ISA may provide this kind of feature for the Reduce Instruction Set Computer (RISC) processors. In general, it usually provides two different widths of instruction formats: short and long instruction format. In commercial, ARM, MIPS and Andes all support this feature in their products. From our research, the formats of 49% instructions can be decided only after register assignment. Therefore, the register assignment policy is very important for mixed-width ISA. Register reassignment renumbers the registers in each instruction for specific goals. Register reassignment for mixed-width ISA has been proved to be an NP problem. Some researches have devoted to design heuristic algorithms to find the feasible solutions. In this thesis, we use integer linear programming to solve the register reassignment problem in mixed-width ISA for reducing the code size. On the average, we reduce about 34.4% code size compared to the original program.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079755537
http://hdl.handle.net/11536/45882
显示于类别:Thesis


文件中的档案:

  1. 553701.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.