基于混合式两阶段的动态部分重构FPGA软硬件划分算法
马昱春1, 张超1, LukWayne2    
1. 清华大学计算机科学与技术系, 北京 100084;
2. 帝国理工大学电子计算学系, 伦敦 SW72BZ
摘要:动态部分重构的特性大大提高了硬件设计的灵活性, 但传统的软硬件划分算法不再适用于针对这类硬件的系统设计。部分研究考虑了动态部分重构的特性, 并建立了混合整数线性规划(MILP)模型进行求解。但是由于MILP自身的限制, 求解时间特别长, 只能处理规模较小的问题。为了能够处理规模较大的问题, 并且缩短求解时间, 该文对MILP方法进行了详细的分析, 并且通过启发式算法确定部分关键任务的状态, 从而减小MILP的规模, 加快求解速度。实验结果表明: 与传统的数学规划方法相比, 在求解质量不变的情况下, 该算法可以得到最高约200倍的速度提升。
关键词软硬件划分    动态部分重构    启发式    混合整数线性规划    
Hybrid two-stage HW/SW partitioning algorithm for dynamic partial reconfigurable FPGAs
MA Yuchun1, ZHANG Chao1, LUK Wayne2    
1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2. Department of Computing, Imperial College, London SW72BZ, UK
Abstract: More and more hardware platforms are providing dynamic partial reconfiguration; thus, traditional hardware/software partitioning algorithms are no longer applicable. Some studies have analyzed the dynamic partial reconfiguration as mixed-integer linear programming (MILP) models to get solutions. However, the MILP models are slow and can only handle small problems. This paper uses heuristic algorithms to determine the status of some critical tasks to reduce the scale of the MILP problem for large problems. Tests show that this method is about 200 times faster with the same solution quality as the traditional mathematical programming method.
Key words: HW/SW partitioning    dynamic partial reconfiguration    heuristic method    mixed-integer linear programming (MILP)    

硅技术的持续发展使得片上系统设计逐渐变得可行,带有处理器、嵌入式存储单元和硬件逻辑部分的现场可编程门阵列(FPGA)是最常见的实验平台。越来越多的硬件开始支持动态部分重构的特性,允许硬件的一部分资源在其他部分保持运行的时候进行重新配置,从而实现了资源的时分复用,提高了硬件资源的利用率。

但是,动态部分重构也使得硬件不再固定,从而给软硬件划分带来了新的问题: 此前,软硬件划分算法只需要决定一个任务应该放在软件上还是硬件上执行,现在却需要决定它是否要放在部分重构区域上执行。此外,重新配置硬件会带来额外的时间开销,也增加了设计的复杂性。因此,传统的软硬件划分方法不再适用。

在传统的软硬件协同设计流程中,软硬件划分以程序的总执行时间为优化目标。优化方法主要分为2类: 一类是随机优化方法如模拟退火[1]和蚁群算法[2, 3]等,但随机优化方法得到的解并不稳定,收敛速度也很慢; 另一类方法是数学规划分析方法如混合整数线性规划(MILP)[4, 5]等,但数学规划分析方法由于变量和约束条件较多,需要很长的求解时间,不能解决大规模的问题。

原始的软硬件划分可以视为背包问题[6],但是考虑动态重构特性之后,问题发生了变化。Banerjee 等[7]结合FPGA的物理结构和动态部分重构特性,提出了一种整数线性规划方法以期得到最优解,却无法处理大规模问题,也与现在的工业设计流程不符合。刘鹏等[8]把禁忌搜索和模拟退火这2种随机优化方法结合起来使用,效果有所提高,但是由于随机优化算法本身的限制,依然存在解不稳定以及收敛速度慢等问题。

总体而言,已有的大部分研究成果都是独立的随机优化方法或者数学规划分析方法,并没有把两者综合起来。为了支持动态部分重构的FPGA的软硬件划分,并且在可接受的时间内得到比较好的划分结果,本文对数学规划分析方法特别是MILP进行了仔细分析,发现可以通过事先决定部分关键任务的状态来减少变量和约束的个数,进而减小问题规模。本文采用基于贪婪策略的启发式算法选取关键任务,并且决定它们的状态,再采用MILP对剩余问题进行求解,得到了较好的解。

