摘要：在分区内存体系结构中，如何尽可能少地插入片选指令是研究的热点。根据该问题的特点，构建了片选优化的图划分模型，并在该模型的基础上，提出了一种二阶段启发式搜索算法求解该问题。该算法首先根据节点自身的大小与图中分区大小快速获得一个初始可行解，然后在该可行解基础上利用节点之间边的权值和分区之间的权值作为启发式参数，搜索更优的解。通过对MiBench用例集和实际嵌入式系统的测试，验证了该模型及相应启发式算法的有效性，相对于VPAB算法，平均优化率达到37．99％，略优于成熟的商用编译器PICC，大幅度减少了片选指令的数量。

关键词：分区内存 图模型 启发式搜索 嵌入式系统 

单位：中国电子科技集团公司第十四研究所 江苏南京210039 武汉大学计算机学院 湖北武汉430072