基于最大完全子图的嵌入式系统寄存器分配方法

摘要

本发明提出了一种基于最大完全子图的嵌入式系统寄存器分配方法，主要解决现有启发式算法分配效果较差，进化算法在交叉算子部分由于没有考虑溢出代价而造成溢出代价太大的问题。其实现步骤是：(1)对中间变量相互干扰图取补图，得到补图G；(2)将所有结点随机分成两类，分别放入集合A或者集合B，并完成对种群的初始化；(3)运用基于溢出代价的最大完全子图交叉算子SC-MCX对种群中的个体进行交叉，产生子代个体；(4)对子代个体利用局部搜索算子LSP进行优化后替换掉父代个体中适应度函数值最大的一个个体，继续参与种群进化。本发明加快了种群进化速度，降低了个体的溢出代价和溢出变量个数，可用于嵌入式系统寄存器分配中。

主权项

1.一种基于最大完全子图操作的嵌入式系统寄存器分配方法，包括：(1)初始化种群步骤1a)绘制程序编译过程中产生的中间变量的相互干扰图H，在干扰图H中，每一个结点代表一个中间变量，每一条边所连接的两个结点相互干扰，并且给出每个中间变量的溢出代价，溢出代价即嵌入式系统从存储器中存取中间变量所花费的时间；1b)取出相互干扰图H的补图G＝{N，S，V，E}，其中，N代表中间变量总数，S代表寄存器数量，每个寄存器用R_i，i＝1…S表示，V代表所有中间变量的结点集，结点分别标记为0，1，2，...，N-1，E代表所有的无向边的集合，在补图G中，每一条边所连接的两个结点放在同一个寄存器中，使得溢出代价和溢出变量个数尽可能的小；1c)将中间变量的结点集V中的N个结点随机的分成两类，分别用A和B来表示；1d)根据补图G绘制集合A中所有结点之间的邻接关系图G_A＝(V_A，E_A)，其中V_A＝A，对于V_A中任意的两个结点v_i，v_j，当v_i和v_j能放在同一个寄存器中时，将v_i与v_j相连；1e)寻找邻接图G_A的一个最大完全子图，将该最大完全子图中包含的结点v_k放入下标最小的空寄存器中；1f)从G_A中删除步骤1e)已经放入寄存器中的结点v_k，得到G_A更新后的子图G_A′；1g)对子图G_A′重复步骤1e)-1f)直到S个寄存器均被使用为止，然后将子图G_A′中剩余结点和集合B中的结点按照冲突最小原则放入到寄存器中；1h)给定种群规模为M，M设定为任意偶数，将步骤1c)-1g)重复执行M次产生M个个体，分别用Ind_i，i＝1...M表示每个个体，完成种群的初始化；(2)使用交叉算子产生一个新的子代个体步骤2a)使用基于溢出代价的最大完全子图交叉算子SC-MCX对种群中的个体Ind_p和Ind_p+1进行交叉产生一个新的子代个体，用offspring_p表示，其中p＝1，3，5，...且p＜M；2b)根据补图G绘制两个父代个体${\mathrm{Ind}}_p=\{R_1^p,...,R_S^p\}$和${\mathrm{Ind}}_{p+1}=\{R_1^{p+1},...,R_S^{p+1}\}$中每个寄存器所包含的结点构成的邻接关系图，分别用和表示；2c)找出每个邻接关系图的一个最大完全子图，分别用和表示，从中选出溢出代价最大的最大完全子图其中t∈{p，p+1}，l∈{1，...，S}，将包含的结点率先放入子代个体${\mathrm{offspring}}_p=\{R_1^{\mathrm{os}},...R_S^{\mathrm{os}}\}$的第一个寄存器中；2d)从所有结点中选取与中结点不相冲突的结点放入寄存器中，完成对子代个体offspring_p第一个寄存器的构造，并将已经放入寄存器中的结点从两个父代所包含的所有寄存器中删除；2e)重复步骤2b)-2c)依次构造子代offspring_p中剩余的寄存器；2f)将父代个体中剩余的结点，按照冲突最小原则依次放入子代相应的寄存器中，完成对父代个体Ind_p和Ind_p+1的交叉，产生出子代个体offspring_p。(3)用局部搜索算子LSP优化子代个体步骤3a)对步骤2f)中产生的每一个子代个体offspring_p，采用局部搜索算子LSP进行优化，用优化后的个体替换掉种群中个体Ind_p和Ind_p+1适应度函数值最大的一个，继续参与种群进化；3b)设定迭代次数为K，对步骤2a)-3a)重复执行K次，就能将所有的结点高效的分配到寄存器中，达到溢出代价和溢出变量个数最小。