1 问题描述 1.1 目标系统结构

本文针对图1的系统结构来考虑相应的任务的软硬件划分,系统由软件和带有动态部分重构能力的硬件这2部分组成。

图1 目标系统结构

被分配到软件上执行的任务只能够顺序执行。硬件为FPGA,被划分为静态区域和若干个部分重构区域,静态区域内的任务保持不变,部分重构区域内的任务可以根据需要进行重新配置,却会导致额外的时间消耗,重新配置通过内部配置端口(ICAP)进行,该端口在一般情况下只有一个。

1.2 部分重构模型候选集

在目前工业界普遍采用的动态可重构设计流程[9]中,设计者需事先选取若干个矩形区域作为部分重构区域(PR Regions),在每个部分重构区域里,有一组部分重构模型(PR Modules),对应的功能模块在调度上不会同时运行,可以根据需要在重构区域内进行切换。

一般来说,部分重构模型的选取是由设计者根据自身经验决定的,但也可以利用高层次的任务依赖图来产生部分重构模型候选集[10]

1.3 任务信息及约束

给定图2的任务依赖图和部分重构模型的候选集,可以通过以下参数来描述一个任务:

1) 执行时间即硬件和软件执行时间;

2) 资源消耗即占用的硬件资源;

3) 重构时延即同一部分重构区域内切换任务所用的时间。

图2 任务依赖图

软硬件划分的目标是使应用程序的总执行时间最小,也就是在满足目标系统带来的约束下,使任务依赖图的总时延(最长路径的时延)最小。经过算法处理,最终得到图3的任务调度图,每个任务都分配到软件或者硬件(静态区域或部分重构区域)执行。 其中HS表示软硬件数据传输的延迟,RL表示在同一个部分重构区域内不同模型进行切换的时间消耗。

图3 软硬件划分结果
2 混合式优化算法流程 2.1 MILP建模

传统的面向软硬件划分的MILP模型以单位时间片段进行划分,变量和约束的规模随着应用的复杂化急剧增加。传统的方法无法有效地解决面向基于区域的可重构设计,因此本文参考文[11],以任务依赖图为出发点,根据各种约束形成MILP的模型,有效地降低了模型的复杂度,其中PRm表示可重构区域m

2.1.1 和结点有关的变量

hihi=1表示任务i被分配到硬件上执行,hi=0表示任务i被分配到软件上执行。

uij: 任务i被在同一个重构区域内的任务j替代,则uij=1; 否则 uij=0。

hsij: 当且仅当任务i和j被分配到同一个计算单元(软件或者硬件)的时候 hsij=0; 否则 hsij=1。

yij: 任务i在任务j开始之前完成,则yij=1; 否则yij=0。

sijkl: 如果任务i需要被重新配置为任务j,任务k需要被重新配置为任务l,并且前一个配置先进行,则有 sijkl=1; 否则sijkl=0 。

hhij: 如果任务i和任务j都被分配到硬件上并且在同一个重构区域内,那么hhij=1; 否则 hhij=0。

THi: 任务i在硬件上的执行时间。

TSi: 任务i在软件上的执行时间。

HS: 硬件和软件的通信时间。

RLm: 重新配置重构区域m内任务需要的时间。

C: 一个足够大的常量。

TNCLB: 总的硬件可用资源。

delay: 总延迟。

ti: 任务i的开始时间。

end_ti: 任务i的结束时间。

sAij: 任务i和j中占用硬件资源最少的任务所占用资源。

tRijm: 重构区域m内任务i和j的重构的开始时间。

NCLBi: 任务i占用的硬件资源。

2.1.2 目标和约束:

优化问题表示如下:

