ARM Linux的Gameboy模拟器移植和优化研究04 模拟器, 寄存器, Linux, 技术

samwalton

本文采用了与机器相关优化的优化技术,与机器相关的优化这里主要是寄存器分配问题,一般寄存器分配算法是基于一种称为图着色技术的。给定一个无向图G= (V , E ) ,V 是有限节点的集合,V = { v 1, v 2, ., v n} , E是边的集合, E = { ( i, j ) | v i∈V , v j∈V , v i和v j相连} , 图着色问题要求找到一个k尽量小的所有节点的赋值(也称“完全赋值”) C: V — > {1.k } , 要求在该完全赋值中, 若( i,j ) ∈E , 则C ( v i) ≠C ( vj) 。
　　简化的图着色技术应用
　　针对本文的优化,第一阶段是把C函数用伪ARM汇编指令(即用符号寄存器Ui替代真正ARM寄存器的arm指令)改写。
　　第二阶段对符号寄存器U1～Un ( n > 15)画出相干图并进行着色,所谓对图进行着色是指给图中的每个结点赋予一种颜色,而且所有相邻的两个结点都具有不同的颜色。这样,每种颜色就对应于处理器中的一个实际的物理寄存器,如此着色保证了所有可能发生冲突的符号寄存器都被赋予不同的物理寄存器。
　　假设n + 1个符号寄存器的相干图如图5 ( a)所示,其中结点是符号寄存器,而结点之间的弧线表示变量的生命周期有重叠,最少需要16种颜色才能避免相连结点颜色有重叠。由于arm920T只有r0～r14等15个寄存器可用于存储程序变量,小于16,也就是存在寄存器冲突问题,这个时候就可以通过选择删除一个结点(如图中Un + 1) ,也就是把U6对应的数据存储到存储器中,以后再重装入寄存器来达到对各寄存器进行释放的目的,见图5 ( b)所示,虚线圆圈表示符号寄存器U16对应的数据转存到存储器中。

　　用上面介绍的方法对updatepatp ix和bg scan color函数进行处理,得到的arm汇编函数,用它们替换掉gnuboy源代码中原先的C函数并进行编译生成可执行文件,可执行文件在构建的测试板上运行良好。下面对上面提到的优化来进行一些测试。
　　测试评估
　　用CodeWarrior forarm Developer Suite和AXD Debugger软件测试优化前后函数的运行时间,结果如表1所示。图着色技术强调实现活跃变量的100%分配,并且代码需要寄存器数量越多,优化效果越明显,这从updatapatp ix和bg scan color函数的优化中可以看出(前者代码较后者复杂,需要存放的临时变量也多) 。进一步优化gnuboy,可用类似的方法替换源代码的另外一些影响速度较大的函数。

　　总结
　　本文构建了一个基于arm920T嵌入式Linux的实验平台环境, gnuboy作为一种虚拟机,应用到这样的嵌入式环境中遇到的问题具有一定的代表性,最需要解决的问题是速度问题,针对于此,本文实现了它在所构建的平台上的移植和一些优化研究。