基于FPGA(Field-programmable gate array)的可重构混合计算系统主要由通用处理器GPP(General purpose processor)和可重构加速单元RAUs(Reconfigurable acceleration units)两部分构成,其中,FPGA的可扩展、高速并行等特性为高性能计算提供了硬件支持,GPP的灵活性则为高性能计算提供了软件支持。为了使两种运算部件都能够发挥各自优势,设计人员需要通过软硬件划分方法,将应用程序所需完成的功能有效地分配到两个运算部件上。因此研究面向基于FPGA的可重构混合系统的软硬件划分方法对于充分发挥可重构混合系统的结构优势、构建灵活高效的可重构混合系统十分重要。

自20世纪90年代初CODES研讨会针对软硬件划分问题,首次提出“模型+算法”^{[ 1]}的解决方案后,人们研究了各具特色的划分模型和划分算法,其中最常用的划分模型是任务图,划分算法有遗传算法^{[ 2, 3]}、模拟退火算法^{[ 4]}、禁忌搜索算法^{[ 5]}等。已有划分方法通常默认应用程序在硬件处理器上只有一种实现方式,实际上一段应用程序可能存在多种硬件实现方式,这种多样性主要来源于循环。循环是应用程序中耗时较长的代码,将其展开放在硬件上执行可以增加其并行性,提高性能,但同时循环展开也占用了更多的硬件面积。结合循环展开、循环流水灯面向硬件的并行优化技术,一段应用程序可能会有上百种不同的硬件实现方式^{[ 6]}。

Stitt^{[ 7]}提出了一种BUB启发式算法,同时解决软硬件划分问题及划分中的子问题:硬件多种实现方式选择问题,并将该问题称为PIE(Partitioning w/multi-version implementation exploration)。文献[7]是第一个在求解划分问题的同时确定硬件实现方式的方法,实验结果表明,与FI(选择最快速的硬件实现方式)方法和NE(不考虑多种实现方式,使用最简单的硬件实现方式)方法比较,PIE达到的平均加速比要高于FI和NE。但BUB启发式算法采用了贪婪算法,易陷入局部最优。

遗传算法(Genetic algorithm,GA)是一种模仿生物进化过程的全局优化随机搜索算法,具有简单、通用性高、鲁棒性强等优点,据此本文提出一种改进遗传算法求解PIE问题,算法根据硬件多种实现方式的延时-面积互斥特征,结合Q-学习算法与贪婪规则,改进遗传算法的变异算子,增强遗传算法的局部搜索能力。实验结果表明,本文方法具有良好的效果。

本文采用的目标系统结构是由一个GPP和一个RAU构成的可重构混合架构,如图1所示。GPP和RAU以松耦合的方式实现数据通信,GPP从存储器MEM中读取数据并提供给RAU,RAU独立执行计算,计算完成后再将计算结果写回GPP,GPP和RAU不能并行执行。该结构已被应用在多个领域^{[ 8, 9]}。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 目标系统结构Fig.1 System architecture

循环有多种硬件实现方式,包含循环的函数等粗粒度程序结构自然也有多种硬件实现方式。因此本文的划分粒度可以是循环、函数等。为方便问题描述,本文选取函数为划分粒度,以函数调用图作为输入来描述PIE问题:给定一个调用图的节点集合,及每个节点的硬件实现方式集合,确定哪些节点应该在硬件上实现,以及在硬件上实现时采用哪一种实现方式,目标是在满足给定硬件面积约束 a_constraint的条件下,最小化应用程序总体运行时间 t_sys实现性能的最优化。

PIE问题的形式化描述如下:划分算法的输入用三元组< R, a_constraint, t_total>表示, t_total是当整个应用程序都在软件上运行时的总运行时间, R是节点集合,可表示为二元组< t_SW, I>, t_SW是一个节点在软件上的运行时间, I是一个节点的所有硬件实现方式的集合,可用三元组< a, t_hw, t_comm>表示,其中 a、 t_hw、 t_comm分别是一种硬件实现方式所需的硬件面积、运行时间及软硬件间通信时间。问题定义为:将 R中的每一个节点选择为0或者1,创建一个解集合 S,使划分目标最小,划分目标如式(1)所示:

式中: t_{sw, R}是集合 R中一个节点的软件运行时间; t_{hw, I}是该节点被选定的硬件实现方式的硬件运行时间; t_{comm, I}是使用该硬件方式时所需的通信时间。除减少性能外,每一个划分集合 S还必须满足下列约束条件,如式(2)所示:

式中: a_I是集合 S中实现每一个节点的硬件面积。