min delay, (1)
s.t. delayti+hi×THi+(1-hi)TSi,∀taski∈T; (2)
ti+hi×THi+(1-hiTSi+HS×hsijtj; (3)
ti+TSiTj+(hi+hj+1-yij)C; (4)
tj+TSjTi+(hi+hj+yij)C; (5)
$$\sum\limits_{tas{k_i} \in T} {{h_i}} \times {N_{CLB}}^i - \sum\limits_{{\rm{P}}{{\rm{R}}_m} \in E} {\sum\limits_{tas{k_i} \in P{R_m}} {\sum\limits_{tas{k_i} \in P{R_m},i \ne j} {{u_{ij}}} } } \times s{A_{ij}} \le T{N_{CLB}}$$ (6)
ti+THitRijm+(2-hhijuij)C; (7)
tRijm+RLmtj+(2-hhijuij)C; (8)
tj+THjtRijm+(2-hhijuji)C; (9)
tRijm+RLmti+(2-hhijuji)C; (10)
tRijm+RLmtRkln+(2-hhijhhkl+1-sijkl)C; (11)
tRkln+RLntRijm+(2-hhijhhkl+1-sklij)C. (12)

式(1)表示目标是最小化总延迟delay。式(2)表示delay不小于每个任务的结束时间。式(3)表示数据依赖约束: 如果任务i和j之间有数据依赖关系,那么任务j不能在任务i完成之前开始。式(4)和(5)表示软件资源冲突约束: 如果任务i和任务j之间没有数据依赖并且都被分配到软件上执行,它们之间应该有先后顺序。式(6)表示硬件资源约束: 硬件上的任务所占用的资源不能超过硬件总的可用资源。式(7)-(10)表示重构花销的影响: 任务之间的重新配置需要花费一定的时间,一个任务不能在它重构完成之前开始。式(11)和(12)表示单重构控制器约束: 一般来说,只有一个重构控制器,所以同时只能进行一个重构。

2.1.3 对MILP的分析

基于以上的变量和公式,软硬件划分问题被完全数学化,通过求解便可以得到精确的最优解。但是,随着问题规模即任务个数的增加,变量和约束的个数随之迅速增加,求解非常困难。

综合分析MILP的模型会发现,在基于区域的动态部分重构的软硬件划分算法模型的复杂性体现为:

1) 任务状态的多样性。

传统的软硬件划分只需要考虑软件和硬件这2种状态,而在考虑动态部分重构的情况下,硬件又被分为静态区域和部分重构区域这2种情况。

2) 任务状态的相互关联性。

在传统的划分方法中,任务之间的关系仅限于数据依赖; 而考虑动态部分重构之后,任务和任务之间的关系变得更加复杂,2个同时被分配到硬件上执行的任务可能在同一片重构区域内,与此直接对应的变量包括hhijuij; 此外,不同区域之间的重构顺序也增加了彼此的关联,使问题变得更加复杂,对应的约束为式(11)和(12)。

3) 任务状态的影响。

一个任务的状态会影响其他任务的状态以及资源和时延的计算。如果它被分配到部分重构区域内,资源的计算需要取该区域内任务消耗资源的最大值,程序的执行时间也需要考虑重构代价,相应的约束对应式(6)-(10),这些都增加了MILP的复杂性。

通过上述分析可以发现,决定一个任务的状态可以决定与之相关的变量如hi的取值,事先满足式(6)-(12)对应的约束,从而减少约束数量,减小搜索空间,缩短求解时间。本文通过选择关键任务即预期能够获取最大的时间和资源收益的任务,并且事先确定它们的状态,来删减和修改对应的约束,减小问题的规模。

2.2 面向关键任务的启发式算法 2.2.1 关键任务的选取及MILP的修改

由节2.1可知,为减少约束数量,需要选择关键任务并确定它们的状态。由于优化目标是程序的执行时间,因此运行时间是首先考虑的因素; 除此之外,由于硬件资源是有限的,因此还要比较任务对资源的占用情况。

为了快速确定关键任务和它们的状态,本文采用基于贪婪规则的启发式算法,从时间和资源两方面来衡量任务能获得的最大收益。

为了方便描述,本文有以下定义:

定义1 状态候选集: 每一个任务在软硬件划分设计中可以被分配到软件上、硬件的静态区域或者重构区域内,这三者构成了任务的状态候选集,分别用 ssshsr表示。

定义2 状态迁移收益: 在软硬件划分的每个阶段,每个任务都拥有一个初始状态 so,当任务i从状态so被移动到一个新状态sn(n∈{s,h,r})时,程序的执行时间和硬件资源会产生相应的变化,从而获取收益benifitsoi->sn,也就是状态迁移收益。

