基于优化遗传算法改进软硬件划分效率的技术实现方法

摘要

一种基于优化遗传算法改进软硬件划分效率的技术实现方法，含有模块间的紧密性度量、层次结群算法和遗传算法加速等步骤。其特征在于它依次包含如下步骤：先通过数据输入预处理，创造性引入模块间的紧密性度量的概念，通过紧密性度量再利用层次结群算法将最初的划分图生成层次结点树，通过这种预处理之后，利用混合粒度的遗传算法，可以得到细粒度的划分结果，同时具有粗粒度的划分效率。初始个体生成后通过本发明引入的选择策略来对交配算子变异算子保存最佳个体，最后经由判敛规则，若不收敛则返回重新进行策略选择。发明的紧密性度量原则的技术方法在软硬件划分的准确度及粒度划分的自动化程度优于一般的遗传算法，并且在运行处理时间上要少。优化了层次结点树的构成，使得软硬件划分的执行效率得以提高。

主权项

1.一种基于优化遗传算法改进软硬件划分效率的技术实现方法，含有模块间的紧密性度量、层次结群算法和遗传算法的加速等步骤，其特征在于它依次包含如下步骤：(1)读入系统的功能描述：用SystemC或VHDL语言来描述系统功能实现；(2)编译与模块提取：对于SystemC或VHDL的语言描述，在进程级进行模块提取，得到系统的模块连接图，并且评估模块的计算负载和模块间的通信量等，作为划分的数据；(3)计算模块间的紧密性度量：基于模块连接图的结点和边信息，定义出模块的紧密性度量：closeness＝0.5×connectivity+0.5×balancedsize，$\mathrm{connectivity}=\frac{C_{\mathrm{ij}}}{{\Sigma }_{k\ne j}{C}_{\mathrm{ik}}+{\Sigma }_{k\ne i}{C}_{\mathrm{jk}}},$ 其中Cij为结点i，j之间的连接边数，$\mathrm{balancedsize}=\frac{\left|V\right|-\left(\right|V_i|+|V_j\left|\right)}{\left|V\right|},$ 其中V为模块的面积；(4)进行层次结群操作：利用层次结群算法，依据模块间的紧密性度量，对模块连接图的结点进行多路结群操作，生成层次结点树；(5)初始个体生成：每个层次划分图都对应于一棵层次生成树，故初始个体的产生等价于由层次结点树生成一棵层次生成树；(6)对产生的种群进行组合选择操作：具体的组合选择方法如下：a)如果方差大于某一个值时采用排序选择算子，按奇数或偶数位选取一半个体，余下的一半采用赌轮法来选取；b)如果方差小于某一个值时用锦标赛策略；(7)进行混合粒度遗传算法的余下操作：首先进行交配操作，其次是变异操作，然后保存最佳个体，最后判断遗传算法是否收敛：否，则返回步骤(6)；是，则算法结束，输出最佳个体，即找到优化解。