遗传算法本身具有较强的全局搜索能力,但局部搜索能力较弱。在选择、交叉、变异算子中,遗传算法的局部搜索能力主要依靠变异算子,该算子的随机变异策略容易对优秀的染色体造成破坏,产生较差的个体。因此本文提出了一种改进的遗传算法,该算法依据硬件实现方式的延时-面积互斥特征,采用基于Q-学习算法的自适应变异算子,增强遗传算法的局部搜索能力。

改进的遗传算法主要包括以下几个步骤:①初始化种群及Q表;②对种群中父代个体进行选择、交叉操作;③根据种群中各个个体的状态,使用Q学习算法,从设定的动作集中自适应选择变异策略,产生子代个体;④使用子代个体代替父代个体;⑤重复②、③、④步骤,直到满足终止准则,选择出最优解。

为了验证算法的可行性,本文使用基准测试用例MiBench中tmndec、tmn、djpeg、cjpeg、jm10.2五个应用程序作为输入,以函数为节点,使用GCC的gprof工具^{[ 11]}获得五个应用程序的函数调用图,节点数量分别为27、36、88、101、215,节点和边的运行时间及硬件面积采用伪随机数,且按以下原则生成:①硬件运行时间、通信时间之和比软件运行时间短;②一个节点的硬件实现方式个数取1~8的随机数;③同一个节点的多种硬件实现方式中,占用硬件面积越大的实现方式,其相应的硬件运行时间越短;④为了使不同节点的实验结果具有可比性,硬件面积约束值 a_constraint与节点数相关,计算公式如式(11)所示:

式中: n是指节点个数; ha_max为各节点的硬件实现方式所用的最大硬件面积,本文设定总硬件面积约束值为各个节点最大硬件面积和的30%。

算法测试环境为Intel(R) Core(TM)2 2.26 GHz CPU,400 MB内存;操作系统为Fedora 10。本文使用C++编程实现了BUB算法、标准遗传算法及本文算法。表1列出了分别使用三种算法解决PIE问题的实验结果,其中标准遗传算法采用随机变异原则,变异率取0.01,其他参数与本文算法相同。其中 N表示节点数, a_S是划分后应用程序所占硬件面积,提高百分比是指标准遗传算法和本文算法相对于BUB算法提高的百分比。从表1数据可以看出,对于所有节点,本文算法划分结果 t_sys比BUB算法和标准遗传算法都要小,且本文算法提高的百分比要比标准遗传算法大,可见在满足硬件面积约束的条件下,本文算法生成的解要优于标准遗传算法及BUB算法。

表1

Table 1

表1(Table 1)

表1 BUB算法、标准遗传算法与本文算法的实验结果对比 Table 1 Result comparison of BUB algorithm, standard GA and proposed algorithms N ttotal aconstraint BUB算法 GA算法 本文算法 提高百分比% tsys aS tsys aS tsys aS GA算法 本文算法 27 1644087 1155 741056 1140 520578 1154 521887 1155 29.75 29.58 36 1398766 1653 801195 1646 585039 1649 569548 1653 26.98 28.91 88 4072975 3852 2137639 3849 1723416 3839 1638696 3852 19.38 23.34 101 5192855 4594 2427948 4590 2034598 4576 1851037 4593 16.2 23.76 215 11113833 9611 6074043 9576 5054388 9611 4475093 9607 16.79 26.32

表1 BUB算法、标准遗传算法与本文算法的实验结果对比 Table 1 Result comparison of BUB algorithm, standard GA and proposed algorithms

本文对比了BUB算法、遗传算法和本文算法的收敛性。图2为节点数为215、88的应用程序示范系统运行10次, 划分过程中平均每代最佳有效个体的目标函数曲线。从图2中可看出,经过多次迭代后,与标准遗传算法相比,本文算法收敛速度更快,得到的解更好。本文算法的初期收敛动力来自于变异算子本身,遗传算法本身的大量迭代次数又保证了Q-学习算法的快速收敛,因此本文算法的收敛速度比较快。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 目标函数曲线Fig.2 Objective function curve

作者提出了一种改进的遗传算法,该算法在求解软硬件划分问题的同时解决了硬件多种实现方式的探索。为了验证本文算法的可行性,分别测试了MiBench中五个应用程序,通过与BUB算法、标准遗传算法进行比较,结果表明本文算法的搜索质量和算法执行时间都得到了提升。另外划分过程中生成的目标函数曲线,验证了本文算法具有较好的收敛性。本文针对PIE问题的求解,改进了遗传算法的变异算子,而其他对遗传算法的改进方法(例如改进种群初始化、改进交叉等)也可以与本文算法相结合,这也是下一步的研究工作。