benifitsoi->sn=(CA×ΔA+Cd×ΔdAunused/Ai. (13)

其中: Δd 表示状态sosn下延迟的差值; ΔA表示状态snso下硬件剩余可用资源的差值,Ai表示任务i占用的硬件资源,Aunused表示状态sn下硬件上剩余的可用资源; CACd 分别表示衡量资源和时间影响的权重。由于时延是主要的优化目标,因此占有较大的权重,在本文中,CA=-1,Cd=19。

使状态迁移收益最大的Sn为该任务的关键状态,最大的状态迁移收益为该任务的收益benifiti:

benifiti=max{benifitsoi->sn|n=s,h,r} . (14)

定义3 关键任务: 对每个任务,计算出它们的关键状态以及在关键状态下的收益benifiti,其中收益最大的便是关键任务keytask

keytask=taski | benifiti= max{benefitk | k=1,2,…}. (15)

根据关键任务和它的关键状态,对MILP中的变量和约束进行修改和删减。

2.2.2 启发式算法流程

图2表1的输入为例说明启发式算法的具体过程。任务1和5构成重构模块候选集1,任务3和4构成重构模块候选集2,重构的时间开销为2,软硬件之间数据传输的时间开销为1,总的硬件可用资源为7。

表1 任务基本信息
i占用的硬件资源THiTSi
1213
2323
34311
4325
5237

开始的时候,所有任务都被分配在软件上,总延迟为29,剩余面积为7即Aunused=7。考虑任务1,它可以被分配到软件上、硬件的静态区域上或者重构区域上(因为此时重构区域内没有其他任务,所以不用考虑重构开销)。如果任务1仍然在软件上运行,ΔA 和 Δd 都是0,因此benifitso1->ss为0; 如果任务1在硬件上运行,总延迟为28,因此Δd=1,又ΔA=2,则

benifits1o->sh=benifits1o->sr= (-1×2+19×1)×5/2=42.5.

因此,任务1的关键状态为sh,改变任务1的状态的最大收益为42.5。以此类推,改变任务2的状态的最大收益为72,改变任务3的状态的最大收益为111,改变任务4的状态的最大收益为153.75,改变任务5的状态的最大收益为327.5。改变任务5的状态的最大收益最大,所以在第一次迭代中,任务5为关键任务,它的关键状态为sh,也就是任务5应该被分配到硬件上执行。继续迭代,每轮确定一个关键任务以及关键状态,直到达到终止条件。

注意到随着启发式的选择,越来越多的任务被分配到硬件上执行,单个任务的影响也变得越来越大。为了不使单个任务的影响过大从而影响最终解,启发式过程在被分配到硬件上执行的任务占用的资源与总的硬件资源的比例p达到阈值时停止。

启发式算法的步骤如下:

1) 对每个未决定状态的任务,计算其在每个状态的收益,选取最大的收益作为该任务的收益,对应的状态为该任务的关键状态;

2) 选取收益最大的任务作为关键任务,并更新其状态;

3) 判断p是否比阈值小,是则结束,否则返回步骤1。

当被使用的硬件资源达到事先设定的阈值时,迭代过程就会停止,从而减小了落入局部最优解的几率。在每次迭代过程中,影响最大的任务(关键任务)被选择,从而保证解的质量。在迭代结束之后,得到一些关键任务,并且决定了它们应该被分配到哪里,同时没有使精度下降太多。

在启发式算法终止之后,统一对MILP的约束和变量进行删减和修改,达到减小规模的目的。

2.3 混合式算法流程概述

经过对前面的分析,可以发现,对于动态部分重构FPGA的软硬件划分而言,可以根据任务依赖图以及基本信息建立MILP模型,然后通过基于贪婪规则的启发式算法事先确定一些关键任务以及关键状态来减少MILP的约束以及变量,使解空间变小,进而缩短求解时间。

作为简化,可以先不建立MILP模型,而是在启发式算法来确定关键任务以及关键状态之后,把剩余的问题建模为MILP模型。本文把启发式算法的求解速度和MILP的全局搜索能力结合起来,形成两阶段的加速算法: 在初始时刻,所有的任务都被分配到软件。在第一阶段即启发式阶段,选定一些可以有效减小程序运行时间的关键任务和其状态; 在第二阶段即MILP阶段,把剩下的问题建模成为MILP公式并且求解。

例如图4中,先把所有的任务分配到软件上执行,在启发式阶段,通过反复迭代来确定关键任务的状态(分配到硬件上、软件上还是可重构区域里),得到中间结果: 任务3和5对整体性能的影响最大,被标记为关键结点,并且被分配到硬件上执行。其余的任务保持在软件执行的状态,等待进一步的优化。

图4 算法流程

在第二阶段,剩余部分被建模为MILP公式,已经决定的任务状态直接作为已知量使用,减少约束的数量。通过求解MILP,可以得到图3的最终结果,包含软硬件划分结果以及任务的调度时序。

3 实 验

为了表明算法的有效性,本文进行了一系列的实验,并且对实验结果进行了详细的分析。

3.1 实验设置

本文采用Xilinx Virtex-5系列的 XC5VLX 330T开发板作为目标芯片,使用ICAP来进行动态重构。根据硬件参数,任务在软件上的执行时间通常比硬件上的要长3~5倍。测试用例包括CHStone_v1.7_121031[12]和ExPRESS[13]中的部分例子,以及随机生成的若干测试用例。通过高层次工具对测试用例进行了适应化处理,得到符合程序输入的用例信息。

3.2 阈值的选择

在节2.2.2 中提到启发式阶段的终止条件,是硬件资源的占用率达到事先指定的阈值。阈值的影响见表2,其中: 可有资源比例表示硬件总的可用资源与所有任务占用的硬件资源之比; N表示在启发式阶段选定的任务数目; TMILP表示MILP阶段求解所花费的时间,启发式阶段的时间可以忽略。

表2 停止条件对算法的影响
测试用例任务数目可用资源比例/% N TMILP/s delay
阈值=50%60%70%50%60%70%50%60%70%
8_node8 100678000181818
80556000181818
60355000181818
40334000363636
gsm11 100899000212121
80789000212121
60778000272527
40557210555555
15_node15 100101214000171717
8091011100232323
60799500323232
40677110474747
20_node20 100151920000373737
80121415000373737
60101214810383844
4067101683777777
arf28 100192122000353535
80161820000353535
60121516860383838
40101113>1 80010536838387

阈值会影响到TMILPdelay,因为阈值决定了启发式阶段的停止时间,影响了N的值。可以发现,阈值设置较低将会极大地影响求解效率,阈值偏高时,解的质量会降低。测试用例arf在阈值为50%时不能在可接受的时间内得到结果,在阈值为70%时无法得到较好的解。权衡运行时间和解的质量,本文中阈值设为60%

3.3 算法的效果

在阈值被确定为60%之后,将实验结果与单纯的MILP方法以及单纯的启发式方法进行了比较,结果如表3所示。Area表示硬件可用资源占所有任务需要的硬件资源之和的比例。

表3 实验结果对比
测试用例可用资源比例/% 求解时间/s delay 本文方法与MILP方法求解时间的加速比
MILP本文方法启发式方法MILP本文方法启发式方法
8_node 100<1<10181818-
80<1<10181820-
60<1<10181821-
401<10353636-
15_node 100<1<10171717-
802<10222321-
602<10293228-
406104547486
20_node 1001<10373737-
80<1<10373741-
601103838601
40>1 800808277123>225
Gsm 1001<10212121-
801<10212125-
605<10252528-
40101051556810
cos1 100<1<10262626-
804202626342
60670134139878875
40>1 80019015243185204>9.4
Ewf 100<1<10454545-
809804545491.125
60>1 800403575962>45
40>1 80018559091109>9.7
Arf 100<1<10353535-
80<1<10353543-
6045623838487.5
40>1 80010539283103>17.14

可以发现,启发式方法的求解时间最短,但是求解精度较差。与MILP相比,启发式求解的时间可以忽略不计,因此在计算本文方法的求解时间时,采用启发式获取关键任务状态的时间并未计算在内。本文使用lingo[14]来对MILP进行求解,由于软件的限制,求解时间最多精确到秒,问题规模过大时,无法在短时间内得到结果,因此采用1 800 s时得到的解作为最终解,对应的求解时间表示为大于 1 800 s。

与MILP方法相比,本文方法可以在更短的时间内得到几乎相同的解。当2种方法都可以得到最终解的时候如8_node和gsm等测试用例,本文方法有着1~10倍的加速比。当问题规模增加到MILP方法不能在有限时间内得到最终解的时候如测试用例20_node,本文方法依旧可以得到最终解,加速比达到了225。可以发现,与MILP算法相比,本文方法能够处理更大规模的问题,而且能够在更短的时间内求得最优解或者近似最优解,表明本文方法具有足够的可用性。

4 结 论

本文针对基于动态部分重构FPGA的软硬件划分算法进行了研究,并且使用混合式两阶段方法进行了优化。通过把启发式方法和MILP方法结合起来,具有前者快速求解的优点,也充分利用了MILP的全局搜索能力。实验结果表明本文方法可以得到与MILP几乎一样的解,但是求解时间却大大缩短。此外,本文的工作具有很强的扩展性。

参考文献
[1] 张良, 徐成, 田峥, 等. 基于贪心算法和模拟退火算法的软硬件划分[J]. 计算机应用, 2013(07):1898-1902. ZHANG Liang, XU Cheng, TIAN Zheng, et al. Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm[J]. Journal of Computer Applications, 2013(7):1898-1902. (in Chinese)
[2] 李正民, 郭金金, 吕莹莹. 一种嵌入式系统软硬件划分算法[J]. 计算机仿真, 2011(10):204-207. LI Zhengmin, GUO Jinjin, LV Yingying. Simulation research on HW-SW partitioning of embedded system based on ant colony algorithm[J]. Computer Simulation, 2011(10):204-207. (in Chinese)
[3] 李春江. 面向动态可重构片上系统的过程级软硬件划分方法研究[D]. 长沙:湖南大学, 2010. LI Chunjiang. Research on Hardware and Software Partitioning Method on Process Level for Dynamically Reconfigurable System-on-Chip[D]. Changsha:Hunan University, 2010. (in Chinese)
[4] Niemann R, Marwedel P. Hardware/software partitioning using integer programming[C]//European Design and Test Conference. Paris, France:IEEE Press, 1996:473-479.
[5] Cordone R, Redaelli F, Redaelli M A, et al. Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAs[J].Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2009,28(5):662-675.
[6] 王璞, 武继刚. 高效软硬件划分算法及其提升技术[J]. 计算机科学, 2012(1):290-294. WANG Pu, WU Jigang. Efficient heursitic and tabu search for hardware/software partitioning[J]. Computer Science,2012(1):290-294. (in Chinese)
[7] Banerjee S, Bozorgzadeh E, Dutt N D. Integrating physical constraints in HW-SW partitioning for architectures with partial dynamic reconfiguration[J].Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 2006,14(11):1189-1202.
[8] LIU Peng, WU Jigang, WANG Yongji. Integrated heuristic for hardware/software co-design on reconfigurable devices[C]//Parallel and Distributed Computing, Applications and Technologies (PDCAT). Beijing, China:IEEE Press, 2012:370-375.
[9] Xilinx. Partial Reconfiguration User Guide.[EB/OL].[2015-01-15]http://www.xilinx.com/support/documentation/sw_manuals/xilinx14_7/ug702.pdf.
[10] HE Running, MA Yuchun, ZHAO Kang, et al. ISBA:An independent set-based algorithm for automated partial reconfiguration module generation[C]//International Conference on Computer-Aided Design (ICCAD). San Jose, CA, USA:IEEE Press, 2012:500-507.
[11] MA Yuchun, LIU Jinglan, ZHANG Chao, et al. HW/SW partitioning for region-based dynamic partial reconfigurable FPGAs[C]//Computer Design (ICCD), IEEE International Conference on, Seoul, Korea, IEEE Press, 2014:470-476.
[12] Hara Y, Tomiyama H, Honda S, et al. Proposal and quantitative analysis of the CHStone benchmark program suite for practical C-based high-level synthesis[J]. Journal of Information Processing, 2009(17), 242-254,
[13] UCSB. Benchmark[EB/OL].[2015-01-15]http://express.ece.ucsb.edu/benchmark/.
[14] Lindo. Lindo Software Products[EB/OL].[2015-01-15]http://www.lindo.com.